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

Загальна економіко-математична моде&# 727f54h 1083;ь задачі лінійного програмування

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

(2.1)

(2.2)

(2.3)

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

_n

Допустимий план Х = (х₁, х₂, …, х_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-те обмеження має вигляд нерівності а_{i i in}x_n b_i x_n a_i x a_i x  a_in x_n x_n b_i

_k x a_k x a_knx_n b_k зводять до рівності, віднімаючи від лівої частини додаткову змінну х_n + 2, тобто: a_k x a_k x a_knx_n x_n b_{k n n}

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

(2.4)

_n ≥ 0. У результаті дістаємо лінійне рівняння, яке містить n+1 змінну:

a x a x a_nx_n x_n b (2.5)

X нерівність виконується:

.

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

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

Y

і .

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

.