Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

121

Таким образом, оптимальный план перевозок имеет вид:

= 10; x

= 20; x

= 10; x

= 10.

Суммарная стоимость перевозок составляет 490.

6.3. Задача о назначениях

Частным случаем классической транспортной задачи (6.1)-

(6.4) является задача о назначениях, которая помимо того, что

сама имеет важное прикладное значение, часто используется, как

вспомогательная при решении дискретных оптимизационных за-

дач различного рода. Практическая суть задачи, из которой и

возникло ее название, заключается в том, что имеется (n) долж-

ностей, на которые могут быть

назначены (n) кандидатов, причем

назначение некоторого i–го кандидата на j-ю должность связано с

расходами равными c

. Необходимо так распределить кандида-

тов на должности, чтобы суммарные расходы были минимальны.

В этих условиях решение (распределение кандидатов)

можно описать вектором x с компонентами x

, которые прини-

мают значение 1 или 0 в зависимости от того, назначается i–ый

кандидат на j–ю должность, или нет. Математическая модель та-

кой задачи имеет вид

∑

→ min (6.18)

при ограничениях

∑

= 1, i = 1,…, n, (6.19)

∑

= 1, j = 1,…, n, (6.20)

∈ {0, 1}, i = 1,…, n, j = 1,…,n. (6.21)

Такая задача относится к классу задач линейного дискрет-

ного (целочисленного, булевого) программирования. В силу аб-

солютной унимодулярности матрицы условий такой задачи (см.

5.2) многогранник условий имеет только целочисленные верши-

ны, поэтому решение такой задачи может быть получено на осно-

ве симплекс-метода (см. 3.5). Так как задача о назначениях явля-

ется

частным случаем транспортной задачи, то она может быть

решена и с использованием метода потенциалов (см. 6.2). Одна-

122

ко более эффективным в вычислительном смысле методом ре-

шения задачи о назначениях является венгерский метод, моди-

фицированный с учетом специфики задачи.

Венгерский метод решения задачи о назначениях

(Эгервари, Кун Г., 1955)

В алгоритме [54] используется матрица стоимости назначе-

ний С = ║c

║

. . . . . c

С = . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . c

Элементам матрицы c

соответствует стоимость соответст-

вующего назначения i–ого кандидата на j–ю должность. В каждом

столбце и каждой строке матрицы при решении задачи о назна-

чении можно выбрать только один элемент (одно назначение, в

соответствии с ограничениями 6.19 - 6.21). Тогда, если ко всем

элементам некоторой строки или некоторого столбца матрицы

добавить (или вычесть) одно и

то же число, то решение (вариант

назначения) не изменится, а изменится только стоимость реше-

ния на такое же число. Такие преобразования матрицы назначе-

ний С называются э к в и в а л е н т н ы м и преобразованиями.

Очевидно, что если из всех элементов строки c

, j = 1,…,n

вычесть минимальный элемент, то в каждой строке появится как

минимум один элемент, равный 0. Аналогичные преобразования

можно произвести со столбцами. Тогда минимальное по стоимо-

сти назначение соответствует выбору таких нулей, по одному в

каждой строке и в каждом столбце (отметим, что их может быть

несколько в каждой строке и в каждом

столбце матрицы С). Нули,

расположенные в различных строках и столбцах матрицы С, на-

зываются н е з а в и с и м ы м и нулями. Если количество неза-

висимых нулей равно n, то задача решена.

Алгоритм состоит в последовательном проведении итера-

ций. На каждой итерации, если число независимых нулей мень

ше, чем n, то производится назначение очередного независимого

нуля, и, если это необходимо, то производятся эквивалентные

преобразования матрицы С. Таким образом, на каждой итерации

число независимых нулей увеличивается на 1.

123

Работа алгоритма начинается с предварительной подготов-

ки матрицы С путем эквивалентных преобразований.

0). Начальное состояние. Производятся предварительные

преобразования матрицы назначений С. Из элементов каждого

столбца матрицы вычитается минимальный элемент, тогда в ка-

ждом столбце будет содержаться элемент равный 0. Соответст-

венно, из элементов каждой строки вычитается минимальный

элемент, тогда и в каждой строке будет содержаться нулевой

элемент. Такая матрица обозначается как С

= С

, s=0.

Производится выбор независимых нулей. Выбирается некото-

рый элемент равный 0 и помечается звездочкой (0*), строка и

столбец, соответствующие данному помеченному нулю, вычерки-

ваются. В оставшейся части матрицы С производится аналогич-

ная операция, и так далее до тех пор, пока в оставшейся части

матрицы будут содержаться нули.

Номер итерации k = 1; s = 0.

Произвольная k-ая итерация состоит

в выполнении нескольких

шагов. Рассмотрим их содержание.

1). Анализ оптимальности решения. Если количество поме-

ченных нулей (0*) равно n (размерности матрицы назначений С),

то процесс окончен – найдено оптимальное назначение, которое

определяется помеченными (*) независимыми нулями.

2). Анализ кандидатов. Производится анализ нулевых эле-

ментов матрицы С

, которые могут быть кандидатами в незави-

симые нули.

А). Производится выделение знаком (+) столбцов, соответст-

вующих помеченным (0*) нулям (независимым нулям). Выделен-

ные (+) столбцы будем называть з а н я т ы м и с т о л б ц а м и,

аналогично, в дальнейшем выделенные знаком (+) строки будем

называть з

а н я т ы м и с т р о к а м и. Нули, непомеченные (*)

и содержащиеся в занятых строках или столбцах будем называть

з а н я т ы м и нулями, в отличие остальных нулей, которые бу-

дем называть с в о б о д н ы

м и нулями.

Б). Производится анализ свободных нулей.

Если в незанятых столбцах и строках не содержится свобод-

ных нулей, то производится выполнение пункта 4 (эквивалентные

преобразования матрицы).

В противном случае в незанятых столбцах матрицы С

содер-

жится непомеченный (*) нуль, тогда возможно два случая:

124

а). В строке с непомеченным нулем нет помеченного (*) нуля;

тогда непомеченный нуль помечается (0′), и производится

переход к пункту 3 (увеличение числа независимых нулей).

б). В строке с непомеченным нулем

есть помеченный (*) нуль;

тогда: - непомеченный нуль помечается (0′);

- строка выделяется знаком (+) и является занятой

строкой;

- снимается отметка с занятого столбца, соответст-

вующего помеченному (0*) нулю (знак (+) обводит-

ся кружком ⊕ и считается незанятым);

- производится переход к пункту Б) данного шага.

Данный шаг заканчивается переходом либо к шагу 3, с после-

дующим увеличением

числа независимых нулей и переходом к

шагу 1, либо к шагу 4, с преобразованием матрицы назначений С

в С

s+1

и последующим возвратом к выполнению шага 2.

3). Увеличение числа независимых нулей. Строится цепоч-

ка нулей, состоящая из (0′) и (0*). Начиная с последнего помечен-

ного нуля (0′), в столбце выбирается (0*), от него по строке произ-

водится переход к (0′), далее снова по столбцу к (0*) и т. д. Про-

цесс построения цепочки оборвется на некотором (0′) (возможно,

что и на первом).

Производится замена

пометки в образованной цепочке: (0*)

заменяется на (0); и (0′) заменяется на (0*). Иначе, снимается от-

метка с (0*), а (0′) заменяется на (0*). Число независимых нулей,

отмеченных как 0*, становится на 1 больше.

Снимается выделение строк и столбцов («занятость» строк и

столбцов). Снимается отметка (0′).

Итерация закончена; производится переход на шаг 1; k = k + 1.

4). Эквивалентные преобразования матрицы. Среди эле-

ментов С

, соответствующих незанятым строкам и столбцам, вы-

бирается минимальный элемент, который вычитается из этих

свободных элементов и добавляется к элементам, стоящих на

пересечении занятых строк и столбцов. Полученная матрица С

s+1

эквивалентна матрице С

и содержит свободные нули; s = s+1.

В случае, когда задача о назначениях решается на макси-

мум целевой функции, алгоритм отличается выполнением 0-го

шага.

0). При выполнении предварительных преобразований мат-

рицы назначений в каждом столбце выбирается максимальный

125

элемент, из которого последовательно вычитаются все осталь-

ные элементы столбца. Затем в каждой строке выбирается мини-

мальный элемент, который вычитается из каждого элемента дан-

ной строки.

Рассмотрим пример.

Пример.

Применим рассмотренный алгоритм для решения задачи о

назначениях, если матрица стоимости назначений имеет вид

0). Произведем предваритель-

ные преобразования матрицы С.

Из элементов каждого столбца и

каждой строки вычтем минималь-

ные элементы. В результате по-

лучим матрицу С

Итерация 1.

1). Анализ оптимальности ре-

шения. Количество помеченных

нулей (0*) равно 3, что меньше

размерности С

(n=5).

2). Анализ кандидатов.

А). Производится выделение

знаком (+) 1, 2, 3 столбцов.

Б). Производится анализ свободных нулей.

б). В строке 2 с непомеченным нулем есть помеченный (*)

нуль; непомеченный нуль помечается (0′); строка выделяется

знаком (+) и является занятой строкой; снимается отметка со 2-го

занятого столбца, соответствующего помеченному (0*) нулю (знак

(+) обводится кружком ⊕ и считается незанятым). Переход

на на-

чало пункта Б.

б). В строке 4 с непомеченным нулем есть помеченный (*)

