Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Определение двойственной задачи

Читайте также:
  1. I Предопределение
  2. I. ОПРЕДЕЛЕНИЕ НЕКОТОРЫХ ОСНОВНЫХ ТЕРМИНОВ И ПОНЯТИЙ
  3. I. Предмет и задачи кризисной психологии
  4. I. Самоопределение к деятельности
  5. I. Цели и задачи музейной практики
  6. I. Цели и задачи учебной дисциплины
  7. I. Цель и задачи производственной

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

(32)

при условиях

(33)

(34)

Определение 1. Задача, состоящая в нахождении минимального значения функции

(35)

при условиях

(36)

(37)

называется двойственной по отношению к задаче (32) – (34). Задачи (32) – (34) и (35) – (37) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) – на минимум.

2. Матрица

(38)

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

(39)

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

3. Число переменных в двойственной задаче (35) – (37) равно числу ограничений в системе (33) исходной задачи (32) – (34), а число ограничений в системе (36) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) – (37) являются свободные члены в системе (33) исходной задачи (32) – (34), а правыми частями в соотношениях системы (36) двойственной задачи – коэффициенты при неизвестных в целевой функции (32) исходной задачи.

5. Если переменная xj исходной задачи (32) – (34) может принимать только лишь положительные значения, то j –е условие в системе (36) двойственной задачи (35) – (37) является неравенством вида “? ”. Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i –я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

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

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

(40)

при условиях

(41)

(42)

Решение. Для данной задачи

и

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

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

Пример 2. Для задачи, состоящей в максимизации функции

при условиях

сформулировать двойственную задачу.

Решение. Для данной задачи

,

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


Дата добавления: 2015-07-26; просмотров: 91 | Нарушение авторских прав


Читайте в этой же книге: Определение 6. | Пример 4. | Пример 5. | Свойства основной задачи линейного программирования. Геометрическое истолкование задачи линейного программирования | Теорема 4. | Пример 7. | Пример 8. | Геометрическая интерпретация двойственных задач | Пример 4. | Экономическая интерпретация двойственных задач |
<== предыдущая страница | следующая страница ==>
Пример 10.| Связь между решениями прямой и двойственной задач

mybiblioteka.su - 2015-2024 год. (0.008 сек.)