Алгоритм венгерского метода в предыдущем примере завершен успешно, поскольку нулевые элементы в конечной матрице соответствуют допустимому решению (в том смысле, что каждому ребенку назначена в точности одна работа). В некоторых случаях нулевые элементы, полученные на первом и втором этапах венгерского метода, не позволяют непосредственно получить допустимое решение. Тогда необходимы дополнительные действия. Следующий пример демонстрирует это.

Пример 5.4.2

Предположим, что в примере 5.4.1 представлено четыре ребенка и четыре вида работ. Таблица 5.36 соответствует матрице стоимостей для этой задачи (данные представлены в долл.).

Таблица 5.36

Применение первого и второго этапов алгоритма к исходной матрице (при этом рх =1, рг = 7, р3 = 4, р4 = 5, <?, = 0, q2 = 0, <?3 = 3 и <?4 = 0) приводит к следующей матрице (проверьте!).

Таблица 5.37

Виды работ 2 3

Дети

В последней матрице расположение нулевых элементов не позволяет назначить каждому ребенку одну работу. Например, если мы назначим первому ребенку работу 1, из дальнейшего рассмотрения исключается первый столбец, и тогда в строке третьего ребенка не окажется нулевых элементов. Подобные проблемы можно разрешить, добавив к описанной в примере 5.4.1 процедуре следующий этап.

Этап 2.1. Если после выполнения первого и второго этапов описанного алгоритма не получено допустимое решение, выполните следующие действия.

i) В последней матрице проведите минимальное число горизонтальных и вертикальных прямых по строкам и столбцам, чтобы вычеркнуть в матрице все нулевые элементы.

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. В цех будут