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

1. Загальна економіко-математична модель задачі лінійного програмування

Загальна лінійна економіко-математична модель економічних процесів та явищ — так звана загальна задача лінійного програмування подається у вигляді:

(2.1)

за умов:

(2.2)

(2.3)

Отже, потрібно знайти значення змінних x₁,x₂, …,x_n, які задовольняють умови (2.2) і (2.3), і цільова функція (2.1) набуває екстремального (максимального чи мінімального) значення.

Для довільної задачі математичного програмування у § 1.2 були введені поняття допустимого та оптимального планів.

Для загальної задачі лінійного програмування використовуються такі поняття.

Вектор Х= (х₁,х₂, …,х_n), координати якого задовольняють систему обмежень (2.2) та умови невід’ємності змінних (2.3), називаєтьсядопустимим розв’язком (планом) задачі лінійного програмування.

Допустимий план Х= (х₁,х₂, …,х_n) називаєтьсяопорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніжmлінійно незалежних обмежень системи (2.2) у вигляді рівностей, а також обмеження (2.3) щодо невід’ємності змінних.

Опорний план Х= (х₁,х₂, …,х_n), називаєтьсяневиродженим, якщо він містить точноmдодатних змінних, інакше вінвироджений.

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

Задачу (2.1)—(2.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2.2) всі b_i(i= 1, 2, …,m) невід’ємні, а всі обмеження є рівностями.

Якщо якесь b_iвід’ємне, то, помножившиi-те обмеження на (– 1), дістанемо у правій частині відповідної рівності додатне значення. Колиi-те обмеження має вигляд нерівностіа_i1х₁+а_i2х₂+ … +а_inx_n≤b_i, то останню завжди можна звести до рівності, увівшидодатковузміннуx_{n + 1}:a_i1x₁+a_i2x₂+ … + + a_in x_n + x_{n + 1}=b_i.

Аналогічно обмеження виду а_k1x₁+a_k2x₂+ … +a_knx_n≥b_kзводять до рівності, віднімаючи від лівої частинидодатковузміннух_n + 2, тобто:a_k1x₁+a_k2x₂+ … +a_knx_n–x_{n + 2}=b_k(х_n+1≥ 0,х_n+2≥ 0).

Доведемо, що заміна нерівностей рівняннями за допомогою введення додаткових змінних не змінить розв’язку початкової задачі. Розглянемо лінійну нерівність з nневідомими:

(2.4)

Для зведення нерівності (2.4) до рівняння необхідно до її лівої частини додати деяку невід’ємну величину х_{n + 1}≥ 0. У результаті дістаємо лінійне рівняння, яке міститьn+1змінну:

a₁x₁+a₂x₂+ … +a_nx_n+x_{n + 1}=b. (2.5)

Теорема 2.1. Кожному розв’язку нерівності (2.4) відповідає єдиний розв’язок рівняння (2.5), який одночасно є розв’язком нерівності (2.4), і, навпаки, кожному розв’язку рівняння (2.5) і нерівності (2.4) відповідає єдиний розв’язок нерівності (2.4).

Доведення: НехайX^*— розв’язок нерівності (2.4), тоді підстановкою нерівність виконується:

.

Перенесемо ліву частину даної нерівності в праву і позначимо вираз у правій частині через , тобто:

Отже, розв’язок задовольняє рівняння (2.5) і водночас нерівність (2.4). Дійсно, і при підстановців рівняння маємо:

Навпаки, нехай Y^*задовольняє рівняння (2.5) і нерівність (2.4), тобто:

і .

Тоді, відкидаючи в лівій частині рівності невід’ємну величину , отримаємо нерівність:

.

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

Задачу лінійного програмування зручно записувати за допомогою знака суми «». Справді, задачу (2.1)—(2.3) можна подати так:

за умов:

(2.6)

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

max(min) Z = CX

за умов:

АХ=А₀; (2.7)

Х ≥ 0,

де

є матрицею коефіцієнтів при змінних;

— вектор змінних; — вектор вільних членів;

С= (с₁, с₂, …, с_п) — вектор коефіцієнтів при змінних у цільовій функції.

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

max(min)Z = CX

за умов:

A₁x₁ + A₂x₂ + … + A_nx_n = A₀; (2.8)

X ≥0,

де

є векторами коефіцієнтів при змінних.

3. Геометрична інтерпретація задачі лінійного програмування

Розглянемо на площині х₁Оx₂сумісну систему лінійних нерівностей:

(2.9)

К

Рис. 2.1

ожна нерівність цієї системи геометрично визначає півплощину з граничною прямоюa_i1x₁+a_i2x₂=b_i (i = 1, 2, ...,т).Умови невід’ємності змінних визначають півплощини з граничними прямимих₁= 0 тах₂= 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв’язком даної системи (рис. 2.1).

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

Якщо в системі обмежень (2.9) буде три змінних, то кожна нерівність геометрично визначатиме півпростір тривимірного простору, граничними площинами котрого будуть a_i1x₁+a_i2x₂+a_i3x₃=b_i(i = 1, 2, ...,т),а умови невід’ємності — півпростори з граничними площинамих_j = 0 (j = 1, 2, 3), деі— номер обмеження, аj— номер змінної. Якщо система обмежень сумісна, то ці півпростори як опуклі множини, перетинаючись, утворять у тривимірному просторі спільну частину, що називаєтьсябагатогранником розв’язків.Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Нехай у системі обмежень (2.9) кількість змінних більша, ніж три: х₁,х₂,…х_n; тоді кожна нерівність визначає півпростірn-вимірного простору з граничною гіперплощиноюа_i1x₁+a_i2x₂+a_i3x₃+ … +a_inx_n=b_i(i = 1, 2, ...,т). Кожному обмеженню виду (2.9) відповідають гіперплощина та напівпростір, який лежить зодного боку цієї гіперплощини, а умови невід’ємності —півпростори з граничними гіперплощинамих_j = 0 (j = 1, 2, 3, ...,n).

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

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

Цільову функцію

в п-вимірному просторі основних змінних можна геометрично інтерпретувати як сім’ю паралельних гіперплощин, положеннякожної з яких визначається значенням параметраZ.

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

Таблиця 2.3