4 Симплекс – метод, переход от графического решения к алгебраическому

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

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

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

В работе Л. В. Канторовича «Математические методы организации и планирования производства» (1939) были впервые изложены принципы новой отрасли математики, которая позднее получила название линейного программирования.

Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджем Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием Project SCOOP. Первое успешное решение задачи линейного программирования на компьютере SEAC было проведено в январе 1952 года.

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый выпуклый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причем их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его ребрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

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

Многогранник симплексного алгоритма в 3D

Переход от одной вершины к другой

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

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

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

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

Общая задача линейного программирования (далее – ЛП) имеет вид:

Каноническая форма задачи ЛП

Каноническая форма задачи ЛП:



Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

1. Неравенства с отрицательными умножаем на (-1).
2. Если неравенство вида (≤), то к левой части добавляем – добавочную переменную, и получаем равенство.
3. Если неравенство вида (≥), то из левой части вычитаем , и получаем равенство.
4. Делаем замену переменных:

• Если , то
• Если — любой, то , где

Замечание: Будем нумеровать по номеру неравенства, в которое мы его добавили.

Замечание: ≥0.

Пример

Ресторан быстрого обслуживания торгует порционными мясными пирогами и чизбургерами. На порцию мясного пирога идет четверть кг мяса, а на чизбургер — только 0.2 кг. В начале рабочего дня в ресторане имеется 200 кг мяса, можно еще прикупить мясо в течение дня, но уже с наценкой в 25 руб. Мясо, оставшееся в конце рабочего дня, жертвуется благотворительной организации. Ресторан имеет доход 20 руб. от одной порции мясного пирога и 15 руб. — от одного чизбургера. Как и многие другие, этот ресторан не может продать в день более 900 бутербродов. Какова должна быть доля каждого из бутербродов (т.е. сколько порций мясного пирога и сколько чизбургеров) в ежедневном производстве ресторана, чтобы максимизировать его доход?

Ограничения. Обозначим x1 и x2 соответственно количество порций пирога и гамбургеров.

Можно ограничиться либо 200 фунтами мяса, либо докупить еще.

В первом случае ограничение 0,25x₁+0,2x₂ ≤ 200, во втором 0,25x₁+0,2x₂ ≥ 200.

Естественно, выбор неравенства будет влиять на решение.

Так как мы не знаем, какое ограничение необходимо, логично заменить их одним равенством 0,25x₁+0,2x₂-x₃=200, где x₃ –свободная переменная.

Здесь она играет роль и избыточной, и остаточной.

Целевая функция. Раз надо максимизировать доход, надо продавать как можно больше продукции, то для этого нужны дополнительные закупки мяса, в этом случае x₃ должна быть отрицательной, т.е. играть роль избыточной переменной. Для того, чтобы раскрыть «двойственную» природу переменной x₃, представим ее в таком виде:

, где 0

Если >0 и , то переменная x₃ играет роль остаточной. Если >0 и =0, то x₃ выступает как избыточная.

Итак ограничения теперь имеет вид

.

А целевая функция

Z=

Открыть на весь экран

Переход от графического решения к алгебраическому.

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

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

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

Пример. Z=2x₁+3x₂ max

2x₁+x₂ 4

x₁+2x₂ 5

x₁,x₂ 0.

После преобразования к стандартной форме имеем следующую задачу ЛП.

Z=2x₁+3x₂ max

2x₁+x₂+S₁ =4,

x₁+2x₂+S₂=5,

x₁, x₂, S₁, S₂ 0.

Имеем систему из m=2 уравнений для n=4 переменных. Как мы договорились, угловые точки можно определить алгебраически, присвоив n=m=4-2=2 переменным нулевые значения, а затем решив систему относительно m=2 переменных. Если положить x₁=0 и x₂=2 (точка C).

Какие же переменные полагать равными нулю, чтобы получить угловые точки? Надо просто рассмотреть все комбинации n-m переменных, приравнять их нулю и найти все угловые точки.

В нашем примере мы имеем угловых точек. На рисунке мы видим только 4. Где же еще две? В действительности точки E и F также являются угловыми точками. Но они еще не кандидаты на оптимальное решение, поскольку не удовлетворяют всем ограничениям.

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

