Улучшим план перевозок

Построим для клетки (2,4) в таблице 5 замкнутый цикл: (2,4), (2,2), (3,2), (3,4). Припишем знаки «+» и «–» вершинам цикла, начиная с клетки (2,4), последовательно чередуя их. Найдем число и переместим его по циклу: вычтем 100 из значений отрицательных клеток и прибавим 100 к значениям положительных. В результате клетка (2,4) стала занятой, , а две клетки (2,2) и (3,4) освободились.

Таблица 6

Запасы груза	Потребности в грузе
		4

В новом плане перевозок заполненных клеток 5, а должно быть . Из двух освободившихся клеток (3,4) и (2,2) заполним базисным нулем клетку (3,4), так как ей соответствует меньшая стоимость перевозок , а клетку (2,2) оставим свободной.

Таблица 7

Запасы груза	Потребности в грузе

Получим таблицу 7 с новым опорным планом перевозок , для которого транспортные расходы равны .

Проверим правильность расчетов, используя формулу (11.7):

.

7) Проверим решение на оптимальность.

Найдем потенциалы и из новой системы уравнений, составленных для заполненных клеток таблицы 7:

При получим одно из решений этой системы:

a₁ = 1, a₂ = 0, a₃ = 0, b₁ = 1, b₂ = 3, b₃ = 1, b₄ = 2.

Все оценки свободных переменных положительны:

D11 = с11 + a1 - b1 = 3 + 1 – 1 = 3;	D12 = с12 + a1 - b2 = 6 + 1 – 3 = 4;
D13 = с13 + a1 - b3 = 5 + 1 – 1 = 5;	D23 = с23 + a2 - b3 = 3 + 0 – 1 = 2;
D22 = с22 + a2 - b2 = 4 + 0 – 3 = 1;	D31 = с31 + a3 - b1 = 4 + 0 –1 = 3.

Отсутствие отрицательных оценок является признаком оптимальности плана перевозок , при котором значение целевой функции минимально и равно .

8) Дадимэкономическое истолкование оптимального решения.

Для того, чтобы затраты на перевозку груза из пунктов , , были наименьшими и составляли 2200, нужно отправить: 1) 100 ед. груза из в ; 2) 300 ед. груза из в и 100 ед. из в ; 3) 500 ед. груза из в и 100 ед. груза из в .

Дата добавления: 2014-01-07