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

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

101

Если g

≤ L

- текущий рекорд), то Δ

исключается из списка

кандидатов Q и производится переход на шаг 4.

Если g

> L

, тогда,

а) если при расчете оценки получено целочисленное ре-

шение x

, то рекордом становится новое значение

, x

. При этом ветвление Δ

исключается из спи-

ска кандидатов Q и производится переход на шаг 4;

б) если x

нецелочисленно, то выполняется шаг 3.

Шаг 3.- Ветвление. Согласно правилу ветвления производит-

ся разбиение Δ

на два подмножества Δ

= Δ

q+1

∪ Δ

q+2

; при этом

q+1

∩ Δ

q+2

= ∅. Далее Δ

исключается из списка кандидатов Q, а

q+1

и Δ

q+2

в этот список добавляются; q = q+2. Происходит пере-

ход на шаг 4.

Шаг 4.- Анализ списка кандидатов.

Если Q = ∅, тогда, процесс заканчивается. При этом,

если L

= -∞, то допустимых решений нет;

если L

> -∞, то решение x

- оптимально.

Если Q ≠ ∅, производится переход на шаг 1.

Конечность алгоритма, построенного по данной схеме, сле-

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

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

кивании кандидатов из списка.

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

1. В чем состоят особенности задач дискретного программиро-

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

граммирования ?

2. Какие различают группы методов решения задач целочис-

ленного программирования. В чем их особенность ?

3. Каким образом получить решение методом округления.

Сколько вариантов округления может быть, как нужно выбирать

один из вариантов ?

4. В каких

ситуациях решение задач целочисленного програм-

мирования может быть получено непосредственно на основе ис-

пользования непрерывных методов ?

5. В чем суть метода отсечений. Какие требования предъяв-

ляются к отсечению. Как его построить ?

6. В чем суть метода ветвей и границ; чем определяется его

эффективность; какие задачи можно решать с его помощью ?

102

6. СПЕЦИАЛЬНЫЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО

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

Ряд задач математического программирования, имеющих

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

фическими особенностями, позволяющими строить вычислитель-

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

ются в общих случаях. Это касается, прежде всего, задач линей-

ного и дискретного программирования. Рассмотрим здесь некото-

рые наиболее известные и разработанные в алгоритмическом

смысле задачи.

6.1. Транспортная задача

В 2.2 в качестве примера модели математического про-

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

дача. Транспортная модель является частным случаем общей

сетевой модели оптимизации, интерес к которым связан с тем,

что в рамках терминологии сетевых (графовых) моделей описы-

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

нием системами различной природы. Особенности математиче-

ской

структуры сетевых моделей позволяют строить эффектив-

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

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

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

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

тельности.

Представим транспортную модель в следующем виде [23,

30, 34. Имеется:

- множество поставщиков A = {A

, i = 1,…, m};

- множество потребителей B = {B

, j = 1,…, n}.

103

Каждому поставщику соответствует объем имеющегося у него

ресурса a

, а каждому потребителю сопоставляется объем необ-

ходимого для него ресурса b

. Предполагается, что каждый по-

ставщик соединен с каждым потребителем, т.е. множество дуг

такой сети E = A × B. Задана функция c: E → R

, характеризую-

щая некоторое качество (время, стоимость, и т.п.) перевозки по

дуге e

= (A

, B

) ∈ E

В этом случае математической конструкцией, описывающей

решение, может являться вектор

x =

,....,x

,...., x

)

= ║x

║,

компоненты которого x

характеризуют объем перевозок от по-

ставщика A

к потребителю B

. Ограничения накладываются на

объем продукции, вывозимой от i-го поставщика, и количество

продукции, которую необходимо завести j-му потребителю. Це-

левая функция характеризует суммарные расходы на все такие

перевозки.

Тогда математическая модель классической транспортной

задачи имеет вид:

∑

→ min (6.1)

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

∑

≤ a

, i = 1,…, m, (6.2)

∑

≥ b

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

≥ 0, i = 1,…, m, j = 1,…,n. (6.4)

В ситуациях, когда имеется равенство суммарного ресурса

у всех поставщиков и суммарных потребностей всех потребите-

лей,

∑

, (6.5)

неравенства в ограничениях транспортной модели приобретают

вид равенств.

∑

→ min (6.6)

104

∑

= a

, i = 1,…, m, (6.7)

∑

= b

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

≥ 0, i = 1,…, m, j = 1,…,n. (6.9)

Такая задача называется стандартной (закрытой) транс-

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

портная задача может быть сведена к стандартной путем введе-

ния фиктивных поставщиков (потребителей), объем ресурсов (по-

требностей) которых равен разности левой и правой части в ог-

раничениях (6.2) (или (6.3)).

Транспортная задача (6.6)-(6.9) описывается линейными

ограничениями и линейной целевой

функцией, следовательно,

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

нейного программирования (симплекс-метод, например). Размер-

ность такой задачи равна (m+n)×(mn). Однако для решения

транспортных задач был разработан специализированный алго-

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

задачи. Рассмотрим, в чем состоят эти особенности.

Каждой переменной x

соответствует перевозка от i-го по-

ставщика к j-му потребителю. Соответственно тому, как все пере-

менные x

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

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

перевозки на запланированные и незапланированные.

Обозначим

- множество номеров пунктов производства; M = {1,...,m};

- множество номеров пунктов потребления; N = {1,...,n}.

Тогда все возможные перевозки задаются множеством

J = M × N.

В этом случае обозначим через

S = {(i,j)∈J│ x

>0} - множество запланированных (базисных)

перевозок;

Q = {(i,j)∈J│ x

=0} - множество незапланированных (небазис-

ных) перевозок.

Как в любой задаче линейного программирования число

базисных переменных опорного решения не превышает числа

ограничений, так и здесь число базисных перевозок не превыша-

ет │S│ ≤ (m + n). Вместе с тем специфика транспортной задачи

такова, что любую строку матрицы условий можно выразить как

105

линейную комбинацию остальных, т.е. ранг системы ограничений

равен (m+n-1). Действительно, матрица условий имеет вид

⎪

⎭

⎪

⎬

⎫

m-строк

⎪

⎭

⎪

⎬

⎫

n-строк

Тогда последняя

строка А является линейной комбинацией первых (m+n-1) строк:

m+n

∑

−

Следовательно, det A = 0 и в базисе S содержится (m+n-1)

переменная, т.е.rang A = m+n-1. Тогда в любой транспортной за-

даче может быть запланировано только (m+n-1) перевозка.

Следующая особенность транспортной задачи заключается

в том, что, как отмечалось в 5.2, матрица условий удовлетворяет

достаточным условиям абсолютной унимодулярности. Тогда мно-

гогранник решений транспортной задачи является целочислен-

ным при любом целочисленном векторе

ограничений, а следова-

тельно, все опорные решения и оптимальное решение будут це-

лочисленны.

Для решения транспортной задачи был разработан специа-

лизированный метод - метод потенциалов [45], суть которого со-

стоит в том, что, начиная с некоторого опорного решения (множе-

ство запланированных перевозок), последовательно анализиру-

ется его оптимальность. Если решение не оптимально, то нахо

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

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

базиса. Для расчетов по методу потенциалов используется таб-

лица, элементами которой являются стоимости перевозок c

, i =

1,…, m, j = 1,…,n. Таким образом, специализированный метод

потенциалов более эффективен для решения транспортных за-

дач, т.к. он оперирует с задачей размерности m×n, в отличие от

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

1 1 … 1 0 0 … 0 0 . . . . . 0 0 … 0

0 0 … 0 1 1 … 1 0 . . . . . 0 0 … 0

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

A = 0 0 … 0 0 0 … 0 0 . . . . . 1 1 … 1

1 0 … 0 1 0 … 0 1 . . . . . 1 0 … 0

0 1 … 0 0 1 … 0 0 . . . . . 0 1 … 0

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

0 0 … 1 0 0 … 1 0 . . . . . 0 0 … 1

106

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

мерности (m+n)×(mn).

6.1.1. Построение исходного опорного плана

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

Построение исходного опорного плана (решения) транс-

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

позволяющих вывести все товары от поставщиков и обеспечи-

вающих всех потребителей. Такие перевозки характеризуются

переменными

{ x

> 0 │(i,j)∈S ⊆ J = M×N } .

Рассмотрим два способа построения исходного опорного

плана перевозок. При расчетах опорного решения используется

два вектора

= (А

,...,А

) – вектор, характеризующий использование

ресурсов, имеющихся у поставщиков;

= (В

,...,В

) – вектор, характеризующий текущее удовле-

творение запросов потребителей.

Значения компонент данных векторов изменяются на каждой на

k-ой итерации метода.

Результаты расчетов при построении исходного опорного

плана заносятся в таблицу вида

………

……

…… ……

………

……… b

Здесь a

, b

, c

- исходные данные транспортной задачи: a

- ко-

личество ресурса i-го поставщика; b

- запросы j-го потребителя; c

и x

– соответственно стоимость перевозки единицы груза и объ-

ем перевозки от i–го поставщика j–му потребителю.

Метод северо-западного угла.

Поиск опорного плана начинается с северо-западного (пра-

вого верхнего) угла матрицы перевозок.

107

0). Исходное состояние: номер итерации k = 1;

= (А

,...,А

), A

= a

, i ∈ M;

= (В

,...,В

), B

= b

, j ∈ N;

текущая перевозка (i,j) = (1,1).

Каждая k-я итерация состоит в выполнении 3-х шагов:

а). Вычисляется объем перевозки (i,j)

= min {A

, B

} .

Пересчитываются значения компонент векторов A и B:

k+1

= A

- x

;

k+1

= B

- x

б).

Если A

k+1

= 0, i∈M и B

k+1

= 0, j∈N, то процесс окончен, т.е.

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

лей удовлетворены. Если это не так, то определяется очередная

перевозка: если A

≥ B

, то j = j + 1;

если A

< B

, то i = i + 1.

в). k = k+1. Переход на шаг а.

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

Пусть производится перевозка грузов от 3-х поставщиков

=11; a

=8) к 4-м потребителям (b

=5; b

=9; b

=7).

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

заданы стоимости перевозок единицы груза (c

0). Исходное состояние: k = 1;

= (11, 11, 8);

= (5, 9, 9, 7);

текущая перевозка (i,j) = (1,1).

Итерация 1. k = 1;

= 5; А

= (6, 11, 8);

= (0, 9, 9, 7);

≥ B

- j = j +1 = 2.

Итерация 2. k = 2;

= 6; А

= (0, 11, 8);

= (0, 3, 9, 7);

< B

- i = i +1 = 2.

Итерация 3. k = 3;

= 3; А

= (0, 8, 8);

= (0, 0, 9, 7);

≥ B

- j = j +1 = 3.

5 9 9 7

108

Итерация 4. k = 4;

= 8; А

= (0, 0, 8);

= (0, 0, 1, 7);

< B

- i = i +1 = 3.

Итерация 5. k = 5;

= 1; А

= (0, 0, 7);

= (0, 0, 0, 7);

≥ B

- j = j +1 = 4.

Итерация 6. k = 6;

= 7; А

= (0, 0, 0);

= (0, 0, 0, 0);

∀А

= 0; ∀В

= 0; - конец.

Значение целевой функции (стоимость перевозок) L = 7×5

+ 8×6 + 4×3 + 5×8 + 1×1 + 2×7 = 150. Исходный опорный план пе-

ревозок построен, однако в процессе поиска исходного опорного

решения не учитывалась стоимость перевозок.

Метод минимального элемента.

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

тывать уже на этапе построения исходного плана. Для этого пред-

назначен метод минимального элемента.

0). Исходное состояние: номер итерации k = 1;

= (А

,...,А

), A

= a

, i ∈ M;

= (В

,...,В

), B

= b

, j ∈ N;

