ii) Найдите наименьший невычеркнутый элемент и вычтите его из остальных невычеркнутых элементов и прибавьте к элементам, стоящим на пересечении проведенных на предыдущем этапе прямых.
iii) Если новое распределение нулевых элементов не позволяет построить допустимое решение, повторите этап 2.1. В противном случае перейдите к третьему этапу алгоритма.
В задаче данного примера выполнение этапа 2.1 требует проведения трех прямых и приводит к табл. 5.38.
Таблица 5.38
Виды работ 3
Дети
Наименьший невычеркнутый элемент (он подчеркнут) равен 1. Этот элемент вычитаем из остальных невычеркнутых элементов и прибавляем к элементам, стоящим на пересечении прямых. В результате получим матрицу, представленную в виде табл. 5.39.
Таблица 5.39
Оптимальное решение, показанное в таблице подчеркнутыми нулями, предлагает первому ребенку работу 1, второму - работу 3, третьему - работу 2 и четвертому - работу 4. Соответствующее значение целевой функции равно 1 + 10+ 5+ 5 = 21 долл. Такое же значение можно получить путем суммирования значений pt и q. и значения элемента, наименьшего среди всех невычеркнутых: (1 + 7 + 4 + 5) + (0 + 0 + 3 + 0) + (1) = 21 долл.
УПРАЖНЕНИЯ 5.4
1. Решите задачи о назначениях, представленные в табл. 5.40.
Таблица 5.40
a) Решите задачи венгерским методом.
b) С помощью программы TORA решите задачи как транспортные.
c) Запишите задачи как задачи ЛП и решите их с помощью программы TORA.
d) Решите задачи в Excel с помощью шаблона ch5SolverTransportation.xls.
e) Решите задачи с помощью программы LINGO.
2. Дана следующая задача распределения четырех рабочих по четырем видам работ. Различная квалификация рабочих обусловливает различную стоимость выполнения работ. Стоимость работ (долл.) приведена в табл. 5.41. Отметим, что первый рабочий не может выполнять работу 3, а третий - работу 4. Найдите оптимальное решение.
Таблица 5.41
3. Пусть в задаче из предыдущего упражнения можно ввести нового (пятого) рабочего, способного выполнить любой вид работ со стоимостью соответственно 60, 45, 30 и 80 долл. Будет ли экономически выгодным заменить одного из "работающих" рабочих новым?
4. Пусть в задаче из упражнения 2 необходимо ввести новый вид работы, который может выполнить любой из четырех рабочих, со стоимостью соответственно 20, 10, 20 и 80 долл. Будет ли новая работа более выгодной по сравнению с имеющимися?
5. Бизнесмен должен сделать четыре поездки туда и обратно из своего головного офиса в Далласе в филиал в Атланте (данные о поездках приведены в табл. 5.42). Билет туда и обратно, т.е. Даллас-Атланта-Даллас, стоит 400 долл. Скидка 25% предоставляется тогда, когда даты отправления и прибытия совпадают с выходными днями (суббота и воскресенье). Если в билете между датами прибытия в Атланту и отправления из нее не менее 21 дня, то скидка увеличивается до 30%. Билет в одну сторону (в любом направлении) стоит 250 долл. Какую минимальную сумму может потратить на билеты бизнесмен?
Таблица 5.42
Дата отправления из Далласа Дата возвращения в Даллас Понедельник, 3 июня Пятница, 7 июня
Понедельник, 10 июня Среда, 12 июня
Понедельник, 17 июня Пятница, 21 июня
Вторник, 25 июня Пятница, 28 июня
6. На рис. 5.8 схематически показан план обрабатывающего цеха с четырьмя старыми станками, обозначенными квадратиками с номерами от 1 до 4. В цех будут
поставлены четыре новых станка, местоположение которых обозначено кружочками с буквами а, Ь, с и d. Необходимо так разместить новые станки, чтобы минимизировать суммарные перемещения обрабатываемых деталей между новыми и старыми станками. В табл. 5.43 показана интенсивность перемещения деталей между новыми и старыми станками. Детали перемещаются по сторонам прямоугольника, противоположными вершинами которого будут старый и новый станки. Например, расстояние (в метрах) между станком 1 и станком, расположенным в позиции Ь, равно 30 + 20 = 50 м.
О 10 20 30 40 50 60 70 80 Рис. 5.8. Расположение станков в задаче упражнения 6
Таблица 5.43
Старые станки
Новые станки 2 3
5.4.2. Интерпретация венгерского метода как симплекс-метода
Задачу о назначении п работников на п видов работ можно представить в виде задачи линейного программирования следующим образом. Обозначим через с(/ стоимость назначения работника i на работу у и определим
1, если работник / назначен на работу у, 0, в противном случае.