Решение задачи назначения с помощью электронных таблиц

     Умение  руководить коллективом:

1) хорошее;

2) удовлетворительное.

Практический  опыт:

1) большой;

2) небольшой;

3) отсутствует.

       Приведем  для примера формулировку оценок на «зеркальных» шкалах критерия «Профессиональная  подготовленность».

Шкала требований:

1) требуются  работники с высокой профессиональной  подготовкой.

2) достаточна  удовлетворительная профессиональная  подготовка.

Шкала возможностей:

1) претендент  обладает высокой профессиональной  подготовкой.

2) профессиональная  подготовка претендента удовлетворительна. 
 

     Предположим, что эксперты охарактеризовали возможности  субъектов следующими оценками по выбранным  критериям: 

     =(2; 1; 2);

     =(2; 2; 2);

     =(2; 2; 3).

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

     Характеристики  объектов:

     =(l; 1; 2);

     =(2; 1; 2);

     =(2; 2; 2).

 Эти  характеристики выражают должностные  требования. Так, для занятия должности

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

       1.2 Методы решения  задач, оптимизации  процесса назначения

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

     Для применения симплекс-метода необходимо, чтобы знаки в ограничениях были вида «меньше либо равно», а компоненты вектора b - положительны.

     Алгоритм  решения сводится к следующему: приведение системы ограничений к каноническому  виду путём введения дополнительных переменных для приведения неравенств к равенствам.

     Если  в исходной системе ограничений  присутствовали знаки «равно» или  «больше либо равно», то в указанные  ограничения добавляются искусственные  переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума. Формируется  симплекс-таблица. Рассчитываются симплекс-разности. Принимается решение об окончании  либо продолжении счёта. При необходимости  выполняются итерации. На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица  пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

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

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

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

     Суть  венгерского метода состоит в  следующем: путем прибавления определенным образом найденных чисел к  некоторым столбцам и вычитания  из них некоторых чисел находят  систему так называемых независимых  нулей. Набор нулей называется системой независимых нулей, если никакие  два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей  равно n, то, приняв соответствующие  им переменные xij равными 1, а все  остальные – равными 0, согласно утверждению 2, получим оптимальный  план назначения.

     Алгоритм  венгерского метода состоит из предварительного шага и не более, чем (n-2) последовательно  повторяющихся итераций. На предварительном  этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную  задачу на минимум. На этом же этапе  выделяется система независимых  нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как  только число независимых нулей k станет равным размерности матрицы (k=n), задача решена. Оптимальный план назначения определится положением независимых нулей на последней  итерации. 

       1.3 Экономико-математическая  модель

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

       Исходные  параметры модели задачи о назначениях

1. n – количество ресурсов, m – количество работ.

2.–  единичное количество ресурса,  например: один работник; одно транспортное  средство;   одна научная тема и т.д.

3.–  единичное количество работы, например: одна должность; один маршрут;  одна лаборатория.

4.–  характеристика качества выполнения  работы

с помощью  ресурса.

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

      Искомые параметры:

 1.–  факт назначения или неназначения  ресурса

       на  работу: 

2. L(X) – общая (суммарная) характеристика качества распределения ресурсов по работам.

 
 
 

2 Практическая  реализация  задачи назначения

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

Этот  алгоритм состоит из трех этапов.

Этап 1:

1. Формализация  проблемы в виде транспортной  таблицы по аналогии 

  с решением транспортной задачи.

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

3. Повторить  ту же самую процедуру для  столбцов.

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

Этап 2.

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

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

2. Зачеркнуть  оставшиеся нулевые значения  данного столбца.

3. Пункты 1 и 2 повторять до тех пор,  пока продолжение описанной процедуры  окажется невозможным.

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

4. Найти  столбец, содержащий только одно  нулевое значение, и в соответствующую  клетку поместить один элемент.

5. Зачеркнуть  оставшиеся нули в данной строке.

6. Повторять  пункты 4 и 5 до тех пор, пока  дальнейшая их реализация окажется  невозможной.

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

Этап 3.

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

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

3. Вычесть  его из всех элементов, через  которые не проходят прямые.

4. Прибавить  найденный элемент ко всем  элементам таблицы, которые лежат  на пересечении проведенных ранее  прямых

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

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

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