Небазисные (нулевые) переменные	Базисные переменные	Базисные решения	Угловые точки	Допустимо ли решение?	Значение целевой функции Z
(x1, x2)	(S1, S2)	(5, 4)	A	Да	0
(x1, S1)	(x2, S2)	(4, -3)	F	Нет	-
(x1, S2)	(x2, S1)	(2.5, 1.5)	D	Да	7,5
(x2, S1)	(x1, S2)	(2, 3)	B	Да	4
(x2, S2)	(x1, S1)	(5, -6)	E	Нет	-
(S1, S2)	(x1, x2)	(1, 2)	C	Да	8(опт.)

Из этого примера видно, что при возрастании размерности задачи (n и m) процесс перечисления всех угловых точек задача становится очень сложной задачей. Об этом говорит сайт https://intellect.icu . Например, при n=20 и m=10 необходимо решить 184756 систем уравнений порядка 1010. Это уже устрашающая вычислительная задача. Реально же m и n могут достигать сотен тысяч. Эту проблему снимает симплекс метод.

Алгоритм симплекс – метода.

Итак, процедура перебора всех базисных решений неэффективна. Рассмотрим симплекс – метод.

Итерационная природа симплекс – метода.

Рассмотрим пространство решений для того же примера.

Обычно алгоритм симплекс – метода начинается с исходной точки, где x₁=x₂=0 (точка A). В этой начальной точке значение целевой функции Z равно нулю. Возникает вопрос: если одна или обе небазисные переменные x₁ и x₂ примут положительные значения, приведет ли это к улучшению целевой функции?

Z=2x₁+3x₂ max.

Очевидно, что если переменная x₁ и x₂ (или обе сразу ) примут положительные значения, то это приведет к увеличению значения ЦФ.

Однако алгоритм симплекс – метода на каждом шаге допускает изменение значения только одной небазисной переменной.

1. Если увеличивать значение переменной x₁, то ее значение должно возрасти так, чтобы соответствовать угловой точке B (кандидаты – только угловые точки). В точкеB симплекс – метод должен увеличить значение переменной x₂, перемещаясь в угловую точку C. Т.к. точка C соответствует оптимуму, то процесс заканчивается. Т.о. алгоритм симплекс – метода создает путь ABC.

2. Если сначала увеличивать значение переменной x₂, то следующей угловой точкой будет точка D, из которой переходим в точку C и заканчиваем процесс ADC.

Отметим, что оба пути ABC и ADC расположены вдоль границы Г пространства решений. Т.о. симплекс – метод не может сразу перескочить из т.A в т.C.

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

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

На рисунке показано, что в точке А переменные S₁ и S₂ являются базисными, а переменные x₁ и x₂ – небазисными Если переменная x1 принимает положительное значение, мы переходим в угловую точку В, в которой изменяется состояние переменной x₁ из небазисной в базисную. Одновременно переменная, которая была базисной в точке А становится небазисной и принимает нулевое значение в точке В. Здесь существенно, сто происходит одновременный «обмен состояниями» между небазисной переменной x₁ и базисной S₁, что приводит к новым базисным (x₁,S₂) и небазисным (S₁,x₂) переменным в точке В. В точке А переменная x₁ вводится в базисное решение, а переменная S₁ исключается из базисного решения. По терминологии симплекс-метода выбранная небазисная (нулевая) переменная называется вводимой (в базисное решение), а удаляемая (из базисного решения) базисная переменная исключаемой. В т. В вводимой и исключаемой переменными будутсоответственно x₂ и S₂.

Вычислительный алгоритм симплекс-метода.

Рассмотрим следующий пример.

Вернемся к задаче про компанию Reddy Mikks. В стандартной форме эта задача запишется так:

Z=5x₁+4x₂+0S₁+0S₂+0S₃+0S₄ max

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

6x₁+4x₂+S₁=24

x₁+2x₂+S₂=6

-x₁+x₂+S₃=1

x₂+S₄=2

x₁,x₂,S₁,S₂,S₃,S₄0

Здесь S₁,S₂,S₃,S₄ – дополнительные (остаточные) переменные.

Целевую функцию будем представлять в виде уравнения:

Z – 5x₁ – 4x₂ =0

Задачу ЛП в стандартной форме представим в виде таблицы:

Базис	Z	x1	x2	S1	S2	S3	S4	Решение
Z	1	- 5	- 4	0	0	0	0	0	Z-строка
S1	0	6	4	1	0	0	0	24	S1-строка
S2	0	1	2	0	1	0	0	6	S2-строка
S3	0	-1	1	0	0	1	0	1	S3-строка
S4	0	0	1	0	0	0	1	2	S4-строка

Таблица показывает множества базисных и небазисных переменных, а также решение, соответствующее данной (начальной) итерации. Начальная итерация начинается из точки (x₁,x₂)=(0,0). Это соответствует следующим множествам базисных и небазисных переменных:

Небазисные (нулевые): (x₁,x₂)

Базисные: (S₁,S₂,S₃,S₄)

Так как x₁=0 , x₂=0 и коэффициенты при базисных переменных S₁,S₂,S₃,S₄ в уравнении целевой функции равны нулю, а в формулах левых частей равенств ограничений – 1, то без дополнительных вычислений имеем: Z=0, S₁=24, S₂=6, S₃=1, S₄=0.

В таблице базисные переменные перечислены в левом столбце «Базис», а их значения – в правом столбце «Решение». Таким образом, определена текущая угловая точка.

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

Чтобы определить исключаемую переменную, надо вычислить точки пересечения всех функций с положительным направлением оси x₁. Эти координаты можно вычислить как отношения правых частей равенства (столбец «Решение») и коэффициентов при переменной x₁.

Базис	Коэффициенты при x1	Решение	Отношение (точка пересечения)
S1	6	24	x1=24/6=4
S2	1	6	x1=6/1=6
S3	-1	1	x1=1/(-1)=-1 – не подходит
S4	0	2	x1=2/0= – не подходит

Максимальное неотрицательное соотношение соответствует базисной переменной S₂, она определяется как исключаемая (т.е. на следующей итерации ее значение будет равно нулю). Значение вводимой переменной x₁ также равно минимальному неотрицательному отношению: x₁=6

Максимизировать

Z=5x₁+4x₂

1) 6x₁+4x₂+S₁=24

2) x₁+2x₂+S₂=6

3) -x₁+x₂+S₃=1

4) x₂+S₄=2

x₁,x₂ 0

Значение целевой функции при этом возрастет до 54=20.

Замена исключаемой переменной S₁ на вводимую переменную x₁ приводит к новым множествам базисных и небазисных переменных и к новому решению в т.В.

Небазисные (нулевые) переменные (S₁,x₂)

Базисные переменные (x₁,S₂,S₃,S₄)

Теперь надо выполнить преобразование в таблице, чтобы в столбцах «Базис» и «Решение» получить новое решение, соответствующее точке В.

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

Базис	Z	x1	x2	S1	S2	S3	S4	Решение
Z	1	- 5	- 4	0	0	0	0	0
S1	0	6	4	1	0	0	0	24	Ведущая строка
S2	0	1	2	0	1	0	0	6
S3	0	-1	1	0	0	1	0	1
S4	0	0	1	0	0	0	1	2

Ведущий столбец

Процесс вычисления нового базисного решения состоит из двух этапов:

1. Вычисление элементов новой ведущей строки.

Новая ВС = Текущая ВС / Ведущий элемент

2. Вычисление элементов остальных строк, включая Z-строку.

Новая строка = Текущая строка – ее коэффициент в ведущем столбце Новая ВС

В примере вычисления таковы:

1. Новая ведущая S₁-строка = Текущая ведущая S₁-строка / 6

2. Новая Z-строка = Текущая Z-строка – (-5) Новая ВС

3. Новая S₂-строка = Текущая S₂-строка – (1) Новая ВС

4. Новая S₃-строка = Текущая S₃-строка – (-1) Новая ВС

5. Новая S₄-строка = Текущая S₄-строка – (0) Новая ВС

Базис	Z	x1	x2	S1	S2	S3	S4	Решение
Z	1	0	0	3/4	1/2	0	0	21
x1	0	1	0	1/4	-1/2	0	0	3
x2	0	0	1	-1/8	3/4	0	0	3/2
S3	0	0	0	3/8	-5/4	1	0	5/2
S4	0	0	0	1/8	-3/4	0	1	1/2

Так как Z-строка не имеет отрицательных коэффициентов, соответствующих небазисным переменным S₁ и S₂, полученное решение оптимально.

Значения дополнительных переменных S₁=S₂=0, S₃=5/2 и S₄=1/2 согласуются со значениями переменных x₁ и x₂.

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

Ресурс	Остаточная переменная	Статус
Сырье М1	S1=0	Дефицитный
Сырье М2	S2=0	Дефицитный

Рассмотрим следующую задачу линейного программирования:

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