нуль; непомеченный нуль помечается (0′); строка выделяется

знаком (+); снимается отметка с 1-го занятого столбца, соответст-

вующего помеченному (0*) нулю. Переход на начало пункта Б.

3 5 5 2 2

5 3 4 3 1

= 4 5 6 3 3

2 3 7 2 1

7 7 8 4 5

1 2 1 0* 1

3 0* 0 1 0

= 1 1 1 0 1

0* 0 3 0 0

3 2 2 0 2

+ + +

1 2 1 0* 1

3 0* 0 1 0

= 1 1 1 0 1

0* 0 3 0 0

3 2 2 0 2

126

В незанятых столбцах и стро-

ках не содержится свободных (не

помеченных) нулей. Производит-

ся выполнение пункта 4.

Матрица С

имеет вид:

4). Эквивалентные преобразования матрицы.

Минимальный свободный эле-

мент равен 1, он вычитается из

незанятых элементов 1,3,5 строки

и добавляется к элементам,

стоящим на пересечении 4-го

столбца и 2, 4 строки.

В результате получим матрицу С

2). Анализ кандидатов.

Б). Производится анализ свободных нулей.

б). В строке 1 с непомеченным

нулем есть помеченный (*) нуль.

Переход на начало пункта Б.

а). В строке 3 с непомеченным

нулем нет помеченного (*) нуля;

тогда непомеченный нуль поме-

чается (0′), и производится пере-

ход к пункту 3.

3). Увеличение числа независимых нулей. Строится цепочка

нулей, состоящая из (0′) и (0*), начиная с последнего помеченного

(0′): 0′(3,1) - 0*(4,1) - 0′(4,2) - 0*(2,2) - 0′(2,3). Производится замена

в элементах цепочки: 0*(3,1) - 0(4,1) - 0*(4,2) - 0(2,2) - 0*(2,3).

Итерация 1 закончена

Итерация 2.

1). Анализ оптимальности решения. Количество помеченных

нулей (0*) равно 4 (<5).

2). Анализ кандидатов.

А). Производится выделение знаком (+) 1, 2, 3, 4 столбцов.

Б). Производится анализ свободных нулей.

б). В строке 1 с непомеченным нулем есть помеченный (*)

нуль; непомеченный нуль помечается (0′); строка выделяется (+);

⊕ ⊕

1 2 1 0* 1

3 0*

0′

1 0 +

= 1 1 1 0 1

0′

3 0 0 +

3 2 2 0 2

0 1 0 0* 0

3 0*

0′

2 0 +

= 0 0 0 0 0

0′

3 1 0 +

2 1 1 0 1

⊕

0′

1 0 0* 0 +

3 0*

0′

2 0 +

0′

0 0 0 0

0′

3 1 0 +

2 1 1 0 1

127

снимается отметка с 4 столбца;

производится переход на пункт Б.

Б).

б). В строке 3 с непомеченным

нулем есть помеченный (*) нуль.

Переход на начало пункта Б.

Б).

б). В строке 4 с непомеченным нулем есть помеченный (*)

нуль. Переход на начало пункта Б.

Б). б). В строке 2 с непомеченным нулем есть помеченный (*)

нуль. Переход на

начало пункта Б.

Б). а). В строке 5 с непомеченным нулем нет помеченного (*)

нуля. Переход на пункт 3.

3). Увеличение числа независимых нулей. Строится цепочка

нулей, состоящая из (0′) и (0*), начиная с последнего помеченного

(0′): 0′(5,4) - 0*(1,4) - 0′(1,5). Производится замена в элементах

цепочки: 0*(5,4) - 0(1,4) - 0*(1,5).

Итерация 2 закончена.

Итерация 3.

1). Анализ оптимальности ре-

шения. Количество помеченных

нулей (0*) равно 5, что равно

размерности матрицы.

Получено оптимальное реше-

ние: x

=1.

Оптимальное значение целе-

вой функции равно 2 + 4 + 4 + 3 + 4 = 17.

Контрольные вопросы

1. В чем состоит специфика транспортной задачи по сравне-

нию с другими задачами линейного программирования ?

2. В чем заключается преимущество метода минимального

элемента при построении опорного плана транспортной задачи ?

3. В чем смысл критерия оптимальности решения в методе по-

тенциалов ?

4. Каким образом учитываются возможности движения груза

при решении транспортной задачи в сетевой

постановке ?

5. За счет чего обеспечивается целочисленность решения за-

дачи о назначениях при использовании венгерского метода ?

⊕ ⊕ ⊕ ⊕

0 1 0 0*

0′

0* 2 0 +

=0*0 0

0′

0 +

0′

0* 3 1 0 +

2 1 1

0′

0 1 0 0 0*

3 0 0* 2 0

