Решение задачи о назначениях как задачи целочисленного программирования

Постановка задачиПусть имеется пять исполнителей, и требуется выполнить работы на пяти объектах. Известны значения себестоимости c_ij ( ; ) выполнения i-м исполнителем работы на j-м объекте. Необходимо так закрепить исполнителей за объектами работ, чтобы суммарная себестоимость выполнения всех работ была минимальной. Исходная информация представлена в таблице 5.1.

Таблица 3.1 - Значения себестоимости выполнения работ

Решение.

Математическая модель задачи имеет вид

Найти такой план назначения исполнителей на работы X = {x_ij} (i=1,…,5; j=1,...,5)

- чтобы обеспечить выполнение всех работ с минимальными суммарными затратами

-при следующих ограничениях на X:

каждый исполнитель может выполнять работы только на одном объекте

,

каждая работа на объекте может выполняться только одним исполнителем

,

условие целочисленности .

Переменные x_ij = 1, если i‑й исполнитель выполняет работы на j‑м объекте (только j-м), x_ij = 0 в противном случае.

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

Этап 1. Получение нулей в каждой строке и каждом столбце. Находим минимальный элемент в каждой строке исходной таблицы (табл. 3.2). Из каждого элемента строки вычтем найденное минимальное значение и получим таблицу 3.3.

В каждом столбце таблицы 3.3 находим минимальный элемент и вычитаем его из каждого элемента соответствующего столбца. Получаем таблицу 3.4.

Этап 2. Проверка полученного решения на оптимальность.

Ищем строку, содержащую наименьшее число нулей, отмечаем звёздочкой один из них и зачёркиваем все остальные нули строки и столбца, содержащего нуль со звёздочкой. Аналогичные операции последовательно выполняем для всех строк таблицы. Если число нулей, отмеченных звёздочкой, равно n=5, то решение является оптимальным (задача решена), в противном случае осуществляется переход к следующему этапу.

В рассматриваемом примере (табл. 3.5) количество отмеченных звёздочкой нулей равно 3, следовательно, оптимальное решение задачи еще не получено, переходим к следующему этапу.

Этап 3. Поиск минимального набора строк и столбцов, содержащих нули.

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

Для таблицы 3.5 в качестве такого минимального набора, содержащего все нули таблицы можно использовать строки И₂, И₅ и столбец O₃. Вычеркивая эти строки и столбец, все нули таблицы оказываются вычеркнутыми (табл. 3.6).

Этап 4. Перестановка некоторых нулей.

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

Переходим ко второму этапу венгерского метода. Проверим полученное (в табл. 3.7) решение на оптимальность. Количество помеченных звёздочкой нулей равно 4, следовательно, это решение не оптимально. Для его улучшения еще раз выполним операции третьего и четвертого этапов алгоритма. Получим решение, представленное в таблице 3.8.

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

ВыводОптимальный план назначения исполнителей на работы имеет вид:

Согласно оптимальному решению исполнители на работы должны быть распределены следующим образом: первый исполнитель на третий объект; второй исполнитель – на четвёртый объект; третий исполнитель – на пятый объект; четвёртый исполнитель – на второй объект; пятый исполнитель – на первый объект. При этом суммарная себестоимость выполнения всех работ будет минимальна и составит Z_min = 25 + 23 + 37 + 24 + 34 = 143 ден. ед.

Дата добавления: 2014-12-09; просмотров: 237; Нарушение авторских прав

Мы поможем в написании ваших работ!