Определитель матрицы ▦ Производная функции dydx График 3D Упростить выражение Графический метод решения задач нелинейного программирования ⇲ …
Примеры решений Метод Гомори Графический метод Теория игр Двойственная задача Двухэтапный симплекс-метод Транспортная задача 🚚 Каноническая ЗЛП Задача коммивояжера Метод искусственного базиса

Симплексный метод решения ЗЛП

Количество переменных Количество строк (количество ограничений)
При этом ограничения типа xi≥0 не учитывайте.
Здесь будет отображаться решение.
Инструкция. Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel.

Если в задании для некоторых xi отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом. При решении автоматически определяется использование М-метода (симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода.

Данные также можно будет вставить как текст. Для этого используйте кнопку и вставьте данные в формате:
aij;условие;bi
fxj;С;extri

где aij - матрица коэффициентов системы неравенств, разделенных символом ;, bi - правая часть неравенств, fxj - коэффициенты целевой функции, разделенных символом ;, С - константа целевой функции (обычно 0).

Например, для текста:

1;2;3;-5;=;45
3;1;-3;0;>=;23
0;-2;0;1;<=;44
1;1;1;0;0;max
будет сформирована следующая система неравенств:
x1x2x3x4B
Функция цели F(x)
x1x2x3x4Cextr
Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.


Экстремум функции двух переменных


Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X)зависит от количества реализованных партий товара Х и представлен в таблице.
Объем товара Х (в партиях) Доход G(X)
1 2 3
0 0 0 0
1 28 30 32
2 41 42 45
3 50 55 48
4 62 64 60
5 76 76 72

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

Назначение сервиса. Сервис предназначен для онлайн решения задач линейного программирования (ЗЛП) симплекс-методом в следующих формах записи:

Алгоритм симплекс-метода включает следующие этапы:
  1. Составление первого опорного плана. Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
  2. Проверка плана на оптимальность. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
  3. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
  4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана—Гаусса.
БазисBx1x2x3x4min
x320521020:5=4
x4611016:1=6
F(X1)-8-5000

Если необходимо найти экстремум целевой функции, то речь идет о поиске минимального значения (F(x) → min, см. пример решения минимизации функции) и максимального значения (F(x) → max, см. пример решения максимизации функции)

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

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

Суть симплекс-метода. Движение к точке оптимума осуществляется путем перехода от одной угловой точки к соседней, которая ближе и быстрее приближает к Xопт. Такую схему перебора точек, называемую симплекс-метод, предложил Р. Данцигом.
Угловые точки характеризуются m базисными переменными, поэтому переход от одной угловой точки к соседней возможно осуществить сменой в базисе только одной базисной переменной на переменную из небазиса.
Реализация симплекс-метода в силу различных особенностей и постановок задач ЛП имеет различные модификации.

Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.

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

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

Замечание 2. Пусть в некоторой крайней точке все симплексные разности неотрицательные Dk³ 0 (k = 1..n+m),т.е. получено оптимальное решение и существует такой Аk – небазисный вектор, у которого Dk = 0. Тогда максимум достигается по крайней мере в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную xk, значение целевой функции не изменится.

Замечание 3. Решение двойственной задачи находится в последней симплексной таблице. Последние m компонент вектора симплексных разностей( в столбцах балансовых переменных) – оптимальное решение двойственной задачи. Значение целевых функций прямой и двойственной задачи в оптимальных точках совпадают.

Замечание 4. При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации.

Если задано условие «Необходимо, чтобы сырье III вида было израсходовано полностью», то соответствующее условие представляет собой равенство.

Аналитическое введение в симплекс-метод

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

Итак, если мы решаем ЗЛП в канонической форме, то система ограничений - это обычная система линейных уравнений. При решении задач ЛП получаются системы линейных уравнений, имеющие, как правило, бесконечно много решений.

Например, пусть дана система

Здесь число уравнений равно 2, а неизвестных - 3, уравнений меньше. Выразим x1 и x2 через x3:

Это общее решение системы. если переменной x3 придавать произвольные числовые значения, то будем находить частные решения системы. Например, x3=1 → x1=1 → x2=6. Имеем (1, 6, 1) - частное решение. Пусть x3=2 → x1=-3, x2= 1, (-3, 1, 2) - другое частное решение. Таких частных решений бесконечно много.

Переменные x1 и x2 называются базисными, а переменная x3 - не базисная, свободная.

Совокупность переменных x1 и x2 образует базис: Б (x1, x2). Если x3 = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б (x1, x2).

Базисным называется решение, соответствующее нулевым значениям свободных переменных.
В качестве базисных можно было взять и другие переменные: (x1, x3) или (x2, x3).
Как переходить от одного базиса Б(x1, x2) к другому базису Б(x1, x3)?
Для этого надо переменную x3 перевести в базисные, а x2 - в небазисные т. е. в уравнениях надо x3 выразить через x2 и подставить в 1-е:

Базисное решение, соответствующее базису Б (x1, x3), таково: (-19/5; 0; 11/5).

Если теперь от базиса Б (x1, x3) нам захочется перейти к базису Б (x2, x3), то

Базисное решение, соответствующее базису Б (x2, x3): (0;19/4; 7/8).
Из трех найденных базисных решений решение, соответствующее базису Б (x1, x3) - отрицательное x1  < 0, нас в ЗЛП интересуют только неотрицательные решения.

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

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

Пример. Решить задачу ЛП.

Функцию F= x2 - x1 → min необходимо минимизировать при заданной системе ограничений:
-2x1 + x2 + x3 = 2
x1 + x2 + x5 = 5
x1 - 2x2 + x4 = 12
xi ≥ 0, i = 1, 5

Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x3, x5, x4 - как дополнительные.
Запишем ограничения, выбрав базис из переменных Б{ x3, , x4, x5}:

Этому базису соответствует базисное неотрицательное решение
x1 = 0, x2 = 0, x3 = 2, x4 = 2, x5 = 5 или (0, 0, 2, 2, 5).
Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F= x2 - x1.
Проверим, достигла ли функция F своего минимального значения. Для этого базисного решения F= 0 - 0 = 0 - значение функции равно 0. Но его можно уменьшить, если x1 будет возрастать, т. к. коэффициент в функции при x1 отрицателен. Однако при увеличении x1 значения переменных x4, x5 уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная x1 не может быть увеличена больше чем до 2, иначе x4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x5 - отрицателен. Итак, из анализа равенств следует, что переменную x1 можно увеличить до 2, при этом значение функции уменьшится.
Перейдем к новому базису Б2, введя переменную x1 в базис вместо x4.
Б2{x1, x3, x5}.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим x1 из второго уравнения и подставим в остальные, в том числе и в функцию.

Имеем:

F = -2 - x2 + x4.
Базисное решение, соответствующее базису Б2{x1, x3, x5}, имеет вид (2, 0, 6, 0, 3), и функция принимает значение F= -2 в этом базисе.
Значение функции можно и дальше уменьшать, увеличивая x2. Однако, глядя на систему, x2 можно увеличивать лишь до 1, т. к. иначе из последнего равенства x5 = 3 - 3x2 + x4 следует, что при x2 > 1 x5 станет отрицательной. А у нас все переменные в ЗЛП предполагаются неотрицательными. Остальные уравнения системы не дают ограничений на x2. Поэтому увеличим x2 до 1, введя его в базис вместо x5: Б3{x1, x2, x3}.
Выразим x2 через x5 и подставим во все уравнения:



Базисное решение, соответствующее базису Б3{х1, х2,х3}, выписывается (4, 1, 9, 0, 0), и функция принимает значение F= -3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x4 = 0, x5 = 0 значение F= -3. как только x4, x5 станут положительными, значение F только увеличится, т. к. коэффициенты при x4, x5 положительны. Значит, функция F достигла своего оптимального значения F* = -3. Итак, наименьшее значение F, равное -3, достигается при x1* = 4, x2* = 1, x3* = 9, x4* = 0, x5* = 0.

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

Поиск первоначального опорного плана

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

-4x1-3x2-2x3+x4=-33
-3x1-2x2-x3+x5=-23
-x1-x2-2x3+x6=-12
xi≥0, i=1,6
F = 20х1 + 20х2 + 10х3 → min.

Запишем задачу в симплекс-таблицу (табл. 1).

Таблица 1

Базисное решение, соответствующее базису {x4, x5, x6} и равное (0; 0; 0; -33; 23; -12), не является допустимым ввиду отрицательности х4 < 0, x5 < 0, x6 < 0.

Сформулируем правило нахождения допустимого опорного плана.
Если в столбце свободных членов есть отрицательные элементы, выберите из них наибольший по модулю, а в его строке - любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитайте таблицу по прежним правилам 2-5.
Если в полученной таблице все элементы столбца свободных членов стали положительны либо 0, то данное базисное решение можно взять в качестве первоначального опорного плана. Далее симплекс-методом дорешать задачу. Если в столбце свободных членов не все элементы неотрицательны, то еще раз воспользоваться этим правилом.
Проведем этот шаг для задачи о рационе. В качестве разрешающей строки табл. 1 нужно выбрать первую. А разрешающим элементом выберем, к примеру, элемент -4.

Таблица 2

базисные -х4 -х2 -х3 свободные
х1 1/4 3/4 ½ 33/4
х5 -3/4 1/4 ½ 7/4
←х6 -1/4 -1/4 -3/2 -15/4
↑F 5 5 0 165
Заметим, что переменная х1 вошла в базис вместо х4, все вычисления осуществлялись по правилу 2-5. В правом столбце еще остался отрицательный элемент, воспользуемся правилом еще раз. Строка переменной х6 - разрешающая, а в качестве разрешающего элемента возьмем, к примеру, 3/2, здесь есть некоторая возможность выбора.

Таблица 2

базисные -х4 -х2 -х6 свободные
х1 -1/3 2/3 1/3 7
х5 -5/6 1/6 1/3 ½
х3 1/6 1/6 -2/3 5/2
F 5 5 0 165
Полученный базисный план х* = (х1, х2, х3, х4, х5, х6) = (7, 0, 5/2, 0, 1/2, 0) является допустимым и, к тому же, оказывается оптимальным, т.к. в индексной строке нет отрицательных элементов. Оптимальное значение целевой функции равно F* = 165. Действительно,
F = 20х1 + 20х2 + 10х3 = 20 · 7 + 0 + 10·5/2 = 140 + 25 = 165.

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

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

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

Таблица 3

Виды продукции →

Виды сырья ↓

I

II

III

IV

Запасы ресурсов

1

5

0,4

2

0,5

400

2

0

5

1

1

300

3

1

0

1

1

100

Прибыль

3

5

4

5

 

Составим математическую модель. Пусть х1, х2, х3, х4 - количество продукции I, II, III, IV вида соответственно в плане. Тогда количество используемого сырья и его запасы выразятся в неравенствах:
5x1+0.4x2+2x3+0.5x4≤400
5x2+x3+x4≤300
x1+x3+x4≤100
x1≥0, x2≥0, x3≥0, x4≥0
F = 3x1+5x2+ 4x3+ 5x4 → max.

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

Приведем задачу к канонической форме и к специальному виду, введя дополнительные переменные х5, х6, х7 в каждое из неравенств.
Очевидно, что, если первого ресурса необходимо для производства плановой продукции 5х1 + 0,4х2 + 2х3 + 0,5х4, то х5 обозначает просто излишки первого ресурса как разность между имеющимся запасом и требуемым для производства. Аналогично х6 и х7. Итак, дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Запишем задачу в таблицу 4, предварительно выписав ее каноническую форму:
5x1+0.4x2+2x3+0.5x4+x5=400
5x2+x3+x4+x6=300
x1+x3+x4+x7=100
xi≥0, i=1,7
-F = -3x1-5x2-4x3-5x4 → min.

I этап. Это задача специального вида, базис составляют переменные {х5, х6, х7}, правые части уравнений неотрицательны, план х = (0, 0, 0, 0, 400, 300, 100) - опорный. Он соответствует симплекс-таблице.

Таблица 4

базисные

-х1

-х2

-х3

-х4

свободные

х5

5

0,4

2

0,5

400

х6

0

5

1

1

300

х7

1

0

1

1 ←

100

-F

-3

-5

-4

-5 ↑

0

II этап. Проверим план на оптимальность. Так как в индексной F-строке есть отрицательные элементы, то план неоптимален, переходим к III этапу.

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

Таблица 5

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

В качестве разрешающего элемента выбираем 5, т.к. .

Пересчитываем еще раз таблицу. Заметим, что пересчет удобно начинать с индексной строки, т.к. если в ней все элементы неотрицательны, то план оптимален, и чтобы его выписать, достаточно пересчитать столбец свободных членов, нет необходимости вычислять "внутренность" таблицы (табл. 6).

Таблица 6

базисные

-х1

-х6

-х3

-х7

свободные

х5

 

 

 

 

334

х2

 

 

 

 

40

х4

 

 

 

 

100

-F

1

1

1

4

700

План оптимален, т.к. в индексной строке нет отрицательных элементов, выписываем его.

IV этап. Базисные переменные {x5, x2, x4} принимают значения из столбца свободных членов, а свободные переменные равны 0. Итак, оптимальный план х* = (0, 40, 0, 100, 334, 0, 0) и F* = 700. Действительно, F  = 3х1 + 4х3 + 5х2 + 5х4 = 5 · 40 + 5 · 100 = 700. Т. е. для получения максимальной прибыли в 700 руб. предприятие должно выпускать изделия II вида в количестве 40 штук, IV - вида в количестве 100 штук, изделия I и III вида производить невыгодно. При этом сырье второго и третьего вида будет израсходовано полностью, а сырья первого вида останется 334 единицы (х5  = 334, х6 = 0, х7 = 0).

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

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

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

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

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

Рассмотрим симплексный метод на конкретном примере задачи о составлении плана.

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

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

Задача.

Для изготовления изделий А и В склад может отпустить сырья не более 80 единиц. Причем на изготовление изделия А расходуется две единицы, а изделия В - одна единица сырья. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий А требуется изготовить не более 50 шт., а изделий В - не более 40 шт. Причем, прибыль от реализации одного изделия А - 5 руб., а от В - 3 руб.

Построим математическую модель, обозначив за х1 количество изделий А в плане, за х2 - количество изделий В. тогда система ограничений будет выглядеть следующим образом:

x1≤50
x2≤40
2x1+x2≤80
x1≥0, x2≥0
5x1+3x2→max

Приведем задачу к каноническому виду, введя дополнительные переменные:

x1+x3=50
x2+x4=40
2x1+x2+x5=80
x1≥0, x2≥0
5x1+3x2→max
-F = -5x1 - 3x2 → min.

