Navch._posibnuk_Ivaschyk
.pdf
|
qi = yi v;q1 = 0;q2 =1;q3 = 0;q4 = 0;q5 |
= 0 . |
|
|||
Отже, вектори ймовірностей оптимальних змішаних стратегій |
||||||
відповідно |
для |
першої |
та |
другої |
фірми |
будуть |
p = (0; 0; 0,5; |
0; |
0,5); q = (0; 1; |
0; 0; |
0), а ціна початкової гри – |
v* = v − 4 = 0.♦
8.6.Питання для самоконтролю
1.Які ознаки покладені в основу класифікації ігор?
2.Сформулюйте економічну постановку задачі визначення оптимального розв’язку в іграх двох осіб з нульовою сумою.
3.Яка гра має назву гри з сідловою точкою?
4.Що таке змішані стратегії?
5.На чому грунтується методика визначення розв’язку при змішаних стратегіях?
6.Опишіть алгоритм графічного методу розв’язку ігор виду 2 × m і n × 2.
7.Охарактеризуйте методику зведення задач теорії ігор до задач лінійного програмування.
8.З яких етапів складається процес знаходження розв’язку гри з використанням лінійного програмування?
9.Розв’яжіть приклад 8.3, якщо:
5 |
0 |
2 |
−3 |
−5 8 |
|
|
|
−2 |
0 |
5 |
0 |
|
|
4 |
−3 |
|||||
0 |
4 |
−8 |
−6 |
2 |
0 |
|
A = |
3 |
5 |
8 |
−6 −7 |
. |
|
0 |
|
|||||
3 |
2 |
0 |
7 |
5 |
−6 |
|
|
|
−5 −4 9 |
|
|
||
8 0 |
−9 |
|||||
|
|
|
|
|
|
|
241
Розділ 9. Оптимізаційні моделі предметних областей
9.1.Модель оптимізації виробничої програми підприємства
Розглянемо постановку задачі оптимізації виробничої програми підприємства та побудуємо її економіко-математичну модель.
Для організації виробництва m видів продукції підприємство має n видів виробничих ресурсів, стосовно яких задано обсяги запасів та норми їх використання на одиницю випуску продукції.
Відомий ринковий попит на окремі види продукції, а також ефективність їх виробництва (ціна, прибуток від одиниці продукції, собівартість одиниці продукції і т.д.). Необхідно побудувати модель оптимізації виробничої програми підприємства для випуску різних видів продукції на основі наявних ресурсів. У якості критерію ефективності прийнятиабоприбуток, абоваловупродукцію, абособівартість.
Для побудови економіко-математичної моделі задачі введемо позначення: і – індекс виду ресурсу, i =1,n ; j – індекс виду продукції, j =1, m ; k – індекс критерію оптимальності, k =1, K ; aij– норма
використання і-го виду ресурсу на випуск одиниці продукції j-го виду; Аі – обсяг запасів і-го виду ресурсів; Вj – величина договірних поставок j-го виду продукції; Ckj – величина ефективності k-го критерію оптимальності при випуску одиниці продукції j-го виду; xj – невідома величина, яка означає обсяг випуску продукції j-го виду; M1
– множина видів продукції, для яких встановлюється нижня та верхня межа ринкового попиту; M2 – множина видів продукції, для яких
існують фіксовані договірні поставки; |
αj , βj –відповідно, нижня та |
||||||||
верхня межі ринкового попиту на продукцію j-го виду. |
|
||||||||
Враховуючи введені позначення, математична модель матиме |
|||||||||
вигляд. |
|
|
|
|
|
|
|
|
|
Знайти розв’язок {x j |
≥ 0, j = |
|
}, який забезпечить |
|
|||||
1, m |
|
||||||||
|
m |
|
|
|
|
|
|
||
Zk |
= ∑Ckj xj → max(min) |
(9.1) |
|||||||
|
j=1 |
|
k= |
1,K |
|
|
|||
при виконанні умов: |
|
|
|
|
|
|
|
|
|
1) з використання обсягів наявних ресурсів |
|
||||||||
|
m |
|
|
|
; |
(9.2) |
|||
|
∑aij xij ≤ Ai ,i =1,n |
j=1
242
2) |
з випуску продукції, врахувуючи ринковий попит |
|
|||
|
|
αj ≤ x j |
≤ βj , |
j M1 . . |
(9.3) |
3) |
з виконання фіксованих умов відносно поставки продукції |
||||
|
|
x j |
= Bj , |
j M 2 ; |
(9.4) |
Приклад |
9.1 Для виготовлення п’яти видів |
продукції |
|||
( B1 ,B2 ,...,B5 ) |
підприємство |
використовує токарне, |
фрезерне, |
свердлильне устаткування № 1, розточувальне та свердлильне устаткування № 2, а також комплектуючі деталі.
Крім цього, складання виробів вимагає виконання певного обсягу складально-налагоджувальних робіт. Норми затрат всіх видів ресурсів на виготовлення одиниці кожного виробу, запаси ресурсів, прибуток від реалізації одного виробу та ціна одиниці продукції наведені в табл. 9.1. Договірними умовами передбачено мінімальний випуск продукції четвертого виду в кількості 200 одиниць. Аналізуючи ринковий попит, встановлено обмеження з максимального випуску другого та п’ятого видів продукції, відповідно в кількості 3400 і 2800 одиниць.
Таблиця 9.1
|
|
|
|
|
Норми затрат ресурсів на |
|
Обсяг |
||||||
|
|
Ресурси |
|
виготовлення одного виробу |
|||||||||
|
|
|
ресурсу |
||||||||||
|
|
|
|
B |
B |
2 |
B |
3 |
B |
4 |
|
B |
|
|
|
|
|
1 |
|
|
|
|
5 |
|
|||
Устаткування, люд. год. |
|
Свердлильне №1 |
2,1 |
|
|
2,5 |
|
|
|
4,3 |
25000 |
||
|
Свердлильне №2 |
2,1 |
1,8 |
2,3 |
1,5 |
|
1,2 |
16000 |
|||||
|
|
Фрезерне |
|
6,2 |
4,1 |
5,0 |
|
|
30000 |
||||
|
|
Токарне |
0,6 |
|
|
0,7 |
|
|
|
0,9 |
5000 |
||
|
|
Розточне |
0,8 |
0,9 |
1,1 |
1,3 |
|
0,4 |
10000 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Комплектуючі деталі, шт. |
4 |
3 |
4 |
6 |
|
4 |
40000 |
||||||
Складально-налагоджувальні |
4,5 |
2,2 |
2,6 |
5,3 |
|
4,6 |
45000 |
||||||
роботи, люд.-год. |
|
|
|
|
|
|
|
|
|
|
|
||
Прибуток |
від |
реалізації |
1200 |
2300 |
3000 |
1600 |
|
1900 |
|
||||
одного виробу, грн. |
|
|
|
|
|
|
|
|
|
|
|
||
Ціна одного виробу, грн. |
9000 |
6400 |
6000 |
4200 |
|
7200 |
|
||||||
Мінімальний випуск, шт. |
|
|
|
|
|
200 |
|
|
|
||||
Максимальний випуск, шт. |
|
3400 |
|
|
|
|
|
2800 |
|
Розрахувати оптимальний випуск продукції, який забезпечить підприємству максимальний прибуток та провести повний економікоматематичний аналіз.
243
♦Розв’язування.
Для побудови числової моделі задачі введено невідомі величини х1, х2, …, х5, які відповідно означають розміри випуску підприємством продукції першого, другого і т.д. п’ятого видів.
Необхідно знайти такий розв’язок {x j ≥ 0, j =1,5}, який би забезпечив
підприємству максимальний прибуток (Z1):
Z1 =1200x1 + 2300x2 +3000x3 +1600x4 +1900x5 → max
при виконанні умов:
наявного фонду робочого часу устаткувань 1) свердлильного № 1
2,1x1 +3,5x3 + 4,3x5 ≤ 25000;
2) фрезерного
6 ,2 x2 + 4 ,1x3 + 5 ,0 x4 ≤ 30000 ;
3) токарного
0,6x1 + 0,7x3 + 0,9x5 ≤ 5000 ;
4) розточного
0,8x1 + 0,9x2 +11, x3 +1,3x4 + 0,4x5 ≤10000 ; 5) свердлильного № 2
2,1x1 +1,8x2 + 2,3x3 +1,5x4 +1,2x5 ≤16000; 6) використання комплектуючих деталей
4x1 +3x2 + 4x3 +6x4 + 4x5 ≤ 40000;
7)можливого виконання складально-налагоджувальних робіт
4,5x1 +3,2x2 + 2,6x3 +5,3x4 + 4,6x5 ≤ 45000 ;
8)з виконання договірних умов відносно випуску продукції
четвертого виду x4 ≥ 200;
9)з максимального випуску продукції другого виду x2 ≤ 3400 ;
10)п’ятого виду x5 ≤ 2800 .
Розв’яжемо задачу з допомогою пакету LINA. Введемо цільову функцію та систему обмежень побудованої задачі з допомогою команди МАХ.
Для одержання оптимального розв’язку і післяоптимізаційного аналізу задачі використаємо команду GO. З допомогою команди TABL одержимо зміст останньої симплекс-таблиці. У результаті виконання цих двох команд нами будуть одержані дані у вигляді трьох таблиць (табл. 9.2, 9.3, 9.4).
244
: MAX 1200x1+2300x2+3000x3+1600x4+1900x5
?ST
?2.1x1+3.5x3+4.3x5≤25000
?6.2x2+4.1x3+5.0x4≤30000
?0.6x1+0.7x2+0.9x5≤5000
?0.8x1+0.9x2+1.1x3+1.3x4+0.4x5≤10000
?2.1x1+1.8x2+2.3x3+1.5x4+1.2x5≤16000
?4x1+3x2+2x3+6x4+4x5≤40000
?4.5x1+3.2x2+2.61x3+5.3x4+4.3x5≤45000
?x4≥200
?x2≤3400
?x5≤2800
END
|
|
|
|
Таблиця 9.2 |
|
|
Значення цільової функції |
|
|
||
1) |
|
21634060.0 |
|
|
|
Змінна |
|
значення |
|
відносна оцінка |
|
X1 |
|
.000000 |
|
1520.000000 |
|
X2 |
|
2124.127000 |
|
.000000 |
|
X3 |
|
3702.857000 |
|
.000000 |
|
X4 |
|
200.000000 |
|
.000000 |
|
X5 |
|
2800.000000 |
|
.000000 |
|
рядок |
|
додаткові змінні |
|
двоїста змінна |
|
2) |
|
.000000 |
|
17.460300 |
|
3) |
|
13818.290000 |
|
.000000 |
|
4) |
|
992.111000 |
|
.000000 |
|
5) |
|
2635.143000 |
|
.000000 |
|
6) |
|
.000000 |
|
1277.778000 |
|
7) |
|
13821.900000 |
|
.000000 |
|
8) |
|
15475.360000 |
|
.000000 |
|
9) |
|
.000000 |
|
316.666700 |
|
10) |
|
1275.873000 |
|
.000000 |
|
11) |
|
.000000 |
|
291.000000 |
|
245
|
|
|
Таблиця 9.3 |
|
|
Граничний коефіцієнт цільової функції |
|||
Змінні |
Поточний |
Допустиме |
Допустиме |
|
коефіцієнт |
збільшення |
зменшення |
||
|
||||
х1 |
1200.000000 |
1520.000000 |
нескінченність |
|
х2 |
2300.000000 |
47.826030 |
322.847000 |
|
х3 |
3000.000000 |
237.338400 |
61.111040 |
|
х4 |
1600.000000 |
316.666700 |
нескінченність |
|
х5 |
1900.000000 |
|
291.587200 |
|
|
Границі правих частин |
|
||
Рядок |
Поточна RHS |
Допустиме |
Допустиме |
|
збільшення |
зменшення |
|||
|
|
|||
2 |
25000.000000 |
5817.261000 |
3494.781000 |
|
3 |
30000.000000 |
нескінченність |
13818.290000 |
|
4 |
5000.000000 |
нескінченність |
992.111000 |
|
5 |
10000.000000 |
нескінченність |
2635.143000 |
|
6 |
16000.000000 |
2296.571000 |
3822.429000 |
|
7 |
40000.000000 |
нескінченність |
13821.900000 |
|
8 |
45000.000000 |
нескінченність |
15475.360000 |
|
9 |
200.000000 |
2548.953000 |
200.000000 |
|
10 |
3400.000000 |
нескінченність |
1275.873000 |
|
11 |
2800.000000 |
648.150800 |
2351.845000 |
|
|
|
|
|
246
Таблиця 9.4
Рядок (Базис) |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
||
1 |
ART |
Х3 |
1520.00 |
.000 |
.000 |
.000 |
.000 |
2 |
SLK |
.600 |
.000 |
1.000 |
.000 |
.000 |
|
3 |
3 |
3.740 |
.000 |
.000 |
.000 |
.000 |
|
4 |
SLK |
4 |
.320 |
.000 |
.000 |
.000 |
.000 |
5 |
SLK |
5 |
-220 |
.000 |
.000 |
.000 |
.000 |
6 |
SLK |
Х2 |
.400 |
1.000 |
.000 |
.000 |
.000 |
7 |
7 |
1.600 |
.000 |
.000 |
.000 |
.000 |
|
8 |
SLK |
8 |
1.660 |
.000 |
.000 |
.000 |
.000 |
9 |
SLK |
Х4 |
.000 |
.000 |
.000 |
1.000 |
.000 |
10 |
10 |
-.400 .000 |
.000 |
|
.000 |
.000 |
|
11 |
|
Х5 |
.000 |
.000 |
.000 |
.000 |
1.000 |
Рядок |
SLK2 |
SLK3 |
SLK4 |
SLK5 |
SLK6 |
SLK7 |
|
|
1 |
17.460 |
.000 |
.000 |
.000 |
1277.778 |
.000 |
|
2 |
.286 |
.000 |
.000 |
.000 |
.000 |
.000 |
|
3 |
-1.171 |
1.000 |
.000 |
.000 |
.000 |
.000 |
|
4 |
.256 |
.000 |
1.000 |
.000 |
.389 |
.000 |
|
5 |
.014 |
.000 |
.000 |
1.000 |
-.500 |
.000 |
|
6 |
-.365 |
.000 |
.000 |
1.000 |
.556 |
.000 |
|
7 |
.524 |
.000 |
.000 |
.000 |
-1.667 |
1.000 |
|
8 |
.425 |
.000 |
.000 |
.000 |
-1.778 |
.000 |
|
9 |
.000 |
.000 |
.000 |
.000 |
.000 |
.000 |
|
10 |
.365 |
.000 |
.000 |
.000 |
-.556 |
.000 |
|
11 |
.000 |
.000 |
.000 |
.000 |
.000 |
.000 |
Рядок |
SLK8 |
SLK9 |
SLK10 |
SLK11 |
|
1 |
.000 |
.32E+03 |
.000 |
.29E+03 |
.22E+08 |
2 |
.000 |
.000 |
.000 |
-1.229 |
3702.857 |
3 |
.000 |
5.000 |
.000 |
5.037 |
13818.290 |
4 |
.000 |
-.583 |
.000 |
-3.532 |
993.111 |
5 |
.000 |
.550 |
.000 |
.139 |
2635.143 |
6 |
.000 |
.833 |
.000 |
.903 |
2124.127 |
7 |
.000 |
.500 |
.000 |
-4.252 |
13821.900 |
8 |
1.000 |
3.633 |
.000 |
-3.996 |
15475.360 |
9 |
.000 |
2.000 |
.000 |
.000 |
2.000 |
10 |
.000 |
-.833 |
1.000 |
-.903 |
1275.873 |
11 |
.000 |
.000 |
.000 |
1.000 |
2800.000 |
У табл. 9.2 наведено дані про розв’язок задачі (значення цільової функції, розмір випуску відповідного виду продукції, використання наявних запасів ресурсів). У табл. 9.3 міститься інформація про післяоптимізаційний аналіз, а в табл. 9.4 – числові значення останньої симплекс-таблиці.
247
Із табл. 9.2 бачимо, що відповідно до оптимального розв’язку, підприємство одержить максимальний прибуток у розмірі Z1=21634060 грн., при цьому випуск продукції відповідних видів буде: другого – x2=2124,128; третього – х3=3702,857; четвертого – х4=200,0; п’ятого – х5=2800,0. Перший вид продукції не випускається,
х1=0.
Виконаємо повний економіко-математичний аналіз одержаних розрахунків.
Позначимо через yi (i =1,n) – значення двоїстих оцінок. Числові значення їх для нашого прикладу наведено в другій частині табл. 9.8:
y2 |
= y3 = y4 = y6 |
= y7 = y9 ; y1 =17,4603; |
y5 |
=1277,778; y8 |
= 316,6667; y10 = 291,5872. |
Проведемо аналіз одержаного розв’язку задачі із використанням основних властивостей двоїстих оцінок. Насамперед необхідно пам’ятати, що всі враховані ресурси та види продукції оцінюються в одиницях виміру цільової функції. Таким чином, оцінки yi дають можливість співставити різні затрати і результати та давати оцінку різних заходів з врахуванням їх впливу на критерій оптимальності. У розглянутому прикладі оцінки yi рівні тому приросту (зменшенню) прибутку, яке виникає внаслідок зміни в деяких границях наявності ресурсів та завдань з випуску продукції. Найвищу оцінку одержало свердлильне устаткування № 2. Введення у виробничий процес додатково однієї люд.-год. роботи цього устаткування може призвести до збільшення прибутку на 1277,778 грн., на окреслену величину прибуток зменшиться при вилученні однієї люд.-год.
Оцінка свердлильного устаткування № 1 є низькою – 17,4603 грн. Аналізуючи ці оцінки, бачимо, що доцільно розглянути питання про можливість заміни свердлильного устаткування № 1.
Двоїсті оцінки дають можливість встановити норми заміни ресурсів або видів продукції, тобто визначити співвідношення, на основі яких можна провести заміну один одного без зміни кінцевого результату (екстремального значення цільової функції).
Заміну ресурсів необхідно проводити у відношенні, оберненому відношенню їх оцінок. Так, у нашому прикладі норма заміни свердлильного устаткування №1 на №2 становить:
y5 : y1 =1277,778:17,2, тобто 1 люд.-год. свердлильного устаткування № 2 може замінити 73,2 люд.-год. устаткування № 1.
248
Якщо виробничі та технологічні умови, пов’язані з випуском продукції, дають можливість провести таку заміну, то їх економічну ефективність можна визначити з допомогою двоїстих оцінок. Припустимо, що затрати на заміну 1 люд.-год. свердлильного устаткування № 1 устаткуванням № 2 на підприємстві складає 3500 грн. Ці затрати необхідно порівняти із додатковим ефектом, тобто із їх різницею оцінок (1277,778 –17,4603=1260,3177 грн. на 1 люд.-год.).
Тоді термін окупності затрат буде становити (3500:1260,3177=2,8) майже 3 роки. Аналіз показує, що затрати швидко окупляться, тому цей захід необхідно включити в число ефективних напрямків використання капітальних вкладень.
Відомо, що із збільшенням значення двоїстої оцінки ефективнішим або дефіцитнішим стає ресурс, тобто більш виправданими є заходи та затрати на збільшення його обсягів. Якщо оцінка відповідного ресурсу приймає нульове значення, то це означає, що описуваний ресурс є в залишку.
Обсяг залишку ресурсу наводиться в табл. 9.8 у стовпці «додаткові змінні». Так, у нашому прикладі залишок токарного устаткування становить 993,111 люд.-год., а фрезерного – 13818,29 люд.-год.
Оцінка обмеження з випуску четвертого виду продукції показує (y8 = 316,6667), наскільки необхідно підвищити ціну (або знизити
собівартість), щоб її випуск, згідно з укладеним договором, був ефективним.
Наведені вище висновки мають місце в межах стійкості базисного розв’язку (табл. 9.3), що пов’язано з поняттям коефіцієнтів заміщення останньої симплекс-таблиці. Ці коефіцієнти одержують з допомогою команди TABL і дають можливість провести економічний аналіз у певних напрямках.
Перший напрямок стосується вивчення стійкості оптимального розв’язку відносно зміни початкових запасів виробничих ресурсів, гарантованого обсягу виробництва та оцінок цільової функції. Цей аналіз ґрунтується на результатах, наведених у табл. 9.9. Так, наприклад, базисний розв’язок плану зберігається при зменшенні запасу свердлильного устаткування №1 на 3494,781 люд.-год. або збільшенні його на 5818,261 люд.-год. Для повністю невикористаних ресурсів границі можливого збільшення не вказуються. У табл. 9.9 наведені параметри стійкості базисного розв’язку стосовно коефіцієнтів цільової функції.
249
Другий напрямок відноситься до знаходження нової структури розв’язку при зміні або обсягів виробничих ресурсів, або обсягів гарантованого виробництва продукції, або включення в розв’язок невідомих величин, що не ввійшли в базисний розв’язок.
Розглянемо вплив коефіцієнтів заміщення на базисний розв’язок у випадку збільшення запасів виробничих ресурсів. Якщо ресурс використано повністю, то додаткова невідома величина (залишок ресурсу) входить у число небазисних змінних і має нульове значення. Тобто в зазначеному випадку додаткова невідома величина, введена в
обмеження виду «≤», рівна нулю. Коефіцієнти заміщення показують, наскільки збільшиться, якщо вони додатні, і наскільки зменшиться, якщо вони від’ємні, значення відповідних базисних змінних при одиничному збільшенні початкового запасу ресурсу. При зменшенні
– навпаки. Наприклад, в нашому випадку залишок свердлильного устаткування №1 SLK2=0. Збільшимо початковий запас свердлильного устаткування №1 на 1 людино-год. Тоді на основі даних табл. 9.4 (стовпець SLK2) отримаємо, що випуск третього виду продукції збільшиться на 0,286, а другого зменшиться на 0,365, а четвертого та п’ятого залишиться незмінним. При цьому недовикористання токарного устаткування збільшиться на 0,256 люд.-год., а фрезерного – зменшиться на 1,171 люд.-год. і т.д. Прибуток підприємства зросте на 17,46 грн.
Розглянемо випадок, коли основна невідома величина не включена в базис. Це означає, що при окреслених умовах включення її в оптимальний план неефективне на величину відносної оцінки. При введенні в базис такої невідомої величини з одиничною інтенсивністю додатні коефіцієнти заміщення покажуть, наскільки зменшиться, а від’ємні – наскільки збільшаться відповідні базисні невідомі. Такою невідомою величиною в нашому прикладі є х1 .
Як видно з табл. 9.4, введення в базис х1 призведе до такої зміни розв’язку. Випуск продукції третього виду зменшиться на 0,6, другого зменшиться на 0,4, а четвертого і п’ятого залишиться без змін. У той же час недовикористання токарного і фрезерного обладнання зменшиться відповідно на 0,32 та 3,74 люд.- год., а прибуток зменшиться на 1520,0 грн.
Перейдемо до розгляду випадку, коли додаткова невідома величина не ввійшла в базис і введена в обмеження виду «≥». Це означає, що відповідна їй основна невідома величина ввійшла в базис в розмірі мінімального гарантованого обсягу виробництва і далі її
250