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

Размещено на http://www.allbest.ru/

Изм.	Лист	№ докум.	Подп.	Дата
Разраб.				Задача о назначениях	Лит.	Лист	Листов
Пров.					У			2
					ВСГТУ
Н. контр.
Утв.

Содержание

Введение

1. Постановка задачи

2. Теоретический раздел

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

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

3. Проектный раздел

3.1 Описание алгоритма и структуры программы

3.2 Формальная постановка

3.3 Описание использованных программных средств

4. Экспериментальный раздел

Заключение

Список использованных источников

Приложение



Введение

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

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

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

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



1. Постановка задачи

Задача о назначении. Нахождение минимального (максимального) убытка при найме работников. Эта задача осуществляется путем реализации венгерского алгоритма.



2. Теоретический раздел

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

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

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

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

Частным случаем транспортной задачи является задача о назначениях, в которой число пунктов производства равно числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях 2может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода.

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

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

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

Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы

чтобы сумма была максимальна и при этом из каждой строки и столбца С был выбран только один элемент.

Введем следующие понятия.

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

Две прямоугольные матрицы С и D называются эквивалентными (C ~ D), если для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).

Словесное описание алгоритма

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

Таблица 2.1. Расстояние от сбытовых баз до потребителей

Сбытовая база	Расстояние, миль Потребители
	I	II	III	IV
А В С D	68 56 3847	72 60 40 42	75 58 35 40	83 63 45 45

Решение

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

Этап 1 Венгерского метода: В каждой строке находится наименьший элемент.



Таблица 2.2. Выявление наименьших элементов по строкам

	Потребители	Наименьший элемент строки
	I	II	III	IV
А В С D	68 56 38 47	72 60 40 42	75 58 35 40	83 63 45 45	68 56 35 40

Наименьший элемент вычитается из всех элементов соответствующей строки

Таблица 2.3. Вычитание наименьшего элемента по строкам и выявление наименьшего элемента по столбцам

0	4	7	15
0	4	2	7
3	5	0	10
7	2	0	5
0	2	0	0	?Наименьший элемент столбца

Найденный наименьший элемент вычитается из всех элементов соответствующего столбца.

Таблица 2.4. Вычитание наименьшего элемента по столбцам

0	2	7	10
0	2	2	2
3	3	0	5
7	0	0	0

В соответствии с процедурой, описанной в этапе 2, осуществляются назначения. Наличие назначения обозначается через все нули таблицы.



Таблица 2.5. Назначения в клетки с нулевыми значениями

0	2	7	10
0	2	2	2
3	3	0	5
7	0	0	0

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

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

Таблица 2.6. Скорректированная таблица с назначениями для нулевых клеток

	I	II	III	IV
А	0	0	7	8
В	0	0	2	0
С	3	1	0	3
D	9	0	2	0

Теперь требование о размещении четырех назначений в клетки с нулевой стоимостью выполняется, следовательно, полученное решение является оптимальным. Перевозки осуществляются со сбытовой базы А к потребителю I, с базы В - к потребителю II, с базы С - к потребителю III и с базы D - к потребителю IV. Хотя данное решение и является оптимальным, однако оно не единственное. В любом оптимальном решении должен присутствовать маршрут (С,III), поскольку это единственный элемент с нулевой стоимостью в строке С. Два других оптимальных распределения назначений представлены ниже.

Таблица 2.7. Первое альтернативное оптимальное решение

	I	II	III	IV
A	0	0	1	8
В	0	0	2	0
С	3	1	0	3
D	9	0	2	0

Таблица 2.8. Второе альтернативное оптимальное решение

	I	II	III	IV
А	0	0	7	8
В	0	0	2	0
С	3	1	0	3
D	9	0	2	0

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

Решение 1: 68 + 60 + 35 + 45 - 208 миль;

Решение 2: 68 + 63 + 35 + 42 = 208 миль;

Решение 3: 72 + 56 + 35 + 45 = 208 миль.

Общая дальность перевозок для всех трех решений одинакова.

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

В этой связи может оказаться полезным так называемое "правило правой руки":

1. Выбирается любая строка или столбец, содержащие только один нулевой элемент.

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

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

4. Пункты 1-3 повторяются до тех пор, пока не будут учтены все входящие в таблицу нули.



3. Проектный раздел

3.1 Описание алгоритма и структуры программы

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

1. Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.

2. Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.

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

Для написания программы используется язык программирования С++. При написании программы использовалась среда Microsoft Visual Studio.

Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.

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

По нажатию кнопки "найти путь" включается функция алгоритма Дейкстра и найденный путь выводится в окне сообщений. Если пути между заданными точками не существует - выводится соответствующее сообщение.



3.2 Формальная постановка

Входные данные: взвешенный ориентированный граф, номера начальной и конечной вершины.

Выходные данные: кратчайший путь из начальной в конечную вершину, его длина.

3.3 Описание использованных программных средств

Таблица 3.1. Описание переменных

Переменная	Описание
myPoint V[Max_N]	Массив вершин графа(коодинаты вершины)
int E[Max_N][Max_N]	Массив ребер графа
PointFstartpos,endpos	Начальная и конечная точка ребра(вершины графа)
intcena[Max_N][2]	Массив значений - минимальное расстояние до вершины и предок
multimap<int,int> m	Словарь значений - минимальная цена среди текущих и номер его

В программе были использованы следующие функции:

· Double modul(myPointA,myPointB) - функция, которая возвращает расстояние между 2мя точками.

· Void Deikstra(intA,intB) - функция, реализующая алгоритм Дейкстры.

· Void DrawCena(intA,intB) - графическая процедура рисования цены дуги.

· Void DrawGraph() - графическая процедура рисования графа.



4. Экспериментальный раздел

Тестирование при нормальных условиях

Нормальные условия - количество ребер меньше 100, цена ребра меньше 1000000000. Алгоритм выполняется успешно.

Рисунок 4.1. Тестирование при нормальных условиях.

Рисунок 4.2. Тестирование при нормальных условиях

Тестирование при экстремальных условиях

Экстремальные условия - длина дуги больше миллиарда. Как видно на рисунке 3, из за проверки на максимальную цену, дуга не создается.

Рисунок 4.3. Тестирование при экстремальных условиях.



Экстремальные условия - координаты начала дуги и конца совпадают. Программа не может рисовать петли в графе, соответственно выводится сообщение об ошибке (это видно на рисунке 4.4).

Рисунок 4.4. Тестирование при экстремальных условиях.



Заключение

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

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



Список использованных источников

1. Таха Х. А. Введение в исследование операций. 7-е издание: Пер. с англ. - Москва: Издательский дом "Вильяме", 2014. - 912 с.

2. Диниц Е.А., Крондрл М.А. Один алгоритм решения задачи о назначении. / ДАН.-2009. - Т. 189. - №1. - С. 23-25.

3. Ершов В.А., Ирбенек А.С. Алгоритм решения задачи назначения на матрицах специального вида. - М., 1981. - 20 с. (Препр. Ин-т точн. Механ. и вычислит. техн. Им. С.А. Лебедева; №4).

4. Флейшман С.Б. Назначения с задачным порядком следования. - 2011. - Т. 319. - №1. - С. 581-584.

5. Ирбенек В.С. Верификация временных соотношений и оптимизация размещения конструктивных элементов супер ЭВМ. - М., 2003. - 29 с. (Препр. Ин-т точн. механ. и вывислит. техн. им. С.А. Лебедева; №2).

6. Карлин С. Математические методы в теории игр, программирования и экономике. - М.: Мир, 1964.

7. Флейшман С.Б. Оптимальные назначения специального вида. - М., 2014. - 15 с. (Препр. Ин-т точн. механ. и вычислит. техн. Им. С.А. Лебедева; №2).



Приложение

Листинг программы

Объявление переменных, функций и констант:

#pragmaonce

#include<math.h>

#include"inputbox.h"//подключаетсяформа

#include<vector>

#include<map>//подключаем ассоциативный массив - содежит пары <ключ,значение> и сортирует автоматически по ключу

usingnamespace System::Drawing;

struct myPoint //создаемструктуру

{

float X,Y;

};

usingnamespace std;//используем стандартное пространство имен

constint Max_N=100;//максимальное количество вершин

myPoint V[Max_N];//Массив вершин графа(коодинаты вершины)

int E[Max_N][Max_N];//Массив ребер графа(1000000000-нет ребра, менее 1 млрд - ребро из i-ой вершины в j-ую заданной стоимости)

int N=0;//количество вершин

PointF startpos,endpos;//начальная и конечная точка ребра(вершины графа)

constdoubleR_min=8.0;//радиус точки обозначающей вершины графа



Процедура алгоритма Дейкстры:

void Deikstra(int A,int B)//реализация алгоритма Дейкстры

{

--A;//приводим номера вершин к отсчету с 0

--B;//

int i;

for (i=0;i<Max_N;i++)//присваиваем всем очень большое число - знак что их еще не посетили.

{

cena[i][0]=1000000000;

cena[i][1]=-1;

}

if (A<0||A>=N || B<0 || B>=N)//если номера вершин не существуют, завершаем работу процедуры

return;

m.clear();//очищаем список цен и вершин.

cena[A][0]=0;//достижимость вершины А равна нулю.

m.insert(make_pair(0,A));//и добавляем ее как текущую.

while (!m.empty())//и пока есть вершины для обновления

{

int k=(*m.begin()).second;//запоминаем номер вершины с самой маленькой ценой

m.erase(m.begin());//удаляем ее из списка

for(i=0;i<Max_N;i++)//и бежим по всем ребрам из этой вершины (К-ой)

if (E[k][i]<1000000000 &&//если есть ребро и..

cena[i][0]>cena[k][0]+E[k][i])//цена перехода из этой вершины меньше чем из другой то

{

cena[i][0]=cena[k][0]+E[k][i];//присваиваем цену минимальную

cena[i][1]=k;//и запоминаем из какой вершины пришли

m.insert(make_pair(cena[i][0],i));//добавляем в словарь цен и номеров вершин

}

}

Процедура рисования графа и цены возле дуги:

private: void DrawCena(int A,int B)//процедура рисования Цены возле ребра

{

double a,b;

a=(V[A].X+V[B].X)/2; //вычисляемсерединуребра

b=(V[A].Y+V[B].Y)/2;

double x,y,r=sqrt(pow(V[A].X-V[B].X,2)+pow(V[A].Y-V[B].Y,2));//длинуребра

x=(V[B].X-V[A].X)/r;//нормируем вектор

y=(V[B].Y-V[A].Y)/r;

a-=y*12;//и по середке со смещением пишем

b+=x*12;

g->DrawString(E[A][B].ToString(),l1->Font,(gcnew Pen(Color::Blue))->Brush,a,b);//ценуребра

x*=7;

y*=7;

a=V[B].X-x;

b=V[B].Y-y;

Pen^ p =gcnew Pen(Color::Black);

g->DrawLine(p,(float)a,(float)b,(float)a-x-y,(float)b-y+x);

g->DrawLine(p,(float)a,(float)b,a-x+y,b-y-x);

};

private: void DrawGraph()//процедурарисованияграфа

{

float r=R_min/2;//радиус точки "вершины"

this->g->FillRectangle((gcnew Pen(Color::White))->Brush,0,0,pictureBox1->Width,pictureBox1->Height);//заливаемвесьпикчербокс

for (int i=0;i<N;i++)// в цикле прорисовываем все вершины на полотне в виде кружков

g->DrawEllipse(p,V[i].X-r,V[i].Y-r,R_min,R_min);

for (int i=0;i<N;i++)//и по всему массиву ребер бежим

for (int j=0;j<N;j++)

if (E[i][j]<1000000000)//если есть ребро, то рисуем его:

{

g->DrawLine(p,ftoF(V[i]),ftoF(V[j]));//рисуем ребро из i-ой в j-ую вершину

g->DrawString((i+1).ToString(),l1->Font,p->Brush,V[i].X+4,V[i].Y+4);//ипишемномеравершин

g->DrawString((j+1).ToString(),l1->Font,p->Brush,V[j].X+4,V[j].Y+4);//ивторойномер.

DrawCena(i,j);

}

}

Процедуры обработки событий нажатия и опускания мыши:

private: System::Void pictureBox1_MouseDown(System::Object^ sender, System::Windows::Forms::MouseEventArgs^ e)

{//событиеопусканиякнопкимыши

startpos= pictureBox1->PointToClient(MousePosition);//запоминаемпозициюуказателянабоксе

}

private: System::Void pictureBox1_MouseMove(System::Object^ sender, System::Windows::Forms::MouseEventArgs^ e)

{//событие перемещения мыши над боксом(картинкой)

DrawGraph();//перерисуемграф

if (startpos!= PointF(-1,-1))//и если существует точка начала ребра, то

{

this->g->DrawLine(p,startpos,pictureBox1->PointToClient(MousePosition));//проводим ребро до текущей позиции курсора

}

for (int i=0;i<N;i++)//бежим по всем вершинам и ...

if (modul(Ftof(pictureBox1->PointToClient(MousePosition)),V[i])<R_min/2.0)//если расстояние от указателя до вершины меньше заданного то

{

pictureBox1->Cursor = Cursors::Hand;//ставимкурсовввид "Руки"

break;//прерываемцикл

}

else

pictureBox1->Cursor = Cursors::Default;//иначеставимстандартныйкурсор

}

private: System::Void pictureBox1_MouseUp(System::Object^ sender, System::Windows::Forms::MouseEventArgs^ e)

{//событие отпускания мыши

if (startpos!= PointF(-1,-1))//если есть стартовая точка ребра то...

{

int n1=N;

endpos=pictureBox1->PointToClient(MousePosition);//вычисляем конечную точку ребра

if (modul(Ftof(endpos),Ftof(startpos))<R_min)

{

startpos=PointF(-1,-1);//убираем стартовую точку(начало ребра)

MessageBox::Show("Нельзя делать 'Петли'(начало и конец совпадает) в графе","Результат");

return;

}

int fl1=-1,fl2=-1;//номера конечной и начальной вершины для нового ребра

for (int i=0;i<N;i++)//пробегаем по циклу и ищем, есть ли совпадения со старыми вершинами

{

if (modul(Ftof(startpos),V[i])<R_min) fl1=i;//если начало совпадает с какой-то вершиной, то ставим ее туда

if (modul(Ftof(endpos),V[i])<R_min) fl2=i;//если конец ребра совпадает с какой-то вершиной, то ставим ее туда

}

if (fl1==-1) {V[N++]=Ftof(startpos);fl1=N-1;}//если не совпадает начало ни с какой старой вершиной, то делаем новую вершину

if (fl2==-1) {V[N++]=Ftof(endpos);fl2=N-1;}//если не совпадает конец ни с какой старой вершиной, то делаем новую вершину

if (E[fl1][fl2]<1000000000)//если есть уже ребро то

{

startpos=PointF(-1,-1);//убираем стартовую точку(начало ребра)

MessageBox::Show("Нельзя делать 'Кратные ребра'(такое ребро уже есть) в графе","Результат");

return;

}

else{

InputBox p;

p.ShowDialog(this);//показываем форму ввода цены

if (p.result)//и если не отмена, то

E[fl1][fl2]=Convert::ToInt32(p.textBox1->Text);//ставим в матрицу смежности что есть ребро такой то цены

else

N=n1;//иначе восстанавливаем количество вершин

}

startpos=PointF(-1,-1);//убираем стартовую точку(начало ребра)

}

}

Процедура вызова алгоритма Дейкстры:

System::Void button1_Click(System::Object^ sender, System::EventArgs^ e)

{//

int i=Convert::ToInt32(maskedTextBox1->Text),j=Convert::ToInt32(maskedTextBox2->Text);//запоминаемномеравершин

Deikstra(i,j);//запускаемалгоритмДейкстры

if (cena[j-1][1]==-1)//если цена осталась отрицательна, то пути нету между вершинами

MessageBox::Show("Нет пути между этими вершинами!","Результат");

else

{

int k=j-1;//запоминаем вершину

DrawGraph();//рисуемграф

String^ Path ="";//

while (k!=i-1)//и пока не встретим начальную вершину, поднимаемся и прорисовываем от конечной

{

Path=(k+1).ToString()+" - "+Path;//заносим весь путь в стрчку через тире

k=cena[k][1];//переходя к предку текущей

}

Path=(i).ToString()+"-"+Path;//добавляем начальную вершину в начало списка

MessageBox::Show("Последовательность: "+Path +".""\nДлина пути = "+cena[j-1][0].ToString(),"Результат",MessageBoxButtons::OK);

}

}

Размещено на Allbest.ru

...