За допомогою симплекс-методу знайти такий план виробництва, який би забезпечував найбільший прибуток

Якщо змінна прямої задачі може бути будь-якою за знаком, то відповідне їй обмеження є рівнянням. І навпаки, якщо основне обмеження прямої задачі є рівнянням, то відповідна змінна двоїстої задачі може набувати будь-яких значень.

Коефіцієнти, що стоять при х­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, ­y­1 ≥ 0, y2 ≥ 0.

Розв’язок двоїстої задачі можна знайти за допомогою останнього рядка останньої симплексної таблиці прямої задачі (табл. 4).

0 0 0 54/25 44/25

основні х₁, х₂х₃, х₄, х₅ додаткові

додаткові у₄, у₅у₁, у₂, у₃ основні

маємо: У = (0; 54/25; 44/25 | 0; 0), F­_min­ = 378.

Двоїсті змінні показують міру дефіцитності ресурсів, вони чисельно рівні зміні цільової функції при зміні відповідного ресурсу на одиницю. Відповідно, зміна другого ресурсу на одиницю призводить до збільшення обсягу реалізації на у₂ = 54/25, третього – на у₃ = 44/25. Змінна у₁ = 0 вказують, що перший ресурс у надлишку, тому його збільшення до будь-якої зміни цільової функції не призведе.

Додаткові двоїсті змінні показують міру збитковості продукції, яку, згідно з розв’язком, недоцільно випускати. З розв’язку двоїстої задачі випливає, що збиткової продукції немає.

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ

№№ 201 – 300. Для виготовлення двох видів продукції Р₁ і Р₂ підприємство використовує три види сировини S₁, S₂, S₃. Запаси ресурсів, норми їх затрат і прибуток від реалізації одиниці продукції задано таблицею.

2. Скласти модель двоїстої задачі. Використовуючи відповідність між змінними прямої і двоїстої задач та симплексну таблицю для прямої задачі, записати оптимальний розв’язок двоїстої задачі.

Дата добавления: 2014-10-15