Контрольные вопросы

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

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

3. Используя таблицу 10, содержащую оптимальное решение задачи, определите исключаемую переменную и соответствующее изменение величины z, если в качестве новой базисной переменной будет выбрана:

3.1) переменная s₃,

3.2) переменная s₄.

4. Какой вывод следует из результатов вопроса в)?

5. На рисунке 2 показано пространство допустимых решений трёхмерной задачи ЛП с вершинами A, B, … , J.

5.1) Являются ли следующие пары вершин смежными: (A, B), (B, D), (E, H), (A, I)?

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

• ABGH.

• AEIH.

• ACEBADH.

x₃

D G

J H

F B

A I x₁

C E

Рисунок 2

6. Пусть в задаче ЛП, которой соответствует пространство допустимых решений, показанное на рис.2, все ограничения являются неравенствами типа “≤”, а все исходные переменные задачи (т.е. x₁, x₂ и x₃) неотрицательны. Обозначим через s₁, s₂, s₃ и s₄ дополнительные (неотрицательные) переменные, ассоциируемые с ограничениями, представленными плоскостями CEIJF, BEIHG, DFJHG и IJH соответственно. Определите базисные и небазисные переменные для каждой вершины пространства допустимых решений.

7. Пусть в задаче ЛП, для которой пространство допустимых решений представлено на рис. 2, реализация симплекс-метода начинается в точке A. Определите вводимую переменную на первой итерации симплекс-метода, а также её значение и значение целевой функции, если целевая функция имеет следующий вид:

1. Максимизировать z = x₁ – 2x₂ + 3x₃.

2. Максимизировать z = 5x₁ + 2x₂ + 4x₃.

3. Максимизировать z = -2x₁ + 7x₂ + 2x₃.

4. Максимизировать z = x₁ + x₂ + x₃.

11. Искусственное начальное решение

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

Пример 11.1

Запишем в канонической форме:

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

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

Идея использования искусственных переменных достаточно проста. Она предполагает вклю­чение неотрицательных переменных в левую часть каждого из уравнений, не содержащих “очевидных” начальных базисных переменных (т.е. тех переменных, которые входят только в одно уравнение с положительным коэффициентом, а в симплекс-таблице им соответствуют единичные столбцы [0 0 1 0 … 0]^T).

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

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

1) М-метод (или метод больших штрафов);

2) двухэтапный метод.

11.1. М - метод

Вернемся к введенной в примере 11.1 линейной модели.

В первом и во втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из уравнений по одной искусственной переменной, обозначив их через R₁ и R₂:

За использование этих переменных в составе целевой функции можно ввести штраф, при­пи­сывая им достаточно большой положительный коэффициент М. Такой способ введения искусст­венных переменных R₁ и R₂ приводит к следующей линейной модели:

Логика использования искусственных переменных: имеем m=3 уравнения, n=6 неизвестных. Сле­до­вательно, базисное решение должно включать n-m= =6-3=3 нулевые переменные. Если положить рав­ны­ми нулю переменные x₁, x₂ и x₃, то сразу же будет получено требуемое начальное допусти­мое решение: R₁=3, R₂=6, x₄=4.

Рассмотрим теперь, каким образом “новая” структура модели автоматически приводит к тому, что на конечной стадии процесса оптимизации переменные и принимают нулевое значение. Так как мы имеем дело с задачей на отыскание минимума, а переменным R₁ и R₂ в целевой функции приписан большой по величине коэффициент М, то метод оптимизации, направленный на нахождение минимального значения z, приведет к тому, что переменные R₁ и R₂ в оптимальном решении обратятся в ноль. Заметим:

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

Если целевая функция подлежит максимизации: приписываем искусственным переменным в целевой функции достаточно большой по абсолютной величине отрицательный коэффициент –М (М>0), что обусловит недопустимость положительных значений искусственных в оптимальном решении.

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

В результате

При этом z-уравнение в симплекс-таблице будет иметь вид:

,

.

Таким образом, стартовой точке, в которой x₁=x₂=x₃=0, соответствует значение z=9M, как и должно быть при R₁=3, R₂=6.

Построим симплекс-таблицу (таблица 11).

Так как целевая функция минимизируется, переменные, включаемые в базис, должны иметь наибольшие положительные коэффициенты в z-уравнении. Оптимум достигается на той итерации, где все небазисные переменные имеют неположительные коэффициенты в z-уравнении (М – положительный коэффициент, значение которого принимается очень большим).

Итерация 0 (начало вычислений).

Таблица 11

БП	x1	x2	x3	R1	R2	x4	Решение
z	- 4+7M	-1+4M	-M	0	0	0	9M
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
x4	1	2	0	0	0	1	4

Согласно условию оптимальности переменная x₁ вводится в базис. Согласно условию допустимости переменная R₁ выводится из базиса. Получаем таблицу 12.

Итерация 1.

Таблица 12

БП	x1	x2	x3	R1	R2	x4	Решение
z	0	(1+5M)/3	-M	(4-7M)/3	0	0	4+2M
x1	1	1/3	0	1/3	0	0	1
R2	0	5/3	-1	-4/3	1	0	2
x4	0	5/3	0	-1/3	0	1	3

Согласно условию оптимальности переменная x₂ вводится в базис. Согласно условию допустимости переменная R₂ выводится из базиса. Получаем таблицу 13.

Итерация 2.

Таблица 13

БП	x1	x2	x3	R1	R2	x4	Решение
z	0	0	1/5	8/5-M	-1/5-M	0	18/5
x1	1	0	1/5	3/5	-1/5	0	3/5
x2	0	1	-3/5	-4/5	3/5	0	6/5
x4	0	0	1	1	-1	1	1

Согласно условию оптимальности переменная x₃ вводится в базис. Согласно условию допустимости переменная x₄ выводится из базиса. Получаем таблицу 14.

Итерация 3.

Таблица 14

БП	x1	x2	x3	R1	R2	x4	Решение
z	0	0	0	7/5-M	-M	-1/5	17/5
x1	1	0	0	2/5	0	-1/5	2/5
x2	0	1	0	-1/5	0	3/5	9/5
x3	0	0	1	1	-1	1	1

Согласно условию оптимальности данное решение является оптимальным.