Задача про призначення

Постановка задачі: на п'ятьох токарних верстатах різних типів виконуються п'ять різних технологічних операцій. Та сама операція може виконуватися тільки на одному верстаті. За кожним верстатом може бути закріплена тільки одна операція. Час виконання кожної з операцій на кожному з верстатів задано матрицею с_ij:

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

Розв’язання:

Нехай

1, якщо на i-м верстаті виконується j-я операція;

x_ij =

0, якщо на i-м верстаті не виконується j-я операція.

За умовою задачі за кожним верстатом закріплена тільки одна операція. Це виражається наступними рівностями:

Кожна операція може виконуватися тільки на одному верстаті:

Сформулюємо задачу про призначення в наступному вигляді:

знайти значення невідомих x_ij (i = 1...5…5; j=1…5), задовольняючій системі рівнянь і рівні 0 або 1, при яких функція

приймає мінімальне значення.

Розв’язання задачі проводимо за допомогою пакету програм MathCAD. Сумарні витрати часу будуть мінімальними, якщо на першому верстаті виконувати п'яту операцію, на другому верстаті - першу, на третьому - другу, на четвертому - четверту, на п'ятому - третю.

Список використаної літератури:

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология.- М.: Наука, Главная редакция физико-математической литературы, 1975.

2. Акулич И. Л. Математическое программирование в примерах и задачах. Учеб. пособие для студ. экономич. специальн. вузов. М.: Вища школа, 1986.

3. Конспект лекцій ДонІЗТ 2007.

4. Математические методы в планировании на железнодорожном транспорте. А.Б. Каплан, И.В. Белов. Транспорт 1972 г., 248с.

5. Сборник задач по математическому моделированию на железнодорожном транспорте. Учебное пособие для ВУЗов ж-д транспорта М., «Транспорт», 1978. 200 с. Авт.: А.Б. Каплан, А.Д. Майданов, Р.М. Царев.