Попередні відомості теорії лінійного програмування

Задача математичного програмування вигляду (1.3) або (1.4) називається задачею лінійного програмування (ЛП), якщо цільова функція f є лінійною функцією, а множина допустимих розв’зків Х задається лінійними нерівностя­ми або рівняннями

min(max) f (x)= c₁x₁+c₂x₂+…+c_nx_n (2.1)

a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁;

a₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ b₂; (2.2)

…………………………

a_k1x₁+a_k2x₂+…+a_knx_n ≤ b_k.

x₁ ≥ 0,…, x_n ≥ 0 (2.3)

або у векторному вигляді

(2.4)

де

А = { ,..., }; ,…, ; ; .

Наведена модель є стандартною постановкою задачі ЛП, у якій в системі обмежень (2.2) можуть бути різні відношення типу «<», «>», «=». Тут c₁,…, c_n – коефіцієнти при цільовій функції, a₁₁,..., a_nn – коефіцієнти при змінних в системі обмежень, b₁,…, b_k – вільні члени системи обмежень. Усі ці компоненти задачі ЛП є відомими (заданими) числами. Невідомими (шуканими) змінними будуть елементи вектора { x₁,…, x_n } ^T. При цьому задача ЛП полягає у тому, щоб знайти такі значення змінних x₁*,..., x_n* (точку мінімуму (максимуму)), щоб вони, по-перше, задовольняли обмеження (2.2) і (2.3) (умова допустимості), а, по-друге, щоб у точці х* = (х₁*,..., x_n*) цільова функція f приймала мінімальне (максимальне) значення f (x*) (умова оптимальності). Аналогічно ставиться задача на мінімум.

Крім стандартної форми запису задачі ЛП є також загальна і канонічна форми запису. Загальна форма запису аналогічна стандартній за винятком відсутності обмежень за знаком для шуканих змінних { x₁,…, x_n } ^T.

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

;

;

.

Між формами запису задач ЛП є правила переходу. Розглянемо правила переходу від загальної форми до канонічної. У системі обмежень нерівності типу перетворюються у рівності шляхом додавання до її лівої частини додаткової невід’ємної змін­ної . Так само перетворюються у рівності нерівності типу шляхом віднімання від їх лівих частин додаткової невід’ємної змінної . При цьому слід зауважити, що умову легко звести до , помноживши кожну нерівність на -1, аналогічно тому як обмеження типу можна звести до обмежень типу помноживши їх на -1 та замінивши знак змінних , . Кожну змінну, на знак якої не накладено обмежень, можна описати як різницю двох невід’ємних змінних де , , . При цьому обмеження типу , де , можна перетворити в рівність за правилом: , де .

Приклад 2.1. Звести до канонічної таку загальну задачу ЛП:

Застосовуючи вищенаведені правила зводимо задачу ЛП до вигляду:

що досягається введенням додаткових змінних x₅ ³ 0 та x₆ ³ 0 в друге і третє обмеження-нерівності, заміною x^’₂= - x₂ ³ 0 та описом змін­них x₃ та x₄, що не обмежені за знаком, запишемо у вигляді x₃= x’₃- x»₃, де x’₃, x»₃ ³ 0; x₄= x’₄- x»₄, де x’₄, x»₄ ³ 0.

Приклад 2.2. Перехід від канонічної форми запису задачі ЛП до стандартної. Структура задачі ЛП залежить від рангу r системи обмежень. Якщо r < n, то n-r змінним, які називають небазисними, можна надавати будь-які значення, при цьому r змінні, що називаються базисними, можна визначити через небазисні. Розглянемо канонічну задачу ЛП:

Ранг системи обмежень дорівнює двом. Тому за небазисні змінні виберемо, наприклад, х₁ та х₄. Визначимо через них базисні змінні x₂ та x₃:

.

Оскільки х₁ та х₄ невід’ємні, то: 8+3/2 x₂ - x₃ ³ 0; 2+5/2 x₂ ³ 0. При цьому цільова функція від небазисних змінних набуде такого вигляду:

10 +5 x₂ – 3 x₃ ® max.

Запишемо тепер задачу у стандартній формі:

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

