Пример решения ОЗЛП симплексным методом

 

Пусть необходимо найти оптимальный план производства двух видов продукции х 1 и х 2 (табл. 3.2).

 

Таблица 3.2 – Исходные данные примера

Вид продукции Норма расхода ресурса на единицу прибыли Прибыль на единицу изделия
  А В  
Объем ресурса  

1. Построим ОМ

ограничение по ресурсу А ;

ограничение по ресурсу В .

2. Преобразуем задачу в приведенную каноническую форму. Для этого достаточно ввести дополнительные переменные x 3 и x 4 . В результате неравенства преобразуются в строгие равенства:

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

и

Базисные переменные Свободные члены (план) x 1 x 2 x 3 x 4
x 3
x 4
F j - C j  

1-я итерация. Находим генеральный столбец и генеральную строку:

Генеральный элемент равняется 5.

Базисные переменные Свободные члены (план) x 1 x 2 x 3 x 4
x 1 0,4 0,2
x 4 0,8 - 1,6
F j – C j 0,2 - 1,4

2-я итерация. Найденное базисное решение не является оптимальным, так как строка оценок ( F j - C j ) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:

(0, 0,3, - 1,4, 0)

Базисные переменные Свободные члены (план) x 1 x 2 x 3 x 4
x 1 - 0,5 0
x 2 - 2 1,25
F j - C j - 1 - 0,25

Найденное решение оптимально, так как все специальные оценки целевой функции ( F j - C j ) равны нулю или отрицательны. F ( x ) = 29; x 1 = 2; x 2 = 5.