= 0* 0 0 0 0

0 0* 3 1 0

2 1 1 0* 1

128

7. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО

ПРОГРАММИРОВАНИЯ

7.1. Постановка задач математического программирования

Проанализируем особенности построения модели принятия

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

Пусть концептуальная модель принятия решения задается сле-

дующим содержательным описанием.

Задача.

Для инженерного оборудования позиционного района от-

дельного командно-измерительного комплекса (ОКИК) необходи-

мо обеспечить четыре строительные площадки материалами,

которые могут быть доставлены с баз, расположенных в трех

близлежащих населенных пунктах, численностью соответственно

2, 5 и 8 тысяч жителей. Требуется спланировать, каким образом

следует осуществить перевозки материалов, с тем чтобы мини-

мизировать расход бензина,

необходимого для работы автомо-

бильного транспорта (грузоподъемность одной машины 5 т).

Потребность в материалах на строительных площадках

(СП) составляет соответственно 25, 30, 15, 20 тонн. На складах

населенных пунктов (НП) имеется соответственно материалов в

количестве 62, 45, 37 тонн. Расход бензина (в литрах), необходи-

мого для доставки материалов одной машиной, задается табли-

цей

СП

НП

Анализ ситуации принятия решения.

Решение заключается в планировании перевозок материа-

лов из населенных пунктов на строительные площадки ОКИК. На

данное решение влияют потребности в материалах на строи-

тельных площадках и имеющиеся ресурсы на складах населен-

ных пунктов, и не оказывает влияния численность жителей. Об-

щее количество материалов на всех базах достаточно для обес-

печения потребностей

всех строительных площадок.

129

Решение должно содержать данные о том, сколько машин с

грузом материалов следует отправить из какого-либо населенно-

го пункта на некоторую строительную площадку ОКИК. Таким об-

разом, решение (план перевозок) можно описать совокупностью

переменных x

≥ 0, характеризующих количество машин, необхо-

димых для перевозки груза из i-го населенного пункта на j-ую

строительную площадку.

Разработка модели принятия решения.

Модель принятия решения в общем случае описывается

конструкцией вида (Δ,f), где Δ - множество допустимых решений,

f - правило выбора решения. Решение x однозначно описывается

вектором x = ║x

║, ∀x

≥ 0, i = 1,2,3; j = 1,2,3,4 компоненты кото-

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

возки материалов из i-го пункта на j-ую площадку. Допустимое

решение x ∈ Δ должно быть практически реализуемо, для чего

оно должно удовлетворять условиям поставленной задачи. Сле-

довательно, прежде всего, необходимо провести формализацию

условий задачи в виде ограничений некоторого вида.

На каждую

строительную площадку следует доставить не-

обходимое количество материалов. Так как суммарное количест-

во материалов на всех базах больше, чем это необходимо для

проведения работ на строительных площадках, то потребности в

материалах могут быть полностью удовлетворены. Эти условия

можно формально описать совокупностью ограничений

20 5x 15, 5x 30, 5x 25, 5x

====

∑∑∑∑

====

С каждой базы может быть выделено материалов не боль-

ше, чем их имеется там в наличии. Эти условия могут быть фор-

мально описаны совокупностью неравенств

37. 5x 45, 5x 62, 5x

≤≤≤

∑∑∑

===

В задаче следует найти решение, минимизирующее сум-

марный расход бензина, необходимого для доставки грузов. Сле-

довательно, качество решения можно описать следующей целе-

вой функцией

130

xf L(x)

∑∑

где f

- количество бензина, необходимого для передвижения од-

ной машины от i-го населенного пункта до j-ой строительной

площадки (см. таблицу). Наилучшим будет решение с наимень-

шими значениями целевой функции L(x). Тогда правило выбора

будет иметь вид

xf L(x)

∑∑

= → min .

В целом задача выбора наилучшего решения x* описыва-

ется следующей конструкцией

x* = arg max L(x),

x∈∆

где Δ - множество решений, удовлетворяющих поставленным ог-

раничениям.

Анализ задачи показывает, что целевая функция L(x) яв-

ляется линейной функцией; множество допустимых альтернатив

(решений) задается линейными ограничениями. Следовательно,

разработанная модель принятия решения является задачей ли-

нейного программирования и решение может быть найдено на

основе использования соответствующих алгоритмов (симплекс-

метода, например).

Выбор решения.

Нахождение наилучшего решения основывается на исполь-

зовании алгоритма симплекс-метода, для чего задача должна

быть представлена в каноническом виде, то есть неравенства на

основе ввода дополнительных переменных x

д1

, x

д2

, x

д3

сводятся к

виду равенств. Тогда задача принятия решения в каноническом

виде

xf L(x)

∑∑

= → min .

при ограничениях

= 25

= 30

= 15