Розділ 2.Загальна задача лінійного програмування та методи її розв’язку

Математичне програмування – це розділ математики, який розробляє теорію і чисельні методи розв’язку оптимізаційних задач, в яких цільова функція прямує на extr (min/max), а система обмежень наведена у вигляді лінійних або нелінійних рівнянь чи нерівностей.

Усі математичні методи поділяються на аналітичні, графічні, кількісні (чисельні).

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

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

1. Цільова функція (функція мети)

Система обмежень і умов:

2. 

3. 

4. 

1.5. Умови невід’ємності змінних (природні умови)

Прийняті позначення:

n – загальна кількість змінних величин;

j – порядковий номер змінної;

і – порядковий номер обмеження;

m – загальна кількість обмежень;

m₁ – кількість обмежень з використання ресурсів (m₁ є m);

m₂ - кількість обмежень по гарантованих обсягах виробництва (m₂ є m);

a_ij – затрати і-ого ресурсу на одиницю j-ої продукції;

v_ij – обсяг виробництва і-го виду в розрахунку на одиницю j-го виду виробництва;

b_i – обсяг і-го виду виробничих ресурсів;

R_i – гарантований обсяг виробництва і-го виду продукції;

B_i – фіксований обсяг виробництва і-го виду продукції;

C_j – оцінка змінної у цільовій функції, тобто ціна або собівартість одиниці продукції;

X_j –(основна змінна) розмір j-го виду діяльності.

Такий запис економічної задачі називають структурною економіко-математичною моделлю.

Задача лінійного програмування – це задача, в якій цільова функція (1.1) та обмеження (1.2-1.4) є лінійними функціями, тобто вони містять змінні X_j у першому або нульовому степені. В усіх інших випадках задача буде нелінійною. Важливою перевагою лінійного програмування є те, що для їх розв’язку розроблений універсальний метод, який називається симплексним методом. Для деяких задач лінійного програмування, що мають особливу структуру, розробляють спеціальні методи розв’язування, які є ефективнішими в цьому випадку. Наприклад, транспортну задачу можна розв’язати симплексним методом, але ефективнішими є інші методи, наприклад, метод потенціалів.

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

Основна ідея математичного програмування – це ідея оптимізації, тобто знаходження оптимального плану розвитку досліджуваної системи:

;

де – вектор Х, координати якого задовольняють систему обмежень (1.2-1.4), називають допустимим розв‘язком або допустимим планом задачі. Сукупність допустимих розв’язків (планів) задачі утворює область допустимих розв‘язків задачі.

Опорним планом задачі лінійного програмування називається план, утворений координатами вершин многогранника планів задачі. Опорний план – це план, який задовольняє не менш, ніж n лінійно незалежних обмежень (1.2-1.4) у вигляді строгих рівностей разом з обмеженнями щодо знаку (1.5).

Опорний план, за якого цільова функція досягає свого максимального (мінімального) значення, називається оптимальним розв’язком (планом) задачі лінійного програмування.

Опорний план називається невиродженим, якщо він є вершиною многогранника планів задачі, утвореною перетином n лінійно залежних обмежень – строгих рівностей. У іншому випадку опорний план є виродженим.

Теорема: якщо задача лінійного програмування має розв‘язки і серед них є опорні, то хоча б один із них буде оптимальним.

Сукупність усіх розв‘язків задачі лінійного програмування є многогранною опуклою множиною, яку називають многогранником розв‘язків (симплексів).

Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин многогранника розв‘язків. А коли цільова функція набуває екстремального значення більш як в одній вершині цього многогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.