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

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


Обозначим Cj показатели эффективности назначений (например, время выполнения i-м исполнителем j-й работы) и занесем исходную информацию в таблицу (табл. 2.11).


Т а б л и ц а 2.11


Показатели эффективности


Исполните


ли


Работы


г,


г


1


T


1 n


м


C11


C12


c1j


c1n


м2


C21


c22


C2j


c2n


м


Ci2


Cij


cin


мп


cn1


cn2


Cnj


c


nn

Решением задачи будет являться набор переменных xij, каждая из которых принимает одно из двух значений: Xj = 0 — i-й работник не назначается на j-ю работу, Xj = 1 — i-й работник назначается на j-ю работу.


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


n П


Целевая функция задачи:    CjXj ^ min .


г=1 j=1


П


Ограничения задачи двух типов: по назначению исполнителей ^Xj = 1, j = 1,2,…,n ; по вы-


i=1


n


полнению работ: ^xij— = 1, i = 1,2,…,n при xij> 0, где i = 1,2,…,n; j = 1,2,…,n.


j=1


Задачу о назначениях можно считать частным случаем транспортной задачи в классической постановке с n поставщиками и n потребителями однотипного товара. Поэтому задачу о назначениях можно решить, как транспортную задачу методом потенциалов. Возможность применения «транспортных» алгоритмов для решения задач распределительного типа объясняется тем, что транспортные и распределительные задачи близки по структуре целевой функции и типу ограничений. В качестве стоимостей перевозок в задачах распределительного типа выступают показатели эффективности назначений исполнителей на работы. Количество производителей (поставщиков) и количество потребителей в задачах о назначениях равно n. Различием является лишь то, что величины спроса и предложения для каждого производителя и каждого потребителя равны единице.

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