Вопросы для самоконтроля по теме 3

1. Каким образом построить ОДЗ при решении задачи линейного программирования графическим методом?

2. Что такое градиент?

3. Что такое изоцель?

4. Как найти угловую точку, дающую наилучшее значение целевой функции при решении задачи графическим методом?

5. Что такое связующее ограничение?

6. Каким может быть ОДЗ задачи линейного программирования?

7. Что такое альтернативный оптимум?

8. Какие переменные называются базисными (небазисными)?

9. Как выбрать базисные переменные?

10. Каков алгоритм симплекс-метода?

11. Что такое стандартная форма задачи линейного программирования?

12. Как заполняется симплекс-таблица?

13. Каков критерий определения оптимальности текущего базисного решения?

14. Как определить, какая переменная войдет в базис?

15. Как определить, какая переменная покинет базис?

16. Как рассчитать новое базисное решение методом Жордана-Гаусса?

17. Что такое теневая цена? Как ее узнать?

18. Какие задачи приходится решать методом искусственного базиса?

19. Каким образом формируется целевая функция в М-задаче?

20. Как определить наличие альтернативного оптимума при решении задачи симплекс-методом?

21. Как определить, что решение задачи линейного программирования неограниченно?

22. Как определить, что задача линейного программирования не имеет решений?

Тема 4 теория двойственности и анализ линейных моделей оптимизационных задач

4.1. Понятие и экономический смысл двойственной задачи

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

Сформулируем постановку двойственной задачи для задачи о мебельной фабрике из примера 3.2. Пусть некая фирма решила выкупить все ресурсы мебельной фабрики, и она хочет узнать, по какой минимальной цене это сделать. Переменные y₁, y₂, y₃, y₄ – обозначают, соответственно, цены на каждый из четырех ресурсов (древесину, время на участке отделке, столярном участке и «квоты» на продажу столов). Цены же, очевидно, не должны быть ниже, чем стоимость продукции, которую из этих ресурсов мебельная фабрика могла бы произвести. Таким образом, целевая функция двойственной задачи будет минимизировать стоимость всех выкупаемых ресурсов, а ограничения отражают тот факт, что стоимость ресурсов, взятых в определенных пропорциях, должна дать цену не меньше стоимости соответствующей продукции мебельной фабрики.

Поставленную задачу можно записать в следующем виде (табл. 4.1).

Таблица 4.1 – Постановка двойственной задачи к примеру 3.2

Прямая задача: (8)

Двойственная задача: (9)

Сформулируем основные правила построения двойственной задачи.

1. Критерий оптимальности у двойственной задачи меняется на противоположный.

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

3. Коэффициенты ЦФ прямой задачи становятся правыми частями ограничений двойственной и, наоборот, правые части ограничений прямой задачи становятся коэффициентами ЦФ двойственной.

4. Матрицей коэффициентов при переменных в ограничениях двойственной задачи является транспонированная матрица этих коэффициентов прямой задачи.

5. Ограничения на знак переменных двойственной задачи связаны с типом соответствующего ограничения прямой задачи, а тип ограничений двойственной задачи связан с ограничением на знак соответствующей переменной прямой задачи. Эта связь выглядит следующим образом (табл. 4.2).

Таблица 4.2 – Связь типа ограничения с ограничением на знак переменной у прямой и двойственной задачи

Прямая	Двойственная	Прямая	Двойственная
max z(x) …  bi … = bi …  bi xi  0 xi неогр. на знак xi  0	min w(y) yi  0 yi неогр. на знак yi  0 …  ci … = ci …  ci	min z(x) …  bi … = bi …  bi xi  0 xi неогр. на знак xi  0	max w(y) yi  0 yi неогр. на знак yi  0 …  ci … = ci …  ci

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

Ограничения типа  для задачи на максимум и типа  для задачи на минимум называются нормальными.

Поэтому вместо таблицы 4.2, достаточно использовать правило: для нормальных ограничений – двойственные переменные будут неотрицательными; если переменные прямой задачи неотрицательны – двойственные ограничения будут нормальны.

Пример 4.1. Составим двойственную задачу к следующей:

Двойственная задача будет иметь 4 переменных (по числу ограничений прямой) с коэффициентами в ЦФ: 5, 6, 4, 5. У двойственной задачи будет три ограничения (по числу переменных прямой задачи) с правыми частями равными: –1, 3, 1. Переменные y₁ и y₃ не будут иметь ограничений на знак (так как в 1 и 3 ограничении знак =), переменная y₂ будет неотрицательной (так как второе ограничение правильное), а переменная y₄ будет неположительной (так как четвертое ограничение неправильное – ≥ у задачи на max).

Аналогично первое ограничение двойственной задачи будет иметь знак = (поскольку x₁ не имеет ограничений на знак), второе – ≤ (будет неправильным, поскольку ), третье – ≥ (будет правильным, поскольку ). Получили двойственную задачу:

Решения прямой и двойственной задачи взаимосвязаны.

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

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

коэффициенту при S_i, если i­-е ограничение прямой задачи типа  ;

коэффициенту при e_i · (–1), или коэффициенту при a_i в первой индексной строке, если i­-е ограничение прямой задачи типа  ;

коэффициенту при a_i в первой индексной строке, если i­-е ограничение типа = .

Решение двойственной задачи отражает теневые цены (двойственные оценки) ограничений, которые для связующих ограничений (критических ресурсов) отличны от нуля.

Напомним еще раз, что теневая цена отражает величину на которую изменится ЦФ при изменении правой части ограничения на 1 единицу;

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

При решении прямой задачи на максимум симплекс-методом, строка целевой функции отражает значение переменных двойственной задачи, а столбец b_j по сути является строкой ЦФ для двойственной задачи. При решении задачи на минимум, строка целевой функции отражает значение переменных двойственной задачи, взятых со знаком «–».

Рассмотрим последнюю симплекс-таблицу решения задачи (табл. 3.4) о мебельной фабрике (8) и найдем соответствующее решение двойственной задачи (9).

Базис	cj		х1	х2	х3	S1	S2	S3	S4
			60	30	20	0	0	0	0
1) S1	0	24	0	-2	0	1	2	-8	0
2) х3	20	8	0	-2	1	0	2	-4	0
3) х1	60	2	1	5/4	0	0	-1/2	3/2	0
4) S4	0	5	0	1	0	0	0	0	1
		280	0	5	0	0	10	10	0

Получим: y₁ = y₄ = 0, y₂ = y₃ = 10, e₁ = e₃ = 0, e₂ = 5, Z = 280.