Математическое моделирование экономики

Содержание 

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

2. Описание  алгоритма …………………………………………………………...3

3. Решение  поставленной задачи……………………………………………….. 6

4. Выводы по  проделанной работе ……………………………………………..14

5. Список  использованной литературы……………………………………….. 15 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

     Математическая постановка задачи.

Дана  неотрицательная матрица размера n×n, где элемент в i-й строке и j-ом столбце соответствует объемам  продаж в  j-м магазине i-м продавцом. Нужно найти такое соответствие работников магазинам, чтобы максимизировать объем продаж. 

     Тестовый пример.

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

 

Как нужно  распределить продавцов по торговым точкам, чтобы добиться максимального объема продаж? 

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

     Венгерский алгоритм — алгоритм  оптимизации, решающий задачу  о назначениях за полиномиальное время. Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари).

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

     Венгерский алгоритм состоит  из 3х этапов: 

Этап 1:

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

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

Этап 2:

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

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

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

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

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

Этап 3: 

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

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

3. Решение поставленной задачи 

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

Этап 1 

Шаг 1: Умножаем каждый элемент данной таблицы на (-1) :

 
 

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

 
 

Шаг 3: Вычитаем минимальный элемент из каждого элемента соответствующей строки, получим:

 
 

Шаг 4: В отдельной строке выписываем минимальный элемент каждого столбца: