Тема 9. Задачі динамічного програмування

Економічна сутність, деякі основні типи задач та моделі динамічного програмування (ДП).

Задачі про заміну основного капіталу підприємства.

Багатокроковий процес прийняття рішень та ДП.

Метод рекурентних співвідношень. Принцип оптимальності Беллмана.

Алгоритм Джонсона.

Розділ 2

ЗАГАЛЬНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇЇ РОЗВ’ЯЗУВАННЯ

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

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

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

або

за умов

(2.2)

. (2.3)

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

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

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

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

Приклад 2.1.

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

 max

за умов

.

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

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

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

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

за умов

(2.5)

. (2.6)

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

.

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.

2.4. ОСНОВНІ АНАЛІТИЧНІ ВЛАСТИВОСТІ РОЗВ’ЯЗКІВ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

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

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

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

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

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

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