, , ,

де Якщо ж обмеження задані у формі , то

, , .

Розглянемо задачу з обмеженнями або у вигляді системи:

.

Введемо такі позначення:

, ,…, , ,…, , ...

Тоді канонічну задачу ЛП можна записати у вигляді:

,

.

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

Означення 2.1. Набір чисел , що задовольняє обмеження задачі лінійного програмування, називається її планом.

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

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

. (2.5)

Очевидно, що стовпці матриці утворять базис -вимірного простору. Тому вектор і будь-який стовпець матриці можна зобразити у вигляді лінійної комбінації стовпців матриці .

Помножимо обидві частини виразу (2.5) на матрицю , що є матрицею, оберненою щодо матриці В, і як результат отримаємо

, (2.6)

звідки знайдемо вектор розв’язку :

. (2.7)

Для різних значень , будемо отримувати різні розв’язки , і якщо покласти, що , то будемо мати

. (2.8)

Розв’язок (2.8) називають базисним розв’язком системи з рівнянь з невідомими.

Якщо отриманий розв’язок містить тільки додатні компоненти, то такий розв’язок називається допустимим базисним розв’язком.

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

Якщо серед компонентів немає нульових, то допустимий базисний розв’язок називається невиродженим.

Означення 2.3. План задачі лінійного програмування будемо називати опорним, якщо вектори умов з додатними коефіцієнтами лінійно незалежні.

Тобто опорний план – це допустимий базисний розв’язок розширеної системи і є кутовою точкою багатокутника розв’язків.

Означення 2.4. Опорний план називається невиродженим, якщо він містить додатних компонентів (за числом обмежень).

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

Теорема 2.1. (Основна теорема лінійного програмування).

1. Лінійна форма досягає свого мінімуму в кутовій точці багатокутника розв’язків.

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

Доведення. Доведення теореми основано на такій лемі.

Лема. Якщо – замкнена, обмежена і опукла множина, що має скінченне число крайніх (кутових) точок, то будь-яка точка може бути зображена у вигляді опуклої комбінації крайніх точок .

1. Нехай – деяка внутрішня точка (див. на рисунку). Багатокутник обмежений, замкнений і має скінченне число кутових точок, – допустима множина.

Припустимо, що є оптимальною точкою, тобто , . Припустимо, також, що точка не є кутовою. Тоді на підставі леми точку можна визначити через кутові точки багатокутника , тобто , , .

Оскільки функція лінійна, то

.

Виберемо серед точок ту, у якій лінійна форма приймає найменше значення. Нехай це буде точка . Позначимо мінімальне значення функції в кутовій точці через :

.

Підставимо це значення в лінійну форму замість і отримаємо

.

Оскільки, за припущенням, – оптимальна точка, то ми отримали суперечність: . Отже, , – кутова точка.

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

, і ,

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

Теорема 2.2. Якщо відомо, що система векторів умов , лінійно незалежна, причому така, що

,

де всі , то точка є кутовою точкою багатокутника розв’язків.

Теорема 2.3. Якщо вектор є кутовою точкою багатокутника розв’язків, то вектори умов, що відповідають додатним компонентам вектора , є лінійно незалежними. При цьому: кутова точка багатокутника розв’язків має не більше ніж додатних компонентів вектора ; кожній кутовій точці багатокутника розв’язків відповідає лінійно незалежних векторів, що належать системі векторів .

Підсумовуючи вищеописане, можна відзначити такі властивості задач лінійного програмування.

1. Допустима множина розв’язків ЛП або порожня, або є опуклим багатокутником у Rⁿ, що є перерізом півпросторів, які описуються нерівностями (2.2) - (2.3). Вона може бути як обмеженою, так і необмеженою, у будь-якому випадку це замкнений багатокутник.

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

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

4. Якщо дві або кілька вершин є оптимальними розв’язками, то будь-яка їх опукла комбінація також є оптимальним розв’язком, тобто існує нескінченна множина точок максимуму або мінімуму.

Методами розв’язання задач ЛП є графічний метод (у випадку двох змін­­них) або його різновиди (у загальному випадку).