Имя материала: Математика в экономике

Автор: Солодовников А.С.

§ 8.4. м-метод

 

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

Решим задачу линейного программирования с системой ограничений, имеющей для определенности размеры 3x5 (три уравнения с пятью неизвестными).

Наряду с задачей (8.24) - (8.26), которую будем считать исходной, рассмотрим другую задачу линейного программирования при ограничениях

(8.28)

а,*, + а2х2 + аз*з + 04*4 + а5х5 + а = У\< + Ъ2х2 + Ьгхг + b4x4 + b5x5 + Ь = у2, с,дс, + с2х2 + С3Х3 + сАхА + с5х5 + с = уг,

и условиях

(8.29)

jc,>0 0 = 1,-.,5), yjZO 0=1,2,3) минимизировать функцию

/= d + dxxx + dp2 + ^3 + d4x4 + dix5 + M(yi+y2 + Уі), (8.30)

где M — некоторое число.

Сформулированная задача называется М-задачей. Неизвестными в ней являются хх,...,х5;ух,у2,у3. При этом неизвестные ух уг уъ называются искусственными.

Выражение для F будем записывать в виде

F=fix) + М S(y),

где х = (хх, ...,х5) — вектор переменных хі,...,х5;у = (у,У2>Уі> ~~ вектор искусственных переменных, aS(y)=yi +У2 + Уу

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

(8.27)   является {у,У2,у$}-

При решении Л/-задачи могут представиться две возможности:

Л/-задача имеет решение, т. е. min F существует;

М-задача не имеет решения, min F= - <ю.

Следующая теорема устанавливает связь между решениями исходной задачи и соответствующей Л/-задачи.

Теорема 1. Предположим, что набор

*° = (*?           х°), у° = (уіуІуЬ

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

Доказательство. Пусть у = у = y = Q. Тогда, очевидно, значения х,х удовлетворяют (8.24) и (8.25). Предположим, что х' = х{,х5' — какое-нибудь другое решение системы (8.24), (8.25).

Мы должны доказать, что/ (Зс0) </(3?).

Дополнив значения х,',.... jc5" числами >у = 0, у{ = 0, у^' = О, получим, что набор (х{,х^,у{,у2 ,уг') удовлетворяет системе

(8.28)   , (8.29). Ввиду оптимальности набора (Зс °, у 0) мы должны иметь:

F(xQ,y°)<F(x',/). Учитывая, что S(у° ) = 0 и S(у' ) = 0, находим

f(x° )*/(?), (8-31) а это означает, что х 0 есть оптимальное решение исходной задачи.

Замечание . Так как F(х°,у 0) =J{х0 ), то неравенство (8.31) означает, что min/= min F.

Теорема 2. Если набор х° = (х°,х°), у 0 = (yQuy,y ) является оптимальным решением М-задачи для всех достаточно больтих значений М, и при этом хотя бы одно из чисел у, у, отлично от нуля, то система (8.24), (8.25) несовместна (т. е. исходная задача не имеет допустимого решения).

Доказательство проведем от противного. Предположим

вопреки утверждению теоремы, что система (8.24), (8.25) имеет реше-

ние Зс' = (х{,х5'). Дополнив снова значения         х5' числами

^' = 0, У2=0, Уз,' = ®' получим решение (х',у') системы (8.28), (8.29). Ввиду оптимальности набора ( х °, у 0 ) имеем

F(x0,y0)<F(xy)mnf(x0) + MS(y°)<f(x') + MSG'). Но S (у') = 0, поэтому

f(x°) + M S(y°)<f(x'). (8-32)

Число S(y0) = y]+y2) + y<l строго положительно, так как по условию числа у,у,у неотрицательны и хотя бы одно из них отлично от нуля. Но тогда неравенство (8.32) при больших М попросту невозможно. Мы пришли к противоречию.

Замечание .На практике число М выбирается столь большим, чтобы все встречающиеся по ходу выкладок выражения вида a + ЬМ с положительными Ъ были положительны.

Из теорем 1 и 2 можно извлечь следствия.

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

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

Добавим к этому еще одно предложение, которое примем без доказательства.

3. Если М-задача не имеет оптимального решения (что означает min F= - со), то исходная задача неразрешима (либо min/= - со, либо нет ни одного допустимого решения).

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

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

Пример 1. Решим задачу линейного программирования

/= -2х, + *2 - *3 ->■ min

при условии (х,, х2, Xj)£ 0 и ограничениях

2*, + х2 + *3 = 4,

'   *1 -2лг3<5, 2x|+2x2 >3.

Приведем сначала задачу к канонической форме, введя две балансовые переменные х4 > 0 и *5 > 0. Получим задачу:

/=-2*| + *2-x3-» min (8.33)

при условии (*|, *2, *3, *4, *5)> 0 и ограничениях

2*, + *2 +   *3 =4,

• *,        - 2*3 + *4      = 5,      (8 34)

2*,+2*2 -*5=3.

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

Для первого и третьего уравнений приходится ввести искусственные переменные х6 и *7. Получаем М-задачу:

F=f + М (ух+ у2) = _2*( + xl ~ хг + м *б + М *7 -> min при условии (*,, х2, *3, *4, *5, *6, х7)> 0 и ограничениях

2*,+*2+ *3      +*б =4>

• *,       -2*3 + *4 =5,

2*, +2*2          -*5     +*7 = 3,

где*! *2 —«естественные»переменные,*4 *5—«балансовые»переменные, *6 *7 — искусственные переменные.

Заполняем симплекс-таблицу 1. При нахождении последней строки (для F) используем способ, изложенный в § 8.3. В последней строке имеются (при достаточно большом М) сразу три положительных числа 2 + 4Л/, -1 + ЪМ и 1 + М. Выбираем первое из них. Разрешающий элемент находится в столбце *, и строке *7. Производим шаг, в результате которого искусственное неизвестное *7 выходит из базиса, уступая в нем место неизвестному хх. Получаем таблицу 2. В таблице 2 выбираем столбец с *3, поскольку стоящее в нем число 1 + М положительно. Разрешающий элемент находится в столбце *2 и строке *6. Производим шаг, в результате которого *6 выходит из базиса, уступая в нем место *3. Получаем таблицу 3. В строке для целевой функции уже нет положительных чисел, что свидетельствует о достижении оптимального решения Л/-задачи. При этом искусственные неизвестные в базис не входят. Таблицу 3 — без столбцов *6 и *7 — можно рассматривать как симплекс-таблицу для задачи (8.33), (8.34), причем в ней содержится оптимальное решение этой задачи:

min/=4, *"„„„,=(j;0; i;y;o)-

Поскольку нас интересуют непосредственно лишь значения неизвестных *), *2, *3, то ответ запишется в виде:

min/=4, *,)nm=f|;0; 1 j.

Для удобства будем решать задачу на нахождение минимума, рассматривая вместо/функцию -/:

-/= х{ - х2 - *з + х4 -> min.

Укажем без пояснения последовательность симплекс-таблиц для соответствующей Л/-задачи. Разрешающие элементы выделяются пунктиром. В таблице I строка F для разнообразия вычислена способом, указанным в § 8.3, в следующей таблице — методом Гаусса.

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

-*1 - 6х2 + х3-дс4= 5, 3*| - 2*2 + Xj - х4 = 1,

*,>0 (і=1,....4), /= -*] + х2 + дс3 - х4 -> max.

 

м

У

4

-4

-4

0

0

I

- 1

-1

*3

1

3

-2

1

- 1

0

1

 

F

4М-1

-4М-4

-4М+3

0

0

0

 

 

При большом М среди чисел последней строки — кроме свободного члена — нет положительных. Значит, достигнуто оптимальное решение А/-задачи:

Х] =о,х2 = 0,*з= 1,*4 = 0,^, = 4,^2 = 0.

Поскольку значение ух = 4 ф 0, то по теореме 2 исходная задача не имеет ни одного допустимого решения.

12* 179 § 8.5. Теорема о конечности симплекс-алгоритма

 

Во всех рассмотренных нами примерах на симплекс-метод дело обстояло очень благополучно в том смысле, что процесс после конечного числа шагов заканчивался либо нахождением оптимального решения, либо установлением того факта, что min/= - да. Всегда ли будет так? Поскольку процесс останавливается при наступлении одного из случаев I или II из § 8.1, то поставленный вопрос равнозначен следующему: не может ли случиться, что, производя (по симплекс-методу) шаг за шагом вычисления, мы никогда не окажемся перед одним из случаев I или И? По этому поводу можно высказать следующие соображения.

Каждый шаг состоит в замене одного базиса Б другим Б', причем эта замена происходит таким образом, что значение целевой функции /(для базисного решения) не увеличивается.

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

Б, Б', Б",..., (8.35)

для которых

fs*foZfB.Z.... (8.36)

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

&кБ<к+]...,Б<к+т

в которых начальное и конечное звенья совпадают. Такие цепочки называются циклами. Ясно, что тогда и

/ (*) _ f (к+т) JB    ~J Б

откуда следует в силу (8.36), что

 

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

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

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

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

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

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

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

Условимся считать вектор

А = (а{,а2, -іаг) положительным и записывать это как

А >0,

если А * 0 и первая из отличных от нуля координат вектора А положительна. Если даны два вектора:

А = (аиа2, ...,аг)нВ = (Ь{,Ь2, ...,br), то мы скажем, что вектор Л больше, чем вектор Я (или что вектор В меньше, чем вектор А), если разность А - В есть положительный вектор. Другими словами, А > В означает, что

а{ >ЬХ,

или же

о, = й(, но а2>Ь2,

или же

а) = b, O-i = Ь2, но й3 > й3 и т. д.

Очевидно, для любых двух векторов А и В выполняется одно и только одно из соотношений

А > В, А < В, А = В. Далее, если А > В и В > С, то А > С.

Обратимся теперь непосредственно к доказательству теоремы.

Пусть дана задача линейного программирования, причем система ограничений с самого начала разрешена относительно некоторого базиса, скажем х]гх2,хг Итак, дана система

 

. х2 = b2 - (fl2,r+l        + - + а2п хп)> (8-3?)

[xr = b, -(arr+lxr+l + ...+ агпхп) и линейная функция

/=80-(6н.,дсм.| + ... + 8#гхя).

Как обычно, требуется среди неотрицательных решений системы найти такое, которое минимизирует функцию/

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

 

Базисные неизвестные

х

 

 

Хг+

 

Хп

Свободные члены

 

 

 

 

*|

I

 

0

«l.r+l

 

ап

ь,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

I

°1,г+1

 

 

 

 

с,2

 

сг,

f

0

 

0

 

 

к

с1

с2

 

 

(приписанная часть здесь заключена в пунктирную рамку). Числа с()- и с- (;',_/'= 1, 2,г) могут выбираться как угодно, но с одним условием: матрица ( Су) должна быть невырожденной.

Условимся называть базис положительным, если все векторы Ci = (bt,cil,ci2,...,cir) (i= 1,2,...,г)

 

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

независимо оттого, какие числа стоят в приписанной части таблицы. Однако если какое-либо из чисел равно нулю, то условие положительности базиса накладывает некоторое ограничение на числа cl2,.., cir: первое отличие от нуля среди них должно быть положительным. Таким образом, свойство базиса быть положительным может зависеть не только от самой системы ограничений (8.37), но и от приписанных чисел ctj.

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

Очередной шаг симплекс-метода начинается с выбора разрешающего элемента. Напомним, как производится этот выбор. Мы находим среди чисел 8Л+1,...,8Л последней строки положительное

число 8;, после чего просматриваем все числаaXj, a2j,аг- столбца х-. Для каждого положительного а,.,- составляем отношение — и

 

затем среди этих отношений выбираем наименьшее, допустим —

аИ

Тогда элемент а и будет разрешающим. Если минимум отношения —

ак

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

—Ск. для всех положительных ак: и берется наименьший из них.

akj

Допустим, что наименьшим является —С,-, Тогда в качестве разрешу

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

среди векторов —С.,—С не может быть равных — в противном aj arj

случае две строки матрицы (с^) оказались бы пропорциональными, что противоречит невырожденности этой матрицы. Введем в рассмотрение еще один вектор

С = (80, сх,...,сг).

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

новый базис снова будет положительным;

новый вектор С" меньше, чем старый вектор С:

С <С.

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

Вспомним, как происходит преобразование симплекс-таблицы. Выбрав разрешающий элемент а,у, мы умножаем і-ю строку таблицы

на —. Таким образом, aij

С = —С

 

и так как atj > О, С, > 0, то С\■> 0. Из любой другой строки вычитается подходящее кратное /'-й 1 строки, подобранное с таким расчетом, чтобы элемент, стоящий в >м столбце, обратился в нуль. В результате получим;

 

С',. = С,.-^С,- (* = ,...,r,k*i).

к      к    а.. г

 

Если при этом akj < 0, то   —1СІ > 0 и С, > 0. Если же akj > 0, то

(        1 Л

V\%     aij lj

Но в силу условия на выбор разрешающего элемента вектор, записанный в скобках, положителен: следовательно, С'к > 0. Это показывает, что новый базис является положительным. Наконец, заметим, что

С = С - -^С:.

atj

Так как в данном случае 8; > 0, то мы получаем С < С, что

и требовалось доказать.

Чтобы завершить доказательство теорем ы, нам остается ответить только на один вопрос: как обеспечить положительность исходного

базиса? Но это совсем просто: достаточно, например, приписать к исходной симплекс-таблице справа следующие числа:

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 |