Модифицированный симплекс-метод

Таблица 1.11

Таблица 1.8

Элементы	Элементы таблицы
Старой	Новой
Разрешающий	ak,s
Разрешающей строки	ak,j
Разрешающего столбца	ai,s
Все остальные	ai,j

В этой таблице введем следующие индексы:

S - индекс элементов разрешающего столбца,

K - индекс элементов разрешающей строки.

ai,s

ak,s

Поясним вычисления a_i,j¢ с использованием “правила прямоугольника“. Необходимо взять разрешающий элемент a_k,s и мысленно соединить его с тем коэффициентом, новое значение которого требуется найти. Эту прямую следует считать главной диагональю, на ней строится прямоугольник, сторонами которого являются строки и столбцы. В прямоугольнике надо провести побочную диагональ, тогда значение нового коэффициента будет равно его исходному значению, из которого вычитается произведение элементов, стоящих на побочной диагонали, поделенному на разрешающий элемент. Поясним эти действия на схеме (рис. 1.9). Прежде чем заполнить симплекс-таблицу исходные уравнения следует представить в виде (1.21).

	ak,j
			ai,j

Суть преобразований симплекс-метода рассмотрим на примере 1.4. Давайте вспомним ограничивающие неравенства и целевую функцию из этого примера и найдем max целевой функции, пользуясь вышеизложенным методом:

F = 908X₁ + 676X₂ ® max.

X₁ + X₂ 14,

X₂ 10,

10 X₁ + 8 X₂ 120,

7X₁ + 5 X₂ 70,

4X₁ + 2X₂ 28,

.

Преобразуем ее в каноническую форму, вводя дополнительные переменные X_j 0, и превратив неравенства в равенства. Следует обратить внимание, что если в неравенстве стоит знак "", то при свободной переменной пишут " - ", в противном случае - " + ":

X₁ + X₂ = 14 - X₃,

X₂ = 10 - X₄ ,

10 X₁ + 8 X₂ = 120 - X₅ ,

7X₁ + 5 X₂ = 70 - X₆ ,

4X₁ + 2X₂ = 28 - X₇ .

Чтобы приступить к процедуре симплекс-метода, нужно из множества базисных решений полученной системы уравнений сначала найти опорное. С учетом этого в решении задач симплекс-методом различают три этапа:

- нахождение первоначального базисного решения и формирование исходной симплекс-таблицы;

- определение допустимого решения;

- определение оптимального решения.

1-й этап

Первоначальное базисное решение систем находим, полагая свободными переменные X₁ и X ₂.

Тогда X₃ = 14 - X₁ - X₂ ,

X₄ = 10 - X₂ ,

X₅ =120 - 10X₁ - 8X₂ ,

X₆ = 70 - 10X₁ - 5X₂,

X₇ = 28 - 4X₁ - 2X₂ ,

F = 908X₁ + 676X₂ = 0.

Преобразуем эти уравнения к нормальному виду:

X₃ = 14 - (X₁ + X₂ ),

X₄ = 10 - (0X₁ + X₂ ),

X₅ =120 - (10X₁ + 8X₂ ),

X₆ = 70 - (7X₁ + 5X₂ ),

X₇ = 10 - (4X₁ + 2X₂ ),

F = 0 + 908 X₁ + 676 X₂ .

Полученную систему уравнений запишем в виде исходной симплекс-таблицы (табл. 1.9). В табл. 1.9 нет отрицательных свободных членов. Следовательно, нами получено опорное (допустимое) решение, так как допустимым решением является любое неотрицательное решение (при котором > 0), но оно не является оптимальным.

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

Таблица 1.9

Базисные переменные Xб	Свободный член	Свободные переменные
X1	X2
X3
X4
X5
X6
X7
F		- 908	- 676

2-й этап

Напомним, что основная операция симплекс-метода заключается в том, что некоторая базисная переменная замещается на свободную переменную . При этом операция замещения выполняется при соблюдении следующих условий:

