План-1 |
40 |
70 |
30 |
10 |
|
30
| 5 -1 + | 3 1 | 6 20 − | 0 10 |
|
45
| 5 0 | 1 45 | 6 1 | 0 1 |
|
50
| 2 40 − | 7 9 | 2 + 10 | 0 4 |
|
25
| 8 1 | 3 25 | 7 0 | 0 -1 |
|
|
|
|
|
|
|
Проверим полученный план на оптимальность методом потенциалов:
а) Потенциалами строк –
и столбцов – 
называются числа, удовлетворяющие условию 
для базисных переменных (для заполненных клеток).
Так как система для определения потенциалов содержит на одно уравнение меньше, чем число потенциалов, то, чтобы найти решение системы потенциалов, один потенциал задаём произвольно, например, 
.
Остальные потенциалы найдём, решая систему уравнений:
б) Определяем характеристики для свободных клеток по формуле 
и запишем их в левом нижнем углу свободных клеток. План является оптимальным если все 
.
План 1 не оптимален, так как 
и 
.
Улучшим план. Выберем клетку с наименьшей отрицательной характеристикой, например, клетку (1,1) пометим знаком «+» и построим для неё контур:
(1,1)
(1,3)
(3,3) 
(3,1).
Контур удовлетворяет следующим условиям: это замкнутая ломаная, состоящая из вертикальных и горизонтальных отрезков; отрезки контура могут пересекаться; все вершины контура находятся в заполненных клетках, за исключением той клетки, для которой он строится; число вершин ─ чётное.
Клетки, в которых находятся вершины контура, поочередно помечаем знаками «+» и «─». Из клеток, помеченных знаком «─», выбираем наименьшую поставку 
. Число 
перераспределяется по контуру, в клетках со знаком «+» добавляется 
, в клетках со знаком «─» отнимается 
. После перераспределения груза, только одна вершина контура становится свободной.
Строим новый план перевозок.
План-2 |
40 |
70 |
30 |
10 |
|
30
| 5 20 + | 3 2 | 6 1 | 0 10 − |
|
45
| 5 1 | 1 45 | 6 2 | 0 1 |
|
50
| ─ 2 20 | 7 9 | + 2 30 | 0 3 |
|
25
| 8 1 | 3 25 | ─ 7 0 | + 0 -2 |
|
|
|
|
|
|
|
Затраты на реализацию плана 2 составляют: 
Найдем потенциалы строк и столбцов, для чего составим систему уравнений. Потенциал 
примем равным 0.
Определим характеристики для свободных клеток.
План 2 не является оптимальным, т. к. 
После применения, рассмотренного выше алгоритма, получили план 3.
План-3 |
40 |
70 |
30 |
10 |
|
30
| 5 20 | 3 0 | 6 1 | 0 10 |
|
45
| 5 2 | 1 45 | 6 3 | 0 2 |
|
50
| 2 20 | 7 7 | 2 30 | 0 3 |
|
25
| 8 3 | 3 25 | 7 2 | 0 0 |
|
|
|
|
|
|
|
План 3 является оптимальным, т, к. все 
. Затраты на реализацию оптимального плана составляют 
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
