Методы оптимизации управления для менеджеров - Зайцев М.Г.. Методы оптимизации управления для менеджеров компьютерноориентированный подход
 Скачать 7.64 Mb.
|
|
3.1. Графическое решение задачи об оптимальном плане выпуска продукции мебельного цеха Напомним, что в этой задаче в качестве переменных мы выбрали количество производимых ежедневно шкафов –Х 1 и тумб — Х 2 . Целевая функция - прибыль - записывалась как P=200X 1 +100X 2 , а ограничения состояли в том, что ежедневный расход ресурсов не должен превышать их ежедневные запасы: ДСП 3,5Х 1 +Х 2 ≤ 350, Стекло Х 1 +2Х 2 ≤ 240, Труд Х 1 +Х 2 ≤ 150. Любой план выпуска продукции цеха характеризуется двумя числами Х 1 и Х 2 может быть изображен как точка на плоскости в координатах (Х ] и Х 2 ).Некоторые числа удовлетворяют приведенным выше неравенствам (ограничениям), другие нет. Например, нельзя при заданных запасах ресурсов произвести Х 1 =1000 шкафов и Х 2 =500 тумб. Те планы Х 1 , Х 2 , которые удовлетворяют имеющимся ограничениям на ресурсы, мы называли допустимыми. Среди множества допустимых планов нужно найти оптимальные (т.е. соответствующие оптимальной целевой функции). Изобразим графически область оптимальных планов на координатной плоскости (Х ] и Х 2 ).Для этого построим линии, изображающие предельные расходы ресурсов за день: 3,5Х 1 +Х 2 = 350, Х 1 +2Х 2 = 240, Х 1 +Х 2 = 150. Очевидно, что это прямые линии, которые могут быть построены по двум точкам. Например, для линии, изображающей ограничения по расходам трудовых ресурсов за день, линию можно построить по точкам (Х 1 = 50, Х 2 = 100) и (Х 1 = 100, Х 2 = 50). На рис. 11 построены все три линии - границы области допустимых планов. Область, ограниченная получившимся многоугольником OABCD, и есть область допустимых планов. Любая точка, лежа-шля внутри данной области, имеет координаты Х 1 , Х 2 удовлетворяющие всем трем ограничениям на расход ресурсов, а также требованию положительности переменных решения. Далее изобразим графически выражение для прибыли от производства Х 1 шкафов и Х 2 тумб. Это несколько сложнее, чем изображение границы для использования того или иного ресурса, так как выражение для прибыли содержит две независимые переменных (Х 1 , Х 2 ) и прибыль Р, которая от них зависит. Допустим на минуту, что нас устраивает прибыль 10 000 у.е. в день и мы хотим графически изобразить линию, на которой находятся планы, дающие такую прибыль. В этом случае мы получим уже знакомое нам уравнение прямой линии 10000 = 200Х 1 + 100Х 2 , которое, если сократить обе части на 100, приводится к виду 2Х 1 + Х 2 =100 График этой линии внутри области допустимых планов показан на рис. 12. На этом же рисунке показан участок линии, содержащий планы, для которых достигается ежедневная прибыль Р=20000: (20000 = 200Х 1 + 100Х 2 →2Х 1 + Х 2 =200). Видно, что эти линии параллельны. Таким образом, становится ясно, что графическим изображением уравнения для прибыли является семейство параллельных прямых (две из которых показаны на рис. 12). Причем, чем больше прибыль Р, тем правее расположена линия, содержащая планы, отвечающие этой прибыли. Очевидно, что максимум прибыли достигается в угловой точке С области допустимых планов. Прямая, проходящая через эту точку, - последняя из семейства прямых прибыли, которая имеет хотя бы одну общую точку с областью допустимых планов. Все прямые, лежащие правее ее (отвечающие большим значениям прибыли), целиком находятся вне области допустимых планов. В данном случае оптимальный план (точка С)лежит на пересечении границ ресурсов "труд" и "ДСП". Ресурс "стекло" при этом расходуется не полностью. Это означает, что координаты точки, соответствующей оптимальному плану, одновременно удовлетворяют уравнениям двух линий, изображающих предельные расходы ресурсов "труд" и "ДСП": 3,5Х 1 + Х 2 =350 Х 1 + Х 2 =150 Решив эту систему уравнений (например, выразив Х 1 из второго уравнения и подставив его в первое), нетрудно получить значения Х 1 =80, Х 2 = 70, которые и были получены при решении этой задачи с помощью MS-Excel. Следует заметить, что подобное графическое решение очень трудно провести для задач с тремя переменными решения. В этом случае область допустимых планов представляет собой многогранник сложной формы в 3-мерном пространстве. Что же касается задач с числом переменных более трех, то графически изобразить область допустимых планов вообще нельзя, поскольку это многогранник в многомерном пространстве. Таким образом, графическое решение никоим образом нельзя рассматривать как практический метод решения задач линейного программирования. Однако проведенный графический анализ дает очень важное интуитивное представление о том, где находится оптимальный план-решение задачи линейной оптимизации. Оптимум (максимум или минимум) целевой функции достигается в одной из угловых точек области допустимых планов. Эта точка является пересечением границ тех ресурсов, которые при оптимальном плане расходуются полностью. Исключение из этого правила составляют случаи, когда линии постоянной прибыли параллельны границе области допустимых планов, соответствующей предельному расходу одного из ресурсов (см. рис. 12). В таких случаях существует бесконечно много планов, отвечающих оптимальному значению целевой функции. (В многомерном случае говорят, что "гиперплоскость" постоянной прибыли параллельна гиперплоскости — границе одного из ресурсов.) Симплекс-метод Сделанный вывод на первый взгляд позволяет предложить простой метод решения задач линейного программирования: надо просто "перебрать" все угловые точки области допустимых планов, в каждой из них вычислить значение целевой функции и выбрать ту угловую точку, где целевая функция оптимальна. Однако количество угловых точек области допустимых планов растет очень резко с ростом числа переменных и особенно числа ограничений. Так, для небольшой задачи линейного программирования с 20 переменными и 10 ограничениями число угловых точек составляет около 30 млн., а для задачи с 100 переменными и 20 ограничениями это число может достигать 47 трлн. (47х10 12 ). Чтобы сосчитать значения целевой функции во всех этих точках, компьютеру, выполняющему миллион арифметических операций в секунду, потребуется около года непрерывной работы. Вместе с тем ваш персональный компьютер, используя надстройку "Поиск решения" MS-Excel, решит такую задачу за доли секунды. Дело, разумеется, в том, что MS-Excel использует эффективные алгоритмы решения задач. Эти алгоритмы не перебирают все угловые точки подряд, а, начав с любой из них, выбирают каждую последующую так, чтобы значение целевой функции и ней было гарантированно ближе к оптимальному. Первый такой алгоритм, называемый симплекс-методом, был предложен американским математиком Джорджем Данцигом в 1947 г. С тех пор появились различные модификации этого алгоритма, ускоряющие сходимость алгоритма к оптимальному решению. Кстати, симплекс (лат. simplex) означает замкнутую область и многомерном пространстве (область допустимых планов). Как меняется оптимальное решение при изменении целевых коэффициентов? На рис. 13 показано, как меняется наклон семейства прямых постоянной прибыли, если уменьшать прибыль от продажи одно-i о шкафа от 200 до 150 и далее до 50 у.е. Очевидно, что изменение наклона прямых постоянной прибыли от 200 до 150 у.е. (и даже до 100 у.е.) не приведет к изменению оптимального решения. По-прежнему последней точкой области допустимых планов, которой коснется прямая максимальной прибыли, будет точка С. Отсюда следует важный вывод: Существует определенный интервал устойчивости, в котором изменение целевых коэффициентов не приводит к изменению оптимального решения. Разумеется, значение максимума прибыли при изменении целевого коэффициента меняется, но оптимальный план остается абсолютно тем же. Однако при дальнейшем уменьшении прибыли от продажи одного шкафа (до 50 у.е.) последней точкой, которой касается прямая постоянной прибыли при ее движении в сторону больших значений прибыли, станет точка В. При этом резко изменится оптимальный план и соответствующее значение максимальной прибыли. Таким образом, если значение целевого коэффициента выходит за пределы интервала устойчивости, оптимальное решение резко изменяется, переходя в совершенно другую угловую точку области допустимых планов. Предсказать, в какую именно, невозможно. Для этого нужно заново решить задачу линейного программирования с новыми параметрами. Отчет об устойчивости В процессе поиска оптимального решения MS-Excel формирует так называемы отчет об устойчивости, в котором, в частности, выдает интервал изменений коэффициентов целевой функции, внутри которого их изменение не приводит к изменению оптимального решения. Для получения этого отчета, после того как"Поиск решения" нашел оптимальное решение, нужно в окне "Результаты поиска решения", перед тем как нажать на кнопку Ok, щелкнуть мышкой по строке "Устойчивость" в списке "Тип отчета" (см. рис. 6). Тогда после нажатия на кнопку Ok MS-Excel создаст дополнительный лист "Отчет об устойчивости". Распечатку такого отчета для задачи об оптимальном плане выпуска продукции мебельного цеха дана нарис 14. Первая таблица отчета об устойчивости "Изменяемые ячейки содержит столбцы "Целевой коэффициент", "Допустимое увеличение" и "Допустимое уменьшение". В первом из них даны исходные значения целевых коэффициентов: прибыль от продажи одного шкафа (200 у.е.) и одной тумбы (100 ух.). Второй и третий столбцы содержат информацию об интервале устойчивости найденного оптимального решения. При увеличении прибыли от продажи шкафа до 350 у.е. (на 150 у.е. больше исходного значения) и при ее уменьшении до 100 у.е. оптимальное решение не изменяется. Аналогично второй целевой коэффициент может изменяться в пределах от 57,14 у.е. (уменьшение на 42,86 у.е. относительно исходного значения) до 200 у.е. Смысл столбца "Нормированная стоимость" мы прокомментируем позже. Во второй таблице отчета об устойчивости - "Ограничения" аналогичные интервалы устойчивости установлены для запасов ресурсов "ДСП", "стекло", "труд" (столбцы "Ограничения, правая часть", "Допустимое увеличение" и "Допустимое уменьшение"). Однако смысл этих интервалов несколько иной. При изменении запасов ресурсов оптимальное решение будет изменяться непрерывно (как можно увидеть, анализируя рис. 11), При движении границ ресурсов координаты угловой точки, очевидно, будут непрерывно меняться, но до тех пор, пока решение будет оставаться в той же угловой точке области допустимых планов, будет оставаться неизменной так называемая теневая цена ресурса - важнейшая характеристика оптимального решения. Для того чтобы понять, что это такое, необходимо рассмотреть так называемую двойственную задачу к задаче об оптимальном плане выпуска продукции мебельного цеха. Упражнение по использованию отчета об устойчивости: влияние изменений в ценовых коэффициентах В этом упражнении вы имеете возможность проверить правильность данных, приведенных в отчете об устойчивости к задаче об оптимальном плане выпуска продукции мебельного цеха. I. Решите задачу об оптимальном плане выпуска продукции мебельного цеха (рис. 1) и получите отчет об устойчивости. II. Измените коэффициенты целевой функции (в ячейках С9, D9) и с помощью надстройки "Поиск решения" найдите, как изменится решение (Х 1 ,Х 2 ) и значение целевой функции. Результаты впишите в пустые рамки (см. ниже). 1. Увеличить норму прибыли при производстве шкафа на 100 у.е. 2. Увеличить норму прибыли при производстве шкафа на 160 у.е. 3. Уменьшить норму прибыли при производстве тумбы на 40 у.е. 4. Уменьшить норму прибыли при производстве тумбы на 50 у.е. В некоторых случаях решение (Х 1 ,Х 2 ) не меняется, в других -изменяется. Как это объяснить с помощью данных таблицы "Изменяемые ячейки" отчета Excel об устойчивости? III. Для последнего случая (п. 1.4) сделайте новый отчет об устойчивости. Обратите внимание, что в колонке "Нормированная стоимость" таблицы "Изменяемые ячейки" для тумбы появилось отрицательное число. Попробуйте выяснить, что оно означает. Для этого увеличьте прибыль от продажи тумбы на величину, слегка превышающую по модулю это отрицательное число, и решите задачу еще раз. Что произошло? Каков смысл данных в колонке "Нормированная стоимость" таблицы "Изменяемые ячейки" отчета Excel об устойчивости? Если продукт входит в оптимальный план, в колонке "Нормированная стоимость" отчета об устойчивости для этого продукта стоит 0. Если продукт не входит в оптимальный план, в этой колонке стоит отрицательное число, показывающее, на сколько (по абсолютной величине) нужно увеличить прибыль от производства единицы этого продукта, чтобы он вошел в оптимальный план. 3.2. Двойственная задача. Теневые цены Для любой задачи линейного программирования можно сформулировать задачу-двойник, или, иначе, двойственную задачу. Эта задача-двойник является своеобразным ''зеркальным отражением‖ исходной задачи, поскольку ее формулировка использует те же параметры, что и исходная задача, а ее решение может быть получено одновременно с решением исходной задачи. Фактически при решении исходной задачи симплекс-методом одновременно решается и двойственная задача, и наоборот. Следует также отметить, что исходная и двойственная задачи совершенно симметричны. Если двойственную задачу рассматривать как исходную, то исходная будет для нее двойственной. Одной из важнейших "зеркальных" связей между исходной и двойственной задачами является связь "переменные решения - теневые цены ресурсов". Для того чтобы уловить эту связь, сформулируем содержательно двойственную задачу к знакомой нам задаче об оптимальном плане выпуска продукции мебельного цеха. Постановка двойственной задачи к задаче об оптимальном плане выпуска продукции мебельного цеха Пусть имеется покупатель на все ресурсы, используемые для выпуска продукции мебельного цеха (ДСП, стекло и труд). Таблица параметров та же, что и для исходной задачи (табл. 5). Какие цены на эти ресурсы нужно назначить, чтобы продать их было выгоднее, чем производить продукцию? Какую минимальную сумму можно выручить от продажи ресурсов при этом условии? Таблица 5 Параметры задачи Ресурсы Запасы Продукты Шкаф Тумба ДСП 350 3,5 1 Стекло 240 1 2 Труд 150 1 1 Прибыль 200 100 Поскольку в этой задаче три вида ресурсов, то переменных решения, очевидно, должно быть тоже три. Это цены, которые назначает производитель при продаже, 1 м ДСП Y 1 , 1 м стекла Y 2 , 1 дня труда рабочего цеха - Y 3 . Сразу заметим, что эти цены называются теневыми. Они, разумеется, не могут иметь никакого отношения к рыночным ценам на данные ресурсы, поскольку, как будет видно из решения, никаких рыночных (или внерыночных) механизмов формирования цен на данные ресурсы в решении не рассматривается. Теневые цены характеризуют ценность ресурсов для производителя. Целевая функция - это, очевидно, прибыль, которую получит производитель - продавец ресурсов, если продаст по этим ценам все имеющиеся ресурсы. Таким образом, целевая функция, записанная в таблице элементов модели, - это сумма произведений искомых цен Y 1 , Y 2 , Y 3 на запасы имеющихся ресурсов, приведенных в соответствующем столбце таблицы параметров задачи. Разумеется, интерес продавца ресурсов состоит в том, чтобы продать их подороже. Однако интерес покупателя в том, чтобы купить подешевле. Решение данной задачи позволит продавцу определить нижние границы цен на ресурсы, которые он может назначить, чтобы прибыль от их продажи была не ниже, чем прибыль от производства товаров на основе этих ресурсов. Целевую функцию данной задачи можно также рассматривать как издержки покупателя ресурсов, которые необходимо минимизировать, приняв во внимание интересы производителя - продавца ресурсов. Цель производителя - продавца ресурсов - найти минимальное значение суммарной выручки от продажи всех ресурсов при условии, что продать их было бы не менее выгодно, чем производить из них продукцию. Соответственно при записи ограничений в таблице элементов модели (табл. 6) использован тот же принцип. Если производить (продавец ресурсов) хочет продать 3,5 м ДСП, 1 м стекла и I день труда рабочего, то он должен получить не меньше, чем прибыль от производства одного шкафа (на который, согласно данным таблицы параметров, и идут все эти ресурсы). Аналогично если он хочет продать 1 м ДСП, 2 м стекла и 1 день труда рабочего он должен получить не меньше, чем прибыль от производства одной тумбы. Таблица 6 Элементы модели Переменные решения Целевая функция Y 1 – цена 1 м ДСП Y 2 – цена 1 м стекла Y 2 – цена 1дня труда рабочего цеха C=350Y 1 +240Y 2 +150Y 3 Ограничения 3,5Y 1 +1Y 2 +1Y 3 ≥200 1Y 1 +2Y 2 +1Y 3 ≥200 Y 1 , Y 2 , Y 3 ≥0 Симметрия исходной и двойственной задач хорошо видна из исходной таблицы параметров и элементов решения этих двух задач (табл. 7). Как видно из этой таблицы, в исходной задаче две переменные и три ограничения; в двойственной – наоборот: три переменные и два ограничения. Исходная задача – это задача на максимум прибыли производителя продуктов; двойственная – на минимум издержек покупателя ресурсов. Целевая функция исходная задача формируется как сумма произведений строки переменных (количеств продуктов разного типа Х 1 ,Х 2 ) на строку прибылей от производства единицы каждого продута; целевая функция двойственной задачи – как сумма произведений столбца переменных (теневых цен ресурсов Y 1 , Y 2 , Y 3 ) на столбец запасов этих ресурсов. Аналогично ограничение на расходы каждого из используемых ресурсов в исходной задаче формируется как сумма произведений строки переменных (X 1 , X 2 ) на расход данного ресурса при производстве единиц каждого продукта. Ограничение на выручку от продажи ресурсов, идущих на производство данного продукта в двойственной задаче, формируется как сумма произведений столбца переменных решений (Y 1 , Y 2 , Y 3 ) на столбец расходов каждого из используемых ресурсов на производство единицы данного продукта. Эта симметрия проявляется и при сопоставлении более общих формулировок исходной и двойственной задач, когда n продуктов может быть произведено из m ресурсов (вкладка 1). Здесь матрица {a ij } может быть интерпретирована как расход каждого i-го ресурса на единицу j-го продукта. Строка целевых коэффициентов c j тогда представляет собой величину прибыли на единицу j-го продукта. Строка переменных X j – количество производимых единиц j-го продукта. |