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

СОДЕРЖАНИЕ

 

Введение в понятие  блочное программирование……………………………….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), получаем

в левой части 

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