Двойственные задачи линейного программирования (определения, пример). Установление возможности перехода от прямой задачи к двойственной (и наоборот) согласно теореме двойственности. Метод последовательных уступок и его алгоритм и пример применения.
Аннотация к работе
Задачу (1) называют прямой, а связанную с ней задачу (2) - двойственной. Связь между задачами (1) и (2) взаимна, т.е. если прямой считать задачу (2), то в качестве двойственной ей будет соответствовать задача (1). Возможность перехода от прямой задачи к двойственной (и наоборот) устанавливается теоремой двойственности: если одна из задач (1) или (2) имеет оптимальное решение, то и другая также имеет оптимальное решение, причем оптимальные значения функции цели прямой и двойственной задач совпадают, т.е. max F (x) = min F (y). Если среди ограничений прямой задачи имеются равенства или на некоторые переменные не наложено условие неотрицательности, то построив двойственную ей задачу, получим пару несимметричных двойственных задач: При этом выполняются следующие правила: 1. Если в прямой задаче имеются ограничения равенства, то на соответствующие переменные двойственной задачи не накладывается условие неотрицательности.Процедура решения многокритериальной задачи методом последовательных уступок заключается в том, что все частные критерии располагают и нумеруют в порядке их относительной важности; максимизируют первый, наиболее важный критерий; затем назначают величину допустимого снижения значения этого критерия и максимизируют второй по важности частный критерий при условии, что значение первого критерия не должно отличаться от максимального более чем на величину установленного снижения (уступки); снова назначают величину уступки, но уже по второму критерию и находят максимум третьего по важности критерия при условии, чтобы значения первых двух критериев не отличались от ранее найденных максимальных значений больше чем на величины соответствующих уступок; далее подобным же образом поочередно используются все остальные частные критерии; оптимальной обычно считают любую стратегию, которая получена при решении задачи отыскания условного максимума последнего по важности критерия. Таким образом, при использовании метода последовательных уступок многокритериальная задача сводится к поочередной максимизации частных критериев и выбору величин уступок. При решении многокритериальной задачи методом последовательных уступок вначале производится качественный анализ относительной важности частных критериев; на основании такого анализа критерии располагаются и нумеруются в порядке убывания важности, так что главным является критерий K1, менее важен. Затем назначается величина "допустимого" снижения (уступки) D1>0 критерия K1 и ищется наибольшее значение Q2 второго критерия K2 при условии, что значение первого критерия должно быть не меньше, чем Q1-D1. Наконец, максимизируется последний по важности критерий Ks при условии, что значение каждого критерия Kr из S-1 предыдущих должно быть не меньше соответствующей величины Qr-Dr; получаемые в итоге стратегии считаются оптимальными.
План
Содержание
1. Двойственные задачи линейного программирования (определения, пример)
2. Метод последовательных уступок. Алгоритм метода. Пример применения метода к решению задачи многокритериальной оптимизации выпуска продукции предприятием
1. Двойственные задачи линейного программирования (определения, пример)