Привести к канонической форме Из ЗЛП в СЗЛП P-метод

Решение задач линейного программирования.
Copyright © Semestr.RU

Переход к КЗЛП.
F(X) = 3x1 + 8x2 → max при ограничениях:
10x1 + 70x2<=570
20x1 + 50x2<=420
300x1 + 400x2<=5600
200x1 + 100x2<=3400
Для приведения ЗЛП к канонической форме необходимо:
10x1 + 70x2 + 1x3 + 0x4 + 0x5 + 0x6 = 570
20x1 + 50x2 + 0x3 + 1x4 + 0x5 + 0x6 = 420
300x1 + 400x2 + 0x3 + 0x4 + 1x5 + 0x6 = 5600
200x1 + 100x2 + 0x3 + 0x4 + 0x5 + 1x6 = 3400
F(X) = 3x1 + 8x2
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
	
10	70	1	0	0	0	570
20	50	0	1	0	0	420
300	400	0	0	1	0	5600
200	100	0	0	0	1	3400
		

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5,6).
Соответствующие уравнения имеют вид:
10x1 + 70x2 + x3 = 570
20x1 + 50x2 + x4 = 420
300x1 + 400x2 + x5 = 5600
200x1 + 100x2 + x6 = 3400
Выразим базисные переменные через остальные:
x3 = - 10x1 - 70x2+570
x4 = - 20x1 - 50x2+420
x5 = - 300x1 - 400x2+5600
x6 = - 200x1 - 100x2+3400
Подставим их в целевую функцию:
F(X) = 3x1 + 8x2
или
F(X) = 3x1 + 8x2 → max
Система неравенств:
- 10x1 - 70x2+570 ≥ 0
- 20x1 - 50x2+420 ≥ 0
- 300x1 - 400x2+5600 ≥ 0
- 200x1 - 100x2+3400 ≥ 0
Приводим систему неравенств к следующему виду:
10x1 + 70x2 <= 570
20x1 + 50x2 <= 420
300x1 + 400x2 <= 5600
200x1 + 100x2 <= 3400
F(X) = 3x1 + 8x2 → max
Упростим систему.
10x1 + 70x2 <= 570
20x1 + 50x2 <= 420
300x1 + 400x2 <= 5600
200x1 + 100x2 <= 3400
F(X) = 3x1 + 8x2 → max
Решим прямую задачу линейного программирования симплекс-методом..
Определим максимальное значение целевой функции F(X) = 3x1 + 8x2 при следующих условиях-ограничений.
10x1 + 70x2<=570
20x1 + 50x2<=420
300x1 + 400x2<=5600
200x1 + 100x2<=3400
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
10x1 + 70x2 + 1x3 + 0x4 + 0x5 + 0x6 = 570
20x1 + 50x2 + 0x3 + 1x4 + 0x5 + 0x6 = 420
300x1 + 400x2 + 0x3 + 0x4 + 1x5 + 0x6 = 5600
200x1 + 100x2 + 0x3 + 0x4 + 0x5 + 1x6 = 3400
Введем новую переменную x0 = 3x1 + 8x2.
Выразим базисные переменные <3, 4, 5, 6> через небазисные.
x0 = 0+3x1+8x2
x3 = 570-10x1-70x2
x4 = 420-20x1-50x2
x5 = 5600-300x1-400x2
x6 = 3400-200x1-100x2
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
max(3,8,0,0,0,0) = 8
x0 = 0+3x1+8x2
x3 = 570-10x1-70x2
x4 = 420-20x1-50x2
x5 = 5600-300x1-400x2
x6 = 3400-200x1-100x2
В качестве новой переменной выбираем x2.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2
и из них выберем наименьшее:
Вместо переменной x3 в план войдет переменная x2.
Выразим переменную x2 через x3
и подставим во все выражения.
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 456/7+13/7x1-4/35x3
x2 = 57/7-1/7x1-1/70x3
x4 = 90/7-90/7x1+5/7x3
x5 = 16400/7-1700/7x1+40/7x3
x6 = 18100/7-1300/7x1+10/7x3
Полагая небазисные переменные x = (2, 4, 5, 6) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-13/7, 0, 4/35, 0, 0, 0), x0 = 456/7
max(13/7,0,-4/35,0,0,0) = 13/7
x0 = 456/7+13/7x1-4/35x3
x2 = 57/7-1/7x1-1/70x3
x4 = 90/7-90/7x1+5/7x3
x5 = 16400/7-1700/7x1+40/7x3
x6 = 18100/7-1300/7x1+10/7x3
В качестве новой переменной выбираем x1.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai1
и из них выберем наименьшее:
Вместо переменной x4 в план войдет переменная x1.
Выразим переменную x1 через x4
и подставим во все выражения.
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 67-1/90x3-13/90x4
x2 = 8-1/45x3+1/90x4
x1 = 1+1/18x3-7/90x4
x5 = 2100-70/9x3+170/9x4
x6 = 2400-80/9x3+130/9x4
Полагая небазисные переменные x = (2, 1, 5, 6) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 1/90, 13/90, 0, 0), x0 = 67
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 67-1/90x3-13/90x4
x2 = 8-1/45x3+1/90x4
x1 = 1+1/18x3-7/90x4
x5 = 2100-70/9x3+170/9x4
x6 = 2400-80/9x3+130/9x4
Оптимальный план можно записать так:
x2 = 8
x1 = 1
x5 = 2100
x6 = 2400
F(X) = 67
Возвращаемся к системе уравнения в СЗЛП.
x3 = - 10x1 - 70x2+570
x4 = - 20x1 - 50x2+420
x5 = - 300x1 - 400x2+5600
x6 = - 200x1 - 100x2+3400
Подставим в них найденные переменные.
x3 = -10*1 -70*8 + 570 = 0
x4 = -20*1 -50*8 + 420 = 0
x5 = -300*1 -400*8 + 5600 = 2100
x6 = -200*1 -100*8 + 3400 = 2400