Особые случаи симплексного метода

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

Если выбранные переменные имеют те же знаки, что и соответствующие им свободные члены, то полученное БР будет ДБР. Если получено не ДБР, то М-метод. Будет рассмотрен дальше.

1 шаг. Осн – х3, х4, х5, х6.

Неосн – х1, х2.

Х3 = 18 – х1 – 3х2

Х4 = 16 – 2х1 – х2 (1)

Х5 = 5 – х2

Х6 = 21– 3х1

Неосновные = 0àХ1 =(0; 0; 18; 16; 5; 21) соответствует вершине О(0; 0).

Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2. При решении Х1 значение функции F(X1) = 0. Функцию можно увеличить за счет увеличения любой из неосновных переменных, входящих в уравнение для функции с положительным коэффициентом. Это можно осуществить перейдя к такому новому ДБР, в котором эта переменная будет основной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). Одна из переменных, при этом из основных – в неосновные. Геометрически – к соседней вершине. В данном примере и х1 и х2 м можно. Выберем х2 – больший коэффициент.

Система (1) накладывает ограничения на рост переменной х2. Т.к. необходимо сохранять допустимость решений, т.е. все переменные неотрицательны, то должны выполняться неравенства (х1 при этом = 0 как неосновная):

Х3 = 18 – 3х2 >= 0 Х4 = 16 – х2 >= 0 Х5 = 5 – х2 >= 0 Х6 = 21 >= 0

откуда

Х2 <= 18/3 Х2 <= 18/1 Х2 <= 5/1

Каждое уравнение системы (1), кроме последнего, определяет оценочное отношение – границу роста переменной х2, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при х2 при условии, что эти числа имеют разные знаки.

Граница - ¥:

§ Последнее уравнение системы не ограничивает рост переменной х2, т.к. эта переменная не входит в него (входит с 0 коэффициентом).

§ Когда свободный член и коэффициент при переменной имеют одинаковые знаки, так как и в этом случае нет ограничения на рост переменной.

§ Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член = 0, а переводимая переменная имеет знак +.

При свободном члене = 0, а переводимая переменная имеет знак – уравнение ограничивает рост переменной 0.

В данном примере наибольшее возможное значение для х2 = min{18/3; 16/1; 5/1; ¥} = 5. При х2 = 5 переменная х5 обращается в 0 и переходит в неосновные.

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

2 шаг. Осн – х2, х3, х4, х6.

Неосн – х1, х5.

Х2 = 5 – х5

Х3 = 18 – х1 – 3(5 – х5)

Х4 = 16 – 2х1 – (5 – х5) (2)

Х6 = 21– 3х1

или

Х2 = 5 – х5

Х3 = 3 – х1 + 3 х5

Х4 = 11 – 2х1 + х5

Х6 = 21– 3х1

Неосновные = 0àХ2 =(0; 5; 3; 11; 0; 21) соответствует вершине А(0; 5).

Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 2х1+ 3(5 – х5) = 15+ 2х1 – 3х5. При решении Х2 значение функции F(X2) = 15. Изменение значения линейной функции можно определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в целевой функции (изменение F = 5 * 3 =15.

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

Система (2) определяет наибольшее возможное значение для х1 = min{¥; 3/1; 11/2; 21/3} = 3. второе уравнение – разрешающее, переменная х3 обращается в 0 и переходит в неосновные, при этом приращение целевой функции = 3*2 = 6.

3 шаг. Осн – х1, х2, х4, х6.

Неосн – х3, х5.

Выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения. После преобразования получаем:

Х1 = 3 – х3 + 3 х5

Х2 = 5 – х5

Х4 = 5 + 2х3 - 5х5 (3)

Х6 = 12 + 3х3 – 9х5

Неосновные = 0àХ3 =(3; 5; 0; 5; 0; 12) соответствует вершине В(3; 5).

Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 2(3 – х3 +3х5) + 3(5 – х5) = 21- 2х3 + 3х5. При решении Х3 значение функции F(X3) = 21.

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

При определении наибольшего возможного значения для х5, которую переводим в основные, обратить внимание, что первое уравнение системы (3) не дает ограничения на рост х5, т.к. свободный член и коэффициент при х5 имеют одинаковые знаки. Система (3) определяет наибольшее возможное значение для х5 = min{¥; 5; 1; 12/9} = 1. Третье уравнение – разрешающее, переменная х4 обращается в 0 и переходит в неосновные, при этом приращение целевой функции = 1*3 = 3.

4 шаг. Осн – х1, х2, х5, х6.

Неосн – х3, х4.

Выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения. После преобразования получаем:

Х1 = 6 + 1/5х3 – 3/5х4

Х2 = 4 – 2/5х3 + 1/5х4

Х5 = 1 + 2/5х3 – 1/5х4 (3)

Х6 = 3 – 3/5х3 + 9/5х4

Неосновные = 0àХ4 =(6; 4; 0; 0; 1; 3) соответствует вершине С(6; 4).

Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 24 – 4/5х3 – 3/5х4. При решении Х4 значение функции F(X4) = 24.

Значение F4 является оптим, т.к. нет положительных коэффициентов при неосновных переменных.

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

§ Прибыль предприятия примет макс значение 24 руб. при реализации 6 ед. продукции первого вида (х1 = 6) и 4 ед. продукции второго вида (х2 = 4).

§ Дополнительные переменные х3, х4, х5 и х6 показывают разницу между запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов. При оптим плане производства х3 = х4 = 0, т.е. остатки первого и второго ресурсов равны 0, а остатки третьего и четвертого ресурсов равны соответственно 1 и 3 единицам.

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

При отыскании мин лин функции Z возможны два пути:

1) отыскать макс лин функции F, полагая, что F = - Z и учитывая, что Zmin = - Fmax;

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

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

Замечание. На каждом шаге симплексного метода какая-либо неосновная переменная переводится в основные, при этом каждое уравнение системы ограничении определяет конечное или бесконечное наибольшее возможное значение этой переменной – оценочное отношение. Могут встречаться различные случаи оценки роста неосновной переменной, которые зависят от знаков и значений свободного члена и коэффициентов при переводимой переменной. Введем обозначения:

Xi – переводимая неосновная переменная;

Bj– свободный член;

Aij – коэффициент при Xi;

Сформулируем все возможные случаи оценки роста Xi в уравнении Xj = Bj + … + AijXi + …:

1) Хi = ½Bj/Aij½, если Bj и Aij разного знака и Aij не = 0, Bj не = 0.

2) Хi = ¥, если Bj и Aij одного знака и Aij не = 0, Bj не = 0.

3) Хi = 0, если Bj = 0 и Aij > 0.

4) Хi = ¥, если Bj = 0 и Aij < 0.

5) Хi = ¥, если Aij = 0.

Неединственность оптимального решения (альтернативный оптимум):

Решим симплексным методом задачу:

F=3x1 + 3х2 à maxпри ограничениях:

х1 + х2 <= 8

A

2х1 - х2 >= 1

B

х1 - 2х2 <= 2

F=24

х1, х2 >= 0

Геометрическое решение:

Оптимум в любой точке отрезка АВ. Т.к. линия уровня параллельна этому отрезку. При решении задачи симплекс-методом наличие альтернативного оптимума проявляется следующим образом:

На очередном шаге получим: осн пер – х1, х2, х5;

неос п - х3, х4.

Выражение основных через неосн:

Х1 = 5 – (2/3)Х3 – (1/3)Х4

Х2 = 3 – (1/3)Х3 + (1/3)Х4

Х5 = 9 – Х3 – Х4

Х1 = (3; 5; 0; 0; 9) – ДБР, соответствует угловой точке А (3; 5). Линейная функция F = 24 – Х3. В выражении отсутствуют положительные коэффициенты при неосновных переменных, значит критерий оптимальности выполнен, т.е. Х1 – оптим БР, Fмакс = 24. Однако в последнем выражении для F = 24 – Х3 отсутствует неосновная переменная Х4 (входит с нулевым к-ом), поэтому изменение этой переменной не приведет к изменению цел функции.

Вырожденность базисного решения:

Решим симплексным методом задачу:

F=2x1 - х2 à maxпри ограничениях:

х1 - х2 <= 2

3х1 - 2х2 <= 6

6х1 - 4х2 <= 14

х1, х2 >= 0

На первом шаге получим: осн пер – х3, х4, х5;

неос п - х1, х2.

Выражение основных через неосн:

Х3 = 2 - Х1 + Х2

Х4 = 6 – 3Х1 + 2Х2

Х5 = 14 – 6Х1 + 4Х2

Х1 = (0; 0; 2; 6; 14) – допустимое БР. Линейная функция F = 2x1 - х2. Переводя Х1 в основные, получаем Х1 = min{2; 6/3; 14/6} = 2. Оценочные отношения в первых двух совпадают. Любое выбираем.

