Решение задачи линейного программирования симплекс-методом (стр. 3 из 6)
Исключаемой переменой будет та базисная переменная, которая первой обратится в "0" при переходе в смежную вершину после ввода включаемой переменной.
Столбец включаемой переменной будем называть разрешающим столцом.
Строку исключаемой переменной будем называть разрешающей строкой.
Пересечение разрешающего столбца и строки определяют разрешающий элемент (РЭ).
Чтобы определить исключаемую переменную необходимо:
разделить правые части всех базисных переменных (кроме
- строки) на соответствующие положительные коэффициенты разрешающего столбца;выбрать из полученных отношений наименьшее.
Делить на "0" и отрицательную величину нельзя, т. к. это приводит к отсутствию пересекающейся вершины или к вершине вне ОДР.
Для перехода в смежную вершину необходимо сформировать матрицу перехода B(0), которая определит связь между СТ(0) и СТ(1): СТ(1) = В(0) СТ(0).
Для произвольной квадратной матрице размерности n, имеющей в качестве (n - 1) столбца единичные орты, расположенные в соответствии с единичными ортами единичной матрицы, и одного произвольного столбца с ненулевым элементом на главной диагонали, обратная матрица находится по следующему правилу:
Каждый элемент j – столбца делится на РЭ и меняет знак на противоположный, кроме разрешающего элемента.
Искусственный начальный базис. М – метод.
Если исходное ограничение записано в виде равенства "=" или имеет знак "
", то нельзя сразу получить допустимое начальное базисное решение, т. к. при записи задачи в стандартной форме, после введения дополнительных переменных может получиться вариант, когда полученные уравнения не позволяют сформировать начальный допустимый базис в виде единичных орт.В этом случае для нахождения начального допустимого базиса вводятся дополнительно искусственные переменные
. Искусственные переменные не имеют отношения к содержанию поставленной задачи, их введение допустимо только в том случае, если соответствующая схема вычислений будет обеспечивать получение оптимального решения, в котором все искусственные переменные окажутся равными нулю.Переменные R определяют начальный допустимый базис с точки зрения возможного дальнейшего перехода в одну из вершин ОДР. За использование искусственных переменных в целевой функции вводится штраф М. В задаче максимизации М отрицательное (М<<0), в задаче минимизации М положительное (М>>0).
Свойство М: При сложении (вычитании) с любой конечной величиной
, определяющей любое значение, которое может принимать каждая из переменных исходной ЗЛП, её значение (переменной М) не меняется, а именно, 
При составлении начальной симплекс-таблицы все переменные начального допустимого базиса (дополнительные и искусственные) должны располагаться в последних m столбцах перед правой частью.
Алгоритм получения оптимального решения:
1. Переход от неравенств к равенствам с учётом правил перехода - введение остаточных, избыточных, искусственных переменных и коэффициентов штрафа;
2. Определение числа базисных и небазисных переменных;
3. Получение
- строки для заполнения СТ(0. Для этого необходимо целевую функцию преобразовать к виду 
; для чего из соответствующих равенств ограничений выразить искусственные переменные 
и подставить в строку и привести к рациональному виду;4. Заполнение СТ(0). Перенесение коэффициентов
- строки и равенств ограничений в соответствующие строки и столбцы симплекс-таблицы;5. Исследование
функции на условие оптимальности:определение разрешающего столбца (по знаку и величине коэффициентов небазисных переменных
- строки);определение включаемой переменной из небазисных переменных;
6. Определение разрешающей строки по условию допустимости:
определение минимального отношения при делении правых частей ограничений на положительные коэффициенты разрешающего столбца;
определение исключаемой переменной из начального базиса;
7. Определение разрешающего элемента РЭ;
8. Получение B (0). Замена в матрице начального базиса коэффициентов исключаемой переменной на коэффициенты включаемой переменной; вычисление B (0) по соответствующему правилу;
9. Определение элементов СТ(1) = В(0) СТ(0);
10. Исследование
-строки СТ(1) на условие оптимальности.Если условие не выполнено, то вычисления продолжаются и необходимо повторить пункты 5-10.
Если условие оптимальности выполнено, то решение ЗЛП симплекс-методом закончено, необходимо выделить оптимальные значения переменных и оптимальное значение целевой функции.
Решение задачи линейного программирования симплекс-методом.
Двойственная задача.
Двойственная задача (ДЗ) – это вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными, чем при ПЗ. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. Для перехода к ДЗ необходимо, чтобы прямая задача была записана в стандартной канонической форме. При представлении ПЗ в стандартной форме в состав переменных
включаются также избыточные и остаточные переменные.Двойственная задача имеет:
m переменных, соответствующих числу ограничений прямой задачи;
n ограничений, соответствующих числу переменных прямой задачи.
Двойственная задача получается путём симметричного структурного преобразования условий прямой задачи по следующим правилам:
Каждому ограничению
ПЗ соответствует переменная 
ДЗ;Каждой переменной
ПЗ соответствует ограничение 
ДЗ;Коэффициенты при
в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ;Коэффициенты
при в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;Постоянные ограничений
ПЗ становятся коэффициентами целевой функции ДЗ.Рассмотрим правила составления двойственной задачи:
Прямая задачаДвойственная задача
Остановимся более подробно на определении областей допустимых решений двойственных переменных при переходе от прямой задачи к двойственной.
Области допустимых решений для двойственных переменных
Вид ограничений прямой задачи, а также дополнительные и искусственные переменные, образующие начальный допустимый базис, определяют ОДР для соответствующих двойственных переменных.
1. Рассмотрим ограничение (2) прямой задачи:
Область допустимых решений ДП ( ) определяется знаками ограничений (8) и (9) двойственной задачи и знаком ограничения (2) прямой задачи. Для определения ОДР найдём ограничения ДЗ, соответствующие остаточным переменным ПЗ. Коэффициенты целевой функции для остаточных переменных равны нулю ( 
).Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак ограничения 
, соответствуют неотрицательные двойственные переменные: 
.