7.3.3. Приклад

Згідно із замовленням треба обробити чотири деталі на чотирьох верстатах. Тривалість обробки (у хвилинах) кожної деталі на кожному верстаті наведено у матриці:

Деталі	Верстати
	1-й	2-й	3-й	4-й
1	10	65	40	5
2	20	35	15	5
3	10	45	60	45
4	30	15	10	30

Математична модель

Вибір

Розрахунок

Складання покриття з

Оптимальний розв’язок

=

Фіксація - рядків

без базисних нулів

<

Фіксація р – колонок з

вільними нулями в - рядках

Фіксація - рядків з базисними нулями в р – колонках

Побудова покриття з

та

Вибір з елементів

поза покриття

Розрахунок елементів

поза

перетин

Рис.7.4

Треба розподілити деталі між верстатами так, щоб тривалість обробки була мінімальною.

Виконаємо попереднє перетворення матриці: знайдемо по кожній колонці мінімальні елементи 10, 15,10, 5 та побудуємо наступну матрицю:

Деталі	Верстати
	1-й	2-й	3-й	4-й
1	0	50	30	0	1
2	10	20	5	0	5
3	0	30	50	40	4
4	2 0	0	0	25

2 3

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

Знаходимо мінімальне покриття:

• позначаються рядки, які не мають базисних нулів (1-й рядок);

• позначаються колонки, які мають вільні нулі у позначених рядках (1-ша та 4-та);

• позначаються рядки з базисними нулями у позначених колонках (2-й та 3-й).

На цьому позначення закінчується, оскільки в останніх позначених рядках немає вільних нулів. Послідовність позначення таблиці вказана стрілками. У таблиці означене покриття обведене жирною лінією.

Мінімальний елемент поза покриття . Після перетворення елементів складається нова таблиця:

Деталі	Верстати
	1-й	2-й	3-й	4-й
1	0	45	25
2	10	15		0
3		25	45	40
4	25		0	30

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

Оптимальна прив’язка пар: (1,4), (2,3), (3,1), (4,2), цільова функція .