Завдання 1
Дані вихідної задачі запишемо у вигляді таблиці (таблиця 1).
Таблиця 1
СирьеВід продукцііЗапаси сировини 1 А 2 S 1 1110S 2 1428S 3 3124Доход від реалізаціі48
Припустимо, що буде використано х 1 сировини S 1 для виготовлення продукції А 1, х 2 сировини для продукції виду А 2. Тоді загальний прибуток від реалізації складе 4х 1 + 8х 2.
Так як загальна кількість сировини S 1 не може перевищувати 10, то повинно виконуватися наступне нерівність: х 1 + х 2? 10
Аналогічні міркування щодо можливого використання решти кількості сировини приведуть до слідуючи нерівностей:
х 1 + 4х 2? 28;
х 1 + х 2? 24.
При цьому, так як кількість продукції не може бути негативним, то: х 1? 0, х 2? 0
Нехай F - прибуток підприємства, так як за умовою необхідно скласти план виробництва двох видів продукції, що забезпечує максимальний прибуток, отже, функція F, за умови, що виготовлено х 1 одиниць продукції виду А 1 і х 2 одиниць продукції виду А 2 буде максимизироваться:
витрата тіньової ціна прибуток
F=4х 1 + 8х 2? max.
Таким чином, ми приходимо до наступної математичної задачі:
Дана система:
(1)
трьох лінійних нерівностей з двома невідомими хi (i=1,2). І лінійна функція відносно цих же змінних:
F=4х1 + 8х2 (2)
потрібно серед всіх невід'ємних рішень системи нерівностей (2), знайти таке, при якому функція (3) прийме максимальне значення.
Знайдемо рішення сформульованої задачі, використовуючи її геометричну інтерпретацію. Спочатку визначимо багатокутник рішень. Для цього в нерівностях системи обмежень і умов не заперечності змінних знаки нерівностей замінимо на знаки точних рівностей і знайдемо відповідні прямі.
Прямі S1 - S3, зображені на малюнку 1.
Кожна з побудованих прямих ділить площину на дві півплощини. Координати точок одній півплощині задовольняють вихідного нерівності, а інший - ні. Визначимо шукану напівплощина через точку О (0; 0).
Припинення отриманих площин визначає багатокутник рішень даної задачі.
Малюнок 1 - Багатокутник рішень
Як видно з малюнка 1, багатокутником рішень є п'ятикутник ОАВСD.
Таким чином, серед точок п'ятикутника ОАВСD нам потрібно знайти такі, в яких функція F=4х 1 + 8х 2 приймає максимальне значення. Для знаходження цих точок побудуємо нульову лінію рівня (F 0) 4х 1 + 8х 2=0 і вектор N=(4; 8).
Пересуваючи дану пряму паралельно самій собі в напрямку вектора N, бачимо, що її останньою крапкою з багатокутником рішень задачі є точка В. Отже, в цій точці функція F приймає максимальне значення. Так як В - точка перетину прямих S1 і S2, то її координати задовольняють рівнянням цих прямих:
Вирішивши цю систему рівнянь ми отримали: х1=4 і х2=6.
Таким чином, максимальне значення функції Fmax=4 * 4 + 8 * 6=16 + 48=64.
Рішення симплекс-методом
Математична модель задачі:
х1, х2? 0
F=4х1 + 8х2
Запишемо цю задачу у формі основної задачі ЛП:
Для цього перейдемо від обмежень нерівностей - до обмежень равенствам.
Введемо 3 додаткові змінні, в результаті чого обмеження запишуться у вигляді систем обмежень:
Перетворену систему обмежень запишемо у векторній формі:
Оскільки серед векторів Р1-Р5 маються 3 одиничних вектора, для даної задачі можна безпосередньо записати опорний план.
Таким є план Х=(0; 0; 0; 10; 28; 24), який визначається системою тривимірних одиничних векторів Р3, Р4, Р5, які утворюють базис тривимірного векторного простору.
Складемо сімплексну таблицю для I ітерації (таблиця 2), підрахувавши значення F0, zi - ci і перевіряємо вихідний план на оптимальність.
F 0=(c, P 0); z 1=(c, P 1)=0; z 2=(c, P 2)=0; z 3=(c, P 3)=0; 4=(c, P 4)=0; z 5=(c, P 5)=0; 1 - c 1=0 - 4=- 4; z 2 - c 2=0 - 8=- 8.
Для векторів базису zi - ci=0.
Таблиця 2
iБазісС б Р 0 48000Р 1 Р 2 Р 3 Р 4 Р 5 1Р 3 010111002Р 4 028140103Р 5 0243100140-4-8000
Таким чином, за 4 рядку таблиці 2 видно, що план не оптимальний, тому значення zi - ci - негативні.
Далі визначаємо вектор, що підлягає виключенню з базису. Для цього знаходимо Q 0min (bi/a i1) для a i1 gt; 0 і Q 0min (bi/a i2) для a i2 gt; 0.
Таким чином, Q 0min (bi/a i1)=min (10/1; 28/1; 24/4)=24/4, а Q 0min (bi/a i2)=min...
