щодо можливо використання решти кількості сировини приведуть до слідуючи нерівностей:
х 1 + х 2? 11;
х 1 + 5х 2? 40.
При цьому, так як кількість виготовлених виробів не може бути негативним, то:
х 1? 0, х 2? 0 (1)
Нехай F - прибуток підприємства, так як за умовою необхідно скласти план виробництва двох видів виробів, що забезпечує максимальний прибуток, отже, функція F, за умови, що виготовлено х 1 одиниць виробів I і х 2 одиниць виробів II буде максимизироваться:
F=6х 1 + 5х 2? max
Таким чином, ми приходимо до наступної математичної задачі:
Дана система:
(2)
трьох лінійних нерівностей з двома невідомими хi (i=1,2). І лінійна функція відносно цих же змінних:
F=6х1 + 6х2 (3)
потрібно серед всіх невід'ємних рішень системи нерівностей (2), знайти таке, при якому функція (3) прийме максимальне значення.
Знайдемо рішення сформульованої задачі, використовуючи її геометричну інтерпретацію. Спочатку визначимо багатокутник рішень. Для цього в нерівностях системи обмежень і умов не заперечності змінних знаки нерівностей замінимо на знаки точних рівностей і знайдемо відповідні прямі.
Прямі S1 - S3, зображені на малюнку 1.
Кожна з побудованих прямих ділить площину на дві півплощини. Координати точок одній півплощині задовольняють вихідного нерівності, а інший - ні. Визначимо шукану напівплощина через точку О (0; 0).
Припинення отриманих площин визначає багатокутник рішень даної задачі.
Малюнок 1 - Багатокутник рішень
математичний змінна витрати витрати
Як видно з малюнка 1, багатокутником рішень є п'ятикутник ОАВСD.
Таким чином, серед точок п'ятикутника ОАВСD нам потрібно знайти такі, в яких функція F=6х 1 + 6х 2 приймає максимальне значення. Для знаходження цих точок побудуємо нульову лінію рівня (F 0) 6х 1 + 6х 2=0 і вектор N=(12; 12).
Пересуваючи дану пряму паралельно самій собі в напрямку вектора N, бачимо, що її останньою крапкою з багатокутником рішень задачі є точка С. Отже, в цій точці функція F приймає максимальне значення. Так як С - точка перетину прямих S1 і S2, то її координати задовольняють рівнянням цих прямих:
Вирішивши цю систему рівнянь ми отримали:
х1=7 і х2=4.
Таким чином, максимальне значення функції Fmax=6 * 7 + 6 * 4=42 + 24=66.
. Рішення симплекс-методом
Математична модель задачі:
х1, х2? 0
F=6х1 + 6х2
Запишемо цю задачу у формі основної задачі ЛП:
Для цього перейдемо від обмежень нерівностей - до обмежень равенствам.
Введемо 3 додаткові змінні, в результаті чого обмеження запишуться у вигляді систем обмежень:
Перетворену систему обмежень запишемо у векторній формі:
Оскільки серед векторів Р 1 -Р 5 маються 3 одиничних вектора, для даної задачі можна безпосередньо записати опорний план.
Таким є план Х=(0; 0; 0; 36; 11; 40), який визначається системою тривимірних одиничних векторів Р 3, Р 4, Р 5, які утворюють базис тривимірного векторного простору.
Складемо сімплексну таблицю для I ітерації (таб. 2), підрахувавши значення F 0, 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 - 6=- 6; z 2 - c 2=0 - 6=- 6.
Для векторів базису zi - ci=0.
Таблиця 2
iБазісС б Р 0 66000Р 1 Р 2 Р 3 Р 4 Р 5 1Р 3 036421002Р 4 011110103Р 5 0402500140-6-6000
Таким чином, за 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 (36/4; 11/1; 40/2)=36/4, а Q 0min (bi/a i2)=min (36/2; 11/1; 40/51)=40/5.
Min (36/4; 40/5)=40/5.
Таким чином, ми знайшли дозволяє елемент, що знаходиться на перетині другого рядка і стовпця вектора Р 2.
Отже, вектор Р 4 підлягає виключенню з базису.
Стовпець вектора Р 2 і другий рядок є напрямними.
Далі, складаємо таблицю для ітерації II (таб. 3).
С...
