Главная | Обратная связь

Алгоритм решения задач линейного программирования симплекс методом.

Z(x)=-2x₁-3x₂ ->min

Шаг 1:Ввести 3 дополнит переменные и изменить знак целевой ф в результате - канонич форма ЗЛП.

z^*=(-2)*x₁+(-3)*x₂+0*x₃+0*x₄+0*x₅ ->min

+1*x₂+1*x₃+0*x₄+0*x₅ =6 3*x₁+1*x₂+0*x₃+1*x₄+0*x₅ =12 1*x₁+2*x₂+0*x₃+0*x₄+1*x₅ =10 x₁;x₂;x₃;x4;x5 ≥0

Шаг 2: В качестве опорного плана взять x⁽⁰⁾=(0,0,6,12,10),координаты вершины точки О(0;0) .

Шаг 3:Составить симплекс таблицу

i	Базис	Сб	Ао	С1= -2	С2= -3	C3=0	C4=0	C5=0
А1	А2	А3	А4	А5
	А3	0
	А4	0
	А5	0
	∆j

Порядок заполнения:В стлбц А₀ - правые части из системы ограничения.В 1-е 3 стрч и 5-ть стлц - коэффициенты из системы лин ограничений КЗЛП. 3 вектора (А₃ А₄ А₅) - стандартный базис 3-хмерного пространства.В верхней стрк (А₁ А₂ А₃ А₄ А₅ ) - соответствующие коэффициенты лин целевой ф. (z). В стлц «Сб» - коэф базисных векторов. В 4-ой стрк в стлц «А₀» - значение целевой ф. z^* для начального опорного плана: Z^*( ⁽⁰⁾)=C_б*А₀=0-6+0*12+0*10=0. Др клетки в 4-ой строке- оценки, опред по формуле:∆j=C_б*A_j-C_j

∆₁=0*1+0*3+0*1-(-2)=2; ∆₂=0*1+0*1+0*2-(-3)=3;∆_3,4,5=0*1+0*0+0*0-0=0.

Шаг 4:Критерий опт опорного плана - отсутствие «+» оценок в 4-ой строке. Т.к.имеется 2 «+» оценки

∆₁=2>0, ∆₂=3>0, то опорн план X⁽⁰⁾неоптимлен.

Шаг 5: В матрице (А1:А5) находим разрешаемый элемент: см. толко на «+» числа. для каждого вектора А_i с + оценкой ∆_i вычисляем отношение соответствующих координат вектора А_о и вектора А_i и берём min из полученных чисел. 2 Если + оценок несколько то из min отношений берётся max-ое.

3 Число в знаменателе дроби - разреш эл. (в прямоугльник)

∆₁=2>0, min ( ∆₂=3>0, min max (4;5)=5= разреш эл в А5А2.

Шаг 6Т.к. разреш эл в А5А2, то в базисе (А₃ А₄ А₅ ) вместо вектора А₅ поставляем А₂. Для этого элементар преобразования над строками матрицы коэф. Сделать из столбца А₂ новый (в которм был А5) . . (три нуля - с помощью разреш эл).2-ая симплекс табл.

i	Базис	Сб	Ао	С1= -2	С2= -3	C3=0	C4=0	C5=0
А1	А2	А3	А4	А5
	А3							-1/2
	А4			5/2				-1/2
	А2	-3		1/2				1/2
	∆j	Х	-15	1/2				-3/2

в стлбц «Базис» элемент А₅ заменён на А₂ , в стлбц «С_б» стоит коэф С₂= -3

Шаг 7. Контроль вычислений по 4 строке: С_б *Ао=0*1+0*7+(-3)*5=-15. ∆j=C_б*A_j-C_j

∆₁=0* ∆₂=0*0+0*0+(-3)*1-(-3)=0.∆₃=0.∆₄=0.∆₅=-3/2

Новый опорный план.Х⁽¹⁾=(0,5,1,7,0).(из А0).Далее шаги 4-7 повторяются пока не будет выполняться условия оптимальности ∆j≤0 для всех j.Тогда будет получен опт опорный план.

Шаг 4`.∆<sub>1</sub>=1/2>0, значит план Х<sup>(1)</sup> не оптен. Шаг 5`.min ( .A3A1.Шаг 6`Из базиса убрать А₃ заменив на А₁ . . .

Cимплекс табл.

Шаг 7`,Контроль вычислений -ошибок нет. Получен опорный план Х⁽²⁾=(2,4,0,2,0) (Ао) - который соответствует вершине В(2,4) Шаг 4`` все оценки ∆j≤0-оптимый, х₁=2, х₂=4 ; Z^min= -16

Замечание: если план Х⁽³⁾ не оптимален то нет реш.