17. Математична постановка задач лінійного програмування. Система гіпотез.

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

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

або

за умов

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

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

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

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

Приклад 2.1. Записати в канонічній формі таку задачу ЛП:

за умов

Розв'язування. Помножимо другу нерівність на (–1) і введемо відповідно допоміжні змінні x₄ і x₅ для другого та третього обмеження:

Неважко переконатися, що допоміжні змінні, у цьому разі x₄ і x₅, є невід'ємними, причому їх уведення не змінює цільової функції.

Отже, будь-яку задачу ЛП можна записати в такій канонічній формі:

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

за умов

Задачу (2.4)—(2.6) можна розв'язувати на мінімум, якщо цільову функцію помножити на (–1), тобто

18. Визначення множини допустимих планів задачі лп

Задачу ЛП (ЗЛП) зручно записувати за допомогою знака суми «». Справді, задачу (2.4)—(2.6) можна подати так:

за умов

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

за умов

де

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

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

— вектор коефіцієнтів при змінних у цільовій функції.

Часто ЗЛП зручно записувати у векторній формі:

за умов

де

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

Геометрична інтерпретація ЗЛП. Кононічна форма ЗЛП і її оптимальний план.

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

№ з/п	Техніко-економічний показник із розрахунку на 1 га	Сільськогосподарська культура		Наявний ресурс
		Озима пшениця	Цукровий буряк
1	Жива праця, людино-днів	5	25	270
2	Механізована праця, людино-днів	2	8	80
3	Прибуток, тис. грн.	0,7	1

Критерієм оптимальності є максимізація прибутку.

Запишемо економіко-математичну модель структури виробництва озимої пшениці та цукрового буряка, скориставшись такими позначеннями:

x₁ — шукана площа посіву озимої пшениці;

x₂ — шукана площа посіву цукрового буряка.

ЗЛП має вигляд:

за умов

Геометричну інтерпретацію задачі наведено на рис. 2.1.

Область допустимих розв'язків дістаємо так. Кожне обмеження, наприклад , задає півплощину з граничною прямою . Будуємо її і визначаємо півплощину, яка описується нерівністю . З цією метою в нерівність підставляємо координати якоїсь характерної точки, скажімо і . Переконуємося, що ця точка належить півплощині . Цей факт на рис. 2.1 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають нерівностям (2.8)—(2.12). У результаті перетину цих півплощин утворюється область допустимих розв'язків задачі (на рис. 2.1 — многокутник ABCD). Цільова функція описує сім'ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z = 0, маємо . Ця пряма проходить через початок системи координат. Коли Z = 3,5, дістаємо пряму .

Загальна задача лінійного програмування (2.1)—(2.3) геометричне інтерпретується так: кожне і-те обмеження, що має вигляд рівняння

у n-вимірному просторі основних змінних задає гіперплощину. Кожному обмеженню виду (2.2) і (2.3) відповідають гіперплощина та півпростір, який лежить по один бік цієї гіперплощини. У перетині всіх півпросторів, що визначаються обмеженнями задачі (2.2) і (2.3), утворюється опуклий многогранник допустимих її розв'язків. Цільову функцію

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