Эта задача имеет специальный вид (с базисом, правые части неотрицательны). Ее можно решить симплекс-методом.

I этап. Запись задачи в симплекс-таблицу. Между системой ограничений задачи (3.10) и симплекс-таблицей взаимно-однозначное соответствие. Строчек в таблице столько, сколько равенств в системе ограничений, а столбцов - столько, сколько свободных переменных. Базисные переменные заполняют первый столбец, свободные - верхнюю строку таблицы. Нижняя строка называется индексной, в ней записываются коэффициенты при переменных в целевой функции. В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена; если есть, то записываем его с противоположным знаком. На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблицы к другой должно увеличиваться по модулю. Итак, нашей системе ограничений соответствует таблица 3.4, и можно переходить ко II этапу решения.

Таблица 3.4

базисные

-х1

-х2

свободные

х3

х4

х5

1

0

2

0

1

1

50

40

80

-F

-5

-3

0

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

Данной таблице 3.4 соответствует следующий опорный план:

(х1, х2, х3, х4, х5) = (0, 0, 50, 40, 80).

Свободные переменные х1, х2 равны 0; х1 = 0, х2 = 0. А базисные переменные х3, х4, х5 принимают значения х3 = 50, х4 = 40, х5 = 80 - из столбца свободных членов. Значение целевой функции:

-F = - 5х1 - 3х2 = -5 · 0 - 3 · 0 = 0.

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

Возможны различные ситуации.

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

2. В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция F→∞ неограниченно убывает.

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

III этап. Улучшение опорного плана.

Из отрицательных элементов индексной F-строки выберем наибольший по модулю, назовем соответствующий ему столбец разрешающим и пометим "↑".

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

В нашем примере, , элемент 2 - разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей (табл. 3.5).

Таблица 3.5

Выбрав разрешающий элемент, делаем перечет таблицы по правилам:

1. В новой таблице таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В нашем примере: х1 входит в базис, вместо х5, которая выходит из базиса и теперь свободная (табл. 3.6).

Таблица 3.6

базисные

-х5

-х2

свободные

х3

-½

х4

0

 

 

х1

½ ½

40

-F

5/2

 

 

2. На месте разрешающего элемента 2 записываем обратное ему число ½.

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

4. Элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком.

5. Чтобы заполнить оставшиеся элементы таблицы 3.6, осуществляем пересчет по правилу прямоугольника. Пусть мы хотим посчитать элемент, стоящий на месте 50.

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

Итак, . Записываем 10 на место, где было 50. Аналогично:
, , , .

Таблица 3.7

Имеем новую таблицу 3.7, базисными переменными теперь являются переменные {x3,x4,x1}. Значение целевой функции стало равно -200, т.е. уменьшилось. Чтобы проверить данное базисное решение на оптимальность надо перейти опять ко II этапу. Процесс, очевидно, конечен, критерием остановки являются пункт 1 и 2 II этапа.

Доведем решение задачи до конца. Для этого проверим индексную строку и, увидев в ней отрицательный элемент -½, назовем соответствующий ему столбец разрешающим и, согласно III этапу, пересчитаем таблицу. Составив отношения и выбрав среди них минимальное  = 40, определили разрешающий элемент 1. теперь пересчет осуществляем согласно правилам 2-5.

Таблица 3.8

базисные

-х5

-х4

свободные

х3

-½ ½

30

х2

0

1

40

х1

½ -½

20

-F

5/2 ½

220

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

IVэтап. Выписывание оптимального решения.

Если симплекс-метод остановился согласно пункту 1 II этапа, то решение задачи выписывается следующим образом. Базисные переменные принимают значения столбца свободных членов соответственно. В нашем примере х3 = 30, х2  = 40, х1 = 20. Свободные переменные равны 0, х5 = 0, х4 = 0. Целевая функция принимает значение последнего элемента столбца свободных членов с противоположным знаком: -F = -220 → F= 220, в нашем примере функция исследовалась на min, и первоначально F → max, поэтому фактически знак поменялся дважды. Итак, х* = (20, 40, 30, 0, 0), F* = 220. Ответ к задаче:

- необходимо в план выпуска включить 20 изделий типа А, 40 изделий типа В, при этом прибыль будет максимальной и будет равна 220 руб.

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

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

Пример. Решить следующую задачу ЛП в канонической форме симплекс-методом.
f(x)=x1+9x2+5x3+3x4+4x5+14x6 → min
x1+x4=20
x2+x5=50
x3+x6=30
x4+x5+x6=60
xi ≥ 0, i = 1,…,6
Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид равенств, а все свободные члены неотрицательны. Так что мы имеем задачу в канонической форме.
Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число "шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).
Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП.
Решение. Чтобы найти начальное допустимое базисное решение, т.е. чтобы определить базисные переменные, систему (5.6) нужно привести к "диагональному" виду. Применяя метод Гаусса (метод последовательного исключения неизвестных), получаем из (5.6):
x2+x1+x3=40
x4+x1=20
x5-x1-x3=10
x6+x3=30
Следовательно, базисными являются переменные x2, x4, x5, x6, им придаем значения, равные свободным членам соответствующих строк: x2=40, x4=20, x5=10, x6=30,. Переменные x1 и x3 являются небазисными: x1=0, x3=0 .
Построим начальное допустимое базисное решение
x0 = (0,40,0,20,10,30) (5.9)
Для проверки на оптимальность найденного решения x0 нужно из целевой функции исключить базисные переменные (с помощью системы (5.8) ) и построить специальную симплекс таблицу.
После исключения переменных целевую функцию удобно записать в виде:
f(x) = -7x1 – 14x3 +880 (5.10)
Теперь при помощи (5.8) –(5.10) составляем начальную симплекс-таблицу:

В нулевую строчку записаны коэффициенты с обратным знаком соответствующих переменных при целевой функции. Критерий оптимальности (для задачи на поиск минимума): допустимое базисное решение(x0) оптимально, если в нулевой строчке нет ни одного строго положительного числа (не считая значения целевой функции (880)). Это правило распространяется и на следующие итерации (таблицы). Элементы нулевой строки будем называть оценками столбцов.
Так что начальное допустимое базисное решение (5.9) неоптимально: 7>0, 14>0.
В нулевом столбике записаны значения базисных переменных. Они обязательно должны быть неотрицательными (см. уравнение (5.7) ). От первой по четвертую строки написаны коэффициенты переменных из системы (5.8).
Так как x0 неоптимально, то надо перейти к другой вершине многогранника допустимых решений (построить новое д.б.р.). Для этого нужно найти ведущий элемент и провести определенное преобразование (симплексное преобразование).
Сначала находим ведущий элемент таблицы, который стоит в пересечении ведущего столбика (столбец с наибольшей положительной оценкой) и ведущей строки (строки, соответствующей минимальному соотношению элементов нулевого столбика к соответствующим элементам (строго положительным) ведущего столбика).
В таблице 1 ведущий столбик - третий столбик, и ведущая строка - четвертая строка (min{40/1,30/1}=30/1) обозначены стрелками, а ведущий элемент - кружочком. Ведущий элемент показывает, что базисную переменную x6 нужно заменить на небазисную x3. Тогда новыми базисными переменными будут x2, x3, x4, x5, , а небазисными -x1, x6, . Это и означает переход к новой вершине многогранника допустимых решений. Чтобы найти значения координат нового допустимого базисного решения x00 нужно строить новую симплекс-таблицу и провести в ней элементарные преобразования:
а) все элементы ведущей строки поделить на ведущий элемент, превратив этим самым ведущий элемент в 1 (для простоты выкладок);
б) с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения неизвестных);
В результате в нулевом столбце получены значения новых базисных переменных x2, x3, x4, x5, (см. таблицу 2) - базисные компоненты новой вершины x00 (небазисные компоненты x1=0, x6=0, ).
Как показывает таблица 2, новое базисное решение x00=(0,10,30,20,40,0) неоптимально (в нулевой строке есть неотрицательная оценка 7). Поэтому с ведущим элементом 1 (см. таблицу 2 ) строим новую симплекс-таблицу, т.е. строим новое допустимое базисное решение
Таблице 3 соответствует допустимое базисное решение x000=(10,0,30,10,50,0) и оно оптимально, т.к. в нулевой строчке нет положительных оценок. Поэтому f(x000)=390 есть минимальное значение целевой функции.
Ответ: x000=(10, 0, 30, 10, 50, 0) - точка минимума, f(x000)=390.

Условно стандартная задача линейного программирования

Необходимо выполнить в указанном порядке следующие задания.
  1. Найти оптимальный план прямой задачи:
    а) графическим методом;
    б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
  2. Построить двойственную задачу.
  3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
  4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
  5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).
  6. Найти оптимальное целочисленное решение:
    а) графическим методом;
    б) Методом Гомори.
    Сравнить значения функций целочисленного и нецелочисленного решений

Особенности симплекс-метода

При решении симплекс-методом могут возникать следующие ситуации:
  1. Вырожденность;
  2. Зацикливание;
  3. Альтернативные оптимальные решения;
  4. Неограниченные решения;
  5. Отсутствие допустимых решений.

Вырожденность

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

Зацикливание

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

Альтернативные оптимальные решения

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

Пример. Определим максимальное значение целевой функции F(X) = 2x1 + 4x2 при следующих условиях-ограничений.
x1 + 2x2<=5
x1 + x2<=4
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (<=) вводим базисную переменную x3. В 2-м неравенстве смысла (<=) вводим базисную переменную x4.
1x1 + 2x2 + 1x3 + 0x4 = 5
1x1 + 1x2 + 0x3 + 1x4 = 4
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =
1210
1101

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x3, x4,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,5,4)
Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4
x3 5 1 2 1 0
x4 4 1 1 0 1
F(X0) 0 -2 -4 0 0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (5 : 2 , 4 : 1 ) = 21/2
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 min
x3 5 1 2 1 0
x4 4 1 1 0 1 4
F(X1) 0 -2 -4 0 0 0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 1 войдет переменная x2 .
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4
5 : 2 1 : 2 2 : 2 1 : 2 0 : 2
4-(5 • 1):2 1-(1 • 1):2 1-(2 • 1):2 0-(1 • 1):2 1-(0 • 1):2
0-(5 • -4):2 -2-(1 • -4):2 -4-(2 • -4):2 0-(1 • -4):2 0-(0 • -4):2


Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4
x2 21/2 1/2 1 1/2 0
x4 11/2 1/2 0 -1/2 1
F(X1) 10 0 0 2 0

1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4
x2 21/2 1/2 1 1/2 0
x4 11/2 1/2 0 -1/2 1
F(X2) 10 0 0 2 0

Оптимальный план можно записать так:
x2 = 21/2
F(X) = 4•21/2 = 10
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x4. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 11/2
В индексной строке в 1-ом столбце нулевое значение. В столбце, содержащем этот нуль, имеется хотя бы один положительный элемент. Следовательно, задача имеет множество оптимальных планов.
Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x2), выполнив соответствующие этапы алгоритма.
После преобразований получаем новую таблицу:

Базис B x1 x2 x3 x4
x1 5 1 2 1 0
x4 -1 0 -1 -1 1
F(X ) 10 0 0 2 0

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

Неограниченные решения

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

Пример. Определим максимальное значение целевой функции F(X) = x1 + 2x2 при следующих условиях-ограничений.
x1 - x2<=10
x1<=20
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (<=) вводим базисную переменную x3. В 2-м неравенстве смысла (<=) вводим базисную переменную x4.
1x1-1x2 + 1x3 + 0x4 = 10
1x1 + 0x2 + 0x3 + 1x4 = 20
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =
1-110
1001

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x3, x4,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,10,20)
Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4
x3 10 1 -1 1 0
x4 20 1 0 0 1
F(X0) 0 -1 -2 0 0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (10 : 1 , 20 : 1 ) = 10
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 min
x3 10 1 -1 1 0 10
x4 20 1 0 0 1 20
F(X1) 0 -1 -2 0 0 0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 1 войдет переменная x1 .
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4
10 : 1 1 : 1 -1 : 1 1 : 1 0 : 1
20-(10 • 1):1 1-(1 • 1):1 0-(-1 • 1):1 0-(1 • 1):1 1-(0 • 1):1
0-(10 • -1):1 -1-(1 • -1):1 -2-(-1 • -1):1 0-(1 • -1):1 0-(0 • -1):1


Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4
x1 10 1 -1 1 0
x4 10 0 1 -1 1
F(X1) 10 0 -3 1 0

Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (- , 10 : 1 ) = 10
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 min
x1 10 1 -1 1 0 -
x4 10 0 1 -1 1 10
F(X2) 10 0 -3 1 0 0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x2 .
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4
10-(10 • -1):1 1-(0 • -1):1 -1-(1 • -1):1 1-(-1 • -1):1 0-(1 • -1):1
10 : 1 0 : 1 1 : 1 -1 : 1 1 : 1
10-(10 • -3):1 0-(0 • -3):1 -3-(1 • -3):1 1-(-1 • -3):1 0-(1 • -3):1


Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4
x1 20 1 0 0 1
x2 10 0 1 -1 1
F(X2) 40 0 0 -2 3

Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4
x1 20 1 0 0 1
x2 10 0 1 -1 1
F(X3) 40 0 0 -2 3

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

Отсутствие допустимых решений

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

