Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
| Колишня базисна при цьому в новому наборі стає вільною, небазисною (з нульовим значенням).
А ось яку саме виводити з базису, а яку вводити в базис - при цьому дивляться на збільшення функціоналу: Вводять ту змінну в базис, заміна на яку в базисі, принесе в базис найбільше збільшення функціоналу. Тепер трохи про сам алгоритм На початковому "нульовому" кроці ми приймемо всі додаткові змінні, як базисні (за механізмом введення додаткових змінних ми на цьому кроці відразу отримали систему, що визначена щодо базисних змінних), а початкові змінні як небазисні. Нижче (крок 0) показана заповнена симплекс таблиця для нульового кроку - додаткові змінні записані тут в перший стовпець симплекс-таблиці а початкові змінні в перший рядок. У разі якщо у початковій оптимізаційній задачі необхідно знайти не мінімум, а максимум - знаки коефіцієнтів цільової функції F змінюються на протилежні: a0,n=-a0,n. Знаки коефіцієнтів (для задач типу (*)) обмежуючих умов зі знаком "≥" так само змінюються на протилежні. У разі якщо умова містить знак "≤" - коефіцієнти запишуться без змін (для (**) ми вже це зробили). При кожній ітерації елементи симплекс-таблиці перераховують за правилами - (1). КОРОТКО нагадаємо зміст ітерацій симплекс методу СМ: На початку необхідно потрапити в будь-яку допустиму вершину (рішення): На нульовому кроці перевіряємо, чи перебуваємо ми в допустимої точці: змінні в рішеннях-вершинах можуть приймати тільки позитивні значення, а оскільки на нульовому кроці приймається рішення, що всі небазисні змінні = 0, то (див систему 1-2), всі базисні стають рівними відповідним вільним членам bi, таким чином перевірка на допустимість - це відсутність в вільних членах від’ємних елементів ! ! Якщо ми знаходимося в допустимої вершині, то перевіряємо чи не оптимальною є вона, і якщо ні, то вибираємо перехід в наступну допустиму вершину з найкращим приростом функціоналу. І так далі до оптимальної вершини сімлекса ! ! Якщо ж ми в нульовому кроці знаходимося в неприпустимій вершині, то виключаючи на наступних ітераціях з базисного рішення змінні з від'ємним значенням, ми або прийдемо до допустимої вершині і продовжимо шлях по симплекс до оптимальної вершини, або переконаємося що немає допустимих вершин і таким чином рішення у ЛР задачі немає. жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|