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

1. Целевая функция исходной задачи (4.1) – (4.3) задается на максимум, а целевая функция двойственной (4.4) – (4.6) – на минимум.

2. Матрица:

, (4.7)

составленная из коэффициентов при неизвестных в системе ограничений (4.2) исходной задачи (4.1) – (4.3), и аналогичная матрица:

(4.8)

в двойственной задаче (4.4) – (4.6) получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов – строками).

3. Число переменных в двойственной задаче (4.4) – (4.6) равно числу ограничений в системе (4.2) исходной задачи (4.1) – (4.3), а число ограничений в системе (4.5) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (4.4) двойственной задачи (4.4) – (4.6) являются свободные члены в системе (4.2) исходной задачи (4.1) – (4.3), а правыми частями в соотношениях системы (4.5) двойственной задачи – коэффициенты при неизвестных в целевой функции (4.1) исходной задачи.

5. Если переменная x_j исходной задачи (4.1) – (4.3) может принимать только лишь положительные значения, то j–е условие в системе (4.5) двойственной задачи (4.4) – (4.6) является неравенством вида “ ”. Если же переменная x_j может принимать как положительные, так и отрицательные значения, то j – соотношение в системе двойственной задачи представляет собой уравнение. Аналогичные связи имеют место между ограничениями (4.2) исходной задачи (4.1) – (4.3) и переменными двойственной задачи (4.4) – (4.6). Если i – соотношение в системе (4.2) исходной задачи является неравенством, то i–я переменная двойственной задачи . В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (4.2) прямой задачи и соотношения (4.5) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Для практических целей рассмотренные правила позволяют составить следующую схему соответствия.

 

 

Таблица 4.1. – Таблица соответствия

Исходная задача	Двойственная задача
Целевая функция максимизируется	Целевая функция минимизируется
Константы в правых частях ограничений	Коэффициенты целевой функции
Коэффициенты целевой функции	Константы в правых частях ограничений
j-й столбец коэффициентов в ограничениях	j-я строка коэффициентов в ограничениях
j-я строка коэффициентов в ограничениях	j-й столбец коэффициентов в ограничениях
j-я неотрицательная переменная	j-е неравенство вида ≥
j-я переменная, не имеющая ограничений в знаке	j-е соотношение в виде =
i-е неравенство вида ≤	i-я неотрицательная переменная
i-е соотношение в виде =	i-я переменная, не имеющая ограничений в знаке

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

Пример №4.1.

Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции

(1)

при условиях

(2)

(3)

Решение.

Для данной задачи

и .

Число переменных в двойственной задаче равно числу уравнений в системе (2), т.е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (2), т.е. числа 23, 21, 12.

Целевая функция исходной задачи (1) – (3) исследуется на максимум, а система условий (2) содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Т.к. все три переменные исходной задачи (1) – (3) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида “ ”.

Ответ.

Для задачи (1) – (3) двойственная задача имеет вид:

найти минимум функции при условиях

где у₁, у₂, у₃ – любого знака.

 

Пример №4.2.

Построить двойственную задачу к следующей задаче ЛП:

Решение.

Т.к. целевая функция минимизируется, то неравенства должны быть записаны с помощью знака ≥. Поэтому, прежде чем приступать к построению двойственной задачи, необходимо упорядочить запись исходной, умножив второе неравенство на (-1):

.

Теперь, вводя двойственные переменные y₁, y₂, y₃ можно записать в соответствии с указанными правилами пару двойственных задач:

Задача слева – исходная прямая задача, задача справа – двойственная к исходной задаче.

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

Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже леммами и теоремами двойственности.

Лемма 1.

Если X – некоторый план исходной задачи, а Y – произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане X всегда не превосходит значения целевой функции двойственной задачи при плане Y, т.е. .

Лемма 2.

Если для некоторых планов X^* и Y^* прямой и двойственной задач, то X^* – оптимальный план произвольный исходной задачи, а Y^* – оптимальный план двойственной задачи.

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. I. Предмет и задачи дидактики
2. II. Предполагаемые союзники и их задачи
3. III. Целевые установки, задачи и направления обеспечения транспортной безопасности
4. IX. Общие правила подачи и рассмотрения апелляций
5. Алгоритм решения транспортной задачи
6. Анализ подходов и методов решения задачи
7. Анализ современного состояния АПК в России: задачи и экономическая стратегия развития
8. БИЛЕТ 1. Цели, задачи и основные принципы православной педагогики. Сотериологический характер педагогических воззрений Святых Отцов Церкви
9. БИЛЕТ 9. Вопрос 2. Психолого-педагогические задачи процесса духовно-нравственного становления личности на этапе вхождения в мир (наследство, зачатие, внутриутробное развитие, роды, новорожденность).
10. Бухгалтерский учет: его задачи, функции и
11. ВВЕДЕНИЕ. ЗАДАЧИ И ПРОБЛЕМЫ ГИСТОЛОГИИ.
12. Введение. Сущность , основные задачи, субъекты и объекты менеджмента.