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

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

Поэтому при решении основной задачи условие (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):