Линейное программирование

 
 

Симплексный  метод   решения   линейной  производственной  задачи  представлен  в  Таблице 1. 

Как видно из последней симплексной таблицы, оптимальная производственная программа имеет вид:

Х₁=40,  Х₂=0,  Х₃=24,  Х₄=0,

а максимальная прибыль равна 

Z_МАХ = 1576 

При этом  второй и третий  ресурс будут исчерпаны  полностью, а первый ресурс имеет остаток Х₅= 8 единиц т. е. узкие места производства Х₆=0 и Х₇=0 

Проверим выполнение соотношения H=Q^-1 В, где Q^-1 базис в последней симплексной таблице, соответствующий набору базисных неизвестных.  
 
 
 
 

Проверка: Q^-1*B = H 
 

              1    -15/10   175/100                        120             8

   Q^-1 =  0       5/10   -75/100   B=    168            H=      24

         0        0       5/10               80                       40

                                     

           1   -15/10   175/100         120        1*120+(-15/10)*168+175/100*80          8                     H =     0     5/10     -75/100   *    168  =   0*120+5/10*168+(-75/100)*80        =  24

           0         0          5/10          80         0*120+0*168+5/10*80                          40 
 
 

Вывод: при решении  симплексной таблицы ошибок допущено не было.

Графическое решение 

Проверим полученный результат.

Воспользуемся тем, что в оптимальной производственной программе Х₂=0, Х₄=0. Предположим, что первую и вторую продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

Z = 31X₁ + 14X₃ max 

X₁  + 3X₃    120  (1)

3X₁  + 2X₃   168  (2)

2X₁  + 0X₃   80    (3) 

X₁ 0, X₃ 0 

1) X₁  + 3X₃ = 120

     X₁=0    X3=40

     X3=0    X1=120 

2) 3X₁  + 2X3=168

      X1=0   X3=84

      X3=0   X1=56    

3) 2X1=80

      X1 =40

Решая эту задачу графически, получим следующее: 

Точка M лежит на пересечении прямых (2) и (3) 

3X₁  + 2X₃ =168

2X₁   = 80 

2X₁ =80  => X₁ = 40 

3*40+2X₃   = 168 

2X₃   = 168-120

2X₃   = 48

X₃   = 24 

Ответ Х₁=40,  Х₃=24,   

Вывод:  решение  в симплексной таблице верно 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Двойственная задача линейного программирования 

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

Теперь представим себе что возникла новая ситуация. Некий предприниматель, занимающийся производством каких-то других видов продукции, но с использованием таких же трех видов ресурсов, какие имеются у нас, предлагает нам «уступить» по определенным ценам все имеющиеся у нас ресурсы и обещает платить y₁ руб. за каждую единицу первого ресурса, у₂ руб. – второго, у₃ руб. – за единицу третьего ресурса. Возникает вопрос: при каких ценах y₁, у₂, у₃ мы можем согласиться с предложение предпринимателя?

Величины y₁, у₂, у₃  принято называть расчетными или двойственными оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие. 

Дано:

                   1 4 3 4  120

            A=  3 0 2 2 B= 168 C= (31,10,14,20)

                   2 5 0 3   80 

A – технологическая матрица

B – вектор объема ресурсов

C – вектор удельной прибыли 

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А,  1 единицу ресурса первого вида, 3 единицы ресурса второго вида и 2 единицы третьего (элементы первого столбца матрицы). В ценах y₁, у₂, у₃ наши затраты составят y₁ + 3у₂ +2y₃,   т.е. столько заплатит предприниматель за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 31 руб.  Следовательно,  мы  можем  согласиться  с предложением предпринимателя только в том случае, если он заплатит не меньше  

   y₁ + 3 у₂ + 2 y₃  31

    4 y₁ +          5 y₃  10

    3 y₁ + 2 у₂               14

    4 y₁ + 2 у₂ + 3 y₃  20 

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

