1) Завдання лінійного програмування і різні форми її запису

Оптимізація і математичні методи прийняття рішень

Якщо цільова функція і система обмежень лінійні. то задача математичного програмування називається задачею лінійного програмування (ЗЛП).

Основна форма ЗЛП

Симетрична форма ЗЛП

Загальна задача лінійного програмування

Будь-яке завдання лінійного програмування приводиться до стандартної (канонічної) формі основної задачі лінійного програмування, яка формулюється так: знайти невід'ємні значення змінних X1, X2, Xn, які відповідають обмеженням у вигляді рівності:

A11X1 + A12X2 + ... + A1nXn = B1;

A21X1 + A22X2 + ... + A2nXn = B2;

Am1X1 + Am2X2 + ... + AmnXn = Bm;

і звертають в максимум лінійну функцію цих змінних:

E = C1X1 + C2X2 + ... + CnXn Þ max

При цьому також потрібно, щоб праві частини рівностей були невід'ємні, тобто повинні дотримуватися умови:

Приведення до стандартної форми необхідно, так як більшість методів вирішення завдань лінійного програмування розроблено саме для стандартної форми. Для приведення до стандартної форми завдання лінійного програмування може знадобитися виконати такі дії:

перейти від мінімізації цільової функції до її максимізації;

змінити знаки правих частин обмежень;

перейти від обмежень-нерівностей до рівності;

позбутися від змінних, які не мають обмежень на знак.

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

2) Приведення загальної задачі лп до канонічного вигляду.

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

Правило приведення завдання лінійного програмування до канонічного виду полягає в наступному:

якщо у вихідній задачі потрібно визначити максимум лінійної функції, то слід змінити знак і шукати мінімум цієї функції;

якщо в обмеженнях права частина негативна, то слід помножити це обмеження на -1;

якщо серед обмежень є нерівності, то шляхом введення додаткових невід'ємних змінних вони перетворюються в рівності;

Приклад 1. Приведення до канонічної формі завдання лінійного програмування:

Min l = 2x1 + x2 - x3; 2x2 - x3 ≤ 5; x1 + x2 - x3 ≥ -1; 2x1 - x2 ≤ -3; x1 ≤ 0; x2 ≥ 0; x3 ≥ 0.

Введемо в кожне рівняння системи обмежень вирівнюють змінні x4, x5, x6. Система запишеться у вигляді рівності, причому в перше і третє рівняння системи обмежень змінні x4, x6 вводяться в ліву частину зі знаком "+", а в друге рівняння змінна x5 вводиться зі знаком "-".

Вільні члени в канонічній формі повинні бути позитивними, для цього два останніх рівняння помножимо на -1:

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

3) Умова оптимальності базисного плану канонічної задачі ЛП. Симплекс-метод і його збіжність.

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

Так як число опорних рішень звичайно, то через кінцеве число кроків отримаємо оптимальне опорне рішення. Опорним рішенням називається базисне невід'ємне рішення.

Алгоритм симплексного методу 1. Математична модель задачі має бути канонічною. Якщо вона неканонічна, то її треба привести до канонічного виду. 2. Знаходимо вихідне опорне рішення і перевіряємо його на оптимальність. Для цього заповнюємо симплексну таблицю 1. Всі рядки таблиці 1-го кроку заповнюємо за даними системи обмежень і цільової функції.

Можливі такі випадки при вирішенні задач на максимум:

1. Якщо всі коефіцієнти останнього рядка симплекс-таблиці j 0, то знайдене

2 Якщо хоча б один коефіцієнт j 0, але при відповідній змінної немає жодного позитивного оцінного ставлення, то рішення задачі припиняємо, так какF (X) , т.е.целевая функція не обмежена в області допустимих рішень.

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

4. Якщо негативних коефіцієнтів в останньому рядку кілька, то в стовпець базіснойпеременной (БП) вводять ту змінну. якої відповідає найбільший за абсолютною велічінеотріцательний коефіцієнт.

5. Якщо хоча б один коеффіціентk <0 ,то k- тый столбец принимаем за ведущий.

6. За провідну рядок приймаємо ту, якої відповідає мінімальне відношення вільних членів bi до позитивних коефіцієнтам ведучого, k- того стовпця.

7. Елемент, що знаходиться на пересеченііведущіх рядків і стовпці, називаетсяведущім елементом.

Заповнюємо симплексну таблицю 2:

 заповнюємо базисний стовпець нулями і одиницею

 переписуємо провідний рядок, розділивши її на провідний елемент

 якщо провідна рядок має нулі, то в наступну симплекс-таблицю можна перенести відповідні стовпці

 інші коефіцієнти знаходимо за правилом "прямокутника"

Отримуємо нове опорне рішення, яке перевіряємо на оптимальність:

Якщо всі коефіцієнти останнього рядка j 0, то знайдене рішення максимальне.

Якщо немає, то заповнюємо симплексну таблицю 8-го кроку і так далі.

Якщо цільова функція F (X) вимагає знаходження мінімального значення. то критерієм оптимальності задачі є непозитивним коефіцієнтів jпрі всехj = 1,2.n.

Збіжність симплекс-методу. Виродженість в задачах ЛП. Найважливішим властивістю будь-якого обчислювального, алгоритму є збіжність, т. Е. Можливість отримання в ході його застосування шуканих результатів (із заданою точно-стю) за кінцеве число кроків (ітерацій).

Легко помітити, що проблеми зі збіжністю симплекс-ме-тода потенційно можуть виникнути на етапі вибору значення r (п. 2 ") в разі, коли однакові мінімальні значення від-носіння

будуть досягнуті для кількох рядків таблиці Т (q) одночасним-аме. Тоді на наступній ітерації стовпець b (β (q + 1)) буде спів-тримати нульові елементи.