Пример. Определим максимальное значение целевой функции F(X) = 3x1 + 2x2 при следующих условиях-ограничений.
2x1 + x2<=2
3x1 + 4x2=>12
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (<=) вводим базисную переменную x3. В 2-м неравенстве смысла (=>) вводим базисную переменную x4 со знаком минус.
2x1 + 1x2 + 1x3 + 0x4 = 2
3x1 + 4x2 + 0x3-1x4 = 12
Введем искусственные переменные x: в 2-м равенстве вводим переменную x5;
2x1 + 1x2 + 1x3 + 0x4 + 0x5 = 2
3x1 + 4x2 + 0x3-1x4 + 1x5 = 12
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = - Mx5 → max
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x5 = 12-3x1-4x2+x4
которые подставим в целевую функцию:
F(X) = - M(12-3x1-4x2+x4) → max
или
F(X) = (3M)x1+(4M)x2+(-M)x4+(-12M) → max
Введем новую переменную x0 = 3x1 + 4x2.
Выразим базисные переменные <3, 5> через небазисные.
x0 = -12+3x1+4x2-x4
x3 = 2-2x1-x2
x5 = 12-3x1-4x2+x4
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
max(3,4,0,-1,0) = 4
x0 = -12+3x1+4x2-x4
x3 = 2-2x1-x2
x5 = 12-3x1-4x2+x4
В качестве новой переменной выбираем x2.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2
и из них выберем наименьшее:
min (2 : 1 , 12 : 4 ) = 2
Вместо переменной x3 в план войдет переменная x2.
4. Пересчет всех уравнений.
Выразим переменную x2 через x3
x2 = 2-2x1-x3
и подставим во все выражения.
x0 = -12+3x1+4(2-2x1-x3)-x4
x5 = 12-3x1-4(2-2x1-x3)+x4
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = -4-5x1-4x3-x4
x2 = 2-2x1-x3
x5 = 4+5x1+4x3+x4
Полагая небазисные переменные x = (2, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (5, 0, 4, 1, 0), x0 = -4
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
x0 = -4-5x1-4x3-x4
x2 = 2-2x1-x3
x5 = 4+5x1+4x3+x4
На этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.
x2 = 2-2x1-x3
x5 = 4+5x1+4x3+x4
Выразим базисные переменные:
x2 = 2-2x1-x3
которые подставим в целевую функцию:
F(X) = 3x1 + 2(2-2x1-x3)
или
F(X) = 4-x1-2x3
Получаем новую систему переменных.
x0 = 4-x1-2x3
x2 = 2-2x1-x3
x5 = 4+5x1+4x3+x4
Переменных для включения в новый базис не найдено.
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 4-x1-2x3
x2 = 2-2x1-x3
x5 = 4+5x1+4x3+x4
Так как в оптимальном решении присутствуют искусственные переменные (x5 > 0), то задача не имеет допустимого решения.

Симплекс-метод с естественным базисом

Для применения симплекс-метода с естественным базисом КЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП).
Для определенности предположим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден – (b1, b2 ,…, bm ,0,…,0).
Проверка на оптимальность опорного плана проходит с помощью признака оптимальности, переход к другому опорному плану проводится с помощью преобразований Жордана-Гаусса при использовании математического признака оптимальности. Полученный опорный план снова проверяется на оптимальность и так далее. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получается оптимальный опорный план и соответствующее ему оптимальное значение ЦФ.
Математический признак оптимальности состоит из следующих двух теорем:
1. Если для всех векторов А1, А2,…, Аn выполняется условие
где ,
то полученный опорный план является оптимальным.
2. Если для некоторого вектора, не входящего в базис, выполняется условие, то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:
- если все компоненты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);
- если имеется хотя бы одна положительная компонента у вектора, подлежащего вводу в базис, то можно получить новый опорный план.
На основании признака оптимальности в базис вводится вектор Ак, давший минимальную отрицательную величину симплекс разности:
Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор Аr, который дает минимальное положительное оценочное отношение

Строка Аr называется направляющей, столбец Аки элементar к– направляющими.
Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:
а элементы i-й строки – по формулам:
Значения нового опорного плана рассчитываются по формулам:
для i = r ;
Процесс решения продолжают либо до получения оптимального плана, либо до установления неограниченности ЦФ. Если среди симплекс-разностей (оценок) оптимального плана нулевые только оценки, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему, то в общем случае это означает, что оптимальный план не единственный.
Примечание. Для использования приведенной процедуры к минимизации линейной функции f (x1,x2,…, xn) следует искать максимум - f (x1,x2,…, xn), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.
Пример. Получить решение по модели:
Эта задача (модель) линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных x 3 и x4:
КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,300,150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

Номер



В

2

3

0

0


симплекс-

Базис


план





Q

таблицы









А3

0

300

1

3

1

0

100
0
А4

0

150

1

1

0

1

150


f(x)

0

-2

-3

0

0


А2

3

100

1/3

1

1/3

0

300
I
А4

0

50

2/3

0

-1/3

1

75


f(x)

300

-1

0

1

0


А2

3

75

0

1

1/2

-1/2

II
А1

2

75

1

0

-1/2

3/2




f(x)

375

0

0

1/2

3/2


В симплекс-таблице II получен оптимальный опорный план, поскольку все симплекс-разности (оценки)j. Оптимальные значения переменных равны: x1*=75, x2* =75 (основные переменные), x3* =0, x4* =0 (дополнительные переменные). Максимальное значение целевой функции равно 375.
Таким образом, в рассмотренной выше задаче об оптимальном использовании ограниченных ресурсов, оптимальная производственная программа состоит в выпуске 75ед. изделий первого вида и 75ед. изделий второго вида. С этой программой связана максимальная выручка от реализации готовой продукции – 375 у.е.

Вопросы для самоконтроля

  1. Как строится симплекс-таблица?
  2. Как отражается смена базиса в таблице?
  3. Сформулируйте критерий остановки симплекс-метода.
  4. Как организовать пересчет таблицы?
  5. С какой строки удобно начинать пересчет таблицы?

Анализ оптимального плана симплекс-таблицы

