 |
Основні типи прикладних задач лінійного програмування
|
|
|
|
Розглянемо моделі прикладних задач лінійного програмування, які найчастіше зустрічаються в різних галузях народного господарства.
Задача на суміш
У практиці планування є ряд задач на знаходження оптимального складу матеріалу (речовини) з існуючих запасів складових компонентів згідно з критерієм задачі. При цьому вартість кінцевого продукту має бути мінімальною чи максимальною величиною згідно зі змістом задачі.
Складемо математичну модель задачі на суміш на прикладі приготування оптимального раціону харчування.
Необхідно визначити склад раціону харчування з n кінцевих продуктів, які можна дістати з т компонент. Кінцеві продукти позначимо індексом 
, а компоненти – індексом 
. Задані вартості одиниці кожного 
-го продукту позначимо через 
, а кожна і -та компонента має запас ресурсів 
.
Крім того, відома кількість і -ї компоненти, яка витрачається на приготування одиниці -го продукту, тобто задана норма витрати.
Мета задачі – скласти оптимальний раціон харчування з мінімальною його вартістю.
Умови задачі доцільно навести у вигляді таблиці:
| і | J | ||||
| … | n | 
| |||
| 
| … | 
| 
| |
| 
| … | 
| 
| |
| … | … | … | … | … | … |
| m | 
| 
| … | 
| 
|
| 
| 
| … | 
|
Побудуємо математичну модель задачі.
Якщо кількість кожного кінцевого -го продукту раціону харчування позначити 
, то математична модель задачі матиме такий вигляд:
– цільова функція
– обмеження
– умовиневід’ємності
Зауважимо, що іноді в задачі на суміш задають діапазони витрат тієї чи іншої початкової компоненти. Такі умови в математичній моделі можна передбачити двома типами обмежень:
та 
де 
, 
– відповідно нижня та верхня межа витрат і -ї компоненти.
|
|
|
Приклад. Для приготування раціону харчування, який складається з трьох продуктів, треба витратити не менше6 одиниць компоненти А, не менше8 одиниць компоненти В та не більше 12 одиниць компоненти С. Для приготування одиниці кожного продукту потрібні такі кількості компонент А, В та С:
| Компонента | Кількість продукту | ||
| А | |||
| В | 1,5 | ||
| С |
Відома також вартість одиниці кожного продукту: першого – 2 грн. другого – 3 грн., третього – 2,5 грн.
Треба скласти математичну модель задачі, яка відповідає варіанту з мінімальною вартістю раціону харчування.
Кількість кінцевих продуктів, які є складовими частинами раціону харчування, зобразимо відповідно через 
та 
. Тоді маємо наступну математичну модель:
– цільова функція 
– обмеження
– умови невід’ємності
Транспортна задача
Транспортні задачі часто зустрічаються на практиці і характерні для класу розподільних задач, наприклад, оптимальне розміщення вантажу, складання оптимальних маршрутів, доставка продуктів, які швидко псуються, та ін. Іноді транспортну задачу називають Т -задачею.
Змістова постановка транспортної задачі така.
Є 
пунктів постачання та 
пунктів споживання декотрого однорідного продукту. Відомі обсяги можливого постачання 
продукту від кожного пункту постачання та обсяги попиту 
кожного пункту споживання, а також витрати 
, які пов’язані з перевезенням одиниці продукту від і -го пункту постачання до j- го пункту споживання.
Необхідно знайти такий план перевезення продукту, щоб загальна вартість перевезення цього продукту була мінімальною.
Позначимо через змінні 
кількість вантажу, яку належить перевезти з і -го пункту постачання до j -го пункту споживання. Тоді загальна кількість вантажу, що йде з і -го пункту постачання до всіх пунктів споживання має вигляд
|
|
|
а кількість вантажу, що приймається j- м пунктом споживання відусіхпунктів постачання
Мета задачі має вигляд
за умови 
.
Приклад. Існує три пункти постачання з відповідними запасами ресурсів (вантажу)
та два споживача ресурсів з відповідним попитом
Вартість перевезень одиниці вантажу задано у вигляді матриці
.
Скласти математичну модель задачі, яка передбачає мінімальні транспортні витрати перевезень ресурсів.
Математична модель має такий вигляд:
– цільова функція
– обмеження за пунктами постачання
– обмеження за пунктами споживання
Розглянуті математичні моделі типових задач лінійного програмування не вичерпують усіх задач, що зустрічаються на практиці. Але за допомогою певних перетворень всі вони зводяться до загальної задачі математичного програмування.
Графічний метод
Графічний метод розв’язування задач лінійного програмування ґрунтується на геометричному зображенні математичної моделі задачі в системі координат. Але його використання обмежено зростанням кількості змінних у задачі, оскільки таку п -вимірну задачу графічно зобразити в просторі неможливо. Як на мене, краще не писати „зобразити задачу”. Тому в основному цей метод використовується для задач, які мають дві-три змінні, або якщо різниця між кількістю змінних та кількістю обмежень задовольняє умові (т – п) < 2. У цьому випадку математичну модель задачі потрібно перетворити так, щоб вона мала вигляд двовимірної.
Основна перевага графічного методу полягає в простому зображенні та наочності ходу розв’язування.
Графічний метод реалізується в два етапиа:
– побудова ОДР;
– знаходження оптимального розв’язку.
Зауважимо, що в процесі побудови ОДР можливі такі випадки:
– порожня область (рис.1.8, а); при цьому обмеження в математичній моделі несумісні і згідно з цим задача не має розв’язку;
– опуклий многогранник (рис.1.8, б); при цьому обмеження сумісні та зображують область, до якої входять допустимі розв’язки;
– необмежена область з одного боку (рис. 1.8, в-г); при цьому існує мінімум або максимум, або взагалі не існує розв’язку.
Наведемо алгоритм розв’язування задачі лінійного програмування графічним методом.
|
|
|
1. Згідно з обмеженнями математичної моделі задачі будують ОДР. Для цього всі нерівності обмежень подають рівняннями безпосередньою заміною знаків „ 
” та „ 
” знаком „=”. Кожне знайдене рівняння зображують на площині прямою, яку будують за двома довільними точками. Кожна така пряма поділяє площину на дві півплощини – допустиму та недопустиму, а сама пряма є межею цих півплощин.
Щоб знайти допустиму півплощину, треба взяти дві довільні точки в кожній півплощині та їх координати підставити до заданого обмеження: точка, яка порушує знак обмеження, є точкою недопустимої півплощини, а точка, яка не порушує знака, знаходиться в допустимій півплощині (для такого аналізу доцільно використовувати нульову точку, тобто початок координат, якщо пряма не проходить через початок координат).
Після побудови всіх допустимих півплощин знаходять ОДР як перетин цих півплощин з урахуванням умови 
.
а) б)
в) г)
Рис.1.8
2. Будують пряму цільової функцію 
у такій послідовності:
– за двома точками (точкою початку координат та точкою, координати якої є коефіцієнти при відповідних змінних з цільової функції) будують градієнт функції, який показує напрямок максимальної зміни значення цільової функції ;
– перпендикулярно до градієнта будують пряму цільової функції, наприклад, через початок координат, де = 0).
3. Знаходять місце розміщення оптимальних точок у допустимому просторі. Для цього пряму цільової функції зсовують паралельно собі у напрямку градієнта: найближча точка дотику ОДР відповідає точці мінімуму, а найвіддалена – точці максимуму.
4. Знаходять координати точок дотику ОДР. Для цього розв’язують систему рівнянь прямих, які утворюють ці точки. Наслідок розв’язування таких систем рівнянь дає оптимальні значення змінних, які потім підставляють у вираз цільової функції та знаходять значення 
чи 
.
Іноді лінії рівня цільової функції розташовується паралельно одній з границь ОДР. У цьому разі задача має множину оптимальних розв’язків з постійним значенням . Такі задачі називають задачами з альтернативним оптимумом.
|
|
|
Послідовність розв’язування задачі графічним методом зображено на рис.1.9.
Приклад. Знайти оптимальний розв’язок для такої математичної моделі:
– цільова функція
;
– обмеження
|
|
 |
|
|
 | |
 |  | ||||
 |
|
Рис.1.9
за умов 
Згідно з обмеженнями задачі будуємо ОДР (рис. 1.10).
Спочатку будуємо градієнт цільової функції F через нульову точку та точку А з координатами 
; потім – пряму цільової функції F перпендикулярно до побудованого вектора. Пряму F зсовуємо в напрямку вектора до найближчої точки дотику ОДР – точки В, яка утворюється прямими 
та 
.Розв’язуючи систему цих рівнянь, знаходимо 
та 
, а значення цільової функції 
=4.
qrad F
А 
В 
F =0 
Рис.1.10
Симплексний метод
|
|
|
E) тело, размерами которого можно пренебречь в условиях данной задачи
I Приклади розв’язання задач
I ЭТАП. Постановка задачи
I. ОСНОВНІ ЗАДАЧІ І НАПРЯМКИ САМОСТІЙНОЇ НДР СТУДЕНТІВ
I. Цели и задачи учебной дисциплины
I. Цель задачи дисциплины «История государства и права зарубежных стран»
II Анализ задачного материала
II Раздаточный материал из сборника задач по технологии горячей и холодной прокатки стали и сплавов. Протасов А.А. Изд-во «Металлургия» М.1972, 320 с.
II. Задачи работы с классом
II. Мета та основні завдання Програми
