Методи дослідження операцій

будемо називати псевдовартістю перевезення одиниці вантажу із пункту в пункт . Помітимо, що платежі , не обов'язково мають бути додатними: не виключено, що «перевізник» сам платить тому чи іншому пункту якусь премію за перевезення.

Позначимо всю сукупність платежів , через . Не уточнюючи, у який спосіб вони призначаються сформулюємо «теорему про платежі».

Теорема 1. Для заданої сукупності платежів сумарна псевдовартість перевезень

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

У цій формулі величина С залежить лише від сукупності платежів і не залежить від того, який допустимим планом () використовується.

Доведемо це твердження. Маємо

Перетворимо першу з двох останніх сум

відповідно до рівностей (10.3).

Аналогічно

в силу рівностей (10.4).

Таким чином,

Останній вираз для від () не залежить для будь-якого допустимого плану. Теорему 1 доведено.

Спробуємо встановити зв'язок між вартостями та псевдовартостями. Припустимо, що план () допустимий і не вироджений (кількість базових клітинок у таблиці дорівнює n+m-1). Для всіх цих клітинок . Визначимо платежі так, щоб в усіх базових клітинках псевдовартості дорівнювали вартостям:

при .

Для довільних клітин () співвідношення між та може бути будь-яким:

або при .

Співвідношення між та у вільних клітинках таблиці показує, чи оптимальний план перевезень обрано і чи можна його поліпшити.

Теорема 2. Якщо в усіх базових клітинках ()

(12.2)

а для всіх вільних клітинок ()

(12.3)

то план перевезень оптимальний і ніяким способом не може бути здешевлений.

Доведення. Позначимо через - план перевезень із системою платежів , що задовольняє умови теореми 2. Визначимо його сумарну вартість:

(12.4)

У сумі (12.4) відмінні від нуля лише доданки, які відповідають базовим клітинкам, але в них вартості дорівнюють псевдовартостям (згідно з (12.2)). Тому

Згідно з теоремою 1 . Тепер замінимо план () іншим планом (). Новий план має сумарну вартість :

(12.5)

де - нові кількості перевезень, відмінні від нуля, в інших клітинах. Деякі з них збігаються з попередніми клітинками попереднього плану, а інші - з вільними. У першому випадку вартості співпадають з , а в іншому згідно (12.3). Тому сума (12.5)

Звідси випливає, що в умовах теореми 2 ніякими змінами плану перевезень () його вартість змінити не можна. Це означає, що план перевезень, який задовольняє умови теореми 2 - оптимальний. Теорему доведено.

Не важко переконатися, що дана теорема справедлива також для виродженого плану, у якому деякі з базових змінних дорівнюють нулю. Дійсно, те, що в базових клітинках перевезення строго додатні, для доведення не суттєво: достатньо, щоб вони були невід'ємними.

Таким чином, доведено, що ознакою оптимальності плану () є виконання умов:

для всіх базових клітинок;

для всіх вільних клітинок.

План, для якого виконуються ці умови називається потенціальним, а відповідні платежі - потенціалами пунктів . Теорему 2 можна переформулювати так: будь-який потенціальний план оптимальний.

Для розв'язання ЗТТ треба побудувати потенціальний план. Його можна побудувати методом послідовних наближень, задаючись спочатку довільною системою платежів, які задовольняють першу з умов (12.6). Причому в кожній базовій клітинці призначимо суму платежів, що дорівнює вартості перевезень у цій клітинці, потім будемо поліпшувати план, змінюючи систему платежів так, щоб вони наближались до потенціальних.

Для поліпшення плану перевезень використаємо властивість платежів і псевдовартостей: яка б не була система платежів , що задовольняє першу з умов (12.6), для кожної вільної клітинки вартість циклу перерахунку дорівнює:

(12.7)

Приклад. Розглянемо таблицю:

ПП ПВ	В1	В2	В3	В4	В5	В6
А1	c11	c12 -	с13	c14	с15 +	с16
А2	c21	c22 +	с23 -	c24	с25	с26
А3	с31	с32	с33 +	с34	с35 -	с36
А4	с41	с42	с43	с44	с45	с46
А5	с51	с52	с53	с54	с55	с56

