Тема 2. Лекція 2. Лінійне програмування: графічний метод і розробка моделі.

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

0. математичні моделі великої кількості практичних задач лінійні щодо шуканих змінних;

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

В области электросвязи методами линейного программирования решаются такие задачи:

1. отыскание местоположения узла или станции на сети;

2. распределение емкости существующих АТС между новыми районами застройки;

3. выбор оптимальных направлений потоков сообщений;

4. распределение работников по операциям и т.д.

Основна задача лінійного програмування (ОЗЛП).

Основна задача лінійного програмування ставитися в такий спосіб.

Є ряд змінних х₁, х₂, … х_n. Потрібно знайти такі невід’ємні значення цих змінних, котрі задовольняють системі рівнянь:

a₁₁x₁+a₁₂x₂+…+a_1nx_n = b₁;

a₂₁x₁+a₂₂x₂+…+a_2nx_n = b₂;

. . . . . . . . . . . . . . . . . . . . .

a_m1x₁+a_m2x₂+…+a_mnx_n=b_m;(2...1)

і перетворювали в мінімум функцію

W = c₁x₁+c₂x₂+…+c_nx_n,де х₁ ≥0; х₂≥0; … х_n≥0.

яка називається цільовою функцією задачі.

Припустимим рішенням називається сукупність невід’ємнних х, що задовольняють рівнянням системи.

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

Задачі лінійного програмування вирішуються в два етапи:

1. знаходження припустимих рішень;

2. пошук оптимальних рішень серед припустимих.

Властивості припустимих рішень.

При розгляді властивостей рішень систем лінійних рівнянь виду (2.1) можливі три випадки: m=n, m>n, m<n.

Якщо число рівнянь m дорівнює числу перемінних n, і визначник системи (2.1) не дорівнює 0, то система має єдине рішення. Якщо всі змінні системи невід’ємнні, те це рішення буде припустимим. Оскільки таке рішення єдине, те воно буде й оптимальним.

У класичних задачах лінійного програмування, як правило, m>n. У таких задачах, якщо система сумісна, те існує нескінченна множина її рішень. При цьому m-n змінним можна надавати довільні значення в рамках обмежень, і такі змінні називаються вільними. Інші m змінних можуть бути виражені через вільні і називаються базисними. Базисні змінні вибираються за допомогою спеціального алгоритму.

Якщо число вільних змінних не більш 2-х, те задачу можна вирішити графічно.

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

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

Розробка моделей лінійного програмування.

Термін «розробка» означає побудову моделей лінійного програмування для практичних задач. Розробка моделі містить у собі три етапи:

1. Визначення перемінні задачі.

2. Представлення обмежень на значення перемінних у виді лінійних чи рівнянь нерівностей.

3. Завдання лінійної цільової функції, що підлягає чи мінімізації максимізації.

Приклад. Оптимізація побудови мережі телевізійного віщання.

Для побудови мережі телевізійного віщання на території площею 30 000 тис. кв. км пропонується використовувати телевізійні станції 2-х типів із загальною споживаною потужністю не більш 125 квт. Загальна чисельність штату на всіх станціях не винна перевищувати 24 шт. од.

Параметри станцій наведені в таблиці.

Тип станції	1	2
Площа, що обслуговується, кв. км.	500	10 000
Чисельність штату, шт. од.	0,15	8
Споживана потужність, квт	0,63	55
Приведені витрати, тис. грн.	15	200

Задана площа обслуговування враховує деяке взаємне перекриття зон обслуговування.

Потрібно визначити оптимальне число станцій типів 1 і 2 при, якому приведені витрати на всю мережу будуть найменшими.

Рішення.

Шукане число станцій 1 і 2 приймаємо за керовані змінні х₁ і х₂ відповідно Х = (х_1,х₂). Сумарні витрати на мережу W(X) = 15x₁ + 200x₂.

Оптимізаційна математична модель: знайти невід’ємнні значення зінних х₁ і х₂, при яких цільова функція

W(х_1,х₂) = 15x₁ + 200x₂ è min (2.2)

і задовольняють обмеженням:

500 х₁ + 10000х₂ ≥ 30000

0,15 х₁ + 8х₂ ≤ 24

