Частные случаи симплекс-метода

Рассмотрим пример. Требуется минимизировать функцию

F=4x₁+x₂

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

3x₁+x₂=3,

4x₁+3x₂≥6,

x₁+2x₂≤4,

x₁, x₂ ≥0

Запишем задачу в стандартной форме

3x₁+ x₂ =3,

4x₁+3x₂-x₃ =6,

x₁+2x₂ +x₄=4,

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

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

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

3x₁+x₂ + R₁ =3,

4x₁+3x₂-x₃ + R₂ =6,

x₁+2x₂ +x₄=4,

За использование этих переменных в составе целевой функции нужно ввести штраф, приписывая им большой коэффициент М.

Тогда функция цели примет вид:

Min F=4x₁+x₂+MR₁+MR₂.

Начальное допустимое решение при этом будет

R₁=3, R₂=6 и x4=4.

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

Для построения симплекс-таблицы выразим искусственные пере­менные через небазисные:

R₁=3-3x₁-x₂

R₂=6-4x₁-3x₂+x₃

F=4x₁+x₂+M (3-3x₁-x₂) +M (6-4x₁-3x₂+x₃) = (4-7M) x1+ (1-4M) x₂+Mx₃+9M

Тогда первая симплекс-таблица будет иметь вид

Базисные переменные	x1	x2	x3			x4	Решение
F	-4+7M	-1+4M	-M				9M
R1
R2			-1
x4

Далее решение ведется обычным образом. Оптимальному решению соответствует точка x₁=2/5, x₂=9/5, где F=17/5.

Отметим, что при максимизации F штраф М необходимо брать c обратным знаком.

Рассмотрим другой пример.

Max F=3x₁+9x₂

при условии

x₁+4x₂≤8,

x₁+2x₂≤4,

x₁, x₂ ≥0

Введя остаточные переменные x₃ и x₄, построим симплекс-таблицу

	x1	x2	x3	x4
F	-3	-9
x3
x4

x₃- выводится, x₂ вводится

На следующем шаге

	x1	x2	x3	x4
F	-3/4		9/4
x1	¼		¼
x4	½		-1/2

x₄- выводится, x₁ - вводится

Получим

	x1	x2	x3	x4
F			3/2	3/2
x2			½	-1/2
x1			-1

Заметим, что после двух итераций значение функции цели не умень­шилось (18). Т.е. налицо зацикливание. Что же это означает? Рас­смотрим рис.2.3. Через точку оптимума проходят три прямые, а за­дача содержит только две переменные. Отсюда следует вывод, что одно из ограничений лишнее.

Max F=2x₁+4x₂

при условии

x₁+2x₂≤5,

x₁ + x₂≤4,

x₁, x₂ ≥0

Рис. 2.5

Рис. 2.4

Рис. 2.4 иллюстрирует суть дела. Целевая функция параллельна одной из прямой ограничений. Это означает, что задача имеет бес­конечное множество решений.

Может быть, случай, когда решение отсутствует вообще.

Пример: Max F=3x₁+2x₂

при условии 2x₁+ x₂≤2,

x₁+4x₂≥12,

x₁, x₂ ≥0.

Рис.2.5 хорошо иллюстрирует суть дела.