Не будемо проставляти в табл. (12.8) ні запаси ні замовлення, ні перевезення (вони нам не потрібні), просто помітимо (обведемо жирною лінією) базові клітинки.

Візьмемо будь-яку вільну клітинку, наприклад (1,5), і побудуємо її цикл перерахунку, додатна вершина якого лежить у вільній клітинці, а всі інші - в базових. Визначимо вартість циклу:

Відповідно до умов (12.6) для всіх базових клітинок вартість дорівнює псевдовартостям, тому

Очевидно, що ця властивість справедлива для будь-якої довільної клітинки. Крім того, вона спрощує пошук циклів з від'ємною вартістю.

Процедура побудови потенціального плану така: як перше наближення до оптимального плану береться будь-який допустимий план. Платежі можна визначити так, щоб виконувалась умова

(12.9)

Рівнянь у (12.9) m+n-1, а кількість невідомих m+n, отже, одну з невідомих можна взяти довільною (наприклад, нульовою), а інші визначимо із системи: для всіх вільних клітин. Якщо виконується умова то ЗТТ розв'язана, оскільки план перевезень оптимальний. Якщо ж хоча б в одній вільній клітинці псевдовартість більша за вартість:

(12.10)

то план перевезень не оптимальний і може бути поліпшений перенесенням перевезень по циклу, який відповідає вільній клітинці. Вартість циклу встановлюється за формулою (12.7).Алгоритм розв'язання ЗТТ методом потенціалів (на підставі теореми 2) такий:

Беремо будь-який опорний план перевезень, у якому відмічено m+n-1 базових клітинок (інші клітинки - вільні). Визначаємо для цього плану платежі виходячи з умови, що в будь-якій базовій клітинці псевдовартість дорівнює вартості:

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

ПП ПВ	В1	В2	В3	В4	В5	Запасиai	Платежібі
А1	10 10 - 17	8 8 + 8	6 9	5 6	4 5	25	0
А2	8 5 +	6 6 - 13	4 4 19	3 3	2 8	32	-2
А3	9 9	7 7	5 5 22	4 4 14	3 3 4	40	-1
А4	6 14	4 10	2 8	1 8	8 8 20	20	4
Замов-лення bj	17	21	41	14	24	117
Платежі вj	10	8	6	5	4

У табл. (12.11) з'явився один стовпчик для платежів б_і та один рядок для платежів в_j. Псевдовартості будемо записувати в лівій частині кожної клітинки, а вартості - у правій. Один з платежів, наприклад, б_і покладемо рівним нулю (). Для кожної базової клітинки покладемо . Випишемо клітинки, де виконується ця рівність:

Отримаємо вісім рівнянь і дев'ять невідомих, тому маємо право одну з невідомих покласти рівною нулю ():

(12.12)

Оскільки не всі псевдовартості у вільних клітинках табл. (12.11) задовольняють умову (12.6), план наведений в таблиці не оптимальний.