На втором шаге получим: осн пер – х1, х4, х5;

неос п - х2, х3.

Выражение основных через неосн:

Х1 = 5 + Х2 – Х3

Х4 = 0 – Х2 + 3Х3

Х5 = 2 – 2Х2 + 6Х3

Х2 = (2; 0; 0; 0; 2) – вырожденное БР, т.к. осн переменная Х4 = 0. Линейная функция F = 4 + Х2 – 2Х3. Переводя Х2 в основные, получаем Х2 = min{¥; 0; 1} = 0, поэтому на следующем шаге изменения целевой функции не произойдет (0 * 1). Это нарушение принципа улучшения решения. Поэтому принцип – не ухудшить.

Следующий шаг данного примера тоже приведет к вырожденному БР. Этот шаг, хоть и не вызвал увеличения значения цел функции, привел к новому БР. Наличие «пустых» шагов может привести к «зацикливанию» - не рассматриваем.

Вывод:

Если на каком-либо шаге наибольшее возможное значение переменной достигается в нескольких уравнениях одновременно (совпадают их оценочные отношения), то разрешающее – любое из них. На очередном шаге получим вырожденное БР.

Отсутствие конечного оптимума:

Решим симплексным методом задачу:

F=2x1 - 3х2 + 1à min при ограничениях:

х1 + х2 >= 4

2х1 - х2 >= 1

F=0

х1 - 2х2 <= 1

х1, х2 >= 0

A

На очередном шаге получим: осн пер – х1, х2, х5;

B

неос п - х3, х4.

Выражение основных через неосн:

Х1 = 5/3 + 1/3 Х3 + 1/3 Х4

Х2 = 7/3 + 2/3 Х3 – 1/3 Х4

Х5 = 4 + Х3 – Х4

Х1 = (5/3; 7/3; 0; 0; 4) – допустимое БР. Линейная функция F = -8/3 - 4/3x3 + 4/3х4. Переводя Х3 в основные (т.к. имеет отрицательный коэффициент, а ищем мин), получаем Х3 = min{¥; ¥; ¥} = ¥, т.к. во все уравнения эта переменная входит со знаком свободного члена. Уравнения не ограничивают рост Х3, поэтому и целевая функция неограниченно убывает.

Вывод:

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

Симплексные таблицы

Практические расчеты с использованием симплекс метода – на компьютере. Если вручную, то используются симплекс-таблицы. Будем решать задачу на максимум.

I. После введения добавочных переменных систему уравнений и лин функцию записывают в виде, который называется расширенной системой: (Слайд 2)

а11*Х1 + а12*Х2 + … + а1n*Xn + Xn+1 = В1

а21*Х1 + а22*Х2 + … + а2n*Xn + Xn +2 = В2 …………………………………………………………….

аm1*Х1 + аm2*Х2 + … + аmn*Xn + Xn +m = Вm

F – c1X1 – c2X2 - … - cnXn = 0

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены, в противном случае используется М-метод (рассмотрим дальше).

II. Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой уравнение целевой функции – оценочная. В левом столбце таблицы – основные переменные (базис), в первой строке – все переменные (отмечая при этом основные), во втором столбце – свободные члены. Последний столбец – для оценочных отношений. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты Aij.

III. Проверим выполнения критерия оптимальности (при макс – наличие отриц коэффициентов в последней строке, т.к. они с «-»). Если их нет, то достигнут максимум (его значение – в левом нижнем углу таблицы), основные переменные – значение второго столбца, неосновные = 0, т.е. оптимальное БР.

IV. Если критерий оптим не выполнен. То наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий столбец.

Составляем оценочные отношения каждой строки по правилам:

1) ½Bi/Aij½, если Bi и Aij одного знака и Aij не = 0, Bi не = 0.

2) ¥, если Bi и Aij разного знака и Aij не = 0, Bi не = 0.

3) 0, если Bi = 0 и Aij > 0.

4) ¥, если Bi = 0 и Aij < 0.

5) ¥, если Aij = 0.

Определяем min по I для {½Bi/Aij½}. Если конечного минимума нет, то нет конечного оптимума. Если минимум конечен, то выбирается строка q, на которой он достигается (любая, если их несколько), называется разрешающей строкой. На пересечении разрешающий элемент Aqs.

V. Переходим к следующей таблице по правилам:

