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

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

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

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

Вступ. Лінійне програмування — один з важливих розділів дослідження операцій, що зводиться до оптимізації лінійної цільової функції на множині, яка описується лінійними рівняннями і нерівностями. Лінійне програмування є окремими випадками математичного програмування. Одночасно воно — основа декількох методів вирішення задач цілочисельного і нелінійного програмування. Багато властивостей задач лінійного програмування можна інтерпретувати також як властивості многогранників і таким чином геометрично формулювати і доводити їх. Термін «програмування» треба тут розуміти в значенні «планування». Він був запропонований в середині 1940-х років Джорджем Данціґом, одним із засновників лінійного програмування, ще до того, як комп'ютери були використані для вирішення лінійних задач оптимізації [2, c.208].

Результати. В даний час лінійне програмування є одним з найбільш вживаних апаратів математичної теорії оптимального прийняття рішень. Для вирішення завдань лінійного програмування розроблено складне програмне забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих обсягів. Володіння апаратом лінійного програмування необхідно кожному фахівцю в галузі прикладної математики. Спеціальні методи враховують особливості моделі задачі, її цільової функції і системи обмежень.

Особливістю завдань лінійного програмування є те, що екстремуму цільова функція досягає на кордоні області допустимих рішень. Класичні ж методи диференціального обчислення пов'язані з перебуванням екстремумів функції у внутрішній точці області допустимих значень. Звідси - необхідність розробки нових методів. [1, c.264]

Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:

1. раціонального використання сировини та матеріалів;

2. задачі оптимального розкрою;

3. оптимізації виробничої програми підприємств;

4. оптимального розміщення і концентрації виробництва;

5. складання оптимального плану перевезень, роботи транспорту (транспортні завдання);

6. управління виробничими запасами;

7. і багато інших, що належать сфері оптимального планування.

Модель лінійного програмування має вигляд:

Задача лінійного програмування пов’язана з оптимізацією процесу, в ході якого невід’ємні шукані зміні Х_1, Х_2,…..Х_n, які використовуються потім для максимізації (мінімізації) цільової функції в наступній формі.

Максимізувати (мінімізувати) цільову функцію

Z = C_1,X₁ + C_1,X₁ + C_n, X_n

при умові обмежень на кількість ресурсів, виражених в такому вигляді

А₁₁ Х₁ + А₁₂ Х₂ + А_1n X_n < B₁

А₂₁ Х₁ + А₂₂ Х₂ + А_2n X_n < B₂ …

А_m1 Х₁ + А_m2 Х₂ + А_mn X_n < B_m,

д C _n, А_mn, B_m – постійно задані величини.

В залежності від типу задачі обмеження можуть вказуватись також з використанням знаку рівності (=), чи знаку більше (>).

Лінійне програмування є однією з основних частин того розділу сучасної математики, який отримав назву математичного програмування. У загальній постановці, завдання цього розділу виглядають наступним чином.

Завдання лінійного програмування вирішуються декількома методами:

1. графічний метод;

2. симплексний метод;

3. двоїстість у ЛП;

4.двойственний симплексний метод.

Завдання лінійного програмування з двома змінними завжди можна вирішити графічно. Проте вже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більше трьох, графічне рішення неможливо[3, c.452].

Висновок. Отже, зміст математичного програмування становлять теорія і методи розв'язання задач про знаходження екстремумів функцій на множинах, що визначаються лінійними і нелінійними обмеженнями. .

Завдання математичного програмування знаходять застосування в різних областях людської діяльності, де необхідний вибір одного з можливих образів дій (програм дій), наприклад, при вирішенні проблем управління і планування виробничих процесів, у проектуванні та перспективному плануванні, у військовій справі і т.д.

Значне число завдань, що виникають у суспільстві, пов'язане з керованими явищами, тобто з явищами, регульованими на основі свідомо прийнятих рішень. При тому обмеженому обсязі інформації, який був доступний на ранніх етапах розвитку суспільства, приймалося оптимальне в деякому сенсі рішення на підставі інтуїції і досвіду, а потім, зі зростанням обсягу інформації про досліджуваному явищі, - за допомогою ряду прямих розрахунків. Так відбувалося, наприклад, створення календарних планів роботи промислових підприємств.

Література:

1. Карманов В.Г. Математичне програмування: навчальний посібник для студентів вузів. - М.: Фізматліт, 2001. - 264с.

2. Мазаракі А.А., Толбатов Ю.А. Математичне програмування в Excel: Навчальний посібник. – К.: Четверта хвиля, 2005. – 208с.

3. Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. — К.: КНЕУ, 2003. — 452 с.