Оптимізаційні методи та моделі

ОПТИМІЗАЦІЙНІ МЕТОДИ ТА МОДЕЛІ

Конспект лекцій

 

 

Сєвєродонецьк 2013р.

 

 

УДК

Конспект лекцій з дисципліни «Оптимізаційні методи та моделі»

для напряму підготовки: 6.030504 «Економіка підприємства»/ Укл. О.Л. Бродський – Сєвєродонецьк: Вид-во ТI - 2013. – 84 с.

Розроблено на підставі робочої програми дисципліни «Оптимізаційні методи та моделі»

 

 

Укладач	______________	О.Л. Бродський, доцент
Відповідальний за випуск	______________	О.В. Поркуян, зав. каф. ВПМ, проф., д.т.н.
Рецензент	______________	Н.В. Швець, доцент каф. ЕП

 

 

 

 

Вступ

 

Дисципліна «Оптимізаційні методи та моделі» є частиною більш об’ємного курсу «Економіко-математичне моделювання».

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

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

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

Конспект містить 14 лекцій відповідно до діючого робочого плану спеціальності «Економіка підприємства».

Розглянуті лінійні та нелінійні моделі різних рівнів та методи розв’язання задач оптимізації в умовах цих моделей.

 

 

Зміст

1. Вступ………………………………………………………………………..3

2. Лекція 1.Концептуальні аспекти математичного моделювання економіки.Оптимізаційні економіко-математичні моделі…….5

3.Лекція 2.Задачі лінійного програмування та методи їх розв’язування...8

4.Лекція 3.Розв’язування задачі лінійного програмування не в канонічній формі.Двоїстість у лінійному програмуванні………………16

5.Лекція 4. Цілочисельне програмування………………………………...21

6.Лекція 5.Транспортна задача. Побудова опорного плану……………..28

7. Лекція 6. Транспортна задача. Поліпшення плану. Розв’язування задачі у відкритій моделі…………………………………………… 34

8. Лекція 7. Моделі галузевого планування………………………………42

9. Лекція 8. Моделі управління запасами…………………………………46

10.Лекція 9. Багатопродуктові моделі управління запасами…………….53

11. Лекція 10. Ймовірносні моделі управління запасами. Основні поняття теорії ігор……………………………………………………59

12. Лекція 11. Матричні ігри………………………………………………..63

13.Лекція 12. Зведення матричної гри до задачі лінійного програмування. …………………………………………….69

14. Лекція 13. Ігри з природою…………………………………………….73

15. Лекція 14. Динамічні моделі…………………………………………...77

 

Лекція 1
Концептуальні аспекти математичного моделювання економіки
Оптимізаційні економіко-математичні моделі

 

1. Економіко-математичним моделювання
2. Класифікація економіко-математичних моделей
3. Задача оптимального планування випуску продукції
4. Загальна задача лінійного програмування

 

1. Економіко-математичним моделювання

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

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

За способом побудови розрізняють моделі: логічні, фізичні, математичні.

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

Економіко-математичним моделюванням називається теорія, методи та алгоритми розв’язання задач з економічним змістом у математичній формі.

Потреба в такому моделюванні виникає в різних задачах економічного аналізу, планування, прогнозування та ін.

Математичні методи одержання розв’язків для найпростіших задач об’єднані назвою математичне програмування.

 

2.Класифікація економіко-математичних моделей

 

Схема економіко-математичного моделювання:

1) постановка задачі;

2) побудова формалізованої схеми;

3) побудова моделі;

4) дослідження моделі;

5) оцінка отриманого рішення задачі.

Загальна задача лінійного програмування (ЗЛТ)

(1.4)

 

(1.5)

 

; j= 1 ,... n

(1.6)

 

Контрольні запитання

1. Що таке математична модель?

2. Як формулюється задача оптимального планування випуску продукції?

3. Який зміст є у параметрів та змінних цієї задачі?

4. Який вигляд має загальна ЗЛП?

Лекція 2

Алгоритм симплекс-методу

Теорема. Якщо В>0, задача (2.4) - (2.6) завжди має розв’язок; він може бути отриманий за кінцеве число кроків.

 

 

3. Запишемо (2.5) в іншій формі:

 

x₁ • A₁ + x₂ • A₂ +...+ x_n • A_n = B, (2.7)

де ; ;.... - стовпці матриці А.

 

Припустимо, що матриця А містить у собі одиничну матрицю порядку m, розташовану в перших m стовпцях А₁, А₂,...А_М.

Тоді початковий план Х₀ має вигляд:

або у вигляді вектора . (2.8)

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

Розв’язок (план) системи (2.5) за умови (2.6) назвемо припустимим.

Ненульовий припустимий розв’язок задачі називається опорним розв’язком (планом), якщо вектори А_j, щовідповідають додатним координатам плану утворюють незалежну лінійну систему. Якщо число векторів у цій системі дорівнює m, план називається не виродженим, якщо менше - виродженим.

План (вектор) X тоді і тільки тоді є опорним розв’язком задачі, коли точка
М(х₁, х₂,...х_n) є вершиною припустимого багатогранника.

Лекція 3

Не в канонічній формі

Лекція 4

Цілочисельне програмування

1. Постановка задачі цілочисельного програмування (ЗЦП)
2. Метод Гоморі
3. Приклад розв’язування ЗЦП
4. Задача придбання устаткування

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

Розглянемо найпростішу задачу:

(4.1) (7.1)

i = 1, 2, 3...m (4.2)(7.2)

(4.3) (7.3)

цілі (4.4) (7.4)

Метод Гоморі

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

2. Якщо всі координати цього плану цілі – задача розв’язана.

3. Якщо ні – додаються додаткові обмеження.

4. Розширена задача розв’язується симплекс-методом і т.д.

 

Після розв’язування отримуємо оптимальний цілочисельний план або доводимо, що цілочисельного плану задача не має. Недоліки методу: вимога цілочисельності для всіх змінних задачі (як основних так і додаткових). Будемо вважати, що результатом пункту 1 розв’язування задачі (7.1)-(7.3) є такий план

Припустимо, що x_i - дробове число. Позначимо через [ x_i ] його цілу частину, через q_i=x_i-[x_i]={x_i} - його дробову частину. Розглянемо рядок i останньої симплекс-таблиці

 

 

Якщо в цьому рядку дробових елементів не має, то задача (4.1)-(4.4) не має розв’язків. Припустимо, що x_ij – дробові, j=m+1,…n...

Позначимо - дробові частини цих чисел. Уведемо додаткове обмеження

–q_im+1∙ x_m+1 - q_im+2∙ x_m+2-...-q_inx_n+q_i≤ 0 (4.5)

Додамо змінну x_m+1 і перетворимо (4.5) у рівність:

–q_im+1x_m+1-q_im+2x_m+2-…-q_inx_n+x_n+1=-q_i+1

Розв’яжемо отриману задачу двоїстим симплексом-методом.

3.Приклад

x_j>0, цілі, j=1,2,3.

 

Приведемо задачу до канонічного вигляду і розв’яжемо симплекс-методом без умови цілочисельності змінних

 

				-1
	Базиз	Сбаз	B	A1	A2	A3	A4	A5	A6
	А4				-1	1
	А5			-4		-1
	А6
	Fj – Cj			-1	-3
	A3				-1
	A5			-2	1
	A6				1		-1
	Fj – Cj			-4
	A3
	A2			-2
	A6			3			-2	-1
	Fj – Cj		-1
	A3
	A2		11/3				- 1/3	1/3	2/3
	A1	-1	1/3				- 2/3	- 1/3	1/3
	Fj – Cj	46/3				19/3	11/3	1/3

 

 

План не оптимальний

План не оптимальний

План не оптимальний

План оптимальний

; F^* = 46/3

Тому що х₁ =1/3 і х₂= 11/3 не цілі, необхідно доповнити задачу обмеженням. Будемо працювати з другим рядком q₂ =2/3; q₂₅ =1/3; q₂₆ =2/3

-2/3x₄-1/3x₅-2/3x₆+x₇=-2/3

