Eng | Rus | Ukr | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Исследование операций
|
24.12.2008
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2.7. ИССЛЕДОВАНИЕ МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ЧУВСТВИТЕЛЬНОСТЬ Теория двойственности позволяет анализировать модели ЛП на чувствительность. Рассмотрим обычную задачу ЛП в виде максимизировать (2.7.1) (2.7.2) xj³0. Напомним ее экономическую интерпретацию. Целевая функция L(x) -это доход от реализации плана производства x; aij -интенсивность расходования i-го ресурса при j-м способе производства; bi- имеющийся уровень i-го ресурса. 1. Варьирование ограниченных ресурсов. Предположим, что величины ресурсов b=|| bi || варьируются. Тогда возникают вопросы: при каких вариациях правых частей ограничений найденный оптимальный план x0 не изменяется; как эти вариации влияют на функцию максимального дохода Lmax? Ответ на эти вопросы дает анализ соответствующей задачи ЛП на чувствительность. Пусть ограничение bi получают некоторые вариации Dbi, что приводит к вариациям плана x0, x0= x0(b+Db) и функции Lmax (x0(b0+Db)). Предположим, эти вариации Db таковы, что план x0(b+Db) остается допустимым ( т.е. удовлетворяет условию неотрицательности). Найдем отношения приращения DLmax(b)= Lmax (x0(b0+Db))- Lmax (x0(b)) к Db. Имеем (2.7.3) где b рассматривается как варьируемый параметр. Вспомним, что в соответствии с основной теоремой двойственности , (2.7.4) и, подставляя (2.7.4) в (2.7.3), получим . (2.7.5) Таким образом, оптимальные значения двойственных переменных определяют вклад каждого ресурса в доход Lmax при оптимальном решении x0. Эта величина численно равна дополнительному доходу при увеличении i-го ресурса bi на единицу при условии, что ресурсы используются оптимальным образом. Итак, величины служат показателями важности соответствующих ресурсов для системы. Чем большее значение при некотором i, тем существеннее вклад i-го ресурса в функцию максимального дохода Lmax и тем выгоднеее его увеличение. Если для некоторого =0, то i-й ресурс не является существенным ограничением для системы. Заметим, что этот вывод хорошо согласуется с результатами теоремы 2.6 двойственности, которая связывает величины с ограничениями прямой задачи. Обозначим через Ax матрицу оптимального базиса задачи ЛП при векторе ресурсов b. Очевидно соответствующее оптимальное решение xопт= A-1x b. Предположим, что мы изменили вектор ресурсов b=|| bi || на bн=b+ Db и хотим узнать, как это повлияет на оптимальное решение. Для этого найдем новое соответствующее базисное решение xн = А-1хbн = А-1х(b+Db). Если все компоненты xiн ³ 0, то это решение xн = [xiн] оптимально (т.е. оптимальный базис не изменился). В противном случае нужно произвести поиск нового решения, для этого можно применить двойственный симплекс-метод, начиная с текущего базисного решения xн. 2. Варьирование целевой функции. Теперь рассмотрим случай, когда варьируются коэффициенты {cj}, j= 1,2,.,n... Попытаемся выяснить условия, при которых найденный ранее оптимальный план останется оптимальным при таких вариациях. Пусть вариациям подвергнется коэффициент . Обозначим через Jб, Jнеб множество индексов базисных и небазисных векторов в оптимальном плане x0 соответственно. Найдем значения оценок после вариации cr для двух случаев: 1) rÎ Jнеб , тогда для всех j¹r ; для j=r ; (2.7.6) 2) rÎ Jб, jÎJнеб (2.7.7) Очевидно, что для сохранения оптимальности прежнего плана при вариациях коэффициента cr необходимо и достаточно сохранение знаков оценок для всех небазисных переменных. Поэтому из условий ³0 в соответствии с формулами (2.7.6) и (2.7.7) можно определить допустимые вариации коэффициента , при которых сохраняется прежнее оптимальное решение. До сих пор мы рассматривали вариации лишь одного коэффициента целевой функции. Этот же подход можно применить, когда варьируются одновременно несколько коэффициентов ci. В таком случае получим соотношения, аналогичные (2.7.7), в которых оценки будут функциями уже нескольких параметров (d1, d2,.,dr)... Решая совместно систему неравенств вида (c1, c2,.,cr)³0,jÎJнебы находим условия для вариаций , при которых прежний оптимальный базис сохраняется. Эта задача относится к классу задач параметрического программирования [12]. 3. Варьирование элементов матрицы ограничений A. Рассмотрим лишь случай вариации компонентов небазисных векторов Aj=[aij], i=1,2,...,m, поскольку исследование вариаций компонент базисных векторов Ai довольно сложное, легче заново решить задачу с новыми условиями. Итак, пусть небазисный вектор Aj=[amj] изменился. Нужно выяснить, останется ли оптимальным текущий базис. Для этого полезно применить теорию двойственности. Пусть оптимальный базис прямой задачи Ax, а соответствующие оптимальные значения двойственных переменных . Как известно, условие оптимальности ³0, " jÎ Jнеб Вместе с тем в соответствии с (2.6.11), . Значит если ,то прежний оптимальный базис сохраняется. 4. Добавление еще одного способа производства. Предположим, что первоначально задача имеет вид максимизировать (2.7.8) при условиях , (2.7.9) xj³0. Предположим, что найден оптимальный базис {Ai}, iÎ Jб и соответствующие оптимальные решения прямой и двойственной задач. Пусть прибавляется еще один (n+1)-й способ производства, которому отвечает вектор технологических затрат An+1=[ai n+1] и коэффициент целевой функции cn+1. Тогда будем иметь следующую задачу: максимизировать (2.7.10) , (2.7.11) xj³0, j=1, 2,., n+1. (2.7.12) Нужно определить, изменится ли при этом прежнее оптимальное решение и при каком значении коэффициента cn+1 выпуск (n+1)-го продукта будет рентабельным (то есть ). Чтобы оптимальное решение после ввода вектора An+1 не изменилось , необходимо, чтобы вектор An+1 и переменная xn+1 оставались небазисными, т.е., чтобы Dn+1³0. На основании теории двойственности получим . Если , то прежний оптимальный план не изменится после включения выпуска (n+1)-го вида продукции. Если же , то выпуск (n+1)-го вида продукции становится рентабельным, и прежний оптимальный план изменяется. Пример 2.10. Предприятие выпускает изделия двух видов, для изготовления которых используются ресурсы двух типов. Пусть прибыль от продажи изделий составляет соответственно c1=2 и c2=3, объем ресурсов равняются b1=32, b2=24 соответственно. Нормы затрат ресурсов на единицу выпуска задаются такой матрицей:
1. Нужно найти оптимальный план выпуска, который максимизирует суммарный доход и исследовать чувствительность целевой функции к вариации ограниченных ресурсов, т.е. как изменится суммарный доход при увеличении на единицу любого из видов ресурсов. 2. Пусть первый ресурс b1 увеличился до 35, а второй уменьшился до 20. Как изменится при этом оптимальное решение, останется ли оптимальным прежний базис? 3. Пусть вводится дополнительное ограничение на выпуск первого продукта x1³ 6. Определить новый оптимальный план. 4. Пусть предприятие может дополнительно выпускать третий вид продукции, для которого c3=4, а нормы затрат ресурсов составляют a13=3; a23=2. Найти оптимальный план с учетом этого условия и определить, при каком значении c3 производство третьего вида изделий будет рентабельным. Решение. Математическая модель задачи: max (2 x1+3 x2) при условиях 3 x1+2 x2 £ 32; 1 x1+2 x2 £ 24; x1³0, x2³0. Решим эту задачу симплекс-методом и через две итерации найдем оптимальный план (табл.2.27). Получим=4; =10; max (2 x1+3 x2)=38. Матрица образована небазисными векторами A4, A5 в табл.2.27. Таблица2.27
Оптимальные значения двойственных переменных находим в индексной строке табл.2.27: ; . Анализируя значения , , видим, что при увеличении на единицу первого ресурса мы получим приращение ц.ф. а при увеличении на единицу второго ресурса . Итак, второй ресурс оказывается более важным для системы и его повышение выгоднее. Пусть первый ресурс увеличен до 35 единиц, а второй уменьшен до 20 единиц, тогда новый вектор =[ 35; 20 ]T. Найдем новое базисное решение для этого вектора:
Поскольку, то это решение будет оптимально (так как не изменились оценки D4 и D5 для небазисных векторов). Пусть введено дополнительное ограничение x1³6. Приведем его к стандартному виду: x1-x6=6R-x1+x6=-6. Допишем эту строку в симплекс-таблице 2.27, и одновременно справа от нее столбец A6. Получим главную часть табл.2.28. Таблица 2.28.
Анализируя ее видим, что базисный столбец A1 не является единичным, и нужно исключить переменную x1 в строке x6. Для этого прибавим к строке x6 строку x1, в результате получим новую строку , которую дописываем в табл.2.28 внизу, а строку x6 можно вычеркнуть. Так как компонента = -2<0, то базисное решение { x1 , x6 , x'6} -это псевдоплан: и дальше для продолжения итераций применим двойственный симплекс-метод. Направляющая строка , направляющий столбец A4. Выполнив одну итерацию двойственного симплекс-метода, получим симплекс-таблицу 2.29. Таблица 2.29.
Так как=6>0, =7>0, то это новое решение оптимально. При этом Lmax==33. Проверим целесообразность введения третьего способа производства. Для этого рассмотрим столбец В соответствии с теорией двойственности . Так как D3<0 , то столбец A3 целесообразно ввести в базис. В соответствии с методом обратной матрицы вычисляем его вид , в котором его можно дописать в таблицу 2.27:
Дописав столбец A3 в симплекс-таблиу оптимального решения исходной задачи (табл.2.27), получим табл. 2.30. При этом . Таблица 2.30.
Выполнив одну итерацию симплекс-метода, получим симплекс-таблицу 2.31. Таблица 2.31.
Поскольку все элементы ее индексной строки Dj ³ 0, то это решение оптимально: =8; =4. При этом значение ц.ф. увеличилось до 44 единиц. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Copyright © 2002-2004 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||