Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Прямо-двойственный метод решения задачи о назначениях

Задача о назначениях как транспортная задача.

Определим значения переменных следующим образом: , если назначается на должность , и в противном случае. Тогда функция соответствия имеет вид . Если матрицу соответствия заметить на матрицу несоответствия , где и - некоторая константа, то задача состоит в таком выборе должностей , чтобы цена несоответствия была минимальной. Таким образом, модель задачи о назначениях принимает вид:

(1)

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

Транспортная задача (1) может быть решена методом потенциалов, причем ее решение окажется, очевидно, целочисленным. Из вида ограничений в (1) следует, что для каждого ровно одна из целочисленных переменных равна 1, а остальные равны 0 (и аналогично для каждого ровно одна из целочисленных переменных равна 1, а остальные равны 0). Следовательно, число ненулевых переменных (число «заполненных» клеток в транспортной таблице) равно , в то время как ранг задачи (число базисных переменных) равен . Задача получается сильно вырожденной, и для ее решения методом потенциалов потребуется вводить в рассмотрение «базисных нулей», что осложняет решение.

Изложим теперь суть прямо-двойственного метода решения задачи (1). Также как и в методе потенциалов рассматриваются двойственные переменные и , удовлетворяющие ограничениям двойственной задачи:

. (2)

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

(3)

имеет место и служит для определения самих потенциалов, а в прямо-двойственном методе, наоборот, это условие служит для определения «заполненных» клеток транспортной таблицы, соответствующих ненулевым переменным . Таким образом, «ход мысли» здесь противоположен методу потенциалов.

Как было уже замечено выше, из условия следует, что, на самом деле, , причем в этом случае все остальные переменные в - ой строке и -ом столбце равны нулю. Будем для удобства называть такие «возможными единицами». Ясно, что выполнение ограничений задачи (1) равносильно существованию ровно возможных единиц. Хорошо известно, что допустимые решения исходной транспортной задачи (1) и соответствующей двойственной задачи будут оптимальны, если для всех выполнены условия 2-ой теоремы двойственности . Итак, оптимальное решение будет получено, если удастся отыскать ровно допустимых единиц, определяемых условием .

Прямо-двойственный метод именно это и позволяет сделать. Для простоты изложим его на конкретном примере.

<== предыдущая лекция | следующая лекция ==>
Определения и основные понятия | Пример решения задачи о назначениях
Поделиться с друзьями:


Дата добавления: 2014-01-05; Просмотров: 465; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.