MOP

ЧАСТИНА 1. ЛІНІЙНЕ І ЦІЛОЧИСЕЛЬНЕ ПРОГРАМУВАННЯ

ГЕОМЕТРИЧНА ІНТЕПРЕТАЦІЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

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

Розглянемо задачу в стандартній формі з двома змінними:

L 3x1 3x2 min(max)

x1 x2 8,

2x1 x2 1,x1 2x2 2,

x1 0, x2 0;

До такої форми може бути зведена і канонічна задача ( з обмеженнями у виді рівнянь), коли число змінних n більше числа рівнянь m на 2, тобто n - m = 2.

Множина рішень кожної нерівності із системи обмежень є напівплощина.

Побудуємо границі напівплощин - прямі

x1 x2 8, 2x1 x2 1, x1 2x2 2, x1 0, x2 0 .

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

ABCD (мал.1).

5

визначаємо координати точки А (3 ; 5) і точки В (2 ; 6).

У результаті одержуємо:

найменше значення Lmin=1.5 функція цілі набуває в точці D (0.5 ;0);

найбільше значення Lmax=24 функція цілі набуває в будь-якій точці відрізка АВ.

ЗАВДАННЯ №1

Використовуючи геометричну інтепретацію задач лінійного програмування,

визначити екстремальні значення функції цілі при заданій системі обмежень (або переконатись в її нерозв'язності).

7

8

СИМПЛЕКСНИЙ МЕТОД ВИРІШЕННЯ ЗАГАЛЬНОЇ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Розглянемо задачу лінійного програмування в загальному вигляді:

Довільну задачу лінійного програмування можна вирішити за допомогою універсального математичного методу, який отримав назву симплексного методу.

Але для його використання необхідно привести систему граничних умов поставленої задачі до канонічного вигляду, добавивши додаткові змінні xn i 0, i 1, m . В результаті отримали розширену задачу, еквіваленту вихідній задачі. У функцію цілі додаткові змінні вводяться з нульовими коефіцієнтами:

Якщо кожна гранична умова системи обмежень має змінну, що входить у ліву частину умови з коефіцієнтом, рівним 1, а в усі інші – рівним 0, (при не негативних вільних елементах) то система подана у бажаному вигляді. Такі змінні можна назвати базисними. Щоб отримати опорне рішення, необхідно всі змінні, крім базисних, прирівняти до нуля, а базисним надати значення правих

9

частин відповідних рівнянь. Змінні, що набули значення нуля, називаються

вільними.

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

Далі виконуємо симплексні перетворення:

обчислення проводяться доти доти, поки в оцінному рядку не будуть знаходитись невід`ємні оцінки для задачі максимізації або з недодатні оцінки для задачі мінімізації;

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

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

(мінімізації) – цей стовпець буде вирішаючим;

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

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

називається вирішаючим;

далі будуємо нову симплексну таблицю на основі елементів вихідної таблиці :

1. Елементи вирішаючого рядка діляться на вирішаючий елемент. Нехай

вирішаючим буде r-й рядок.

10

2. Елементи вирішаючого стовпця, всі, крім вирішаючого, діляться на

вірішаючий елемент з протилежним знаком, а вирішаючий дорівнює своєму оберненому значенню. Нехай вирішаючим буде s-й стовпець.

3.Елементи, що залишилися, у таблиці обчислюються за правилом прямокутника,

завжди починаючи з вирішаючого елемента:

Тобто, у вихідній таблиці виділяємо прямокутник, вершинами якого служать наступні елементи: вирішаючий, шуканий, а також елементи з вирішаючого рядка і стовпця. Діагональ, що містить вирішаючий і шуканий елементи, назвемо

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

Розглянемо крок симплексних перетворень на прикладі:

11