- значение целевой функции F в новом опорном (допустимом) решении должно быть больше, чем в предыдущем;

- новое решение системы должно быть также опорным (допустимым).

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

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

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

; ; ; ; .

Для столбца X₂:

; ; ; ; .

Наименьшее отношение 28/4 определяет разрешающую строку и разрешающий столбец, а пересечение разрешающего столбца и разрешающей строки - разрешающий элемент a_ks = 4. В табл. 1.9 разрешающий столбец и разрешающую строку отмечаем стрелками (®). Определив a_ks , строят следующую таблицу, в которой меняют местами переменные, входящие в строку и столбец разрешающего элемента, т.е. переводят базисные переменные в свободные, а свободные - в базисные.

В нашем примере меняем местами переменные Х ₇ и Х ₁ , отмеченные в табл. 1.9 стрелками. Коэффициенты новой табл. 1.10 находят по коэффициентам старой табл. 1.9, используя выражения, приведенные в табл. 1.8 и “правило прямоугольника”. В табл. 1.10 снова не имеем оптимального решения.

Таблица 1.10

Базисные переменные Хб

Свободный член В

Свободные переменные

X7

X2

Х3

- 1/4

1/2

Х4

Х5

-5/2

Х6

-7/4

3/2

Х1

1/4

1/2

F

-222

По вышеописанным правилам в табл. 1.10 находим разрешающий элемент 1 и строим новую табл. 1.11 сделав замещение базиса (Х₄ и Х₂). Особо подчеркнем, что для нахождения разрешающего элемента мы должны выбирать наименьшее положительное значение, т.е. отрицательные отношения свободных членов к коэффициентам разрешающего столбца мы не рассматриваем.

Базисные переменные Хб

Свободный член В

Свободные переменные

X7

X4

Х3

- 1/4

- ½

Х2

Х5

-5/2

- 3

Х6

-7/4

- 3/2

Х1

1/4

- ½

F

3-й этап

Проверим, является ли найденное решение оптимальным, а для нашего примера - максимальным. Для этого сделаем анализ целевой функции F: F = 8576 + 227 X₇ + 222 X₄.

Целевая функция не содержит отрицательных коэффициентов и имеет наибольшее значение в последней таблице, нами получено оптимальное решение:

X₃ = 2; X₂ = 10; X₅ = 20; X₆ = 6; X₁ = 2; X₇ = X₄ = 0;

F_max = 8576.

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

В соответствии с рассмотренной последовательностью, алгоритм симплекс-метода должен иметь следующие блоки:

1. Нахождения первоначального базисного (опорного) решения и формирование исходной таблицы.

2. Отыскание разрешающего элемента a _ks (нахождение отрицательного свободного члена - b _i < 0 и минимального отношения b _i / a_ij ; если в строке отрицательного свободного члена нет отрицательных коэффициентов, то задача неразрешима).

3. Перерасчет новой таблицы по формулам табл. 1.8.

4. Проверка наличия отрицательного свободного члена. Если он есть, то переходим к п. 2. Отсутствие отрицательного свободного члена означает, что получено опорное (допустимое) решение.

5. Аналогично п. 2 - 4 выполняется перерасчет таблицы при поиске оптимального решения.

Решение задачи ЛП симплекс-методом в матричной форме

Требуется минимизировать ,

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

при " x ³ 0.

Введем векторы:

C = (C₁,..., C_n) - вектор оценок,

X = (X₁,..., X_n) - вектор переменных,

b = (B₁,..., B_m) - вектор ограничений

и матрицу

A =

размером (mn) - матрицу коэффициентов ограничений.

Тогда задача ЛП будет иметь следующую трактовку:

минимизировать F=CX

при условиях AX = b, X 0.

Эту задачу можно записать в матричной форме:

Введем обозначение:

А^*= - здесь матрица A ^* размером (m+1)(n+1).

Согласно выше приведенной методике находят разрешающий элемент a_ks.