Спробуємо його поліпшити, переводячи в базову одну з вільних клітинок, для якої , наприклад, клітинку (2,1). Будуємо відповідний цій клітинці цикл (див. табл. (12.11)). Вартість циклу 5 - 8 = -3. Перенесемо по ньому 13 одиниць вантажу (найменше число, що стоїть у вершинах циклу з від'ємними вершинами). Сумарна вартість перевезень зменшилася на . Знову повторимо перетворення в таблиці, перерахувавши псевдовартості після заміни в (12.12) рівняння на , перерозв'язавши систему рівнянь. Послідовне перетворення табл. (12.11) в (12.13), (12.4), (12.15). Табл. (12.15) містить оптимальні розміри перевезень оптимальними маршрутами.

ПП ПВ	В1	В2	В3	В4	В5	Запасиai	Платежібі
А1	10 10 4 -	8 8 21	9 9	8 6 +	7 5	25	0
А2	5 5 13 +	3 6	4 4 19 -	3 3	2 8	32	-5
А3	6 9	4 7	5 5 22 +	4 4 14 -	3 3 4	40	-4
А4	11 14	9 10	10 8	9 8	8 8 20	20	1
Замов-лення bj	17	21	41	14	24	117
Платежі вj	10	8	9	8	7

ПП ПВ	В1	В2	В3	В4	В5	Запаси ai	Платежі бі
А1	8 10	8 8 21	7 9	6 6 4	5 5	25	0
А2	5 5 17	5 6	4 4 15	3 3	2 8	32	-3
А3	6 9	6 7	5 5 26 -	4 4 10	3 3 + 4	40	-2
А4	11 14	11 10	10 8 +	9 8	8 8 - 20	20	3
Замов-лення bj	17	21	41	14	24	117
Платежівj	8	8	7	6	5

ПП ПВ	В1	В2	В3	В4	В5	Запаси ai	Платежібі
А1	8 10	8 8 21	7 9	6 6 4	5 5	25	0
А2	5 5 17	5 6	4 4 15	3 3	2 8	32	-3
А3	6 9	6 7	5 5 6	4 4 10	3 3 24	40	-2
А4	9 14	9 10	8 8 20	7 8	6 8	20	1
Замов-лення bj	17	21	41	14	24	117
Платежі вj	8	8	7	6	5

Відповідь:

Поняттям «платежі» та «псевдовартості» можна дати наочну економічну інтерпретацію.

Будемо вважати, що - реальні платежі, які пункти та платять за перевезення одиниці вантажу третій особі «перевізнику». Будемо також вважати, що інтереси А і В не антагоністичні. Нехай вони діють як єдина економічна система. Перевезення одиниці вантажу з пункту в пункт об'єктивно дорівнює , а сторони А та В разом платять за це перевезення «перевізнику» суму . Оптимальним буде такий план перевезень, за якого пункти та не платять «перевізнику» понад об'єктивну вартість перевезень. Тобто такий план, будь-яке відхилення від якого не буде вигідне системі АВ, оскільки примусить платити за перевезення більше, ніж якби пункти самі перевозили вантаж.

Розв'яжемо методом потенціалів ЗТТ у виродженому випадку.

Приклад. Розв'язати ЗТТ, транспортна таблиця якої має вигляд (12.16). Будемо вважати, що опорний план методом північно-західного кута побудували.

ПП ПВ	В1	В2	В3	Запаси ai
А1	6 20	4	2	20
А2	3	5 25	4	25
А3	3	6	3 30	30
Замовлення bj	20	25	30	75

Для розв'язання цієї виродженої ЗТТ використовуємо такий прийом. Будемо вважати, що в пункті А₁ знаходиться не 20 одиниць вантажу, а трохи більше: 20+е (е - мала кількість). У пункті А₂ не 25 одиниць вантажу, а 25+е; у пункті А₃: 30-2е.

Після застосування методу північно-західного кута до нової таблиці, отримаємо табл. (12.17).

ПП ПВ	В1	В2	В3	Запаси ai	Платежі бі
А1	6 6 20 -	4 4 + е	3 2	20+ е	0
А2	7 3	5 - 5 25- е	4 4 + 2е	25+ е	1
А3	6 3 +	4 6	3 - 3 30-2е	30-2е	0
Замов-лення bj	20	25	30	75
Платежі вj	6	4	3

Далі, використовуючи метод потенціалів, одержуємо послідовно табл. (12.18)-(12.20).

ПП ПВ	В1	В2	В3	Запаси ai	Платежі бі
А1	3 6	4 4 20+е -	3 2 +	20+ е	0
А2	4 3	5 5 5-е +	4 - 4 20+2е	25+ е	1
А3	3 3 20	4 6	3 3 10-2е	30-2е	0
Замовлення bj	20	25	30	75
Платежі вj	3	4	3

ПП ПВ	В1	В2	В3	Запаси ai	Платежі бі
А1	2 6	3 4	2 2 20+ е	20+ е	0
А2	4 3 -	5 5 25	4 4 + е	25+ е	2
А3	3 3 20 +	4 6	3 - 3 10-2е	30-2е	1
Замовлення bj	20	25	30	75
Платежі вj	2	3	2

ПП ПВ	В1	В2	В3	Запаси ai	Платежі бі
А1	2 6	4 4	2 2 20+ е	20+ е	0
А2	3 3 е	5 5 25	3 4	25+ е	1
А3	3 3 20-е	5 6	3 3 10-е	30-2е	1
Замовлення bj	20	25	30	75
Платежі вj	2	4	2

Після побудови потенціального плану в табл. (12.20) покладемо е =0.

Відповідь:

13. Задачі транспортного типу з неправильним балансом

Досі розглядалася лише одна ЗТТ, у якій сума запасів збігалася із сумою замовлень:

Це класична ЗТТ, інакше «ЗТТ з правильним балансом».

Трапляються також ЗТТ, у яких умова порушується. Баланс може порушуватися в двох напрямках:

Сума запасів у ПВ перевищує суму замовлень:

Сума поданих замовлень перевищує наявні запаси:

Домовимося перший випадок називати «ЗТТ з перевагою запасів», а другий - «ЗТТ з перевагою замовлень».

Розглянемо перший випадок. Для нього справедливі співвідношення:

(13.1)

(13.2)

Задачі транспортного типу (10.5), (13.1), (13.2) можна звести до ЗТТ з правильним балансом. Для цього до n пунктів залучимо пункт , якому призначимо фіктивне замовлення, що дорівнює

і покладемо вартості перевезень в стовпчику . Отже, відправлення певної кількості вантажу , з пункту в пункт не відбулося і залишилося в пункті відправлення.

Аналогічно в другому випадку

тобто на ПВ запасів для виконання всіх замовлень недостатньо. Очевидно, що цю задачу також можна звести до класичної ЗТТ, якщо ввести в розгляд фіктивний пункт відправлення із запасами:



і покласти вартості перевезень із ПВ в будь-який ПП рівними нулю .

Приклад. Розв'язати ЗТТ з неправильним балансом.

ПП ПВ	В1	В2	В3	Запаси ai
А1	5	7	6	50
А2	6	6	5	40
А3	8	4	5	20
Замов-лення bj	18	21	33

ПП ПВ	В1	В2	В3	Вф	Запаси ai	Платежі бі
А1	5 5 18	7 7 21	6 6 11 -	1 0 +	50	0
А2	4 6	6 6	5 5 22 +	0 0 - 18	40	-1
А3	4 8	6 4	5 5	0 0 20	20	-1
Замов-лення bj	18	21	33	38	110
Платежі вj	5	7	6	1

ПП ПВ	В1	В2	В3	Вф	Запаси ai	Платежі бі
А1	5 5 18	7 7 21 -	5 6	0 0 + 11	50	0
А2	5 6	7 6	5 5 33	0 0 7	40	0
А3	5 8	7 4 +	5 5	0 0 - 20	20	-1
Замов-лення bj	18	21	33	38	110
Платежі вj	5	7	6	0

ПП ПВ	В1	В2	В3	Вф	Запаси ai	Платежі бі
А1	5 5 18	7 7 1 -	5 6	0 0 + 31	50	0
А2	5 6	7 6 +	5 5 33	0 0 - 7	40	0
А3	2 8	2 4 20	2 5	-3 0	20	-3
Замов-лення bj	18	21	33	38	110
Платежі вj	5	7	5	0

ПП ПВ	В1	В2	В3	Вф	Запаси ai	Платежі бі
А1	5 5 18	6 7	5 6	0 0 32	50	0
А2	5 6	6 6 1	5 5 33	0 0 6	40	0
А3	3 8	4 4 20	3 5	-2 0	20	-2
Замов-лення bj	18	21	33	38	110
Платежі вj	5	6	5	0

Завдання для самостійних та контрольних робіт

Розв'язати задачі транспортного типу 1-32. Знайти опорний та оптимальний плани перевезень вантажу.

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

14. Розв'язання задач лінійного програмування в цілих числах

Часто в ЗЛП

(14.1)

за обмежень

(14.2)

потрібно одержати розв'язок у якому деякі або всі компоненти мають бути цілими числами. Для цього використовують метод ланцюгів і границь. Схема розв'язання ЗЛП у цілих числах ЦЗЛП полягає в наступному:

Розв'язуємо ЗЛП (14.1), (14.2) за допомогою симплекс-методу (або будь-яким іншим методом) без умови цілочисельності змінних. Якщо змінні - цілі числа, то задачу можна вважати розв'язаною. Нехай змінна x_k набула не цілого значення x_k=б_k , б_k має дробову складову.

Розв'язуємо дві задачі:

(14.1), (14.2) за умови ;

(14.1), (14.2) за умови ,

де значок означає цілу частину числа, що в ньому міститься.

3. У випадку цілих розв'язків задач a) і b) порівнюємо одержані значення функцій L. Більше з них - оптимальне значенням , а змінні, за яких воно досягається, - розв'язок задачі.

4. Якщо ж знайдеться таке x_l, що не відповідає умові цілочисельності, тоді повторюємо виконання п.2, замінивши x_k на x_l. Таку процедуру повторюємо доти, доки всі потрібні змінні не стануть цілими.

Приклад. Розв'язати ЗЛП в цілих числах:

(14.3)

(14.4)

Розв'язування. Виконуємо п. 1 відповідно до симплекс-процедури розподілу:

	b	x1	x2			b	x1	y1
	0	2	3
y1	14	1	4		x2
y2	12	2	3		y2

	b	y2	y1
	-12	-1	0
х2
х1

Розв'язок досягається при . Будемо виділяти клітинки таблиці з базовим елементом. Оскільки, х₁ та х₂ не цілі числа, переходимо до виконання п. 2.

Використовуючи симплекс-метод, розв'язуємо нову задачу:

	b	x1	x2			b	x1	y1
	0	2	3
y1	14	1	4		x2
y2	12	2	3		y2
y3	-4	0	-1		y3

Оскільки в рядку, де стоїть від'ємний елемент, немає від'ємних чисел, задача розв'язку не має, допустима область порожня. Це означає те, що при х₂?4 розв'язку даної задачі не існує. Розв'яжемо задачу (13.3), (13.4) за додаткової умови . Тут і далі значок означає цілу частину числа, що стоїть у дужках. Отримаємо:

	b	x1	x2			b	x1	y3
	0	2	3
y1	14	1	4		y1
y2	12	2	3		y2
y3	3	0	1		x2	3

	b	y2	y3
y1
x1
x2

Розв'язок задачі досягається при . Оскільки містить дробову частину, то знову розв'язуємо дві задачі:

а) (14.3), (14.4) за умови

б) (14.3), (14.4) за умови

Розв'язуємо задачу а):

	b	x1	x2			b	x1	y4
	0	2	3
y1	14	1	4		x2
y2	12	2	3		y2
y3	1	1	0		y3			0
y4	3	0	1		x2	3	0

	b	y3	y4
	-11	-2	-3
y1	1	-1	-4
y2	1	-2	-3
x1	1	1	0
x2	3	0	1

Відповідь: .

Розв'язуємо задачу б):

	b	x1	x2			b	y3	x2
	0	2	3			-4	2	3
y1	14	1	4		x2	12	1	4
y2	12	2	3		y2	8	2	3
y3	-2	-1	0		x1	2	-1	0
y4	3	0	1		y4	3	0	1

	b	y3	y2
	-12	-6	-1
y1
x2
x1	2	1	0
y4

Відповідь: .

Задача знову розпадається на дві:

а) (14.3), (14.4),

б) (14.3), (14.4), .

Розв'язуємо задачу а):

	b	x1	x2			b	y3	x2
	0	2	3			-4	2	3
y1	14	1	4		x2	12	1	4
y2	12	2	3		y2	8	2	3
y3	-2	-1	0		x1	2	-1	0
y4	2	0	1		y4	2	0	1
	b	y3	y4			b	y2	y4
	-10	2	-3			-12	-1	0