в качестве текущей перевозки выбирается перевозка с мини-

мальной стоимостью

(i, j) = arg min c

r∈M

s∈N

Каждая k-я итерация состоит в выполнении 3-х шагов:

а). Вычисляется объем перевозки (i,j)

= min {A

, B

} .

Пересчитываются значения компонент векторов A и B:

k+1

= A

- x

;

k+1

= B

- x

б).

Если A

k+1

= 0, i∈M и B

k+1

= 0, j∈N, то процесс окончен, т.е.

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

лей удовлетворены. Если это не так, то определяется очередная

перевозка:

109

(i, j) = arg m i n c

r∈M│A

k+1

s∈N│B

k+1

в). k = k+1. Переход на шаг а.

Построим исходный опорный план перевозок предыдущего

примера с использованием метода минимального элемента.

0). Исходное состояние: k = 1;

= (11, 11, 8);

= (5, 9, 9, 7);

текущая перевозка (i,j)=(3,3).

Итерация 1. k = 1;

= 8; А

= (11, 11, 0);

= (5, 9, 1, 7);

(i,j)=(2, 1).

Итерация 2. k = 2;

= 5; А

= (11, 6, 0);

= (0, 9, 1, 7);

(i,j)=(1, 4).

Итерация 3. k = 3;

= 7; А

= (4, 6, 0);

= (0, 9, 1, 0);

(i,j)=(2, 2).

Итерация 4. k = 4;

= 6; А

= (4, 0, 0);

= (0, 3, 1, 0);

(i,j)=(1, 3).

Итерация 5. k = 5;

= 1; А

= (3, 0, 0);

= (0, 3, 0, 0);

(i,j)=(1, 2).

Итерация 6. k = 6;

= 3; А

= (0, 0, 0);

= (0, 0, 0, 0);

∀А

= 0; ∀В

= 0; - конец.

Значение целевой функции (стоимость перевозок) L = 8×3

+ 5×1 + 3×7 + 2×5 + 4×6 + 1×8 = 92. Исходный опорный план, най-

5 9 9 7

110

денный методом минимального элемента, значительно превыша-

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

западного угла.

6.1.2. Метод потенциалов

(Канторович Л.В., Гавурин М.К., 1940)

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

рования перевозок некоторого груза от поставщиков (производи-

телей) к потребителям. Отдельную перевозку можно характери-

зовать

⎯⎯→ B

, i∈M = {1,…,m}; j∈N = {1,…,n}.

Здесь c

- стоимость перевозки (задана в исходных данных); x

объем перевозки (необходимо найти в результате планирования).

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

(6.6)-(6.9). Решение задачи, двойственной к задаче (6.6)-(6.9), бу-

дет иметь вид (см.3.1)

μ = (U

,...,U

,...,V

)

где U

характеризует эффективность повышения количества ре-

сурсов a

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

характеризует эффективность повышения величины спроса b

и называется потенциалом j-го пункта потребления. Тогда раз-

ность потенциалов (V

- U

) характеризует эффективность пере-

возки (i,j). В этом случае, если (V

- U

) > c

, то перевозку (i,j) це-

лесообразно запланировать, если (V

- U

) < c

, то перевозка (i,j)

нецелесообразна.

Опорное решение x = ║x

║

= ║x

║, где x

> 0 - вектор ба-

зисных перевозок (запланированных); и x

= 0 - вектор небазис-

ных (незапланированных) перевозок. Все перевозки, определяе-

мые опорным решением x, характеризуются множеством J = M×N,

причем J = S ∪ Q,

где S - базисные перевозки S = { (i,j)∈J │ x

≥ 0 } .

Q - небазисные перевозки Q = { (i,j)∈J │ x

= 0 } .

Очевидно, что если (i,j)∈S, то (V

- U

) = c

, с другой сторо-

ны, если выполняется

∀(i,j) ∈ Q, (V

- U

) ≤ c

, (6.10)

то нет перевозок, которые целесообразно запланировать, следо-

вательно, решение оптимально. В то же время, если