Базова модель лінійного програмування та її структура

Математична модель ЗЛП в загальному випадку записується так: знайти екст­ремум функції

(6)

за умови, що задовольняють системі лінійних нерівностей або рівностей,

які називаються обмеженнями:

(7)

Приймаємо, що - відомі сталі, а в

кожному з обмежень наявний лише один знак Величини п та т кількісно

між собою не пов'язані: т може бути більше, менше або дорівнювати п. Якщо об­меження відсутні, то /п дорівнює нулю. У багатьох задачах змінні x^ мають задово­льняти вимозі невід'ємності, тобто . Набір числових значень величин (х\, х₂,..., х„) називається планом задачі. Доцільно наголосити, що не в кож­ній ЗЛП має бути план, бо не кожна система обмежень (7) має розв'язок.

Математична модель ЗЛП, записана у вигляді (6) та (7), називається загальною задачею лінійного програмування. Визначальним фактором є те, що цільова функ­ція (6) та аналітичне представлення лівих частин обмежень (7) є лінійними стосовно змінних задачі. Усі практичні задачі, ММ яких приводяться до задач лінійного про­грамування, мають представлення, які є частинними стосовно (6) та (7).

Математичні методи розв'язання ЗЛП розбудовані за умов, що форма їх запи­су певним чином упорядкована. Розглянемо деякі форми запису ЗЛП та правила пе­реходу від однієї форми до іншої.

Задачею лінійного програмування в симетричній формі запису називають за­дачу, математична модель якої формулюється так: знайти максимум функції

Симетричну форму запису ЗЛП іноді називають стандартною. Для розбудови методів розв'язання ЗЛП широко використовують запис у ка­нонічній формі (приведеній): знайти максимум функції

Канонічну форму запису ЗЛП іноді називають основною.

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

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