Методы блочного програмирования

СОДЕРЖАНИЕ

 

Введение в понятие  блочное программирование……………………………….3

Блочное программирование……………………………………………………...4

Метод декомпозиции Данцига – Вулфа…………………………………………5

Решение транспортной задачи методом Данцига-Вулфа………………………9

Метод Корнаи – Липтака………………………………………………………..15

Вывод……………………………………………………………………………..21

Список используемой литературы……………………………………....……...22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение в  понятие блочное программирование

 

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

Необходимость такого подхода  обосновывается тем, что с ростом размерности трудоемкость решения задач растет невероятно быстро. “Проклятие размерности”, по меткому выражению американского математика Р. Беллмана, характерно для большинства реальных задач математического программирования.

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

Среди теоретических  схем Б. п. наиболее известны две: метод декомпозиции Данцига—Вульфа и метод планирования на двух уровнях Корнаи—Липтака. Обе они представляют собой последовательные пересчеты, взаимно увязывающие решения главной, “отраслевой” задачи и локальных задач предприятий. Различие же между ними состоит в том, что в первом случае итеративный процесс основан на корректировке двойственных оценок ресурсов и продукции, а во втором случае — на корректировке лимитов общеотраслевых ресурсов, выделяемых предприятиям. При этом задача сводится к игре между центром и предприятиями; ценой игры является сумма целевых функций предприятий. При решении задач большой размерности значительная часть времени тратится на обращения к внешней памяти и это является главным препятствием на пути увеличения размерности задач. Уменьшить число обращений к внешней памяти можно, если удается большую задачу заменить рядом задач существенно меньшей размерности. Приемы и методы, позволяющие выполнять такие преобразования, составляют предмет блочного программирования.

 

 

Блочное программирование

 

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

Одним из эффективных методов блочного программирования применительно к линейным задачам является метод декомпозиции Данцига – Вулфа. По данным авторов метод позволяет решать задачи с размерностью n~10⁶, m~10⁵.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Метод декомпозиции Данцига - Вулфа

 

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

Пусть имеется следующая модель задачи:

L=C^TXàmax;     (6.1)

AX=B;                          (6.2)

X³0,             (6.3)

где вектор X имеет размерность n, а вектор B – m.

Условия (6.2), (6.3) определяют допустимое множество задачи D. Представим матрицу А и вектор В  в виде двух подматриц:

Тогда условия задачи (6.2)-(6.3) записываются следующим образом:

А⁽⁰⁾Х=В⁽⁰⁾;                                  (6.4)

А⁽¹⁾Х=В⁽¹⁾;       (6.5)

Х³0                     (6.6)

Условия (6.4), включающие m₀ равенств, порождают допустимое множество D₀, а система (6.5) содержит m₁ равенств и вместе с (6.6) задает множество D₁. Очевидно, что m=m₀+m₁, D= D₀ Ç D₁. При этом выделение подматриц выполняется так, что m₁>>m₀.

Далее будем полагать, что множество D₁ ограниченное и, значит, является выпуклым многогранником. В противном случае его легко сделать ограниченным добавлением ограничений сверху на переменные так, что они не повлияют на исходное множество D.

Предположим, что нам  известны вершины множества D₁. Обозначим их координаты через Х¹, Х²,…, Х^N, где N – число вершин. Поскольку D₁ – выпуклый многогранник, то любую его точку  можно представить в виде линейной комбинации  вершин:

Х= z_nXⁿ;      (6.7)

S z_n=1;            (6.8)

z_n³0, "v.             (6.9)

Так как все решения Х, определяемые по (6.7)-(6.9), принадлежат D₁, то описание (6.7)-(6.9) эквивалентно (6.5), (6.6).

Подставим Х в виде (6.7) в (6.1) и (6.4):

L =

C^T z_nXⁿ;

SA⁽⁰⁾Xⁿz_n=B⁽⁰⁾.

Считая Xⁿ известными,  введем  обозначения:

С^ТХⁿ=s_n;                       (6.10)

А⁽⁰⁾Хⁿ=Р_n.              (6.11)

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

L=

s_nz_nàmax;

P_nz_n=B⁽⁰⁾;

z_n=1;

"z_n³0.

В этой модели неизвестными являются z_n, число которых равно числу вершин многогранника D₁. Последнее равенство модели можно объединить со всеми остальными, используя обозначения расширенных векторов

.                                  (6.12)

Тогда окончательно получим:

L= s_nz_nàmax;         (6.13)

z_n = ;             (6.14)

"z_n³0.                 (6.15)

Задача в виде (6.13) – (6.15) называется координирующей  или основной задачей. Главное отличие этой задачи от исходной в несравнимо меньшем числе условий (m₀+1<<m).

Если мы сможем ее решить, то есть найти Z^*, то получим решение и исходной задачи, воспользовавшись (6.7):

Х*= z_n^*Xⁿ.                                          (6.16)

Для решения основной задачи применим модифицированный симплекс-метод. Начальное решение можно построить, не зная ни одной вершины, с помощью искусственных переменных z_N+i.

Согласно модифицированному методу после получения очередного базисного  решения вычисляются относительные  оценки. В разд. 4.10 получены формулы:

    

Перепишем их в обозначениях координирующей задачи:

                                               (6.17)

или окончательно      

                              (6.18)

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

Итак, задача состоит в следующем:

D_nàmin.

Отбросив в (6.18) константу, запишем ее  в виде

(p^TA⁽⁰⁾-C^T)Xⁿ®                                     (6.19)

Решение задачи (6.19) проблематично, так  как минимум ищется на дискретном множестве вершин многогранника D₁. Учитывая, что минимизируемая функция линейная, будем искать решение не на вершинах, а на всем многограннике. Известно, что если решение существует, то оно будет достигаться в вершине. Поэтому решение на всем (непрерывном) множестве D₁ совпадет с решением задачи (6.19).

Таким образом, задачу (6.19) заменяем эквивалентной:

L_всп= (p^TA⁽⁰⁾-C^T)X®                                  (6.20)

A⁽¹⁾X = B⁽¹⁾;      (6.21)

X ³ 0.                                                   (6.22)

 Эта задача называется вспомогательной. Если она неразрешима, то и исходная задача не имеет решения. Пусть оптимальное решение вспомогательной задачи (6.20)-(6.22) достигается в вершине r. Это означает, что нам становятся известны координаты вершины X^r и оптимальное значение критерия . Тогда согласно формуле (6.18) вычисляем минимальную оценку

                    (6.23)

Очевидно, что если  D_r³0, то и все оценки неотрицательны, и решение координирующей задачи завершено.  При отрицательной D_r решение продолжается. В базис основной задачи вводится вектор , определяемый по формуле

            (6.30)

Направляющий столбец находится  разложением этого вектора по текущему базису:

.                            (6.31)

После определения направляющего  элемента и симплекс-преобразования получаем новое решение основной задачи. Коэффициент критерия (6.13) при  переменной, введенной в базисное решение, вычисляется согласно (6.10):

s_r =C^TX^r.                            (6.32)

Теперь по формуле (6.17) находим новый  вектор , снова решаем вспомогательную задачу и по полученной минимальной оценке делаем вывод о дальнейших действиях.

Таким образом, решение  исходной задачи заменяется многократным решением основной и вспомогательной задач. При этом порядок размерности вспомогательной задачи такой же, как у исходной. Поэтому естественнен вопрос: в каких случаях такой метод эффективен?

Ответ очевиден: в тех  случаях, когда сложность решения  вспомогательной задачи намного ниже, чем исходной. Такие случаи имеют место, когда матрица условий задачи (после упорядочения строк и столбцов) оказывается почти-блочно-диагональной, как показано на рис. 6.1. Примером может служить задача планирования производства продукции в крупной фирме или холдинге, когда у каждого предприятия своя номенклатура продукции, а некоторые ресурсы являются общими. Подматрица А⁽⁰⁾, входящая в параметры координирующей задачи, соответствует ограничениям по общим ресурсам. Такие условия называют связующими. Их относят к основной задаче.

Остальные условия образуют вспомогательную задачу. При этом подматрица А⁽¹⁾ имеет блочно-диагональную структуру, что позволяет разбить вспомогательную задачу на p независимых задач:

После решения этих задач определяется критерий вспомогательной задачи по очевидной формуле

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

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

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

Решение транспортной задачи методом Данцига-Вулфа

 

Применим метод декомпозиции к  Т-задаче:

    (6.33)

      (6.34)

     (6.35)

"Х_ij³0.      (6.36)

Использование этого метода целесообразно, если m<<n или m>>n. Оба варианта решаются идентично. Они отличаются только распределением условий между основной и вспомогательной задачами.

Рассмотрим случай, когда m<<n. Тогдо основная задача формируется по условиям пунктов отправления. Следовательно, множество D₀  описывается ограничениями (6.34), а D₁ – условиями (6.35) и (6.36).

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

      (6.37)

SZ_v=1;                                                (6.38)

"Z_v³ 0,                                               (6.39)

где X^v_ij – координаты v-ой вершины.

Подставим (6.37) в (6.33) и (6.34):

.

Введем обозначения:

                                           (6.40)

                                             (6.41)

Тогда основная задача запишется в виде

           (6.42)

          6.43)

          (6.44)

"Z_v³ 0.                       (6.45)

Для сбалансированной задачи условие (10) выполняется автоматически. Действительно, суммируя (6.43) и используя подстановки (6.41) и (6.35), получаем

в левой части 

в правой части  Таким образом,

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

Поэтому при решении основной задачи условие (6.44) из модели исключается.

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

D_v= p^TP_v - s_v =

Так как основная задача решается на минимум, то оптимальному статусу  соответствуют неположительные  оценки. Поэтому нужно искать максимальную оценку. Если она окажется не больше нуля, то все оценки неположительны и признак оптимальности выполнился. В противном случае необходимо продолжить решение основной задачи.

Значит, задача ставится так:

Вместо поиска максимума на дискретном множестве вершин перейдем к эквивалентной задаче поиска на всем непрерывном множестве D₁:

                            (6.46)

              (6.47)

"X_ij ³ 0.            (6.48)

Эта задача и является вспомогательной. Очевидно, что в оптимальном решении  этой задачи Теперь остается выяснить, как найти его.

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

        (6.49)

            (6.50)

"X_ij ³ 0.           (6.51)

Критерий вспомогательной задачи равен сумме критериев этих задач:

                                                 (6.52)

Оптимальное решение задачи  (6.49)-(6.51), как линейной, находится на границе. При этом только одна переменная не равна нулю (базис имеет размерность 1). Поэтому ее решение состоит в определении максимального коэффициета в критерии (6.49). Пусть максимум достигается на индексе i*, то есть

Тогда имеем следующее решение  задачи (6.49)-(6.51):

X^v_i*j =b_j,  X^v_ij=0, "i, i¹i*,                              (6.53)

и максимальная оценка определится  как                  

.

Если L^*_всп £ 0, то положительных оценок нет и текущее решение основной задачи будет оптимальным.

При L^*_всп > 0 начинается новая итерация:

1. пo (6.41) и (6.40) находим Р_v и s_v;

2. вычисляем элементы направляющего  столбца как коэффициенты разложения  вектора Р_v по текущему базису:

a_v=P^-1_BP_v;

3. проводим симплекс-преобразование  основной задачи, в результате  которого получаем новое решение  и новую обратную матрицу; 

4. вычисляем p^T=s^T_BP^-1_B;

5. решаем вспомогательную задачу: вычисляем разности  , находим оптимальные решения n задач (6.49)-(6.51) и максимальную оценку основной задачи.

Из рассмотренной вычислительной схемы следует, что эффективность  метода тем выше, чем сильнее неравенство m<<n или m>>n.

Пример.

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

bi ai	8	4	10	8
10	2	5	1	4
20	1	3	4	2

Числа в ячейках таблицы -  затраты  на перевозки C_ij.

Исходная модель задачи:

L = SSC_ijX_ij àmin

      (6.54)

      (6.55)

Координирующая задача формируется по условиям (6.54):

"Z_v³0.

Для построения начального решения  вводим искусственные переменные:

и модифицируем критерий

Составим начальную таблицу  координирующей задачи:  

