Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Розробка моделей лінійного програмування.
|
|
Термін «розробка» означає побудову моделей лінійного програмування для практичних задач. Розробка моделі містить у собі три етапи:
1. Визначення перемінні задачі.
2. Представлення обмежень на значення перемінних у виді лінійних чи рівнянь нерівностей.
3. Завдання лінійної цільової функції, що підлягає чи мінімізації максимізації.
Приклад. Оптимізація побудови мережі телевізійного віщання.
Для побудови мережі телевізійного віщання на території площею 30 000 тис. кв. км пропонується використовувати телевізійні станції 2-х типів із загальною споживаною потужністю не більш 125 квт. Загальна чисельність штату на всіх станціях не винна перевищувати 24 шт. од.
Параметри станцій наведені в таблиці.
| Тип станції | ||
| Площа, що обслуговується, кв. км. | 10 000 | |
| Чисельність штату, шт. од. | 0, 15 | |
| Споживана потужність, квт | 0, 63 | |
| Приведені витрати, тис. грн. |
Задана площа обслуговування враховує деяке взаємне перекриття зон обслуговування.
Потрібно визначити оптимальне число станцій типів 1 і 2 при, якому приведені витрати на всю мережу будуть найменшими.
Рішення.
Шукане число станцій 1 і 2 приймаємо за керовані змінні х1 і х2 відповідно
Х = (х1, х2). Сумарні витрати на мережу W(X) = 15x1 + 200x2.
Оптимізаційна математична модель: знайти невід’ємнні значення зінних х1 і х2, при яких цільова функція
W(х1, х2) = 15x1 + 200x2 è min (2.2)
і задовольняють обмеженням:
500 х1 + 10000х2 ≥ 30000
0, 15 х1 + 8х2 ≤ 24
0, 63 х1 + 55х2 ≤ 125
Задача вирішується методом лінійного програмування (ЛП). Приводимо її до ОЗЛП у такий спосіб:
в усіх нерівностях перенесемо в ліві частини постійні величини і дві останніх нерівності помножимо на –1, помінявши знаки нерівностей:
500 х1 + 10000х2 - 30000 ≥ 0
- 0, 15 х1 - 8х2 + 24 ≥ 0
- 0, 63 х1 - 55х2 + 125 ≥ 0
введемо нові невід’ємнні змінні х3, х4, х5:
х3 = 500 х1 + 10000х2 - 30000 ≥ 0
х4 = - 0, 15 х1 - 8х2 + 24 ≥ 0
х5 = - 0, 63 х1 - 55х2 + 125 ≥ 0 (2.3)
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Одержали обмеження у вигляді рівностей і звели задачу до пошуку мінімуму цільової функції.
Розглянута задача являє собою класичну задачу лінійного програмування, де загальне число змінних n=5, кількість базисних змінних m=3, кількість вільних змінних k=n-m=2. Оскільки k=2, то рішення задачі можна знайти графічно.
Умови невід’ємності змінних обмежують область їхніх припустимих значень першим квадрантом (тобто частиною площини, розташованої над віссю х1 і зправа від осі х2). Інші границі простору не відбиті на площині Х1, Х2. Прямі лінії будуються по рівняннях системи (2.3).
Надамо базисним змінним найменшого можливого значення х3=х4=х5=0 і побудуємо відповідні прямі.
Для рівняння х3=0 відрізки відтинаються прямої на осях координат складуть відповідно:
при х2=0 х1=30000/500=60
при х1=0 х2=30000/10000=3
З одному боку від необмеженої прямої (вправо нагору) значення змінної х3 будуть позитивними, з іншого - негативними.
Нанесемо на малюнок відрізки, що відповідають припустимим (позитивним) значенням змінних. Ту ж процедуру проробимо для рівнянь х4 = 0 і х5 = 0.
Для х4 = 0 при х2 = 0 х1 = 160; при х1 = 0 х2 = 3.
Для х5 = 0 при х2 = 0 х1 = 198, 41; при х1 = 0 х2 = 2, 27.
Частина площини, що задовольняє всім обмеженням, називається областю припустимих рішень (ОПР). Шукана область припустимих рішень показана на малюнку. На малюнку ця область заштрихована; її вершини позначені буквами ABCD (Мал.2.1).
Після завершення 1-го етапу рішення (побудови ОПР) необхідно знайти таку крапку цієї області, що забезпечить виконання умови (2.2), тобто є рішенням задачі. Для цього цільову функцію представимо у вигляді додаткового обмеження:
|
|