double arrow

Решение ЗЛП методом искусственного базиса

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

Составим матрицу коэффициентов системы уравнений:

В матрице нет единичных векторов, из которых можно образовать единичную матрицу, т.е. возникает проблема выбора базисных переменных в каждом из уравнений.

Введем искусственные переменные .

Введем их в целевую функцию с коэффициентами (-М), т.к. решается задача нахождения максимуму:

Единичную матрицу образуют коэффициенты при неизвестных , значит эти переменные являются базисными. А так как они являются искусственными переменными, то исходный базис называют искусственным. Переменные х1, х2, х3 и х4 являются свободными.

Таким образом,мы получили расширенную ЗЛП, и будем решать ее симплекс-методом.

Полагая , находим первоначальный опорный план: При этом плане:

1. Заполним первую симплекс-таблицу.

  хБазис     В       -1
х3 х4 y1 y2
y1              
y2              
Δj -7М -3М-2 -6М-3 -3М-1 -3М+1    

min (Δj < 0) = Δ2 = - 6М – 3, значит в базис введем переменную х2.

, значит, из базиса выводим искусственную переменную y1, поэтому столбец y1 в следующей таблице можно не заполнять.

2. Производим заполнение второй таблицы по правилам симплекс-метода.

  хБазис     В       -1
х1 х2 х3 х4 y2
х2     1/3   2/3 2/3  
y2       -1 -1 1
Δj -М+3 -М-1   М+1 М+3  

min (Δj < 0) = Δ1 = - М - 1, значит в базис введем переменную х1.

, значит, из базиса выводим искусственную переменную y2, поэтому столбец y2 в следующей таблице можно не заполнять.

3. Заполняем третью таблицу.

хБазис     В       -1
х1 х2 х3 х4
х2   2/3        
х1         -1 -1
Δj          

В третьей таблице обе искусственные переменные оказались равными нулю и все , следовательно, получено оптимальное решение исходной задачи.

Ответ: ,


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: