Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 182

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ГЛАВА 7

ПРИНЦИП ДЕКОМПОЗИЦИИ

7.1. Принцип декомпозиции (Данциг и Вулф [46], [47])

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

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

Z =

с х

(1 )

при условиях

х ^

0.

Ах = Ь,

Во многих случаях матрица А имеет структуру, показанную на рис. 7.1, где коэффициенты, стоящие вне указанных блоков, равны нулю.

Такую структуру может иметь линейная программа, составлен­ ная для большой фирмы с несколькими филиалами. Для каждого филиала составлена своя линейная программа, т. е. Агхг = bj, а для управления всей фирмой выписана матрица ограничений, включающая все ограничения, относящиеся к филиалам. Некото­ рые из матриц A i могут быть пустыми, например, в том случае, когда в фирме имеются отделы, не участвующие непосредственно в сфере производства, скажем отдел управления кадрами (отсюда Ai — пусто), но в матрице ограничений, относящейся ко всей фирме, эти отделы присутствуют. Заметим, что вектор Ь задачи

(1)

также разбивается на р

+ 1 векторов Ь0, . . ., Ьр.

Подобным

же

образом вектор с разбивается на р вектор-строк

щ, с2, . . .

.. .

., ср. Поэтому задачу (1)

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

минимизировать

V

Z = 2 c i x i

5 = 1

126

ГЛ.

7. ПРИНЦИП ДЕКОМПОЗИЦИИ

 

при условиях

 

 

 

 

 

V

=Ь0,

 

 

 

2

 

 

 

3=1

Арс^Ь ,-

(/ = 1

(2 )

 

 

xj > 0 .

Каждое из подмножеств ограничений AjXj = b; определяет выпук­ лое многогранное множество Sj. Предположим, что Sj — ограни-

п\

п г

п з

п р

Ьо

Ь,

Ъ ъ

ьз

ЬР

Р и с . 7.1.

чено, и через xi} (i = 1 , . . sj) обозначим крайние точки много­

гранника Sj. Тогда любое решение Xj можно представить в виде

X j —2 ^ i j X i j ,

i = i

 

(3)

 

 

2

hij^^O.

 

i=1

 

 

Допустим, что известны все Xij.

Положим

 

l j j = lujXij,

Cij = Cj'X;'j .

(*>

Тогда задачу (2) можно переписать в виде

 

минимизировать

 

 

v

sj

 

Z=2 2 Cij^ij

 

i= 1 i= l

 

7.1. ПРИНЦИП

ДЕКОМПОЗИЦИИ

 

127

при условиях

 

 

 

 

 

 

 

V

sj

 

 

 

 

 

 

2 2 ^ i A i j — Ьо,

 

 

 

 

(5)

3 = 1i=l

 

 

 

 

 

 

 

si

Ч- = 1

 

(7 = 1, • • •, Р) ,

 

 

2

 

 

 

7—1

 

 

 

 

 

 

 

 

 

 

(i = 1 ,

• .. , sj).

 

Если в задаче (5) найдены все

,

то из условия (3) можно полу-

чить х;- в предположении, что

!

x i} известны.

Задачу (5) можно

наглядно представить, как на

ге. 7.2.

 

 

 

^111* • *

^12i••

ч cs%Z

^13i * • ' 1 Cs33

^Ipl* *' 1 Cgpp

^11■>^21’ *‘ • ’ ^5,1

^ гЛ п т- - ,h ii

^13ч - ч ^ з 3

‘ * *1^SpP

1 , 1 , . . . , 1

 

 

 

 

 

 

 

 

 

 

 

 

I

I

 

 

1 , 1 , . . . , 1

 

 

I

I

 

 

 

 

 

 

1

1

 

 

 

 

 

 

 

I

 

 

 

 

1 , . . . , 1

 

I

 

 

 

 

 

 

 

I

 

 

 

 

 

 

 

1...... 1

 

 

Р и с . 7.2.

 

 

 

Преобразование задачи из формы (2)

в форму (5)

уменьшило

 

р

 

 

 

 

 

 

число строк с т 0 +

2 mi Д° то +

Р- С другой стороны, количество

 

з= 1

 

 

 

 

 

 

 

 

 

 

р

 

р

 

переменных значительно

возросло

с 2

пз Д°

2 sj •

К счастью,

 

 

 

 

3= 1

3 = 1

 

нет нужды использовать сразу все переменные Хц и знать все х;;. Поскольку матрица на рис. 7.2 содержит т0 + р строк, для формирования допустимого базисного решения необходимы т0 -f- + р векторов. Пусть исходное допустимое базисное решение полу­ чено. Воспользуемся модифицированным симплекс-методом. Допу­

стим, что известен вектор цен (л, л), где л — вектор с та

компонентами и л — вектор с р компонентами. Заметим, что лю­ бой столбец на рис. 7.2 имеет вид [1;;, е^]. В соответствии с симп­

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

ч

V - . 4

128 ГЛ. 7. ПРИНЦИП ДЕКОМПОЗИЦИИ

относительная оценка отрицательна, т. е. если

Cij—Cij (it,

я) [1 г/, еД < 0 .

Пусть

 

я = (я^, Яг, . . . , Яр).

Тогда

 

Ci j = Cf j

Я1г_у Яj .

Среди небазисных векторов могут быть векторы из множеств

S 2 и т. д. Если минимальная относительная оценка для каждого Sj

неотрицательна, т. е. Су ^ 0 , то текущее решение оптимально.

Поэтому станем искать в каждом Sj вектор с минимальной отно­

сительной оценкой.

Поскольку в данном Sj компоненты

одни

и те же для всех векторов, то решим следующую задачу:

 

найти

 

 

min {сц —я1*Д = min (с^-—яЬД xij

 

i

i

 

при условии x t j 6 S j . (Другими словами, мы хотим найти вершину

многогранника Sj, в которой сj — яL;- достигает минимума.) Полученная задача является задачей линейного программирова­ ния:

минимизировать

(Cj — nLj ) xj

при условиях

AjXj = bj, ху> 0.

(6)

Поскольку целевая функция задачи (6 ) линейна, минимум ее

всегда достигается в вершине, т. е. в некоторой хг;-. Если

(Cj яЬ j ) X i j Яу<С 01),

то вектор [1^, еД должен быть введен в базис, для чего выполняет­ ся обычная итерация симплекс-метода. Следует отметить одну особенность. Если вектор [1;7-, еД должен быть введен в базис, то, прежде чем выполнять итерацию симплекс-метода, этот вектор необходимо умножить на обращение текущего базиса В-1. Необ­

ходимость умножения на В-1 вытекает из того, что вектор (я, я) был получен умножением матрицы условий задачи (5) на В-1. Поскольку вектор [1*7-, еД входит в условия задачи (5), он должен быть умножен слева на матрицу В"1, такж, как все остальные вектор-столбцы условий (5). Операция умножения вектор-столбца

1) Ху — оптимальное решение задачи (6).

7.2. ПРИМЕР

129

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

коррекцией.

 

Если после решения р линейных программ

 

 

 

 

min(c; — nLj)xij — n j > 0

(для / = 1 ,

 

р),

 

 

 

г

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

7.2.

Пример

 

 

 

 

 

 

 

 

 

 

 

 

Рассмотрим линейную программу:

 

 

 

 

 

 

 

 

минимизировать

Х \ -р 8ж2 “ИЪ х 1

6ж2 -f- х 3

 

 

 

при условиях

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Xi -|- 4х2

 

xt -j- 2.x2

 

х3 — 7,

 

 

 

 

 

2хх-\-Ъхъ

 

 

 

 

 

 

= 5 ,

 

 

 

 

 

5^1+

 

 

 

 

 

 

=

6 ,

 

 

(1 )

 

 

 

 

 

Зх( + 4х'-|-

Зж' = 12,

 

 

 

Заметим, что в задаче (1)

X i ,

х 2 ,

х [ , ж', ж '> 0 .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Li = (1,

4),

L2=

( 4 - ,

2,

А )

,

 

 

 

 

bo = 7 ,

 

b±=

[5,

6 ],

 

b2 =

12,

 

 

 

 

 

A i=

[ 5

1 ] ’

A2 =

[3 ,4 ,3 ],

 

 

 

 

 

 

ci — (1,

8 ),

 

c 2 =

(5,

6 ,

1).

 

 

 

=

Выпуклое множество £4 состоит лишь из одной точки хи =

[1, 1].

Выпуклое

множество

S 2 — треугольник

с

вершинами

 

х12

= [4, 0,

0],

х 22 =

[0,

3,

0], х32 =

[0,

0,

4].

Для того чтобы получить исходное базисное решение, необходимо

та +

р = 1 + 2 векторов. Поэтому предположим, что в качестве

начальных выбираются векторы х11?

х12,

х 22

(заметим,

что х32

знать не обязательно):

 

 

 

 

 

 

hi =

LlXll =

(1, 4) [1, 1] = 5,

 

с„ =

(1,

8 ) [1, 11 =

9,

 

la =

L2x12 =

(V4, 2, 5/4) [4, 0, 0] =

1,

с12 =

(5,

6 , 1) [4, 0, 0] =

20,

hz —^2х 22 =

(1/4) 2, 5/4) [0, 3, 0] =

6 ,

с22 =

(5,

6 , 1) [0, 3, 0] =

18.

Следовательно, задача приобретает вид: минимизировать

9Яц-(- 2ОЯ12 18Я224~ ...

9 т. ху

Смотрите также файлы