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

Содержание 

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: В отдельной строке выписываем минимальный элемент каждого столбца:

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

Этап 2 

Шаг 6:  Найдем строку, содержащую только одно нулевое значение, и пометим эту клетку. (Если такие строки отсутствуют, допустимо начать с любого нулевого значения.).  В данном случае это строка А, помечаем клетку А2, зачеркиваем нулевое значение в столбце 2, т.е. Г2.

     Далее делаем аналогично. Берем  строку с одним нулевым элементом  – Б, помечаем клетку Б7, а  в столбце 7 вычеркиваем нулевой  элемент Г7.

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

     Рассмотрим строку Г: т.к. нули  Г2 и Г7 вычеркнуты, то в строке  Г остался только один ноль  Г6, помечаем его и вычеркиваем  все нули столбца 6, т.е. Ж6.

     Строка Д имеет три нулевых  значений, а строка Е имеет только один ноль, но он вычеркнут. Переходим к строке Ж: Ж6 вычеркнута, поэтому помечаем единственный оставшийся ноль Ж4. Т.к в столбце 4 больше нет нулевых значений, то ничего не вычеркиваем.

     Видим, что таблице остались  незачеркнутые нули. Тогда выбираем строку с единственным нулевым значением, в данном случае 1. Помечаем ноль Д1, а оставшееся нулевое значение в строке Д5 вычеркиваем.

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

Этап 3 

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

Шаг 8: Найдем минимальный элемент из тех, через которые не проходят прямые. В данном случае это единица. Вычитаем это минимальное значение из каждого элемента, через который не проходят прямые (А1-В1, Е1, А4:В6, Е4-Е6), прибавляем минимальное значение к элементам, которые расположены на пересечении прямы (Г2, Д2, Ж3 и т.п.),а остальные элементы оставляем без изменения. Получим такую таблицу:

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

Шаг 9 (аналогичен шагу 6 этапа 2): Рассмотрим строку с единственным нулевым значением А, пометим клетку А2; т.к. в столбце 2 больше нет нулевых значений перейдем к следующей строке.

     Смотрим строку Б и помечаем  элемент Б7, больше нулевых элементов  в 7 столбце нет.

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

     Рассмотрим строку Г, помечаем  ноль Г6, вычеркиваем нули Е6  и Ж6.

     В строке Д два нулевых значения, а в строке Е все нулевые  значения зачеркнуты, поэтому перейдем  к строке Ж: ноль Ж6 вычеркнут, следовательно помечаем оставшийся ноль Ж5.

     Осталась строка Д, т.к. там  два нулевых значения, то выбираем  столбец в одним нулевым значением  Д1, а элемент Д5 вычеркиваем.