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

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

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

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

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

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

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

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

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

Потрібно визначити оптимальне число станцій типів 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), тобто є рішенням задачі. Для цього цільову функцію представимо у вигляді додаткового обмеження: