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

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

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

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

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

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

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

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

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

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

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

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

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

Минимизация		Максимизация
=

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

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

если , то .

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

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

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

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

Дана следующая задача линейного программирования (ЗЛП).

1.1. Все ограничения задачи .

1.2. Переменная ограниченна в знаке, поэтому . Переменная не ограничена в знаке, поэтому вводим замену , где .

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

1.3. Построение ограничений и градиента целевой функции :

1.4. Область допустимых решений – отрезок AB.

1.5. Точка А – оптимальная. Координаты т. А:

; ; .

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

Прямая задача.

Задачу линейного программирования для любой вершины в компактной форме можно представить в виде:

Для получения используем алгоритм, приведённый в теоретической части.

1. Переход от неравенств к равенствам по правилам введения дополнительных переменных. Исходную задачу необходимо привести к стандартной форме: введем замену по переменной , и дополнительные переменные:

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

2. Общее число переменных определим по формуле: =3+2+2=7, где - число искусственных переменных. Число базисных переменных определяется числом ограничений, т. к. , то система имеет три базисные переменные и небазисные переменные .

3. Получение - строки для СТ (0). Приведём целевую функцию к виду

Получим из (2): , из (3):

4. Формирование симплекс – таблицы на первом шаге:

Начальный базис

СТ (0) РС

				ПЧ
-1-4M	3+3M	-3M-3	M	-12M
		-2
	-4
		-1	-1

5. Определение разрешающего столбца.

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

6. Определение разрешающей строки: – исключаемая переменная.

7. Разрешающий элемент РЭ = 1.

8. Получение матрицы перехода

, где В(0) - матрица перехода

9. Определение элементов таблицы СТ(1) = В(0) СТ(0);

10. Исследование z-строки СТ(1) на условие оптимальности:

СТ(1)

	z					ПЧ
z		4+7M	-7M-4	-3M-1	1+4M	-12M
			-1		-1
		-7			-3
			-1	-1

СТ(2)

	z					ПЧ
z			5/7	M+4/7	M-5/7	48/7
			10/7	1/7	-10/7	40/7
		-1	3/7	1/7	-3/7	12/7
			-4/7	1/7	4/7	12/7

СТ(2) – оптимальная, т. к. коэффициенты при НБП .

, , .

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

Двойственная задача.

Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:

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

(1)

(2)

Итак, получено: , , .

2. Приведём запись двойственной задачи к канонической форме. На основании полученных ОДР двойственных переменных введём необходимые подстановки: .

Для удобства решения свернём ограничения (1) и (2) в одно со знаком равенства, а также введем в ограничения и целевую функцию избыточные, остаточные и искусственные переменные.