Автоматизация решения задачи о назначениях в MS Excel. Линейная модель. Поиск решения. Автоматизация решения задачи о назначениях в ПЭР

Лабораторная работа №5

Условие задачи

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

Известны затраты, связанные с назначением i - го исполнителя на j – ю работу, задаваемые матрицей (c i j ) размерностью 66 ( i, j 16 ).

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

Автоматизация решения задачи о назначениях в MS Excel

Данная задачa, которая является совершенно полной и может быть решена с использованием модуля «Поиск решения» электронных таблиц MS Excel. Для этого расположим данные на листе Excel как показано на рис.1.

рис.1

Матрица затрат задана массивом чисел C4:H9, матрица назначений (переменных) – массивом C13:H18, формулы для целевой функции и основных ограничений – по строкам и столбцам матрицы переменных – указаны в соответствующих ячейках на рис.2.

рис.2

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

рис.3

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

рис.4

Автоматизация решения задачи о назначениях в ПЭР

Для решения этой задачи в среде ПЭР необходимо в главном меню программы выбрать пункт «Задача о назначениях».

Далее в режиме ввода новой задачи ввести в ПЭР все необходимые параметры задачи.

После чего ввести числовые данные задачи.

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

рис.4

На первой итерации ПЭР «получает» приведенную матрицу.

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

рис.5

рис.6

рис.7

На первой итерации ПЭР «получает» приведенную матрицу.

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

рис.8

Однако, сам план назначений в табличной форме выводится отдельно как показано на рис.9

рис.9

Автоматизация решения задачи о назначениях в программе Venger

Программа Venger разработана специально для автоматизации процесса решения задачи о назначениях по алгоритму венгерского метода и предназначена для использования в среде ОС Windows.

На итерации «Решение» отображается исходная матрица эффективностей назначений, в которой красным цветом выделены элементы, соответствующие единичным элементам матрицы назначений.

Выделенные элементы являются слагаемыми оптимального значения целевой функции данной задачи.

рис.10

Вывод:  Я

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

v Приобретение навыков автоматизированного решения задачи о назначениях в среде программ Microsoft Excel и ПЭР.

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