y1	4	1	-4		y1	3
y2	2	2	-3		y3
x1	2	-1	0		x1	3
x2	-2	0	1		x2	2	0	1

Відповідь: .

Розв'яжемо задачу б):

	b	x1	x2			b	x1	y4
	0	2	3			-9	2	3
y1	14	1	4		y1	0	1	4
y2	12	2	3		y2	3	2	3
y3	-2	-1	0		y3	-2	-1	0
y4	-3	0	-1		x2	3	0	1

	b	y1	y4
	-9	-2	5
x1	0	1	4
y2	3	-2	-5
y3	-2	1	4
x2	3	0	-1

Відповідь: задача розв'язку не має. Область порожня. Порівнюючи всі розглянуті випадки, одержимо

Аналіз всіх можливих варіантів методу ланцюгів і границь дає можливість зобразити їх наступною схемою (рис. 2).



рис. 2

Завдання для самостійних і контрольних робіт

Розв'язати задачі 1-32 у цілих числах або довести, що вони не мають розв'язку.

1		2
3		4
5		6
7		8
9		10
11		12
13		14
15		16
17		18
19		20
21		22
23		24
25		26
27		28
29		30
31		32

15. Виробничо-транспортна задача

Розглянемо об'єкт економічної діяльності, який складається з виробничого блоку для забезпечення виробництва , де - кількість виробленої продукції і-го асортименту. Крім того, забезпечується доставка виробленої продукції до місця споживання (пунктів споживання). Пункти споживання можуть бути різні: склади, магазини, підрозділи, де продукція виступає як сировина, та ін. Усі вони є складовими частинами єдиної економічної системи (об'єкта економічної діяльності). Будемо вважати, що діяльність такої системи підпорядкована єдиній меті - максимізації прибутку:

