Шаг 1. Определяем оценку для каждой свободной клетки

(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (1,3; 1,2; 2,2; 2,3;).

Оценка свободной клетки равна Д13 = (5) — (3) + (5) — (4) = 3.

(2;1): В свободную клетку (2;1) поставим знак «+».

Цикл приведен в таблице (2,1; 2,2; 1,2; 1,1;).

Оценка свободной клетки равна Д21 = (2) — (5) + (3) — (1) = -1.

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (2,1;) равные: (-1).

Переход от неоптимального опорного плана к лучшему.

Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (2;1) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 2) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1*30 + 3*60 + 2*30 + 4*60 = 510.

Шаг 2. Определяем оценку для каждой свободной клетки.

(1;3): В свободную клетку (1;3) поставим знак «+».

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,3;).

Оценка свободной клетки равна Д13 = (5) — (1) + (2) — (4) = 2.

(2;2): В свободную клетку (2;2) поставим знак «+».

Цикл приведен в таблице (2,2; 2,1; 1,1; 1,2;).

Оценка свободной клетки равна Д22 = (5) — (2) + (1) — (3) = 1.

Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции F невозможно, поскольку она достигла минимального значения.

Таким образом, последний опорный план является оптимальным.

Минимальные затраты составят:

• 1*30 + 3*60 + 2*30 + 4*60 = 510
• 2) Для исследования плана ТЗ на оптимальность сначала по занятым клеткам для нахождения потенциалов поставщиков и потребителей составляется и решается система уравнений вида Ui + Vj =, далее для всех незанятых клеток вычисляются оценки Sij по формуле: ij = Сij — (Ui + Vj).

Если хотя бы одна оценка отрицательна, то план не является оптимальным, его можно улучшить за счет загрузки клетки (k;l). Если таких клеток несколько, то наиболее перспективной для загрузки является клетка с наибольшей по абсолютной величине оценкой.

Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные расходы от загрузки данной клетки единицей груза.

Если все оценки S неотрицательны, то план является оптимальным. Если все оценки S, то оптимальный план единственен.

Если хотя бы одна оценка S, то ТЗ имеет бесконечное множество оптимальных планов с одним и тем же значением целевой функции.

Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой S. Если таких клеток несколько, то обычно выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой.

Для выбранной клетки строится замкнутый цикл (цикл перераспределения), начальная вершина которого лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках. Нельзя рассматривать как вершины клетки, в которых горизонтальные и вертикальные отрезки цикла пересекаются. Очевидно, число вершин цикла будет четным. Вершинам цикла приписываются поочередно знаки «+» и «?», начиная со знака «+» в выбранной свободной клетке. Из поставок в клетках цикла со знаком «?» выбирается наименьшее количество груза. На эту величину увеличиваются поставки в вершинах со знаком «+» и уменьшаются поставки в вершинах со знаком «?». Это правило гарантирует, что в вершинах контура не появится отрицательных поставок, начальная выбранная клетка окажется занятой, в то время как одна из занятых клеток при этом обязательно освободится.

Потенциалы подсчитаем непосредственно в таблице. Положим V2=0.

13 = 5- (3−1) = 3 21 = 2 — (5−2) = -1.

Так как среди оценок есть отрицательная, то план не является оптимальным. Надо улучшать план, загружая клетку (2,1).

Min (30, 60) = 30.

13 = 5- (3+0) = 2 22 = 5 — (4+0) = 1.

Так как среди оценок нет отрицательных (решаем задачу на минимум), то план является оптимальным.

Fmin = 30*1+60*3+30*2+60*4 = 510 ден. ед.

ХОПТИМ. =.