Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


Общая постановка задачи о назначениях такова: необходимо выполнить Т1, Т2, …, Тп различных работ, для выполнения которых можно привлечь M1, M2, …, Mn различных исполнителей. Каждый исполнитель может выполнить любую из работ с некоторым показателем эффективности Су (Сц может означать время качественного выполнения i-м работником j-й работы; стоимость выполнения 7-м работником j-й работы; эффективность выполнения работы, выраженную в некоторых условных единицах, и т.п.), при условиях, что каждый исполнитель должен быть назначен на какую-нибудь работу и каждая работа должна быть кем-то выполнена. Требуется так распределить работы между исполнителями, чтобы суммарная эффективность выполнения всех работ (суммарное время на выполнение всех работ, суммарные затраты на выполнение всех работ) была минимальной.


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


п п


ZZ ciyxij ^ ^


7=1 j=1    (26)


п    п


Z xij = 1, j = 1,2,…п; Z xij = 1, i = 1,2,…п,


i=1    j=1


где Xj е {0,1}, Xj = 0 — i-й работник не назначается на j-ю работу; Xj = 1 — i-й работник назначается на j-ю работу.


Таким образом, решение задачи есть матрица X* = [.Xj ], где в каждой строке и каждом столбце только одна единица, остальные — нули.


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


Задачу о назначениях можно считать частным случаем транспортной задачи в классической постановке размерности п»п с объемами производства и потребления, равными единице. Поэтому решать ее можно методом потенциалов. Также задачу о назначениях можно считать примером комбинаторной задачи и отыскать ее решение путем перебора всех допустимых решений. Однако такой метод, очевидно, неэффективен с увеличением числа п.

Скачать в pdf «Экстремальные модели менеджмента и экономики»