(15.1)

де - вартість одиниці продукції і-го асортименту. Для простоти міркувань, розглядатимемо замкнену систему (без суттєвих зовнішніх впливів), що задовольняє умови рівноваги за В.В. Леонтьєвим [2]:

 (15.2)

де - технологічна (нормативна) матриця коефіцієнтів, а - кількість кінцевої продукції і-го асортименту; а також умови:

(15.3)

де запаси ресурсів, що використовуються в процесі виробництва, m - їх кількість, - нормативи використання j-го ресурсу для виробництва одиниці і-го продукту.

Транспортні витрати зменшують розмір прибутку, тому мають бути мінімальними. Суть досліджуваної проблеми полягає в гармонізації обсягу виробництва продукції з витратами на її транспортування для оптимізації прибутку так, щоб виконувалися умови (15.2), (15.3).

Для розв'язання даної задачі пропонується наступна схема. Будемо вважати, що всі величини задачі (15.1)-(15.3) мають вартісну сутність.

Розширимо матрицю А, додаючи до неї (n+1)-й стовпчик та (n+1)-й рядок . Елементи матриці є технологічними коефіцієнтами витрат і-ї продукції для забезпечення одиничних перевезень (наприклад, перевезень вартістю в 1000 грн.). Елементи - розмір сумарних транспортних затрат для доставки одиниці j-ї продукції до місця призначення. Тоді система (15.2) має вигляд:

(15.4)

де , ; - роз-ширена та доповнена матриця сумарних транспортних затрат на перевезення всієї продукції системи;

де - сумарні транспортні затрати на перевезення продукції і-го асортименту. Покладемо або будемо вважати, що затрат на власні перевезення немає.

Надалі опустимо знак «-» у формулі (15.4), і додамо знак «N». Тоді (15.4) можна переписати так:

Знаходимо обернену матрицю , де

Знаходимо

Підставляємо в (15.1) та (15.3) і зводимо подібні члени відносно .

Розв'язуємо ЗЛП:

де - компоненти вектора .

Знаходимо .

Формуємо ЗТТ:

ППk ПВk			…
			…
			…
…	…	…	…	…	…
			…
			…

де - вартості перевезень одиниці продукції з і-го пункту відправлення в j-й пункт призначення для продукції k-го виду; - кількість споживачів k-го виду продукції, - кількість її виробників; та - відповідно пункти відправлення та призначення продукції k-го виду.

Обчислюємо . Покладемо , одержаними числами в матриці , де - елементи k-го стовпчика матриці повних затрат . В пп. 3-7 покладаємо замість знака «0» у змінних знак «1». Повторюємо виконання пп. 3-8, поступово нарощуючи на одиницю доти, доки виконується умова:

де - наперед задане число, яке характеризує точність обчислень і задається ОПР;

Розв'язком виробничо-транспортної задачі будуть та , які відповідно складають , . Остання компонента вектора визначає сумарні оптимальні транспортні витрати економічного об'єкта.

