Графический метод решения задач математического программирования 1. Общий вид задачи математического программирования Z = F(X) >min Z = F(X) >min g i (x 1,x 2,…,х n ) 0 h j (x 1,x 2,…,x n ) = 0 h j (x 1,x 2,…,x n ) = 0 2. Методы решения задач математического программирования Графический метод; Графический метод; Аналитические методы; Аналитические методы; Численные методы. Численные методы.

Графический метод решения задач математического программирования 3. Графическая интерпретация задачи математического программирования. 3. Графическая интерпретация задачи математического программирования. Пространство переменных одномерно. Пространство переменных одномерно. F(x) > max/min a x b Необходимо найти экстремум функции F(x) на отрезке [a,b]. Пространство переменных двумерно. Пространство переменных двумерно. F(x 1,x 2 ) > max/min g i (x 1,x 2 ) 0 h j (x 1,x 2 ) = 0 Необходимо найти экстремум функции F на части плоскости.

Графический метод решения задач математического программирования Графическая интерпретация задачи. Графическая интерпретация задачи. Условие задачи: Х 1 2 – х 2 2 >min -10x x 2 10 График целевой функцииКарта линий уровня задачи Определение. Градиентом функции f(x 1, x 2,…,x n ) в точке X 0 =(x 0 1, x 0 2,…,x 0 n ) называется вектор, компонентами которого являются частные производные функции f по всем переменным :

Графический метод решения задачи математического программирования Свойства вектора – градиента Свойства вектора – градиента Указывает направление максимального возрастания функции Указывает направление максимального возрастания функции f(x 1, x 2,…,x n ) в точке X 0 =(x 0 1, x 0 2,…,x 0 n ) Модуль вектора-градиента соответствует абсолютному значению скорости возрастания функции Является нормалью к касательной плоскости, проведенной к поверхности уровня в точке X 0 =(x 0 1, x 0 2,…,x 0 n ). Перечисленные свойства положены в основу графического метода решения задач МП.

Графический метод решения задачи математического программирования 3. Пример решения задачи линейного программирования. 3. Пример решения задачи линейного программирования.Задача. Ограничения: Спрос на продукцию Р 1 не превосходит спрос на продукцию Р 2 более чем на 5 Спрос на продукцию Р 2 4; Найти: План выпуска продукции, который обеспечивает максимальную выручку от реализации Ресурсы Расходы сырья на 1ед. Продукции Запасы сырья Р1Р1Р1Р1 Р2Р2Р2Р2 Сырье1314 Труд4226 Цена продукции 33

Графический метод решения задач математического программирования Формализация задачи: Формализация задачи: Z =3x 1 + 3x 2 > Max x 1 + 3x 2 14(1) 4x 1 + 2x 2 26(2) x 1 – x 2 5(3) x 2 4(4) x 1 0; x 2 0(5) Ресурсы Расходы сырья на 1ед. Продукции Запасы сырья Р1Р1Р1Р1 Р2Р2Р2Р2 Сырье1314 Труд4226 Цена продукции 33

Графический метод решения задач математического программирования 0 x1x1 x2x (4) (1) 6.50 (3)(3) (2)(2) A B H C D E Шаг 1. Построение области допустимых значений для x 1 и x 2 Шаг 2. Проводится прямая (5) вдоль направления: V=grad(Z)={3, 3} Шаг 3. Проводится прямая (6) перпендикулярная прямой (5) Шаг 4. Прямая (6) перемещается по прямой (5) до верхней точки касания с областью Grad(Z) (5) (6)

Графический метод решения задач математического программирования В данном случае решением задачи является точка С Ее координаты x 1 и x 2 можно снять из графика или вычислить из условия, что решение – координаты точки пересечения прямых (1) и (2) Имеем систему уравнений: Решение есть: x 1 =5, x 2 =3 Таким образом, максимальная выручка равна Z=24 при выпуске продукции х 1 =5 единиц, а продукции х 2 =3 единицы

Графический метод решения задач математического программирования Замечание. В общем случае задачи МП направление и модуль вектора-градиента зависит от точки области Графическая иллюстрация позволяет показать возможные решения задач математического программирования А В Grad(Z) Бесконечное множество решений Решения нет Решение внутри области

Оценка устойчивости решения Устойчивость – важная характеристика решения задачи Определение. Решение считается устойчивым, если малые изменения ограничений приводят к малым изменениям решения. В случае задачи математического программирования, устойчивость это сохранение структуры решения при небольших изменениях ограничений. В рассмотренном примере решение лежит на пересечении границ (1) и (2) Именно эти ограничения определяют структуру оптимального решения.