Здесь x — переменные из исходного линейного функционала, xs — новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство, c — коэффициенты исходного линейного функционала, Z — переменная, которую необходимо максимизировать. Полупространства x⩾0 и xs⩾0 в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений дает нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число ребер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «небазисными». Остальные переменные при этом будут вычисляться однозначно и называться «базисными». Сам же набор этих переменных называется базисом. Полученная точка будет вершиной в пересечении соответствующих небазисным переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнем движение), присвоим всем изначальным переменным x значение 0 и будем их считать небазисными, а все новые будем считать базисными. При этом начальное допустимое решение вычисляется однозначно : .

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

где cB — коэффициенты вектора c, соответствующие базисным переменным (переменным xs соответствуют 0), B — столбцы [AE], соответствующие базисным переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг.

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

Второй шаг

Покажем, что в выражении только небазисные переменные имеют ненулевой коэффициент. Заметим, что из выражения базисные переменные однозначно выражаются через небазисные, так как число базисных переменных равно числу уравнений. Пусть x′ — базисные, а x″ — небазисные переменные на данной итерации. Уравнение можно переписать, как . Умножим его на слева:. Таким образом мы выразили базисные переменные через небазисные, и в выражении , эквивалентному левой части равенства, все базисные переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству равенство , то в полученном равенстве все базисные переменные будут иметь нулевой коэффициент — все базисные переменные вида x сократятся, а базисные переменные вида xs не войдут в выражение .

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

.

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

Третий шаг

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

При фиксированных значениях небазисных переменных система однозначно разрешима относительно базисных, поэтому мы можем определить, какая из базисных переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами — входящая «войдет» в базисную, а выходящая из них «выйдет» в небазисные. Теперь перепишем матрицу B и вектор cB в соответствии с новыми наборами базисных и небазисных переменных, после чего вернемся ко второму шагу. x''

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

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

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

Все ограничения задачи модифицируются согласно следующим правилам:

• ограничения типа «≤» переводятся на равенства созданием дополнительной переменной с коэффициентом «+1». Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис.
• ограничения типа «≥» дополняются одной переменной с коэффициентом «−1». Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать еще одну, вспомогательную, переменную. Вспомогательные переменные всегда создаются с коэффициентом «+1».
• ограничения типа «=» дополняются одной вспомогательной переменной.

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

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

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

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

То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

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

.

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

Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:

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

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

В модифицированном методе матрица

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

1. Вычисляем двойственные переменные

2. Проверка оптимальности. преобразуется в .

Проверка заключается в вычислении для всех столбцов n∈N. Столбец со значением < 0 можно вводить в базис.

Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.

Чаще выбирают значение, меньшее некоторого заданного значения

Если такого столбца не обнаружится, за ε принимается максимальное найденное абсолютное значение и соответствующий столбец AJ вводится в базис.

3. Определение выводимого.

Пусть — вводимый столбец, соответствующий переменной Базисный план — это решение системы Увеличиваем.

Умножим слева на, то есть .

Здесь — базисный план, q=B−1AJ — разложение вводимого столбца по базису.

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

4. Пересчет опорного(базисного) плана.

Вычисляем новый опорный план по уже приведенной формуле с найденным значением ϑ.

5. Пересчитываем обратную к базисной .

Пусть — выводимый столбец.

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

где — базисная матрица без выводимого столбца.

После замены столбца базисная матрица будет иметь вид

Нам нужно найти матрицу B1, такую что

=> => =>

Откуда

Замечание.

При пересчете матрицы накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется «повторением».

В мультипликативном варианте матрица не хранится, хранятся лишь множители

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

Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.

При подавляющем числе ограничений типа «неравенство» может быть использован метод переменного базиса.

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

Обратная к ней имеет вид

При относительно небольших размерах матрицы остальная часть матрицы может не храниться.

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

Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:

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

.

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

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

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

Наблюдения и анализ эффективности метода в практических приложениях привело к развитию других способов измерения эффективности.

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

Вычислительная эффективность оценивается обычно при помощи двух параметров:

• числа итераций, необходимого для получения решения;
• затрат машинного времени.

В результате численных экспериментов получены следующие результаты.

1. Число итераций при решении задач линейного программирования в стандартной форме с m ограничениями и n переменными заключено между m и 3m. Среднее число итераций 2m. Верхняя граница числа итераций равна 2m+n.
2. Требуемое машинное время пропорционально .

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

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

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

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

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

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

Назначение весов. Переменным назначаются веса. См. раздел 3.6.4 Метод оценивания в системе DEVEX Муртафа.

Поиск наиболее крутого ребра Гольдфарба и Рида. См. раздел 3.6.5 Метод оценивания с поиском наиболее крутого ребра в книге Муртафа.

Возможны и другие приемы, такие как правило Заде.

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