Глава 8 решение общей задачи линейного программирования § 8.1. симплекс-метод

Глава 8 решение общей задачи линейного программирования § 8.1. симплекс-метод

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

С самого начала укажем, что симплекс-метод в его непосредственной форме предназначен для решения канонической задачи линейного программирования.

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

a,,*, +al2x2 +...+alnxH = blt . а2х + а22х2 ++ <,2iAi = *2. (8.1)

атх+ат2х2+-+атПхП = Ьт

т линейных уравнений с и неизвестными и линейная функция

f=clxl+c2x2 + ...+cnxn + c. (8.2)

Среди неотрицательных решений системы (8.1) нужно найти такое, которое минимизирует функцию (8.2).

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

Пример допустимой системы:

*( = -2;с4 + 7*5 + 5, • хг = 3*4 + 6*5 + 4, (8.3) *2 = -ЛГ4 + 2*5,

здесь свободные члены равны соответственно 5, 4 и 0. Можно ли привести систему уравнений к допустимому виду и как это сделат^ рассмотрим в § 8.2.

Неизвестные в допустимом виде системы, которые выражены через остальные, называются базисными, а весь набор этих неизвестных, который мы обозначим для краткости одной буквой Б,— допустимым базисом неизвестных. Остальные неизвестные называются небазисными или свободными. Например, в системе (8.3) допустимый базис образован неизвестными *(, *2, х3; неизвестные же *4 и *5 —

свободные.

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

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

Например, если

/= 5х| 7*2 + х3 jc4 *5 + 2,

а система ограничений приведена к виду (8.2), то новое выражение

Для / будет

/= 5(-2*4 + 7х5 + 5) 7(3*4 + 6д:5 + 4) + (-*4 + 2*5)*4 х5 + 2 = = 33*4 6*5 1.

Чтобы упростить дальнейшие записи, будем считать, что имеется всего пять неизвестных х,, х2, х3, х4, х5 и система ограничений приведена к допустимому виду с базисом { Х|, х2, х3 } :

Х = а4х4 + а5х5 + а , • х2 = Р4х4+Р5х5 + р, (а>0,р>0,у>0), (8-4)

. *3 = ?4*4 + У 5*5 + У ■

а целевая функция — к виду

/=54х4 + 65х5 + 5. (8.5)

Напомним, что решается задача о минимизации/при ограничениях (8.4) и условиях х, > 0, х2 > 0, х3 >0, х4 > 0, х5 > 0. Положим все свободные неизвестные равными нулю:

х4 = 0, х5 = 0,

и найдем из системы (8.4) значение базисных неизвестных:

х, =а,х2=р,х3 = у.

Полученное таким путем решение системы (8.4) :

(а, Р, у, 0,0) (8.6)

будет неотрицательным. Оно называется базисным решением, отвечающим базису {х,, х2, х3}. Для базисного решения значение функции / равно /Б = Ь.

Возможны три случая.

I. Все коэффициенты при свободных неизвестных в выражении для

f неотрицательны: б4 > 0,55 > 0.

Тогда для любого неотрицательного решения системы (8.4) имеем 54х4 > 0, 65х5 > 0, значит, / = 54х4 + 55х5 + 8 > S. Таким образом, min/ = 5, т. е. базисное решение является оптимальным — задача решена.

II. Имеется свободное неизвестное, коэффициент при котором в

выраженииf отрицателен, а все коэффициенты при этом неизвестном

в уравнениях (8.4) — неотрицательны.

Пусть, например, 54 < 0, а а4 > 0, р4 > 0, у4 > 0. Тогда, отправляясь от базисного решения (8.6), будем наращивать значение х4 (не меняя х5 = 0). Значения базисных неизвестных также будут меняться; мы получим:

Х| =а4х4 + а > а > 0, х2 = р4х4 + р>р>0, Х3 = у4Х4 + у>у>0,

т. е. решение (Х|, х2, х3, х4, 0, 0) будет оставаться неотрицательным. При этом /=54х4 + 5, и ввиду 54<0 значение/с ростом х4

будет неограниченно уменьшаться. Таким образом, в этом случае min/= оо, т. е. задача решения не имеет.

III. Имеется свободное неизвестное, коэффициент при котором вf отрицателен, но и среди коэффициентов при этом неизвестном в уравнениях (8.4) также есть отрицательные.

В этом случае производится шаг, а именно, от базиса Б мы переходим к новому базису Б', с таким расчетом, чтобы значение fs уменьшилось или по крайней мере не увеличилось: /&^/БРазумеется, изменение базиса влечет за собой соответствующую перестройку системы(8.4)ограничений и выражения (8.5) для функции/.

Опишем конкретно содержание шага. Пусть, например, а4 и р4 отрицательны, а у4— положительно или равно 0:

а4<0, р4<0, у4>0. (8.7) Если снова, как в случае II, наращивать значение х4, то будем иметь:

х,=а4х4 + а, х2 = Р4х4+Р, *3 = У<Л'4 + УВвиду а4<0 и Р4<0 значения Х[ и х2 будут уменьшаться, а значение х3 будет оставаться неотрицательным (так как по-прежнему х3>у). При наращивании Х4 наступит момент, когда одно из неизвестных

а

л'і или х2 обратится в нуль: для х, таким моментом будет х4 = 0 „а0 а для х2 будет х4 = ~. Выберем из этих отношении ^и —

Р4 Р4

а _

наименьшее. Пусть, например, это будет = р. Тогда наращивание х4 возможно только от 0 до р. При х4 = р неизвестное х | обратится в нуль, а при дальнейшем росте х4 неизвестное х, станет уже отрицательным, что допускать нельзя. Полагая в системе (8.4) х4 = р и х5 = 0, получим неотрицательное решение

х, = 0, х2 = р4р + р, x3 = y4p+r, *4 = Р> *5 = °. <8-8)

для которого значение функции / будет Р4 р +Р <Р (поскольку р4 < 0 и р > 0).

Таким образом, с ростом х4 первым из базисных неизвестных обращается в нуль неизвестное х,. Это служит для нас сигналом к замене базиса Б = {х,,х2,х3} на £"= {х4,х2,х3}, а именно: из старого базиса удаляется неизвестное х, и вместо него в базис вводится неизвестное х4 (из числа прежних свободных).

Смена базиса, как уже говорилось, влечет за собой перестройку системы (8.4). Из первого уравнения (для xt) выражаем:

1 а5 а (о пч

*4= 04*1-05*5-04" ( }

и подставляем это выражение для х4 в остальные два уравнения. В итоге получаем систему вида

х4 = а,х] + а5х5 + а, ■ x2 = blxi+bsx5 + b, (8.10)

Х3 = С|Х] + С5Х5 + с,

с базисным решением

х,=0, x2 = fc, х3 = с, х4 = а, х5 = 0, (8.11)

которое должно совпадать с решением (8.8), поскольку, как видно из самой системы (8.9) , двух разных решений с х, = 0,х5 = 0 быть не может. Таким образом, базисное решение (8.10) является снова неотрицательным.

Что же касается нового значения функции /, то оно равно

/£, = Р4р+Р (8.12)

и, таким образом, /Б. </Б (следует учесть, что Р4 < 0 и поэтому j34 р + Р <Р). Итак, с переходом от базиса Б к Б' система ограничений сохранила допустимую форму (8.10), где а > 0, Ь > 0, с > 0, а значение функции /для базисного решения уменьшилось или осталось прежним.

Переход от базиса Б к новому базису Б' и означает шаг, который (напомним) делается в случае III. Разумеется, старое выражение для/, т. е. (8.5), должно быть теперь заменено новым:

/=d4x4 + d5x5 + d, (8. ІЗ)

которое получается из (8.5) заменой неизвестного х4 по формуле (8.9).

Если для полученной задачи (8.10), (8.13) снова имеет место случай III, то делаем следующий шаг, т. е. переходим к новому базису Б", для которого/Б„ < /Б..

И так до тех пор, пока не придем к одному из случаев I или II. Тогда процесс заканчивается.

Пример 1. Решим задачу/=х4 х5 -> min при условиях X, = 1 -х4+ 2х5,

х2 = 2 + 2х4-х5, (8.14) х3 = 3 — Зх4 x^, х,>0 0=1,2,3,4,5).

Здесь неизвестные Xj, х2, х3 образуют базис (допустимый), а функция /выражена через свободные неизвестные х4 и х5.

Среди коэффициентов при свободных неизвестных в выражении/ имеется отрицательное число — это коэффициент при х5. Просматривая коэффициенты при х5 в уравнениях (8.14), мы видим, что и среди них имеются отрицательные. Следовательно, перед нами случай III, и в соответствии с изложенной выше методикой необходимо сделать шаг. Выбрав уравнения с отрицательными коэффициентами при х5,— а это второе и третье уравнения,— составляем

1 •) —3700

161

2 3 Т И Г

2

из которых меньшим является отношение у, отвечающее уравнению для *2.

Производим замену базиса по схеме х2 х5. Это означает, что вместо х2 в базис вводится *5. Новый базис теперь состоит из *1> *5> *3Чтобы осуществить соответствующую перестройку системы (8.14), нужно выразить эти неизвестные через х2 и *4.

Начинаем с уравнения для х2, из которого выражаем х5 (новое базисное неизвестное):

х5 = 2 + 2*4 *2;

затем выражаем *|, *3 и/:

*, = 1 х4 + 2 (2 + 2х4 х2), *3 = 3 3*4 -(2 + 2*4 *2 ). / = *4 (2 + 2*4 х2).

Итак, задача приведена к виду :

*, = 5 + 3*42*2, ■ *5 = 2 + 2*4-*2, (8Л5) *3 = 1 5*4 + *2,

(мы сохранили порядок уравнений в (8.14)) и

/=-2-*4 + *2. (8.16)

Для полученной задачи снова имеем случай III, так как коэффициент при *4 в выражении/отрицателен и среди коэффициентов при *4 в уравнениях (8.15) также имеются отрицательные. Последним является коэффициент при *4 только в одном уравнении — для *3, поэтому производим замену базиса по схеме *3 *4.

Выкладки предоставляем читателю провести самостоятельно.

28

12

о

Для полученной задачи имеет место случай I, так как оба коэффициента при свободных неизвестных в выражении/неотрицательны. Это означает, что последнее базисное решение:

5 > *5 5 > *4

1

: 5' *2~*3:

Итак,

5 ■

является оптимальным, а искомый минимум / равен оптимальное решение есть

28 001 12 5 ' ' ' 5' 5

11

и min/= - Задача решена.

min при условиях

(8.19)

В разобранном примере 1 процесс закончился случаем I, т. е. нахождением оптимального решения. Однако имеется еще одна возможность окончания процесса — когда наступает случай II, тогда min/= оо. Разберем пример.

Пример!. Решим задачу/= *( *2

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

*(>0 (/=1,2,3,4).

Здесь имеем случай III, так как коэффициент при хх в выражении Для/отрицателен и среди коэффициентов при *| в уравнениях тоже

| х3 = 3 х4 + х2, j х, = 2-х4 + 1хъ

f=-2 + x4Зх2.

Для этой задачи имеем случай II, так как при неизвестном х2 коэффициент в выражении/отрицателен, а в каждом из уравнений — коэффициент неотрицателен. Следовательно, min/= со, и оптимального решения не существует.