Головна Головна -> Інше українською -> Економічні теми -> Методи розвязання задач про призначення

Методи розвязання задач про призначення

Назва:
Методи розвязання задач про призначення
Тип:
Інше
Мова:
Українська
Розмiр:
1,62 KB
Завантажень:
435
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Лабораторна робота
з Теорії прийняття рішень
на тему:
“Методи розвязання задач про призначення”


Угорський алгоритм
Нехай множина А – іноземні корпорації, які продають автозапчастини українським партнерам, множина В – види автозапчастин, а елементи матриці мито (в млн. доларів), яке має бути виплачено при ввозі запчастин на Україну.
Завдання – знайти шлях, при якому мито буде найменшим. |
В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
Розраховуємо прибуток:
А: Затрати на одну деталь: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 грошових одиниць.

Завантажити цю роботу безкоштовно



Інше на тему: Методи розвязання задач про призначення

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок