ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ : Математические методы исследования операций в экономике - П. Конюховский : Книги по праву, правоведение

ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1 2 3 4 5 6 7 8 9 10 11 12 
РЕКЛАМА
<

 

1.1.1. Формы задачи линейного программирования.

В общем виде задача линейного программирования* (в дальней­шем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции

 

 

на некотором множестве D Ì Rn, где х Î D удовлетворяют сис­теме ограничений

 

 

и, возможно, ограничениям

х1 ≥0, х2 ≥0,..., хj ≥0,..., хn ≥0.           (1.3)

* Напомним, что частные примеры, сводящиеся к задаче линейного программирования, были описаны во введении.

 

Не умаляя общности, можно считать, что в системе (1.2) пер­вые m ограничений являются неравенствами, а последующие — l-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направ­ления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противопо­ложный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме нера­венств, но в силу особой структуры их обычно выделяют от­дельно и называют условиями неотрицательности (или три­виальными ограничениями).

Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относитель­ный характер. Так, задача поиска максимума функции

 

 

эквивалентна задаче поиска минимума функции

 

 

Часто условия задачи (1.1)-(1.3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращен­ной матричной форме

 

f(x) = сх → max, Ax ≤ b, х ≥ 0,          (1.6)

 

где с и х — векторы из пространства Rn, b — вектор из простран­ства Rm, а А — матрица размерности m х n.

Задачу линейного программирования, записанную в форме (1.1)-(1.3), называют общей задачей линейного програм­мирования (ОЗЛП).

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные хj наложены усло­вия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матрич­ной форме КЗЛП можно записать в следующем виде:

 

Поскольку любая оптимизационная задача однозначно оп­ределяется целевой функцией f и областью D, на которой отыс­кивается оптимум (максимум), будем обозначать эту задачу парой (D, f).

Условимся относительно терминологии, которая использу­ется в дальнейшем и является общепринятой в теории линейно­го программирования.

Планом ЗЛП называется всякий вектор х из пространства Rn.

Допустимым планом называется такой план ЗЛП, кото­рый удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планом х* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию

 

max f(x) = f(x*).

 

Величина f* =f(х*) называется оптимальным значением целевой функции.

Решением задачи называется пара (х*, f*), состоящая из oптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.

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

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

ограничения в виде неравенств преобразуются в уравне­ния за счет добавления фиктивных неотрицательных переменных хi, (i Î 1:m), которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;

переменные, на которые не наложено условие неотрица­тельности, представляются в виде разности двух новых неотрицательных переменных:

                                                                         -    =      -          =

хj = хj – хj, (xj ≥ 0, хj ≥ 0).

 

Проиллюстрируем применение описанных выше рекоменда­ций на примере. Пусть задана задача линейного программирова­ния (D, f) в общей форме с целевой функцией

 

f(x) = 5х1  + 3x2 + x3 + 2х4 -2х5  →  max

 

и множеством допустимых планов D, определенным системой уравнений и неравенств,

 

2х1

+ 4х2

+ 5x3

 

=7,

 

- 3x2

+ 4x3

– 5x4 – 4x5

≤ 2,

3х1

 

- 5x3

+ 6x4 – 2x5

≤ 4,

х1≥ 0,

 

x3

≥ 0.

 

 

Тогда в соответствии со сформулированными правилами эк­вивалентная каноническая задача будет иметь вид (D',f'), где:

 

 

а множество D' определено как:

 

 

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

 

1.2. ОСНОВНЫЕ СВОЙСТВА ЗЛП И ЕЕ ПЕРВАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

 

1.2.1. Основные понятия линейной алгебры и выпук­лого анализа, применяемые в теории математического программирования. Кратко напомним некоторые фундамен­тальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как линейного, так и нелинейного программирования.

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

Частными случаями линейных пространств являются веще­ственная прямая, плоскость, геометрическое трехмерное про­странство.

Вектор  λ1a1 + λ2a2 + …+ λmam называется линейной комбина­цией векторов а1 а2,..., аm с коэффициентами λ1, λ2, λm,

Система векторов линейного пространства а1 а2,..., аm называется линейно зависимой, если существуют такие числа λ1, λ2, λm не равные одновременно нулю, что их линейная комбинация λ1a1 + λ2a2 + …+ λmam  равняется нулевому вектору (вектору, все компоненты которого равны нулю). В против­ном случае систему а1, а2,..., аm называют линейно независи­мой, т. е. линейная комбинация данных векторов может быть равна нулевому вектору только при нулевых коэффициентах λ1, λ2, …, λm

Максимально возможное количество векторов, которые могут образовывать линейно независимую систему в данном линейном пространстве, называют размерностью простран­ства, а любую систему линейно независимых векторов в коли­честве, равном размерности, — базисом пространства.

Линейное пространство обычно обозначают как Rn, где n — его размерность.

Любое подмножество данного линейного пространства, ко­торое само обладает свойствами линейного пространства, назы­вается линейным подпространством. Множество Н, получае­мое сдвигом некоторого линейного подпространства L Ì Rn на вектор a Î Rn: H=L+a, называется аффинным множеством (пространством). Если фундаментальным свойством любого ли­нейного пространства или подпространства является принад­лежность ему нулевого вектора, то для аффинного множества это не всегда так. На плоскости примером подпространства явля­ется прямая, проходящая через начало координат, а аффинного множества — любая прямая на плоскости. Характеристическим свойством аффинного множества является принадлежность ему любой прямой, соединяющей две любые его точки. Размерность аффинного множества совпадает с размерностью того линейно­го подпространства, сдвигом которого оно получено.

Если рассматривается некоторое линейное пространство Rn, то принадлежащие ему аффинные множества размерности 1 на­зываются прямыми, а размерности (n-1)—гиперплоско­стями. Так, обычная плоскость является гиперплоскостью для трехмерного геометрического пространства R3, а прямая — ги­перплоскостью для плоскости R2. Всякая гиперплоскость делит линейное пространство на два полупространства.

Множество V векторов (точек) линейного пространства Rn называется выпуклым, если оно содержит отрезок прямой, соединяющей две его любые точки, или, другими словами, из того, что a ÎV и bÎV , следует, что х = (1- λ) х а+ λ х b Î V , где 0 ≤λ≤ 1.

Линейная комбинация

 

векторов а1, а2... аm называется выпуклой, если λi ≥0, iÎ1:m и

 

 

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

Выпуклая оболочка конечного множества точек называется выпуклым многогранником, а непустое пересечение конечного числа замкнутых полупространств — многогранным выпук­лым множеством. В отличие от выпуклого многогранника пос­леднее может быть неограниченным.

Точка v выпуклого множества V называется его угловой (крайней) точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V. Угловые точки выпуклого многогранника являются его верши­нами, а сам он — выпуклой оболочкой своих вершин.

Множество К называется конусом с вершиной в точке x0, если x0 Î К , и из того, что некоторая точка х принадлежит К ( х Î К ), следует, что в К содержится и луч, начинающийся в х0 и проходящий через х, т. е.

или

 

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

1.2.2. Первая геометрическая интерпретация ЗЛП и графический метод решения. Рассмотрим следующий пример. Пусть дана задача максимизации линейной целевой функции

f(x) =   3х1    + х2 → max

на множестве

 

Так как количество переменных в неравенствах, задающих область допустимых планов задачи, равно двум, то ее можно изобразить на координатной плоскости (см. рис. 1.1).

На рис. 1.1 показано, что каждое неравенство определяет некоторую полуплоскость. Соответствующие области для каж­дого ограничения отмечены штрихами. Пересечение D данных полуплоскостей (т. е. множество точек, которые одновременно принадлежат каждой их них) является областью допустимых планов задачи. Поведение целевой функции f(x) = 3х1 + х2 в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня.

Напомним, что линией уровня функции называется множе­ство точек из ее области определения, в которых функция при­нимает одно и то же фиксированное значение. Градиентом функции f(x) называется вектор

 

Δf(x) = df,…, df

dx1     dxn

 

указывающий направление наиболее быстрого возрастания фун­кции, и, стало быть, ориентированный перпендикулярно лини­ям уровня.

Для линейной функции двух переменных линия уровня пред­ставляет собой прямую, перпендикулярную вектору с, который служит градиентом данной функции. Следовательно, если ли­ния уровня определяется уравнением f(x)=c1x1+ c2x2 =const, то этот вектоp имеет вид

 

 

и указывает направление возрастания функции.

Таким образом, с геометрической точки зрения задача мак­симизации сводится к определению такой точки области D, че­рез которую проходит линия уровня, соответствующая наи­большему из возможных значений. Последнее означает, что для нахождения точки экстремума в задаче линейного программирования мы должны сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем необходимо осуществлять ее параллельное передвижение (так, чтобы она оставалась перпендикулярной вектору с) до тех пор, пока не достигнем такой точки области допустимых планов D, из которой смещение в направлении вектора с было бы невоз­можно. Такой метод решения получил название графического. Заметим, что решение задачи поиска минимума линейной функ­ции осуществляется аналогично, с той лишь разницей, что дви­жение по линиям уровня должно производиться в направлении, обратном градиенту целевой функции, т. е. по вектору (-с).

На рис. 1.1 изображен некоторый частный случай, для кото­рого решение ЗЛП достигается в угловой точке х* = (0, 6) обла­сти D. Нетрудно представить, что возможны и другие варианты. Они изображены на рис. 1.2.

Рисунок (а) иллюстрирует ситуацию неограниченности це­левой функции f(x)=cx на множестве D, т.е. сколько бы мы ни перемещались по линиям уровня в направлении вектора с, ее значение будет возрастать.

В случае, изображенном на рисунке (b), линия уровня, со­ответствующая максимальному значению f(x), касается грани множества D, и, соответственно, все точки, лежащие на этой гра­ни, являются оптимальными планами.

Во всех рассмотренных иллюстрациях допустимые планы ЗЛП представлялись в виде некоторого многогранного выпук­лого множества на плоскости. Такое их представление в лите­ратуре получило название первой геометрической интерпре­тации задачи линейного программирования.

Заметим также, что аналогичным образом могут быть пост­роены интерпретации ЗЛП для случая трехмерного простран­ства R3, где множеству D будет соответствовать некоторый ограниченный или неограниченный многогранник, а поведе­ние целевой функции будет характеризоваться поверхностями (плоскостями) уровня.

Несмотря на свою очевидную ограниченность, графический метод решения ЗЛП часто оказывается полезным. В частности, он может быть применен не только к задачам с двумя перемен­ными и ограничениями в виде неравенств, но и к каноническим задачам вида (1.7), у которых n - m = 2, где n — количество пе­ременных, а m — ранг матрицы А.

Действительно, можно выбрать две произвольные перемен­ные хj1,xj2 и, используя систему уравнений, выразить через них остальные переменные

 

 

 

где φj(xj1, xj2 ) —линейные функции.

Подставив выражения (1.9) в целевую функцию, мы получим эквивалентную задачу

 

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

 

Последняя ЗЛП может быть решена графически.

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

 

Теорема 1.1. Если целевая функция f принимает мак­симальное значение в некоторой точке множества до­пустимых планов D, то она принимает это значение и в некоторой угловой точке данного множества.

 

Доказательство.

Чтобы не усложнять изложение, ограничимся тем случаем, когда множество D ограничено, и, следовательно, является вы­пуклым многогранником.

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

 

Если D — замкнутое ограниченное выпуклое множе­ство, имеющее конечное число угловых точек, то лю­бая точка х Î D может быть представлена в виде вы­пуклой комбинации угловых точек D*.

 

* Строгое доказательство данного утверждения см., например, в [14].

 

Пусть х1, х2,…,хm — угловые точки множества D, а х* — точка, в которой целевая функция f достигает максимума.

На основе сформулированного выше утверждения точку х* можно представить в виде выпуклой комбинации угловых то­чек х1, х2,..., xm

 

Так как х* — точка максимума, то для любого х Î D сх* ≥ сх. Функция f(x) — линейная, поэтому

 

 

cледовательно,

 

где xr — угловая точка, удовлетворяющая условию

 

 

Из (1.10) видно, что сх* ≤ схr. В то же время справедливо об­ратное неравенство: сх* ≥ схr. Откуда следует, что сх* = схr, т. е. существует по крайней мере одна угловая точка хr, в которой целевая функция принимает максимальное значение. A

 

Теорема 1.2. Если целевая функция f принимает мак­симальное значение в нескольких точках множества D, то она принимает это же значение в любой точке, яв­ляющейся их выпуклой комбинацией.

 

Доказательство.

Пусть максимальное значение функции f достигается в точ­ках х̃1, х̃2,...,x̃s , т. е. сх~i=f*, iÎ l:s. Рассмотрим произвольную выпуклую комбинацию этих точек

 

 

Найдем значение целевой функции в точке х*

 

 

Итак, для произвольной выпуклой комбинации х* точек х̃1, х̃2,...,x~s справедливо равенство

 

 

1.3. БАЗИСНЫЕ РЕШЕНИЯ И ВТОРАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП

 

1.3.1. Векторная форма записи КЗЛП и ее примене­ние. Рассмотрим каноническую задачу линейного программи­рования

 

 

Обозначим через аj столбцы матрицы А и будем рассматри­вать их как векторы пространства Rm. Тогда каждому допусти­мому плану КЗЛП — n-мерному вектору х — соответствует неотрицательная линейная комбинация столбцов аj, равная столбцу bÎ Rm:

 

 

Такое представление ограничений КЗЛП обычно называют векторной формой записи.

Векторы аj, j Î l:n будем называть векторами требований задачи (D, f), а вектор b — вектором ограничений. Множе­ство всех неотрицательных линейных комбинаций столбцов аj  с геометрической точки зрения может быть представлено как многогранный выпуклый конус, натянутый на систему векто­ров аj  в пространстве Rm (рис. 1.3).

Соответственно, вопрос о существовании допустимого пла­на задачи (D, f) равнозначен вопросу о принадлежности векто­ра b данному конусу, а компоненты хj некоторого допустимого плана х Î D являются не чем иным, как коэффициентами раз­ложения вектора ограничений задачи b по векторам, требо­ваний аj.

Такое представление КЗЛП получило название второй гео­метрической интерпретации.

В дальнейшем без ограничения общности можем предпола­гать, что число уравнений, задающих множество D, меньше или равно числу переменных задачи (m ≤ n). Действительно, если это не так, то либо система уравнений Ах = b несовместна (и, зна­чит, множество D пустое), либо содержит избыточные (линейно зависимые) уравнения.

Если некоторые т столбцов аj1 ,аj2 ,...,аjm матрицы A явля­ются линейно независимыми, то они образуют базис в простран­стве Rm, и их, вообще говоря, будет достаточно для представ­ления вектора b в виде линейной комбинации указанных столбцов. Это означает, что остальные столбцы войдут в данное разложение с нулевыми коэффициентами. Если к тому же коэффициенты линейной комбинации окажутся неотрицатель­ными, то мы получаем так называемый базисный допустимый план х, у которого не более m компонентов отличны от нуля. Сформулируем определение базисного плана более строго, так как это одно из фундаментальных понятий теории линейного пpогpаммиpования.

 

 

Пусть задана некоторая каноническая ЗЛП (D,f), А —матрица системы ограничений задачи, и β= {аj1, аj2,..., аjm} —линейно независимая система столбцов матрицы А, образующая базис Rm. Обозначим множе­ство номеров столбцов, входящих в систему b, через N (β) = {j1, j2,..., jm}. План х называется базисным планом задачи (D,f), если его компоненты, соответствующие базисным столбцам и называемые базисными компонен­тами, больше или равны нулю (хj ≥ 0, j Î N (β)}, а все остальные компоненты (небазисные) — равны  нулю (xj = 0, j Ï N (β)).

 

Базисный план х называется невырожденным, если все его базисные компоненты строго  

      положительны, и вы­рожденным в противном случае.

 

1.3.2. Свойства базисных планов. Следующая теорема трактует понятие базисного плана в терминах первой геометри­ческой интерпретации ЗЛП.

 

Теорема 1.3. Каждый допустимый базисный план яв­ляется угловой точкой множества допустимых пла­нов D.

 

Доказательство.

Ради простоты положим, что базисными векторами являют­ся первые m столбцов матрицы A, т. е. β={al, a2,...,am}. Тогда утверждение теоремы 1.3 может быть переформулировано сле­дующим образом:

Если существует такой n-мерный вектор

 

 

что x1 a1 +х2 а2 +...+xk ak =b, то х есть угловая точка множе­ства D.

 

Проведем доказательство от противного, т. е. предположим, что рассматриваемый базисный план х не является угловой точ­кой множества D. Тогда ее можно представить в виде выпуклой комбинации некоторых двух различных допустимых планов х1 и х2:

 

x = λx1+(1-λ)x2, 0<λ<1.

 

В координатной форме последнее утверждение означает

 

 

Поскольку последние (n - k) компоненты вектора х по пред­положению равны 0, а числа хj1, xj2 ≥ 0 и λ, (1 -λ )>0, то эти же компоненты в векторах x1 и х2 также равны 0. Поэтому, с учетом допустимости планов х1 и х2, можно утверждать, что

 

 

Вычитая из (1.15) (1.16), получим

 

 

Так как векторы а1, а2,...,аk — линейно независимы, то коэф­фициенты х11 –х21 =0,..., х1k –х2k =0, из чего следует, что x1 =х2. Это противоречит предположению, что х1 и х2 являются раз­личными угловыми точками множества D. Следовательно, х не может быть представлен в виде выпуклой комбинации двух точек D и по определению является угловой точкой данного множества. A

Интересно отметить, что справедливо и обратное утвержде­ние, которое приведем без доказательства:

 

     Если х — угловая точка множества D, то она являет­ся допустимым базисным планом задачи (D, f).

 

В завершение параграфа необходимо отметить практиче­ское значение установленной связи между угловыми точками и допустимыми базисными решениями: она позволяет формали­зовать (и тем самым существенно упростить) процесс перехода от одной угловой точки к другой.

 

1.4. СИМПЛЕКС-МЕТОД

 

1.4.1. Основные этапы симплекс-метода. Исходя из свойств линейных экстремальных задач, рассмотренных в пре­дыдущих параграфах, можно заключить, что на принципиаль­ном уровне поиск их решений сводится к последовательному перебору угловых точек множества допустимых планов или, что то же самое, перебору соответствующих допустимых ба­зисных планов. Следует подчеркнуть, что такой перебор для реальных многомерных задач возможен только в теоретиче­ском плане и на практике неосуществим (или крайне неэффек­тивен) даже при условии использования мощной вычислитель­ной техники. Средством решения данной проблемы явились прикладные оптимизационные методы, основанные на последо­вательном, целенаправленном переборе базисных планов ЗЛП.

Классическим методом решения ЗЛП стал симплекс-ме­тод, получивший также в литературе название метода по­следовательного улучшения плана, разработанный в 1947г. американским математиком Джорджем Данцигом.

Идея такого перехода от одного базисного плана к другому, при котором происходит «улучшение» значения целевой функ­ции, может быть продемонстрирована для случая m = 2 с помо­щью рис. 1.4. Если вектор ограничений b принадлежит конусу, натянутому на некоторые два базисных вектора условий {аj1,аj2}, то существует такой базисный план х с базисными компонентами хj1, хj2, что b= хj1aj1 + хj2aj2 . Разумеется, таких планов может быть несколько в зависимости от выбора систе­мы базисных векторов. Чтобы различать их по соответствую­щей величине целевой функции f(x)=cj1xj1 +сj2хj2, вводятся так называемые расширенные векторы условий и ограничений. В общем случае расширенный столбец условий  āj получается соединением коэффициента целевой функции сj и столбца аj:

 

 

расширенный вектор ограничений определим как

 

 

В дальнейшем для удобства нумерации элементов будем счи­тать, что добавляемый коэффициент целевой функции сj явля­ется нулевым элементом j-го расширенного столбца условий, т. е. ā0,j = сj. При изображении расширенных векторов нулевая координата откладывается вдоль вертикальной оси — оси апп­ликат.

Рассмотрим также вектор

        =

Геометрически определение вектора b означает, что он при­надлежит конусу, натянутому на расширенные векторы, а век­тор служит его проекцией. Нулевая координата вектора b имеет вид:

 

 

т. е. равна значению целевой функции для выбранного базисно­го плана.

Из геометрической иллюстрации следует, что для решения задачи мы должны среди векторов аj выбрать такой набор {аj1,аj2}, чтобы, прямая, проведенная через конец вектора параллельно оси аппликат, пересекала конус, натянутый на систему соответствующих расширенных столбцов { āj1, āj2}, в «наивысшей» точке.

На рис. 1.4 выделен конус, натянутый на систему расширен­ных столбцов ā2 и ā3, отвечающих текущему допустимому ба­зису. Нетрудно заметить, что данный базис не является опти­мальным, например, для базиса {а3, а4} точка пересечения соответствующего конуса и прямой будет находиться выше. Можно, наоборот, указать базис с «худшим» значением целе­вой функции: {а1 а2}. Наконец, рассматриваемая геометричес­кая интерпретация КЗЛП иллюстрирует и общую идею крите­рия, который используется в симплекс-методе для определения оптимальности (или неоптимальности) текущего плана: если существуют векторы-столбцы, лежащие выше плоскости, проходящей через векторы текущего базиса, то он не явля­ется оптимальным и может быть «улучшен».

 

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

Для удобства дальнейшего изложения введем некоторые обозначения. Учитывая то, что симплекс-метод представляет собой некоторый итеративный вычислительный процесс, то че­рез q будем обозначать номер очередной (текущей) итерации. Соответственно, набор базисных столбцов, получаемых на q-й итерации, будет обозначаться как β(q):

 

 

Для того чтобы было легче отличить номер итерации от номе­ров компонентов матриц и векторов, он заключен в круглые скобки. Номера столбцов, входящих в базис, обозначим через N(β(q)), а именно

 

 

При этом Nr(β(q)) =jr — номер столбца, занимающего r-ю пози­цию в базисе. Тогда текущий базисный план х имеет вид:

 

Обозначим через Δ(ß(q)) матрицу, составленную из столбцов {аj1, аj2,..., аjm}, образующих базис, через Δ(ß(q)) матрицу, об­разованную из соответствующих расширенных столбцов и до­полненную слева столбцом специального вида:

 

 


а через ∆-1(β(q)) и ∆-1(β(q))  — матрицы, обратные по отношению к ним. Также представляется удобным ввести отдельные обо­значения для элементов матрицы ∆-1(β(q)):

δi(β(q)) — i-я строка матрицы ∆ˉ-1(β(q)), (i Î 0: m );

δij(β(q))  — элемент матрицы ∆-1(β(q)), находящийся в i-й строке j-го столбца (i Î 0: m, jÎ 0 : m).

Расширенный вектор ограничений b представляется в виде линейной комбинации расширенных векторов условий с коэф­фициентами, равными базисным компонентам текущего базис­ного плана:

 

 

Если интерпретировать компоненты векторов аj и b как ко­ординаты в ортогональном базисе, то их столбцы координат от­носительно произвольного базиса (β(q)), дополненного единич­ным вектором (-1,0,..., 0), направленным противоположно оси аппликат примут вид:

 

 

а для расширенной матрицы задачи в целом можно записать

 

 

Нулевая строка данной матрицы a0(β(q)) содержит координаты расширенных векторов условий по оси аппликат. Согласно по­строению, элементы данной строки имеют следующие знаки:

a0,j (β(q)) < 0 — для расширенных векторов условий, рас­положенных выше плоскости, натянутой на систему расширенных базисных векторов;

a0,j (β(q)) > 0 — для расширенных векторов условий, рас­положенных ниже плоскости, натянутой на систему расширенных базисных векторов;

a0,j (β(q))  = 0 — для расширенных базисных векторов.

Подводя итог сказанному, сформулируем критерий опти­мальности допустимого базисного плана в симплекс-методе:

F план является оптимальным, если для всех j Î1: n a0,j (β(q)) ≥ 0, и неоптимальным в противном  

    случае, т. е. если существует такое l Î l : n, что a0l (β(q)) < 0.

Значения a0,j (β(q)) также называют оценками столбцов мат­рицы А относительно текущего базиса, или симплекс-разнос­тями.

В случае неоптимальности текущего базиса в алгоритме сим­плекс-метода осуществляется переход к следующему базису. Это делается за счет вывода одного столбца из базиса и ввода другого. Для обеспечения улучшения значения целевой фун­кции в базис должен быть введен вектор-столбец, имеющий от­рицательную оценку. Если таких столбцов несколько, то для ввода рекомендуется выбирать столбец, имеющий макси­мальную по модулю оценку. Отметим, что данное правило но­сит относительный характер и не гарантирует наилучшего выбора вводимого столбца. Одновременно на этой стадии тре­буется принять решение о том, какой столбец следует вывести из базиса. Сделать это нужно таким образом, чтобы вновь формируемый базис оказался допустимым. Данное требование может быть легко проиллюстрировано для случая m = 2. Например, на рис. 1.3 векторы {а2,а3} образуют допустимый ба­зис, а векторы {а3,a4} —недопустимый, т. к. разложение b по а3 и а4 содержит один отрицательный компонент плана, что противоречит условиям КЗЛП.

Можно доказать, что допустимость базиса, к которому осу­ществляется переход, обеспечивается следующим правилом вывода столбца из текущего базиса:

F для столбца l, претендующего на ввод в базис, и вектора ограничений b рассматриваются

     отношения

 

и определяется такая строка r, что

 

 

Полученный индекс r определяет номер столбца в N(β(q)), выводимого из базиса, а именно, N(β(q)).

 

Таким образом, если базис на q-й итерации включал столбцы с номерами

 

 

то базис на итерации q + 1 будет состоять из столбцов с номе­рами:

 

 

Отдельно следует обсудить тот случай, когда столбец al (β(q)), претендующий на ввод в базис, не содержит положительных компонентов al (β(q)) ≤ 0). Это означает, что целевая функция в задаче не ограничена на множестве допустимых значений, т. е. может достигать сколь угодно большого значения. Последнее, очевидно, означает завершение процесса вычислений ввиду отсутствия оптимального плана. Геометрически ситуация, когда al (β(q)) ≤ 0, соответствует тому, что ось ординат оказыва­ется внутри конуса, натянутого на систему расширенных стол­бцов аj, а значит, прямая, проведенная через конец вектора b параллельно оси аппликат, однажды «войдя» в этот конус, более никогда из него «не выходит».

Вообще говоря, после перехода от базиса β(q) к базису β(q+1) мы можем заново сформировать матрицы ∆ (β(q+1)), Δ-1 (β(q+1)) и, вычислив А(β(q+1)) = Δ-1 (β(q+1))A, делать выводы о его оптималь­ности. Однако, учитывая, что β(q+1) отличается от β(q) всего лишь одним столбцом, с точки зрения техники вычислений представляется рациональным непосредственно переходить от A (β(q)) и b (β(q))  к A (β(q+1)) и b (β(q+1)) . Дело в том, что у матриц типа A (β(q)) столбцы, соответствующие базисным векторам, состоят из нулей, за исключением одного элемента, равного единице. Позиция этого ненулевого элемента определяется по­рядковым номером базисного столбца в N(β(q)). Поэтому для получения матрицы A (β(q+1))  достаточно с помощью линейных операций над строками матрицы A (β(q)) привести ее столбец, соответствующий вводимому в базис вектору, к «базисному» виду.

Для это применяется преобразование Жордана—Гаусса (так называемый метод полного исключения). В данном случае оно состоит в том, что мы должны «заработать» единицу на мес­те элемента ar,l(β(q)) (он обычно называется ведущим)* и нули на месте остальных элементов столбца al(β(q)). Первое достига­ется посредством деления r-й строки на ведущий элемент, вто­рое — путем прибавления вновь полученной r-й строки, умно­женной на подходящий коэффициент, к остальным строкам матрицы A(β(q)).

* Напомним, что l — номер столбца, вводимого в базис, а r — номер строки в симплекс-таблице, определяющей номер столбца, выводимого из базиса.

 


Формально результат выполнения данного преобразования над элементами A(β(q)) и b(β(q))   может быть выражен в следующем виде

 

 


Следует особо отметить смысл элементов вектора b(β(q)). Его нулевой компонент b0(β(q)) в соответствии с построением содержит значение целевой функции, достигаемое ею на теку­щем плане

 

 

а остальные элементы — ненулевые компоненты этого плана:

 

 

Название метода произошло от понятия симплекса. Напом­ним, что m-симплексом называют выпуклый многогранник, аффинная оболочка* которого есть аффинное множество размерности m. В данном случае можно считать, что система рас­ширенных базисных столбцов {аj1 ,аj2,..., аjm}, рассматривае­мых как точки в Rm+1, порождает (m -1)-мерный симплекс в пространстве Rm+1.

* Аффинной оболочкой множества называют наименьшее аффинное множество, в котором содержится данное множество.

 

В заключение настоящего пункта обобщим изложенные во­просы и приведем схему алгоритма симплекс-метода для решения задачи максимизации. Она включает однократно выполняемый 0-этап и повторяемый конечное число раз I-этап (стандартную итерацию).

0-этап. Нахождение допустимого базисного плана (см. п. 1.4.5). Результатом 0-этапа является допустимый базис­ный план х(β(1)), а также соответствующие ему матрица A(β(1)) и вектор b(β(1)), которые будут использованы на первой итера­ции. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.

I-этап. Стандартная итерация алгоритма — выполня­ется для очередного базисного плана x(β(q)).

1°. Проверка оптимальности текущего базисного плана: осуществляется просмотр строки оценок а0(β(q) ). Возможны два варианта:

1′. a0(β(q) )≥0 — план, соответствующий текущему базису за­дачи, оптимален. Вычислительный процесс закончен. Соглас­но формулам (1.33) и (1.32) выписываются оптимальный план задачи х* = x(β(q)) и значение целевой функции f(x*) = f(x(β(q))).

1″. В строке оценок а0(β(q)) существует по меньшей мере один элемент а0,j (β(q))<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план x(β(q))  —неоптимален. Выбирается столбец с номером l, имеющий минимальную (максимальную по абсолютной величине) отрицательную оценку

 

 

Он называется ведущим и должен быть введен в очередной базис. Переходим к пункту 2° алгоритма.

2°. Определение столбца, выводимого из базиса. Рассмат­ривается ведущий столбец аl(β(q)) Возможны два варианта:

2'. Для всех iÎ1:m аi,l(β(q))≤0. Делается вывод о неогра­ниченности целевой функции и завершается вычислительный процесс.

2". Существует по крайней мере одна строка с номером iÎ1:m, для которой аi,l(β(q))>0 . Согласно правилу (1.27) опре­деляются место r и номер Nr (β(q)) = jr для столбца, выводимого из базиса. Переходим к пункту 3° алгоритма.

3°. Пересчет элементов матрицы А и столбца b относи­тельно нового базиса. В соответствии с формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи А и век­тора ограничений b относительно базиса β(q+1), который полу­чается после введения в базис β(q) столбца аl и выводом из него столбца аr. Полагаем номер текущей итерации q: = q+l и пере­ходим к первому пункту алгоритма.

 

Рис.1.5

 

1.4.2. Табличная реализация симплекс-метода. С точ­ки зрения обеспечения рациональности и наглядности вычис­лительного процесса выполнение алгоритма симплекс-метода удобно оформлять в виде последовательности таблиц. В различ­ных источниках приводятся разные модификации симплекс-таблиц, отличающиеся друг от друга расположением отдель­ных элементов. Однако это не должно вызывать смущения у читателя, так как все они базируются на одних и тех же прин­ципах. Остановимся на структуре таблицы, показанной на рис. 1.5.*

* Настоящая структура симплекс-таблиц строится на идеях и прин­ципах их организации, предложенных в [1].

 

Симплекс-таблица Т(q), изображенная на рис. 1.5, соответ­ствует допустимому базису КЗЛП β(q)), получаемому на q-й ите­рации. Столбец N(β(q)) содержит номера базисных столбцов (в той последовательности, в которой они входят в базис), стол­бец b(β(q)) —компоненты вектора ограничений относительно текущего базиса β(q), A(β(q)) — компоненты матрицы задачи относительно текущего базиса β(q). Наконец, в строке а0(β(q)) находятся текущие оценки столбцов, а ячейка b0(β(q)) содержит значение целевой функции, достигаемое для текущего плана.

