Алгоритм симплексного методу
Завдання лінійного програмування.
Контрольні питання і завдання.
1.Як завдання лінійного програмування (ЛП) називають загальною, стандартної, канонічної (основний)?
2. Як перейти від однієї форми запису задачі ЛП до іншої?
3. Які завдання лінійного програмування можна вирішувати симплексним методом?
4. Як ознака оптимальності в симплексному методі?
5. Як будується опорний план?
6. Як визначається роздільна рядок і дозволяє стовпець?
7. Як здійснюється перерахунок елементів симплексного таблиці?
Симплексний метод є універсальним, так як дозволяє вирішити будь-яке завдання лінійного програмування, задану в канонічному вигляді.
Ідея симплексного методу (методу послідовного поліпшення плану) полягає в тому, що, починаючи з деякого вихідного опорного рішення, здійснюється послідовно спрямоване переміщення по опорним рішенням завдання до оптимального. Значення цільової функції при цьому переміщенні для задач на максимум не убуває. Оскільки число опорних рішень звичайно, через кінцеве кількість кроків отримаємо оптимальне опорне рішення.
Для зручності обчислень симплексним методом складають сімплексні таблиці. У рядку зверху (сj) вказують коефіцієнти всіх змінних цільової функції, в рядку знизу - оцінки # 8710; j.
Алгоритм симплексного методу.
1. Математична модель задачі має бути канонічною. Якщо вона неканонічна, то її потрібно привести до канонічного виду.
2. Заповнюємо симплексну таблицю. Всі рядки таблиці 1-го кроку, за винятком рядка # 8710; j (індексна (оціночна) рядок), заповнюємо за даними системи обмежень і цільової функції. Знаходимо вихідне опорне рішення.
3. Перевіряємо знайдене опорне рішення на оптимальність. Оціночна рядок знаходиться за формулою
для змінних і для вільного члена.
При вирішенні завдання на максимум можливі наступні випадки
·. тоді знайдене рішення оптимально;
· Хоча б одна оцінка. але при ній немає жодного позитивного коефіцієнта, тоді цільова функція не обмежена і рішення задачі припиняємо;
· Хоча б одна оцінка. і при ній є хоча б один позитивний коефіцієнт, тоді можна перейти до нового оптимального плану, якому відповідав би більшого значення функції;
· Якщо негативних оцінок кілька, то в базис вибираємо ту змінну, якій відповідає найбільша за абсолютною величиною негативна оцінка
Нехай одна оцінка # 8710; k <0 или наибольшая по абсолютной величине ∆k <О, тогда k-ю графу принимаем за разрешающую .
За роздільну рядок приймаємо ту, якої відповідає мінімальне відношення вільних членів (bi) до позитивних коефіцієнтам k-ї графи. Елемент, що знаходиться в роздільній рядку і дозвільному стовпці, називають дозволяє елементом.
4. Заповнюємо симплексну таблицю 2-го кроку:
• переписуємо роздільну рядок, розділивши її на дозволяючий елемент;
• заповнюємо базисні графи;
• інші коефіцієнти таблиці знаходимо за правилом "прямокутника" або за спрощеною схемою. Отримуємо нове опорне рішення.
5. Повертаємося до першого кроку алгоритму.
Завдання. Вирішити задачу лінійного програмування
Рішення. Вихідна задача приводиться до канонічного вигляду
Крок 1. Складаємо першу симплексну таблицю