Варіанти завдань для самостійного розв’язання задачі №5

Потрібно від підприємств-постачальників 1, 2, 3 доставити до підприємств-споживачів 1, 2, 3 і 4 певну кількість вантажу. В табл. 5.11 показані можливості пропозиції постачаючих підприємств і попит споживаючих підприємств, а також вартість c_іj в умовних одиницях перевезення тонни вантажу від i-го постачальника до j-го споживача.

Необхідно визначити об’єми перевезень x_ij між i-м постачальником і j-м споживачем, що забезпечує мінімальну вартість.

Таблиця 5.11

Вартість перевезення вантажу від постачальників до споживачів

Підприємства-постачальники	Підприємства-споживачі								Пропозиція, т
	1		2		3		4
1		c11		c12		c13		c14	a1
	x11		x12		x13		x14
2		c21		c22		c23		c24	a2
	x21		x22		x23		x24
3		c31		c32		c33		c34	a3
	x31		x32		x33		x34
Попит, т	b1		b2		b3		b4

Чисельні значення коефіцієнтів с₁₁, c₁₂, c₁₃, c₁₄, c₂₁, c₂₂, c₂₃, c₂₄, с₃₁, c₃₂, c₃₃, c₃₄, a₁, a₂, а₃, b₁, b₂, b₃, b₄ визначаються відповідно до варіанта (номер за списком) за табл. 5.12.

Таблиця 5.12

Вихідні дані для розв’язання транспортної задачі

№ вар.	Коефіцієнти в математичній моделі задачі
	с11	c12	c13	c14	c21	c22	c23	c24	с31	c32	c33	c34	a1	a2	a3	b1	b2	b3	b4
1	10	20	30	40	50	60	70	80	90	100	110	120	10	150	50	10	100	20	80
2	20	30	40	50	60	70	80	90	100	110	120	10	20	140	60	20	90	40	70
3	30	40	50	60	70	80	90	100	110	120	10	20	30	130	70	30	80	60	60
4	40	50	60	70	80	90	100	110	120	10	20	30	40	120	80	40	70	80	50
5	50	60	70	80	90	100	110	120	10	20	30	40	50	110	90	50	60	100	40
6	60	70	80	90	100	110	120	10	20	30	40	50	60	100	100	60	50	90	60
7	70	80	90	100	110	120	10	20	30	40	50	60	70	90	150	70	40	70	130
8	80	90	100	110	120	10	20	30	40	50	60	70	80	80	140	80	30	50	140
9	90	100	110	120	10	20	30	40	50	60	70	80	90	70	130	90	20	30	150
10	100	110	120	10	20	30	40	50	60	70	80	90	100	60	120	100	10	10	160
11	110	120	10	20	30	40	50	60	70	80	90	100	110	50	110	110	30	20	110
12	120	10	20	30	40	50	60	70	80	90	100	110	120	40	10	100	50	10	10
13	10	20	30	40	50	60	70	80	90	100	110	120	130	30	20	90	30	40	20
14	20	30	40	50	60	70	80	90	100	110	120	130	140	20	30	80	20	50	40
15	30	40	50	60	70	80	90	100	110	120	130	10	150	10	40	70	50	60	20
16	40	50	60	70	80	90	100	110	120	130	10	20	10	140	20	10	40	70	50
17	50	60	70	80	90	100	110	120	130	10	20	30	20	130	40	20	30	80	60
18	60	70	80	90	100	110	120	130	10	20	30	40	30	120	60	30	40	90	50
19	70	80	90	100	110	120	130	10	20	30	40	50	40	110	80	40	10	100	80
20	80	90	100	110	120	130	10	20	30	40	50	60	50	100	100	50	20	90	90
21	90	100	110	120	130	10	20	30	40	50	60	70	60	90	120	60	30	80	100
22	100	110	120	130	10	20	30	40	50	60	70	80	70	80	140	70	40	70	110
23	110	120	130	10	20	30	40	50	60	70	80	90	80	70	50	80	50	60	10
24	120	130	10	20	30	40	50	60	70	80	90	100	90	60	70	90	60	50	20
25	130	120	110	100	90	80	70	60	50	40	30	20	100	50	90	100	70	40	30

Питання для експрес-контролю якості засвоєння знань до задачі №5.

1. До якого класу задач відноситься транспортна задача, в чому їх особливість?

2. У якому випадку транспортна задача вважається закритою, а в якому – відкритою?

3. Як виглядає цільова функція транспортної задачі?

4. Які обмеження вводяться в транспортній задачі?

5. Що в транспортній задачі позначається змінними x_ij?

6. Чи можуть змінні в транспортній задачі бути від'ємними або дробовими?

7. Яким методом знаходиться допустиме рішення транспортної задачі, в чому він полягає?

8. Яким методом знаходиться оптимальне рішення транспортної задачі, в чому він полягає?

9. Як визначити, що отримане рішення транспортної задачі є оптимальним?

10. Де в авіаційній галузі знаходить прикладне застосування транспортна задача?

Аналітично-розрахункова задача №6

Оптимальний розподіл людських ресурсів авіаційного підприємства

І. Вихідні дані

В авіакомпанії організується фінансово-економічний відділ і необхідно розподілити працівників за вакантними посадами. Кожний працівник може виконувати будь-яку роботу, але з різним ступенем майстерності. Якщо на певну посаду призначити працівника саме тої кваліфікації, яка необхідна для роботи на ній, то вартість виконання роботи буде нижча, ніж при призначенні на дану посаду працівника невідповідної кваліфікації.

Компетентна комісія оцінила витрати, пов’язані з майбутнім розподілом працівників. В табл. 6.1 наводяться умовні оцінки вартості c_іj призначення i-го працівника на j-ту посаду. Змінна x_ij =1 у випадку призначення i-го працівника на j-ту посаду, або x_ij =0 – в іншому випадку.

Вам, як менеджеру з персоналу, доручено знайти оптимальний розподіл працівників за всіма посадами, що забезпечує мінімальну вартість виконання робіт.

ІІ. Завдання до ситуації

1. Використовуючи дані табл. 6.1, знайдіть оптимальний розподіл працівників за всіма посадами венгерським методом.

2. Розрахуйте сумарну вартість виконання робіт для визначеного оптимального варіанта розподілу працівників.

ІІІ. Інформаційне забезпечення задачі

Таблиця 6.1

Оцінки вартості призначення працівників на певні посади

Працівники	Посади
	Економіст		Бухгалтер		Касир		Менеджер
Іванов І.П.	x11	10	x12	40	x13	60	x14	30
Петров С.М.	x21	90	x22	70	x23	100	x24	90
Сидоров В.Н.	x31	40	x32	50	x33	110	x34	70
Федотов Р.Д.	x41	80	x42	70	x43	80	x44	50

ІV. Алгоритм розв’язання задачі

1. Задача про призначення персоналу є приватним випадком транспортної задачі, в якій число пунктів відправлення дорівнює числу пунктів призначення, тобто, транспортна таблиця має форму квадрата. Крім того, у кожному пункті призначення обсяг попиту дорівнює 1, і величина пропозиції кожного пункту відправлення також дорівнює 1. Задача про призначення персоналу може бути розв'язана з використанням методів лінійного програмування або алгоритму рішення транспортної задачі. Однак через особливу структуру даної задачі був розроблений спеціальний алгоритм, що одержав назву угорського методу.

Математична модель задачі про призначення персоналу:

- цільова функція:

L =  min, n = m; (6.1)

- обмеження:

= 1, ;

= 1, ; (6.2)

, ;

x_ij ≥ 0, .

Для прикладу маємо наступну модель:

L = 10x₁₁ + 40x₁₂ + 60x₁₃ + 30x₁₄ + 90x₂₁ + 70x₂₂ + 100x₂₃ + 90x₂₄ + 40x₃₁ + + 50x₃₂ + 110x₃₃ + 70x₃₄ + 80x₄₁ + 70x₄₂ + 80x₄₃ + 50x₄₄ min; (6.3)

x ₁₁ + x₁₂ + x₁₃ + x₁₄ = 1;

x₂₁ + x₂₂ + x₂₃ + x₂₄ = 1;

x₃₁ + x₃₂ + x₃₃ + x₃₄ = 1;

x₄₁ + x₄₂ + x₄₃ + x₄₄ = 1; (6.4)

x₁₁ + x₂₁ + x₃₁ + x₄₁ = 1;

x₁₂ + x₂₂ + x₃₂ + x₄₂ = 1;

x₁₃ + x₂₃ + x₃₃ + x₄₃ = 1;

x₁₄ + x₂₄ + x₃₄ + x₄₄ = 1;

x11 ≥ 0; x12 ≥ 0; x13 ≥ 0; x14 ≥ 0;

x21 ≥ 0; x22 ≥ 0; x23 ≥ 0; x24 ≥ 0;

x31 ≥ 0; x32 ≥ 0; x33 ≥ 0; x34 ≥ 0;

x41 ≥ 0; x42 ≥ 0; x43 ≥ 0; x44 ≥ 0.

2. Знаходимо в кожній строчці мінімальний елемент і віднімаємо його від кожного елементу строчки (табл. 6.2).

Таблиця 6.2

Знаходження мінімальних елементів в строчках та їх віднімання

Працівники	Посади
	Економіст		Бухгалтер		Касир		Менеджер		min
Іванов І.П.	x11	0	x12	30	x13	50	x14	20	10
Петров С.М.	x21	20	x22	0	x23	30	x24	20	70
Сидоров В.Н.	x31	0	x32	10	x33	70	x34	30	40
Федотов Р.Д.	x41	30	x42	20	x43	30	x44	0	50

3. Знаходимо в кожному стовпці мінімальний елемент і віднімаємо його від кожного елементу стовпця (табл. 6.3).

Таблиця 6.3

Знаходження мінімальних елементів в стовпцях та їх віднімання

Працівники	Посади
	Економіст			Бухгалтер		Касир		Менеджер
Іванов І.П.	x11	0		x12	30	x13	20	x14	20
Петров С.М.	x21	20		x22	0	x23	0	x24	20
Сидоров В.Н.	x31	0		x32	10	x33	40	x34	30
Федотов Р.Д.	x41	30		x42	20	x43	0	x44	0
min	0		0			30		0

3. Якщо в кожній строчці та кожному стовпці знаходиться один „0”, тобто, кожний працівник призначається тільки на одну посаду, то оптимальне рішення знайдене. В іншому випадку:

– проводимо мінімальне число прямих через строки та стовпці, щоб всі „0” були викресленими (табл. 6.4);

– обираємо мінімальний невикреслений елемент (=10), віднімаємо його від кожного невикресленого елементу і додаємо до кожного елементу, що стоїть на перетині проведених прямих (табл. 6.5).

Якщо на останньому кроці оптимальне рішення не знайдене, то процедуру проведення прямих необхідно повторювати до тих пір, поки не буде отримане допустиме рішення.

Таблиця 6.4