уявлення реального світу: економічних завдань, завдань управління і планування, оптимального розміщення устаткування і ін.
Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівностей і нерівностей. Коротко задачу лінійного програмування можна сформулювати наступним чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійних рівностей або нерівностей.
Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
· раціонального використання сировини і матеріалів; задачі оптимізації розкрою;
· оптимізації виробничої програми підприємств;
· оптимального розміщення і концентрації виробництва;
· складання оптимального плану перевезень, роботи транспорту;
· управління виробничими запасами;
· і багато інших, що належать сфері оптимального планування.
Так, за оцінками американських експертів, близько 75% від загального числа застосовуваних оптимізаційних методів припадає на лінійне програмування. Близько чверті машинного часу, витраченого в останні роки на проведення наукових досліджень, було відведено вирішенню завдань лінійного програмування та їх численних модифікацій.
Перші постановки завдань лінійного програмування були сформульовані відомим радянським математиком Л.В. Канторовичем, якому за ці роботи була присуджена Нобелівська премія з економіки.
В даний час лінійне програмування є одним з найбільш уживаних апаратів математичної теорії оптимального ухвалення рішення.
Отже, лінійне програмування - це наука про методи дослідження та відшукання найбільших і найменших значень лінійної функції, на невідомі якої накладено лінійні обмеження. Таким чином, завдання лінійного програмування відносяться до завдань на умовний екстремум функції.
. Основна задача лінійного програмування
Основна задача лінійного програмування (ОЗЛП) ставиться таким чином: Є ряд змінних. Потрібно знайти такі їх невід'ємні значення, які задовольняли б системі лінійних рівнянь:
{1.1}
і, крім того, звертали б в мінімум лінійну цільову функцію (ЦФ)
Очевидно, випадок, коли ЦФ потрібно звернути не в мінімум, а в максимум, легко зводиться до попереднього, якщо змінити знак функції і розглянути замість неї функцію
Допустимим рішенням ОЗЛП називають будь-яку сукупність змінних, що задовольняє рівнянням (1.1).
Оптимальним рішенням називають те з допустимих рішень, при якому ЦФ звертається в мінімум.
На практиці обмеження в задачі лінійного програмування часто задані не рівняннями, а нерівностями. У цьому випадку можна перейти до основної задачі лінійного програмування.
Розглянемо задачу лінійного програмування з обмеженнями-нерівностями, які мають вигляд
{1.2}
і є лінійно-незалежними. Останнє означає, ніяке з них не можна представити у вигляді лінійної комбінації інших. Потрібно знайти, які задовольняють нерівностям і звертають в мінімум
Введемо рівняння:
{1.3}
де - додаткові змінні, які також як і є невід'ємними.
Таким чином, маємо спільну задачу лінійного програмування - знайти невід'ємні, щоб вони задовольняли системі рівнянь (1.3) і звертали в мінімум.
Коефіцієнти у формулі (1.3) перед дорівнюють нулю.
. Графічний метод розв'язання задачі лінійного програмування
Графічний метод досить простий і наочний для вирішення завдань лінійного програмування з двома змінними. Він заснований на геометричному поданні допустимих рішень і ЦФ завдання.
Кожне з нерівностей задачі лінійного програмування (1.2) визначає на координатній площині деяку полуплоскость, а система нерівностей в цілому - перетин відповідних площин. Безліч точок перетину даних напівплощин називається областю допустимих рішень (ОДР). ОДР завжди являє собою опуклу фігуру, тобто Володіє наступними властивостями: якщо дві точки А і В належать цій фігурі, то і весь відрізок АВ належить їй. ОДР графічно може бути представлена ??опуклим багатокутником, необмеженої опуклою багатокутної областю, відрізком, променем, однією точкою. У разі несумісності системи обмежень задачі (1.2) ОДР є порожнім безліччю.
Все вищесказане відноситься і до випадку, коли система обмежень (1.2) включає рівності, оскільки будь-яке рівність
можна представити у виг...