Оценка устойчивости решения При анализе устойчивости оптимизационной модели определяются пределы изменения параметров модели, при которых остается неизменной качественная структура решения Если решение неустойчиво, то им нельзя пользоваться Основными параметрами задачи являются правые части ограничений и коэффициенты целевой функции

Оценка устойчивости решения Анализ устойчивости позволяет ответить на ряд практически важных вопросов: - на сколько могут быть снижены запасы дефицитных ресурсов при сохранении общей структуры решения - на сколько могут быть увеличены запасы дефицитных ресурсов с целью повышения эффективности экономической системы - на сколько можно снизить запасы не дефицитных ресурсов при сохранении эффективности экономической системы

Оценка устойчивости решения Провести оценку возможных изменений всех параметров модели одновременно не возможно, т.к. параметры связаны между собой Оценка устойчивости проводят для каждого параметра отдельно Для задачи с двумя переменными оценку устойчивости можно провести графически Алгоритм исследования продемонстрируем на рассмотренном примере

Оценка устойчивости решения Шаг 1. Определяются те ресурсы, которые являются дефицитными. В нашем случае это те ресурсы, которые определяют структуру оптимального решения: ресурсы, определяющие положение прямых (1) и (2), т.к. на их пересечении лежит оптимальное решение Определение. Ограничения, которые определяют структуру оптимального решения называются связывающими Остальные ограничения – не связывающие Неизменность качественной структуры решения предполагает неизменность типов ограничений задачи

Оценка устойчивости решения 0 x1x1 x2x2 (4) (1) 6.50 (3)(3) (2)(2) A B H C D E Начнем с ресурса х 1 «Сырье» При увеличении ресурса х 1 прямая (1) будет перемещаться вверх Структура решения сохраняется при перемещении (1) до точки Н При дальнейшем перемещении оптимальным решением будет пересечение прямых (2) и (4) 5.0

Оценка устойчивости решения Значения ресурсов х 1 и х 2 можно снять с графика или вычислить из системы уравнений: Откуда получаем х 1 =4.5; х 2 =4 Подставляя, полученные значения х 1 и х 2 в ограничение (1) получим верхний предел запаса ресурса «Сырье» x 1 + 3x 2 14(1) ·4 = ·4 = 16.5 Таким образом, ресурс «Сырье» можно увеличить на 2.5 единицы без изменения структуры оптимального решения. Эффективность системы при этом возрастет на 1.5 единицы (Z=25.5)

Оценка устойчивости решения Аналогичным образом можно определить нижний предел ресурса «Сырье» при сохранении структуры решения 0 x1x1 x2x2 (4) (1) 6.50 (3)(3) (2)(2) A B H D E Прямую (1) опускаем до точки D. Ниже нее связывающими ограничениями становятся (1) и (3) Координаты х 1 и х 2 находятся из решения системы уравнений Откуда: х 1 =6; х 2 =1 «Сырье» 1·6+3·1=9 Z=3·6+3·1=21

Оценка устойчивости решения 0 x2x2 (1) 6.50 (3)(3) (2)(2) A B D E Аналогично определяются допустимые пределы изменения ресурса «Труд» L Прямую (2) можно перемещать между точками В и L. В точке В имеем x1=2; х2=4; Z=18 «Труд» - 16 В точке L: X1=7,25; x2=2.25; Z=28.5 «Труд»

Оценка устойчивости решения Определение. Ценностью ресурса называется отношение: С=ΔZ/ΔR где ΔR – диапазон изменения ресурса при сохранении структуры решения В данном примере: Показатель ценности ресурсов играют важную роль при определении приоритетов увеличении запасов ресурсов В первую очередь увеличивают ресурсы с большей ценностью

Оценка устойчивости решения Пределы изменения недефицитных ресурсов Спрос 1. задается ограничением (3). 0 x2x2 (1) 6.50 (3)(3) (2)(2) A B D E 5.0 L С Возможное уменьшение ресурса «Спрос 1» определяется положением (3-1) Предельное значение ресурса находится из равенства (3) подстановкой координат точки C {5,3}: x 1 -x 2 =5-3=2 Аналогично находится нижний предел ресурса «Спрос 2» x 2 =3 (3-1)

Оценка устойчивости решения Ресурс Тип ресурса Значение ресурса Пределы изменения ресурса Изменения ЦФ Ценность ресурса Сырье Дефи- цитный 14 9 – – Труд Дефи- цитный – – Спрос 1 Недефи- цитный – 5 0 Спрос 2 Недефи- цитный Результаты исследования на устойчивость