Конспект лекций по курсу «Математическое программирование»

Опишем общую  идею симплекс-метода.

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

При решении ЗЛП симплекс-методом можно выделить следующие этапы:

1) приведение  ЗЛП к каноническому виду;

2) приведение  системы линейных уравнений к  жордановой форме с неотрицательными  правыми частями с одновременной  проверкой на неразрешимость  ЗЛП из-за противоречивости системы линейных ограничений;

3) исследование  опорного плана на оптимальность;

4) исследование  ЗЛП на неразрешимость из-за  неограниченности снизу на ОДР  целевой функции;

5) переход к  новому, "лучшему" опорному  плану.

 

3.2. Табличный вид ЗЛП. Симплекс - таблицы.

 

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

Пусть ЗЛП записана в каноническом виде (2.3-2.5). Для приведения ЗЛП к табличному виду систему (2.4) следует сначала привести к жордановой форме с неотрицательными правыми частями. Предположим, что эта жорданова форма имеет вид (2.6). Выразим из (2.6) базисные переменные через свободные:

 

                                               (3.1)      

 

Подставив в целевую функцию (2.3) вместо базисных переменных их выражения  через свободные переменные по формулам (3.1), исключим тем самым из целевой  функции базисные переменные. Целевая функция примет вид:

 

                                                       (3.2)

 

В табличном виде целевая  функция записывается так:

                                                     (3.3)

где      .

Отметим следующие  особенности табличного вида ЗЛП:

а) система линейных уравнений приведена к жордановой форме с неотрицательными правыми  частями;

б)  из целевой  функции исключены базисные переменные и она записана в форме (3.3).

Перейдем теперь к описанию симплекс-таблицы. Пусть ЗЛП записана в табличном  виде:       

                                    (3.4)

 

Тогда заполненная  симплекс-таблица выглядит так.

Таблица 3.1.

Базис	Переменные								Свободные члены
			...	xk			...
	1	0	...	0			...
	0	1	...	0			...
. . .	.  .	. .	...	. .	.  .	.  .	...	.  .	.  .  .
	0	0	...	1			...
f	0	0	...	0			....

                                                                                                                                                   Опорный план ЗПЛ: ..., называется  опорным  планом,  соответствующим этой  симплекс-таблице.  Как видно из формулы (3.2), значение целевой функции при этом опорном плане равно γ₀.

Рассмотрим пример. Привести к табличному виду следующую ЗЛП и заполнить  симплекс-таблицу:

 

Вначале ЗЛП следует привести к каноническому виду. Для этого функцию f нужно заменить на - f:

 

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

Табличный вид  ЗЛП таков:

 

Заполним симплекс-таблицу (для сокращения записей первый столбец  озаглавлен "Б", последний столбец - "Q").

Таблица 3.2.

Б					Q
	4	1	-5	0	8
	-7	0	-2	1	4
-f	-4	0	8	0	-20

 

Опорный план, соответствующий  этой симплекс-таблице, имеет вид:

. Значение функции - f при этом опорном плане равно - 20.

3.3. Условие  оптимальности опорного плана.

 

Пусть имеется  заполненная симплекс-таблица. Сформулируем условие оптимальности опорного плана.

Если в нижней строке симплекс-таблицы все числа, кроме, быть может, самого правого, неположительны, то опорный план, соответствующий этой таблице, оптимален.   

Для простоты обоснуем справедливость этого утверждения на примере. Пусть  заполненная симплекс-таблица имеет вид:

Таблица 3.3.

Б						Q
	1	0	2	-1	3	2
	0	1	2	0	-1	3
f	0	0	-5	-3	-1	6

Значение целевой  функции при опорном плане, соответствующем  симплекс-таблице, равно 6. Выпишем целевую  функцию в табличном виде: , откуда . Так как при любом допустимом решении ЗЛП переменные принимают только неотрицательные значения, то из последней записи целевой функции видно, что ее значение в любой точке ОДР не меньше 6. Следовательно, минимальное значение целевой функции на ОДР равно 6 и оно достигается при опорном плане, соответствующем симплекс-таблице,  .

 

3.4. Условие неразрешимости  ЗЛП из-за неограниченности снизу  на ОДР целевой функции.

 

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

Условие неразрешимости формулируется  так.

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

Для обоснования  снова воспользуемся примером.

Таблица 3.4.

Б						Q
	1	0	2	5	-2	2
	0	1	-3	0	-1	3
f	0	0	3	-1	2	4

 

Столбец в нижней строке содержит положительное число, а в остальных строках - неположительные числа. Докажем неразрешимость ЗЛП.

Выпишем жорданову  форму, соответствующую симплекс-таблице, и перенесем члены, содержащие , в правую часть. Получим

Пусть а - произвольное положительное число. Очевидно, ЗЛП имеет следующее допустимое решение: .  Вычислим значение целевой функции при этом допустимом решении. Из таблицы 3.4 имеем:

. При указанном допустимом  решении f = 4 - 2а. Отсюда видим, что значение целевой функции может стать как угодно малым при достаточно большом  значении  а. Иначе говоря, целевая функция не ограничена снизу на ОДР. Следовательно, ЗЛП неразрешима.

 

3.5. Переход к новому  опорному плану.

 

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

1)  новый базис  должен быть по-прежнему допустимым, т.е. правые части соответствующей  жордановой формы должны быть  по-прежнему неотрицательными;

2) при новом опорном плане  значение целевой функции не  должно превышать ее значения  при прежнем опорном плане.

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

Правило выбора генерального элемента.

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

Проиллюстрируем это правило на примере.

Таблица 3.5.

Б						Q
	1	0	0	2	-1	4
	0	1	0	3	4	8
	0	0	1	-2	6	3
F	0	0	0	7	5	12

 

В качестве генерального столбца можно выбрать либо столбец  , либо столбец . Выберем (чаще всего выбирают тот столбец, у которого внизу большее положительное число). Теперь приступим к выбору генеральной строки. Для этого рассмотрим две строки - и .  Составляем отношения 4:2 и 8:3. Меньшее значение имеет отношение 4:2, поэтому первую строку выбираем в качестве генеральной. Следовательно, генеральный элемент равен 2 - он стоит на пересечении столбца и строки .