<<
>>

6.3. Пример решения транспортной задачи венгерским методом

Задача 3

Найти оптимальный вариант назначений, если матрица производительности имеет следующий вид:

Ниже приводится цепочка матриц, получаемых в процессе решения задачи, с соответствующими пометками.

Снятие знака выделения «+» отмечено заключением его в рамку. Цепочка на этапе 2 отмечается стрелками.

Оптимальный вариант назначений х11 = х24 = х35 = х43 = х52 = 1, остальные Хij = 0, т. е. первый исполнитель назначается на первую работу, второй — на четвертую, третий — на пятую, четвертый — на третью, пятый — на вторую. Соответствующая ему суммарная производительность 4 + 4 + 4 + 6 + 4 = 22.

Пояснения к решению задачи.

Процесс нахождения оптимального варианта назначений состоит из предварительного этапа и двух итераций.

Предварительный этап

На этом этапе осуществляются два последовательных преобразования матрицы С. Сначала находится максимальный элемент в каждом столбце: в первом столбце максимальный элемент равен 5, во втором — 4, в третьем — 6, в четвертом — 5, в пятом — 5. Из максимального элемента вычитаются элементы этого столбца. Получается неотрицательная матрица, в каждом столбце которой есть хотя бы один нуль. Затем из каждой строки полученной матрицы вычитаем минимальный элемент этой строки. В результате подготовительного этапа Осуществлен переход к неотрицательной матрице, в каждом столбце и каждой строке которой имеется хотя бы один нуль.

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

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

Итерация 1

Этап 1

Выделяем знаком «+» первый, второй и пятый столбцы матрицы, содержащие нули со звездочкой. Просматриваем невыделенные нули матрицы, начиная с третьего столбца. Отмечаем штрихом нуль этого столбца, расположенный в четвертой строке. Поскольку в этой строке имеется 0*, то строка подлежит выделению (ставим знак «+» справа, от четвертой строки). Одновременно уничтожается (обводится рамкой) знак выделения над первым столбцом, содержащим 0* в четвертой строке (случай (а)).

Далее, отмечаем штрихом нуль, расположенный в четвертом столбце и во второй строке. Поскольку во второй строке имеется О* во втором столбце, то выделяем вторую строку и снимаем знак выделения над вторым столбцом. Так как во втором столбце имеются невыделенные нули, отмечаем нуль этого столбца, расположенный в пятой строке. Пятая строка матрицы не содержит О*. Следовательно, имеет место случай (б) (исход IA), т. е. необходим переход к этапу 2.

Этап 2

Строим цепочку. От последнего нуля со штрихом (пятая строка, второй столбец) движемся по столбцу к нулю со звездочкой (второй столбец, вторая строка), затем от 0* — к 0', расположенному в этой же строке в четвертом столбце. Поскольку в четвертом столбце матрицы нет 0*, процесс образования цепочки закончен. Искомая цепочка состоит из элементов: 0'52, 0*22, 0'24. Для завершения этапа 2, а вместе с ним и первой итерации, необходимо поставить звездочки над нулями цепочки, отмеченными штрихами, уничтожить звездочку над единственным четным элементом цепочки и стереть все знаки выделения. В результате итерации / число независимых нулей увеличилось на единицу и стало равно 4.

Итерация 2

Этап 1

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

Единственный нуль в невыделенном (третьем) столбце расположен в четвертой строке, в которой имеется.0*. Следовательно, выделяем четвертую строку и уничтожаем знак выделения над первым столбцом (случай (а)). После этого все нулевые элементы матрицы оказываются выделенными (исход IB), поэтому завершаем этап 1 и переходим к этапу 3.

Этап 2

Минимальным из числа невыделенных элементов матрицы является единица. Поэтому из всех элементов невыделенных строк (первой, второй, третьей, пятой) вычитаем h = 1, а к элементам выделенных столбцов (второго, четвертого, пятого) прибавляем h = 1. Получается матрица, эквивалентная предыдущей и содержащая незанятые нули. Переносим все знаки выделения (+,*,') с предыдущей матрицы, кроме знаков, обведенных рамкой, и переходим к этапу 1.

Этап 3

Отмечаем штрихом невыделенный нуль первого столбца первой строки, так как в первой строке имеется 0* в пятом столбце, выделяем первую строку и снимаем знак выделения над пятым столбцом. В пятом столбце имеется невыделенный нуль, расположенный в третьей строке, отмечаем его штрихом. Поскольку в третьей строке нет нулей со звездочкой (случай (б)), переходим к этапу 2.

Этап 4

Строим цепочку. От последнего 0' (третья строка, пятый столбец) движемся по столбцу до 0*, расположенного на пересечении первой строки и пятого столбца, далее от 0* — к 0', находящемуся в этой же строке в первом столбце, затем по первому столбцу к 0* (четвертая строка, первый столбец) и по строке 4 к 0', расположенному в третьем столбце. Так как в третьем столбце нет 0*, процесс образования цепочки закончен. Искомая цепочка состоит из элементов: 0'35, 0*15, 0'11, 0*4], 0'43. Снимаем звездочки у нулей из цепочки и заменяем звездочками штрихи у нулей из цепочки. В результате второй итерации число независимых нулей увеличилось на единицу и стало равно 5, поэтому процесс решения задачи закончен.

<< | >>
Источник: С.И.Дмитриева. Управление денежными, материальнымии информационными потоками .УЧЕБНОЕ ПОСОБИЕПрактически задачи, примеры решения,варианты для самостоятельной работы, тесты. 2009

Еще по теме 6.3. Пример решения транспортной задачи венгерским методом:

  1. Примеры решения задачпо оценке наземных транспортных средств
  2. Примеры решения задач
  3. Пример решения ситуационной задачи
  4. Примеры решения задач
  5. Примеры решения задач
  6. Примеры решения задач
  7. Примеры решения задач
  8. Примеры решения задач
  9. Примеры решения задач
  10. Примеры решения задач
  11. Примеры решения задач
  12. Примеры решения задач
  13. Примеры решения задач
- Бюджетная система - Внешнеэкономическая деятельность - Государственное регулирование экономики - Инновационная экономика - Институциональная экономика - Институциональная экономическая теория - Информационные системы в экономике - Информационные технологии в экономике - История мировой экономики - История экономических учений - Кризисная экономика - Логистика - Макроэкономика (учебник) - Математические методы и моделирование в экономике - Международные экономические отношения - Микроэкономика - Мировая экономика - Налоги и налолгообложение - Основы коммерческой деятельности - Отраслевая экономика - Оценочная деятельность - Планирование и контроль на предприятии - Политэкономия - Региональная и национальная экономика - Российская экономика - Системы технологий - Страхование - Товароведение - Торговое дело - Философия экономики - Финансовое планирование и прогнозирование - Ценообразование - Экономика зарубежных стран - Экономика и управление народным хозяйством - Экономика машиностроения - Экономика общественного сектора - Экономика отраслевых рынков - Экономика полезных ископаемых - Экономика предприятий - Экономика природных ресурсов - Экономика природопользования - Экономика сельского хозяйства - Экономика таможенного дел - Экономика транспорта - Экономика труда - Экономика туризма - Экономическая история - Экономическая публицистика - Экономическая социология - Экономическая статистика - Экономическая теория - Экономический анализ - Эффективность производства -