Теория симплекс метода и его приложения

Общая задача линейного программирования состоит в том, чтобы найти неотрицательное значение n при переменных xi удовлетворяющих m линейным ограничениям вида Ранг матрицы r(A) - это максимальное число линейно независимых строк или столбцов матрицы А.  Расширенная матрица системы А*х=b это A_b=(A,b). Система уравнений называют однородной, если вектор b = 0.  Решение x = 0 всегда является решением системы уравнений A*x=0, такое решение называется тривиальным.  Для того, чтобы существовали нетривиальные решения системы, необходимо и достаточно, чтобы r(A)b)=m. Из матрицы А выберем подматрицу порядка m и обозначим ее через В. Пусть X_r - это вектор, который содержит все остальные переменные. X_b - это вектор, который содержит все переменные, входящие в матрицу В, т.е. соответствуют столбцам матрицы В. Через X_r - это все оставшиеся переменные, а через R обозначим матрицу состоящую из столбцов матрицы А соответствующих переменным X_r. Тогда для произвольного вектора X_r решение системы можно получить, если считать X_b=B^-1*b-B^-1*R*X_r, решения, когда X_r=0, а X_b=B^-1*b наз базисным решением. Базисное решение содержит не более m отличных от 0 переменных. Переменные, вошедшие в вектор X_bназываются базисными переменными, остальные называются небазисными. Базисное решение называется вырожденным, если одна или более базисных переменных =0. Максимальное кол-во базисных решений для системы A*x=b равно  что соответствует числу различных комбинаций из m столбцов матрицы А, которые могут быть выбраны для получения матрицы В. Для некоторых таких комбинаций базисное решение может не существовать, т.к. входящие в данную комбинацию векторы могут оказаться линейно независимыми. Предположим, что все ограничения перенумеруем, что первыми записаны ограничения со знаком ≤, вторые со ≤ и третьими со знаком =.  - Если ограничения имеют знак ≤, то вводим вспомогательную (дополнительную) переменную X_n+i, полагая, что  Для любых переменных X_j (j от 1 до n), удовлетворяющих исходному ограничению X_n+i≥0.  - Если i-ое ограничение имеет знак ≥ то необходимо ввести новую вспомогательную (избыточную) переменную X_n+i следующим образом. Для любых X_j, удовлетворяющих ограничениям. В результате проделанных операций от исходных ограничений мы переходим к системе из m линейных уравнений с N неизвестными вида A*x=b, при этом n ≤N ≤n+m.  Число вновь введенных переменных равно N-n, при этом столбцы А называются производственными векторами. Произвенный вектор соответствующий вспомогательной переменной равен, либо единичному вектору, либо единичному вектору, умноженному на (-1).  Между неотрицательными векторами, соответствующими исходным ограничениям и решениям системы A*x=b существует взаимнооднозначное соответствие. Таким образом добавлением вспомогательных переменных любую задачу линейного программирования можно свести к эквивалентной задаче вида: найти max или min целевой функции y=c*x, где c=(c1,…cn) при условиях A*x=b, x≥0. Любое число переменных в задаче линейного программирования принято обозначать через n. Любой вектор Х удовлетворяющий условиям A*x=b и x≥0 называют допустимым решением.  Пусть исходная задача приведена к стандартному виду. Тогда:  а) если задача имеет оптимальное решение, то существует по крайней мере 1 базовое оптимальное решение.  б) если имеется допустимое базовое решение, но не оптимальное решение, то через конечное число шагов от этого решения можно перейти к базовому оптимальному решению или установить, что целевая функция (ЦФ) неограничена на множестве всех допустимых решений. При этом на каждом шаге выполняется замена только 1 базисной переменной. Предположим, что ранг матрицы A равен рангу рассматриваемой матрицы и равен m. Пусть В - это матрица, состоящая из m линейнонезависимых столбцов матрицы А. Соответствующие и базисные, необязательно оптимальные решения могут быть записаны  все небазисные переменные равны 0. Значение целевой функкции: Пусть Pj - некоторый произвольный вектор. Найдём вектор  y_j - это вектор, который содержит соответствующие коэффициенты матрицы ограничений после того как все базисные переменные выражены через небазисные.  y_j - меняется на каждой итерации.  c_j - коэффициенты целевой функции, соответствующие i-ой переменной или произвольному вектору P_j . Теперь предположим, что мы имеем базисное допустимое решение X_b, имеем y_j, Y_j, вычисленных для всех произвольным вектором P_j.  Тогда существуют возможности:  а) разность Y_j - c_j ≥0, (j от 1до n). В этом случае базисное допустимое решение оптимально. б) Y_j-c_j<0, y_ij ≤0, (i от 1 до m). Целевая функция не ограничена, оптимального решения получить нельзя. с) Y_j-c_j<0, и для каждого такого j по крайней мере 1 значение y_ij>0, (i от 1 до m) существует другое базисное допустимое решение, которой соответствует значение ЦФ не меньше, чем значение ЦФ для исходного решения. Если исхоноеое решение не вырожденное, то значение ЦФ можно увеличить заменив в матрице В один вектор. Симплекс метод исходит из допустимого базисного решения и на каждой итерации производит замену одного вектора в базисе.  Правило замены векторов в базисе:  1) Определение вектора вводимого в базис, так называемое условие оптимальности. Для небазовых переменных вычисляем разность Y_j-C_k=min_j(Y_j-c_j), Y_j - c_j<0. Это означает выбор максимального коэффициента в строке y. Вектор P_к соответствующий этому минимуму на следующей итерации вводится в базис. Если вычисляемый минимум достигается при нескольких векторах, то в базис вводится вектор с наименьшим индексом j.  2) Определение вектора исключенного из базиса, так называемое условие допустимости. Вычислеям отношение: Из базиса исключаетсяся r-й столбец матрицы В и заменяется вектором P_к. В случае неоднозначности выбирается вектор, для которого y_ik имеет наименьшее значение. Если и этим однозначность не исключается, то среди оставшихся векторов выбираем вектор с наименьшим индексом i. Новые значения обозозначим так: Пусть X_B=y₀; Y_j - c_j=y_n+1; Y=y_n+1,0. Тогда  Рассмотрим задачу нахождения исходногого базисного решения: Если матица А содержит в качестве подматрицы единичную матрицу. Тогда базовое допустимое решение получается легко: Если единичная матрица не содержится в матрице А, то присоединим к матрице А такую подматрицу (единичную).  Дополнительные векторы называют исскуственными векторами, а соответствующие переменные - исскуственными переменними. Обозначим эти пременные X_ai.  После этого решения можно осуществлять двумя путями:  а) образование искуственной целевой функции и решение задачи в 2 этапа.  б) использование метода введения штрафов (М-метода).  Для получения допустимого решения исходной задачи значение искуственных переменных нужно уменьшить до 0. Для этого коэффициенты ЦФ соответствующие искуственным переменным полагают = “-М”, где М-это большое по значению положительное число. При ручном счёте конкретное значение М не задаётся. Если исходная задача имеет допустимое решение, то значение искуственных пременных могут быть сделаны равными 0. Если матрица А не содержит ни одного единичного вектора, то вводят искуственные переменные и решают следующую задачу линейного программирования. X_a - вектор столбец вида X_a=[X_a1…X_an], I - вектор строка = (1,1…1).  Начальные базисные допустимые решения для задачи: Если матрица А содержит единичный вектор e_k, то искуственный вектор e_k вводить не нужно.  Общий вид симплекс таблицы: 

