Пример №29.
Решим ЗН с матрицей затрат, заданной в табл. 7.4.
Шаг 1. Определяем допустимое решение двойственной задачи.
Шаг 2. Вычисляем
Результаты расчетов приведены в табл. 7.5.
Шаг 3. Решим задачу о наибольшем паросочетании, считая допустимыми клетки с нулями. Ход решения задачи отражен в табл. 7.6.
Число дуг в наибольшем паросочетании равно 5. Непомеченные строки 1, 2 4, 5 и помеченный столбец 2 образуют минимальное покрывающее множество рядов.
Шаг 4. Прочеркнем в матрице затрат непомеченные строки и помеченный столбец (см. табл. 7.5). Минимальный элемент h в оставшейся части матрицы равен 1 (все такие минимальные элементы в табл. 7.5 показаны жирным курсивом).
Шаг 5. Пересчитаем значения двойственных переменных.
Остальные двойственные переменные остаются без изменения.
Вычтем 1 из всех непрочеркнутых элементов табл. 7.5 и прибавим к дважды прочеркнутым элементам (табл. 7.7).
Шаг 6. Решим задачу о наибольшем паросочетании, считая допустимыми клетки с нулями (табл. 7.8).
Увеличивающая цепь: (6, 3), (1, 3), (1, 6). Жирным шрифтом выделено ребро (1,3), принадлежащее паросочетанию. Включаем в паросочетание ребра (6, 3) и (1, 6), исключаем из паро-сочетания ребро (1,3) (см. табл. 7.8). Теперь в паросочетание входят шесть ребер, оно — наибольшее. Полагаем
Первый рабочий получает шестую работу, второй — первую, третий — вторую, четвертый — четвертую, пятый — пятую, шестой — третью. Минимальные затраты равны:
Для контроля вычислим значение целевой функции двойственной задачи. На оптимальных решениях значения целевых функций должны совпасть (первая теорема двойственности).
Описываемый алгоритм решения ЗН был предложен американским математиком Куном (1955 г.), который назвал его венгерским, в честь венгерских математиков, на работах которых он основывался.
Эта задача взята со страницы решения задач по предмету «линейное программирование»:
Решение задач по линейному программированию
Возможно эти страницы вам будут полезны:
