Комплекс и симпплекс методы решения задач по оптимизации бизнеса

 
 

     Задание 
 

     Дано: 

     затраты сырья на единицу продукции заданы матрицей затрат; 

 
 
 

     стоимость реализации равна:  р₁  = 5, р₂  = 4;      
 
 

     Требуется: 
 

     1) Составить исходную задачу, обеспечивающую максимальную прибыль. 
 

     2) Составить двойственную задачу  к исходной. 
 

     3) Первую задачу решить графическим  методом, вторую задачу решить  симплекс-методом. 
 
 
 
 
 
 
 
 
 
 
 

     Решение 
 
 
 

     1). 
 

     Для частной экономической модели введем обозначение: 

     X_j; где: Х_j – количество продукции j – того вида, X_j ≥0. 

     Составим  ограничение по ресурсам в виде системы неравенств: 

     

     5хХ₁+5хХ₂≤42 

     7хХ₁+3хХ₂≤36 

     2хХ₁+4хХ₂≤74 
 

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

     L=5хХ₁+4хХ₂ => max 

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

2). 
 

Теперь  составим задачу, двойственную к исходной.

Это будет  задача по обеспечению минимализации затрат.  
 
 

     Для частной экономической модели введем обозначение: 

     Y_j; где: Y_j – стоимость ресурсов j – того вида, Y_j ≥0. 

     Составим  ограничение по стоимости ресурсов в виде системы неравенств: 

     

     5хY₁+7хY₂+2xY₃≥5 

     6хY₁+3хY₂+4xY₃≥4 
 
 
 

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

     Z=42хY₁+36хY₂+74xY₃ => min 

Это и есть математическая форма задачи, двойственной к исходной, решение которой обеспечивает минимальные затраты.  
 
 
 
 
 
 
 
 
 
 

     3).  

     Решим первую задачу графическим методом 

     Для исходной системы неравенств определяем линии границ и точки их пересечений  с осями координат:  

     

     5хХ₁+6хХ₂≤42          5хХ₁+6хХ₂=42      (0;7),    (8,4;0).                             

     7хХ₁+3хХ₂≤36         7хХ₁+3хХ₂=36    (0;12),  (5 1/7;0). 

     2хХ₁+4хХ₂≤74          2хХ₁+4хХ₂=74      (0;18,5), (37;0). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Для множества решений системы неравенств лежащего в границах многоугольника ОАВС найдем координату точки В решив  систему уравнений: 
 

      5хХ₁+6хХ₂=42    5хХ₁+6хХ₂=42     5хХ₁+6хХ₂=42    5хХ₁+6хХ₂=42                                            

     7хХ₁+3хХ₂=36    14хХ₁+6хХ₂=72            9хХ₁=30              Х₁=3 1/3        

                
 

      5х3,3+6хХ₂=42    16,5+6хХ₂=42     6хХ₂=25,5        Х₂=4,25                                            

     Х₁=3,3               Х₁=3,3                Х₁=3,3             Х₁=3,3      
 
 
 

     Среди неотрицательного множества решений  системы неравенств, лежащего в границах четырехугольника ОАВС вычислим значения функции L в точках ОАВС: 

     L(0)=5х0+4х0=0+0=0;        L(А)=5х0+4х7=0+28=28;      

     L(В)=5х3,3+4х4,25=16,5+17=33,5;  

     L(С)=5х5 1/7+4х0=25 5/7+0=25 5/7;  
 

     Функция L=5хХ₁+4хХ₂ принимает свое максимальное значение в точке В (3,3;4,25).  
 

     Ответ(1): 

     Максимальная прибыль будет обеспечена при одновременном производстве 3,3 штук товара № 1 и 4,25 штук товара № 2. 
 
 
 

     Решим вторую задачу симплекс-методом  
 

     Запишем задачу в канонической форме, т.е. ограничения-неравенства  перепишем в виде равенств, добавляя балансовые переменные: 

      5хY₁+7хY₂+2xY₃≥5        5хY₁+7хY₂+2xY₃+Y₄=5 
 

     6хY₁+3хY₂+4xY₃≥4        6хY₁+3хY₂+4xY₃+Y₅=4 

     где: Y_j – стоимость ресурсов j – того вида, Y_j ≥0. 
 

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

     Z=42хY₁+36хY₂+74xY₃ +Y₄+Y₅ => min 
 

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

     Составим  первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод, т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных.  
 
 

 
 

     Здесь "БП" означает столбец базисных переменных 
 

     Решение не является оптимальным, т.к. в Z – строке есть отрицательные коэффициенты.  
 
 

     Для улучшения решения перейдем к  следующей итерации симплекс-метода, получим следующую симплекс-таблицу.

     Для этого надо выбрать разрешающий  столбец, т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему  по модулю отрицательному коэффициенту в Z-строке. Это столбец Y₃.

     Затем выбирается разрешающая строка, т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца «коэфф» к соответствующим положительным элементам разрешающего столбца, в начальной итерации (итерация 0) это строка Y₅.

     Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 4.

     Заполним  следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец Y₃ в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов). 
 

 
 

     В Z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение. 

     Z=42хY₁+36хY₂+74xY₃ +Y₄+Y₅ =42х0+36х0+74=1+0х3+0х0=74. 
 
 

     Ответ(2): 
 

     Минимальные затраты Z_min= 74.