1) в левом столбце записываем новый базис: вместо основной переменной Xq – переменную Xs;

2) в столбцах, соответствующих основным переменным, проставляем: 1 – против «своей основной переменной, 0 – против «чужой основной переменной, 0 – в последней строке для всех основных переменных;

3) новую строку с номером q получаем из старой делением на разрешающий элемент Aqs;

4) все остальные новые элементы Aij вычисляем по правилу прямоугольника: (Слайд 3)

Далее перейти к п. III алгоритма.

Пример (решали как пример симплекс-метода):

F=2x1 + 3х2 à max при ограничениях:   х1 + 3х2 <= 18 2х1 + х2 <= 16 х2 <= 5 3x1 <= 21 х1, х2 >= 0

Расширенная система имеет вид: х1 + 3х2 + х3 = 18 2х1 + х2 + х4 = 16 х2 + х5 = 5 3x1 + х6 = 21 х1, х2, х3, х4, х5, х6 >= 0 F - 2x1 - 3х2 = 0

Таблицы:

Базис	Свободный член	Переменные	Оценочное отношение
Х1	Х2	Х3	Х4	Х5	Х6
Х3								18/3
Х4
Х5
Х6								¥
F		-2	-3

Базис	Свободный член	Переменные	Оценочное отношение
Х1	Х2	Х3	Х4	Х5	Х6
Х3						-3
Х4						-1		11/2
Х2								¥
Х6
F		-2

Базис	Свободный член	Переменные	Оценочное отношение
Х1	Х2	Х3	Х4	Х5	Х6
Х1						-3		¥
Х4				-2				5/5
Х2								5/1
Х6				-3				12/9
F						-3

Базис	Свободный член	Переменные	Оценочное отношение
Х1	Х2	Х3	Х4	Х5	Х6
Х1				-1/5	3/5
Х5				-2/5	1/5
Х2				2/5	-1/5
Х6				3/5	-9/5
F				4/5	3/5

Метод искусственного базиса (М-метод)

Используется, когда первое БР – недопустимое.

В каждое уравнение, дающее отрицательную компоненту в БР, вводится своя новая неотрицательная искусственная переменная У1, У2, …, Ук, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаются в число основных (базисных) все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты БР. Составляется новая линейная функция Т = F – М(У1 + У2 + … + Ук), где М – произвольно большое число, и ищется ее максимум. (Слайд 6)

Справедлива теорема (без доказательства):

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

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

3. Если Тмах = ¥, то исходная задача также неразрешима, причем либо Fмах = ¥, либо условия задачи противоречивы.

Из теоремы следует, что сначала надо найти минимум М-функции. Если он = 0, то далее можно отбросить эти переменные и решать исходную задачу, исходя из полученного БР. На практике находят не минимум М-функции, а максимум (-М)-функции.

Пример:

F=x1 + 2х2 à max х1 - х2 <= -1 х1 - х2 >= -3 х1 <= 3 х1, х2 >= 0

Расширенная система имеет вид: х1 – х2 + х3 = -1 х1 - х2 - х4 = -3 х1 + х5 = 3 х1, х2, х3, х4, х5, х6 >= 0

Х1= (0; 0; -1; 3; 3) – недопустимое БР, поэтому в первое уравнение введем искусственную переменную У1 с тем же знаком, что и свободный член.

х1 – х2 + х3 – у1= -1 х1 - х2 - х4 = -3 х1 + х5 = 3

- х1 + х2 - х3 + у1= 1 - х1 + х2 + х4 = 3 х1 + х5 = 3

В первой симплексной таблице последняя строка – это (-М)-функция, т.е. (-М)У1. Заполняется умножением строки У1 на коэффициент (-М).

(Слайд 7) Базис	Свободный член	Переменные	Оценочное отношение
Х1	Х2	Х3	Х4	Х5	У1
У1		-1		-1
Х4		-1
Х5								¥
F		-1	-2
-Мф	-М	М	-М	М			-М

Заменяем У1 на Х2.

Базис	Свободный член	Переменные	Оценочное отношение
Х1	Х2	Х3	Х4	Х5
Х2		-1		-1
Х4
Х5
F		-3		-2
-Мф

Последняя строка показывает, что критерий оптимальности выполнен: мах (-М) = 0, значит мин М = 0. далее эту строку можно не рассматривать. Получено ДБР (0; 1; 0; 2; 3), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом.

Дата добавления: 2014-01-15