37

задачи.

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

Пусть для выполнения пяти различных работ имеется пять человек. Из отчетных данных известно, какое время требуется каждому из них для выполнения каждой работы. Эти данные приведены в таблице.

В данном случае величины Cij представляют собой затраты времени

каждого работника на выполнение каждой из работ, а величины xij равны 1

или 0, причем xij =1, если работник i назначен на работу j, и 0 во всех

остальных случаях.

Таким образом, задача сводится к минимизации функции

n n

Z = ∑∑Cijxij i=1 j=1

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

n

∑xij =1, j =1,n;

i=1

n

∑xij =1, i =1,n;

j=1

39

Метод решения сводится к прибавлению констант к строкам и столбцам и вычитанию их из строк и столбцов до тех пор, пока достаточное число величин Cij не обращается в нуль, что дает решение, равное нулю.

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

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

Из столбцов и строк было вычтено всего 10 единиц. Поэтому для правильной оценки любого решения необходимо прибавить к результату 10 единиц.

Прежде всего стремятся отыскать решение, включающее лишь те

41

Использованы только 4 линии, а порядок матрицы пятый, следовательно, нулевые клетки не содержат оптимального решения.

Шаг 2. Выбрать наименьший элемент, через который не проведена линия (в нашем случае – это 1 в клетке (5,2)).

Шаг 3. Вычесть это число из всех элементов, через которые не проведена ни одна линия, и прибавить его ко всем элементам, через которые проведены 2 линии. Другие элементы оставить без изменений.

Этот шаг должен приводить к появлению нуля в клетке, где его ранее не было. В нашем случае – в клетке (5,2).

Шаг 4. Определить, имеется ли решение среди нового набора нулей. (В нашем случае оно отсутствует) Если решение не обнаруживается, то вернуться к шагу 1 и выполнять алгоритм до тех пор, пока не будет найдено решение.

Теперь наименьшее незачеркнутое число 2. Вычтем его из всех элементов, через которые не проведена ни одна линия и прибавим его ко всем элементам, зачеркнутым дважды. Получим три новых нуля в клетках (3,1), (4,1), (5,1). Среди нового набора нулей пытаемся отыскать решение.

42

Оно помечено в матрице круглыми скобками:

Получено решение: x13=1, x25=1, x34=1, x42=1, x51=1.

Ему соответствуют суммарные затраты времени, равные 13, что на единицу меньше начального допустимого решения.

При выборе целевой функции, кроме описанного, возможно несколько подходов:

1.Максимизация вероятности успешного выполнения каждым исполнителем работы, на которую он назначен, т.е. требуется найти

максимум целевой функции

n n

Z= ∑∑log(Pij )xij ,

i=1 j=1

где Pij есть вероятность того, что исполнитель Ii успешно выполнит

работу J j . Оценки вероятности того, что исполнитель с определенными

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

2.Минимизация вероятности неуспешного в целом назначения на все виды работ, т.е. требуется найти минимум целевой функции

43

n n

Z = ∑∑log(1 − Pij )xij .

i=1 j=1

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

n n

Z = ∑∑Pij xij . i=1 j=1

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

n n

Z = ∑∑(1 − Pij )xij .

i=1 j=1

2.3.2. Модель последовательного назначения исполнителей

Рассмотрим модель последовательного назначения исполнителей. В

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

относительно мало. Рассмотрим один из подходов к решению таких задач. Предположим, что имеется n исполнителей для выполнения n работ, причем работы появляются в случайном порядке и исполнители этих работ назначаются также в случайном порядке. После того как определенному исполнителю поручается выполнение той или иной работы, его кандидатура не рассматривается при последующих возможных назначениях. Далее, за выполнение каждой j-й работы

44

устанавливается денежное или какое-то иное вознаграждение Xj ,

имеющее ценность xj , и для каждого исполнителя i производится оценка

характера j-й работы, которую он выполняет, и, кроме того, 0 ≤ pi ≤ 1. Это означает, что если, например, оценка вероятности успешного ведения дел адвокатом равна 1.0. то он всегда выигрывает дело, при оценке 0.0 он всегда проигрывает его, а при оценке 0.5 вероятности выиграть или проиграть дело равны. Очевидно, оптимальным является следующий принцип управления: исполнителю с наибольшей оценкой вероятности успешного выполнения им работы следует поручать работу с наивысшей оплатой, а исполнителю с более низкой оценкой – работу с меньшей оплатой.

2.3.3. Вопросы для самопроверки

1.Вспомните, какая задача называется задачей о назначениях?

2.Какой смысл, в случае задачи о назначениях, имеют элементы матрицы

(Cij )?

3.Какие значения могут принимать неизвестные величины xij ?

4.Запишите целевую функцию и ограничения к задаче о назначениях.

5.Сформулируйте и докажите теорему 1.

6.Сформулируйте теорему 2. Объясните, почему ее доказательство очевидно.

7.К чему сводится метод решения задачи о назначениях?

8.Опишите алгоритм решения задачи о назначениях.

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

45

10.Какими способами может быть выбрана целевая функция в задаче о назначениях?

11.Опишите модель последовательного назначения исполнителей.

2.3.4. Задачи для самостоятельного решения

Решите следующие задачи о назначениях: а)

2.4. Общая линейная распределительная задача

В общей распределенной задаче фигурируют ресурсы и работы,

46

измеряемые в различных единицах. Например, завод выпускает n различных изделий в объемах x1 ,x2 ,...,xn , используя различные комбинации m станков разного типа.

Для выпуска единицы продукции j требуется затрата aij единиц времени станка i, j =1,m; i =1,n. Выполнение одной и той же работы на

одном станке (например, более старом) может занимать больше времени, чем на другом (более новом). Общий ресурс станочного времени на планируемый период для i-ого станка составляет bj . Известна прибыль на каждую единицу продукции j, равная Сj . Все исходные данные сводятся в таблицу.

Эту задачу можно свести к максимизации некоторой линейной функции, на которую наложены линейные ограничения в виде неравенств.

Рассмотрим метод решения таких задач на примере.

Небольшое предприятие выпускает 2 типа автомобильных деталей. Оно закупает литье, подвергаемое токарной обработке, сверловке, шлифовке.