Слишком сложно? Тогда запросите консультацию специалиста!
Наша компания занимается тем, что помогает студентам выполнять различные учебные работы на заказ. Вы можете ознакомиться с перечнем выполняемых работ, а так же с их стоимостью на странице с ценами.
Преобразуем матрицу стоимости
| 0 | 9 | 0 | 11 | 0 |
| 0 | 13 | -1 | 0 | -2 |
| 5 | 12 | 0 | 15 | 0 |
| 1 | 0 | -11 | 8 | 0 |
| 2 | 30 | 16 | 25 | 0 |
Т.к. матрица содержит отрицательные элементы, то план не является оптимальным.
7. Выбираем максимальный по модулю отрицательный элемент матрицы (-11).
8. Из клетки этого элемента строим цикл по другим выделенным элементам, вершины нумеруем.
| 0 | 9 | 0 | 11 | 0 |
| 0 | 13 | -1 | 0 | -2 |
| 5 | 12 |  II 0
| 15 | III0 |
| 1 | 0 | I -11 | 8 | IV0 |
| 2 | 30 | 16 | 25 | 0 |
9. Найденный цикл переносим на транспортную таблицу. Из четных вершин цикла, выбираем вершину с минимальным объемом перевозок: 185; 30.
Таким образом min=30.
| 14513 | 9 | 13 | 6 | 1514 |
| 15520 | 20 | 19 | 245 2 | 19 |
| 10 | 4 | II 5 185
| 2 | III 685 |
| 19 | 205 | I7 | 8 | IV1930 |
| 3 | 18 | 17 | 8 | 402 |
10. Из четных вершин этот объем вычитается, а в нечетных прибавляется.
Получаем новый план.
| 14513 | 9 | 13 | 6 | 1514 |
| 15520 | 20 | 19 | 2452 | 19 |
| 10 | 4 | 155 5 | 2 | 1152 |
| 19 | 20 5 | 30 7 | 8 | 19 |
| 3 | 18 | 17 | 8 | 402 |
11. Определяем новые затраты.
, 
(ден.ед).
12. Проверяем новый план на оптимальность, выполняя вновь пункты с 5 по 11.
| -13 | -11 | -13 | -14 |  vi
ui
| |
| 13 | 9 | 13 | 6 | 14 | |
| 20 | 20 | 19 | 2 | 19 | -7 |
| 10 | 4 | 5 | 2 | 6 | |
| 19 | 5 | 7 | 8 | 19 | |
| 3 | 18 | 17 | 8 | 2 |
| 0 |   I-2
| 0 | 11 |  II0
|
| 0 | 2 | -1 | 0 | -2 |
| 5 | 1 |   IV0
| 15 | III0 |
| 12 |  VI0
| V0 | 19 | 11 |
| 2 | 19 | 16 | 25 | 0 |
Найденный цикл переносим на транспортную таблицу. Из четных вершин цикла, выбираем вершину с минимальным объемом перевозок: 15; 155, 20.
Таким образом min=15.
| 145 13 |  I 9
| 13 | 6 | II1514 |
| 15520 | 20 | 19 | 2452 | 19 |
| 10 | 4 | IV 5155 | 2 | III 6115 |
| 19 | VI 520 | V 730 | 8 | 19 |
| 3 | 18 | 17 | 8 | 402 |
| 145 13 | 159 | 13 | 6 | 14 |
| 15520 | 20 | 19 | 245 2 | 19 |
| 10 | 4 | 1405 | 2 | 1302 |
| 19 | 5 5 | 45 7 | 8 | 19 |
| 3 | 18 | 17 | 8 | 40 2 |
Определяем новые затраты.
, 
(ден. ед.)
| -13 | -9 | -11 | -12 |  vi
ui
| |
| 13 | 9 | 13 | 6 | 14 | |
| 20 | 20 | 19 | 2 | 19 | -7 |
| 10 | 4 | 5 | 2 | 6 | |
| 19 | 5 | 7 | 8 | 19 | |
| 3 | 18 | 17 | 8 | 2 |
| 0 | 0 | 2 | 11 | 2 |
| 0 | 4 | 1 | 0 | 0 |
| 3 | 1 | 0 | 13 | 0 |
| 10 | 0 | 0 | 17 | 11 |
| 0 | 19 | 16 | 23 | 0 |
Т.к. преобразованная матрица в базисных клетках содержит нули, а элементы в остальных клетках неотрицательные, то полученный план является оптимальным.
Таким образом, необходимо осуществить 9 перевозок по следующим маршрутам:
Суммарные затраты при перевозках составят: F=7510 (ден. ед.).