Завдання для самостійних і контрольних робіт

Розв'язати виробничо-транспортні задачі.

Транспортні таблиці мають такий вигляд:

І.

			С1	С2	М1	М2
	4	6	4	6	5	5
	6	5	6	6	4	4

ІІ.

			С1	С2	М1	М2
	4	6	4	6	5	5
	6	5	6	6	4	4

Примітка: - підприємства, що випускають продукцію 1-го виду, і=1,2; - підприємства, що випускають продукцію 2-го виду, і=1,2;

С₁, С₂ - склади; М₁, М₂ -магазини.

1		2
3		4
5		6
7		8
9		10
11		12
13		14
15		16
17		18
19		20
21		22
23		24
25		26
27		28
29		30
31		32

16. Динамічна модель оптимального керування. Принцип максимуму Л.С. Понтрягіна

Розглянемо математичну модель оптимального керування. Нехай математична модель економічної системи має вигляд:

(16.1)

 -похідна функції x(t) за t. - неперервно-диференційовані функції за фазовими змінними ; - вектор-параметр керування, який знаходиться в розпорядженні ОПР. , де U - множина змінних вектор-параметра керування.

Будемо вважати, що треба перевести систему за фіксований час Т із стартового стану у такий стан , у якому функціонал:

, (16.2)

де - диференційована функція аргументів , досягає найменшого значення. Тобто, треба знайти таке оптимальне керування, набір з множини U, і відповідну йому оптимальну траєкторію, що мінімізують функціонал (16.2).

Спряженою до (16.1) будемо називати систему рівнянь:

(16.3)

де H - функція Гамільтона:

, .

Сформулюємо теорему [4]: принцип максимуму Л. С. Понтрягіна.

Теорема. Для розв'язання задачі (16.1), (16.2) необхідне виконання умови:

при кожному , що задовольняє (16.3).

Очевидно, у разі виконання умови (16.4) на єдиному наборі , та існування розв'язку задачі оптимального керування принцип максимуму є і достатньою умовою оптимальності на розв'язках задачі (16.1), (16.3).

Проілюструємо застосування принципу максимуму на конкретному прикладі. Функції будемо вважати залежними від часу.

Приклад. Розв'язати макроекономічну задачу оптимального керування [7], якщо модель системи описується диференційним рівнянням вигляду:

(16.5)

де х - відношення основного капіталу до кількості населення; u - частка національного доходу, спрямована на збільшення основного капіталу; n - амортизаційна постійна; - виробнича функція.

Математична модель (16.5) побудована на допущенні, що частка оплати праці дорівнює ; - задані числа, .

Задача полягає у знаходженні , що забезпечує мінімальне значення функціоналу:

 (16.6)

де - наперед задані додатні числа.

Алгоритм розв'язку задачі:

Будуємо функцію Гамільтона для задачі (16.5),(16.6):

,

(16.7)

Згідно з принципом максимуму:

Спочатку не будемо зважати на нерівності . Тоді:

або (16.8)

Підставимо отримане значення в (16.7).

(16.9)

Отримаємо диференціальне рівняння з відокремлюваними змінними.

Розв'яжемо рівняння (16.9)

Враховуючи , отримаємо:

Оскільки знайдено , для оптимального керування , що задовольняє принцип максимуму (16.4), то можна вважати .

Знайдемо траєкторію , для оптимального керування:

або

Враховуючи початкову умову

Підставляючи значення в (16.8) отримаємо

Знайдемо розв'язок для кожного з трьох випадків:

Проведемо заміну змінних:

Як і в попередньому випадку покладемо:

(16.19)

Завдання для самостійних і контрольних робіт

Розв'язати задачі оптимального керування.

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.
25.		26.
27.		28.
29.		30.

17. Оптимізація розподілу ресурсів в умовах кризи. Оптимальність за Парето

Будемо вважати, що об'єкт виробничої діяльності складається з керівного центрального органу і S підпорядкованих йому підсистем. Підсистеми зобов'язані виконувати замовлення центрального органу, але після виконання замовлень (за наявності ресурсних можливостей) можуть вести і самостійну господарську діяльність. Замовлення центрального органу має пріоритет.