sv	Базисные перемен.	P0	Pn+1	Pn+2
M	Zn+1	10	1	0
M	Zn+2	20	0	1
pТ			M	M

В последней строке значения p_i получены умножением первого столбца на столбцы P_n+i.

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

bj	8	4	10	8
p1-C1j	M-2	M-5	M-1	M-4
p2-C2j	M-1	M-3	M-4	M-2
v=1	X121=8	X122=4	X113=10	X124=8

Значения переменных в последней  строке таблицы получены согласно (6.53). Например, при j=1 максимальная разность равна M-1, поэтому X¹₂₁=b₁= 8.  Клетки с максимальными разностями выделены цветом фона. Вычисляем значение критерия по формуле (6.46):

[(M-1)*8 + (M-3)*4 + (M-1)*10 + (M-2)*8] > 0.

Так как признак оптимальности  не выполняется, переходим к итерациям. Находим s₁ согласно (6.40):

s₁=1*8 + 3*4 + 1*10 + 2*8 = 46.

Вычисляем компоненты вектора Р₁:

Р₁₁= X¹₁₃=10;

P₂₁= X¹₂₁+ X¹₂₂+ X¹₂₄= 8+4+8 = 20.

Следовательно, . Находим его разложение по начальному базису:

.

Добавляем столбец P₁ с элементами a₁ в начальную таблицу в качестве направляющего столбца:

sv	Базисные перемен.	P0	Pn+1	Pn+2	P1	q
M	Zn+1	10	1	0	10	1
M	Zn+2	20	0	1	20	1
pТ			M	M

 

Взяв 1-ю строку за направляющую и выполнив симплекс-преобразование, получаем новое решение основной задачи:

       Для выяснения статуса этого решения снова находим максимальную оценку основной задачи, решая вспомогательную задачу:             

 

 

Очевидно, что L²_всп>0, то есть решение основной задачи не является оптимальным.

Вычисляем коэффициент критерия при Z₂:

s₂=1*8 + 3*4 + 4*10 + 2*8 = 8+12+40+16 = 76.

Определяем компоненты вектора Р₂:

Р₁₂=0,  P₂₂= 8+4+10+8 = 30

Имея  , находим элементы направляющего столбца

и добавляем его к последней таблице основной задачи:

В результате симплекс-преобразования получаем:

Соответствующая вспомогательная  задача:

Критерий этой заачи L³_всп =(23/15)*8–(7/15)*4–(22/15)*10+(8/15)*8=0. Следовательно, получено оптимальное решение основной задачи: Z^*₁=1, Z^*₂=0, L^* = 46_*1 + 76_*0 = 46.

Находим значения исходных переменных по формуле (6.37), которая для нашей задачи принимает вид:

Таким образом,  получено следующее  оптимальное решение исходной задачи: X^*₂₁ = 8, X^*₂₂ = 4, X^*₁₃ = 10, X^*₂₄ = 8.

Проверка: L = SSC_ijX_ij=1*8 + 3*4 + 1*10 + 2*8=46. Это значение совпадает с вычисленным через переменные Z_i.

Метод Корнаи – Липтака

 

Пусть имеется задача ЛП вида:

максимизировать              c^Tx                            (10.3.1)

при условиях      (10.3.2)        (10.3.3)

где    c^T=[c₁,c₂,.,c_n]; x^T=[x₁,x₂,.,x_n]; b^T₀=[b₁,b₂,.,b_m]               
 
Рассмотрим подход к ее решению, использующий метод декомпозиции Корнаи-Липтака (20; 31).  Разобьем матрицу А₀ на подматрицы  , где при каждом   матрица   имеет размерность m x n_j. Тогда соответственно разбиваем  вектор с на подвектора с₁, с₂, ., с_j, ., с и х - на подвектора х₁, х₂, .,  х_jn, где c_j, x_j - вектора, имеющие размерность  , тогда задача (10.3.1)-(10.3.3) преобразуется к виду  максимизировать

 
               (10.3.4) 
 
при условиях             (10.3.5)                  (10.3.6)

 
Введем m-мерные вектора-столбцы у_і, удовлетворяющие условию

 
                  (10.3.7) 
 
Сформулируем J задач ЛП:    максимизировать      (10.3.8)

 
при условиях                    (10.3.9) 
 
                      (10.3.10) 
 
Рассмотрим вектор y = [y₁, y₂, ., y_J]. Обозначим через М_у множество всех векторов у таких, что выполняется условие (10.3.7) и задачи (10.3.8)-(10.3.10) имеют решения. Оптимальные значения функционалов задач (10.3.8)-(10.3.10) зависят от у_j, как от параметров. Указанную зависимость представим в виде f_j(y_j). Обозначим . Тогда задача (10.3.8)-(10.3.10) сводится к следующей координирующей задаче:

 
Максимизировать    F(y)             (10.3.11) 
 
при ограничениях                                        (10.3.12) 
 
Если разложение матрицы А₀ интерпретируется как разбиение системы на J подсистем, а вектор b₀рассматривается как общий ресурс системы, то задача (10.3.11),(10.3.12) заключается в нахождении оптимального распределения общего ресурса. Заметим, что здесь не вводится ограничения на знак величины y_j (это означает, что система может как потреблять(+), так и производить ресурсы (-)). Рассмотрим задачу (10.3.11), (10.3.12). Ее анализ усложняется, поскольку функция F(y) аналитически не известна, а задана лишь алгоритмически. Для ее вычисления необходимо решить задачу ЛП (10.3.8)-(10.3.10). 
Применение той или иной схемы максимизации функции F(y) порождает соответствующий метод разложения на основе принципа Корнаи-Липтака. Так, в работе Корнаи-Липтака предлагалось сведение этой задачи к минимаксной, далее решаемой методами теории игр. Рассмотрим этот подход. 
Запишем двойственные задачи к задаче (10.3.8)-(10.3.10): 
минимизировать            (10.3.13)  при ограничениях

 
            (10.3.14) 
 
 ,     (10.3.15) где вектор-столбец   имеет m компонент  . 
 
Пусть через  обозначены выпуклые многогранники в пространстве R^m, задаваемые условиями (10.3.14), (10.3.15). Введем вектор   с компонентами  и множество  . В соответствии с основной теоремой двойственности справедливо

 
 .             (10.3.16) 
Таким образом, 
 
     (10.3.17) и окончательно задача (10.3.11), (10.3.12) сводится к отысканию седловой точки:   найти           (10.3.18) 
 
где  -фиксированы,  и  . 
 
Задачу (10.3.18) можно решать методом матричных игр для фиктивной игры Брауна. 
 
Указанный метод представляет собой итеративный процесс, где каждая итерация в терминах теории игр представляет собой определенную партию игры и соответствует выбору некоторых стратегий двух игроков. Эти стратегии в данной задаче являются векторами   и y. Стратегии каждого игрока берутся наиболее выгодными с учетом ответа его противника. 
Оптимальные стратегии для задачи (10.3.18) определяются в виде: 
                        (10.3.19) 
.                           (10.3.20) 
 
Итеративный процесс, согласно методу Брауна, состоит из следующих шагов (52). 
 
Начальная итерация (k=1).   Выбирается произвольная стратегия  ; 
 
Полагаем      Определяем   согласно (10.3.19) 

  Полагаем   
Пусть уже проведено  (k-1) итераций, в результате которых определены   и  . 
 
k -ая итерация.

Определяем   согласно (10.3.20); 
 
Вычисляем  ; 
 
Определяем   согласно (10.3.19); 
 
Вычисляем  . 
 
В силу теоремы Робинсона о сходимости метода Брауна последовательность   при   сходится к седловой точке задачи (10.3.18). 
 
Метод разложения Корнаи-Липтака наиболее эффективен в случае, когда часть ограничений имеет блочно-диагональную структуру.

 
Введем в задачу (10.3.1)-(10.3.2) дополнительные блочные ограничения:

 
                                 максимизировать                           (10.3.21) 
 

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

 
                                        (10.3.22) 
 
 ,                               (10.3.23) 
 
где b_j - m_j -мерный вектор-столбец, а матрица A_j имеет размерность m_j x n_j.  
 
Составим функцию Лагранжа для задачи (10.3.8)-(10.3.10):