Задача по "Оптимизации (симплекс метод)"
Автор: ElenaP1988 • Февраль 7, 2023 • Задача • 520 Слов (3 Страниц) • 149 Просмотры
Задание. Решить задачу ЛП симплекс - методом
𝐿 = 𝑥1 − 𝑥2 → 𝑚𝑎𝑥 2𝑥1 + 𝑥2 ≤ 5 2𝑥1 + 𝑥2 ≥ 2 𝑥1 + 2𝑥2 ≤ 10 𝑥1 ≥ 0, 𝑥2 ≥ 0 | (1) |
Решение. Приведем задачу (1) к канонической форме:
𝐿 = 𝑥1 − 𝑥2 → 𝑚𝑎𝑥 2𝑥1 + 𝑥2 + 𝑦1 = 5 2𝑥1 + 𝑥2 − 𝑦2 = 2 𝑥1 + 2𝑥2 + 𝑦3 = 10 𝑥𝑖 ≥ 0, 𝑖 = 1̅̅, ̅2 𝑦𝑖 ≥ 0, 𝑖 = 1̅̅,̅3̅ | (2) |
Запишем задачу (2) в специальной форме (переменные 𝑦𝑖 - базисные):
𝐿 = 0 − (−𝑥1 + 𝑥2) → 𝑚𝑎𝑥 𝑦1 = 5 − (2𝑥1 + 𝑥2) 𝑦2 = −2 − (−2𝑥1 − 𝑥2) 𝑦3 = 10 − (𝑥1 + 2𝑥2) 𝑥𝑖 ≥ 0, 𝑖 = 1̅̅, 2 𝑦𝑖 ≥ 0, 𝑖 = 1̅̅,̅3̅ | (3) |
Решим задачу (3) прямым симплекс-методом. Допустимая симплексная таблица приведена в таблице 1.
Таблица 1 – Допустимая симплексная таблица
𝑏 | 𝑥1 | 𝑥2 | 𝑥3 | |
𝐿 | 0 | -4 | -5 | -1 |
𝑦1 | 10 | 3 | 2 | 0 |
𝑦2 | 11 | 1 | 4 | 0 |
𝑦3 | 13 | 3 | 3 | 1 |
Последовательное решение задачи (3) прямым симплекс-методом представлено в таблицах 2, 3, 4.
Таблица 2 – Результат первой итерации прямого симплекс-метода[pic 1][pic 2]
𝑏 | 𝑥1 | 𝑦2 | 𝑥3 | |
𝐿 | 55 [pic 3] 4 | 11 − 4 | 5 [pic 4] 4 | -1 |
𝑦1 | 9 [pic 5] 2 | 𝟓 [pic 6] 𝟐 | 1 − 2 | 0 |
𝑥2 | 11 [pic 7] 4 | 1 [pic 8] 4 | 1 [pic 9] 4 | 0 |
𝑦3 | 19 [pic 10] 4 | 9 [pic 11] 4 | 5 [pic 12] 4 | 1 |
Таблица 3 – Результат второй итерации прямого симплекс-метода[pic 13]
𝑏 | 𝑦1 | 𝑦2 | 𝑥3 | |
𝐿 | 187 [pic 14] 10 | 11 [pic 15] 10 | 7 [pic 16] 10 | -1 |
𝑥1 | 9 [pic 17] 5 | 2 [pic 18] 5 | 1 − 5 | 0 |
𝑥2 | 23 [pic 19] 10 | 1 − 10 | 3 [pic 20] 10 | 0 |
𝑦3 | 7 [pic 21] 10 | 9 − 10 | 3 − 10 | 1 |
Таблица 4 – Оптимальная симплексная таблица[pic 22][pic 23][pic 24][pic 25]
𝑏 | 𝑦1 | 𝑦2 | 𝑦3 | |
𝐿 | 97 [pic 26] 5 | 1 [pic 27] 5 | 2 [pic 28] 5 | 1 |
𝑥1 | 9 [pic 29] 5 | 2 [pic 30] 5 | 1 − 5 | 0 |
𝑥2 | 23 [pic 31] 10 | 1 − 10 | 3 [pic 32] 10 | 0 |
𝑥3 | 7 [pic 33] 10 | 9 − 10 | 3 − 10 | 1 |
Решение 𝑥 = (9 , 23 , 0) является оптимальным, но не является[pic 34][pic 35][pic 36][pic 37][pic 38]
...