Методи розв\’язання задач про призначення (лабораторна)

Лабораторна робота

з Теорії прийняття рішень

на тему:

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

Угорський алгоритм

Нехай множина А – іноземні корпорації, які продають автозапчастини
українським партнерам, множина В – види автозапчастин, а елементи
матриці мито (в млн. доларів), яке має бути виплачено при ввозі
запчастин на Україну.

Завдання – знайти шлях, при якому мито буде найменшим.

А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
грошових одиниць.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *