Форми запису задачі лінійного програмування

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

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

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

(2.1)

(2.2)

(2.3)

(2.4)

(2.5)

(2.6)

(2.7)

Групу обмежень (2.2.-2.4) називають основними обмеженнями, а групу (2.5-2.7) – обмеженнями на знак змінних. Отже, загальна форма задачі є формою зі змішаною системою основних умов і змішаною системою обмежень на знаки невідомих.

Слід зауважити, що обмеження загальної задачі, тобто задачі у вигляді рівнянь (2.2) називають жорсткими обмеженнями, а задачі у вигляді нерівностей (2.3.-2.4) – нежорсткими обмеженнями.

Загальна форма запису задач ЛП (2.1-2.7) непридатна для побудови простих і ефективних методів її розв’язку, оскільки вона містить неоднорідну систему основних умов (2.2-2.4), а тому задачу зводять до стандартної форми (перша канонічна):

(2.8)

за умов:

(2.9)

----------------------------------------

(2.10)

Необхідно знайти значення змінних , які задовольнять умови (2.9) і (2.10), тоді як цільова функція (2.8) має набути екстремального значення. При розв’язку задачі методами математичного програмування, як правило, вимагається стандартна форма запису, при якій система обмежень (2.9) складається тільки з рівнянь, а всі b_i (b_1, b₂,,…, b_m) – невід’ємні.

Задачу лінійного програмування (ЗЛП) зручно записувати за допомогою знака ∑.

У такому випадку:

Для дослідження багатьох важливих властивостей задачі ЛП буває зручно представити всі її основні обмеження у формі нерівності одного визначеного типу зі змінними, що задовольняють природні умови (умови невід’ємності).

Назвемо таку форму запису задачі ЛП другою канонічною, яка згідно з написаним, має вигляд (І задача):

(2.11)

(2.12)

----------------------------------------

(2.13)

Потрібно відмітити, що у задачі на максимум обов’язково обмеження типу “≤”, у задачі на мінімум – типу “≥”.

Якщо записати до цієї задачі симетричну (ІІ задача), то вона набуде вигляду:

(2.14)

(2.15)

----------------------------------------

(2.16)

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

Векторно-матричний запис задачі лінійного програмування має вигляд:

,

де – це матриця коефіцієнтів при невідомих;

- вектор невідомих; - вектор вільних елементів;

- вектор коефіцієнтів при невідомих у цільовій функції.

Векторна форма:

за умов

,

де , – вектори коефіцієнтів при

невідомих.