Содержание
- 2. 6.1. ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ Исходную задачу линейного программирования будем называть прямой. Двойственная задача — это задача,
- 3. В состав n переменных xj, входят также дополнительные переменные. Стандартная форма задачи ЛП предполагает выполнение следующих
- 4. Графически эти правила представлены в табл. 4.1. Правила, определяющие тип оптимизации и ограничений, а также знак
- 5. Пример 4.2-3 Двойственная задача Минимизировать w = 5y1 + 3y2 + 8у3 при ограничениях y1 –
- 6. 6.2. СООТНОШЕНИЯ МЕЖДУ ОПТИМАЛЬНЫМИ РЕШЕНИЯМИ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧ Прямая и двойственная задачи так тесно взаимосвязаны,
- 7. Пример 4.3-1 Рассмотрим прямую и двойственную задачи из примера 4.2-1 В следующей таблице представлены симплекс-итерации решения
- 8. Решениями полученных уравнений будут у1 = 29/5 и у2 = -2/5. Если бы решения двойственной задачи
- 9. Пример 4.3-2 В примере 4.3-1 нетрудно показать (путем подстановки в ограничения), что прямая и двойственная задачи
- 10. 6.3. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД В двойственном симплекс-методе решение задачи ЛП начинается с недопустимого, но лучшего, чем оптимальное
- 11. Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум: ,
- 12. Среди дополнительных переменных этой задачи, x3 и x4 являются избыточными, а x5 — остаточной. Мы умножили
- 14. Скачать презентацию
6.1. ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ
Исходную задачу линейного программирования будем называть прямой.
6.1. ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ
Исходную задачу линейного программирования будем называть прямой.
Часто рассматривают формулировки двойственной задачи в зависимости от различных видов прямой задачи, которые определяются типами ограничений, знаками переменных (неотрицательные или свободные, т.е. без ограничения в знаке) и типом оптимизации (максимизация или минимизация целевой функции), что не всегда оправдано. Приведем единую формулировку двойственной задачи, применимую ко всем видам прямой задачи. В основу такой формулировки положена стандартная форма прямой задачи. Напомним, что задача ЛП в стандартной форме записывается следующим образом.
Максимизировать или минимизировать целевую функцию
при ограничениях
В состав n переменных xj, входят также дополнительные переменные. Стандартная
В состав n переменных xj, входят также дополнительные переменные. Стандартная
1. Все ограничения записаны в виде равенств (с неотрицательной правой частью).
2. Все переменные неотрицательны.
3. Оптимизация определяется как максимизация или минимизация целевой функции.
Стандартная форма задачи ЛП порождает стандартную таблицу симплекс-метода. Поэтому, как будет показано в разделе 4.3, решение двойственной задачи можно получить непосредственно из симплекс-таблицы, соответствующей оптимальному решению прямой задачи. Таким образом, определив двойственную задачу на основе стандартной формы прямой задачи, после вычислений симплекс-метода мы автоматически получаем решение двойственной задачи.
Переменные и ограничения двойственной задачи формируются путем симметричных структурных преобразований прямой задачи по следующим правилам.
1. Каждому из m ограничений прямой задачи соответствует переменная двойственной задачи.
2. Каждой из n переменных прямой задачи соответствует ограничение двойственной задачи.
3. Коэффициенты при какой-либо переменной в ограничениях прямой задачи становятся коэффициентами ограничения двойственной задачи, соответствующей этой переменной, а правая часть формируемого ограничения равна коэффициенту при этой переменной в выражении целевой функции.
4. Коэффициенты целевой функции двойственной задачи равны правым частям ограничений прямой задачи.
Графически эти правила представлены в табл. 4.1.
Правила, определяющие тип оптимизации и
Правила, определяющие тип оптимизации и
Следующий пример иллюстрируют правила построения двойственной задачи.
Пример 4.2-3
Двойственная задача
Минимизировать w = 5y1 + 3y2 + 8у3
при
Пример 4.2-3
Двойственная задача
Минимизировать w = 5y1 + 3y2 + 8у3
при
y1 – y2 + 4y3 = 5,
2у1 + 5y2 + 7у3 ≥ 6,
-y2 ≥ 0 → y2 ≤ 0,
y3 ≥ 0,
у1 — свободная переменная,
y2, y3 — свободные переменные (избыточное условие).
Первое и второе ограничения двойственной задачи заменены одним ограничением в виде равенства. Здесь действует следующее правило: свободной переменной прямой задачи соответствует ограничение в виде равенства двойственной задачи и, наоборот, ограничению в виде равенства прямой задачи соответствует свободная переменная двойственной задачи.
6.2. СООТНОШЕНИЯ МЕЖДУ ОПТИМАЛЬНЫМИ РЕШЕНИЯМИ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧ
Прямая и
6.2. СООТНОШЕНИЯ МЕЖДУ ОПТИМАЛЬНЫМИ РЕШЕНИЯМИ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧ
Прямая и
Соотношение 1. Для любой симплекс - итерации прямой или двойственной задачи.
Это соотношение симметрично относительно прямой и двойственной задач. Его можно использовать для определения оптимального решения одной задачи непосредственно из симплекс-таблицы, содержащей оптимальное решение другой. Данное обстоятельство обуславливает возможность проведения вычислений именно по той задаче (прямой или двойственной), которая требует меньших вычислительных ресурсов. Например, если прямая задача имеет 100 переменных и 500 ограничений, то предпочтительнее нахождение оптимального решения двойственной задачи, так как она будет содержать только 100 ограничений
Пример 4.3-1
Рассмотрим прямую и двойственную задачи из примера 4.2-1
В следующей таблице
Пример 4.3-1
Рассмотрим прямую и двойственную задачи из примера 4.2-1
В следующей таблице
Применяя на третьей симплекс - итерации соотношение 1 для переменных x4 и R из начального базисного решения, получим следующие данные
Решениями полученных уравнений будут у1 = 29/5 и у2 =
Решениями полученных уравнений будут у1 = 29/5 и у2 =
Применение соотношения 1 к переменным начального решения всегда приводит к легко решаемым уравнениям, так как каждое такое уравнение содержит только одну переменную. Конечно же, ничего не мешает использовать другие переменные (такие, как x1, х2 и х3 в рассматриваемой задаче) при построении уравнений, необходимых для определения значений переменных двойственной задачи. Например, соотношение 1 порождает следующие уравнения, ассоциируемые с переменными x1 и x3:
y1 + 2у2 - 5 = 0,
y1 + 3у2 - 4 = 3/5.
Решение этой системы уравнений также приводит к оптимальным значениям двойственной задачи у1 = 29/5 и у2 = -2/5. Однако аналогичные уравнения, ассоциируемые с переменными х4 и R, будут уже не так просты. (Убедитесь самостоятельно, что уравнения, ассоциированные с любыми двумя переменными из множества x1, x2, x3, x4, R, дают одни и те же значения переменных двойственной задачи.)
Представим еще одно соотношение между прямой и двойственной задачами, которое совместно с соотношением 1 предлагает интересную экономическую интерпретацию задачи линейного программирования.
Соотношение 2. Для любой пары допустимых решений прямой и двойственной задачи
В точке оптимума это соотношение принимает вид строгого равенства.
Пример 4.3-2
В примере 4.3-1 нетрудно показать (путем подстановки в
Пример 4.3-2
В примере 4.3-1 нетрудно показать (путем подстановки в
Из соотношения 2 следует, что для всех допустимых решений прямой и двойственной задач значения целевой функции задачи минимизации всегда будут верхним пределом значений целевой функции задачи максимизации. Таким образом, итерационное решение задачи максимизации ведет к возрастанию значений целевой функции, а итерационное решение задачи минимизации — к ее убыванию. В итоге, при успешном завершении процессов вычисления прямой и двойственной задач приходим к точке "равновесия", где значения целевых функций задач максимизации и минимизации становятся равными.
6.3. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
В двойственном симплекс-методе решение задачи ЛП начинается с
6.3. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
В двойственном симплекс-методе решение задачи ЛП начинается с
В двойственном симплекс-методе начальная симплекс-таблица обязательно должна иметь в базисном решении недопустимую (т.е. отрицательную) переменную. Для реализации двойственного симплекс-метода разработаны следующие два условия, выполнение которых гарантирует оптимальность последовательных промежуточных решений и приближение их к области допустимых решений.
Двойственное условие допустимости. В качестве исключаемой переменной хr выбирается базисная переменная, имеющая наибольшее по абсолютной величине отрицательное значение. Если таких переменных несколько, то выбор произволен. Если все базисные переменные неотрицательные, процесс вычислений заканчивается.
Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная,
Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная,
,
где αrj — коэффициент из симплекс-таблицы, расположенный на пересечении ведущей строки (соответствующей исключаемой переменной хr) и столбца, соответствующего переменной xj. При наличии нескольких альтернативных переменных, выбор делается произвольно.
Двойственное условие оптимальности основывается на той же основной идее, что и условие оптимальности прямого симплекс-метода из главы 3.
Пример 4.5-1
Дана следующая задача ЛП.
Минимизировать z = 3x1 + 2х2
при ограничениях
3x1 + x2 ≥ 3,
4х1 + 3x2 ≥ 6,
xl +x2 ≤ 3,
x1, x2 ≥ 0.
Начальная симплекс-таблица этой задачи имеет следующий вид
Среди дополнительных переменных этой задачи, x3 и x4 являются избыточными,
Среди дополнительных переменных этой задачи, x3 и x4 являются избыточными,
Двойственное условие допустимости указывает на переменную х4 (= -6) как на вводимую в базис. Теперь применим двойственное условие оптимальности для определения исключаемой переменной. Для этого используем следующую таблицу
Приведенные отношения показывают, что исключаемой переменной будет х2. Отметим, что переменные хj будут кандидатами на исключение из базисного решения только тогда, когда коэффициент α4j будет строго отрицательным. По этому критерию переменные x3, х4 и х5 не рассматриваются как кандидаты на исключение из базиса.
Следующая таблица получена с помощью известных операций над строками, применяемых в прямом симплекс-методе