M-задача

Метод искусственного базиса применяется для решения канонической ЗЛП в случае, когда задача не имеет начального решения с базисом из единичных векторов (ортонормированным базисом).
В этом случае в уравнения, не содержащие базисной переменной, добавляют со знаком «+» неотрицательные переменные, называемые искусственными.
В отличие от дополнительных переменных, искусственные переменные влияют на целевую функцию Z(X), они входят в нее с коэффициентами М, причем в задачу на максимум с коэффициентом –М, в задачу на минимум с коэффициентом . Величина М предполагается достаточно большим положительным числом (M>>1), значение которого не задается. Поэтому такая задача носит название М-задачи.
В случае решения задачи на максимум расширенная задача имеет вид:

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

xj≥ 0.
Векторы An+1,An+2,…,An+m называются искусственными векторами. Данная задача имеет начальное опорное решение с базисом Б = (An+1,An+2,…,An+m) (в этом случае исходный базис целиком состоит из искусственных векторов).

Справедлива следующая теорема.

  1. Если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи;
  2. если в оптимальном решении М-задачи хотя бы одна искусственная переменная отлична от 0, то исходная задача не имеет решения (из-за несовместимости системы ограничений);
  3. если М-задача не имеет решения из-за неограниченности целевой функции, то и исходная задача решения не имеет.

Особенности алгоритма метода искусственного базиса

  1. Виду того, что начальное опорное решение расширенной ЗЛП содержит искусственные переменные, входящие в целевую функцию с коэффициентами -М (max) или +М (min), оценка разложений векторов условий Δj= CбXj -cj состоит из двух слагаемых Δj= Δ’j +Δ’’j( M). Т.к. М – велико, то на первом этапе расчета для нахождения векторов, вводимых в базис, используется только слагаемое Δ’’j( M).
  2. Векторы, соответствующие искусственным переменным, которые выводятся из базиса опорного решения, исключаются из рассмотрения.
  3. После того как все векторы, соответствующие искусственным переменным, исключены из базиса, расчет продолжается обычным симплексным методом с использованием оценок Δ’j, не зависящих от М.
  4. Переход от решения расширенной ЗЛП к решению исходной ЗЛП осуществляется с помощью указанных ранее замечаний.

Пример. Найти решение следующей задачи.
Z(X)=x1+x2+4x3→max
xj≥0 (j=1,2,3)
Приведем задачу к каноническому виду:

xj ≥ 0 (j=1,2,3,4,5,6)

Z(X)=x1+x2+4x3+0x4+0x5+0x6-Mx7→max

В первых двух уравнениях содержатся базисные переменные x4 и x5 (это дополнительные переменные), а в третьем базисная переменная отсутствует, поэтому введем искусственную переменную x7, которая и будет являться базисной. Решаем М-задачу.
Составим симплексную таблицу:


Базис
Cб В 1 1 4 0 0 0 -M
A1 A2 A3 A4 A5 A6 A7
A4

A5
← A7

0

0

-M

20

24

6

1

2

1

4

1

1

1

3

0

1

0

0

0

1

0

0

0

-1

0

0

1


Z0= 0-6М

-1

-1М↑

-1

-1

-4

0

0

0

0

0

0

1

0

0

A4
←A5

A1

0

0

1

14

12

6

0

0

1

3

-1

1

1

3

0

1

0

0

0

1

0

1

2

1

Z1=6 0 0 -4↑ 0 0 -1

←A4

A3

A1

0

4

1

10

4

6

0

0

1

10/3

1/3

1

0

1

0

1

0

0

-1/3

1/3

0

1/3

2/3

-1

Z2=22 0 -4/3 0 0 4/3 5/3
A2

A3

A1

1

4

1

3

5

3

0

0

1

1

0

0

0

1

0

2/10 1/10 1/10
Z3=26 0 0 0 4/10 6/5 9/5
Все оценки положительны, поэтому решение X3 = (3,3,5,0,0,0) оптимально.
Отбрасывая дополнительные переменные, получим ответ: Zmax=26 при X*=(3,3,5).
Для более подробного ознакомления с алгоритмом M-метода рекомендуем воспользоваться калькулятором.

Количество переменных
Количество строк (количество ограничений)

загрузка...