Математическое программирование

Математическое программирование для студентов сельхозакадемии

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

МЕТОД ИСКУССТВЕННОГО БАЗИСА, ИЛИ М-МЕТОД

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

При решении таких задач был введен метод искусственного ба­зиса. Он особенно удобен, когда число переменных значительно пре­восходит число уравнений.

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

Пример 1:
Математическое программирование для студентов сельхозакадемииНайти максимум Z = 4Х1 + 2Х2 + Хз
Х1 + Х2 + Х3 ? 8
2Х1 + Х2 + Х3 ? 8
3Х1 + 2Х2 + Х3 = 15
Хj ? 0, j = 1,…,3.

Математическое программирование для студентов сельхозакадемииПереходим к канонической форме:
Х1 + Х2 + Х3 – Х4 = 8
2Х1 + Х2 + Х3 + Х5 = 8
3Х1 + 2Х2 + Х3 = 15
Хj ? 0, j = 1,…,5
Zmax = 4Х1 + 2Х2 + Х3 + 0*Х4 + 0*Х5.

Данная система ограничений не имеет единичного базиса, так как дополнительная переменная Х4 имеет коэффициент минус единица, а третье ограничение было представлено уравнением, и в нем отсутст­вует базисная переменная. Для того чтобы был единичный базис, вводим в соответствующие ограничения искусственные переменные У1 и У2 с положительными коэффициентами (+1).

Следует отметить, что искусственные переменные вводятся толь­ко для математической формализации задачи. Поэтому схема вычис­лений должна быть такой, чтобы искусственные переменные не мог­ли попасть в окончательное решение в числе базисных переменных. С этой целью для искусственных переменных в целевой функции вводят коэффициент М, обозначающий очень большое число. На практике (особенно при решении задачи на ЭВМ) вместо М берут конкретное большое число, например 10 000. Причем при решении задачи на максимум этот коэффициент вводится в целевую функцию со знаком минус, а при решении на минимум — со знаком плюс. Те­перь будем решать Т (М)-задачу, целевая функция которой содержит целевую функцию Z-задачи и искусственные переменные с коэффи­циентом  ±М, то есть
m
Т = Z — М ? Уi    при решении на максимум целевой функции и
i =1
m
Т = Z + М ? Уi    при решении на минимум целевой функции.
i=1

В нашем случае:
Математическое программирование для студентов сельхозакадемииХ1 + Х2 + Х3 – Х4 + У1  = 8
2Х1 + Х2 + Х3 + Х5 = 8
3Х1 + 2Х2 + Х3 + У2 = 15
Хj ? 0, j = 1,…,5
Тmax = 4Х1 + 2Х2 + Х3 + 0*Х4 + 0*Х5 – М(У1 + У2).

Эта задача решается в симплексных таблицах, но для удобства целевую функцию разбивают на 2 строки:

  • в первую строку записываем оценки, которые не содержат ко­эффициент М;
  • во вторую строку — оценки по каждой свободной переменной, содержащие коэффициент М.

Расчет элементов (оценок) этих двух строк производится по фор­муле (1). Только отличие:

  • при расчете оценок Z-строки должны быть учтены коэффици­енты Сj, входящие вфункцию Z;
  • при расчете оценок М-строки этот коэффициент во внимание не берется, а М — выносится, как общий множитель.

Для того чтобы Т-задача и Z-задача были равны, нужно, чтобы значения Уi были равны нулю. Поэтому, пока Уi не равно нулю, раз­решающий столбец выбирается по оценкам во второй строке, исполь­зуя алгоритм симплексного метода.

Лишь после того, как все Уi станут равны нулю, дальнейший рас­чет будет вестись по первой индексной строке, то есть — обычная Z-задача.

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

1.Если в оптимальном решении М-задачи все искусственные пе­ременные (Уi) равны нулю, то это решение будет являться оптималь­ным решением Z-задачи

2. Если в оптимальном решении М-задачи хотя бы одна из искус­ственных переменных отлична от нуля, то Z-задача не имеет решения по причине несовместности системы ограничений.

3. Если М-задача оказалась неразрешимой (Т>+? или-?), то ис­ходная задача также неразрешима либо по причине несовместности системы ограничений, либо по причине неограниченности функции Z.

Составим первую симплексную таблицу. При решении М-методом разрешающий столбец можно выбирать в М-строке не по наиболь­шей, по абсолютной величине отрицательной оценке (при решении на максимум) и не по наибольшей положительной оценке (при решении на минимум), а по той из них, которая быстрее выводит У из базиса. В данном примере разрешающим столбцом будет столбец свободной переменной Х2 с оценкой (-3).

Таблица 3.1
Первая симплексная таблица

Математическое программирование для студентов сельхозакадемииМатематическое программирование для студентов сельхозакадемииСв.П
Б.П.

Сj
Ci

0

4

2

1

0

ai0/aip

ai0

X1

X2

X3

X4

У1

8

1

1

1

-1

8

X5

0

8

2

1

1

0

8

У2

15

3

(2)

1

0

7,5 <

Z

0

-4

-2

-1

0

М

-23

-4

-3 ^

-2

1

Заполнение Z-строки осуществляется по формуле:
a00 = 0*8-0=0
a01 = 0*2-4=-4
a02 = 0*1-2=-2
a03 = 0*1-1=-1
a04 = 0*0-0=0.

Заполнение М-строки:
a?00 = -М*8+(-М)*15=-23М
a?01 = -М*1+(-М)*3=-4М
a?02 = -М*1+(-М)*2=-3М
a?03 = -М*1+(-М)*1=-2М
a?04 = -М*(-1)+(-М)*0=1М.
М выносим как общий множитель.

В последнем столбце в разрешающей строке стоит 0, поэтому столбец свободной переменной Х4 переносим без изменений.

Таблица 3.2
Вторая симплексная таблица

Математическое программирование для студентов сельхозакадемииМатематическое программирование для студентов сельхозакадемииСв.П
Б.П.

Сj
Ci

0

4

1

0

ai0/aip

ai0

X1

X3

X4

У1

1/2

-1/2

(1/2)

-1

1(-2) <

X5

0

1/2

1/2

1/2

0

1(0)

Х2

2

15/2

3/2

1/2

0

15(0)

Z

15

-1

0

0

М

-1/2

1/2

-1/2 ^

1

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

Таблица 3.3
Третья симплексная таблица

Математическое программирование для студентов сельхозакадемииМатематическое программирование для студентов сельхозакадемииСв.П
Б.П.

Сj
Ci

0

4

0

ai0/aip

ai0

X1

X4

Х3

1

1

-1

-2

X5

0

0

(1)

1

0 <

Х2

2

7

2

1

3,5

Z

15

-1^

0

Теперь решаем обычным симплексным методом.
Таблица 3.4

Четвертая симплексная таблица

Математическое программирование для студентов сельхозакадемииМатематическое программирование для студентов сельхозакадемииСв.П
Б.П.

Сj
Ci

0

0

0

ai0

X5

X4

Х3

1

1

1

-1

X1

4

0

1

1

Х2

2

7

-2

-1

Z

15

1

1

В оценочной строке все элементы являются неотрицательными величинами, следовательно, получено оптимальное решение:
Zmax = 15     Хопт (0,7,1,0,0).

Пример 2:
Задача решалась на минимум (Z>min) целевой функции. На по­следней итерации получили следующую таблицу:

Таблица 3.5
Последняя симплексная таблица

Математическое программирование для студентов сельхозакадемииМатематическое программирование для студентов сельхозакадемииСв.П
Б.П.

Сj
Ci

0

4

1

0

ai0

X1

X3

X4

У1

М

-1/2

-1/2

-1/2

-1

X5

0

1/2

1/2

1/2

0

Х2

2

15/2

3/2

1/2

0

Z

15

-1

0

0

М

-1/2

-1/2

-1/2

-1

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