Науковий керівник: Клочко О.В.
Вінницький національний
аграрний університет
Федорова Т. О.
ЛІНІЙНЕ ПРОГРАМУВАННЯ
Вступ. Лінійне програмування —
один з важливих розділів дослідження операцій, що зводиться до оптимізації
лінійної цільової функції на множині, яка описується лінійними рівняннями і
нерівностями. Лінійне програмування є окремими випадками математичного
програмування. Одночасно воно — основа декількох методів вирішення задач
цілочисельного і нелінійного програмування. Багато властивостей задач лінійного
програмування можна інтерпретувати також як властивості многогранників і таким
чином геометрично формулювати і доводити їх. Термін «програмування» треба тут
розуміти в значенні «планування». Він був запропонований в середині 1940-х
років Джорджем Данціґом, одним із засновників лінійного програмування, ще до
того, як комп'ютери були використані для вирішення лінійних задач оптимізації
[2, c.208].
Результати. В даний час лінійне програмування є одним з найбільш вживаних апаратів
математичної теорії оптимального прийняття рішень. Для вирішення завдань
лінійного програмування розроблено складне програмне забезпечення, що дає
можливість ефективно і надійно вирішувати практичні завдання великих обсягів.
Володіння апаратом лінійного програмування необхідно кожному фахівцю в галузі
прикладної математики. Спеціальні методи враховують особливості моделі задачі,
її цільової функції і системи обмежень.
Особливістю завдань лінійного програмування є
те, що екстремуму цільова функція досягає на кордоні області допустимих рішень.
Класичні ж методи диференціального обчислення пов'язані з перебуванням
екстремумів функції у внутрішній точці області допустимих значень. Звідси -
необхідність розробки нових методів. [1, c.264]
Лінійне програмування є найбільш часто використовуваний
метод оптимізації. До завдань лінійного програмування можна віднести завдання:
1. раціонального використання сировини та
матеріалів;
2. задачі оптимального розкрою;
3. оптимізації виробничої програми
підприємств;
4. оптимального розміщення і концентрації
виробництва;
5. складання оптимального плану перевезень,
роботи транспорту (транспортні завдання);
6.
управління виробничими запасами;
7. і багато інших, що належать сфері
оптимального планування.
Модель лінійного
програмування має вигляд:
Задача лінійного
програмування пов’язана з оптимізацією процесу, в ході якого невід’ємні шукані
зміні Х1, Х2,…..Хn, які використовуються потім для максимізації (мінімізації)
цільової функції в наступній формі.
Максимізувати (мінімізувати) цільову
функцію
Z = C1,X1 + C1,X1 + Cn, Xn
при умові обмежень на кількість
ресурсів, виражених в такому вигляді
А11 Х1 + А12
Х2 + А1n Xn
< B1
А21 Х1 + А22 Х2 + А2n Xn
< B2 …
Аm1 Х1 + Аm2 Х2 + Аmn Xn
< Bm,
д C n, Аmn,
Bm – постійно задані величини.
В залежності від
типу задачі обмеження можуть вказуватись також з використанням знаку рівності
(=), чи знаку більше (>).
Лінійне
програмування є однією з основних частин того розділу сучасної математики, який
отримав назву математичного програмування. У загальній постановці, завдання
цього розділу виглядають наступним чином.
Завдання лінійного
програмування вирішуються декількома методами:
1. графічний метод;
2. симплексний метод;
3. двоїстість у ЛП;
4.двойственний симплексний метод.
Завдання лінійного програмування з двома
змінними завжди можна вирішити графічно. Проте вже в тривимірному просторі таке
рішення ускладнюється, а в просторах, розмірність яких більше трьох, графічне
рішення неможливо[3, c.452].
Висновок. Отже, зміст математичного
програмування становлять теорія і методи розв'язання задач про знаходження
екстремумів функцій на множинах, що визначаються лінійними і нелінійними
обмеженнями. .
Завдання
математичного програмування знаходять застосування в різних областях людської
діяльності, де необхідний вибір одного з можливих образів дій (програм дій),
наприклад, при вирішенні проблем управління і планування виробничих процесів, у
проектуванні та перспективному плануванні, у військовій справі і т.д.
Значне число завдань, що виникають у суспільстві,
пов'язане з керованими явищами, тобто з явищами, регульованими на основі
свідомо прийнятих рішень. При тому обмеженому обсязі інформації, який був
доступний на ранніх етапах розвитку суспільства, приймалося оптимальне в
деякому сенсі рішення на підставі інтуїції і досвіду, а потім, зі зростанням
обсягу інформації про досліджуваному явищі, - за допомогою ряду прямих
розрахунків. Так відбувалося, наприклад, створення календарних планів роботи
промислових підприємств.
Література:
1. Карманов В.Г. Математичне
програмування: навчальний посібник для студентів вузів. - М.: Фізматліт, 2001.
- 264с.
2. Мазаракі А.А.,
Толбатов Ю.А. Математичне програмування в Excel: Навчальний посібник. – К.:
Четверта хвиля, 2005. – 208с.
3. Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. — К.: КНЕУ, 2003. — 452
с.