шая их как систему линейных уравнений (после присвоения какой-либо переменной произвольного значения, например и, = 0), находим значения потенциалов и, и i>y. Вычислив значения потенциалов, далее определяем вводимую в базис переменную среди всех небазисных как переменную, имеющую наибольшее положительное значение величины и, + и - с1}.

Присвоение одной из двойственных переменных произвольного значения (например, и, = 0) противоречит представлениям раздела 4.2.3, поскольку это присвоение показывает, что, возможно, решение двойственной задачи (определяется вычисленными значениями двойственных переменных (потенциа-лов)) не единственное. В действительности противоречия здесь нет, и решение упражнения 5.3.3.2 объясняет, - почему.

УПРАЖНЕНИЯ 5.3.3

1. Запишите двойственную задачу для транспортной модели из примера 5.3.5 (см. табл. 5.21). Вычислите оптимальное значение целевой функции двойственной задачи с помощью значений двойственных переменных, приведенных в табл. 5.25, и покажите, что найденное значение совпадает с оптимальным значением целевой функции транспортной задачи.

2. В транспортной модели одной из двойственных переменных присваивается произвольное значение. Это означает, что одному и тому же базисному решению прямой задачи соответствует не единственный набор значений двойственных переменных. Это противоречит положениям теории линейного программирования, где значения двойственных переменных вычисляются как произведение вектора коэффициентов целевой функции, стоящих при базисных переменных, на обратную матрицу соответствующего базиса (см. метод 1 из раздела 4.2.3). Покажите, что в транспортной модели обратная матрица всегда определяется однозначно, в то время как вектор коэффициентов целевой функции, стоящих при базисных переменных, можно определить не единственным образом. В частности, покажите, что если коэффициенты ctj заменить на сц + к для всех i и у, где к - произвольная константа, то оптимальные значения переменных хц не изменятся. Покажите, что присвоение одной двойственной переменной произвольного значения эквивалентно прибавлению к коэффициентам ctj некой константы к.

5.4. ЗАДАЧА О НАЗНАЧЕНИЯХ

Лучший работник для выполнения данной работы - вот подходящее краткое описание задачи о назначениях. В этой задаче необходимо назначить работников на определенные работы; каждый работник может выполнять любую работу, хотя и с различной степенью мастерства. Если на некоторую работу назначается работник именно той квалификации, которая необходима для ее выполнения, тогда стоимость выполнения работы будет ниже, чем при назначении на данную работу работника неподходящей квалификации. Цель задачи - найти оптимальное (минимальной стоимости) распределение работников по всем заявленным работам.

Общая задача назначения п работников на п работ представлена в табл. 5.31. Таблица 5.31

Коэффициент сц равен стоимости назначения работника i на работу j (i,j= 1, 2, n). То, что количество работников равно количеству работ, не является ограничением общности, поскольку всегда можно ввести в модель фиктивных работников или фиктивные работы.

Задача о назначениях является частным случаем транспортной задачи, в которой работники соответствуют пунктам отправления, а работы - пунктам назначения. В данном случае все величины спроса и предложения равны 1. Стоимость транспортировки рабочего i на работу равна cv. Задачу о назначениях можно эффективно решить точно так же, как и транспортную задачу. Вместе с тем тот факт, что все величины спроса и предложения равны 1, привел к разработке упрощенного алгоритма решения, названного венгерским методом. Хотя этот метод не имеет никакого отношения к транспортной задаче, он, как и метод потенциалов, все равно основан на симплекс-методе.

5.4.1. Венгерский метод7

Для представления этого метода используем два примера. Интерпретация венгерского метода как симплекс-метода будет рассмотрена в следующем разделе.

Пример 5.4.1

Трое детей Джоя Клини - Джон, Карен и Терри - желают подзаработать немного денег на школьную экскурсию в местный зоопарк. М-р Клини выбрал три вида работ, которые дети выполнить могут за определенную плату: стрижка газона, уборка гаража и мойка семейного автомобиля. Чтобы избежать ненужных споров между детьми, он опросил каждого (конечно, по секрету), сколько за каждый вид работ они хотят получить. Результаты опроса (в долл.) представлены в табл. 5.32.

Таблица 5.32

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

Основываясь на этой информации, как распределить работы между детьми с минимальными (денежными) потерями для м-ра Клини?

Решим эту задачу о назначениях венгерским методом.

Этап 1. В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки.

Этап 2. В матрице, полученной на первом этапе, найдем в каждом столбце минимальную стоимость и отнимем ее от других элементов столбца.

Этап 3. Оптимальным назначениям будут соответствовать нулевые элементы, полученные на предыдущем этапе.

Обозначим через pt и qt минимальные стоимости соответственно в строке / и столбце у, определенные на первом и втором этапах описанного выше алгоритма. Минимальные стоимости по строкам находятся по исходной матрице стоимостей, как показано в табл. 5.33.

Таблица 5.33

Стрижка газона Уборка гаража Мойка машины Минимумы по строкам

Теперь вычтем минимальные стоимости из элементов соответствующих строк, и в результате получим следующую матрицу.

Таблица 5.34

На втором этапе алгоритма находим минимальные значения по столбцам и вычитаем их из элементов соответствующих столбцов. В результате получим матрицу, представленную в виде табл. 5.35.

Таблица 5.35

В последней матрице подчеркнутые нулевые элементы определяют оптимальное решение: Джон будет убирать в гараже, Карен подстригать газон, а Терри достанется мойка машины. Эти работы обойдутся м-ру Клини в 9 + 10 + 8 = 27 долл. Отметим, что эта сумма всегда равна (р, + р2 + р3) + (<?, + q2 + q3) = (9 + 9 + 8) + + (0 + 1 + 0) = 27 долл. (Доказательство этого приведено в следующем разделе.)