Двойственный симплекс – метод. Исследование моделей задач линейного программирования на чувствительность

Разбить на страницы

Показывать лекцию целиком

1. Двойственный симплекс – метод

Использование идей двойственности в сочетании с общей идеей симплекс-метода позволило разработать еще один метод решения задач ЛП - двойственный симплекс-метод. Впервые этот метод был предложен Лемке в 1954г. Решение задачи ЛП двойственным симплекс-методом сводится к отысканию оптимального плана прямой задачи последовательным переходом от одного базиса к другому.

Задача ЛП в канонической форме имеет вид:$$\text{максимизировать} \; L(x) = \sum_{j=1}^n c_j x_j$$ при условиях$$\sum_{j=1}^n a_{ij} x_j = b_{\mu}, \; (\mu = 1,2,\ldots,m)$$ или $$\sum_{j=1}^n A_j x_j = b , \; x_j \geq 0, \; j = 1,2,\ldots,n$$.

Предположим, что $$n \geq m$$ и ранг матрицы А равен m.

Двойственная задача к задаче (1.1), (1.2) записывается так:$$\text{максимизировать} \; \widetilde{L}_{\delta e} (y) = \sum_{\mu=1}^m b_{\mu} y_{\mu}$$ при условиях$$A_j^T y \geq c_j, \; \sum_{\mu=1}^m a_{ij} y_{\mu} \geq c_j , j=1,2,.,n.$$

Назовем сопряженным базисом, или базисом двойственной задачи такую систему из m линейно-независимых векторов матрицы ограничений прямой задачи $$\{ A_i \}_{i \in I_\delta}$$, для которой базисное решение y соответствующей системы линейных уравнений вида$$A_i^T y = c_i, \; i \; \textit{есть} \; I_{\delta}$$ удовлетворяет всем ограничением (1.4).

Разложим вектор b по сопряженному базису$$\sum_{i \in I_{\delta}} A_i x_i = b = A_0$$

Решив систему (1.6), получим некоторое ее базисное решение $$\{ x_{i0} \}_{i \in I_{\delta}}$$, которое называется псевдопланом прямой задачи, так как для него может выполняться условие неотрицательности переменных x_i0.

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

Как известно, оценки для небазисных векторов $$\Delta_j$$ определяется в соответствии с$$\Delta_j = \sum_{i \in I_{\delta}} c_i x_{ij} - c_j , \; j=1,2,\ldots,n .$$

Псевдоплан можно найти и независимо от двойственной задачи. Пусть $$\{ A_i \}_{i \in I_{\delta}}$$ - произвольная система линейно-независимых векторов прямой задачи.

Выразим все небазисные векторы {A_j} через базисные:$$A_j = \sum_{i \in I_{\delta}} A_i x_{ij} ,$$ $$A_0 = b = \sum_{i \in I_{\delta}} A_i x_i .$$

Обозначим решение (1.9) через х₀. Тогда можно дать дополнительное определение псевдоплана: n - мерный вектор X, для которого x_i = x_i0 при $$i \in I_{\delta}$$, и x_j=0 при $$j \notin I_{\delta}$$, является псевдопланом тогда и только тогда, когда все $$\Delta_j \geq 0, \; j=1,\ldots,n$$.

Доказательство. Векторы $$\{ A_i \}_{i \in I_{\delta}}$$, линейно независимы.

Поэтому можно вычислить такой y={y₁,y₂,...,y_m}, для которого$$A_j^T y = \sum_{\mu =1}^m a_{\mu} y_{\mu} = c_i, \; i \in I_{\delta}$$ Тогда$$\begin{align*} \Delta_j = \sum_{i \in I_{\delta}} c_i x_{ij} - c_j = \sum_{i \in I_{\delta}} (\sum_{\mu=1}^m a_{\mu i} y_{\mu}) x_{ij} - c_j = \\ \sum_{\mu=1}^m (\sum_{i \in I_{\delta}} a_{\mu i} x_{ij}) y_{\mu} - c_j = \sum_{\mu=1}^m a_{\mu i} y_{\mu} - c_j . \end{align*}$$

С учетом (1.4) получим$$\Delta_j = \sum_{\mu = 1}^m a_{\mu i} y_{\mu} - c_j \geq 0, \; \forall = 1,n ,$$ что и требовалось доказать.

Рассмотрим некоторый сопряженный базис и соответствующий ему псевдоплан.

Справедлив следующий признак оптимальности: если среди базисных компонентов псевдоплана Х нет отрицательных, то псевдоплан Х={x_i0} оказывается оптимальным решением прямой задачи.

Доказательство. Имеет место такая цепочка равенств:$$\overline{L}_{\delta e} (y) = \sum_{\mu=1}^m b_{\mu} y_{\mu} \stackrel{(1)}{=} \sum_{\mu=1}^m (\sum_{i \in I_{\delta}} a_{\mu i} x_i) y_{\mu} \stackrel{(2)}{=} \sum_{i \in I_{\delta}} x_i (\sum_{\mu=1}^m a_{\mu i} y_{\mu}) \stackrel{(3)}{=} \sum_{i \in I_{\delta}} c_i x_i .$$

Равенство (1) следует из (1.2), равенство (2) получено переменой порядка суммирования, равенство (3) следует из (1.10).

Так как$$x_j = 0 \; \text{при} \; j \neq I_{delta}$$ то$$\sum_{i \in I_{\delta}} c_i x_i = \sum_{j=1}^n c_j x_j = L(x)$$

Таким образом, $$\overline{L}_{\delta e} (y) = L(y)$$, что и является признаком оптимальности планов х и у, если $$x \ge 0$$.

Этот признак является необходимым и достаточным условием оптимальности в случае невыродженности базисного решения y двойственной задачи .

Пусть известен некоторый сопряженный базис $$\{ A_i \}, i \in I_{\delta}$$, которому соответствует псевдоплан х. Очевидно, $$А_j = \sum_{i \in I_{\delta}} A_i x_{ij}, А_0 = \sum_{i \in I_{\delta}} A_i x_i$$. При этом в зависимости от знаков {x_i} и {x_ij} может иметь место один из трех случаев:

базисные компоненты $$х_i = х_{i0} \ge 0$$ для всех $$i \in I_{\delta}$$ ;

среди х_i имеются отрицательные, причем для некоторого i: х_i0<0, а все $$х_{ij} \ge 0, \; j=1,.,n$$ ;

псевдоплан содержит отрицательные компоненты х_i0<0, но для каждой из них среди элементов {х_ij}, j=1,...,n, имеются отрицательные. В первом случае, как следует из достаточного признака оптимальности, псевдоплан х - оптимальное решение. Во втором случае задача не разрешима. В третьем случае можно перейти к некоторому новому сопряженному базису и, следовательно, к новому псевдоплану с меньшим значением L.

Итак, последовательные переходы от одного сопряженного базиса к другому производят до тех пор , пока не получат решение задачи или не установят ее неразрешимость. Каждый переход от одного псевдоплана к другому составляет одну итерацию (один шаг) двойственного симплекс-метода.

Каждая итерация содержит два этапа. На первом этапе выясняют, не является ли псевдоплан оптимальным планом прямой задачи, и если нет, то разрешима ли задача. Для этого необходимо вычислить $$\{ x_i \}, \; i \in I_{\delta}$$ и установить их знаки. Второй этап состоит в осуществлении элементарного преобразования - (одной итерации) метода полного исключения Жордана-Гауса, приводящего к новому псевдоплану с меньшим значением целевой функции.

Описание алгоритма. Задача ЛП должна быть задана в канонической форме (1.1), (1.2) или сведена к ней. Отыскивают сопряженный базис двойственной задачи и обозначают его $$\{ A_i \}, i \in I_{\delta}$$. Разложим А₀ по векторам базиса А_і1,.,А_іm в соответствии с (1.9) и найдем псевдоплан $$\{ х_{i0} \}, i \in I_{\delta}$$ прямой задачи.

Исследуем знаки {х_i0}. Если имеет место случай $$х_{i0} \ge 0, \; \forall i \in I_{\delta}$$, то начальный псевдоплан является оптимальным планом прямой задачи. При наличии отрицательных компонент {х_i0} вычисляем коэффициенты разложения векторов A_j по векторами сопряженного базиса {х_ij} в соответствии с (1.8).

Если для некоторого r такого, что х_r0<0, все $$х_{rj} \ge 0$$ то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.

Если имеет место третий случай (то есть для каждого r такого, что х_r0<0, по крайней мере одна из компонент х_rj<0 ), то переходим к второму этапу. С этой целью составляют таблицу k -й итерации (аналогичную симплекс-таблице), которая состоит (m+2) строк и (n+1) -го столбца (табл. 6.1).

Столбец В_x таблицы, как обычно, содержит векторы {A_i} базиса псевдоплана хk, а столбец А₀ - базисные компоненти псевдоплана {х_i0(k)}. Строка (m+1) -индексная, ее заполняют параметрами $$\Delta_j^{(k)}$$, являющимися оценками векторов А_j:$$\Delta_j = a_{0j} = \sum_{i \in I_{\delta}} c_i x_{ij} - c_j ,$$

величина - значение целевой функции при псевдоплане$$\Delta_0 = \sum_{i \in I_{\delta}} c_i x_{i0}^{(K)}.$$ Итерацию k завершают заполнением главной части таблицы (от первой до (m+1) -й строк).

`C`			`C₁`	`C₂`	.	`C_j`	.	`C_n`
	`B_x`	`A₀`	`A₁`	`A₂`	.	`A_j`	.	`A_n`
`C₁`	`X₁`	`X₁₀`	`X₁₁`	`X₁₂`	.	`X_1j`	.	`X_1n`
`C₂`	`X₂`	`X₂₀`	`X₂₁`	`X₂₂`	.	`X_2j`	.	`X_2n`
.	.	.	.	.	.	.	.	.
`C_i`	`X_i`	`X_i0`	`X_i1`	`X_i2`	.	`X_ij`	.	`X_in`
.	.	.	.	.	.	.	.	.
`C_m`	`X_m`	`X_m0`	`X_m1`	`X_m2`	.	`X_mj`	.	`X_mn`
	$$\Delta$$	$$\Delta_0$$	$$\Delta_1$$	$$\Delta_2$$	.	$$\Delta_j$$	.	$$\Delta_n$$
	$$\Theta$$		$$\Theta_1$$	$$\Theta_2$$	.	$$\Theta_j$$	.

На первом этапе (k+1) -и итерации выясняют, имеет ли место первый, второй или третий случай.

В третьем случае переходим ко второму этапу. Сначала определяют вектор А_r, который необходимо вывести из базиса. Его индекс r определяют из условия$$A_{r0} = \min_i \{ x_{i0} | x_{i0} < 0 \}$$ т.е. по максимальной по модулю отрицательной компоненте базисного решения.

Затем заполняют элементы (m+2) -й строки, которые вычисляют по формуле$$\Theta_j^{(k)} = \left. \left\{ - \frac{\Delta_j}{x_{rj}} \right| x_{rj} < 0 \right\}.$$

В строке $$\Theta$$ заполняют лишь те позиции, для которых x_rj<0. Вектор А_l, который должен быть введен в базис, находят из условия$$\Theta_i = \min_j \{ \Theta_j \} = \min_j \left. \left\{ - \frac{\Delta_j}{x_{rj}} \right| x_{rj} < 0 \right\}.$$

