Лабораторна робота
з Теорії прийняття рішень
на тему:
“Методи розв(язання задач про призначення”
Угорський алгоритм
Нехай множина А – іноземні корпорації, які продають автозапчастини
українським партнерам, множина В – види автозапчастин, а елементи
матриці мито (в млн. доларів), яке має бути виплачено при ввозі
запчастин на Україну.
Завдання – знайти шлях, при якому мито буде найменшим.
А3 0 0 0 3
А4 3 7 2 0
Серед не закреслених елементів знаходимо найменше (2), віднімаємо його
від усіх елементів не закреслених стовпчиків:
В1 В2 В3 В4
А1 2 1 -2 6
А2 4 2 4 0
А3 -2 -2 -2 3
А4 1 5 0 0
та додаємо до всіх елементів закреслених рядків:
А4 1 5 0 0
Серед не закреслених елементів знаходимо найменше (1), віднімаємо його
від усіх елементів не закреслених стовпчиків:
В1 В2 В3 В4
А1 3 2 0 8
А2 3 1 4 0
А3 -1 -1 0 5
А4 0 5 0 0
та додаємо до всіх елементів закреслених рядків:
А4 0 5 0 0
С = 3+4+1+6 = 14
Симплекс-метод:
Нехай на заводі автозапчастин виробляються два види деталей. Виробництво
здійснюється в 4 етапи, і на кожному етапі проводяться роботи для певної
кількості деталей певної запчастини. А,В – типи автозапчастин, С –
етапи.
А В Вартість години праці
С1 40 15 30
С2 50 25 20
С3 30 21 42
С4 55 11 22
Заготовки 70 90
Ціна 120 150
Розраховуємо прибуток:
А: Затрати на одну деталь:30\40+20\50+42\30+22\55+70 = 72,95
Прибуток за одну деталь: 120 – 72,95 = 47,05
В: Затрати на одну деталь: 30\15+20\25+42\21+22\11+90 = 96,8
Прибуток за одну деталь: 150-96,8 = 53,2
Для отримання максимального прибутку, за одну годину треба обробити Х1
деталей А та Х2 деталей В. Загальний прибуток обраховується за формулою:
z = 47,05Х1 +53,2 Х2
Будуємо систему:
X1 >=0
X2 >=0
z = 47,05X1 + 53,2X2
X1/40 +X2/15 >=1
X1/50 +X2/25 >=1
X1/30 +X2/21 >=1
X1/55 +X2/11 >=1
X1 >=0
X2 >=0
z = 47,05X1 + 53,2X2
15*X1 +40*X2 >=600
25*X1+50*X2 >=1250
21*X1 +30*X2 >=630
11*X1 +55*X2 >=605
X1 >=0
X2 >=0
z = 47,05X1 + 53,2X2
15*X1 +40*X2 +X3=600
25*X1+50*X2 +X4=1250
21*X1 +30*X2 +X5=630
11*X1 +55*X2 +X6=605
P1 P2 P3 P4 P5 P6 P0
P3 15 40 1 0 0 0 600
P4 25 50 0 1 0 0 1250
P5 21 30 0 0 1 0 630
P6 11 55 0 0 0 1 605
? 46,05 53,2
P1 P2 P3 P4 P5 P6 P0
P3 0,375 1 0,025 0 0 0 15
P4 0,5 1 0 0,02 0 0 25
P5 0,7 1 0 0 0,033 0 21
P6 0,2 1 0 0 0 0,018 11
?
P1 P2 P3 P4 P5 P6 P0
P3 7 0 1 0 0 -0,72 160
P4 15 0 0 1 0 -0,9 700
P5 15 0 0 0 1 -0,54 300
P2 0,2 1 0 0 0 0,018 11
? 36,41 0 0 0 0 -0,95 -585,2
Повторюємо алгоритм для стовпця з найбільшою дельтою:
P1 P2 P3 P4 P5 P6 P0
P3 1 0 0,14 0 0 -0,1 22,86
P4 1 0 0 0,067 0 -0,06 46,67
P5 1 0 0 0 0,067 -0,036 20
P2 1 5 0 0 0 0,09 55
P1 P2 P3 P4 P5 P6 P0
P3 0 0 1 0 -0,467 -0,468 20
P4 0 0 0 1 -1 -0,36 400
P1 1 0 0 0 0,067 -0,036 20
P2 0 1 0 0 -0,013 0,022 7
? 0 0 0 0 -2,423 -0,353 -1313,4
Так як немає додатних ?, то можна стверджувати, що
z = 47,05*20 + 53,2*7 = 1312,8
Для отримання максимального прибутку, за одну годину треба обробити 20
деталей А та 7 деталей В. Загальний прибуток буде становити 1312,8
грошових одиниць.
Нашли опечатку? Выделите и нажмите CTRL+Enter