Тема 2. Лінійні оптимізаційні задачі

 

Якщо цільова функція (1.1) і система обмежень (1.2) є лінійно залежними від змінних , для розв’язку оптимізаційної задачі використовуються методи лінійного програмування. Лінійна математична модель у загальному випадку має наступний вид:

                                 (2.1)

де  ‑ задані постійні величини, ; .

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

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

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

Таким чином,

 

2.1 Графічний розв’язок задачі лінійного програмування

 

Цей метод є досить простим, наочним і дозволяє зробити деякі загальні висновки щодо розв’язку оптимізаційних задач методами лінійного програмування. Однак, застосування графічного методу обмежено задачами невеликої розмірності. Розглянемо математичну модель лінійної оптимізаційної задачі, в якій потрібно знайти мінімум цільової функції:

,

при обмеженнях:

і граничних умовах незаперечності змінних:

.

Після введення додаткових змінних х₃, х₄, х₅ перейдемо від обмежень-нерівностей до рівностей:

                                       (2.2)

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

Відкладемо на горизонтальній осі значення змінної х₁, а на вертикальній осі – значення змінної х₂ (рис. 2.1). З огляду на граничні умови , штрихуванням виділимо напівплощини допустимих значень змінних х₁ і х₂ (вправо від осі х₂ і нагору від осі х₁).

Розглянемо одне з обмежень-рівностей, наприклад, перше

і перепишемо його у вигляді:

.

Прирівнюємо змінну х₃ до нуля:

.

Останнє співвідношення являє собою рівняння прямої лінії на площині х₁х₂. На цій прямій значення х₃=0. Отже, по одну сторону від цієї прямої х₃>0, по іншу х₃<0. З огляду на граничну умову x₃≥0, штрихуванням виділимо напівплощину, у якій х₃>0.

Рис.2.1. Ілюстрація графічного розв’язку задачі

 

Аналогічні графічні побудови виконаємо для другого і третього обмежень системи (2.2).

В результаті виконаних графічних побудов на площині х₁х₂ виділиться область Ω допустимих значень змінних х₁, х₂, х₃, х₄, х₅ (рис. 2.1). Ця область являє собою опуклий багатогранник abcde. Всі допустимі розв’язки задачі, в тому числі й оптимальний розв’язок, будуть належати області Ω.

Розглянемо вираз цільової функції й прирівняємо його до нуля:

.

У площині х₁х₂ ‑ це рівняння прямої лінії, що проходить через початок координат (рис. 2.1).

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

та побудуємо в площині х₁х₂ відповідну пряму (рис. 2.1).

Прямі Z=const є лініями рівного рівня цільової функції, оскільки на кожній такій лінії значення цільової функції є незмінним. Лінії рівного рівня паралельні між собою. За взаємним розташуванням ліній рівного рівня Z=0 і Z=1 визначимо напрямок зростання цільової функції Z. Це напрямок зазначений на рис. 2.1 стрілкою.

Переміщаючи пряму цільової функції Z у напрямку її зростання паралельно самій собі, визначимо найближчу точку, приналежної області Ω допустимих значень змінних.

Відповідно до графічних побудов такою точкою буде вершина е багатогранника Ω (рис. 2.1). Ця вершина й буде відповідати мінімуму цільової функції, тобто оптимальному розв’язку задачі.

Мінімальне значення цільової функції Z досягається при наступних значеннях змінних:

х₂>0,  х₃>0,  х₄>0,  х₁=0,  х₅=0.

Три змінні відрізняються від нуля, дві змінні рівні нулю. Видно, що кількість не рівних нулю змінних дорівнює кількості обмежень. Інші змінні дорівнюють нулю.

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

.

Обмеження й граничні умови при цьому не змінюються.

На рис. 2.2 виконаний графічний розв’язок задачі. З побудови прямих  і  або  видно, що зміна знаків коефіцієнтів с₁ і с₂ обумовила зміну напрямку зростання цільової функції на протилежний (див. стрілку на рис. 2.2). Очевидно, що в цьому випадку мінімуму цільової функції відповідає вершина b багатогранника Ω.

Таким чином, задачі мінімізації й максимізації цільової функції вирішуються зовсім однаково. Варто тільки мати на увазі, що

Рис.2.2. Визначення максимуму цільової функції

 

На підставі виконаного графічного розв’язку задачі лінійного програмування можна зробити наступні загальні висновки щодо розв’язку лінійної оптимізаційної задачі:

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

‑ у кожному розв’язку, що відповідає одній з вершин багатогранника Ω, кількість додатних (не рівних нулю) змінних дорівнює кількості обмежень m, інші (n-m) змінні дорівнюють нулю;

‑ для відшукання оптимального розв’язку варто розглянути тільки ті розв’язки, які містять m змінних, не рівних нулю, і (n-m) змінних, рівних нулю.

Надалі відмінні від нуля додатні змінні будемо називати базисними, нульові змінні ‑ вільними. В кожному розглянутому розв’язку кількість базисних змінних дорівнює кількості обмежень m, а кількість вільних змінних дорівнює (n-m).

Оскільки кількість базисних і вільних змінних в розглянутих розв’язках не змінюється, при переході від одного розв’язку до іншого (від однієї вершини багатогранника Ω до іншої) одна з базисних змінних стає вільною, а одна з вільних змінних стає базисною.