Определив направляющую строку r и столбец l, вычисляют элементы главной части таблицы (k+1) -й итерации по рекуррентным соотношениям$$x_{ij}^{(k+1)} = \left\{ \begin{aligned} x_{ij}^{(k)} - \frac{x_{rj}^{(k)}}{x_{ri}^{(k)}} * x_{il}^{(k)}, \; \textit{при} \; i \neq r , \\ \frac{x_{rj}^{(k)}}{x_{ri}^{(k)}}, \; \textit{при} \; i = r , \end{aligned} \right.$$ где x_ri - направляющий элемент преобразования.

Вычислительная схема алгоритма двойственного симплекс-метода похожа на вычислительную схему симплекс-метода. Аналогичны и формы таблиц.

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

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

Отметим некоторые важные свойства двойственного симплекс-метода.

В отличие от прямого симплекс-метода, двойственный симплекс-метод не требует нахождения начального базисного решения ( опорного плана ), а поиск начального псевдоплана часто может оказаться легче, чем поиск ДБР.

Рассмотрим, например, типичную задачу минимизации$$\sum_{j=1}^n c_j x_j$$ при условиях$$\sum_{j=1}^n a_{ij} x_j \ge b_i, \; i=1,2,\ldots,m ,$$ $$x_j \ge 0 ,$$ $$c_j \ge 0.$$

Для задачи такого вида найти сразу начальный опорный план нельзя, и поэтому необходимо применить метод искусственных переменных и выполнить значительный объем вычислений. В то же время псевдоплан находится почти автоматически. Действительно, перейдем от (1.17) - (1.19) к эквивалентной задаче в расширенной форме, введя свободные переменные x_n+1, x_n+2, ., x_n+m...$$-\sum_{j=1}^n c_j x_j$$ при условиях$$\sum_{j=1}^n a_{ij} x_j - 1x_{n+i} = b_i, \; i= \overline{1,m}$$

Запишем ограничения двойственной задачи$$\sum_{i=1}^m a_{ij} y_j \ge - c_j, \; j= \overline{1,n}$$ $$-y_i \ge 0, \; i= \overline{1,m}$$

Из неравенств (1.23) - (1.24) видим, что поскольку решение y_i при i=1,m удовлетворяет всем ограничениям (1.23), то сопряженный базис образуют векторы A_n+1,A_n+2,...,A_n+m при свободных переменных. При этом начальный псевдоплан такой:$$x_{n+i} = -b_i, \; i= \overline{1,m}.$$

Итак, для задачи вида (1.17) - (1.18) пpи условии (1.20) применение двойственного симплес-метода оказывается предпочтительнее в сравнении с прямым.

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

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

Теория двойственности позволяет анализировать модели ЛП на чувствительность. Рассмотрим обычную задачу ЛП в виде$$\text{максимизировать} \; \sum_{j=1}^n c_j x_j = \max L(x)$$ при условиях$$\sum_{j=1}^n a_{ij} x_j \le b_i, \; i=1,2,\ldots,m; \; x_j \ge 0.$$

Напомним ее экономическую интерпретацию. Целевая функция L(x) - это доход от реализации плана производства x ; a_ij - интенсивность расходования i -го ресурса при j -м способе производства; b_i - имеющийся уровень i -го ресурса.

1. Варьирование ограниченных ресурсов. Предположим, что величины ресурсов b=|| b_i || варьируются. Тогда возникают вопросы: при каких вариациях правых частей ограничений найденный оптимальный план x₀ не изменяется; как эти вариации влияют на функцию максимального дохода L_max? Ответ на эти вопросы дает анализ соответствующей задачи ЛП на чувствительность.

Пусть ограничение b_i получают некоторые вариации $$\Delta b_i$$, что приводит к вариациям плана $$x_0, x_0 = x_0(b+\Delta b)$$ и функции $$L_{\max} (x_0(b_0 + \Delta b))$$. Предположим, эти вариации $$\Delta b$$ таковы, что план $$x_0(b + \Delta b)$$ остается допустимым (т.е. удовлетворяет условию неотрицательности). Найдем отношения приращения$$\Delta L_{\max} (b) = L_{\max} (x_0(b_0+\Delta b)) - L_{\max} (x_0(b)) \; \text{к} \; \Delta b.$$

Имеем$$\lim_{\Delta b_i \rightarrow 0} \frac{\Delta L_{\max}(b)}{\Delta b_i} = \frac{\partial L_{\max (b)}}{\partial b_i} ,$$ где b рассматривается как варьируемый параметр.

Вспомним, что в соответствии с основной теоремой двойственности$$L_{\max} (x_0) = \sum_j c_j x_j^0 = \sum_i b_i, y_i^0 ,$$ и, подставляя (2.7.4) в (2.7.3), получим$$\frac{\partial L_{\max (b)}}{\partial b_i} = y_i^0, \; i=1,2,\ldots,m .$$

Таким образом, оптимальные значения двойственных переменных $$y_i^0$$ определяют вклад каждого ресурса в доход L_max при оптимальном решении x₀. Эта величина численно равна дополнительному доходу при увеличении i -го ресурса b_i на единицу при условии, что ресурсы используются оптимальным образом.

Итак, величины $$y_i^0$$ служат показателями важности соответствующих ресурсов для системы. Чем большее значение $$y_i^0$$ при некотором i, тем существеннее вклад i -го ресурса в функцию максимального дохода L_max и тем выгоднеее его увеличение. Если для некоторого $$y_i^0 =0$$, то i -й ресурс не является существенным ограничением для системы.

Обозначим через A_x матрицу оптимального базиса задачи ЛП при векторе ресурсов b. Очевидно соответствующее оптимальное решение$$x_{\text{опт}} = A_x^{-1} b.$$

Предположим, что мы изменили вектор ресурсов b=|| b_i || на $$b_{\text{н}}=b+\Delta b$$ и хотим узнать, как это повлияет на оптимальное решение. Для этого найдем новое соответствующее базисное решение$$x_{\text{н}} = A^{-1}_x b_{\text{н}} = A^{-1}_x (b + \Delta b).$$

Если все компоненты $$x_{i \text{н}} \ge 0$$, то это решение $$x_{\text{н}} = [x_{i\text{н}}]$$ оптимально (т.е. оптимальный базис не изменился). В противном случае нужно произвести поиск нового решения, для этого можно применить двойственный симплекс-метод, начиная с текущего базисного решения $$x_{\text{н}}$$.

2. Варьирование целевой функции. Теперь рассмотрим случай, когда варьируются коэффициенты {c_j}, j= 1,2,.,n.... Попытаемся выяснить условия, при которых найденный ранее оптимальный план останется оптимальным при таких вариациях.

Пусть вариациям $$\delta_{c_r}$$ подвергнется коэффициент $$c_r : c_r^{\text{н}} = c_r + \delta_{c_r}$$. Обозначим через J_б, J_неб множество индексов базисных и небазисных векторов в оптимальном плане x₀ соответственно.

Найдем значения оценок $$\Delta_j^{(\text{н})}$$ после вариации c_r для двух случаев:

1) $$r \in J_{\text{неб}}$$ тогда $$\Delta_j^{(\text{н})}=\Delta_j$$ для всех $$j \neq r$$ ;$$\Delta_r^{(\text{н})} = \sum_{i \in J_{\delta}} c_i a_{ir} - (c_r + \delta_{c_r}), \; \text{для} \; j=r ;$$

2) $$r \in J_{\text{б}}$$,$$\Delta_r^{(\text{н})} = \sum_{i \in J_{\delta}} c_i^{(\text{н})} a_{ij} - c_j = \sum_{i \in J_{\delta}} c_i a_{ij} + \delta_{c_r} a_{rj} - c_j ; \; j \in J_{\text{неб}}$$

Очевидно, что для сохранения оптимальности прежнего плана при вариациях коэффициента c_r необходимо и достаточно сохранение знаков оценок $$\Delta_j^{(\text{н})}$$ для всех небазисных переменных. Поэтому из условий $$\Delta_j^{(\text{н})} \ge 0$$ в соответствии с формулами (2.6) и (2.7) можно определить допустимые вариации коэффициента $$\delta_{c_r}$$, при которых сохраняется прежнее оптимальное решение.

До сих пор мы рассматривали вариации лишь одного коэффициента целевой функции. Этот же подход можно применить, когда варьируются одновременно несколько коэффициентов c_i.

В таком случае получим соотношения, аналогичные (2.7), в которых оценки $$\Delta_j$$ будут функциями уже нескольких параметров $$(\delta_1, \delta_2,.,\delta_r)..$$.

Решая совместно систему неравенств вида $$\Delta_j(c_1, c_2,.,c_r)\ge 0,\; j \in J_{\text{небы}}$$ находим условия для вариаций $$\delta_{c_r}$$, при которых прежний оптимальный базис сохраняется.

