Економіко-математичні методи та моделі (стр. 5 )

max z = 24, дійсно, zmax = 2´6+3´4=24.

Оптимальний план прямоі задачі передбачає виробництво обох видів продукції Р1 и Р2 у кількості відповідно 6 од. и 4 од.

Додаткові змінні х3, х4, х5, х6 характеризують залишок (невикористану частину) ресурсів відповідно S1, S2, S3, S4.

Оскільки х5=1, х6=3, те третій ресурс S3 і четвертий ресурс S4 використовуються в процесі виробництва продукції не повністю, а ресурси S1 и S2 – повністю (х3=х4=0). При такому оптимальному плані виробництва продукції та використанні ресурсів виробництво дістане найбільший прибуток у розмірі 24 у. о.

3) ЗЛП зводиться до розв'язку задачі, у якому кожній лінійній нерівності відповідає якась півплощина. Перетинання цих півплощин є опуклий багатокутник. Область припустимих розв'язків визначимо, побудувавши граничні прямі:

х1 + 3х2 = 18 (I); 2х1 + х2 =16 (II); х2 = 5 (III); 3х1 = 21 (IV); х1 = 0 (V); х2 = 0 (VI). Потім будуємо лінію нульового рівня 2х1 + 3х2 = 0 і градієнт N={2; 3}. Направлення градієнта вказує на направлення зростання цільової функції.

x2

A B

C

D

O 1 E

0 1 x1

Zmax = Z(C), де С –точка перетинання прямих I и II.

Координати точки С знайдемо, розв'язавши систему двох рівнянь:

х1+ 3х2 = 18

2х1 + х2 = 16; С (6; 8)

Z(C) =2´6 +3´4 = 24; Zmax = 24.

Zmin = Z(O), где О – початок системи координат.

Z(O) =2´0 +3´0 =0; Zmin = 0.

Отже, при оптимальному розв'язанні х1 = 6, х2 = 4, Zmax = 24, а при оптимальном решении х1 = 0, х2= 0, Zmin = 0.

Задача 5.2

На три бази надійшов однорідний вантаж у кількості 300 т – на базу А1, 150 т – на базу А2, 250т – на базу А3. Отриманий вантаж потрібно перевезти в п'ять пунктів: 170 т – у пункт В1; 110 т – у пункт В2; 100 т – у пункт В3, 120 т – у пункт В4, 200 т – у пункт В5. Відстані між пунктами відправлення (базами) і пунктами призначення визначені в таблиці (матриця відстаней):

Таблиця 5.3 – Матриця відстаней

Пункти відправлення	Пункти призначення
В1	В2	В3	В4	В5
А1	70	50	15	80	70
А2	80	90	40	60	85
А3	50	10	90	11	25

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

Розв'язок

У випадку пропорційності витрат, кількості вантажу та відстані для розв'язання задачі достатньо мінімізувати загальний обсяг плану перевезень, виражений у тонно-кілометрах. Число баз m = 3, а число пунктів призначення n = 5. Число базисних змінних 3+5-1=7. Знайдемо перший опорний план діагональним методом (методом північно-західного кута).

Заповнення таблиці починається з її північно-західного кута, тобто клітки з невідомим х11. Перша база А1 може цілком задовольнити потребу першого замовника В1 (a1 = 300, b1 = 170, a1 > b1). Припустимо, х11 = 170, уписуємо це значення в клітинку х11 і виключає з розгляду перший стовпець. На базі А1 залишається змінений запас a1' = 130. У новій таблиці із трьома рядками А1, А2, А3 і чотирма стовпцями В2, В3, В4, В5 північно-західним кутом буде клітинка для невідомого х12. Перша база а1 може задовольнити цілком потребу другого замовника В2 (a1' = 130, b2 = 110, a1' > b2). Нехай х12 = 110, уписуємо це значення в клітинку х12 і виключаємо з розгляду другий рядок. На базі А1 новий залишок (запас) а1'' = 20. У новій таблиці із трьома рядками А1, А2, А3 і трьома стовпцями В3, В4, В5 північно-західним кутом буде клітинка для невідомого х13. Тепер третій замовник В3 може прийняти весь запас із бази А1 (а1'' = 20, b2 = 100, а1''< b3). Нехай х13 = 20, уписуємо це значення в клітинку х13 і виключаємо з розгляду перший рядок. У замовника В3 залишилася ще незадоволеною потреба b3'=80. Тепер переходимо до заповнення клітинки для х23 и т. д. Через шість кроків залишиться одна база А3 с запасом вантажу (залишком від попереднього кроку) а3' = 200 і один пункт В5 с потребою b5 = 200. Заповнюємо клітинку, яка залишиться. План складений.

Таблиця 5.4

Пункти відправлення	Пункти призначення										Запас
В1	В2	В3	В4	В5
А1		70		50		15		80		70	300
170	110	20
А1		80		90		40		60		85	150
		80	70
А1		50		10		90		11		25	250
			50	200
Потреби	170	110	100	120	200	700

Базис утворений невідомими х11, х12, х13, х23, х24, х34, х35.

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

S=70´170+50´110+15´20+40´80+60´70+11´50+25´200=30650.

Для оцінки та поліпшення плану скористаємося методом потенціалів. Встановлюємо, що непрямі тарифи перевищують дійсні для клітинок з невідомими х21 і х32. А перерахувавши по циклу, який відповідає вільному невідомому х21, був отриманий новий базисний план перевезень. Оцінимо цей другий крок. Складемо систему рівнянь і розв'яжемо її.

α1 + β1 = 70,

α1 + β2 = 50, β1 = 70,

α1 + β3 = 15, α1 = 0, β2 = 50,

α2 + β1 = 80, => α2 = 10, β3 = 15,

α2 + β4 = 60, α3 = -39, β4 = 50,

α3 + β4 = 11, β5 =65.

α3 + β5 = 25,

Знайдемо непрямі тарифи та порівняємо їх з дійсними:

с14' = α1 + β4 = 50 < с14,

с15' = α1 + β5 = 64 < с15,

с25' = α2 + β5 = 74 < с25,

с22' = α2 + β2 = 60 < с22,

с31' = α3 + β1 = 31 < с31,

с23' = α2 + β3 = 25 < с23,

с32' = α3 + β2 = 11 > с32,

с33' = α3 + β3 = -24 < с33.

Непрямий тариф більше дійсного тільки для однієї клітинки з невідомим х32. Складемо для нього цикл х32+; х34-; х24+; х21-; х11+; х12-;х32+.

Уведемо в базис невідому х32, зробивши перерахунок по циклу із числом

х = min{х34; х21; х12}= min{50; 80; 110}=50, отримаємо нові значення у вершинах циклу.

х32'=0+50=50; х34'=50-50=0; х24'=70+50=120; х21'=80-50=30; х11'=90+50=140; х12'=110-50=60.

Вільна змінна х32 стала базисною, а базисна змінна х34 – вільної. Таким чином, новий план має вигляд:

Таблиця 5.5

Пункти відправлення	Пункти призначення										Запас
В1	В2	В3	В4	В5
А1		70		50		15		80		70	300
140	60	100
А1		80		90		40		60		85	150
30			120
А1		50		10		90		11		25	250
	50			200
Потребности	170	110	100	120	200	700

Для оцінки цього плану складемо систему рівнянь потенціалів для заповнених клі­тинок і розв'яжемо її.

α1 + β1 = 70,

α1 + β2 = 50, β1 = 70,

α1 + β3 = 45, α1 = 0, β2 = 50,

α2 + β1 = 80, => α2 = 10, β3 = 15,

α2 + β4 = 60, α3 = -40, β4 = 50,

α3 + β4 = 10, β5 =65.

α3 + β5 = 25,

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

с14' = α1 + β4 = 50 < с14,

с15' = α1 + β5 = 65 < с15,

с22' = α2 + β2 = 60 < с22,

с23' = α2 + β3 = 25 < с23,

с25' = α2 + β5 = 75 < с25,

с31' = α3 + β1 = 30 < с31,

с33' = α3 + β3 = -25 < с33,

с34' = α3 + β4 = 10

Усі непрямі тарифи менше дійсних, значить отриманий оптимальний план.

Задача 5. 3

Визначити нижню та верхню ціну гри, заданою платіжною матрицею

0,5 0,6 0,8

С= 0,9 0,7 0,8

0,7 0,6 0,6 .

Дослідити гру на наявність сідлової точки.

Розв'язок

Усі розрахунки зручно здійснювати в таблиці 5.6, у якій, крім матриці С, уведені стовпець αi і рядок βj.

Таблиця 5.6

Aj	Bi	αi
В1	В2	В3
А1	0,5	0,6	0,8	0,5
А2	0,9	0,7	0,8	0,7
А3	0,7	0,6	0,6	0,6
βj	0,9	0,7	0,8	α = β=0,7

Аналізуючи рядки матриці (стратегія гравця А), заповнюємо стовпець αi: α1=0,5; α2=0,7; α3=0,6 – мінімальні числа в рядках 1, 2, 3. Аналогічно β1 = 0,9; β2 = 0,7;
β3 = 0,8 – максимальні числа в стовпцях 1, 2, 3 відповідно.

Нижня ціна гри: α = max{0,5; 0,7; 0,6} = 0,7 (найбільше число в стовпці αi),

Верхня ціна гри: β = min{0,9; 0,7; 0,8} = 0,7 (найменше число в рядку βj).

Ці значення рівні, т. е. α = β і досягаються на одній і тій же парі стратегій (А2; В2). Отже, гра має сідлову точку (А2; В2) і ціна гри ν = 0,7.

6 КРИТЕРІЇ ОЦІНЮВАННЯ КОНТРОЛЬНОЇ РОБОТИ

Складові частини контрольної роботи	Кількість балів за правильну відповідь
Теоретичні завдання	задовільно	добре	відмінно
Завдання 1	6	8	10
Завдання 2	6	8	10
Максимальна кількість балів за теоретичний блок	20 балів
Практичні завдання	задовільно	добре	відмінно
Завдання 1	3	4	5
Завдання 2	3	4	5
Завдання 3	3	4	5
Завдання 4	3	4	5
Максимальна кількість балів за блок практичних завдань	20 балів
Максимальна оцінка за контрольну роботу	40 балів
Мінімальна кількість балів для здачі контрольної роботи та допуску до іспиту	24 бала

Оцінка знань студентів по окремих завданнях контрольної роботи курсу «Оптимізаційні методи та моделі» проводиться за наступними критеріями:

-  «відмінно» - вірні та повні відповіді на теоретичні запитання, вірно зроблені розрахунки практичних завдань із грамотними та обґрунтованими висновками;

-  «добре» - вірні але не достатньо повні відповіді на теоретичні запитання, вірно зроблені розрахунки практичних завдань при недостатньо обґрунтованих висновках;

-  «задовільно» - відповіді на теоретичні запитання по темі, але з непринциповими помилками, незначні помилки в здійсненні практичних розрахунків, неправильні висновки.

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

ІНФОРМАЦІЙНО-МЕТОДИЧНЕ ЗАБЕЗПЕЧЕННЯ

ОСНОВНА ЛІТЕРАТУРА

1.  Методи оптимізації в економіці. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 152 с.

2.   А.,  М. Математическое программирование: Учебное пособие. – Х.: ИД «ИНЖЭК», 2003. – 240 с.

3.  Карманов программирование. – М.: Наука, 1986.

4.  Вітлінський В. В.,  І.,  О. Математичне програмування: Навч.-метод. посібник для самост. вивч. дисц. – К.: КНЕУ, 2001. – 248 с.

5.  , Ларіонов Ю. І. Математичне програмування. – Х.: ХТУРЕ, 1997.

6.  Моделирование рисковых ситуаций в экономике и бизнесе: Учеб. пособие / Под ред. . – 2-е изд., перераб. и доп. – М.: Финансы и сатистика, 2001. – 224 с.

ДОДАТКОВА ЛІТЕРАТУРА

1.  Вагнер Г. Основы исследования операций. – Т.1-3. – М.: Мир, 1972.

2.  Вентцель  операций. – М.: Советское радио, 1972.

3.  Дудка  по математике для экономистов. – Львов: Львовский банковский колледж, 1998.

4.  Крушевский А. В., Швецов  программирование и моделирование в экономике. – К.: Вища школа, 1979.

5.  Линейное и нелинейное программирование /Под ред. . – К.: Высш. шк., 1975.

6.  Наконечный С. И., Гвоздецкая  задач по курсу "Математическое программирование": Учебное пособие. – К.: ИСОД, 1996.

7.  Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. – М.: Наука, 1970.

8.  Степанюк  математического программирования. – К.: Высш. шк., 1997.

9.  Таха Х. Введение в исследование операций. – М.: Мир, 1985. – Т. 1, 2.

10.  Хедли Дж. Нелинейное и динамическое программирование. – М.: Мир, 1967.

11.  Юдин Д. Б., Гольштейн  программирование, теория, методы, приложение. – М.: Наука, 1969.

12.  Ястремский  модели математической экономики. – К., 1983.

13.  Ястремский А. И. О соотношениях двойственности в условиях оптимальности в линейных задачах стохастического программирования. – К.: Кибернетика. – 1987.

Додаток А

Приклад оформлення титульного аркуша контрольної роботи

Вищий навчальний заклад України

Харківський інститут економіки ринкових відносин і менеджменту

Кафедра гуманітарних та загально-економічних дисциплін

Контрольна робота

за курсом «Економіко-математичні методи та моделі»
Модуль 1 «Оптимізаційні методи та моделі»

Варіант – ____

студента (ки) економічного факультету II курсу

групи _______ заочної форми навчання

П. І. Б.

номер залікової книжки

Харків – 2010