Следующий шаг симплекс-метода - процедура исключения Гаусса, которая позволяет сделать все коэффициенты в s - м столбце, кроме a_ks , нулевыми, a_ks - равным единице.

Для симплекс-метода в матричной форме итерация симплекс-метода эквивалентна умножению матричного уравнения слева на следующую квадратную матрицу:

(1.23)

, где k 0; s 0.

Если все столбцы матрицы A разделить на базисные B и небазисные N, то задачу ЛП можно записать так:

,

где C_b и C_N - соответствующие компоненты вектора C, X_b, X_N - базисные и небазисные переменные.

Для выбора начальных базисных переменных x_b следует умножить уравнение слева на матрицу:

где R= C_b B^-1 .

В результате получим

,

где I - единичная матрица.

Отсюда следует, что относительные оценки при небазисных переменных

c_j = c_j - C_b B^-1 a_j = c_j - Ra_j.

Базис будет допустимым, если свободные члены при базисных переменных будут неотрицательными, т.е. B^-1b ³ 0.

Если c_j ³ 0 для , то базис является оптимальным решением задачи. Вектор называют вектором текущих цен. Каждая строка умножается на вектор R и вычитается из строки коэффициентов стоимости, для того чтобы исключить коэффициенты стоимости при базисных переменных.

Если задача ЛП задана не в канонической форме, т.е.

минимизировать F=CX

при условиях AX b, X 0,

то, вводя слабые переменные, их можно записать в виде

Метод исключения по строкам для матрицы эквивалентен умножению этой матрицы слева на B^-1, где B - базис подматрицы A, тогда

,

т.е. матрица, получаемая на месте единичной I, будет матрицей, обратной для текущего базиса. Относительные оценки, расположенные над единичной матрицей, будут

,

поскольку - единичные векторы.

Так как F= C_bB^-1b = Rb, текущее значение целевой функции равно произведению вектора текущих цен матрицы A на исходный вектор b.

Пример. F = 5X₁ + 6X₂ + 3X₃ + 4X₄ + 5X₅ ® min

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

2X₁ + 3X₃ + 4X₄ + 2X₅ = 10,

3X₂ + 3X₄ + 6X₅ = 9,

.

Для данного примера матрица A^* будет иметь вид

.

Пусть X₁ и X₂ - базисные переменные.

Матрица B имеет вид

.

Тогда обратная матрица B^-1 имеет следующий вид

.

Напомним, что , где присоединенная матрица, составленная из алгебраических дополнений элементов b_ik определителя матрицы B.

Определитель равен:

= .

Следовательно, матрица B неособенная.

Алгебраические дополнения элементов определителя имеют следующие значения:

b₁₁ = 3, b₁₂ = 0, b₁₂ = 0, b₂₂ = 2; т.е. .

Умножив на , находим обратную матрицу:

.

Вектор текущих цен будет

R = C_bB^-1 = = .

Напомним, что C_b - базисные компоненты вектора C:

C_b = .

Тогда = .

Для выбора начального базиса нужно матрицу A^* умножить слева на матрицу

,

получим

=

.

Разрешающий элемент находится в квадрате.

Итерация симплекс-метода эквивалентна полученной таблице, умноженной слева на следующую матрицу:

.

Эта матрица получена из матрицы (1.23)

Здесь a_ks = 2;

a₁₁ = 1; a₁₂ = - a_0s / a_ks = - 12/2 = - 6;

a₁₃ = 0; a₂₁ = 0; a₂₂ = 1/ a_ks = 1/2; a₂₃ = 0;

a₃₁ = 0; a₃₂ = - a_ms / a_ks = -1/2; a₃₃ = 1.

Тогда имеем

=

(1.24)

Разрешающий элемент помещен в квадрат.

Следующая итерация симплекс-метода равносильна умножению слева на матрицу

.

Тогда

=

.

Следовательно, F min =11; X₄ =7/3; X₅ =1/3; X₁=X₂=X₃ =0.

Модифицированный симплекс-метод ( МСМ ) отличается от обычного симплекс-метода ( СМ ) тем, что в СМ все элементы симплекс-таблиц пересчитываются на каждой итерации и при получении очередной таблицы, все предыдущие таблицы, включая исходную, не сохраняются. В МСМ сохраняется исходная таблица, а на каждой итерации определяются: строка относительных оценок C, вводимых в базис , и текущее значение вектора правых частей ограничений . Для того чтобы определить все элементы таблицы после j- й итерации СМ, достаточно знать матрицу B^-1, соответствующую этой таблице, исходную матрицу и индексы текущих базисных переменных. Тогда текущий вектор R = C_b B^-1 (индексы текущих базисных переменных определяют, какие элементы вектора оценок из исходной таблицы входят в вектор С_b); = B^-1b , где b берется из исходной таблицы, а любой столбец новой таблицы= B^-1 a _j, где a _j - столбец исходной таблицы.

Пусть задана теперь исходная таблица B^-1 , соответствующая таблице i -й итерации. Для того чтобы получить матрицу B^-1 , соответствующую (i+1)- й итерации, надо определить небазисный столбец i -й таблицы , который должен быть введен в базис. Из СМ следует, что может быть введен в базис, если C_j <0. Таким образом, необходимо вычислить С_j для i -ой таблицы, выбрать среди них <0, а затем вычислить

a _S = B^-1 и = B^-1b (= C_j - Ra _j).

Найдя разрешающий элемент и используя элементы векторов и , находим матрицу B^-1 для следующей таблицы.

Пример. Модифицированным симплекс-методом минимизировать

F = 5X₁ + 6X₂ + 3X₃ + 4X₄ + 5X₅ ® min

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

2X₁ + 3X₃ + 4X₄ + 2X₅ = 10,

3X₂ + 3X₄ + 6X₅ = 9,

Выбрав в качестве базисных переменных X₁ и Х₂, получили следующую задачу: F = 43 - 9/2X₃ - 12X₄ - 12X₅

при условиях

X₁ + 3/2X₃ + 2X₄ + X₅ = 5,

X₂ + X₄ + 2X₅ = 3,

.

Эта задача равносильна следующей: максимизировать Х₀= -F при условиях

Х₀ - 9/2Х₃ - 12Х₄ - 12Х₅ = - 43,

Х₁ + 3/2Х₃ + 2Х₄ +Х₅ = 5,

X₂ + Х₄ + 2Х₅ = 3,

.

Исходная таблица имеет вид

	X0	X1	X2	X3	X4	X5	X6
X0				-9/2	-12	-12	-43
X1				3/2
X2

Для исходной матрицы В будет единичной матрицей, т.е. B=I. Поэтому B^-1=I. Вектор текущих цен

R = C_b B^-1;

R == .

Текущие оценки в этом случае будут C_j = Ra_j, поэтому

= = - 9/2;

= = - 12;

= = - 12.

Таким образом, в базис может быть введен вектор , причем:

= B^-1 a ₄ = = .

Текущий вектор правых частей

= B^-1 b = = .

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

min = .

Отсюда видно, что из базиса должен быть исключен вектор . Исключения по строкам с разрешающим элементом = 2 эквивалентно умножению слева на матрицу

= .

После умножения получим

=.

Обращением нового базиса (Х₀, Х₄, Х₂) будет матрица

B^-1 = ;

R = ;

= Ra₁ == 6;

= Ra₃ == 9/2;

= Ra₅ == - 6.

Разрешающим будет 5-й столбец. В базис вводим столбец :

= = ;

= = .

Находим min . Следовательно, из базиса выводим вектор , умножая слева на матрицу

= .

= .

Обращением нового базиса (Х₀, Х₄, Х₅) будет матрица B^-1 .

B^-1 = ;

R = ;

= Ra₁ == 4 > 0;

= Ra₂ == 4 > 0;

= Ra₃ == 3/2 > 0.

Следовательно, получаем оптимальное решение:

X₀ = - F = - 11; X₁ = X₂ = X₃ = 0;

X₄ = ; X₅ = .