- план умовно припустимий.

 

				-1
	Базиз	Сбаз	B	A1	A2	A3	A4	A5	A6	А7
	А3
	А2		11/3				-1/3	1/3	2/3
	А1	-1	1/3				-2/3	-1/3	1/3
	А7		-2/3"				-2/3	-1/3	-2/3
	Fj – Cj					19/3	11/3	1/3
	A3
	A2						-1
	A1	-1					-1	-1/2		1/2
	А6							1/2		-3/2
	Fj – Cj						3,5		0,5

 

Одержали цілочисельний план

F(Х₅)=15

Залишаючи вихідні змінні, одержуємо F(Х^*)=15

Тому що 15< , точка максимуму з умовою цілочисельності координат знаходиться усередині припустимої множини.

Приклад.

Виділено 20 тисяч гривень на придбання устаткування для нової ділянки, м². Розглядається два види устаткування. Машина типу коштує 5 тис. грн., займає 8м² і має продуктивність 7 тис.од. продукції за зміну. Машина типу коштує 2 тис. грн., займає 4м², і забезпечує виробництво 3 тис. од. продукції за зміну. Розрахувати оптимальний план придбання устаткування, що забезпечить за даних обмежень максимальну продуктивність ділянки.

Уведемо змінні і – плановану кількість машин. Складемо цільову функцію.

Обмеження:

, цілі

Розв’язання:

 

Складемо початковий план

 

Базис	Сб.		A1	A2	A3	A4
x3 x4
Fj - Cj		-7	-3
x1 x2		7,5			-2	-0,5 1,5
Fj - Cj	29,5				0,5

 

План оптимальний: , але – неціле.

Метод Гоморі: .

Обмеження: .

Новий план майже припустимий, застосовується двоїстий симплекс-метод. Одержуємо рішення:

 

– план оптимальний.

=29 .

Рекомендується придбання 2 машин типу і 5 машин типу , загальна продуктивність ділянки 29 тис. од. за зміну. Гроші використовуються повністю, невикористаними залишилося м² площі приміщення.

 

 

Контрольні запитання

1. Якою є постановка задачі цілочисельного програмування?

2. Яким є алгоритм методу Гоморі для ЗЦП?

3. Які недоліки методу Гоморі?

Лекція 5

Транспортна задача

Побудова опорного плану

 

1. Економічна постановка транспортної задачі (ТЗ)
2. Математична модель ТЗ
3. Побудова початкового опорного плану для закритої моделі ТЗ: метод північно-західного кута
4. Методи мінімальної вартості і подвійної переваги

 

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

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

 

2. Уведемо наступні позначення:

- постачальники, - обсяг (кількість) товару в кожного з них; .

- споживачі, - обсяг потреб кожного з них; .

- матриця цін (питомих витрат), де - ціна перевезення товару за маршрутом від до .

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

Тоді загальні витрати за всіма маршрутами

Одержали наступну лінійну модель

цільова функція (5.1)

 

i = 1, 2,...m (5.2)

j = 1, 2,...n (5.3)

(5.4)

 

 

Економічний зміст обмежень:

(5.2) – весь товар постачальників вивезений

(5.3) – усі потреби споживачів задоволені

(5.4) – товар за кожним маршрутом або планується до перевезення (х_ij >0) або не планується (х_ij = 0).

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

Для викладення методів додамо умову:

(5.5)

Зміст умови (5.5); загальний обсяг запасів товару дорівнює загальному обсягу потреб.

Модель (5.1)-(5.4) з додатковою умовою (5.5) називається закритою, без неї – відкритою.

Теорема. Будь-яка закрита модель транспортної задачі має розв’язок.

 

3. Побудова початкового опорного плану для закритої моделі

Будемо заповнювати таблицю з m рядками і n стовпчиками. Клітину таблиці назвемо зайнятою, якщо в неї поміщене перевезення x_ij>0. Інші клітини називаються вільними, x_ij = 0 у них не ставляться.

У системі рівнянь (5.2), (5.3) і (5.5) усього m+n-1 незалежних рівнянь, тому опорний план задачі повинен містити не більш m+n-1 зайнятих клітин. Якщо N = m+n-1 - план називається не виродженим, якщо N<m+n-1 – виродженим.

Циклом у заповненій таблиці називається замкнута ламана лінія з вершинами в зайнятих клітинах.

Приклади циклів:

Опорний план не повинен містити циклів.

 

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

Метод подвійної переваги.

