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

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




 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
 

 


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

       
   
 
 

 


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

 

 
 

 

 


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

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

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

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

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

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

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

.

Розглянемо приклад знаходження оптимального розв’язку симплекс-методом.

Нехай задано таку математичну модель:

– цільова функція

– обмеження

за умови .

Наведену модель перетворюємо до розширеної форми:

Спочатку складаємо першу симплекс-таблицю:

 

      -2 -1         - М
     
- М   -5   -1        
                 
                 
                 
5 М +2 -3 М + 1 М        

 

Розв’язок знайдено тільки допустимий, тому знаходимо та . Потім складаємо другу симплекс-таблицю згідно з алгоритмом перетворення:

 

      -2 -1        
     
- 1   -5/3   -1/3       1/3
    5/3   1/3       -1/3
    8/3   1/3       -1/3
                 
11/3   1/3       М -1/3

 

 

Знайдений розв’язок є оптимальним:

– базисні змінні

– вільні змінні

Цільова функція має значення

 

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...