Симплексний метод лінійного програмування

Завдання 1

Кондитерська фабрика для виробництва трьох видів карамелі А₁, А₂, А₃ використовує три види сировини: цукор-пісок, патоку і фруктове пюре. Норми використання сировини кожного виду на виробництво однієї тони карамелі подано в таблиці, відома також загальна кількість сировини кожного виду і прибуток від реалізації 1 тонни карамелі певного виду.

Розв’язок

Складаємо математичну модель задачі. Позначимо через х₁ кількість карамелі 1-го виду, що виготовляє підприємство за деяким планом, а через х₂ кількість карамелі 2-го виду та через х₃ кількість карамелі 3-го виду. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає

∫ = 21х₁+23х₂+25х₃.

Витрати сировини на виготовлення такої кількості виробів складають відповідно:

C_I =0,8х₁+0,5х₂+0,6х₃,

C_IІ =0,4х₁+0,4х₂+0,3х₃,

C_IІІ =0х₁+0,1х₂+0,1х₃.

Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:

0,8х₁+0,5х₂+0,6х₃≤1000

0,4х₁+0,4х₂+0,3х₃≤800

0х₁+0,1х₂+0,1х₃≤150.

Оскільки, кількість виробів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х₁> 0, х₂> 0, х₃>0.

Таким чином, приходимо до математичної моделі:

Знайти х₁, х₂, х₃ такі, що функція ∫ = 21х₁+23х₂+25х₃ досягає максимуму при системі обмежень:

Розв'язуємо задачу лінійного програмування симплексним методом.

Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.

0,8x₁ + 0,5x₂ + 0,6x₃ + 1x₄ + 0x₅ + 0x₆ = 1000

0,4x₁ + 0,4x₂ + 0,3x₃ + 0x₄ + 1x₅ + 0x₆ = 800

0x₁ + 0,1x₂ + 0,1x₃ + 0x₄ + 0x₅ + 1x₆ = 150

де х₁,...,х₆>0

Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:

Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.

Вирішимо систему рівнянь відносно базисних змінних:

x₄ , x₅ , x₆

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

X1 = (0,0,0,1000,800,150)

Оскільки завдання вирішується на максимум, то ведучий стовпець вибираємо по максимальному негативному кількістю та індексного рядку. Всі перетворення проводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.

Складаємо симплекс-таблицю:

Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х₃, оскільки значення коефіцієнта за модулем найбільше.

Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х₁.

Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х₂, оскільки значення коефіцієнта за модулем найбільше.

Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х₁=312.5, х₂=1500. Прибуток, при випуску продукції за цим планом, становить 41062,5 грн.

Завдання 2

Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.

Розв’язок

Розв’яжемо задачу лінійного програмування симплексним методом.

Визначимо мінімальне значення цільової функції F(X)=5x₁+3x₂ при наступних умовах-обмежень.

8x₁-14x₂≥14

3x₁+2x₂≥27

x₂≤11

Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.

8x₁-14x₂-1x₃ + 0x₄ + 0x₅ = 14

3x₁ + 2x₂ + 0x₃-1x₄ + 0x₅ = 27

0x₁ + 1x₂ + 0x₃ + 0x₄ + 1x₅ = 11

Введемо штучні змінні x.

8x₁-14x₂-1x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ = 14

3x₁ + 2x₂ + 0x₃-1x₄ + 0x₅ + 0x₆ + 1x₇ = 27

0x₁ + 1x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ = 11

Для постановки задачі на мінімум цільову функцію запишемо так:

F(X) = 5x₁+3x₂+Mx₆+Mx₇ => min

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

X1 = (0,0,0,0,11,14,27)

Переходимо до основного алгоритму симплекс-методу.