Задача о назначениях реферат

Обновлено: 04.07.2024

Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план, не удовлетворяющий в общем случае всем условиям задачи. Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи. Цель работы – исследовать решение задач о назначениях. Задачи:
1. Рассмотреть теоретические основы задач о назначениях;,
2. Проанализировать Венгерский метод решения задачи о назначениях.

Содержание работы

Введение
1. Теоретические основы задач о назначениях
1.1 Задача о назначениях
1.2 Особые случаи задачи о назначениях
2. Венгерский метод решения задачи о назначениях
2.1 Сущность Венгерского метода
2.2 Описание алгоритма венгерского метода
2.3 Венгерский метод для транспортной задачи
2.4 Обоснование Венгерского метода
3. Алгоритм решения задачи назначениях
Заключение
Список литературы

Содержимое работы - 1 файл

Задача о назначениях.docx

1. Теоретические основы задач о назначениях

1.1 Задача о назначениях

1.2 Особые случаи задачи о назначениях

2. Венгерский метод решения задачи о назначениях

2.1 Сущность Венгерского метода

2.2 Описание алгоритма венгерского метода

2.3 Венгерский метод для транспортной задачи

2.4 Обоснование Венгерского метода

3. Алгоритм решения задачи назначениях

Задача о назначениях является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа.

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

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

В современных условиях развития каждое предприятие стремится с наименьшими затратами функционировать в сложившихся условиях с целью получения высоких доходов. Экономико-математические задачи о назначениях позволяют найти оптимальный вариант размещения одного кандидата на выполнение одной работы таким образом, чтобы минимизировать суммарные затраты по выполнению комплекса работ группой исполнителей. Также возможны некоторые модификации задачи о назначениях: во-первых, она иногда формулируется как задача максимизации (например, суммарного дохода от назначения всех исполнителей на работы); во-вторых, штатный состав организации может быть представлен большим количеством исполнителей, нежели количество работ, на которые должны быть назначены или, наоборот, большее количество работы, при недостаточном количестве исполнителей для ее выполнения; в-третьих, выполнение какой-либо работы по каким-либо причинам запрещается исполнять какому-либо работнику. В такой постановке данная задача относится к классу комбинаторных, решение которых путем прямого перебора невозможно при достаточно больших n, так как число вариантов назначений составляет n!. Данный программный продукт позволяет за короткий промежуток времени решать описанные модификации задачи о назначениях венгерским методом, с определением оптимального варианта размещения исполнителей по работам, исходя из поставленных условий. Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план, не удовлетворяющий в общем случае всем условиям задачи. Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи.

Цель работы – исследовать решение задач о назначениях.

1. Рассмотреть теоретические основы задач о назначениях;

2. Проанализировать Венгерский метод решения задачи о назначениях.

Глава 1. Теоретические основы задач о назначениях

1.1 Задача о назначениях

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

1.2 Особые случаи задачи о назначениях: максимизация целевой функции

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

Пример: В распоряжении некоторой компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в табл. 1.

Таблица 1 - Объемы продаж в различных торговых точках для различных продавцов

Содержание

1 Введение. 3
2 Анализ и постановка задачи 5
3 Разработка алгоритма 7
3.1 Кодирование решения 8
3.2 Генерация начальной популяции 9
3.3 Оператор кроссинговера 9
3.4 Оператор мутации 10
4 Разработка программного продукта 12
5 Экспериментальное исследование результатов 13
6 Заключение. 16
7 Список использованной литературы 17

Вложенные файлы: 1 файл

МИНОБРНАУКИ РОССИИ.docx

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ В ГОРОДЕ ТАГАНРОГЕ

к курсовой работе

Студентка гр. А-69

2 Анализ и постановка задачи 5

3 Разработка алгоритма 7

3.1 Кодирование решения 8

3.2 Генерация начальной популяции 9

3.3 Оператор кроссинговера 9

3.4 Оператор мутации 10

4 Разработка программного продукта 12

5 Экспериментальное исследование результатов 13

6 Заключение. 16

7 Список использованной литературы 17

1 Введение.

Генетические алгоритмы (ГА) – это новая область исследований, которая появилась в результате работ Д. Холланда и его коллег. ГА, описанные Д. Холландом, заимствуют в своей терминологии многое из естественной генетики. Впервые ГА были применены к таким научным проблемам, как распознавание образов и оптимизация. Генетический алгоритм представляет собой адаптивный поисковый метод, который основан на селекции лучших элементов в популяции, подобно эволюционной теории Ч. Дарвина [1]. То есть, генетический алгоритм позволяет получать хорошие решения за счет его следующих преимуществ:

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

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

3) для оценки пригодности решения наряду с использованием целевой функции дополнительно моделируются правила выживания в исследуемом множестве. Эти правила повышают разнообразие множества решений, которое необходимо для выполнения пункта “1”;

4) при инициализации, преобразовании и других видах обработки решения широко используются вероятностные правила, которые вносят в направленность генетического поиска элементы случайности. Тем самым решается проблема преодоления барьеров локальных оптимумов [2].

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

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

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

В данной работе необходимо решить задачу о назначениях.

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

При анализе мысли высказанной выше определяется цель работы. Она заключается в разработке программы для решения задачи о назначениях с помощью генетического алгоритма c использованием операторов кроссинговера и мутации и с настройкой параметров генетического алгоритма.

Для практической реализации алгоритма было разработано программное обеспечение на языке программирования JAVA.

2 Анализ и постановка задачи

Имеется m групп людей численностью a₁, a₂, …, a_m, которые должны выполнять n видов работ объёмом b₁, b₂, …, b_n.

Известна оплата труда для каждой i-й группы людей при выполнении каждого j-го вида работ c_ij, i = 1, 2, …, m, j = 1, 2, …, n.

Требуется так распределить людей для выполнения работ, чтобы суммарный объем выплат заработной платы был минимален.

Математическая модель данной задачи выглядит следующим образом:

Где: x_ij – число людей i – ой группы, занятых j – м видом работ.

Для перехода от нахождения максимума к нахождению минимума нужно умножить коэффициенты целевой функции на (-1). Тогда целевая функция будет иметь вид

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

3 Разработка алгоритма

Блок схема алгоритма представлена на рисунке 1.

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

3.1 Кодирование решения

Рассмотрим пример для наглядности.

Соответственно в строках – группы рабочих, в столбцах – виды работ.

Теперь создаем хромосому:

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

А теперь создаем новый массив для расчета целевой функции. Она составляется следующим образом: берем значение из ячейки из CH (1), затем находим в первой строке M столбец 1 и на пересечении находим значение и записываем его в MForCF.

Легко определить, что максимально возможный и целесообразный размер популяции равен: n 2

Конечно, возможны и другие способы кодирования хромосомы в рамках данной задачи.

3.2 Генерация начальной популяции

Генерация хромосом, входящих в начальную популяцию, производится путем случайного перемешивания чисел натурального ряда.

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

1) путем перекомпоновки двух старых (родительских) решений;

2) путем случайной перестройки НИ отдельных индивидов.

Первый способ в механизмах ГА называется оператором кроссинговера (скрещивания), второй - оператором мутации. Рассмотрим подробнее основные генетические операторы.

3.3 Оператор кроссинговера

Оператор кроссинговера - это языковая конструкция, позволяющая на основе преобразования (скрещивания) хромосом родителей (или их частей) создавать хромосомы потомков [1].

В работе было использовано несколько видов кроссинговера – двухточечный и на основе золотого сечения.

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

Реализация кроссинговера проста:

1) Выбирается точка разрыва

2) Далее происходит обмен участками до точки разрыва;

3) После точки разрыва происходит пошаговое добавление нового гена хромосомы.

Пример: пусть l= 10, а точка разреза установлена после 5-го элемента

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

После выполнения кроссинговера получается новый вариант распределения рабочих и работ, закодированный в хромосомах потомков.

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

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

3.4 Оператор мутации

Оператор мутации – это языковая конструкция, позволяющая на основе преобразования родительской хромосомы (или ее части) создавать хромосому потомка [1].

Каждый индивид в течение жизни подвергается воздействиям внешней среды. Под влиянием этих воздействий происходит разрыв хромосом. В большинстве случаев фрагменты снова воссоединяются по месту разрыва. Если же такого восстановления не происходит, фрагменты остаются либо открытыми, либо могут воссоединиться другим способом, что приводит к хромосомной перестройке. Это приводит к изменению наследственной информации. Изменение НИ в течение жизни одного индивида называется мутацией, а сам индивид – мутантом.

То есть мутация – это генетическое изменение, приводящее к качественно новому проявлению основных свойств генетического материала: дискретности, непрерывности или линейности. Генные мутации на молекулярном уровне – результат различных повреждений в молекулах ДНК. В пределах одного гена за одно поколение обычно встречаются единичные повреждения, редко – большие. Результатом этого могут быть гибель клетки, изменения характера индивидуального развития, изменение признаков и т.д. Термин “мутация” охватывает все скачкообразные наследственные изменения. В зависимости от характера изменений, возникающих в генетическом материале, выделяют следующие типы мутаций:

точечные;
хромосомные перестройки;
инверсии.

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

4 Разработка программного продукта

Алгоритм, описанный выше, был реализован на языке Java, в среде NetBeans 6.8.

На рисунке 2 представлен интерфейс программы. Данные работы алгоритма отображены в консоли.

Рисунок 2 Интерфейс программы

На рисунке видны поля для заполнения начальных параметров алгоритма:

Количество работников и рабочих мест;
Размер начальной популяции;
Количество генераций;
Вероятность кроссинговера и мутации.

Так же в интерфейсе представлена наглядная иллюстрация решения на графе. Вершины графа это группы людей и группы работ. Соответственно соединенные вершины графа представляют собой лучшее решение данной задачи.

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

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

Целочисленные задачи математического программирования могут возникать различными путями.

. Существуют задачи линейного программирования, которые формально к целочисленным не относятся, но при соответствующих исходных данных всегда обладают целочисленным планом. Примеры таких задач - транспортная задача и ее модификации (задачи о назначениях, о потоках в сетях).

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

Исторически первой задачей целочисленного типа является опубликованная в 1932 г. венгерским математиком Е. Эгервари задача о назначении персонала. В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце.

Цель данной работы: В данной работе я рассмотрю Целочисленное линейное программирование(ЦЛП) ориентированное на решение задач линейного программирования, также рассмотрю задачу о назначениях. На их примере решу задачи из этой области.

1. Целочисленное линейное программирование
Целочисленное линейное программирование (ЦЛП) ориентировано на решение задач линейного программирования, в которых все или некоторые переменные должны принимать целочисленные (или дискретные) значения. Несмотря на интенсивные исследования, проводимые на протяжении последних десятилетий, известные вычислительные методы решения задач ЦЛП далеки от совершенства. На сегодня не существует надежных вычислительных алгоритмов решения таких задач.
. Постановка транспортной задачи по критерию стоимости в матричной форме
Транспортная задача (ТЗ) формулируется следующим образом. В m пунктах отправления A1,….,Am сосредоточен однородный груз в количествах соответственно a1,….,am единиц. Имеющийся груз необходимо доставить потребителям B1,….,Bn спрос которых выражается величинами b1,….,bn единиц. Известна стоимость сij перевозки единицы груза из i-го пункта отправления в j-й который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются.

Для построения экономико-математической модели ТЗ рассмотрим матрицу

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

Матрицу Х=[хij]т×п будем называть матрицей перевозок. Предполагается, что все xij≥0. Удельные транспортные издержки (расходы) запишем в форме матрицы C = [cij]m×n и назовем ее матрицей тарифов.

Для наглядности условия ТЗ можно представить таблицей (табл. 2.1), которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ.
Таблица 2.1

Экономико-математическая модель ТЗ должна отражать все условия и цель задачи в математической форме. Так, переменные должны удовлетворять ограничениям по запасам, потребностям и условиям неотрицательности.

В математической форме эти условия можно записать так.

целочисленный отсечение транспортный гомори

(2.2)
Цель ТЗ - минимизировать общие затраты на реализацию плана перевозок, которые можно представить функцией
(2.3)
Итак, математически ТЗ ставится так. Даны система ограничений (2.1) при условии (2.2) и линейная функция (2.3). Требуется среди множества решений системы (2.1) найти такое неотрицательное решение, при котором линейная функция (2.3) принимает минимальное значение (минимизируется).

Будем называть план перевозок Х=[хij]т×п допустимым, если он удовлетворяет ограничениям (2.1) и (2.2).

Допустимый план перевозок, доставляющий минимум целевой функции (2.3), называется оптимальным.
. Задача о назначении (проблема выбора, задача о женихах и невестах)
Она является исторически первой задачей дискретного программирования (опубликована венгерским математиком Е. Эгервари в 1932 г. как задача транспортного типа).

Имеется n исполнителей, которые могут выполнять n различных работ.

Известна полезность cij связанная с выполнением i-м исполнителем j-й работы.

Необходимо так назначить исполнителей на работы, чтобы добиться максимальной полезности при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.

Для составления математической модели задачи обозначим через xij факт назначения или неназначения i-го исполнителя на j-ю работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то xij должны принимать только два значения: 1 или 0. Такие переменные называют булевыми. Итак,

Приходим к задаче: найти план назначения xij, который максимизирует суммарную полезность назначений:

при следующих ограничениях. Каждый исполнитель назначается только на одну работу:
(3.1)
На каждую работу назначается только один исполнитель

(3.2)
Условия неотрицательности и целочисленности (булевости):
(3.3)
Легко видеть, что задача о назначении - частный случай транспортной задачи при Однако с учетом специфики задачи для ее решения разработаны специальные, более эффективные алгоритмы.

Задача о назначении имеет самое широкое применение. Например, при закреплении машин за маршрутами, распределении инструментов для обработки различных марок стали, рабочих или бригад и т. д. В каждом конкретном случае математическая модель задачи может иметь специфику. Например, в задаче распределения алгоритмов между вычислительными машинами на ВЦ число распределяемых алгоритмов, как правило, не равно числу машин. При назначении на должности для некоторых исполнителей существуют ограничения. Прежде всего необходимо отметить, что если задача о назначениях ставится при условии получения максимального эффекта, то ее сводят к задаче на минимум. Пусть дана матрица эффективности C=[cij].В каждом столбце найдем максимальный элемент Построим матрицу С'=[ lj-cij ]
Задача

где - область допустимых решений системы (3.1) - (3.3), эквивалентна задаче

Функция Z' достигает минимума при условии, что Z достигает максимума,

Пример . При закреплении транспортных средств за маршрутами определена матрица прибылей

Найти план закрепления, максимизирующий суммарный эффект.

Решение. Прежде всего сведем задачу на максимум к задаче на минимум. Для этого в каждом столбце матрицы С найдем максимальный элемент и вычтем из него элемент соответствующего столбца. Получим матрицу Сj задачи о назначениях:

которую будем решать на минимум:

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

План назначения (1-4), (2-1), (3-3), (4-2),

maxZ =с14+с21+с33+с42 =12 + 7+ 15+14 = 48.
. Метод отсечения
Алгоритм метода Гомори для решения полностью целочисленной задачи линейного программирования. Рассмотрим полностью целочисленную задачу линейного программирования
(4.1)

(4.4)
Алгоритм Гамори состоит из нескольких этапов:

1. Решается задача (4.1) - (4.3) с отброшенным условием целочисленности.

2. Полученное оптимальное решение (если оно существует) проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение задачи (4.1) - (4.4) совпадает с оптимальным решением задачи (4.1) - (4.3). Если это решение не выполняется хотя бы по одной переменной, то переходят к третьему этапу. Если задача (4.1)-(4.3) оказывается неразрешимой, то задача (4.1)-(4.4) тоже не имеет решения.

3. Строится дополнительное ограничение, отсекающее часть области, в которой содержится оптимальное решение задачи (4.1) - (4.3) и не содержится ни одного допустимого решения задачи (4.1) - (4.4).

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

Алгоритм Гомори позволяет за конечное число шагов прийти к оптимальному целочисленному решению, если оно существует.

С геометрической точки зрения каждому дополнительному линейному ограничению в n-мерном пространстве соответствует определенная гиперплоскость, отсекающая от многогранника решений некоторую его часть, включая и оптимальную на данном этапе нецелочисленную вершину.

При этом все точки с целочисленными координатами, в том числе и искомая оптимальная, остаются в усеченном многограннике. Так как множество целых точек усеченного многогранника совпадает с множеством целых точек исходного многогранника, то понятно, что если оптимальное решение ЗЛП на усеченном многограннике удовлетворяет условию целочисленности, то оно является оптимальным целочисленным решением и исходной задачи. Через несколько операций отсечения искомая целочисленная точка оказывается сначала на границе, а затем становится оптимальной вершиной неоднократно усеченного многогранника решений.

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

Для лучшего понимания существа вопроса обратимся к наглядной иллюстрации случая п=2 (рис. 4.1). Ограничения задачи определяют на плоскости x1Ox2 некоторый многоугольник М, в вершине которого, если не учитывать условия целочисленности, достигается максимум целевой функции. Внутри этого многоугольника имеется конечное множество точек, которым соответствуют решения с целочисленными значениями переменных (на рисунке они обозначены кружочками). На рисунке показаны три прямые l1 ,l2 ,l3 соответствующие трем дополнительным линейным ограничениям. Каждая из прямых отсекает часть области допустимых решений. Так, после отсечения части области прямой оптимальной оказывается вершина ,и, наконец, оптимальной становится целочисленная вершина .Основное в алгоритме - составление дополнительного ограничения, т. е. отсекающей гиперплоскости, которая называется правильным отсечением. Правильное отсечение должно удовлетворять следующим условиям: 1) быть линейным; 2) отсекать найденное оптимальное нецелочисленное решение задачи (4.1) - (4.3); 3) не отсекать ни одной из целочисленных точек задачи (4.1) - (4.5).
Рисунок 4.1

Формирование правильного отсечения. После каждой итерации система ограничений имеет вид
(4.5)
где - множество базисных переменных.

Если выполняется условие оптимальности задачи, то находим оптимальное решение. Если, все компоненты оптимального плана целочисленны, то задача решена. Предположим, что некоторые ( - нецелые. Пусть компонента i0 - нецелая. Рассмотрим i0 равенство системы (4.5), для которой выполняется условие оптимальности, т.е.
(4.6)
Напомним, что наибольшая целая часть числа а, его не превосходящая, обозначается [а], а дробная положительная- . Причем
(4.7)
Например, пусть а = 3,2. Имеем [3,2] = 3; =0,2; 3,2 =3+0,2. Пусть а= - 4,3. Имеем [-4,3]=-5, =0,7, -4,3=-5 + 0,7.

Перейдем к дальнейшему изучению уравнения (4.6). Найдем целую и дробную части его коэффициентов и .Согласно равенству (4.7), имеем:
(4.8)

Так как, по предположению, нецелое, то

Кроме того, . Подставив выражение (4.8) в равенство (4.6), получим
(4.9)

Так как первое слагаемое равенства (4.9) есть целое число, то, для того чтобы было целым, необходимо, чтобы второе слагаемое также было целым, т. е. величина

должна быть целым числом. Так как xio- координата допустимого целочисленного решения задачи (4.1) - (4.4), то Li0 -всегда целое число. Покажем, что Li0≤0. В самом деле, величина

не может быть отрицательной. Из условия (4.7) следует Так как Li0 -целое, то из предположения,что Li0 > 0, должно следовать , что противоречит определению дробной части числа.

Итак, доказано, что любое допустимое решение задачи (4.1) - (4.4) должно удовлетворять неравенству
(4.10)
Решение задач
Задача № 1
x1, x2, … , x5 - план погрузки (ед.)

1. Задача (формулировка).

Мы будем проще (в терминах). =)

Представим себе задачу: нужно эффективным образом реализовать некоторый относительно большой проект. Для проекта была отобрана команда первоклассных разработчиков, разбирающихся в различных областях. И так уж посчастливилось, что есть сведения (накопленная статистика) о степени (эффективности) владения технологиями для каждого. Но, к сожалению, разработчиков в команде не так уж и много, а точнее – столько же, сколько и технологий будет использовано в проекте.

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

2. Подход к решению

In the end, all business operations can be reduced to three words: people, product, and profits ©. Если мы попробуем изобразить поставленную перед нам и задачу на листе бумаги, то наверняка получим подобную иллюстрацию, как на рисунке (с такими картинками).

Получился — граф. Вершины слева – разработчики, вершины справа – технологии (задачи). Ребра, которые их соединяют – означают то, насколько разработчик в ней разбирается. Эти цифры, т.е. степень владения разработчиком данной технологией, очень важны, но к ним обратимся чуть позже. А пока мы уже верно наметили направление, в котором эффективно решается данная задача:

3. Графы

Самые основы графов были изложены в статье (max cost), поэтому сразу перейду к терминологии, касающейся данной задачи:

4. Максимальное паросочетание

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

Как же увеличить паросочетания (назначения)?

Добавим еще немного терминологии из теории графов, простыми словами:

Теперь мы уже сможем задействовать наибольшее количество технологий в проекте. Самое время принять во внимание еще одно важное условие поставленной перед нами проблемы: эффективность владения технологиями. Мы ведь хотим оптимально назначить всем задачи.

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

Стратегия ясна.

6. Описание алгоритма

Все. Все шаги данного метода рассмотрены. Продолжаем в том же духе… Success is not final, failure is not fatal: it is the courage to continue that counts.

7. Алгоритм словами, очень кратко

8. Листинг

Код, конечно, будет покороче, чем все мое описание. =)

Я взял его здесь. На мой взгляд, очень хорошая реализация. Единственное отличие, у автора приведен код метода минимизации назначений (если, допустим, на ребрах – зарплата), а в статье мы распределяли задачи с целью получения максимальной эффективности. Поэтому, слегка модифицировав код, приведу ниже реализацию максимального метода:

int n;
vector int > > a; // Матрица эффективности a[разраб][задача]
vector int > xy, yx; // Паросочетания: xy[разраб], yx[задача]
vector char > vx, vy; // Альтернирующее дерево vx[разраб], vy[задача]
vector int > maxrow, mincol; // Способности, изученность

bool dotry ( int i) if (vx[i]) return false ;
vx[i] = true ;
for ( int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0)
vy[j] = true ;
for ( int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0 && yx[j] == -1) xy[i] = j;
yx[j] = i;
return true ;
>
for ( int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0 && dotry (yx[j])) xy[i] = j;
yx[j] = i;
return true ;
>
return false ;
>

mincol.assign (n, 0);
minrow.assign (n, 0);
for ( int i=0; i for ( int j=0; j for ( int c=0; c int k = 0;
for ( int i=0; i if (xy[i] == -1 && dotry (i))
++k;
c += k;
if (k == 0) int z = INF;
for ( int i=0; i if (vx[i])
for ( int j=0; j if (!vy[j])
z = min (z, maxrow[i]+mincol[j]-a[i][j]);
for ( int i=0; i if (vx[i]) maxrow[i] -= z;
if (vy[i]) mincol[i] += z;
>
>
>

int ans = 0;
for ( int i=0; i "%d\n" , ans);
for ( int i=0; i "%d " , xy[i]+1);
>

* This source code was highlighted with Source Code Highlighter .

9. Итого

Читайте также: