Решение задач линейного программирования «Симплекс»-методом

Предприятие выпускает 2 вида ДСП: простые и улучшенные. Ранее предприятием были заключены контракты, согласно которым им поставляется ежемесячно 4 т опилок. Кроме того, в распоряжении фирмы находится оборудование для прессования с месячным фондом рабочего времени 600 часов и оборудования для отделки с месячным фондом 900 часов. За изготовление партии простых ДСП полагается ЗП рабочим в размере 30$, а за партию улучшенных ДСП – 50$. Предельный ФОТ на предприятии составляет 6000 $.

Определите оптимальный план производства, при котором доход предприятия будет наибольшим, если партия простых ДСП приносят доход в размере 80$, а партия улучшенных – 100$.

1. Примем Х1 – количество партий простых ДСП, за Х2 – количество партий улучшенных ДСП и запишем математическую модель задачи:

F=80∙ X₁+100X₂ → max

X₁, X₂ > 0

2. Обозначим остатки ресурсов Уі и перейдем от системы неравенств к системе равенств

3. Затем переходим к системе равенств, оставляет в левой части y, а все остальные переносим в правую часть.

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

F=(-80)(-X₁) + (-100)(-X₂) → max

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

4. Математическая модель задачи запишем в виде симплекс таблиц:

Этапы оптимизации симплекс- матрицы:

- поиск опорного решения, опорному решению соответствует симплекс – таблица с неотрицательными значениями всех свободных членов в строке F;

- поиск оптимального решения:

а)выбор разрешающего столбца - для этого в F-cтроке выбирают наибольший по модулю отрицательный элемент столбца свободного члена (мах по модулю отрицательное (-С₁; -С₂) = -100 (-Х₂);

б)выбор разрешающей строки - для этого находим минимальное частное от деления элементов столбца свободных членов на соответствующем им элементы, разрешающего столбца (Q = мин (В₁/А₁₂; В₂/А_22..) =100 (В₁));

в)на пересечении разрешённого столбца и разрешённой строки выбирают разрешённый элемент (А₁₂);

г)выполняем преобразование исходной симплексной таблицы с записью результатов в новую таблицу, начиная всегда с пересчета разрешённого элемента: =1/40;

* пересчет элементов разрешённой строки: =20/40=0, 5 =4000/40=100

* пересчет элементов разрешённого столбца =-5/40; и т.д.

* прочие элементы таблицы внешние свободные члены и элементы F строки вычисления по правилу прямоугольника: проводит прямоугольник ч/з элемент, подлежит пересчету и ч/з разрешённый элемент и пересчет по формуле: А₂₁`= А₂₁ – А₁₁*А₂₂/А₁₂= 3 – 20*5/40=0, 5

А₃₁`= А₃₁ – А₁₁*А₃₂/А₁₂= 6 – 20*6/40=3

А₄₁`= А₄₁ – А₁₁*А₄₂/А₁₂= 30 – 20*50/40=5

А₅₁`= А₅₁ – А₁₁*А₅₂/А₁₂= -80 – 20*(-100)/40= -30

В₂`= В₂ – В₁*А₂₂/А₁₂= 600 – 4000*5/40=100

В₃`= В₃ – В₁*А₃₂/А₁₂= 900 – 4000*6/40=300

В₄`= В₄ – В₁*А₄₂/А₁₂= 6000 – 4000*50/40=1000

В₅`= В₅ – В₁*А₅₂/А₁₂= 0 – 4000*(-100)/40=-10000