Файл: пензенский государственный университет политехнический институт.docx

Применить к модели (13) – (16) эквивалентное преобразование прямоугольной матрицы затрат в квадратную. Результатом является получение эквивалентной модели (17) – (20).
Решить задачу, описываемую соотношениями (17) – (20), венгерским методом или методом Мака.

В полученном решении выделить подматрицу

(x_ij) ,

i 1, m,

j 1, n. Данная подматрица является оптимальным решением открытой задачи о назначениях.

Текст программы для нахождения решения открытой задачи о

назначениях средствами математического пакета «Mathcad» представлен в Приложении А. Результаты работы программы представлены на рисунке 5.

Рисунок 5 – Результаты поиска решения открытой задачи о назначениях

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

n

n

Пусть математическая модель задачи о назначениях с элементами матрицы затрат произвольного знака имеет вид:

f(X)  _

_c_ijx_ij min, 1	(21)
, j 1, n,	(22)
1, i  1, n,	(23)
, i, j 1, n,	(24)

i1 j

_x_ij 1

n
i1

n

^^xij^

j1

где c_ij
 0 .

x_ij{0,1}

Эквивалентное преобразование матрицы затрат с элементами произвольного знака в матрицу затрат с неотрицательными элементами основано на теореме 1 и формулируется так:

найти минимальный элемент матрицы С :

min  min c_ij,

ij

i1, n,

j 1, n.

перейти к матрице затрат Q , построенной по правилу:

^qij

 c_ij min ,

i1, n,

j 1, n.

Результатом применения данного преобразования является переход к простейшей линейной модели вида:

f	nn (X)  _ n	^qij	x_ij min,	(25)
_x_ij 1,		j 1, n,		(26)

i1

^^xij^

n

1, i  1, n,	(27)
, i, j 1, n,	(28)

j1

где
^qij
 0 .

x_ij{0,1}

Модели (25) – (28) и (21) – (24) эквивалентны друг другу. Отсюда можно описать алгоритм решения задачи о назначениях (21) – (24).

Применить к модели (21) – (24) эквивалентное преобразование матрицы затрат с элементами произвольного знака в матрицу затрат с неотрицательными элементами. Результатом является получение эквивалентной модели (25) – (28).
Решить задачу, описываемую соотношениями (25) – (28), венгерским методом или методом Мака.

Текст программы для нахождения решения задачи о назначениях с элементами матрицы затрат произвольного знака средствами математического пакета Mathcad представлен в Приложении Б. Результаты работы программы представлены на рисунке 6.

Рисунок 6 – Результаты поиска оптимального решения задачи о назначениях с элементами матрицы затрат произвольного знака

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

Обозначим через

I {1,2,.., n}

множество индексов исполнителей и

работ. На множестве Iустановим бинарное отношение допустимых назначений

R_д_._н_.{(i, j) | назначение (i, j)

допустимо},

и наложим на неизвестные

x_ij, представляющие назначение исполнителя iна

работу j, дополнительное ограничение:

где i 1,..., n,
j 1,..., n.

^xij

 0, если (i, j)  R_д_._н_.,

Тогда математическая модель задачи с недопустимыми назначениями принимает вид:

nn f(X)  _c_ijx_ij min, i1 j1	(29)
n _x_ij 1, j 1, n, i1	(30)
n _^x_ij^¹, i1, n, j1	(31)
x_ij 0 , (i, j)  R_д_._н_.,	(32)
x_ij{0,1}, (i, j)  R_д_._н_..	(33)