Безусловно, следует добавить, что табличная модификация симплекс-метода имеет важное практическое значение не столько как удобная форма организации ручного счета, сколь­ко как основа для реализации данного алгоритма в рамках про­граммного обеспечения ЭВМ.

1.4.3. Пример решения ЗЛП симплекс-методом. Рас­смотрим на конкретном примере процесс решения КЗЛП таблич­ным симплекс-методом. Пусть дана каноническая задача ЛП:

 

 

Как видно, столбцы матрицы с номерами {5, 2, 3} являются линейно независимыми. И можно получить разложение по дан­ным столбцам вектора ограничений с положительными коэф­фициентами. Последнее означает, что столбцы {5, 2, 3} образу­ют допустимый базис, с которого можно начать решение задачи. Из столбцов, входящих в базис, с учетом нулевых эле­ментов формируется матрица Δ(β(1)) и обратная по отношению к ней Δ-1(β(1)):

 

 

Используя их, по формуле (1.26) получаем

 

 

 

-84

0

0

-88

0

 

 

1/3

0

0

1/3

1

 

=

2

1

0

3

0

;

 

-2/3

0

1

-4/3

0

 

 

 


Используя полученные значения A(β(1)) и b(β(1)), заполняем симплекс-таблицу T(1), соответствующую первой итерации (q=1).

 

 

Поскольку строка оценок a0(β(1))  в первом и четвертом столбцах содержит отрицательные элементы (a0,1(β(1)) = -84, a0,4(β(1)) = -88), план х(β(1)) = (0,14,17/3,0,4) не является оптимальным, и значение целевой функции f(x(β(1))) = -226 может быть улучшено. Следуя рекомендации п.1˝ алгоритма симплекс-метода, полагаем номер вводимого в очередной базис столбца l = 4 (т.к. |-88| > |-84|). Рассматриваем ведущий столбец (выделен пунктирной рамкой)   

 

Он содержит два положительных элемента. Применяя рекомен­дацию п. 2" алгоритма, получаем λ1= 4/(1/3) =12, λ2=14/3, и, стало быть r = 2. Следовательно, столбец с номером N2(β(1)) = 2 должен быть выведен из базиса. Таким образом, по­лучаем очередной допустимый базис задачи N(β(2)) = {5, 4, 3}. Элемент a2,3(β(1))  является ведущим (обведен кружком). При­менив формулы (1.28)-(1.31), переходим к симплекс-таблице, соответствующей второй итерации T(2), и полагаем индекс те­кущей итерации q = 2.

 

 

В ходе выполнения второй итерации опять-таки определяют­ся вводимый столбец а1, выводимый а4 и ведущий элемент a2,1(β(2)). Перейдя к итерации q = 3, имеем таблицу T(3).

 

 

Как видно из T(3), строка оценок содержит только неотрицатель­ные значения, поэтому достигнутый базис N(β(3)) = {5, 1, 3} яв­ляется оптимальным. В итоге мы получаем, что вектор х* = (7, 0, 31/3, 0, 5/3) является оптимальным планом (точ­кой максимума) задачи (1.34)-(1.35), максимальное значение целевой функции равно f* =f(х*)=362, а решение КЗЛП имеет вид ((7, 0, 31/3, 0, 5/3); 362).

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

Легко заметить, что проблемы со сходимостью симплекс-ме­тода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения от­ношения

 

 

будут достигнуты для нескольких строк таблицы Т (q) одновре­менно. Тогда на следующей итерации столбец b(β(q+1)) будет со­держать нулевые элементы. Напомним, что

 

допустимый базисный план канонической задачи ЛП, со­ответствующий базису β(q), называется вырожденным, если некоторые его базисные компоненты равны нулю, т. е. вектор b(β(q)) содержит нулевые элементы.

 

Задача ЛП, имеющая вырожденные планы, называется вы­рожденной. При «выходе» на вырожденный план мы фактиче­ски получаем разложение столбца b по системе из меньшего, чем m, количества столбцов аj и, следовательно, лишаемся воз­можности корректно определить, ввод какого столбца в базис приведет к росту значения целевой функции. Подобные ситуа­ции, в конечном счете, могут привести к зацикливанию вычис­лительного процесса, т. е. бесконечному перебору одних и тех же базисов.

С точки зрения первой геометрической интерпретации ЗЛП ситуация вырожденности означает, что через некоторую угло­вую точку многогранного множества допустимых планов зада­чи, соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений задачи. Иными сло­вами, одно или несколько ограничений в данной точке являют­ся избыточными. Последнее предоставляет повод для размыш­лений об экономической стороне проблемы вырожденности как проблемы наличия избыточных ограничений и в некоторых случаях определяет пути ее решения.

С точки зрения второй геометрической интерпретации ЗЛП вырожденность означает «попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро кону­са, натянутого на систему расширенных векторов текущего базиса. Так, в случае, изображенном на рис. 1.6, эта линия по­падает в ребро, определяемое вектором аj2 , т. е., несмотря на то что текущий базис содержит столбцы аj1 и аj2, для представле­ния вектора b достаточно только одного аj2.

Из данной интерпретации вытекает и идея метода решения вырожденных задач ЛП, получившего названия метода возму­щений: при выходе на вырожденный план осуществляется не­значительный сдвиг вектора b и вырожденность (как это видно из иллюстрации) устраняется.

Необходимо, однако, сказать, что рассмотренная здесь про­блема зацикливания для большинства практически значимых задач является достаточно редкой и маловероятной. Более того, она очень часто разрешается за счет ошибок округлений при выполнении расчетов на ЭВМ.

1.4.5. Нахождение допустимого базисного плана. В рас­смотренном выше примере исходный базисный план, необходи­мый для начала вычислений по симплекс-методу, был подобран за счет особенностей матрицы условий. Действительно, данная матрица уже содержала необходимое количество «почти базис­ных» столбцов. Очевидно, что для подавляющего большинства задач ЛП невозможно подобным образом сразу и в явном виде указать исходный допустимый базисный план. Вообще говоря, существуют различные приемы решения данной задачи. Мы остановимся на одном из них, получившем название метода минимизации невязок. Его сильной стороной, безусловно, яв­ляется универсальность. Xотя, в некоторых частных случаях, он может оказаться слишком громоздким.

 

 

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

Не умаляя общности, можно считать, что вектор ограниче­ний в исходной задаче неотрицателен, т. е. bi ≥ 0, i Î 1: m. Тогда для КЗЛП максимизации функции

 

 

на множестве, определяемом ограничениями

 

 

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

 

 

Как видно из (1.36)-(1.39), задача (,) отличается от за­дачи (D, f) матрицей, получаемой в результате добавления к исходной матрице А единичной матрицы, которой соответ­ствуют дополнительные (фиктивные) переменные хn+1,...,хn+m. Данным переменным (собственно говоря, их и называют не­вязками) в целевой функции  отвечают коэффициенты (-1), а переменным х1,...,хn, которые являются общими для обеих задач, — нулевые коэффициенты. Существенной особенно­стью (,) является наличие в ней очевидного исходного ба­зиса, образуемого добавленными столбцами, и соответствую­щего плана с базисными компонентами хn+i = bi ≥ 0, i Î 1: m. В силу структуры целевой функции f̃ в процесс поиска ее мак­симума процедурой симплекс-метода фиктивные переменные (невязки) хn+i  должны минимизироваться желательно до нуля, что может быть достигнуто за счет последовательного перевода их в небазисные компоненты плана. Если в оптималь­ном плане х̃, полученном в результате решения вспомогатель­ной задачи, последние m компонент (т. е. невязки) равны нулю, то его начальные n компонент удовлетворяют системе ограни­чений, определяющих область D, и  легко (простым отбра­сыванием невязок) может быть преобразован в стартовый до­пустимый план основной задачи (D, f). При этом все строки симплекс-таблицы, полученной на последней итерации вспо­могательной задачи (за исключением нулевой), могут быть перенесены в первую таблицу основной задачи. Элементы же нулевой строки для вновь формируемой симплекс-таблицы вы­числяются по формулам:

 

 

где β(*) — базис, полученный на последней итерации вспомога­тельной задачи.

В случае, когда оптимальный план вспомогательной задачи х̃ все же содержит не равные нулю фиктивные компоненты (т. е. ()<0), мы приходим к заключению об отсутствии до­пустимых планов у исходной задачи (D, f), т. е. D = Ø.

 

1.5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

 

1.5.1. Вычислительная схема, основанная на преобра­зовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, не­трудно заметить, что наиболее критичным в этом плане являет­ся этап пересчета значений А и b при переходе от одного базис­ного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных n, можно добиться существенной «экономии», вы­полняя на очередной итерации q преобразование  Жордана—Га­усса   не  над   матрицей А(β(q)),   а   над   матрицей Δ-1(β(q)). При этом учитывается и то, что при необходимости, применяя формулу (1.26), всегда можно получить А(β(q)) по Δ-1(β(q)). Более того, для выполнения описанных выше действий симплекс-процедуры нам в действительности не требовалась матрица А(β(q)) целиком. Реаль­но в ней использовались только строка оценок a0(β(q))  и ведущий столбец al(β(q)). Данные соображения положены в основу вы­числительной схемы симплекс-метода, основанной на преобра­зовании обратных матриц, которую также называют модифици­рованным симплекс-методом. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.

 

 

Вычислительной схеме модифицированного симплекс-мето­да соответствует система таблиц T1 и Т2(q). Таблица T1 (рис. 1.7) является общей для всех итераций и служит для получения строки оценок текущего базисного плана a0(β(q)). Если обозна­чить через δi(β(q))   (i Î 0 : m) строки матрицы Δ-1(β(q)), то из (1.26), в частности, следует, что

 

 

Как видно из рис. 1.7, T1 состоит из трех блоков:

в центре содержится матрица А;

в левом блоке таблицы на каждой итерации дописывают­ся нулевые строки матрицы Δ-1(β(q)) для текущего ба­зиса;

нижний блок, расположенный под матрицей А, на каж­дой итерации дополняется строкой оценок текущего плана, вычисленной по формуле (1.42).

Симплекс-таблица Т2(q), изображенная на рис. 1.8, соответ­ствует допустимому базису КЗЛП β(q), получаемому на q-й ите­рации. Столбец N(β(q)) содержит номера базисных столбцов (в последовательности вхождения в базис); столбец b(β(q)) — компоненты вектора ограничений относительно текущего ба­зиса β(q); Δ-1(β(q)) — матрица, обратная по отношению к матри­це расширенных столбцов текущего базиса β(q); графа аl со­держит расширенный вектор условий, вводимый в базис на текущей итерации, а следующая графа — координаты аl(β(q)) этого же столбца в текущем базисе β(q).

 

 

По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.

0-этап. Нахождение допустимого базисного плана.

1. Для поиска допустимого базиса может быть применен ме­тод минимизации невязок, рассмотренный в п. 1.4.5. При этом для решения вспомогательной задачи используется процедура модифицированного симплекс-метода. В результате 0-этапа мы получаем допустимый базисный план x(β(1)) и соответствую­щие ему матрицу Δ-1(β(1)) и вектор b(β(1)).

2. Заполняем центральную часть таблицы T1, содержащую матрицу А.

3. Содержимое матрицы Δ-1(β(1)) и вектора b(β(1)), получен­ных на этапе поиска допустимого базисного плана, переносит­ся в таблицу T2(1).

4. Полагаем номер текущей итерации q равным 1 и перехо­дим к I-этапу.

1-этап. Стандартная итерация алгоритма — выполня­ется для очередного базисного плана x(β(q)).

1°. Проверка оптимальности текущего базисного плана. Содержимое нулевой строки таблицы T2(q) — δ0(β(q)) переписы­вается в соответствующую графу таблицы T1. По формуле (1.42) рассчитываем и заполняем строку a0(β(q)). Осуществля­ем просмотр строки оценок a0(β(q)). Возможны два варианта:

1΄. a0(β(q))≥0 —план, соответствующий текущему базису задачи, оптимален. Вычислительный процесс закончен. Со­гласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х* = x(β(q)) и оптимальное значение целевой функ­ции f(х*) = f(x(β(q))).

1". В строке оценок a0(β(q)) существует по меньшей мере один элемент a0,j(β(q))<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план x(β(q)) — неоптимален. Выбирает­ся номер l, соответствующий элементу, имеющему минималь­ную (максимальную по абсолютной величине) отрицательную оценку:

 

l-й столбец матрицы A становится ведущим и должен быть вве­ден в очередной базис. Переходим к пункту 2° алгоритма.

2°. Определение столбца, выводимого из базиса. Перепи­сываем ведущий столбец аl из таблицы T1 в текущую таблицу Т2(q). По формуле аl(β(q)) = Δ-1(β(q))аl заполняем соответствую­щий столбец в таблице Т2(q). Возможны два варианта:

2'. Для всех i Î 1: m аi,l(β(q))≤0. Делается вывод о неограни­ченности целевой функции и завершается вычислительный процесс.

2". Существует по крайней мере один индекс i Î 1: m, для ко­торого аi,l(β(q))>0. Согласно правилу (1.27) определяются мес­то r и номер Nr(β(q)) для столбца, выводимого из базиса. Пере­ходим к пункту 3° алгоритма.

3°. Пересчет относительно нового базиса элементов столбца b и матрицы Δ-1. Переход к новому базису β(q+1), кото­рый получается введением в базис β(q) столбца аl и выводом из него столбца аr, осуществляется по формулам, аналогичным формулам (1.28)-(1.31). Они имеют вид:

 

 

Полагаем номер текущей итерации q: =q+l и переходим к первому пункту алгоритма.

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

1.5.2. Пример решения ЗЛП модифицированным сим­плекс-методом. Приведем решение рассмотренной ранее за­дачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3 оно начинается с выбора очевидного исходного базиса, обра­зуемого столбцами {5,2,3}. Для него уже были вычислены Δ-1(β(q)) и b(β(q)), поэтому заполнение начальных таблиц T1 и Т2(1) не представляет труда.

На первой итерации мы переписываем нулевую строку

 

 


из Т2(1) в T1 и, умножив ее на матрицу A, получаем строку оце­нок

 

 

Так как a0(β(1)) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β(1), и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l = 4.

Переписываем столбец

 

 

из таблицы T1 в Т2(1) и пересчитываем его координаты относи­тельно текущего базиса, т. е. умножаем матрицу Δ-1(β(q)), рас­положенную в таблице Т2(1)  слева, на а4.

 

 

 

После заполнения таблицы Т2(1) данными по вводимому в но­вый базис столбцу можно перейти к определению номера выво­димого столбца. Эта процедура осуществляется в полной ана­логии с обычным симплекс-методом. Рассмотрев отношения элементов bi(β(1))  и ai,l(β(1))  для {iÎ1:m| ai,l(β(1))>0} и определив минимальное из них, находим, что r = 2. Следовательно, стол­бец с номером N2(β(q)) = 2 должен быть выведен из базиса. Та­ким образом, получаем очередной допустимый базис задачи с N(β(2)) = {5, 4, 3}. Элемент a2,3(β(1))  является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к сим­плекс-таблице, соответствующей второй итерации Т2(2), и пола­гаем индекс текущей итерации q = 2.

Повторяя те же самые действия (их легко проследить по при­водимым здесь таблицам Т2(2) и Т2(3), на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т2(3). Легко заметить, что в процессе решения мы «про­шли» по той же самой последовательности допустимых базис­ных планов, которая встречалась в п. 1.4.3.

 

1.6. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

 

1.6.1. Понятие двойственной задачи ЛП. Пусть задана КЗЛП (1.7). Если целевая функция f(x) = cx достигает макси­мального значения на множестве D, то обоснованным представ­ляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некото­рый m-мерный вектор, то

 

 

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с. Тогда при любых х ≥ 0 справедливо неравенство

 

Стремясь получить наилучшую оценку (1.47), мы приходим к формулировке некоторой новой кстремальной задачи, которая в некотором смысле логически сопряжена с задачей (1.7) называется двойственной. Оговоримся, что приведенные рассуждения не носят строгого характера и предназначены только для того, чтобы подготовить читателя к приводимому ниже формальному определению двойственной задачи линейного прoграммирования.

 

F Если задана каноническая задача ЛП

 

 

     то задача ЛП

 

    называется двойственной по отношению к ней. Соот­ветственно, задача (D, f) no отношению к  

    (D*,f*) назы­вается прямой (или исходной).

 

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

 

F Если задана общая задача ЛП

 

f(x) = c1x1 + ... + сjхj + сj+1хj+1 + ... + сnxn → max, x Î D, (1.50)

 

     где D определяется системой уравнений и неравенств:

 

 

     то двойственной по отношению к ней называется об­щая задача ЛП

 

 

     где D* определяется системой уравнений и неравенств:

 

 

Правила построения задачи, двойственной по отношению к ОЗЛП, наглядно представлены схемой, показанной на рис. 1.9.

 

 

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. макси­мум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции с и столбец огра­ничений b меняются местами.

3. Матрица ограничений задачи A транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, хj ≥ 0 или uj ≥ 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (aju ≥ сj или aix ≤ bj).

5. Множество номеров ограничений, имеющих форму нера­венств в прямой задаче (например, aix ≤ bj  или aju ≥ сj), опреде­ляют множество индексов переменных, на которые накладыва­ется условие неотрицательности, в двойственной задаче (ui ≥ 0 или xi ≥ 0).

Из приведенного определения вытекает важное свой­ство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, со­впадает с прямой (исходной) задачей:

 

Тем самым имеет смысл говорить о паре взаимно двой­ственных задач.

 

В матричной форме пара двойственных общих задач линей­ного программирования может быть кратко записана как:

 

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП (D, f):

 

тогда двойственной к ней будет задача (D*, f*):

 

 

1.6.3. Теоремы двойственности и их применение. Фун­даментальные свойства, которыми обладают двойственные за­дачи линейного программирования, могут быть сформулирова­ны в виде приводимых ниже утверждений. Их обычно называют теоремами двойственности.

 

Теорема 1.4. Если х, и— допустимые планы для пары двойственных задач (D,f) и (D*,f*), тo f(x)  ≤ f(u).

Доказательство.

Достаточно доказать теорему для случая, когда задача (D, f) является канонической. Рассмотрим пару двойственных задач

 

Из того, что вектор и является допустимым планом задачи (D*, f*), следует, что иА ≥ с. Умножив левую и правую части дан­ного неравенства на вектор х ≥ 0 , получим равносильную сис­тему неравенств

 

 

Одновременно для вектора х, являющегося допустимым планом задачи (D, f), справедливо равенство Ax=b. Тем самым доказа­но, что иb ≥ сх.A

Замечание. Теорема 1.4, разумеется, верна и для оптималь­ных планов взаимно двойственных задач: f(x*) ≤ f*(u*), где х* и u*—любые оптимальные планы задач (D, f) и (D*,f*). На самом деле, как будет видно из дальнейшего, справедливо равенство f(x*) = f*(u*).

Теорема 1.5. Если для некоторых допустимых планов  и  взаимно двойственных задач (D, f) и (D*,f*) вы­полняется равенство f()=f*(), то  и  являются оптимальными планами для этих задач.

Доказательство.

Согласно теореме 1.4, для всех допустимых планов х задачи (D, f) справедливо неравенство сх < b. По условию теоремы f()=f() или, что то же самое, с = b. Следовательно, верно утверждение: для любого x Î D с>сх, т. е. х является опти­мальным планом для задачи (D, f).

Рассуждения, доказывающие оптимальность плана  для за­дачи (D*,f*), проводятся аналогично. A

Теорема 1.6. Если целевая функция f в задаче (D, f) не ограничена сверху, то двойственная к

ней задача (D*,f*) не имеет допустимых планов.

Доказательство.

Если предположить, что у двойственной задачи (D*,f*) су­ществует хотя бы один допустимый план и̃, то, согласно теоре­ме 1.4, для любого допустимого плана х задачи (D, f) справед­ливо неравенство f(x) ≤ f*() <+∞. Последнее означает, что целевая функция f задачи (D, f) ограничена сверху. Поскольку это противоречит условию теоремы, предположение о сущест­вовании допустимых планов двойственной задачи (D*,f*) не­верно. A

Следующее утверждение, известное как теорема равнове­сия, используется при проверке оптимальности планов ЗЛП.

Теорема 1.7. Пусть х* и u* — оптимальные планы ка­нонической задачи (D, f) и двойственной по отноше­нию к ней задачи (D*,f*). Если j-я компонента плана х* строго положительна (xj*>0), то соответствующее j-e ограничение двойственной задачи выполняется как равенство: а1,ju1* +...+аm,jum*= сj; если же j-й компо­нент плана х* имеет нулевое значение (хj* =0), то j-e ограничение двойственной задачи выполняется как неравенство: а1,ju1* +...+аm,jum*≥ сj .

Доказательство.

Векторы х* и и*, будучи допустимыми планами соответствую­щих задач, удовлетворяют условиям: Ах* = b, х* > 0 и и*А-с ≥ 0. Найдем скалярное произведение

 

 

Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных задач совпадают, т. е. u*b=сх*. Последнее означает, что (u*А-с)х* = 0 . Однако ска­лярное произведение двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные про­изведения их соответствующих координат равны нулю. Следо­вательно, если xj* > 0, то u*аj – сj = 0, если же xj = 0, то возмож­но u*аj – сj ≥ 0 , что и утверждается в теореме. A

Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения основной задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, область до­пустимых значений которой описывается двумя уравнениями, связывающими шесть переменных (m = 2, n = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая име­ет только две переменные.

Еще раз вернемся к таблице Т2(q) (рис. 1.8), получаемой на финальной итерации процедуры модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы Δ-1(β(q)), для которой было введено обозначение δ0(β(q)). По­элементно она может быть записана в следующем виде:

 

Введем вектор  = (δ0,1(β(q)), δ0,2(β(q)),..., δ0,m(β(q))). Нетруд­но проверить, что строка оценок a0(β(q)) может быть представ­лена следующим образом:

 

 

Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. ũА≥с. Следовательно, век­тор и является допустимым планом двойственной задачи.

В то же время элемент b0(β(q)), содержащий текущее значе­ние целевой функции и равный на последней итерации f(x*), до­пускает представление

 

 

Согласно теореме 1.5 из равенства f(х*) = f*(ũ) вытекает, что вектор ũ служит оптимальным планом двойственной задачи: u = ũ.

Окончательно можно утверждать, что для оптимального базиса

 

 

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

 

Читателю в качестве самостоятельного упражнения предла­гается построить задачу, двойственную к (1.34)-(1.35), реше­ние которой было приведено в п. 1.5.2, и убедиться, что вектор u = (-10, 32, 2), полученный в таблице Т2(3), является для нее допустимым и оптимальным планом.

1.6.4. Экономическая интерпретация. Традиционная экономическая интерпретация двойственной задачи ЛП бази­руется на модели простейшей задачи производственного планирования, описанной во введении. Напомним, что в ней каждый (j-й) элемент вектора х рассматривается как план вы­пуска продукции данного вида в натуральных единицах, сj — цена единицы продукции j-го вида, аj — вектор, определяющий технологию расходования имеющихся m ресурсов на производ­ство единицы продукции j-го вида, b — вектор ограничений на объемы этих ресурсов.

Предположим, что для некоторых значений A, b и с найден оптимальный план х*, максимизирующий суммарный доход max{cx}=cx*. Достаточно естественным представляется во­прос: как будет изменяться оптимальный план х* при измене­нии компонент вектора ограничений b и, в частности, при ка­ких вариациях b оптимальный план х* останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчи­вости х* имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсов bi; могут существенно колебаться после принятия планового решения х*.

Когда вектор ограничений b изменяется на Δb или, как еще говорят, получает приращение Δb, то возникают соответству­ющие вариации для оптимального плана х*(b+Δb) и значения целевой функции f(х*(b+Δb)). Допустим, приращение Δb та­ково, что оно не приводит к изменению оптимального базиса задачи, т. е. х*(b+Δb)≥ 0. Определим функцию F(b), возвраща­ющую оптимальное значение целевой функции задачи (D(b), f) для различных значений вектора ограничений b

 

 

Рассмотрим отношение ее приращения F(b+Δb)-F(b) к при­ращению аргумента Δb. Если для некоторого i устремить Δbi → 0, то мы получим

 

 

Учитывая, что в соответствии с теоремой 1.5

 

 

и подставив (1.57) в (1.56), приходим к выражению

 

 

Из формулы (1.58) вытекает экономическая интерпре­тация оптимальных переменных двойственной зада­чи. Каждый элемент ui* может рассматриваться как предель­ная (мгновенная) оценка вклада i-го ресурса в суммарный доход F при оптимальном решении х*. Грубо говоря, величи­на ui* равна приросту дохода, возникающему при увеличе­нии ресурса i на единицу при условии оптимального ис­пользования ресурсов.

 

В различных источниках компоненты оптимального плана двойственной задачи также называются двойственными оцен­ками или теневыми ценами, а Л. В. Канторович предлагал та­кой термин, как объективно обусловленные оценки.

На основе теорем двойственности для пары задач ЛП в об­щей форме могут быть сформулированы некоторые важные (с точки зрения экономической интерпретации) следствия.

 

Если при использовании оптимального плана прямой за­дачи i-e ограничение выполняется как строгое неравен­ство, то оптимальное значение соответствующей двой­ственной переменной равно нулю, т.е. если

 

В рамках рассматриваемой задачи производственного плани­рования это означает, что если некоторый ресурс bi, имеется в избыточном количестве (не используется полностью при реа­лизации оптимального плана), то i-e ограничение становится несущественным и оценка такого ресурса равна 0.

 

Если при использовании оптимального плана двойствен­ной задачи j-e ограничение выполняется как строгое не­равенство, то оптимальное значение соответствую­щей переменной прямой задачи должно быть равно нулю, т. е. если a1,ju1* +...аm,j иm – сj > 0, то хj* =0.

 

Учитывая экономическое содержание двойственных оценок u1*,...,um, выражение а1,ju1* +…am,jum*  может быть интерпретиро­вано как удельные затраты на j-й технологический процесс. Сле­довательно, если эти затраты превышают прибыль от реализа­ции единицы j-го продукта, то производство j-го продукта является нерентабельным и не должно присутствовать в опти­мальном производственном плане (xj* =0).

Несмотря на возможные аналогии, которые могут возник­нуть у читателей, знакомых с такими фундаментальными поня­тиями экономической теории, как предельные издержки и пре­дельный доход, двойственные оценки не следует однозначно отождествлять с ценами (хотя такие попытки иногда предпринимались на начальной стадии становления исследования опе­раций как науки). Еще раз подчеркнем, что переменные двой­ственной задачи по своему смыслу являются оценками по­тенциальной возможности получения дополнительной прибыли за счет увеличения соответствующего ресурса в условиях оптимального функционирования управляемого экономического объекта.

1.6.5. Анализ параметрической устойчивости реше­ний ЗЛП. В предыдущем пункте мы затронули некоторые ас­пекты чувствительности и устойчивости оптимального плана по отношению к изменению вектора ограничений b. Очевидно, что аналогичные вопросы могут быть поставлены для случая вариации коэффициентов целевой функции сj, jÎ1:n.

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

Также содержание проблемы устойчивости оптимального плана ЗЛП по отношению к вариациям целевой функции может быть проиллюстрировано с помощью первой геометрической интерпретации. На рис. 1.10 изображено множество допусти­мых планов D некоторой задачи ЛП. Как видно из рисунка, це­левая функция f (ее поведение отражает линия уровня, пока­занная жирным пунктиром) достигает экстремального значе­ния в точке х*, а изменению ее коэффициентов от с к с' или с" на рисунке соответствует поворот линии уровня относительно х*. Активным, т. е. обращающимся в равенство, ограничениям в точке х* соответствуют линии (1) и (2). До тех пор, пока при повороте, вызванном изменением вектора с, линия уровня целе­вой функции не выходит за пределы образуемого линиями огра­ничений конуса, х* остается оптимальным планом. Как показа­но на рис. 1.10, этот план не меняется при переходе от с к с', и, наоборот, при переходе от с к с" линия уровня целевой функции f(x)=c"x пересечет линию (2), что вызовет изменение опти­мального базисного плана, которым теперь станет точка

Используя условия оптимальности плана ЗЛП

 

 

нетрудно получить количественные оценки для пределов коле­баний коэффициентов целевой функции, при которых не проис­ходит изменение оптимального плана. Допустим, вариации под­вергся некоторый элемент сr : сr′ = сr + εr. Возможны два случая:

1. Столбец r не входит в оптимальный базис (r Î N(β(q))). Тог­да для неизменности оптимального плана необходимо и доста­точно выполнение условия

 

 

Отсюда можно получить значение для допустимой вариации

 

 

2. Столбец r входит в оптимальный базис (r Î N(β(q))). В этом случае для сохранения оптимальности текущего плана потре­буется выполнение для всех небазисных столбцов (j Ï N(β(q))) условий

 

 

Следовательно, в этом случае допустимая вариация должна удовлетворять условиям

 

 

Приведенный пример исследования чувствительности оп­тимального плана по отношению к изменению параметров за­дачи является весьма простым. Очевидно, что существуют и более сложные задачи, в которых, например, исследуются совместные вариации параметров разных типов. Они состав­ляют предмет специального раздела исследования операций, получившего название параметрического программирова­ния. Заинтересованный читатель может получить дополни­тельную информацию по данному предмету в [1, 6].

 

1.7. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

 

1.7.1. Основные идеи двойственного симплекс-метода. Непосредственное приложение теории двойственности к вы­числительным алгоритмам линейного программирования позво­лило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода по­следовательного уточнения оценок. Впервые он был предло­жен Лемке в 1954 г.

В процессе изложения идей, положенных в основу двойст­венного симплекс-метода, еще раз воспользуемся второй геометрической интерпретацией ЗЛП. Рассмотрим некоторую КЗЛП (1.48). На рис. 1.11 изображен конус К положительных линейных комбинаций расширенных векторов условий аj для случая m = 2, n = 6, а на рис. 1.12 — (для большей наглядно­сти) — поперечное сечение данного конуса некоторой плос­костью L, проходящей параллельно оси аппликат.

С каждым планом и задачи, двойственной по отношению к (1.48), можно взаимно однозначно связать гиперплоскость, проходящую через начало координат и перпендикулярную век­тору (-1,и). Допустимые планы двойственной задачи (1.49) должны удовлетворять условиям иА ≥ с, которые можно пере­писать в виде (1, и)А ≥ 0 . Последнее означает, что всякий рас­ширенный вектор условий аj лежит «ниже» плоскости, опреде­ляемой вектором (-1, и). Таким образом, любому допустимому плану двойственной задачи в рассматриваемом примере соот­ветствует некоторая плоскость, расположенная выше всех рас­ширенных векторов, а стало быть, и конуса К. На рис. 1.12, где изображено поперечное сечение, конусу К отвечает многогран­ник, а «гиперплоскостям двойственных планов» — пунктирные линии, являющиеся их следами.

 

 

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

Из геометрической иллюстрации видно, что плоскости, не соприкасающиеся с конусом К, заведомо не представляют инте­реса, так как для любой из них легко указать плоскость, у кото­рой искомая точка пересечения лежит ниже. Таким образом, процесс поиска экстремума сводится к последовательному пе­ребору плоскостей, касающихся «верхних» граней конуса, или, как еще говорят, опорных по отношению к конусу. Для слу­чая, изображенного на рис. 1.12, таковыми являются гиперплоскости π1,2, π2,3, π3,4 и π4,5. Как можно заметить, каждая из рассматриваемых гиперплоскостей натянута на некоторый ба­зисный набор расширенных векторов аj, что, собственно, и ис­пользовано для их обозначения (π1,2 ~  {а1, а2} и т. д.).

 

В дальнейшем систему β={aj1, aj2,...,ajm} из т линейно-не­зависимых столбцов матрицы условий прямой задачи А будем называть сопряженным базисом, или двойствен­но допустимым базисом, если всякий вектор и Î Rm, удовлетворяющий условиям, удовлетворяет также ус­ловиям иаj≥cj(jÎ1:n), т. е. является допустимым пла­ном двойственной задачи (1.49).

 

План двойственной задачи и, соответствующий сопряженно­му базису β={aj1, aj2,...,ajm}, называют опорным планом. Его «опорность» заключается в том, что в системе ограничений uаj ≥ cj  (jÎ1:n), задающих область определения двойственной задачи D*, т неравенств с номерами jÎ N(β) обращаются в ра­венства.

Следует обратить внимание на то, что не всем сопряжен­ным базисам соответствуют допустимые базисные планы пря­мой задачи. В частности, вектор b не может быть разложен с неотрицательными коэффициентами по базисам {а1, а2}, {а3 , а4 } или {а4, а5}. В связи с этим систему коэффициентов разложения вектора b по сопряженному базису называют псев­допланом. В то же время базис {а2, а3} является допустимым для прямой задачи, и, более того, из иллюстрации видно, что он, с одной стороны, определяет максимум прямой задачи (наивыс­шую точку пересечения прямой, проходящей через конец b, с конусом К), а с другой — минимум двойственной (низшую точ­ку пересечения этой прямой с лежащей над К опорной гипер­плоскостью):

 

 

Последний факт является не чем иным, как геометрической иллюстрацией утверждения теоремы 1.5.

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

* В данном пункте используется та же система обозначений, что и в п. 1.4.1.

 

F Критерий оптимальности псевдоплана х в двойствен­ном симплекс-методе заключается в том,

     что х одновре­менно должен являться допустимым планом прямой задачи, т. е. все его

     компоненты должны быть не­отрицательны (хj ≥ 0).

Обратно, если хотя бы одна из компонент псевдоплана яв­ляется отрицательной, то процесс улучшения значения целе­вой функции может быть продолжен. Геометрическая иллюст­рация данной ситуации приведена на рис. 1.13. Здесь на плоскости (для m = 2) изображена система столбцов ограниче­ний КЗЛП, из которых {а1, а2} образуют текущий базис. Как видно из рисунка, вектор ограничений имеет отрицательную ко­ординату по направлению, задаваемому вектором а1. В то же время очевидны и те базисы (например, {а2, а3}), в которых b будет иметь все положительные координаты. Однако это не все­гда так. Пример на рис. 1.14 иллюстрирует случай отсутствия допустимых планов у прямой задачи: вектор b имеет отрицатель­ную компоненту в текущем базисе {а1, а2} по направлению а2, а для всех остальных небазисных столбцов (а3, а4) данная коор­дината является положительной, т. е. b и столбцы, являющиеся кандидатами на ввод в очередной базис, лежат в разных полу­плоскостях, образуемых прямой, проходящей через вектор а1,

 

 

и при любых базисах, отличных от текущего, соответствующая координата вектора b все равно останется отрицательной.

F Таким образом, в двойственном симплекс-методе признаком отсутствия допустимых планов у

     решаемой КЗЛП является неотрицательность каких-либо r-х компонент во всех столбцах аj, 

      представленных в текущем базисе β (ar,j(β) ≥ 0, j Î1:n) если br(β) < 0 l.*

* Здесь следует подчеркнуть, что двойственный симплекс-метод не­посредственно нацелен на нахождение решения прямой задачи.

 

С другой стороны, если br(β)<0 и в строке аr(β) существуют отрицательные координаты, то псевдоплан можно улучшить выводя из базиса столбец, находящийся на r-м месте, и вводя в него некоторый вектор al, имеющий отрицательную r-ую координату. При наличии в векторе b(β) нескольких отрицательных компонент номер вектора, выводимого из базиса, обычно опре­деляется строкой, содержащей наименьшую (наибольшую по модулю и отрицательную) компоненту.

Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы очередной базис опре­делял опорную плоскость, ниже которой располагаются все не­базисные векторы. Для этого требуется, чтобы оценки всех не­базисных векторов а0,j(β) ( j Î N(β)), вычисляемые по формулам

 

а0,j(β) = -cj + c(β)аj(β)

 

 (см. (1.26)), оставались положительными. Это, в свою очередь, означает, что номер вводимого столбца l должен быть опреде­лен таким образом. Чтобы

 

 

После выбора выводимого и вводимого векторов производит­ся обычный пересчет симплекс-таблицы по формулам, анало­гичным формулам (1.28)-(1.31), и процесс итеративно повто­ряется. В результате через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты множе­ства допустимых планов.

 

1.7.2. Алгоритм и табличная реализация двойственно­го симплекс-метода. Обобщая сказанное в предыдущем пун­кте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП.

0-этап. Нахождение исходного сопряженного (двой­ственно допустимого базиса). Результатом 0-этапа являют­ся сопряженный базис β(1) и соответствующие ему псевдоплан x(β(1)), матрица A(β(1)) и вектор b(β(1)), которые будут исполь­зованы на первой итерации. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.

I-этап. Стандартная итерация алгоритма — выполня­ется для очередного сопряженного базиса β(q).

1°. Проверка оптимальности текущего псевдоплана: осу­ществляется просмотр значений bi(β(q)), iÎ1:m. Возможны два варианта:

1΄. Для всех iÎ1:m, bi(β(q)) ≥ 0. Тогда текущий псевдоплан x(β(q)) одновременно является допустимым планом решаемой задачи, т. е. ее оптимальным планом. Вычислительный про­цесс закончен. Элементы оптимального плана х* определяют­ся по формуле

 

 

а достигаемое на нем значение целевой функции равно

 

 

1". Существует по меньшей мере один номер строки rÎ1:m, для которого br(β(q))<0 . Следовательно, псевдоплан x(β(q))  — неоптимален. Выбирается строка с номером r, такая, что

 

 

Она становится ведущей и определяет номер столбца Nr(β(q)), который должен быть выведен из базиса. Переходим к пункту 2° алгоритма.                              

2°. Определение столбца, вводимого в базис. Рассматрива­ется ведущая строка аr(β(q)). Возможны два варианта:       

2'. Для всех jÎ1: n аr,j(β(q)) ≥ 0. Делается вывод об отсут­ствии допустимых планов у решаемой задачи (D = Ø) и за­вершается вычислительный процесс*.

* Очевидно, что для определения пустоты множества допустимых планов достаточно найти полностью неотрицательную строку аi(β(q)), соответствующую bi(β(q)) < 0.

 

2". В строке аr(β(q)) существует по крайней мере один эле­мент аr,j(β(q))<0. Согласно правилу (1.62) определяются l — номер столбца, вводимого в очередной базис. Переходим к пун­кту 3° алгоритма.

3°. Пересчет элементов матрицы А и столбца b относи­тельно нового базиса. В соответствии с формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи A и век­тора ограничений b относительно нового базиса β(q+1), который получается в результате вывода из базиса β(q) столбца аr и вво­да в него столбца аl. Полагаем номер текущей итерации q: = q+1 и переходим к первому пункту алгоритма.

По аналогии со стандартным симплекс-методом вычислитель­ную процедуру двойственного симплекс-метода удобно офор­млять в виде таблиц, приведенных на рис. 1.5. Очевидно, что с формальной стороны их структура остается неизменной. Иног­да считается целесообразным добавить к двойственной симп­лекс-таблице строку, содержащую строку со значениями λj, которые вычисляются на этапе определения столбца, вводимо­го в базис.

1.7.3. Особенности применения двойственного симп­лекс-метода. Алгоритм двойственного симплекс-метода (как и остальные симплекс-алгоритмы) предполагает знание исход­ного сопряженного базиса. Очевидно, что в общем случае его нахождение является достаточно непростой задачей, сводящей на нет потенциальные преимущества двойственного алгоритма. Однако в ряде случаев исходный псевдоплан может быть опре­делен достаточно легко.

Рассмотрим задачу минимизации:

 

 

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

 

 

где

 

Приведем задачу (1.66)-(1.68) к канонической форме, введя фиктивные переменные хn+1, хn+2, ... , хn+m:

 

 

Задача, двойственная к (1.70)—(1.72), будет иметь вид:

 

 

 

Из (1.74)-(1.75) очевиден допустимый план двойственной задачи

 

 

и исходный сопряженный базис, образуемый векторами аn+1, аn+2, …., аn+m. При этом начальный псевдоплан равен

 

Таким образом, при решении задачи вида (1.66)-(1.68) двой­ственный симплекс-метод имеет несомненные преимущества по сравнению с прямым.

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

 

 изменение компонент вектора ограничений b, что, допу­стим, может быть интерпретировано как  корректиров­ка объемов доступных ресурсов в процессе управления экономическим объектом;

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

 

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

В заключение отметим, что в настоящем параграфе был рас­смотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что су­ществует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных мат­риц), но, поскольку этот вопрос представляет интерес в основ­ном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознако­миться в [1]. Отметим лишь, что она обладает теми же прин­ципиальными преимуществами, что и модифицированный симп­лекс-метод.

1.7.4. Пример решения ЗЛП двойственным симплекс-методом. Рассмотрим на конкретном, примере процесс реше­ния КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений b в результате которых

 


Содержание исходной симплекс-таблицы T(1) (за исключением столбца b(β(1))) будет идентично содержанию таблицы, полу­чающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для вычисления значений b(β(1)) в данном случае мож­но воспользоваться обратной матрицей, полученной на послед­ней итерации в п. 1.5.2:

 

В результате имеем:

 

 

Как видно из таблицы Т(1), в столбце b(β(1)) содержатся отрицательные элементы b1(β(1)) = - 1/3<0), то есть базис β(1) ={5, 1, 3} не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b(β(1)) является единствен­ным, поэтому номер столбца, выводимого из базиса, опреде­ляется однозначно — r = 1 и N1(β(1))=5. Далее рассматриваем строку a1(β(1)) = (0, -1/6, 0, -1/6, 1). В ней имеются отри­цательные элементы. Вычисляем λ2 =42:(-(-1/6))=252, λ4 =38:(-(-1/6))=228. λ2> λ4, следовательно, номер столбца, вводимого в базис — l = 4. Осуществляем преобразование и получаем симплекс-таблицу T(2).

 

 

Поскольку b(β(2)) >0, то достигнутый базис N(β(2)) = {4,1,3} является оптимальным. Из Т(2) можно выписать оптимальный план х* = (6, 0, 32/3, 2, 0) и соответствующее ему значение це­левой функции f(x*)= 444.

 

КЛЮЧЕВЫЕ ПОНЯТИЯ

 

Общая задача линейного программирования (ОЗЛП).

Каноническая задача линейного программирования (КЗЛП).

Допустимый план.

Оптимальный план.

Первая геометрическая интерпретация ЗЛП.

Базисное решение ЗЛП.

Вторая геометрическая интерпретация ЗЛП.

Вырожденный и невырожденный план ЗЛП.

Симплекс-метод — метод последовательного улучшения плана.

Критерий оптимальности допустимого базисного плана.

Метод минимизации невязок.

Модифицированный симплекс-метод — вычислительная схема, связанная с преобразованием обратных матриц.

Двойственная задача линейного программирования.

Симметричность отношения двойственности.

Теоремы двойственности.

Экономическая интерпретация двойственных оценок.

Параметрическая устойчивость решения ЗЛП.

Двойственный симплекс-метод — метод последовательно­го уточнения оценок.

Сопряженный (двойственно допустимый) базис.

Опорный план и псевдоплан.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

 

1.1. Сформулируйте задачу линейного программирования.

1.2. Дайте определение для следующих понятий: план, допус­тимый план, оптимальный план,

  решение задачи.

1.3. Чем отличается общая задача линейного программирова­ния от канонической?

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

1.5. Дайте определения для следующих понятий: аффинное множество, гиперплоскость, базис.

1.6. Чем отличается выпуклый многогранник от многогранно­го выпуклого множества?

1.7. В чем отличие понятий «линейная оболочка» и «выпуклая оболочка»?

1.8. Любой ли конус является выпуклым множеством?

1.9. Какая точка выпуклого множества называется угловой?

1.10. В чем заключается первая геометрическая интерпрета­ция задачи линейного программирования?

1.11. В чем заключается вторая геометрическая интерпрета­ция задачи линейного программирования?

         В чем ее отли­чие от первой?

1.12. Какой план называется базисным?

1.13. Как связаны базисные планы и угловые точки области оп­ределения задачи линейного

         программирования?

1.14. Какой план задачи линейного программирования называ­ется вырожденным?

1.15. Как с точки зрения второй геометрической интерпрета­ции можно представить процесс поиска

        оптимального плана в задаче линейного программирования?

1.16. Сформулируйте критерий оптимальности допустимого базисного плана, применяемый в          

         симплекс-методе.

1.17. Сформулируйте основные этапы стандартной итерации симплекс-метода.

1.18. Для чего применяется преобразование Жордана—Гаусса?

1.19. Какой элемент симплекс-таблицы называется ведущим?

1.20. При каких условиях делается вывод о неограниченности целевой функции в решаемой задаче?

         Какая геометриче­ская интерпретация соответствует данному случаю?

1.21. Можно ли заранее точно определить количество итера­ций, которое потребуется для решения

         задачи симплекс-методом? Можно ли найти верхнюю границу для данной величины?

1.22. Какая задача называется вырожденной? По каким призна­кам можно узнать, что текущий план

         является вырожден­ным?

1.23. Какие проблемы возникают при решении вырожденных задач?

1.24. Какую экономическую интерпретацию имеет ситуация вырожденности?

1.25. В чем основная идея метода возмущений?

1.26. Для чего предназначен метод минимизации невязок?

1.27. Сформулируйте основные отличия модифицированного симплекс-метода по отношению к

         стандартному.

1.28. Перечислите преимущества модифицированного симп­лекс-метода.

1.29. Будет ли отличаться количество итераций при решении одной и той же задачи при решении ее

         стандартным и мо­дифицированным симплекс-методом?

1.30. Дайте определение двойственной задачи.

1.31. Какими основными свойствами обладает пара двойствен­ных задач?

1.32. В чем заключается экономическая интерпретация пере­менных двойственной задачи?

1.33. Какой смысл  вкладывается в понятие «параметрическая устойчивость»?

1.34. Сформулируйте условия для допустимых изменений це­левой функции задачи, при которых ее

         оптимальный план остается неизменным.

1.35. Перечислите основные идеи, на которых базируется алго­ритм двойственного симплекс-метода.

1.36. Дайте определение сопряженного базиса.

1.37. Что такое псевдоплан?

1.38. Сформулируйте критерий оптимальности, используемый в алгоритме двойственного симплекс-

         метода.

1.39. По каким признакам можно определить, что множество допустимых планов задачи, решаемой

         двойственным сим­плекс-методом, пусто?

В каких ситуациях могут быть реализованы преимуще­ства двойственного симплекс-метода?