змагання тощо.
При цьому виникає проблема раціонального розподілу наявних ресурсів між варіантами можливих стратегій. Вирішення такої проблеми може бути знайдено на основі моделей і методів теорії оптимізації. Математична постановка задачі оптимізації включає одну або декілька цільових функцій (на максимум або на мінімум) і кілька обмежень (виду рівностей і виду нерівностей). У випадку, коли цільова функція тільки одна (скалярна оптимізація) і коли цільова функція і функції, що входять в систему обмежень лінійні, завдання оптимізації відноситься до типу задач лінійного програмування. Основним методом вирішення завдань лінійного програмування є симплексний метод і його модифікації. Однак у випадку розподілу ресурсів між двома варіантами використання може бути використаний графічний метод. У загальному випадку для вирішення завдань лінійного програмування можна використовувати пакети прикладних програм для ЕОМ. Зокрема входять до складу пакету офісних додатків Microsoft Office електронні таблиці Excel містять надбудову Пошук рішення, що дозволяє вирішувати задачі лінійного програмування.
В якості конкретного прикладу розглянемо наступну задачу.
Є 2 різних видів робіт,, які можуть виконуватися протягом робочого часу Т. Погодинна оплата кожного виду робіт становить, на годину. Загальний фонд оплати праці обмежений величиною U.
Матеріальні витрати, пов'язані з виконанням кожного виду робіт, складають на годину. Загальний фонд матеріальних витрат обмежений величиною V. прибуток, одержуваний при виконанні роботи кожного виду протягом однієї години, становить. Потрібно знайти такий розподіл робочого часу Т між роботами, щоб сумарний прибуток була максимальною. Числові дані завдання наведені в таблиці 7.
Таблиця 7. Числові дані завдання розподілу робочого часу
u (у. е./год.) v (у. е./год.) c (у. е./год.) 202550 504070T100 час.U2000 у. е.V1500 у. е.
Побудуємо математичну постановку задачі. Позначимо, - час, плановане для виконання роботи А1 і А2. Тоді математична модель буде мати вигляд:
F ()=+ (max)
+? U
+? V
+? T
,? 0
Або з конкретними числовими даними завдання:
F ()=50 +70 (max)
20 +50? 2000
25 +40? 1500
+? 100
? 0
Для повчання графічного рішення побудуємо прямі, відповідні обмеженням. Ці прямі будуть проходити через точки:
U: (0,40), (100,0)
V: (0,37.5), (60,0)
T: (0,100), (100,0).
Область планів лежатиме в першій чверті цих прямих.
Лінія нульового рівня цільової функції проходить через початок координат (точку (0,0)) і крапку (- 70,50). Паралельний перенос цієї лінії вправо-вгору дозволяє знайти оптимальний план: (60, 0). Таким чином, найкращим розподілом часу буде:=60,=0
Рішення розглянутої задачі може бути отримано також за допомогою електронних таблиць Excel.
Графічне рішення задачі лінійного програмування
Екранна форма електронної таблиці Excel з рішенням задачі лінійного програмування
Збіг рішень задачі лінійного програмування отриманих двома різними методами свідчить про правильність рішення.
Задача про призначення
При виконанні різних робіт у готельному комплексі «солов'їна Роща» виникають завдання, пов'язані з призначенням тих чи інших працівників на деякі роботи. При цьому потрібно скласти схему призначень для якої загальна ефективність виконання всього комплексу робіт була б максимальною. Завдання такого типу відносяться до класу цілочисельних транспортних задач лінійного програмування. Для вирішення використовуються такі методи, як розподільний метод, метод потенціалів, метод диференціальних рент та ін. Самостійне значення мають методи знаходження опорних планів транспортних завдань, такі як, метод північно-західного кута, метод мінімального елемента, метод подвійного переваги та ін. Вони дозволяють побудувати деяку (можливо не оптимальну) схему призначень, яка в подальшому може бути улучш?? на одним з перерахованих методів знаходження оптимальних планів.
В якості прикладу розглянемо наступну задачу про незначних:
Для виконання робіт В1, 2, ..., В n потрібно відповідно b 1, b 2, ..., bn працівників. Наявні працівники за своєю кваліфікацією можуть бути розбиті на групи А 1, А 2, ..., А m, п...