Эта задача относится к классу задач параметрического программирования.

3. Варьирование элементов матрицы ограничений A. Рассмотрим лишь случай вариации компонентов небазисных векторов A_j=[a_ij], i=1,2,...,m, поскольку исследование вариаций компонент базисных векторов A_i довольно сложное, легче заново решить задачу с новыми условиями.

Итак, пусть небазисный вектор A_j=[a_mj] изменился. Нужно выяснить, останется ли оптимальным текущий базис. Для этого полезно применить теорию двойственности. Пусть оптимальный базис прямой задачи A_x, а соответствующие оптимальные значения двойственных переменных $$y_i^0$$. Как известно, условие оптимальности $$\Delta_j \ge 0, \; \forall j \in J_{\text{неб}}$$. Вместе с тем в соответствии с (1.11), $$\Delta_j = \sum_{i \in J_{\delta}} a_{ij} y_i^0 - c_j$$. Значит, если $$\Delta_j^{(\text{н})} = \sum_{i \in J_{\delta}} a_{ij} y_i^0 - c_j \ge 0$$, то прежний оптимальный базис сохраняется.

4. Добавление еще одного способа производства. Предположим, что первоначально задача имеет вид$$\text{максимизировать} \; \sum_{j=1}^n c_j x_j$$ при условиях$$\sum_{j=1}^n A_j x_j \le b , \; x_j \ge 0.$$

Предположим, что найден оптимальный базис $$\{ A_i \}, i \in J_{\delta}$$ и соответствующие оптимальные решения прямой $$x_j^0$$ и двойственной $$y_j^0$$ задач.

Пусть прибавляется еще один (n+1) -й способ производства, которому отвечает вектор технологических затрат A_n+1=[a_{i n+1}] и коэффициент целевой функции c_n+1. Тогда будем иметь следующую задачу:$$\text{максимизировать} \; \sum_{j=1}^n c_j x_j + c_{n+1} x_{n+1}$$ при условиях$$\sum_{j=1}^n A_j x_j +A_{n+1} x_{n+1} \le b , \; x_j \ge 0, \; j=1,2,.,n+1.$$

Нужно определить, изменится ли при этом прежнее оптимальное решение и при каком значении коэффициента c_n+1 выпуск (n+1) -го продукта будет рентабельным (то есть $$x_{n+1}^0 > 0$$ ).

Чтобы оптимальное решение после ввода вектора A_n+1 не изменилось, необходимо, чтобы вектор A_n+1 и переменная x_n+1 оставались небазисными, т.е., чтобы $$\Delta_{n+1} \ge 0$$. На основании теории двойственности получим$$\Delta_{n+1} = \sum_{i \in J_{\delta}} a_{i n+1} y_i^0 -c_{n+1}.$$

Если $$\sum_{i \in J} a_{i n+1} y_i^0 -c_{n+1} \ge 0$$, то прежний оптимальный план не изменится после включения выпуска (n+1) -го вида продукции.

Если же $$\sum_{i \in J} a_{i n+1} y_i^0 -c_{n+1} < 0$$, то выпуск (n+1) -го вида продукции становится рентабельным, и прежний оптимальный план изменяется.

Страницы: