Реферат: Решение задачи линейного программирования симплекс-методом

Коэффициенты при в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;

Постоянные ограничений ПЗ становятся коэффициентами целевой функции ДЗ.

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

Прямая задачаДвойственная задача

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

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

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

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

Область допустимых решений ДП () определяется знаками ограничений (8) и (9) двойственной задачи и знаком ограничения (2) прямой задачи. Для определения ОДР найдём ограничения ДЗ, соответствующие остаточным переменным ПЗ. Коэффициенты целевой функции для остаточных переменных равны нулю ().Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак ограничения , соответствуют неотрицательные двойственные переменные: .

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

.

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

.

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

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

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

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

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

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

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

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

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

если , то .

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

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

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

1. Решение задачи линейного программирования графическим методом.