Файл: Теория систем2.pdf

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 типа автомобильных деталей. Оно закупает литье, подвергаемое токарной обработке, сверловке, шлифовке.