нь.
. Будуємо вектор найшвидшого зростання цільової функції - вектор градиентного напрямки.
. Проводимо довільну лінію рівня.
. При вирішенні завдання на максимум переміщаємо лінію рівня в напрямку вектора з так, щоб вона стосувалася області допустимих рішень у її крайньому положенні (крайній точці). Що стосується виконання завдання на мінімум лінію рівня переміщують у антіградіентном напрямку.
. Визначаємо оптимальний план і екстремальне значення цільової функції.
.4 Симплексний метод розв'язування ЗЛП
Загальна ідея симплексного методу (методу послідовного поліпшення плану) для вирішення ЗЛП складається
) вміння знаходити початковий опорний план;
) наявність ознаки оптимальності опорного плану;
) вміння переходити до нехудшему опорному плану.
Нехай ЗЛП представлена ??системою обмежень в канонічному вигляді:
Кажуть, що обмеження ЗЛП має доцільний вид, якщо при неотрицательной правій частині ліва частина обмежень містить змінну, що входить з коефіцієнтом, рівним одиниці, а в інші обмеження рівності - з коефіцієнтом, рівним нулю.Пусть система обмежень має вигляд
Зведемо задачу до канонічного вигляду. Для цього додамо до лівим частинам нерівностей додаткові змінні. Отримаємо систему, еквівалентну вихідної:
, яка має доцільний вид.
У цільову функцію додаткові змінні вводяться з коефіцієнтами, рівними нулю.
Нехай далі система обмежень має вигляд
.
Зведемо її до еквівалентної відніманням додаткових змінних з лівих частин нерівностей системи. Отримаємо систему
Однак тепер система обмежень не має переважного вигляду, так як додаткові змінні входять в ліву частину (при) з коефіцієнтами, рівними - 1. Тому, взагалі кажучи, базисний план не є допустимим. У цьому випадку вводиться так званий штучний базис. До лівих частинам обмежень-рівностей, що не мають переважного виду, додають штучні змінні. У цільову функцію змінні, вводять з коефіцієнтом М у разі рішення задачі на мінімум і з коефіцієнтом - М для задачі на максимум, де М - велике позитивне число. Отримана задача називається М-завданням, відповідної вихідної. Вона завжди має доцільний вид.
Нехай вихідна ЗЛП має вигляд
причому жодне з обмежень не має кращою змінної. М-задача запишеться так:
,,,
Завдання (2.19) - (2.21) має переважний план. Її початковий опорний план має вигляд
Якщо деякі з рівнянь (2.17) мають доцільний вид, то в них не слід вводити штучні змінні.
Теорема. Якщо в оптимальному плані
(2.22)
М-задачі (2.19) - (2.21) всі штучні змінні, то план
є оптимальним планом вихідної задачі (2.16) - (2.18).
Для того щоб вирішити завдання з обмеженнями, що не мають переважного виду, вводять штучний базис і вирішують розширену М - задачу, яка має початковий опорний план
Рішення вихідної задачі симплексним методом шляхом введення штучних змінних називається симплексним методом зі штучним базисом.
Якщо в результаті застосування симплексного методу до розширеної завданню отриманий оптимальний план, в якому всі штучні змінні, то його перші n компоненти дають оптимальний план вихідної задачі.
Теорема. Якщо в оптимальному плані М-задачі хоча б одна з штучних змінних відмінна від нуля, то вихідна задача не має допустимих планів, т. Е. Її умови несумісні.
Ознаки оптимальності.
Теорема. Нехай вихідна завдання вирішується на максимум. Якщо для деякого опорного плану всі оцінки невід'ємні, то такий план оптимальний.
Теорема. Якщо вихідна завдання вирішується на мінімум і для деякого опорного плану всі оцінки непозитивні, то такий план оптимальний.
3. Розв'язання задач лінійного програмування З ВИКОРИСТАННЯМ MICROSOFT EXCEL
лінійний програмування симплексний графічний
Приклад 1: Потрібно скласти такий раціон годівлі тварин трьома видами корму, при якому вони отримають необхідну кількість поживних речовин A і B і собівартість кормів буде мінімальна.
Ціни кормів, необхідну кіль...
