WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМіжнародні відносини, Міжнародна економіка → Методи розв'язання задач про призначення (лабораторна) - Реферат

Методи розв'язання задач про призначення (лабораторна) - Реферат


Лабораторна робота
з Теорії прийняття рішень
на тему:
"Методи розв язання задач про призначення"
Угорський алгоритм
Нехай множина А - іноземні корпорації, які продають автозапчастини українським партнерам, множина В - види автозапчастин, а елементи матриці мито (в млн. доларів), яке має бути виплачено при ввозі запчастин на Україну.
Завдання - знайти шлях, при якому мито буде найменшим.
В1 В2 В3 В4
А1 7 4 3 10
А2 9 5 9 4
А3 3 1 3 7
А4 6 8 5 4
В1 В2 В3 В4
А1
4 3 0 6
А2 6 4 6 0
А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
та додаємо до всіх елементів закреслених рядків:
В1 В2 В3 В4
А1 4 3 0 8
А2
4 2 4 0
А3
0 0 0 5
А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
та додаємо до всіх елементів закреслених рядків:
В1 В2 В3 В4
А1 3 2 0 8
А2
3 1 4 0
А3
0 0 0 6
А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
Розраховуємо прибуток:
А: Затрати на однудеталь:3040+2050+4230+2255+70 = 72,95
Прибуток за одну деталь: 120 - 72,95 = 47,05
В: Затрати на одну деталь: 3015+2025+4221+2211+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 грошових одиниць.
Loading...

 
 

Цікаве