120у₁ + 168у₂ +80у₃ рублей. При поставленных нами условиях предприниматель будет искать такие значения величин y₁, у₂, у₃, чтобы эта сумма была как можно меньше. Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок У (У₁У₂,У₃) минимизирующий общую оценку всех ресурсов

  f =120у₁ + 168у₂ +80у₃ -> min

при условии, что по каждому виду продукции  суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции, причем оценки ресурсов не могут быть отрицательными

у₁ >=0    у₂>=0   у₃>=0 

Решение полученной задачи легко найти с  помощью второй основной теоремы двойственности, согласно которой для оптимальных решений

Х (Х₁, Х₂, Х₃, Х₄) и у (y₁, у₂, у₃) пары двойственных задач необходимо и достаточно выполнение условий 

     X₁( y₁+3 y₂+2 y₃ -31 )=0  y₁ ( Х₁+4Х₂+3Х₃+4 Х₄- 120)=0

    X₂(4 y₁ + 5 y₃ - 10)=0  y₂ (3Х₁+ 2Х₃+2Х₄- 168)=0

    X₃(3 y₁ +2 y₂ - 14)=0  y₃ (2 Х₁+5 Х₂+ 3Х₄- 80)=0

    X₄(4 y₁ +2 y₂+3 y₃ - 20)=0 

Ранее было найдено, что в решении исходной задачи X₁ >0, X₃>0  => (X₁ =40,

X₂=0, Х₃=24, Х₄=0).

Поэтому

          y₁+3 y₂+2 y₃ - 31=0

          3y₁+2 y₂ - 14=0 

Если же учесть, что первый   ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю: y1 =0, то приходим к системе уравнений

          3 y₂+2 y₃ - 31=0

         2 y₂ - 14=0

откуда следует

         y₂=7, у₃=5 

y*= (0;7;5) 

Таким образом, получили двойственные оценки, причем общая оценка всех ресурсов равна 1576: 

f=120*0+168*7+80*5=1576 

Так как первый ресурс был избыточным, согласно теории свойств, его двойственная оценка равна 0 (y1=0) 

Экономический смысл двойственных оценок. Например, двойственная оценка второго ресурса  у₂=7 показывает, что добавление одной единицы этого ресурса обеспечит прирост прибыли в 7 единиц.

3. Задача о  расшивке узких мест производства 

       При выполнении оптимальной производственной программы второй и третий ресурсы используются полностью, т.е. образуют "узкие места производства". Будем их заказывать дополнительно. Пусть T(t₁,t₂,t₃)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие Н + Q^-1T>=0.

Задача состоит  в том, чтобы найти вектор Т (0, t₂ , t₃) максимизирующий суммарный прирост прибыли (т. к. y₁=0 то t₁=0)

       W = 7 t₂ +5 t₃   → max

при условии  сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы

   8   0                  0

       24       +                           * t₂   0

        40  t₃  0 
 

         0                             120

         t2 ≤    1/3     168

         t3                             80 

причем по смыслу задачи t₂ 0  , t₃ 0 

Составим систему  уравнений для графического решения

      1,5* t₂ -1,75* t₃ 8  (1)  точки (0; -4 ); (5 ;0)

-0,5* t₂ +0,75* t₃ 24 (2)  точки (0;32); (-48;0)

                    -0,5* t₃ 40 (3) 

             t₂ (4) 

                    t₃ (5)

приходим к  задаче линейного программирования 

Эту задачу решим графически:  

1,5* t₂ -1,75* t₃ =8 

t₃

1,5* t₂ -1,75* =8

1,5* t₂  =      =>  t₂ =16 

Программа "расшивки" имеет вид

T_опт = 0;16;26

W_max= 7 t₂ +5 t₃ =7*16+5*26 =388 и прирост прибыли составит 388

При новом плане  выпуска продукции

X₅ ^н =-1,5* 16 +1,75* 26 +8=0

X₃ ^н =0,5* 16 -0,75* 26 +24=22

X₁ ^н =1,5* 16 +40=53

Z ^н =31*53 +14*22 =1964

Z ^н =1576+388 =1964

Графическое решение

 
 
 
 
 
 

Сводка  результатов приведена в Таблице1  

                                                                                    Таблица1