тодів дослідження операцій призвело до того, що аналітики стали стикатися з завданнями, в яких істотним виявляється наявність декількох критеріїв оцінки якості рішення. Такі завдання носять назву багатокритеріальної завданням оптимізації [36,51].
1.1 Лінійне програмування
В даний час оптимізація практично невід'ємна частина в науці, техніці, економіці і в будь-якій області людської діяльності.
Оптимізація - цілеспрямована діяльність, що полягає в отриманні найкращих результатів за відповідних умов [44,46].
Пошуки оптимальних рішень привели до створення спеціальних математичних методів і вже в XVIII столітті були закладені математичні основи оптимізації (варіаційне числення, чисельні методи та ін.) [45,48]. Проте до другої половини XX століття методи оптимізації в багатьох областях науки і техніки застосовувалися дуже рідко, оскільки практичне використання математичних методів оптимізації вимагало величезної обчислювальної роботи, яку без ЕОМ реалізувати було украй важко, а в ряді випадків - неможливо [46].
Залежно від своєї постановки, будь-яка із завдань оптимізації може вирішуватися різними методами, і навпаки - будь-який метод може застосовуватися для вирішення багатьох завдань.
Методи оптимізації можуть бути:
) скалярними (оптимізація проводиться по одному критерію);
) векторними (оптимізація проводиться за багатьма критеріями);
) пошуковими (включають методи регулярного і методи випадкового пошуку), аналітичними (методи диференціального числення, методи варіаційного числення та ін.);
) обчислювальними (засновані на математичному програмуванні, яке може бути лінійним, нелінійним, дискретним, динамічним, стохастичним, евристичним і т.д.);
) теоретико-імовірнісними, теоретико-ігровими та ін. [45,46,48].
Найбільш часто використовуваним методом оптимізації є лінійне програмування. Лінійне програмування (ЛП) - один з перших і найбільш детально вивчених розділів математичного програмування [4,29].
Часом народження лінійного програмування прийнято вважати 1939р., коли була надрукована брошура Леоніда Віталійовича Канторовича «Математичні методи організації і планування виробництва». Оскільки методи, викладені Л.В. Канторовичем, були мало придатні для ручного підрахунку, а швидкодіючих обчислювальних машин у той час не існувало, робота Л.В. Канторовича залишилася майже непоміченою [15,18].
У 50-і рр. ХХ століття незалежно від Канторовича метод розв'язання задачі лінійного програмування (так званий симплекс-метод) був розвинений американським математиком Дж. Данцигом, який в 1951 р і ввів термін «лінійне програмування».
Можна сказати, своє друге народження лінійне програмування отримало з появою електронно-обчислювальних машин (ЕОМ). У той час почалося загальне захоплення лінійним програмуванням, що викликало в свою чергу розвиток інших розділів математичного програмування [29,32].
Слово «програмування» пояснюють тим, що невідомі змінні, які відшукуються в процесі рішення задачі, зазвичай визначають програму (план) дій деякого об'єкта, наприклад, промислового підприємства. Слово «лінійне» відображає лінійну залежність між змінними [12,18].
Лінійне програмування знаходить широке застосування в різних областях практичної діяльності: при організації роботи транспортних систем, в управлінні промисловими підприємствами, при складанні проектів складних систем [4,17]. Багато поширені класи задач системного аналізу, зокрема, задачі оптимального планування, розподілу різних ресурсів, управління запасами, календарного планування, міжгалузевого балансу вкладаються в рамки моделей лінійного програмування. Незважаючи на різні області додатки, дані завдання мають єдину постановку [2,12,18].
Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
) раціонального використання сировини і матеріалів, задачі оптимізації розкрою;
) оптимізації виробничої програми підприємств;
) оптимального розміщення і концентрації виробництва;
) складання оптимального плану перевезень, роботи транспорту;
) управління виробничими запасами і багато інших, що належать сфері оптимального планування [4,12,18,29].
Так, за оцінками американських експертів, близько 75% від загального числа застосовуваних оптимізаційних методів припадає на лінійне програмування. Близько чверті машинного часу, витраченого в останні роки на проведення нау...
