Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i+ v_j> c_ij

(3;1): 4 + 1 > 3; ∆₃₁= 4 + 1 - 3 = 2 > 0

(3;4): 4 + 3 > 5; ∆₃₄= 4 + 3 - 5 = 2 > 0

max(2,2) = 2

Выбираем максимальную оценку свободной клетки (3;1): 3

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

	1	2	3	4	Запасы
1	7	4[150][+]	9	3[250][-]	400
2	2[450] [-]	11	8	4[100] [+]	550
3	3[+]	8[100] [-]	6[200]	5	300
Потребности	450	250	200	350

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

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

	B1	B2	B3	B4	Запасы
A1	7	4[250]	9	3[150]	400
A2	2[350]	11	8	4[200]	550
A3	3[100]	8	6[200]	5	300
Потребности	450	250	200	350

---

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i+ v_j= c_ij, полагая, что u₁= 0

u₁+ v₂= 4; 0 + v₂= 4; v₂= 4

u₁+ v₄= 3; 0 + v₄= 3; v₄= 3

u₂+ v₄= 4; 3 + u₂= 4; u₂= 1

u₂+ v₁= 2; 1 + v₁= 2; v₁= 1

u₃+ v₁= 3; 1 + u₃= 3; u₃= 2

u₃+ v₃= 6; 2 + v₃= 6; v₃= 4

	v1=1	v2=4	v3=4	v4=3
u1=0	7	4[250]	9	3[150]
u2=1	2[350]	11	8	4[200]
u3=2	3[100]	8	6[200]	5

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i+ v_j≤ c_ij.

Минимальные затраты составят: F(x) = 4*250 + 3*150 + 2*350 + 4*200 + 3*100 + 6*200 = 4450

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 2-й магазин (250 ед.), в 4-й магазин (150 ед.)

Из 2-го склада необходимо груз направить в 1-й магазин (350 ед.), в 4-й магазин (200 ед.)

Из 3-го склада необходимо груз направить в 1-й магазин (100 ед.), в 3-й магазин (200 ед.)

---

Смотрите также файлы

• Министерство науки и высшего образования российской федерации выксунский филиал.docx

• Руководство по глушению скважины порядок заполнения листа глушения.docx

• Бельдина Оксана Геннадьевна предмет гражданского правапредмет это общественные.pdf

• Исследование распределения токов и напряжений в трёхфазных цепях, соединённых звездой.docx

• Сабаты таырыбы Онды блшектерді 10 100 1000 жне 0,1 0,01 0,001 сандарына кбейту жне блу.doc