В табл. 16 приведены потенциалы производителей и потребителей, псевдостоимости для нового опорного плана. В клетке (4,2) псевдостоимость превышает стоимость, следовательно, план не оптимален и необходимо загрузить клетку (4,2) путем циклического переноса.
Таблица 16.
объем потребления производства | 120 | 50 | 110 | 190 |
|
200 | 3 7 0 | 4 8 0 | 3 10 | 2 190 | 0 |
40 | 4 4 0 | 5 40 | 4 9 0 | 3 8 0 | 1 |
110 | 1 9 0 |
10 - |
100 + | 0 6 0 | -2 |
120 | 0 120 |
0 + | 0 0 - | -1 0 0 | -3 |
| 3 | 4 | 3 | 2 | итерация 2 |
объем
2
1
1 0
Выполняется фиктивный перенос по циклу 0 единиц груза. В результате меняется условно занятая клетка (вместо клетки (4,3) – занимается клетка (4,2)). Стоимость плана при этом не меняется. Полученная транспортная таблица приведена в табл. 17.
Таблица 17.
объем потребления производства | 120 | 50 | 110 | 190 |
200 | 7 0 | 8 0 | 3 10 | 2 190 |
40 | 4 0 | 5 40 | 9 0 | 8 0 |
110 | 9 0 | 2 10 | 1 100 | 6 0 |
120 | 0 120 | 0 0 | 0 0 | 0 0 |
В табл. 18 приведена транспортная таблица, соответствующая третьей итерации. В клетке (2,1) псевдостоимость превышает стоимость, поэтому клетка (2,1) загружается с помощью переноса груза по циклу.
Таблица 18.
объем потребления производства | 120 | 50 | 110 | 190 |
|
200 | 4 7 0 | 4 8 0 | 3 10 | 2 190 | 0 |
40 | 5 4
| 5
| 4 9 0 | 3 8 0 | 1 |
110 | 2 9 0 | 2 10 | 1 100 | 0 6 0 | -2 |
120 | 0
| 0 0 + | -1 0 0 | -2 0 0 | -4 |
| 4 | 4 | 3 | 2 | итерация 3 |
0 +
40 -
120 -По циклу переносится 40 единиц груза. Итоговая транспортная таблица приведена в табл. 19. Цена цикла равна -1, поэтому стоимость плана уменьшится на 40 единиц и составит: z=730-40=690.
Таблица 19.
объем потребления производства | 120 | 50 | 110 | 190 |
|
200 | 4 7 0 | 4 8 0 | 3 10 | 2 190 | 0 |
40 | 4 40 | 4 5 0 | 3 9 0 | 2 8 0 | 0 |
110 | 2 9 0 | 2 10 | 1 100 | 0 6 0 | -2 |
120 | 0 80 | 0 40 | -1 0 0 | -2 0 0 | -4 |
| 4 | 4 | 3 | 2 | итерация 4 |
Далее вычисляются потенциалы поставщиков, потребителей и псевдостоимости для свободных клеток. Так как для всех свободных клеток псевдостоимости не превышают стоимостей (табл. 19), полученный план перевозок оптимален, ему соответствует минимальная стоимость перевозки всех грузов.
Оптимальный план перевозок транспортной задачи в матричном виде:
.
Стоимость оптимального плана:
.
Контрольные вопросы
1. В чем специфика модели транспортной задачи как задачи линейного программирования? Какие методы применяются для решения транспортной задачи?
2. Что понимается под открытой и закрытой транспортными задачами? Как выполняется сведение открытой транспортной задачи к закрытому типу? В чем заключается условие баланса?
3. Для чего используются методы северо-западного угла и минимального элемента? В чем их суть? Сравните эти методы по эффективности.
4. Объясните шаги алгоритма метода потенциалов для решения транспортной задачи на произвольном примере.
5. Дайте определения понятиям: допустимый план, опорный план, вырожденный опорный план, оптимальный план, потенциал, псевдостоимость, цикл, перенос по циклу, цена цикла.
6. Дайте экономическую интерпретацию метода потенциалов.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
