Решить задачу линейного программирования методом искусственного базиса

1.2 Метод Big M
Метод Big-M-это альтернативный метод решения задачи линейного программирования с использованием искусственных переменных. Чтобы решить L. P. P симплексным методом. Мы должны начать с начального базового допустимого решения и построить начальную симплексную таблицу. В предыдущих задачах мы видим. Что переменные слабины легко обеспечивали начальное базовое осуществимое решение. Однако в некоторых задачах переменные слабины не могут обеспечить начальное базовое осуществимое решение. В этих задачах по крайней мере одно из ограничений имеет тип = или≥. “Большой М-метод используется для решения таких Л. П. П.

1.3 АЛГОРИТМ

Большой М-метод

Большой М-метод или метод штрафов состоит из следующих основных шагов :

Шаг 1:

Выразите задачу линейного программирования в стандартной форме. Введя слабые и/или избыточные переменные. Если таковые имеются.

Шаг 2:

Эти переменные называются искусственными переменнымиs. Цель введения искусственных переменных состоит только в том. Чтобы получить исходное базовое осуществимое решение. Однако добавление этих искусственных переменных приводит к нарушению соответствующих ограничений. Поэтому мы хотели бы избавиться от этих переменных и не позволяли бы им появляться в оптимальной симплексной таблице.

Чтобы добиться этого. Мы назначаем очень большой штраф ‘ — М. — к этим искусственным переменным в целевой функции. Для максимизации целевой функции.

Шаг 3:

Решите модифицированную задачу линейного программирования симплексным методом.

На любой итерации обычного симплексного метода может возникнуть любой из следующих трех случаев :

а) В базисе yb нет вектора. Соответствующего некоторой искусственной переменной.

В таком случае мы переходим к шагу 4.

(b) Существует по крайней мере один вектор. Соответствующий некоторой искусственной переменной , в базисе

yB, на нулевом уровне. То есть соответствующая запись в XB равна нулю. Кроме того, коэффициент M в каждой чистой оценке ZjCj(j = 1, 2, …. n) неотрицателен.

В таком случае текущее базовое допустимое решение является вырожденным. Это тот случай. Когда оптимальное решение данного Л. П. П. включает искусственную базовую переменную и оптимальное базовое осуществимое решение все еще существует.

(в) По крайней мере один искусственный вектор находится в базисеYb , но не на нулевом уровне. То есть соответствующая запись вXb отлична от нуля. Кроме того, коэффициент M в каждой чистой оценке Zj — Cj неотрицателен,

В этом случае данный Л. П. П. не обладает никаким выполнимым решением.

Шаг 4:

Применение симплексного метода продолжается до тех пор. Пока либо не будет получено оптимальное базовое осуществимое решение. Либо не появится указание на существование неограниченного решения для данного ЛПР.

При применении симплексного метода всякий раз, когда вектор. Соответствующий некоторой искусственной переменной. Покидает базис. Мы отбрасываем этот вектор и опускаем все записи. Соответствующие его столбцу. Из симплексной таблицы.

Пример:

Максимизация z = x1 + 5x2

Подлежит

3x1 + 4x2 ≤ 6
x1 + 3x2 ≤ 2

x1, x2 ≥ 0

Решение:

Преобразование неравенств в равенства

Вводя избыточные переменные. Слабые переменные и искусственные переменные. Стандартная форма LPP становится

Максимизировать x1 + 5x2 + 0x3 + 0x4 – MA1

Подлежит

3x1 + 4x2 + x3 = 6
x1 + 3x2 – x4 + A1 = 2

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, A1≥ 0

где,

x3-слабая переменная
x4-избыточная переменная
A1-искусственная переменная.

Исходное базовое осуществимое решение

                     x1 = x2 = x4 = 0, A1 = 2, x3 = 6

Итерация 1:

 

cj

1

5

0   

0   

–М

 

cB

Основные переменные B

x1

x2

x3

x4

А1

Значения решения
b (= XB)

0

x3

3

4

1

0

0

6

–М

А1

1

3

0

–1

1

2

zj–cj

 

–М–1

–3М–5

0

М

0

 

 

Вычисление значений для индексной строки (z

j – cj)

з1 – с,1 = 0 × 3 + (–м) × 1 – 1 = –м – 1
З2 – с2 = 0 × 4 + (–м) × 3 – 5 = –3 М – 5
З3 – с3 = 0 × 1 + (–м) × 0 – 0 = 0
З4 – с,4 = 0 × 0 + (–м) × (-1) – 0 = м
з5 – гр5 = 0 × 0 + (–М) × 1 – (–м) = 0

Поскольку M –большое положительное число. Коэффициент M в строке zj-cj будет определять входящую базовую переменную.
Поскольку -3M
Ключевой столбец = x2 столбца.
Минимум (6/4, 2/3) = 2/3
Ключевая строка = A1
Поворотный элемент строки = 3.


A1 уходит, а x2 входит.

Примечание: Только что завершенная итерация. Искусственная переменная A1 была исключена из базы. Новое решение показано в следующей таблице.

Итерация 2:

 

cj

1

5

0

0

 

cB

Основные переменные
B

x1

x2

x3

x4

Значения решения
b (= XB)

0

x3

5/3

0

1

4/3

10/3

5

x2

1/3

1

0

–1/3

2/3

zj–cj

 

2/3

0

0

–5/3

 

 

Итерация 3:

 

cj

1

5

0

0

 

cB

Основные переменные
B

x1

x2

x3

x4

Значения решения
b (= XB)

0

x4

5/4

0

3/4

1

5/2

5

x2

3/4

1

1/4

0

3/2

zj–cj

 

11/4

0

5/4

0

 

 

Результат:

Оптимальное решение-x1 = 0, x2 = 3/2
Max z = 0 + 5 x 3/2 =15/2