Математическое программирование

 
 

 
ВАРИАНТ 7

   1. Макаронная фабрика производит два вида изделий А и В, используя три вида сырья: муку, яйца, соль. Общие запасы каждого вида сырья соответственно равны 3000, 252, 120 усл. ед. Норма расхода сырья

   на  единицу веса изделия А - 120; 3; 4 усл. ед.,

   на  единицу веса изделий В - 40; 12; 4 усл. ед.

   Составить план производства, обеспечивающий максимальную прибыль, если единица веса изделий  А дает прибыль 300 р., а В - 400 р.:

а) записать математическую модель;

б) решить задачу графическим методом;

в) решить задачу симплекс-методом;

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

   Построение  математической модели

   X1 –изделие первого вида

   X2 –изделие второго вида

   Тогда компоненты производственного плана должны (X1;X2) должны удовлетворять следующим условиям ограничениям

 

   С другой стороны пара величин X1 и X2 может рассматриваться как некоторый вариант производственного плана.

   Нужно найти план, приносящий наибольший доход

       

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

      
 

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

В декартовой системе  координат находим  решение системы  неравенств.

Для этого строим прямые.

120x1+40x2=3000  по точкам  (0;75)  (25;0)

3x1+12x2=252  по точкам  (0;84)  (21;0)

4x1+4x2=120  по точкам  (0;30)  (30;0)

 

 
 
 

OABCD многоугольник решений

Вектор  (30; 40) вектор целевой функции.

Проведём через  любую точку.  например (0;10) прямую P’, перпендикулярно вектору  .

Перемещаем прямую Р’ параллельно самой себе по направлению вектора , пока   она не займёт относительно области OABCD крайнего верхнего положения.

Это произойдёт, когда она пройдёт через точку  B(19.64;16.09).

Оптимальное решение  определяется координатами точки B(19.64;16.09) точка пересечения прямых  3x1+12x2=252    4x1+4x2=120

Zmax=300*19.6364+400*16.09=12327.27 
 
 

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

Введем  дополнительные переменные, в результате чего ограничения  запишутся в виде системы уравнений

120x1+40x2+x3=3000 

3x1+12x2+x4=252 

4x1+4x2+x5=120   

эти дополнительные переменные  по экономическому смыслу

означают неиспользуемое сырьё при данном плане производства

Преобразованную систему уравнений запишем в  векторной 

форме:

          x1*P1+x2*P2+x3*P3+x4*P4+x5*P5=P0, где        

 

P1= P2=   P3=   P4=   P5=    P0=  

Cимплекс-таблица 

 

Определяем  вектор подлежащий, который нужно ввести в базис, очевидно – это P2 (ему соответствует большее отрицательное значение).

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

Вектор, который  необходимо исключить P4. 

Определяем наименьшее, среди отношений  Bi/Pi2, разрешающий элемент -12.  

 

 

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента.

Из первой строки вычитаем вторую строку, умноженную на  (40/12)

Из третьей  строки вычитаем вторую строку, умноженную на  (4/12)

 

Получим следующую  таблицу.

 

Определяем вектор подлежащий, который нужно ввести в базис, очевидно – это P1 (ему соответствует большее отрицательное значение).

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

Вектор, который  необходимо исключить P5. 

Определяем наименьшее, среди отношений  Bi/Pi1, разрешающий элемент -3.

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента.

Из первой строки вычитаем третью строку, умноженную на  (110/3)

Из второй строки вычитаем третью строку, умноженную на  (0,25/3)

  

Получим следующую  таблицу.

 

   Все ΔZi>0,  поэтому, полученное базисное решение

   X1=12 X2=18 X3=840 является оптимальным, значение целевой функции для него равняется 10800 усл. единиц.     
 
 

                  Построение  двойственной задачи

                  Исходная задача (L):

Найти

При ограничениях. 

 

Двойственная  ей задача (L*), будет иметь вид: найти