Главная | Обратная связь | Поможем написать вашу работу!

Алгоритм перетворення

Процес поліпшення варіанта розв’язку задачі полягає в перетворенні збудованої симплекс-таблиці в наступну симплекс-таблицю в такій послідовності.

1. Якщо добутий варіант розв’язку не виконує умови оптимальності, то в індексному рядку знаходять елемент , який найбільше порушує ці умови. Тобто при вибирають найбільш невід’ємний елемент , при – найбільш від’ємний елемент . Такий вибір елементів дає можливість змінити значення на максимальну величину при побудові наступної симплекс-таблиці.

2. Вибраний елемент індексного рядка означає головну колонку симплекс-таблиці. Ця колонка повинна мати хоча б один невід’ємний елемент . Якщо в ній такого елемента немає, то слід узяти наступний за відповідною ознакою (, або ) елемент індексного рядка. Випадок, коли для вибраних колонок, означає, що розв’язок задачі необмежений, тобто

3. Кожний вільний член ділять на відповідний елемент головної колонки і знаходять по кожному рядку симплексні співвідношення. Ще раз підкреслимо: ділять тільки на елементи

4. Вибирають мінімальне значення симплексного співвідношення

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

5. Мінімальне співвідношення відповідає головному рядку симплекс-таблиці.

6. На перетині головного рядка та головної колонки находиться генеральний, або, як його часто називають, розв’язувальний елемент Чому він має індекси ? .

7. Перетворюють елементи симплекс-таблиці за формулами

8. Складають нову сукупність базисних змінних, для чого змінну заміняють на , інші базисні змінні не змінюють.

9. Аналізують на оптимальність новий варіант розв’язку за одержаною симплекс-таблицею.

10. Якщо умови оптимальності виконуються, то переходять до виконання дій п.11, у протилежному разі – до дій п.1.

11. Знаходять числові значення оптимального варіанта:

– базисні змінні дорівнюють відповідним значенням , небазисні (вільні) змінні – нулю;

– значення цільової функції , якщо обчислювалось у процесі перетворення симплекс-таблиць, або після підстановки до її виразу знайдених значень змінних.

Алгоритм перетворення у загальному вигляді наведено на рис.1.12.

Кількість переходів від однієї симплекс-таблиці до іншої (так звана симплекс-ітерація) з метою знаходження оптимального варіанта (якщо він існує) залежить не від кількості змінних, а від кількості обмежень в діапазоні

План оптимальний

Так

Вибір

згідно з умовами оптимальності

Ні

Рис.1.12 Ліва стрілка вниз

1,5 т...3,0 т; кількість обчислювальних операцій одного симплекс-перетворення дорівнює приблизно 2 тп.

У процесі знаходження оптимального варіанта треба мати на увазі:

– якщо в головній колонці немає невід’ємних елементів, то це означає, що значення необмежене в напрямку пошуку;

– якщо в знайденому оптимальному варіанті до сукупності базисних змінних входить штучна змінна, то це означає, що задача не має розв’язку оскільки обмеження моделі несумісні;

– якщо в оптимальному варіанті будь-яка вільна змінна має в індексному рядку оцінку , то задача має множину оптимальних розв’язків; цілком зрозуміло, що коли всі вільні змінні , то це є ознакою тільки одного оптимального розв’язку;

– величини в індексному рядку кінцевої симплекс-таблиці вказують на діапазон , в якому можна змінювати відповідні коефіцієнти цільової функції без зміни оптимального розв’язку; при цьому значення можна знайти з виразу