1. У кожному рядку знаходиться клітина з найменшою ціною і позначається позначкою.

2. Те ж саме проводиться для кожного стовпчика.

3. Заповнення таблиці починаємо з клітин, відзначених двома позначками.

4. Після цього заповнюються клітини з однією позначкою.

5. У таблиці, що залишилася, застосовується метод мінімальної вартості.

 

 

Спожив.   Постач.	В1	В2	В3	В4	В5	Запаси
А1	----	----	----	vv 1	----
А2	vv 2	----		----	----
А3	----	v 5 ----	V 3 ----	v 2 ----	vv 2
А4	----	v 8		----
Потреби

 

Схема плану:

N=7

План опорний, вироджений Z=4250 (гр. од.)

З трьох викладених методів даний метод, як правило, дає план з меншою загальною вартістю порівняно з іншими методами.

 

Контрольні запитання

1. Як економічно формулюється транспортна задача?

2. Якою є математична модель ТЗ?

3. Як треба будувати первісний план ТЗ за методом північно-західного кута?

4. Що таке цикл у таблиці ТЗ?

5. Якими є алгоритми методів найменшої вартості та подвійної переваги?

 

Лекція 6

Транспортна задача

Поліпшення плану

Розв’язування задачі у відкритій моделі

 

1. Загальний алгоритм розв’язування ТЗ

2. Перетворення виродженого плану у не вироджений

3. Метод потенціалів для оцінки плану

4. Поліпшення плану в циклі перерозподілу постачань. Приклад розв’язування ТЗ

5. Розв’язування ТЗ у відкритій моделі

 

1. Загальний алгоритм розв’язування транспортної задачі:

а)Побудова початкового опорного плану.

б)Оцінка плану на оптимальність.

в)Поліпшення плану, якщо він не є оптимальним.

г)Оцінка плану і т.д.

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

3. Кожній зайнятій клітині ставиться у відповідність два числа – потенціали постачальника і споживача. При цьому їхня сума прирівнюється ціні, що міститься в цій клітині.

u_i-потенціал постачальника; v_j-потенціал споживача.

u_i+ v_j = c_ij (6.1)

У цій системі невідомих m+n, число рівнянь m+n-1. Отже, система має безліч розв’язків. Досить одержати один розв’язок системи. Для цього можна припустити, що u₁=0 і знайти інші невідомі з відповідних рівнянь.

Для кожної вільної клітини (i; j) обчислюється сума потенціалів постачальника і споживача

d_ij=u_i+v_j

і записується в цю клітину.

Якщо для всіх вільних клітин виконана нерівність

d_ij ≤ c_ij (6.2)

план перевезень оптимальний.

Якщо для деякої клітини

d_ij >c_ij (6.3)

план не є оптимальним і його можна поліпшити.

4. Поліпшення плану досягається перерозподілом постачань за циклом. Цикл повинен містити вершину в клітині з умовою (6.3), а інші вершини – у зайнятих клітинах. Обсяг товару, що перерозподіляється, дорівнює мінімумові з обсягів перевезень, що складаються в клітинах з парними номерами за циклом, початок якого знаходиться в обраній клітині з порушенням (6.2). (Інше пояснення буде в прикладі).

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

Спожив.   Постач.	В1	В2	В3	В4	Запаси	m=4; n=4; m+n- -1=7
А1
А2
А3
А4
Потреби

Вартість плану

Z= 1005 гр.од.

Схема плану:

 

План опорний.

Кількість зайнятих клітин N=7, план не вироджений.

 

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

 

u₁ + v₃ = 3 u₃ + v₂ = 2

u₁ + v₄ = 4 u₄ + v₂ = 3

u₂ + v₁ = 1 u₄ + v₄ = 7

u₃ + v₄ = 2

u₂ + v₄ = 9

 

Нехай u₁ = 0; тоді одержимо

v₃ = 3; v₄ = 4; u₂ = 5; v₁ = -4; u₄ = 3; v₂ = 0; u₃ = 2

Знайдемо суми потенціалів для вільних клітин і порівняємо з відповідними цінами

 

Спожив.   Постач.	В1	В2	В3	В4	Запаси	ui
А1	-4
А2
А3	-2			*
А4	-1
Потреби
vj	-4

 

План не оптимальний, тому що в клітині (2,3) 8 > 6 і в клітині (3,4) 6 > 4.

Виберемо клітину (3,4) і побудуємо цикл перерозподілу.

 

75 * 35 40

 

45 40 85

min (40, 45) = 40. Передача від «-» до «+» 40 од. товару

Одержали новий план перевезень; обчислимо його вартість, побудуємо схему плану і розрахуємо потенціали.

Спожив.   Постач.	В1	В2	В3	В4	Запаси	ui
А1	-1
А2			*
А3	-1
А4
Потреби
vj	-1

 

Вартість плану

Z= 925 гр.од. N = 7.

Схема плану:

План опорний, не вироджений і не оптимальний; у клітині (2,3) 8 > 6.

Побудуємо цикл перерозподілу

90 10 80 20

 

* 10 10

 

min (90, 10) = 10 – кількість одиниць товару, перерозподілена за циклом.

Новий план перевезень

Спожив.   Постач.	В1	В2	В3	В4	Запаси	ui
А1	-2
А2
А3	-2
А4	-1
Потреби
vj	-2

Вартість плану

Z= 905 гр.од.

План оптимальний, тому що для всіх вільних кліток виконана умова (6.3).

Загальна постановки задачі

Мається деякий склад для збереження найменувань товарів. Відомий щоденний попит на кожен вид товарів Відома загальна ємність (місткість) складу . Потрібно визначити процедуру завезення товарів на склад, при якій попит задовольняється і витрати мінімальні. Нехай – обсяги партій відповідних товарів. Їхню суму позначимо через ,

 

У моделі без дефіциту витрати двох видів:

1. витрати за замовленням і доставкою товарів;

2. витрати збереження;

Задача має тривіальне рішення.

Недоліки цього рішення:

1. склад працює як перевалочна база;

2. неможливість реалізації рішення на практиці:

а) для багатьох видів товарів існують мінімальні обсяги партій;

б) загальний обсяг може бути занадто великий для одночасної доставки (транспортне обмеження).

Висновок: для реального працюючого складу (оптової бази) практично неможливе одноразове завезення за всією номенклатурою товарів.

Формулювання однієї з конкретних задач – визначити графік доставки товарів у такій черговості й у такій кількості, щоб при безумовному задоволенні попиту середньої обсяг (рівень) запасів був мінімальним.

Математичні методи розв’язання подібних задач створюють теорію управління запасами.

 

Однопродуктова модель Уїлсона:

1. на складі зберігається один товар (продукт);

2. попит на товар є постійним (рівень запасу товару зменшується з постійною швидкістю) ;

3. у той момент, коли запас вичерпаний, подається заявка на доставку нової партії товарів;

4. виконання заявки (замовлення) здійснюється миттєво;

5. накладні витрати, пов'язані з замовленням і доставкою товару постійні і не залежать від кількості товарів (обсягу партій) ;

6. щоденна вартість збереження одиниці товару
постійна С₁.

Схема роботи складу

– максимальна кількість товару на складі; – час; – інтервал часу між точками замовлення.

;

3.Плануємо роботу складу на деякий період Т

Розраховуємо кількість замовлень: .

Загальні витрати за замовленням і доставкою:

Середній рівень запасу:

Витрати на збереження в одному періоді: .

Загальні витрати на збереження:

Загальні витрати в плановому періоді S:

,

(8.1)

 

Знайдемо мінімум складеної функції витрат.

; ; .

Формула Уїлсона:

(8.2)

Можна перевірити, що Q * - це точка мінімуму:

(8.3)

 

(8.4)

Висновок: у точці мінімуму витрати збереження дорівнюють витратам на замовлення і доставку.

 

(8.5)

Знайдемо інтервал між замовленнями.

(8.6)

 

Практичні труднощі при використанні моделі Уїлсона:

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

2. оптимальне також може бути практично не реалізованим.

 

Напрямки ускладнення моделі Уїлсона:

1. Модель з дефіцитом.

2. – змінний детермінований попит.

3. Моделі з випадковим попитом

4. Багатопродуктові моделі.

Моделі з випадковим попитом

Існує однопродуктовий склад. Вважаємо, що попит