За допомогою симплекс-методу знайти такий план виробництва, який би забезпечував найбільший прибуток.
Якщо змінна прямої задачі може бути будь-якою за знаком, то відповідне їй обмеження є рівнянням. І навпаки, якщо основне обмеження прямої задачі є рівнянням, то відповідна змінна двоїстої задачі може набувати будь-яких значень.
Коефіцієнти, що стоять при х1 у системі основних обмежень прямої задачі, стають коефіцієнтами в першому обмеженні двоїстої задачі. Аналогічно для х2, і т.д.
Коефіцієнти цільової функції прямої задачі стають вільними членами основних обмежень двоїстої задачі, а вільні члени обмежень прямої задачі стають коефіцієнтами в цільовій функції двоїстої задачі.
Будуємо двоїсту задачу.
При побудові двоїстої задачі користуємося правилами:
1). Двоїста задача містить стільки нових змінних, скільки основних обмежень у прямій задачі.
2). Якщо пряма задача на max, то двоїста – на min і навпаки.
6). Якщо задача на max, то усі нерівності повинні бути виду “≤”, якщо на min, то - “≥”.
Записуємо модель двоїстої задачі з цільовою функцією F та двоїстими змінними у1, у2, у3 (кількість обмежень у нашій задачі три).
| L = 10 х1 + 18 х2 → max, 2 х1 + 2 х2 ≤ 60 ↔ у1, 3 х1 + х2 ≤ 65 ↔ у2, 2 х1 + 9 х2 ≤ 135 ↔ у3 х1 ≥ 0, х2 ≥ 0. | ↔ | F = 60 у1 + 65 y2 + 135 у3 → min, 2 у1 + 3 y2 + 2 у3 ≥ 10, 2 у1 + y2 + 9 у3 ≥ 18, y1 ≥ 0, y2 ≥ 0. |
Розв’язок двоїстої задачі можна знайти за допомогою останнього рядка останньої симплексної таблиці прямої задачі (табл. 4).
0 0 0 54/25 44/25
основні х1, х2х3, х4, х5 додаткові
додаткові у4, у5у1, у2, у3 основні
маємо: У = (0; 54/25; 44/25 | 0; 0), Fmin = 378.
Двоїсті змінні показують міру дефіцитності ресурсів, вони чисельно рівні зміні цільової функції при зміні відповідного ресурсу на одиницю. Відповідно, зміна другого ресурсу на одиницю призводить до збільшення обсягу реалізації на у2 = 54/25, третього – на у3 = 44/25. Змінна у1 = 0 вказують, що перший ресурс у надлишку, тому його збільшення до будь-якої зміни цільової функції не призведе.
Додаткові двоїсті змінні показують міру збитковості продукції, яку, згідно з розв’язком, недоцільно випускати. З розв’язку двоїстої задачі випливає, що збиткової продукції немає.
ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ
№№ 201 – 300. Для виготовлення двох видів продукції Р1 і Р2 підприємство використовує три види сировини S1, S2, S3. Запаси ресурсів, норми їх затрат і прибуток від реалізації одиниці продукції задано таблицею.
2. Скласти модель двоїстої задачі. Використовуючи відповідність між змінними прямої і двоїстої задач та симплексну таблицю для прямої задачі, записати оптимальний розв’язок двоїстої задачі.