Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
= 1 + 2 = 3. 3. Составляем двойственную задачу: 1 2 ( ) 9 11 min, Z Y y y ∗ = + → 1 2 1 2 1 2 5 3 1, : 12 10 4, 2 4 1. y y L y y y y ∗ + ≥ + ≥ + ≥ 144 Подставим в ограничения задачи L * точку : Y 5 ≥ 0; 12 ≥ 0; 2 ≥ 0. Все ограни- чения выполняются, следовательно, переходим к следующему пункту. 4. Вычисляем значение целевой функции двойственной задачи в точке : ( ) 9. Y Z Y ∗ = 5. Сравниваем ( ) 3 Z X = и ( ) 9, Z Y ∗ = получаем, что данные X и Y не яв- ляются оптимальными в паре взаимно двойственных задач. Теорема 5.2 (сильная теорема двойственности). Для взаимно двойствен- ных задач имеет место один из взаимоисключающих случаев: 1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают. Иными словами, если X — оптимальное решение прямой задачи, а Y — оптимальное решение двойственной, то ( ) ( ). Z X Z Y ∗ = 2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество. 3. В двойственной задаче допустимое множество не пусто, а целевая функ- ция на этом множестве не ограничена сверху. При этом у прямой задачи допу- стимое множество оказывается пустым. 4. Обе задачи имеют пустые допустимые множества. Данную теорему примем без доказательства. Заметим, что некоторые авторы называют приведенную теорему «первой теоремой двойственности». Читателю стоит запомнить, что из сильной теоремы двойственности не- посредственно следует, что если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, при этом оптимальные значения целевых функций совпадают. Приведем экономический смысл сильной теоремы двойственности. План производства X и набор теневых цен Y оказываются оптимальными тогда и только тогда, когда доход от продукции, найденный при «внешних» (извест- ных заранее) ценах, равен затратам на сырье по внутренним (определяемым только из решения задачи) теневым ценам. Для всех же других планов обеих задач доход от продукции всегда меньше или равен затратам на сырье. Экономическое содержание сильной теоремы двойственности состоит так- же и в следующем: если задача определения оптимального плана, максимизиру- ющего выпуск продукции в стоимостном выражении, разрешима, то разрешима и задача определения теневых цен сырья. Причем цена продукта, полученного в результате реализации оптимального плана, совпадает с суммарной оцен- кой ресурсов. Совпадение значений целевых функций для соответствующих решений пары двойственных задач достаточно для того, чтобы эти решения были оптимальны. 145 Теневые цены выступают как инструмент балансирования затрат и резуль- татов. Они гарантируют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов обусловливает убыточность всякого дру- гого плана, отличного от оптимального. Теневые цены позволяют сопоставлять и балансировать затраты и результаты системы. Теорема 5.3 (о дополняющей нежесткости). Пусть 1 2 ( , , , ) n X x x x = — до- пустимое решение прямой задачи, а 1 2 ( , , , ) m Y y y y = — допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач, необходимо и достаточно, чтобы выполнялись следующие соотношения, называемые условиями дополняющей нежесткости (или условиями оптимальности): 1 11 1 12 2 1 1 2 21 1 22 2 2 2 1 1 2 2 1 11 1 21 2 1 1 2 12 1 2 ( ) 0, ( ) 0, ( ) 0. ( ) 0, ( n n n n m m m mn n m m m y a x a x a x b y a x a x a x b y a x a x a x b x a y a y a y c x a y a + + + − = + + + − = + + + − = + + + − = + 2 2 2 2 1 1 2 2 ) 0, ( ) 0. m m n n n mn m n y a y c x a y a y a y c + + − = + + + − = Условия дополняющей нежесткости позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой. Пример 5.4. Дана задача линейного программирования: 1 2 ( ) 2 3 max, Z X x x = + → 1 2 1 2 1 2 2 1 2 2, 2, : 2 10, 4, 2 2. x x x x L x x x x x + ≥ − ≤ + ≤ ≤ − + ≤ Известно ее решение: x 1 = 3, x 2 = 4, Z = 18. Требуется составить двойствен- ную задачу и с помощью условий дополняющей нежесткости найти ее решение. Решение. Так как прямая задача на максимум, то при составлении двойст- венной пользуемся первыми двумя столбцами таблицы с правилами перехода, получим: 1 2 3 4 5 2 2 10 4 2 min, y y y y y + + + + → 146 1 2 3 5 1 2 3 4 5 1 2 3 4 5 2 2 2, : 3, 0, 0, 0, 0, 0. y y y y L y y y y y y y y y y + + − = − + + + = ≤ ≥ ≥ ≥ ≥ Теперь составим условия дополняющей нежесткости: 1 1 2 2 1 2 3 1 2 4 2 5 1 2 1 1 2 3 5 2 1 2 3 4 5 ( 2) 0, ( 2) 0, (2 10) 0, ( 4) 0, ( 2 2) 0. ( 2 2 2) 0, ( 3) 0. y x x y x x y x x y x y x x y x x x x y x x x x x + − = − − = + − = − = − + − = + + − − = − + + + − = Подставляя в условия известные x 1 = 3, x 2 = 4, получим: ( ) 1 1 6 4 2 0 0, y y ⋅ + − = → = ( ) 2 2 3 4 2 0 0, y y ⋅ − − = → = ( ) любое 3 3 6 4 10 0 — , y y ⋅ + − = → ( ) любое, 4 4 4 4 0 — y y ⋅ − = → ( ) 5 5 6 4 2 0 0. y y ⋅ − + − = → = 3 3 3 4 4 2 2 0 1 18. 3 0 2 y y Z Z y y y ∗ − = = → = = + − = = Ответ: y 1 = 0, y 2 = 0, y 3 = 1, y 4 = 2, y 5 = 0, 18. Z ∗ = Приведем а л г о р и т м, позволяющий определить с помощью условий дополняющей нежесткости, будет ли некоторый X оптимальнымрешением задачи L. 1. Проверить, принадлежит ли данный X допустимому множеству прямой задачи L. Если не принадлежит, то X не является оптимальным решением. 2. Написать ограничения двойственной задачи L * 3. Составить условие дополняющей нежесткости и подставить в них дан- ный X. 147 4. Решить систему, образованную условием дополняющей нежесткости, и найти ее решение, которое обозначим Y. Если система не имеет решений, тоXне является оптимальным решением. 5. Проверить, что найденный Y принадлежит допустимому множеству двойственной задачи L * . Если не принадлежит, то Xне является оптимальным решением, в противном случае, является. Покажем работу данного алгоритма на следующем примере. Пример 5.5. Проверить, является ли X = (1; 0; 1; 0) оптимальным в задаче: 1 2 3 4 ( ) 2 4 6 max, Z X x x x x = − + − → 1 2 4 1 2 3 4 2 3 4 3 2 15, 2 2 4, : 3 0, 0 , 1,4 i x x x x x x x x x x x L i − + ≤ + − − ≥ − + − ≥ ≥ = Решение. Действуем по описанному выше алгоритму. 1. Проверим, является ли X планом данной задачи (т. е. подставим Xв ог- раничения): 3 − 0 + 0 ≤ 15, 1 + 0 − 1 + 0 ≥ −4, 0 + 3 − 0 ≥ 0, 1 ≥ 0, 0 ≥ 0, 1 ≥ 0, 0 ≥ 0. Все неравенства верные, следовательно, X принадлежит допустимому мно- жеству задачи L. 2. Составим ограничения L * : 3y 1 − y 2 ≥ 2, −y 1 + 2y 2 + 3y 3 ≥ −1, −y 1 + 3y 3 ≥ 4, 2y 1 − 2y 2 − y 3 ≥ −6, y 1 ≥ 0, y 2 ≤ 0, y 3 ≤ 0. 148 3. Запишем условия оптимальности с подстановкой X: ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 2 3 1 2 1 2 3 2 3 1 2 3 3–15 0, –1 4 0, 3–0 0, 1 3 – –2 0, 0 – 2 3 1 0, 1 – 3 – 4 0, 0 2 2 6 0. y y y y y y y y y y y y y = + = = ⋅ = ⋅ + + + = ⋅ + = ⋅ − − + = 4. Получим систему: 1 1 2 2 3 3 1 2 2 3 –12 0 0, 5 0 0, 3 0 0, 3 2 0, – 3 4 0. y y y y y y y y y y = → = = → = = → = − − = + − = Заметим, что система несовместна, следовательно, данный X неоптимален. Стоит также отметить, что условия дополняющей нежесткости имеют не- сколько важных следствий. Приведем их в следующем утверждении. Теорема 5.4 (вторая теорема двойственности). 1. Если некоторое из решений i y двойственной задачи положительно, то a i1 x 1 + a i2 x 2 + … + a im x n = b i 2. Если a i1 x 1 + a i2 x 2 + … + a im x n < b i , то y i = 0. 3. Если x j > 0, то a 1j y 1 + a 2j y 2 + … + a mj y m = c j 4. Если a 1j y 1 + a 2j y 2 + … + a mj y m > c j , то x j = 0. Приведем экономическую интерпретацию условий предыдущей теоремы. Условие 1 говорит о том, что если теневая цена положительна, то по опти- мальному плану соответствующий этой цене ресурс используется полностью, т. е., иными словами, является дефицитным. Условие 2 показывает, что если согласно оптимальному плану некоторое сырье используется не полностью, то соответствующая теневая цена этого сырья равна нулю. Условие 3 гласит: если при работе по оптимальному плану некоторая техно- логия (вид продукции) вовлекается в производство, то в оптимальных теневых ценах эта технология неубыточна. 149 Условие 4 интерпретируется так: если в оптимальных теневых ценах неко- торая технология (продукция) убыточна, то в оптимальном плане она не ис- пользуется, т. е. данная продукция не производится. Теперь покажем применение всех теорем двойственности на конкретной задаче. Пример 5.6. В табл. 5.2 заданы суточные затраты сырья на изготовление некоторой продукции, а также суточные запасы сырья и цены, по которым планируется реализация изготовленной продукции. Таблица 5.2 Вид сырья Затраты сырья на изготовление единицы продукции, кг Запасы сырья, кг А Б В I 4 2 1 180 II 3 1 3 210 III 1 2 5 244 Цена единицы продукции, руб. 10 14 12 Требуется определить план выпуска продукции, при котором обеспечивает- ся ее максимальная стоимость, и оценить каждый из видов сырья, используемых для производства продукции таким образом, чтобы теневые цены используемо- го сырья были минимальны, а суммарная оценка сырья была не меньше цены единицы продукции данного вида. Решение. Перед нами задача на планирование производства. Введем сле- дующие обозначения: x j — планируемое количество продукции j-го вида, j = 1, 2, 3; y i — теневая цена сырья i-го вида, i = 1, 2, 3. Тогда, исходя из того, что доход от реализации продукции должен быть максимальным, но при этом затраты сырья не должны превышать данных фиксированных затрат, имеем: 1 2 3 ( ) 10 14 12 max, Z X x x x = + + → 1 2 3 1 2 3 1 2 3 1 2 3 4 2 180, 3 3 210, : 2 5 244, 0, 0, 0. x x x x x x L x x x x x x + + ≤ + + ≤ + + ≤ ≥ ≥ ≥ Учитывая второе условие задачи, что суммарная оценка всего имеющегося сырья была минимальна и при этом доход от продажи сырья был не меньше, чем от реализации продукции, имеем: 150 1 3 2 ( ) 180 210 244 min, Z Y y y y ∗ → = + + 1 2 1 2 1 3 3 3 2 1 2 3 4 3 10, 2 2 14 , 0, , : 3 5 12 0, 0. y y y y y y L y y y y y y ∗ + + ≥ + + ≥ + ≥ ≥ ≥ + ≥ Таким образом, получили две взаимно двойственные задачи. Решим зада- чу L симплекс-методом. Для этого вначале необходимо перевести эту задачу в каноническую форму, введя дополнительные переменные: x 4 , x 5 , x 6 — излиш- ки сырья I, II и III вида соответственно. Следовательно, каноническая форма задачи L будет иметь следующий вид: 1 2 3 ( ) 10 14 12 max, Z X x x x = + + → 1 2 3 4 1 2 3 5 1 2 3 6 4 2 180, 3 3 210, 2 5 244, 0, 1,6. j x x x x x x x x x x x x x j + + + = + + + = + + + = ≥ = Теперь эту задачу можно решить симплекс-методом, что предлагаем чита- телям сделать самостоятельно. В результате конечная симплекс-таблица будет иметь вид (табл. 5.3). Таблица 5.3 Базис x 1 x 2 x 3 x 4 x 5 x 6 b Z 14,25 0 0 5,75 0 1,25 1 340 x 2 2,375 1 0 0,625 0 –0,125 82 x 5 2,875 0 0 0,125 1 –0,625 80 x 3 –0,75 0 1 –0,25 0 0,25 16 Из таблицы находим решение прямой задачи L: Z = 1 340, x 1 = 0, x 2 = 82, x 3 = 16, x 4 = 0, x 5 = 80, x 6 = 0. Исходя из этих значений, понимаем, что для того, чтобы получить максимально возможный суточный доход в размере 1 340 руб., необходимо изготовить 82 ед. изделия Б и 16 ед. изделия В, а изделие А не про- изводить. При данном плане производства остаются неиспользованными 80 кг сырья II вида. Теперь найдем решение двойственной задачи L * . Согласно сильной теореме двойственности * Z Z = = 1 340. Исходя из второй теоремы двойственности, так как при данном плане имеются излишки сырья II вида, теневая цена y 2 этого 151 сырья будет равна нулю, а теневые цены сырья I и III видов располагаются в симплекс-таблице в Z-строке в столбцах x 4 и x 6 соответственно, т. е. y 1 = 5,75 и y 3 = 1,75. Таким образом, увеличение количества сырья I вида на один кило- грамм приведет к тому, что появится возможность найти новый оптимальный план производства продукции, при котором общая стоимость продукции воз- растет на 5,75 руб. и станет 1 345,75 руб. При этом числа, стоящие в столбце x 4 под Z-строкой, показывают, что ука- занное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска продукции Б на 0,625 ед. и сокращения выпуска продукции В на 0,25 ед. Вследствие чего использование сырья II вида уменьшится на 0,125 кг. Аналогично можно сделать вывод и об увеличении общей стоимости продукции за счет увеличения сырья III вида, воспользовавшись данными из столбца x 6 Далее подставим получившиеся теневые цены в функциональные ограниче- ния двойственной задачи, получим: 23 + 1,25 > 10; 11,5 + 2,5 = 14; 5,75 + 6,25 = 12. В первом ограничении оценка сырья выше цены изделия A, следовательно, выпуск невыгоден, поэтому и производство продукции А не предусмотрено оптимальным планом. Стоит отметить, что, помимо экономических приложений, теоремы двой- ственности в некоторых случаях позволяют решить задачу линейного програм- мирования, не прибегая к методу искусственного базиса или М-методу. Напри- мер, если в некоторой задаче в канонической форме система функциональных уравнений не имеет единичной подматрицы, то симплекс-метод неприменим и нужно прибегать к более сложным методам. В этом случае можно составить двойственную задачу к исходной, и если ее возможно решить симплекс-мето- дом, то решаем ее и из симплекс-таблицы находим решение прямой задачи. Метод, в котором используется вышеописанный подход, называется двой- ственным симплекс-методом. |