Задачи для решения

4. Найти решение задач методом искусственного базиса.

4.15.

4.16.

4.17.

4.18.

4.19.

4.20.

4.21.

4.22.

1.5. Теория двойственности в линейном программировании

1.5.1. Постановка задачи

Пусть исходная задача линейного программирования записывается в виде:

(1.16)

(1.17)

(1.18)

Двойственная к ней задача будет иметь вид:

(1.19)

(1.20)

(1.21)

В матричной форме формулировка задачи будет следующей.

Для прямой задачи:

(1.16*)

(1.17*)

(1.18*)

Для двойственной –

(1.19*)

(1.20*)

(1.21*)

При записи двойственной задачи действуют следующие правила.

1. Если прямая (исходная) задача решается на максимум (1.16) – (1.18), то двойственная к ней (1.19) – (1.21) – на минимум и наоборот.

2. Коэффициенты целевой функции прямой задачи становятся свободными членами для ограничений двойственной задачи.

3. свободные члены прямой задачи становятся коэффициентами двойственной целевой функции.

4. Матрица ограничений двойственной задачи является транспонированной по отношению к матрице ограничений прямой задачи.

5. Если прямая задача решается на максимум, то её система ограничений имеет в неравенствах знак « » или « = ». Двойственная ей задача решается на минимум, и её система ограничений имеет вид неравенств типа « » или « = ».

6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной – числу переменных прямой.

7. Если прямая задача задана в симметричной форме с n переменными и при приведении её к канонической форме были добавлены ещё m переменных, то между переменными и устанавливается взаимно однозначное соответствие

.

Замечания.

1. Исходной задачей может быть задача на минимум (1.19) – (1.21), тогда двойственная к ней будет задача на максимум (1.16) – (1.18).

2. В теории двойственности исходная задача должна быть упорядоченной. То есть, если целевая функция задачи максимизируется, то ограничения – неравенства должны быть вида « », если минимизируется, то вида « ». Если в некоторых ограничениях это условие не выполняется, то их выполнение достигается умножением соответствующих ограничений на (-1).

3. Если на j – переменную исходной задачи не наложено условие неотрицательности, то j – ограничение будет равенством. В противном случае j – ограничение будет неравенством.

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

Любой исходной задаче линейного программирования можно поставить в соответствие двойственную задачу, построенную по правилам, представленным в таблице 1.24.

Таблица 1.24

	yi ≥ 0
	yi ≤ 0
	yi — не имеет ограничений на знак
xj ≥ 0
xj ≤ 0
xj — не имеет ограничений на знак