Будемо також вважати, що центральний орган має ресурсні резерви відповідно в кількостях , де m - розміри номенклатури резервів.

Нехай потреба в продукції, яку виробляє об'єкт економічної діяльності, складається відповідно з вектора чисел , де - кількість продукції і-го виду, яку треба виробити. Нормативні затрати резервних ресурсів складають матрицю:

де - кількість і-го ресурсу необхідного для випуску одиниці j-го продукту. Вважаємо, що деякі ресурси (резерви) можуть бути поповнені під час виробничої діяльності фірми (економічної системи). Відомі також граничні допустимі норми випуску продукції, які, будучи порушені, призводять до припинення діяльності фірми (нижні границі випуску). Це границі її життєдіяльності. Установлені нормативи затрат ресурсів локальних підсистем. Будемо вважати, що завдання центрального органу не може бути виконане через обмеженість резервів.

Викладені вище припущення дозволяють запропонувати таку модель раціонального розподілу запасів ресурсів.

Через недостатній рівень запасів вектора досягнути не можна. Тому логічно поставити задачу: за наявних ресурсів забезпечити найбільший процент виконання плану. Це означає, що треба забезпечити

за умови:

(17.1)

Локальна мета кожної з v підсистем складається з максимізації прибутку:

(17.2)

за виконання умов:

(17.3)

Нехай - характеризує границю «живучості» об'єкта виробничої діяльності. Жодного продукту не можна випускати менше пропорції . - вартість одиниці продукції відповідної v-ї підсистеми, - ціна продукції х_і для v-ї підсистеми.

Як бачимо, модель багатокритеріальна. Розглянемо наступний алгоритм оптимізації:

В нерівностях (17.1), (17.3) зробимо заміну змінних і покладемо

Знайдемо

(17.4)

Перевіряємо

(17.5)

Якщо нерівність (17.5) порушується, то запаси ресурсів не забезпечують «виживання» виробництва. У такому випадку слід нарощувати (якщо є така можливість) ті резерви, для яких забезпечується нерівність (17.5).

Будемо вважати, що умова (17.4) виконується. Тоді покладемо

(17.6)

Розшукаємо такі компоненти в (17.6), які не входять у нерівності (17.1), (17.3) з коефіцієнтом відмінним від нуля. Якщо такі знайшлися, виконуємо п.6. У випадку відсутності шуканих компонентів переходимо до виконання п.7.

Знаходимо число

Покладаємо , якщо

, (17.7)

де - номер компоненти для якої умова п.5 виконалась. Далі повторюємо виконання п.5 за виконання умови (17.7).

Якщо умови п.5 не виконуються, тоді формуємо нерівності:

(17.8)

і розв'язуємо задачу лінійного програмування (17.2), (17.8), послідовно знаходячи доти, доки перестане виконуватися п.5 (); , де компоненти вектора характеризують покомпонентні «пороги» значень граничних рівнів виробництва продукції.

Результатом розв'язування даної багатокритеріальної задачі є одержання розв'язку за Парето.

Описаний вище алгоритм, поступового покомпонентного наповнення розв'язку задачі особливо ефективний для розв'язування задач великої розмірності на комплексах ЕОМ.

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

Список використаної та рекомендованої літератури

Вентцель Е. С. Исследование операций. - М.: Сов. радио, 1972.

Глушков В. М., Кудринский В. Ю., Охрименко М. Г. Об одной модели планирования на макроуровне с оптимизацией транспортных затрат // ДАН СССР. - 1976.- Т. 231.- № 3.

Глушков В. М. Макроэкономические модели и принципы построения ОГАС. - М.: Статистика, 1975.

Математическая теория оптимальных процессов / Л. С. Понтрягин, В. Г. Болтянский, Р. В. Гамкрелидзе, Е. Ф. Мищенко, - М.: Физматгиз, 1961.

Охрименко М. Г. К вопросу о решении систем балансовых уравнений // ДАН СССР. - 1977.- Т. 234.- № 1.

Саати Т. Л. Математические методы исследования операций. М.: Воениздат, 1963.

Сталерью Л. Равновесие и экономический рост. - М.: Статистика, 1974.