Менеджмент 3-е издание - Глухов В.В.. Учебник для вузов. 3е изд. Спб. Питер, 2008. 608 с. ил. Серия Учебник для вузов
 Скачать 3.25 Mb.
|
|
Двойственная задача линейного программирования Каждой задаче линейного программирования можно сопоставить другую, назы ваемую двойственной по отношению к исходной (прямой): Прямая задача Двойственная задача 1 1 1 max(min) ; ( 1... ); 0 ( 1... ). n j j j n ij j i j j L c x a x b i m x j n = = ⎧ = ⎪ ⎪ ⎪ ⎨ ≤ = ⎪ ⎪ ⎪ ≥ = ⎩ ∑ ∑ 2 1 1 max(min) ; ( 1... ); 0 ( 1... ). m i i i m ij i j i i L b z a z c j m z i m = = ⎧ = ⎪ ⎪⎪ ⎨ ≥ = ⎪ ⎪ ⎪ ≥ = ⎩ ∑ ∑ Двойственную задачу по отношению к прямой составляют согласно правилам: Глава 8. Методы решения управленческих задач 150 150 150 150 150 1. Если целевая функция прямой задачи задается на max, тогда целевая функ ция двойственной задачи — на min, и наоборот. 2. Матрица 11 12 1 21 22 2 1 2 , n n m m mn a a a a a a A a a a ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ составленная из коэффициентов в систе ме ограничений прямой задачи, и аналогичная матрица 11 21 1 12 22 2 1 2 m m T n m mn a a a a a a A a a a ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ в двойственной задаче получаются друг из друга транспонированием. 3. Число переменных в двойственной задаче (m) равно числу соотношений (ограничений) в прямой задаче, а число ограничений в двойственной задаче (n) — числу переменных в прямой задаче. 4. Коэффициенты при неизвестных в целевой функции прямой задачи — это свободные члены (b i ), а правые части в ограничениях двойственной задачи (c j) — это коэффициенты при неизвестных в целевой функции прямой задачи. 5. Если переменная x j прямой задачи может принимать только положительные значения (x j ≥ 0), то j е условие двойственной задачи — условие неравенства вида « ≥». Если i е соотношение в прямой задаче — неравенство, то i я пере менная двойственной задачи z i ≥ 0. Если ПЗ имеет решение, то и ДЗ тоже имеет решение, причем max(min)L 1 = = min(max)L 2 . Поэтому достаточно для отыскания оптимума решить какую либо одну из задач двойственной пары; обычно решают ту, которая проще. Оптимальный план двойственной задачи позволяет оценить степень дефицит ности ресурсов, потребляемых при выполнении оптимального плана исходной задачи. Пример. Для производства изделий А, В, С используются три различных вида ресурсов. Каждый из видов ресурсов может быть использован в количестве соот ветственно не большем 180, 210, 244 ед. Известны затраты каждого из видов ресур сов на единицу продукции и цена единицы продукции каждого вида (табл. 8.6). Норма расхода ресурса, ед. изм./ ед. продукции Вид ресурса А В С 1 2 3 4 3 1 2 1 2 1 3 5 Цена продукции 10 14 12 Таблица 8.6 Оценка дефицитности вида продукции 151 151 151 151 151 8.4. Линейное программирование Требуется определить план производства, при котором обеспечивается макси мальный доход, и оценить дефицитность каждого из видов ресурсов, использу емых для производства продукции. Решение. Обозначим через x 1 искомый план производства изделий А, через x 2 — В, x 3 — С, а через z 1 — двойственную оценку дефицитности первого вида ресурса, через z 2 — второго, z 3 — третьего. Тогда прямая и двойственная задачи формули руются следующим образом: Прямая задача Двойственная задача max L 1 = 10x 1 + 14x 2 + 12x 3 ; min L 2 = 180z 1 + 210z 2 + 244z 3 ; 4x 1 + 2x 2 + x 3 ≤ 180; 4z 1 + 3z 2 + z 3 ≥ 10; 3x 1 + x 2 + 3x 3 ≤ 210; 2z 1 + z 2 + 2z 3 ≥ 14; x 1 + 2x 2 + 5x 3 ≤ 180; z 1 + 3z 2 + 5z 3 ≥ 12; x 1 , x 2 , x 3 ≥ 0. z 1 , z 2 , z 3 ≥ 0. Решение прямой задачи дает оптимальный план производства изделий А, В, С, а решение двойственной задачи — оптимальную систему оценок ресурсов, ис пользуемых для производства этих изделий: 0 0 0 1 2 3 1 0 0 0 1 2 3 2 0; 82; 0; max 1340; 5,75; 0; 1,25; min 1340. x x x L z z z L = = = = = = = = Исходя из анализа оптимальных двойственных оценок можно сделать следу ющие выводы. Ресурсы первого и третьего вида используются полностью. Полному исполь зованию этих ресурсов соответствуют полученные оптимальные оценки 0 0 1 3 , , z z отличные от нуля, т. е. положительные двойственные оценки имеют ресурсы, пол ностью потребляемые при оптимальном плане производства. Значит, ресурс вто рого вида недоиспользуется (на 80 ед.). Таким образом, двойственные оценки опре деляют дефицитность используемых ресурсов. Более того, величина двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества соответствующего ресурса на 1 ед. Так, увеличение количества ресурса первого вида на 1 ед. приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общий доход возрастет на 5,75 ден. ед. и станет равным 1340 + 5,75 = 1345,75 ден. ед. Анализ полученных оптимальных значений новой прямой задачи показывает, что это увеличение общего дохода до стигается за счет увеличения производства изделий В на 0,625 ед. и сокращения выпуска изделий С на 0,25 ед. Вследствие этого использование ресурса второ го вида уменьшается на 0,125 ед. Точно так же увеличение на 1 ед. количества ресурсов третьего вида позволит перейти к новому оптимальному плану производства, при котором доход возра стет на 1,25 ден. ед. и составит 1340 +1,25 = 1341,25 ден. ед., что достигается за счет увеличения выпуска изделий С на 0,25 ед. и уменьшения выпуска В на 0,25 ед., причем объем используемого ресурса второго вида возрастает на 0,625 ед. Глава 8. Методы решения управленческих задач 152 152 152 152 152 При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем: 4 × 5,75 + 1,25 > 10; 2 × 5,75 + 1,25 = 14; 5,75 + 5 × 1,25 = 12. Первое ограничение выполняется как строгое неравенство, т. е. двойственная оценка всех ресурсов на производство единицы изделия А выше цены этого из делия и, следовательно, выпускать его невыгодно. Его производство и не пред усмотрено оптимальным планом прямой задачи. При одновременном изменении ресурсов всех видов на величину Δbi(i = 1… m) можно оценить их суммарное влияние на значение целевой функции (при усло вии неизменности двойственных оценок в новой двойственной задаче относи тельно оценок в первоначальной двойственной задаче): 0 1 , m i i i L b z = Δ = Δ ∑ где Δb i — величина возможного (при сохранении оптимального плана первона чальной двойственной задачи) изменения (увеличения или уменьшения) ресур са i го вида. 8.5. 8.5. 8.5. 8.5. 8.5. Целочисленное программирование Целочисленное программирование Целочисленное программирование Целочисленное программирование Целочисленное программирование Под целочисленным или дискретным программированием понимают задачи, в ко торых искомые переменные могут принимать только целые значения: число ра бочих, разделяемых по рабочим местам, количество единиц оборудования, уста навливаемых на заданной площади, и т. п. Аналитическая задача целочисленного программирования формулируется: 1 1 max(min) ; ( 1... ); ( 1... ), n j j j n ij j i j j j j L c x a x b i m d x D j n = = = ≤ = ≤ ≤ = ∑ ∑ где 1 0, 1, 2, ... целые ( 1,..., ). j x j n n = = ≤ Если n 1 = n, то задачу называют полностью целочисленной; если n 1 < n, то ча стично целочисленной (ЧЦП). Предположим, что задача имеет многогранник решений (рис. 8.3). Если нало жить требование целочисленности, то допустимое множество решений выразит ся в системе точек и уже не будет являться выпуклым. Если добавить новые ограничения, связывающие внешние целочисленные точки, а затем в качестве многогранника использовать все выпуклое множество, ограниченное осями координат и новым контуром, то получим новую задачу ли нейного программирования со следующими свойствами: 153 153 153 153 153 8.6. Метод ветвей и границ 1. Новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка — целая. 2. Так как целевая функция достигает оптимума в угловой точке, то построени ем многогранника обеспечивается целочисленность оптимального решения. Решение задач целочисленного программирования трудоемко, поэтому по воз можности лучше не накладывать ограничений целочисленности переменных. В ряде случаев задачу целочисленного программирования решают следующи ми способами: как непрерывную задачу линейного программирования; округля ют переменные; проверяют допустимость округленного решения; если решение допустимо, то оно принимается как целочисленное. При необходимости точного решения применяют специальные методы, где учитывается, что множество решений любой целочисленной задачи — конечно. Например, в задаче с переменными x 1 , x 2 : 0 < x 1 ≤ 4; 0 < x j ≤ 5 число возможных решений — 20. Следовательно, допустим полный перебор возможных сочетаний целочисленных x 1 , x 2 и выбор наилучшего в смысле целевой функции. Трудоем кость этого метода возрастает с ростом числа переменных и области граничных условий, поэтому в реальных задачах применяют методы, в которых не рассмат ривают все возможные альтернативы. Распространены методы отсечений и ме тоды возврата, среди которых наиболее известен метод ветвей и границ. 8.6. 8.6. 8.6. 8.6. 8.6. Метод ветвей и границ Метод ветвей и границ Метод ветвей и границ Метод ветвей и границ Метод ветвей и границ Задача линейного программирования решается без учета целочисленности. Да лее рассматривают одну из переменных х j , на которую накладывают ограничение целочисленности, но получившую дробное значение. На основе полученного ре шения составляют дополнительные ограничения: х j ≤ [х j * ] и х j ≥ [х j * ] + 1, где [х j * ] — целая часть нецелочисленного значения переменной х j * в оптимальном решении. Затем решаются еще две задачи линейного программирования, в каж дую из которых вошли все исходные ограничения и одно из дополнительных. Полученное решение новых задач проверяют на целочисленность переменных. Если решение не удовлетворяет требованию целочисленности, на основе каждой из задач составляют две новые аналогично предыдущим и т. д. Рис. 8.3 Глава 8. Методы решения управленческих задач 154 154 154 154 154 Если одно из решений удовлетворяет требованию целочисленности, значение целевой функции принимается за граничное L гр . При этом рассмотрение других задач продолжается до тех пор, пока не будет получено: • на одной из ветвей — недопустимое решение; • на одной из ветвей — целочисленное решение. Тогда значение целевой функ ции сравнивается с L гр (верхним — при maх, нижним — при min); если полу ченное значение хуже, оно отбрасывается, если лучше, то принимается за граничное; • на одной из ветвей — нецелочисленное решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается. На первом цикле расчета при max ; при min . гр L L L −∞ ⎧ = ⎨ +∞ ⎩ Пример. Определить значение переменных для следующей оптимизационной задачи: maх L = 7х 1 + 3х 2 ; 5х 1 + 2х 2 ≤ 20; 8х 1 + 4х 2 ≤ 38; х 1 , х 2 ≥ 0 — целые. Решение. В результате решения задачи симплекс методом найдем оптималь ное решение: 1* 1* 1 2 1; 7,5, x x = = L 1 = 29,5, где верхний индекс переменных — номер задачи (рис. 8.4). В полученном решении х 2 = 7,5 — нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями. Задача 2: Задача 3: maх L = 7х 1 + 3х 2 ; maх L = 7х 1 + 3х 2 ; 5х 1 + 2х 2 ≤ 20; 5х 1 + 2х 2 ≤ 20; 8х 1 + 4х 2 ≤ 38; 8х 1 + 4х 2 ≤ 38; х 1 ≥ 0; х 1 ≥ 0; 0 ≤ х 2 ≤ 7. х 2 ≥ 8. Рис. 8.4 155 155 155 155 155 8.7. Задачи с булевыми переменными Результаты решения симплекс методом задачи 2: 2* 2* 1 2 1,2; 7; x x = = L 2 = 29,4. Результаты решения симплекс методом задачи 3: 3* 3* 1 2 0,75; 8; x x = = L 3 = 29,25. В задаче 1 переменная х 1 1 = 1 — целочисленная, а при целочисленности х 2 в по следующих задачах х 1 перестала быть целочисленной. Затем следует накладывать ограничения целочисленности на х 1 и т. д. В качестве оптимального принимается решение задачи 5, которое дает наи большее из целочисленных решений значение целевой функции. Из примера видно, что метод ветвей и границ достаточно трудоемкий. При этом оптимальное решение может быть получено в результате сравнения всех допустимых целочисленных решений. 8.7. 8.7. 8.7. 8.7. 8.7. Задачи с булевыми переменными Задачи с булевыми переменными Задачи с булевыми переменными Задачи с булевыми переменными Задачи с булевыми переменными В частном случае искомая переменная х j в результате решения может принимать не любое целое значение, а только одно из двух: 0 либо 1. Чтобы такие перемен ные отличать от обычных, будем их вместо х j обозначать δ j И это уже будет означать, что в результате решения задачи δ j может быть рав ным или 0, или 1, т. е. всегда δ j [0; 1]. Такие переменные обычно называют буле выми в честь предложившего их английского математика Джорджа Буля (1815– 1864). С помощью булевых переменных можно решать самые различные по содержа нию задачи, в которых надо выбирать из имеющихся различных вариантов. Пример. В задаче выбора вариантов примем, что для получения результата в виде максимально возможной прибыли необходимы два вида ресурсов: матери альные и трудовые (табл. 8.7). Таблица 8.7 Задача выбора вариантов Варианты Показатели 1 2 3 4 Наличие Прибыль, ден. ед./ед. 65 80 90 210 – Материальные ресурсы 200 180 240 250 800 Трудовые ресурсы 10 15 22 28 50 Возможны четыре варианта расхода ресурсов и получения прибыли. Требует ся выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех, т. е. k ≤ 3. Решение. Для составления модели примем, что j му варианту будет соответ ствовать δ j ( j = 1… 4). При этом 1, если й вариант принят; 0, если й вариант не принят. j j j δ ⎧ = ⎨ ⎩ Тогда математическая модель задачи запишется в виде: maх L = 65 δ 1 + 80 δ 2 + 90 δ 3 + 210 δ 4 ; 200 δ 1 + 180 δ 2 + 240 δ 3 + 250 δ 4 ≤ 800; Глава 8. Методы решения управленческих задач 156 156 156 156 156 10 δ 1 + 15 δ 2 + 22 δ 3 + 28 δ 4 ≤ 50; δ 1 + δ 2 + δ 3 + δ 4 ≤ 3. Последняя строка системы обеспечивает выполнение условия, чтобы общее число принятых вариантов не превышало трех (табл. 8.8). Таблица 8.8 Из вариантов решения задачи видно, что наибольшая прибыль (maх L = 300) достигается, если будут приняты третий и четвертый варианты. С помощью булевых переменных можно накладывать дополнительные логи ческие связи между вариантами. Например, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй, а если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так: δ 2 = δ 4 или в форме записи ограничений δ 2 – δ 4 = 0. Может быть сформулирован и другой вариант дополнительных условий: на пример, требуется, чтобы был принят либо третий вариант, либо четвертый, т. е. δ 3 + δ 4 = 1 (результат решения в третьем столбце). Сравнивая значение прибыли в оптимальном решении (maх L = 300) с прибы лью при выполнении дополнительных условий, можно сделать вывод, что они приводят к снижению прибыли. Переходя от примера с дополнительными условиями к общему случаю, задачу выбора вариантов можно записать так: 1 1 1 max ; ( 1... ); ; , n j j j n ij j i j s n j j L c a b i m p k δ δ δ = = ≤ = = ≤ = ≤ ≤ ∑ ∑ ∑ где последнее ограничение (*) может учитывать самые разнообразные условия: • если накладывается требование «должен», то в ограничении (*) ставится знак равенства; • если требование «может», то знак неравенства, в частности: если накладыва ется требование «И», то условие (*): 1 1, s j j δ = ≥ ∑ (*) Вариант Показатель 1 2 3 Прибыль 300 290 235 0 1 δ 0 0 1 0 2 δ 0 1 1 0 3 δ 1 0 1 0 4 δ 1 1 0 157 157 157 157 157 8.8. Дискретное программирование например принятие и первого и третьего вариантов запишется: δ 1 + δ 3 ≥ 1; • если для вариантов накладывается требование «ИЛИ», то условие (*) запи шется: 1 1. s j j δ = = ∑ 8.8. 8.8. 8.8. 8.8. 8.8. Дискретное программирование Дискретное программирование Дискретное программирование Дискретное программирование Дискретное программирование В этих задачах результатом решения должны быть целые, но не любые целые. |