Симплекс метод с искусственным базисом

Решение задачи линейного программирование симплекс методом искусственного базиса (М-метод)

Рассмотрим метод искусственного базиса на примере

Дана целевая функция

Z=3x1+2x2+x3→max

Ограничения в виде системы линейных уравнений

системы линейных уравнений

x1,x2,x3 ≥0

Для коэффициентов базисных переменных надо учитывать, что знак неравенства «» эквивалентен «+», а знак неравенства «» — «–»

В целях построения начального опорного плана ведём дополнительные переменные и приведем уравнение к каноническому виду

системы линейных уравнений канонический вид

Далее, в полученную линейную систему введем также искусственные переменные

системы линейных уравнений искусственные переменные

Также целевая функция при максимизации примет вид

F(x)=3x1+2x2+x3-Mx9-Mx10-Mx11

Под символом M, будем понимать очень большое неотрицательное число.

Так как необходимо максимизировать max функцию, то знак перед M ставится «-», то есть коэффициент равен -M.

Далее, из системы линейных уравнений из уравнений 3,4,5 выразим искусственные переменные x9,x10,x11, они равны

x9=200-x1+x6

x10=200-x2+x7

x11=100-x3+x8

Подставим полученные значения в целевую функцию

функция

симплекс-метод целевая функциясимплекс-метод формула

Составим 1-ый опорный план

таблица опорный план

Первая итерация

Данный опорный план не оптимален в связи с тем, что в индексной строке имеются отрицательные значения.

По модулю из индексной строки выбираем наибольшее значение, и оно равно -3-1М.

По строкам найдем минимальное значение по формуле

минимальное значение формула

2000/2=1000

3000/1=3000

200/1=200

min{1000,3000,200,-,-}=200

симплекс-метод первая итерация

таблица первый опорный план

Вторая итерация

Имеем на второй итерации следующий опорный план

Опорный план вторая итерация

Вторая итерация

Полученный опорный план не оптимален имеются отрицательные значения в индексной строке.

Выбираем по модулю наибольшее значение -2-1М

1600/2=800

2800/2=1400

200/1=200

min{1600,1400,-,200,-}=200

формула

Решаем аналогично

вторая итерация симплекс метод

м метод таблица

Третья итерация

min{1200,800,-,-,100}=100

третья итерация симплекс метод с искусственным базисом

третья итерация опорный план

Четвертая (заключительная) итерация

План не оптимален, в индексной строке имеются отрицательные значения

min{550,2100,-,-,-}=650

формула

решение методом искусственного базиса таблица

X1=750

X2=200

X3=100

F(x)=3*750+2*200+100=2750

Leave a Reply

Ваш e-mail не будет опубликован.