Переход от неравенств к равенствам с учётом правил перехода - введение остаточных, избыточных, искусственных переменных и коэффициентов штрафа;

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) прямой задачи. Для определения ОДР  найдём ограничения ДЗ, соответствующие остаточным переменным ПЗ. Коэффициенты целевой функции для остаточных переменных равны нулю ().Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак ограничения , соответствуют неотрицательные двойственные переменные: .

2. Рассмотрим ограничение (3) прямой задачи:

.

При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:

.

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

3. Рассмотрим ограничение (4) прямой задачи:

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

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

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

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

Прямая задача		Двойственная задача
Целевая функция	Ограничения	Целевая функция	Ограничения	Переменные
Максимизация		Минимизация
	=
Минимизация		Максимизация
	=

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

если переменная  не ограничена в знаке, то ;

если , то .

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

После приведения ДЗ к стандартному виду используется симплекс - метод. Алгоритм получения решения тот же, что и для прямой задачи.

II. Практическая часть