Задание. Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В, и С. Потребность aij на каждую единицу j-го вида продукции i-го вида сырья, запас bj соответствующего вида сырья и прибыль cj от реализации единицы j-го вида продукции заданы таблицей.
1. Для производства двух видов продукции I и II с планом x1 и x2 единиц составить целевую функцию прибыли Z и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n единиц обоих видов продукции.
2. В условиях задачи 1 составить оптимальный план (x1,x2) производства продукции, обеспечивающий максимальную прибыль Z. Определить остатки каждого вида сырья. (Задачу решить симплекс–методом)
3. Построить по полученной системе ограничений многоугольник допустимых решений и найти оптимальный план производства геометрическим путем. Определить соответствующую прибыль Z.

Решение находим с помощью калькулятора. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 3x1 + 2x2 при следующих условиях-ограничений.
x1 + 2x2<=6
x1 + x2<=5
2x1 + 2x2<=10
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (<=) вводим базисную переменную x3. В 2-м неравенстве смысла (<=) вводим базисную переменную x4. В 3-м неравенстве смысла (<=) вводим базисную переменную x5.
1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 6
1x1 + 1x2 + 0x3 + 1x4 + 0x5 = 5
2x1 + 2x2 + 0x3 + 0x4 + 1x5 = 10
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =
12100
11010
22001

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,6,5,10)
Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4 x5
x3 6 1 2 1 0 0
x4 5 1 1 0 1 0
x5 10 2 2 0 0 1
F(X0) 0 -3 -2 0 0 0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (6 : 1 , 5 : 1 , 10 : 2 ) = 5
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 x5 min
x3 6 1 2 1 0 0 6
x4 5 1 1 0 1 0 5
x5 10 2 2 0 0 1 5
F(X1) 0 -3 -2 0 0 0 0

Поскольку в последнем столбце присутствует несколько минимальных элементов 5, то номер строки выбираем по правилу Креко.
Метод Креко заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения min=5, делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x1 .
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5
6-(5 • 1):1 1-(1 • 1):1 2-(1 • 1):1 1-(0 • 1):1 0-(1 • 1):1 0-(0 • 1):1
5 : 1 1 : 1 1 : 1 0 : 1 1 : 1 0 : 1
10-(5 • 2):1 2-(1 • 2):1 2-(1 • 2):1 0-(0 • 2):1 0-(1 • 2):1 1-(0 • 2):1
0-(5 • -3):1 -3-(1 • -3):1 -2-(1 • -3):1 0-(0 • -3):1 0-(1 • -3):1 0-(0 • -3):1


Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4 x5
x3 1 0 1 1 -1 0
x1 5 1 1 0 1 0
x5 0 0 0 0 -2 1
F(X1) 15 0 1 0 3 0

1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4 x5
x3 1 0 1 1 -1 0
x1 5 1 1 0 1 0
x5 0 0 0 0 -2 1
F(X2) 15 0 1 0 3 0

Оптимальный план можно записать так:
x3 = 1
x1 = 5
x5 = 0
F(X) = 3•5 = 15

Анализ оптимального плана

В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 1. Значение 0 в столбце x1 означает, что использование x1 - выгодно. Значение 1 > 0 в столбце x2 означает, что использование x2 - не выгодно. Значение 3 в столбце x4 означает, что теневая цена (двойственная оценка) равна 3.

Скачать решение

Пример. Фирме «Иерихонская сталь» предстоит решить, какое количество чистой стали, и какое количество металлолома следует использовать для приготовления (из соответствующего сплава) литья для одного из своих заказчиков. Пусть производственные затраты в расчете на 1т чистой стали равняются 3 у.е., а затраты в расчете на 1 т металлолома – 5у.е. (последнее число больше предыдущего, т.к. использование металлолома сопряжено с его предварительной очисткой). Заказ предусматривает поставку не менее 5 т литья; при этом заказчик готов купить большее количество литья, если фирма «Иерихонская сталь» поставит перед ним такие условия.
Предположим, что запасы чистой стали, ограничены и не превышают 4 т, а запасы металлолома не превышают 6 т. Отношение веса металлолома к весу чистой стали в процессе получения сплава не должно превышать 7:8. Производственно – технологические условия таковы, что на процессы плавки и литья не может быть отведено более 18 часов, при этом на 1 т стали уходит 3 часа, а на 1 т металлолома – 2 часа производственного времени.
Постройте линейную оптимизационную модель.

Решение.

x1 - чистая сталь, [т], x2 - металлолом, [т]

Ограничения по запасам:
1 ≤ 4
x2 ≤ 6

Ограничения по структуре:
x1 : x2 ≤ 7:8

Ограничения по ресурсам:
3x1 + 2x2 ≤ 18

Ограничения по поставкам:
x1 + x2 ≥ 5

Целевая функция:
3x1 + 5x2 = min

Таким образом, линейная оптимизационная модель имеет вид.
x1 ≤ 4
x2 ≤ 6
8x1 -  7x2 ≤ 0
3x1 + 2x2 ≤ 18
x1 + x2 ≥ 5
x1, x2 ≥ 0

Целевая функция:
3x1 + 5x2 = min