2.2. Форми запису задач лп

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

за умов

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

за умов

АХ = А₀,

Х 0,

де

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

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

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

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

за умов

,

,

де

, , …,

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

2.3. Геометрична інтерпретація злп

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

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

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

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

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

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

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

(2.7)

за умов

, (2.8)

, (2.9)

, (2.10)

, (2.11)

, . (2.12)

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

Рис. 2.1. Область допустимих розв’язків

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

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

,

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

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

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