Транспортная задача на минимум
Метод сечения Гомори
Допустим мы решали задачу и получили последнюю таблицу без учета целочисленности
Б
| Xопт
| x1
| x2
| . . . .
| xm
| ω1
| ω2
| . . . .
| ωn
| x1
| β1
|
|
| :
|
| α11
| α21
| . . . .
| α1n
| x2
| β1
|
|
| :
|
| α21
| α22
| . . . .
| α2n
| . . . .
| . . . .
| . . . .
| . . . .
| . . . .
| . . . .
| . . . .
| . . . .
| . . . .
| . . . .
| xn
| βn
|
|
| :
|
| αm1
| αm2
| . . . .
| αmn
| z
| β0
|
|
| :
|
| c1
| c2
| . . . .
| cn
| Если βi – целые, то задача решена; иначе выбирают βi с наибольшей дробной частью и выписывают уравнение из таблицы.
По условию целочисленности xi, ωi – целые.
Чтобы уравнять обе части мы добавляем искусственную переменную
К полученной таблице добавляется строка, соответствующая отсечению Гомори, в столбце Xопт стоит – fi (т.е. отрицательное число). А так как в столбце Xопт стоит отрицательное число – поэтому применяем двойственный симплекс-метод.
пример. max z = 7x1 + 9x2.
Б
| С
| Xопт
|
|
|
|
| r
|
| x1
| x2
| s1
| s2
| s1
|
|
| – 1
|
|
|
|
|
| s2
|
|
|
|
|
|
|
|
| z
|
|
| – 7
| – 9
|
|
|
|
| x2
|
|
| – 1/3
|
| 1/3
|
|
|
| s2
|
|
| 22/3
|
| – 1/3
|
|
|
| z
|
|
| – 10
|
|
|
|
|
| x2
|
| 7/2
|
|
| 7/22
| 1/22
|
|
| x1
|
| 9/2
|
|
| – 1/22
| 3/22
|
|
| z
|
|
|
|
| 28/11
| 15/11
|
|
|
Б
| С
| Xопт
| x1
| x2
| s1
| s2
| R1
|
| x2
|
| 7/2
|
|
| 7/22
| 1/22
|
|
| x1
|
| 9/2
|
|
| – 1/22
| 3/22
|
|
| z
|
|
|
|
| 28/11
| 15/11
|
|
| R1
|
| – 1/2
|
|
| – 7/22
| – 1/22
|
|
|
Б
| С
| Xопт
| x1
| x2
| s1
| s2
| R1
| R2
| x2
|
|
|
|
|
|
|
|
| x1
|
| 32/7
|
|
|
| 1/7
| – 1/7
|
| s1
|
| 11/7
|
|
|
| 1/7
| – 22/7
|
| z
|
|
|
|
|
|
|
|
| R2
|
| – 4/7
|
|
|
| – 1/7
| – 67
|
| x2
|
|
|
|
|
|
|
|
| x1
|
|
|
|
|
|
| – 1
|
| s1
|
|
|
|
|
|
| – 4
|
| s2
|
|
|
|
|
|
|
| – 7
| z
|
|
|
|
|
|
|
|
| Итак, x1 = 4; x2 = 3; max z = 55; s1 = 1; s2 = 4; R1 = 0; R2 = 0.
Транспортная задача на минимум
пример. На трех базах Б1; Б2; Б3 находится однородный груз. Этот груз необходимо доставить в пять пунктов П1, П2, ... , П5. Запасы груза на трех базах ai и потребности пунктов bj указаны в таблице. Стоимость перевозки одной тонны груза с базы Бi в пункт Пj (Бi → Пj) равная cij рублей. Спланировать их перевозки так, чтобы их стоимость была наименьшей.
| П1
| П2
| П3
| П4
| П5
| ai
| Б1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| bj
|
|
|
|
|
|
| 1 способ. Симплекс метод
xij – перевозка Бi → Пj
2 способ. Метод потенциалов
1 этап. Составить начальный план.
Показатели плана записываются только в клетки с оценками, xij ³ 0.
Для построения начального решения используются следующие методы.
1 метод – Метод северо-западного угла
Заполняют верхнюю левую клетку, записывая туда максимально возможное значение, затем переходят к соседней клетке.
| П1
| П2
| П3
| П4
| П5
| ai
| Б1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| bj
|
|
|
|
|
|
| Показатель левой верхней клетки выбирается равным наименьшему значению из заданных сумм по первой строке и по первому столбцу. Дальше заполняется соседняя клетка.
2 метод – минимальный элемент по строке
| П1
| П2
| П3
| П4
| П5
| ai
| Б1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| bj
|
|
|
|
|
|
| Сначала заполняется первая строка, для этого в ней выбирается клетка с минимальной стоимостью перевозки и заполняется максимально возможным значением. Затем переходят к клетке со следующей по величине стоимостью перевозки и т.д., пока не будет исчерпан запас первой строки. Затем переходят ко второй строке, процесс повторяется.
3 метод – минимальный элемент по столбцу. Аналогично вышеизложенному.
4 метод – метод минимального элемента.
| П1
| П2
| П3
| П4
| П5
| ai
| Б1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| bj
|
|
|
|
|
|
| Выбираем наименьший элемент по стоимости по всей таблице. Ставим туда максимально возможное значение.
2 этап. Проверка плана на оптимальность. Пусть таблица содержит m строк и n столбцов. Полученный начальный план называется невырожденным, если число его заполненных клеток не меньше, чем m + n – 1.
Рассмотрим план северо-западного угла.
Заполненных клеток 7.
m + n – 1 = 5 + 3 – 1 = 7 Þ план невырожденный.
В этом случае система потенциалов строится таким образом.
αi – потенциалы строк.
βj – потенциалы столбцов.
Положим α1 = 0, остальные потенциалы считают из условия: для заполненных клеток cij = αi + βj.
| П1
| П2
| П3
| П4
| П5
|
| αi
| Б1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| βj
|
|
|
|
|
|
|
| Отступление.Для вырожденного плана.
например:
| П1
| П2
| П3
| П4
| αi
| Заполненных клеток 6.
m + n – 1 = 4 + 4 – 1 = 7
1. Потенциал строки с наибольшим количеством заполненных клеток положим равным нулю.
2. Далее по общему правилу пока это возможно вычисляем потенциалы. Остались две незаполненные клетки.
Далее невозможно.
| Б1
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б2
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б4
|
|
|
|
|
|
|
|
|
|
|
|
|
| βj
|
|
|
|
|
| В свободные клетки с наименьшей стоимостью, для которой потенциал еще не просчитан ставим ноль (т.е. появляется нулевая перевозка) клетка становится условно заполненной.
Условие оптимальности плана
cij ³ αi + βj – признак оптимальности плана.
Так как для занятых клеток условие выполняется по построению потенциалов, то проверяем только свободные.
cij –(αi + βj) ³ 0
| П1
| П2
| П3
| П4
| П5
| αi
| Б1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б2
|
|
|
|
| –
|
| +
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
| +
|
| –
|
|
|
|
|
|
|
|
|
| βj
|
|
|
|
|
|
|
Б1П3
| 7 – (0 + 6) ³ 0
| хорошая клетка
| Б1П4
| 7 – (4 + 0) ³ 0
| хор.
| Б1П5
| 3 – (0 + 3) = 0
| хор.
| Б2П1
| 6 – (5 + 1) = 0
| хор.
| Б2П5
| 5 – (3 + 1) ³ 0
| хор.
| Б3П1
| 8 – (5 + 2) ³ 0
| хор.
| Б3П2
| 6 – (2 + 6) = – 2
| плохая
| Б3П3
| 5 – (6 + 2) = – 3
| плохая
| Значит план неоптимален, его надо улучшать.
3 этап. Построение цикла перевозки. Здесь мы выбираем самую плохую клетку Б3П3, в нее помещаем вершину.
Цикл – это прямоугольник, начальная вершина которого находится в самой плохой клетке, а остальные вершины только в заполненных клетках. Начальная вершина отмечается знаком «плюс» (+), далее в порядке чередования ставятся знаки «–», «+».
Выберем объем дополнительной перевозки – это будет минимальная перевозка, отмеченная знаком «–».
θ = min (285; 660) = 285.
Прибавим её в клетках со знаком «+» и отнимем в клетках со знаком «–». Таким образом мы пересчитаем план и все начнется сначала.
| П1
| П2
| П3
| П4
| П5
| αi
| Б1
|
|
| –
|
|
|
|
|
| +
|
|
|
|
|
|
|
| Б2
|
|
| +
|
| –
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
| +
|
|
|
| –
|
| – 1
|
|
|
|
|
| βj
|
|
|
|
|
|
| θ = min (525; 375; 810) = 285.
| П1
| П2
| П3
| П4
| П5
| αi
| Б1
|
|
| –
|
|
|
|
|
| +
|
|
|
|
|
|
|
| Б2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
| +
|
|
|
|
|
| –
|
|
|
|
|
|
|
| βj
|
|
|
|
|
|
| θ = min (150; 435) = 150.
| П1
| П2
| П3
| П4
| П5
| αi
| Б1
| –
|
|
|
|
|
|
|
| +
|
|
|
|
|
|
|
| Б2
| +
|
| –
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
| +
|
|
|
|
|
| –
|
|
|
|
|
|
|
| βj
|
|
|
|
|
|
| θ = min (705; 285; 420) = 285.
| П1
| П2
| П3
| П4
| П5
| αi
| Б1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Б3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| βj
|
|
|
|
|
|
| с = 420 · 5 + 285 · 6 + 135 · 7 + 435 · 6 +660 · 5 + 555 · 5 + 810 · 3 = 15870.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|