0,63 х₁ + 55х₂ ≤ 125

Задача вирішується методом лінійного програмування (ЛП). Приводимо її до ОЗЛП у такий спосіб:

в усіх нерівностях перенесемо в ліві частини постійні величини і дві останніх нерівності помножимо на –1, помінявши знаки нерівностей:

500 х₁ + 10000х₂ - 30000 ≥ 0

- 0,15 х₁ - 8х₂ + 24 ≥ 0

- 0,63 х₁ - 55х₂ + 125 ≥ 0

введемо нові невід’ємнні змінні х_3, х_4, х₅:

х₃ = 500 х₁ + 10000х₂ - 30000 ≥ 0

х₄ = - 0,15 х₁ - 8х₂ + 24 ≥ 0

х₅ = - 0,63 х₁ - 55х₂ + 125 ≥ 0 (2.3)

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

Розглянута задача являє собою класичну задачу лінійного програмування, де загальне число змінних n=5, кількість базисних змінних m=3, кількість вільних змінних k=n-m=2. Оскільки k=2 , то рішення задачі можна знайти графічно.

Умови невід’ємності змінних обмежують область їхніх припустимих значень першим квадрантом (тобто частиною площини, розташованої над віссю х₁ і зправа від осі х₂). Інші границі простору не відбиті на площині Х₁, Х₂. Прямі лінії будуються по рівняннях системи (2.3).

Надамо базисним змінним найменшого можливого значення х₃=х₄=х₅=0 і побудуємо відповідні прямі.

Для рівняння х₃=0 відрізки відтинаються прямої на осях координат складуть відповідно:

при х₂=0 х₁=30000/500=60

при х₁=0 х₂=30000/10000=3

З одному боку від необмеженої прямої (вправо нагору) значення змінної х₃ будуть позитивними, з іншого - негативними.

Нанесемо на малюнок відрізки, що відповідають припустимим (позитивним) значенням змінних. Ту ж процедуру проробимо для рівнянь х₄ = 0 і х₅ = 0.

Для х₄ = 0 при х₂ = 0 х₁ = 160; при х₁ = 0 х₂ = 3.

Для х₅ = 0 при х₂ = 0 х₁ = 198,41; при х₁ = 0 х₂ = 2,27.

Частина площини, що задовольняє всім обмеженням, називається областю припустимих рішень (ОПР). Шукана область припустимих рішень показана на малюнку. На малюнку ця область заштрихована; її вершини позначені буквами ABCD (Мал.2.1).

Після завершення 1-го етапу рішення (побудови ОПР) необхідно знайти таку крапку цієї області, що забезпечить виконання умови (2.2), тобто є рішенням задачі. Для цього цільову функцію представимо у вигляді додаткового обмеження:

W - 15x₁ - 200x₂ ≥ 0.

Зобразимо його прямою W:

W - 15x₁ - 200x₂ = 0. (2.4)

Мінімальне значення W прийме, якщо пряма, що її представляє, торкнеться ОПР у самій лівій її частині - у точці А чотирикутника ABCD. При збільшенні W (2.4) пряма переміщається вправо. Крапку торкання прямої W (2.4) можна визначити вирішивши систему рівнянь для х₃ = 0 і х₅ = 0 з (2.3). У результаті одержуємо х₁ = 20 і х₂ = 2. Звідси випливає, що W = 700. Координати крапки А (20; 2) і є рішенням задачі. У розглянутому випадку оптимальне рішення – єдине.

При W < 700 пряма W лежить поза ОПР, тобто жодна з її точок не є рішенням.

Мал. 2.1.

Можливі й інші ситуації.

Якби пряма W збіглася з прямою AD, мі малі б нескінчену множину рішень відповідних крапкам, що лежати на відрізку AD (включаючи крапку А). З іншого боку, деякі задачі можуть і не мати рішення через несумісність обмежень (2.3) – для них відсутня ОПР.

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

Зауважимо, що змінні х₁ і х₂ реально можуть мати тільки цілочислові рішення. У дійсності припустимі рішення відповідають дискретній множині крапок в ОПР. У подібних випадках точні рішення дають спеціальні методи ЛП.