Науковий керівник: Клочко О.В.

Вінницький національний аграрний університет

Федорова Т. О.

 

ЛІНІЙНЕ ПРОГРАМУВАННЯ

 

Вступ. Лінійне програмування — один з важливих розділів дослідження операцій, що зводиться до оптимізації лінійної цільової функції на множині, яка описується лінійними рівняннями і нерівностями. Лінійне програмування є окремими випадками математичного програмування. Одночасно воно — основа декількох методів вирішення задач цілочисельного і нелінійного програмування. Багато властивостей задач лінійного програмування можна інтерпретувати також як властивості многогранників і таким чином геометрично формулювати і доводити їх. Термін «програмування» треба тут розуміти в значенні «планування». Він був запропонований в середині 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 с.