Симплексний метод розв’язування задач лінійного програмування
Автор: pidorpidaras • Март 29, 2023 • Лабораторная работа • 349 Слов (2 Страниц) • 176 Просмотры
Лабораторна робота №4
Тема 5. Симплексний метод розв’язування задач лінійного програмування
Мельничук Давид
Варіант №10
Завдання №1 (Завдання О1 № 11)
За умовою завдання, дано модель задачі, необхідно знайти її розв’язки, якщо такі існують, за допомогою симплекс-методу:
[pic 1]
Рис. 1.1. Умова завдання.
Для початку, необхідно вище вказану систему у вигляді матриці:
[pic 2] | [pic 3] | [pic 4] | [pic 5] | [pic 6] |
5 | 1 | 1 | 0 | 10 |
1 | 3 | 0 | 1 | 9 |
Далі в якості базових змінних приймаємо та , після чого виразимо їх через інші змінні:[pic 7][pic 8]
= - + 10[pic 9][pic 10][pic 11]
= - 3 + 9[pic 12][pic 13][pic 14]
Підставимо виражені змінні у цільову функцію:
= + 6 = 0[pic 15][pic 16][pic 17]
[pic 18]
[pic 19] | [pic 20] | [pic 21] | [pic 22] |
5 | 1 | 1 | 0 |
1 | 3 | 0 | 1 |
Запишемо матрицю коефіцієнтів для подальшого використання під час проведення розрахунків:
Далі будемо розв’язувати систему рівнянь відносно базисних змінних та , тому запишемо першу симплекс-таблицю: [pic 23][pic 24]
Базис | b | [pic 25] | [pic 26] | [pic 27] | [pic 28] |
[pic 29] | 10 | 5 | 1 | 1 | 0 |
[pic 30] | 9 | 1 | 3 | 0 | 1 |
[pic 31] | 0 | -2 | -6 | 0 | 0 |
Зробивши висновки з вище вказаних даних, можемо зробити висновок, що вказаний план не є оптимальним, оскільки містить в собі від'ємні значення, тому переходимо до подальших операцій.[pic 32]
Для подальших обчислень необхідно обрати нову базисну змінну: найкращим варіантом буде вибір стовпчика, який відповідає змінній . Обчислимо за формулою та оберемо найменше зі значень, оскільки нам необхідний мінімум:[pic 33][pic 34][pic 35]
[pic 36]
[pic 37]
В базисі функції буде 0, оскільки при діленні нуля на будь-яке значкення завжди буде нуль. Записуємо наступну симплекс-таблицю з отриманими значеннями:
...