Оптимальными «теневыми» ценами естественно считать такие, которые минимизируют общую стоимость ресурсов

.

Запишем обе задачи в матричном виде:

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

Ах А^Тy C

F = C^Tx Z =

x 0 y 0

Эти задачи называют парой двойственных задач. Пара двойственных задач может быть экономически интерпретирована следующим образом.

Прямая задача: Сколько и какой продукции x_j необходимо производить, чтобы при

заданных стоимостях C_j и размерах ресурсов b_i максимизировать выпуск

продукции в стоимостном выражении?

Двойственная задача: Какова должна быть цена каждого ресурса y_i, чтобы при заданных

количествах b_i и стоимостях C_j минимизировать затраты?

1. Правила построения двойственной задачи.

Исходя из общего вида прямой и двойственной задач можно установить связь между этими задачами, позволяющую для любой ЗЛП строить двойственную ей задачу.

Свойства двойственных задач (правила).

1. Число неизвестных двойственной задачи равно числу ограничений прямой задачи. Число ограничений двойственной задачи равно числу неизвестных прямой задачи.
2. Матрица коэффициентов двойственной задачи является транспонированной матрицей коэффициентов прямой задачи.
3. Коэффициенты целевой функции двойственной задачи являются свободными членами ограничений прямой задачи.
4. Свободные члены ограничений двойственной задачи являются коэффициентами целевой функции прямой задачи.
5. Если ограничения прямой задачи записаны со знаком меньше или равно (), то ограничения двойственной задачи записываются со знаком больше или равно ().
6. Если ограничение прямой задачи задано в виде уравнения, то соответствующее неизвестное двойственной задачи не ограничено знаком.
7. Если какое-либо неизвестное прямой задачи не ограничено знаком, то соответствующее ограничение двойственной задачи будет задано в виде равенства.
8. Если целевая функция прямой задачи сформулирована на максимум, то целевая функция двойственной задачи будет сформулирована на минимум.

Существует много различных комбинаций ограничений и целевой функции для записи исходной задачи. Для упрощения задачи построения двойственной задачи запишем прямую задачу в некотором стандартном виде прямой задачи. Этот вид предполагает, что:

1) все ограничения имеют знак ;

2) целевая функция сформулирована на максимум;

3) все неизвестные неотрицательны.

Чтобы записать прямую задачу в стандартном виде, необходимо:

1) неравенство со знаком умножить на (-1);

2) равенство заменить на два неравенства противоположных знаков, одно из которых следует умножить на (-1);

3) формулировку целевой функции меняют заменой знаков коэффициентов на противоположные;

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

Пример. Составить двойственную задачу к исходной.

.

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

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

Задачу можно записать в виде, соответствующем исходной прямой задаче,

если заменить: а) - не ограничена знаком,

б) два последних ограничения соответствуют равенству.

.

1. Основные теоремы двойственности и их экономическое содержание.

Теорема 1. Двойственная задача к двойственной есть прямая задача.

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

Ах А^Тy C

F = C^Tx Z =

x 0 y 0

Построим к двойственной задаче двойственную:

1) запишем в стандартном виде -А^Тy -C

Z = -

2) -АхАх

F = - C^Tx F = C^Tx

Что и требовалось доказать.

Дата добавления: 2014-01-13