Симплексный метод линейного программирования

Сущность симплексного способа

Разглядим стандартную задачу ЛП:

,

, , (4.1)

, .

При совместности ограничений в (4.1), возможно продемонстрировать, что множество допустимых ответов образует выпуклую многоугольную область в n-мерном пространстве. В случае если эта область есть ограниченной, то будем именовать ее выпуклым многоугольником в n-мерном пространстве. В соответствии с главной теореме линейного программирования, в случае если задача ЛП имеет ответ, то целевая функция достигает оптимального значения хотя бы в одной угловой точке многоугольника ответов. В случае если же целевая функция достигает оптимального значения более, чем в одной угловой точке, то она достигает того же самого решения в любой точке отрезка, соединяющего эти точки. Следовательно, с теоретической точки зрения задача ЛП не есть сложной. Легко достаточно отыскать конечное число вершин многоугольника ответов и вычислить в них значения целевой функции. Из всех этих значений выбрать громаднейшее и мельчайшее.

С практической точки зрения, дело обстоит значительно сложнее. Во-первых, несложный перебор вершин многоугольника ответов может оказаться фактически неосуществим из-за большого числа вершин многоугольника. А во-вторых, кроме того при маленьком количестве вершин, задача нахождения координат вершин, по трудоемкости, сопоставима с исходной задачей. Исходя из этого появилась необходимость применения способов целенаправленного перебора, сущность которых, разумеется, содержится в том, дабы выбирать не все вершины, а переходить от произвольной вершины к той, в которой значение целевой функции «не хуже», чем в прошлой. Одним из таких способов есть симплекс-способ.

Главные определения симплексного способа.

Думаем, что все неравенства в (4.1) имеют вид , в случае если же имеются неравенства вида , то их легко привести к неравенству , умножив левую и правую часть неравенства на (-1). Приведем стандартную задачу ЛП (4.1) к каноническому виду. Для этого вводим дополнительные неотрицательные переменные , и приобретаем соответствующую каноническую задачу ЛП:

,

, , (4.2)

, .

Совокупность ограничений в (4.2) является системой m линейных уравнений, наряду с этим ранг данной совокупности предполагаем равным m. Эта совокупность имеет нескончаемое число ответов. При таких условиях n-m переменных смогут принимать произвольные значения (такие переменные будем именовать свободными переменными), а остальные m переменных выражаются через свободные переменные (их будем именовать базовыми переменными).

Определение 4.1. Ответ совокупности линейных уравнений, в котором все свободные переменные равны нулю, именуются базовым ответом.

Определение 4.2. Базовое ответ, в котором все компоненты неотрицательны, именуется допустимым базовым ответом.

Определение 4.3. Допустимое базовое ответ именуется невырожденным, в случае если в нем имеется ровно m хороших компонент, в другом случае, оно именуется вырожденным.

Построение первой симплексной таблицы.

Предполагаем, что задача ЛП записана в виде (4.2). При ответе задачи симплекс-способом комфортно пользоваться так называемыми симплекс-таблицами. Преобразуем (4.2) следующим образом, выбрав, в качестве базовых переменных, дополнительные переменные :

,

, , (4.3)

, ,

, ,

.

направляться обратить внимание, что в (4.3) перед символами «суммы» в первой и второй строках обязан находиться символ «минус».

На базе (4.3) составляем первую симплексную таблицу.

Таб.1. Первая симплекс-таблица

Базовые переменные Свободные элементы Свободные переменные
Целевая функция F

Метод симплекс-способа.

1итерация.

1 ход.

Нахождение базового ответа.

В базовом ответе все свободные переменные равны нулю, а базовые переменные равны свободным элементам .

2 ход.

Проверка допустимости базового ответа.

Критерий 1. Базовое ответ будет допустимым, в случае если в симплекс-таблице все свободные элементы, не считая возможно последнего, неотрицательные.

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

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

В случае если распознана несовместность, то решения у задачи нет.

В случае если несовместность не распознана и базовое ответ недопустимо, то переходим к шагу 4.

3 ход.

Проверка оптимальности ответа.

В случае если базовое ответ допустимое, то ответ проверяется на оптимальность посредством критерия 3.

Критерий 3. Целевая функция будет иметь большое (минимальное) значение, в случае если последние элементы столбцов «свободные переменные» будут неотрицательными (неположительными). Наряду с этим, большое (минимальное) значение целевой функции равняется последнему элементу в столбце «свободные элементы».

В случае если допустимое базовое ответ неоптимальное, то нужно проверить ограниченность целевой функции в соответствии с критерию 4.

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

В случае если распознана неограниченность целевой функции сверху (снизу), то точки максимума (минимума) не существует.

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

4 ход.

Нахождение разрешающего элемента.

1. Нахождение разрешающего столбца.

а) базовое ответ недопустимое.

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

б) базовое ответ допустимое, неоптимальное.

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

2. Нахождение разрешающей строки.

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

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

По окончании нахождения разрешающего элемента переходим к шагу 5.

5 ход.

Преобразование симплекс-таблицы.

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

1. На месте разрешающего элемента записывается значение .

2. Элементы разрешающей строчки делятся на разрешающий элемент, т.е.

, , , .

3. Элементы разрешающего столбца делятся на разрешающий элемент и берутся с обратным знаком, т.е.

, , , .

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

,

,

, ,

, , , .

В следствии преобразования возьмём новую симплекс-таблицу (таб.2).

Таб.2. Преобразованная симплекс-таблица

Базовые перем. Свобод. Элементы Свободные переменные
Целевая функция F

По окончании исполнения шага 5, нужно перейти ко второй итерации, начиная с шага 1, но использую уже преобразованную таблицу.

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

Подготовим условия задачи к симплекс-способу. Для этого, сначала приведем все неравенства к виду . Для этого умножим левую и правую часть третьего неравенства на (-1) и возьмём:

Сейчас введем в каждом неравенстве дополнительные переменные, дабы перейти к канонической задаче ЛП:

В качестве базовых переменных комфортно выбрать дополнительные переменные и запишем совокупность в виде (4.3):

Составим первую симплекс-таблицу.

Базовые переменные Свободные элементы Свободные переменные
X1 X2
X3 –4
X4
X5 –3 –1
F –1

1 итерация.

1 ход. Находим базовое ответ. В базовом ответе все свободные переменные равны 0, а базовые переменные равны соответствующим свободным элементам:

2 ход. Контролируем допустимость взятого базового ответа. Оно есть недопустимым, т.к. имеется отрицательный элемент (-3).

3 ход. Контролируем совместность ограничений. Ограничения совместны, т.к. в строчке с отрицательным свободным элементом (-3) имеются ещё отрицательный элемент (-1).

Так как несовместность не распознана, мы переходим к шагу 4.

4 ход. Нужно отыскать разрешающий элемент.

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

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

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

5 ход.

Преобразуем симплекс-таблицу, применяя правила преобразования:

1. На месте разрешающего элемента записывается значение .

2. Элементы разрешающей строчки делятся на разрешающий элемент (–1).

3. Элементы разрешающего столбца делятся на разрешающий элемент (–1) и берутся с обратным знаком.

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

В следствии преобразования симплекс-таблицы возьмём:

Базовые переменные Свободные элементы Свободные переменные
X5 X2
X3 -4 -9
X4
X1 -1 -3
F -6

2 итерация.

1 ход. Находим базовое ответ.

2 ход. Контролируем допустимость взятого базового ответа. Оно есть допустимым, т. к. все его компоненты не отрицательны.

Так как базовое ответ есть допустимым, то мы переходим к шагу 3.

3 ход. Все последние элементы столбцов «свободные переменные» являются хорошими (2 и 5), следовательно, отысканное допустимое базовое ответ доставляет максимум целевой функции и большое значение целевой функции равняется последнему элементу в столбце «свободные элементы»:

.

Отыщем сейчас минимум целевой функции. Так как у нас имеется допустимое базовое ответ, но оно не доставляет минимум целевой функции, то нам нужно проверить ограниченность функции снизу в соответствии с критерию 4, по которому целевая функция ограничена снизу, в случае если в каждом столбце, не удовлетворяющем показателю оптимальности, имеется хотя бы один хороший элемент. У нас оба столбца «свободные переменные» не удовлетворяют критерию оптимальности на минимум, т. к. оба последних элемента (2 и 5) являются хорошими. В этих столбцах имеется хорошие элементы (1 и 4), следовательно, неограниченность снизу не распознана и мы переходим к шагу 4.

4 ход. Нужно отыскать разрешающий элемент.

Отыщем разрешающий столбец. Мы имеем пункт б). Выберем любой столбец «свободных переменных», последний элемент которого не удовлетворяет критерию оптимальности на минимум. Так как у нас оба столбца не удовлетворяют критерию оптимальности, то из хороших элементов выбираем громаднейший, а среди 2 и 5 громаднейший имеется 5 и, следовательно, столбец будет разрешающим.

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

, то в качестве разрешающей строчки приобретаем .

Элемент, пребывающий на пересечении разрешающих строки и столбца, есть разрешающим элементом (выделен рамкой). Он показывает, что базовую переменную переводим в свободные, а свободную переменную — в базовые.

5 ход. Преобразуем симплекс-таблицу и приобретаем:

Базовые переменные Свободные элементы Свободные переменные
X5 X4
X3
X2
X1
F

3 итерация.

1 ход. Находим базовое ответ.

2 ход. Контролируем допустимость взятого базового ответа. Оно есть допустимым, т. к. все его компоненты не отрицательны.

Так как базовое ответ есть допустимым, то мы переходим к шагу 3.

3 ход. Допустимое базовое ответ не доставляет минимум целевой функции, т. к. один из последних элементов столбцов «свободная переменная» есть хорошим, это .

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

Делая действия, подобные действиям на итерации 2, приобретаем симплекс-таблицу:

Базовые переменные Свободные элементы Свободные переменные
X2 X4
X3
X5
X1
F –12 –3 –2

4 итерация.

1 ход. Находим базовое ответ.

2 ход. Контролируем допустимость взятого базового ответа. Оно есть допустимым, т. к. все его компоненты не отрицательны.

Так как базовое ответ есть допустимым, то мы переходим к шагу 3.

3 ход. Допустимое базовое ответ доставляет минимум целевой функции, т. к. все последние элементы столбцов «свободная переменная» являются отрицательными и, наряду с этим,

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

Лекция 2: Задача линейного программирования. Задача о ресурсах


Также читать:

Понравилась статья? Поделиться с друзьями: