10. Економічна та математична постановка задач лп

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

знайти максимум (мінімум) функції

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

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

Якщо якесь bі від’ємне, то, помноживши і-те обмеження на (–1), дістанемо у правій частині відповідної рівності додатне значення. Коли і-те обмеження має вигляд нерівності … , то останню завжди можна звести до рівності, увівши допоміжну змінну xn + 1:

Аналогічно обмеження виду зводимо до рівності, віднімаючи від лівої частини допоміжну змінну хn + 2, тобто

11. Цільова функція лп. Оптимальний план. Канонічна форма.

Задачi оптимiзацiї, в яких цiльова функцiя є лiнiйною функцiєю незалежних змiнних (тобто має вигляд z=c1x1+c2x2+...+cnxn, де c1, c2,..., cn-константи, x1, x2,..., xn-змiннi, n-довiльне натуральне число), а умови, що визначають допустимi значення цих змiнних, мають вигляд лiнiйних рiвнянь i нерiвностей, вiдносять до задач лiнiйного програмування.

Л iнiйне програмування розвинулось у зв`язку iз задачами економiки, з пошуком способiв оптимального розподiлу i використання обмежених ресурсiв. Розвиток i ускладнення економiчних виробничих процесiв, обчислюваної технiки стимулює ширше використання математичних методiв в управлiннi, сприяє зростанню ролi лiнiйного програмування як актуального роздiлу прикладної математики.

Задача лiнiйного програмування (ЗЛП) - це задача пошуку найбiльшого (або найменшого) значення лiнiйної функцiї z=c1x1+c2x2+...+cnxn (1) за умов, коли змiннi x1,x2,...,xn мають задовольняти систему лiнiйних обмежень типу рiвностей або нерiвностей:

(2) Стандартна, або канонiчна постановка задачi лiнiйного програмування така: знайти такi невiд`ємнi значення змiнних x1,x2,...,xn, що задовольняють систему рiвнянь i надають найменшого значення функцiї z=c1x1+c2x2+...+cnxn.

Вектор змiнних є допустимим планом ЗЛП, якщо його компоненти задовольняють кожне з обмежень (2) цiєї задачi. Оптимальним планом ЗЛП є такий її допустимий план, при якому цiльова функцiя (1) набуває найбiльшого (найменшого) значення порiвняно з її значеннями за будь-якого iншого допустимого плану.

Розв'язати ЗЛП - означає знайти один (кiлька або всi) з оптимальних планiв i обчислити вiдповiдне - оптимальне - значення цiльової функцiї або встановити, що задача не є розв'язаною.

Розв'язок ЗЛП з двома змiнними легко знайти графiчним методом. Графiчне розв'язування ЗЛП з трьома змiнними стає менш наочним, а в разi бiльшої кiлькостi змiнних навiть неможливим.

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

Будь-яка ЗЛП, якщо вона не канонiчна, може буде зведена до равносильної їй канонiчної ЗЛП. Iснують три правила переходу вiд загальної ЗЛП до канонiчної.

Правила переходу

1.Перехiд вiд мiнiмiзацii до максимiзацiї. Задача пошуку мiнiмуму деякої функцiї рiвносильна задачi пошуку максимум протилежної функцiї.

2.Перехiд вiд нерiвностi до рiвностi. Будь-яке обмеження,що має вигляд нерiвностi, можно звести до обмеження-рiвностi, увiвши додаткову невiд'емну змiнну. Так, нерiвнiсть виду

a1x1+ a2x2+...+ anxn<=b .

рiвносильна вимогам

a1x1+ a2x2+...+ anxn + m = b, m0 ,

а нерiвнiсть виду

v1x1+ v2x2+...+ vnxns

рiвносильна вимогам

v1x1+ v2x2+...+ vnxn + h = s, h 0

3.Перехiд вiд змiнних, якi не мають обмежень щодо знака до невiд'ємних. Нехай xj не має обмежень щодо знака. Тодi таку змiнну можна замiнити рiзницею двох невiд'емних змiнних xj' i xj": xj = xj' - xj"0, xj'0, xj"0.

Найбiльш поширенним методом рiшення ЗЛП є симплекс-метод.