БП	СB	b	P1	…	Pn
XB1	СB1	XB1=y0	y11	…	y1n
…	...	…	…	…	…
XBm	СBm	XBm=ym0	ym1	…	ymn
		Y= ym+1,0	Y1-C1= ym+1,1		Yn-Cn= ym+1,n

Имеется ряд упрощенных вариантов реализации симплекс метода на ЭВМ. Наиболее распранен метод на правиле выбора переменной вводимой в базис. В общем случае из теории симплекс метода следует, что оптимальное решение задачи линейного программирования всегда соответствует некоторому допустимому базисному решению.  Однако в 2-х случаях это правило не выполняется:  1) если линия постоянных значений целевой функции при оптимальном решении оказывается параллельной линии одного из ограничений , то существует бесконечное множество альтернативных оптимальных решений. При реализации симплекс метода эта ситуация соотвует случаю, когда все разности Y_j - c_j для всех небазисных X_j удовлетворяет условию оптимальности, и по крайней мере 1 разность Y_j - c_j=0. Если вектор связанный с этой разностью можно включить в базис, то существует альтернативное базисное оптимальное решение. 2) Для этого случая характерна ситуация, при которой условие оптимальности показывает, что некоторый базис, будучи введенный в базис улучшит решение, однако, такой вектор сделать базисным нельзя, т. е. если  то P_j не может дать допустимое базисное решение. Такое решение называют,неограниченным. Поскольку переменная X_j ассоциирует с произвольным вектором P_jможно увеличивать неограниченно, не влияя на допустимость решения. Хотя теоретическая основа симплекс метода гарантирует сходимость к оптимальному решению за конечное число шагов, в этом методе не учитывается сложности вычислительного характера, связанные с ошибками округления. Во многом такие ошибки затрудняют применение М-метода (штрафы), поскольку использование «больших штрафов» связано с необходимостью сравнения очень больших и относительно малых чисел. Указанная опасность снижается при разбиении всего процесса задачи на 2 этапа. Возможность ошибки в округлении не исчезает и при фазовом решении задачи, это связано с тем, что преобразование симплекс таблицы на каждой итерации, основанной на методе исключения переменных Гаусса-Жордана, что приводит к накоплению и распространению ошибок округления в такой степени, что они искажают исходные данные задачи.  Пример с определением условия допуст-ти:  Пусть (X_B )_i =0, а  (B^-1*P_j)_i =0 - это соотв-ий i-ый коэф-т огран-я, кот. ассоц. с вводимым вектором P_j. Предположим, что в результате ошибок окр-ия мы получим (X_B )_i =10_-9, а (B^-1*P_j)_i =10^-6, теперь вектор P_j в решении м. вводить и возникает неверное решение.  С целью уменьшения ошибок окр-ия был разработан модифицированный симплекс метод. Основные шаги этого метода такие же, что и для симплекс метода, отличие - при получении последовательных таблиц на каждой итерации не используется метод Гаусса-Жордана. Основные вычисления связаны с обращением базиса B^-1. Следовательно, в вычислительных процедурах стараются минимизировать ошибки округления, в основном для матрицы B^-1. Помимо контроля за ошибкой округления модифицированный симплекс метод позволяет так же уменьшить и время расчета, при этом время вычислени для модифицированного симплекс метода тем меньше, чем меньше плотность матрицы А (т.е. это отношение числа ненулевых элементов к общему числу элементов) и чем меньше отношение числа ограничений к числу переменных.