Экономические приложения выпуклого программирования: числовые модели Содержание лекции: Градиентные методы решения задач выпуклого программирования Градиентные методы решения задач выпуклого программирования Градиентные методы решения задач выпуклого программирования Градиентные методы решения задач выпуклого программирования Линеаризация задач математического программирования Линеаризация задач математического программирования Линеаризация задач математического программирования Линеаризация задач математического программирования Прикладные модели нелинейного программирования Прикладные модели нелинейного программирования Прикладные модели нелинейного программирования Прикладные модели нелинейного программирования

Градиентные методы решения задач выпуклого программирования Градиент функции в данной точке – вектор, составленный из её частных производных по всем переменным в данной точке Направление градиента указывает направление, в котором функция растёт быстрее всего, а его модуль (длина, евклидова норма) характеризует скорость роста 2/ 17

1. Ограничения исходной ЗМП преобразуются в равенства – с помощью дополнительных переменных – условия неотрицательности переменных (если имелись) не преобразуются Метод наискорейшего спуска 3/ 17

Замечания 1. Процесс решения можно повторять, увеличивая Μ, чтобы достичь максимальной точности учёта ограничений при приемлемом числе итераций 2. Метод можно применять и для невыпуклых задач, но тогда нет гарантии отыскания глобального оптимума Если число оптимумов определено аналитически и все их удалось найти поиском с разных начальных точек, то глобальный оптимум определён Если число оптимумов определено аналитически и все их удалось найти поиском с разных начальных точек, то глобальный оптимум определён Это достигается далеко не всегда Это достигается далеко не всегда 3. Выполнение условий окончания поиска не гарантирует достижения окрестности оптимума Если задача выпуклая: Если задача выпуклая: переменные могут существенно отличаться от оптимальных значений, но отличие значения ц.ф. от оптимального будет невелико переменные могут существенно отличаться от оптимальных значений, но отличие значения ц.ф. от оптимального будет невелико можно повысить вероятность отыскания действительного оптимума, выполнив поиск с разных начальных точек и убедившись, что он сходится к одному и тому же решению можно повысить вероятность отыскания действительного оптимума, выполнив поиск с разных начальных точек и убедившись, что он сходится к одному и тому же решению Если нет, отличие ц.ф. от оптимального может быть значительным Если нет, отличие ц.ф. от оптимального может быть значительным 4. Существуют и другие градиентные методы Метод покоординатного спуска Метод покоординатного спуска Метод сопряжённых градиентов Метод сопряжённых градиентов квази-Ньютоновский квази-Ньютоновский etc. etc. 4/ 17

Программное обеспечение квази-Ньютоновский метод сопряжённых градиентов генетический алгоритм (Excel 2010) MS Excel квази-Ньютоновский метод сопряжённых градиентов метод Левенберга-Марквардта MathCad GAMS SNOPT Те же плюс Последовательное квадратичное программирование Метод конечных приращений Лагранжа R etc. 5/ 17

Линеаризация задач математического программирования После замены функций z(x) и q(x) кусочно-линейными функциями: задачи выпуклого программирования можно решать с помощью обычного симплекс- метода задачи выпуклого программирования можно решать с помощью обычного симплекс- метода некоторые виды невыпуклых задач можно решать с помощью некоторые виды невыпуклых задач можно решать с помощью целочисленного программирования целочисленного программирования специальной разновидности симплексного метода сепарабельного программирования специальной разновидности симплексного метода сепарабельного программирования возникающая при этом ошибка тем меньше, чем меньше длины отрезков кусочно-линейных функций возникающая при этом ошибка тем меньше, чем меньше длины отрезков кусочно-линейных функций зато тем больше будет ограничений в получившейся ЗМП зато тем больше будет ограничений в получившейся ЗМП Процесс линеаризации может оказаться весьма трудоёмким. Задачи со значительным количеством переменных и нелинейных ограничений намного эффективнее решать градиентными методами. 6/ 17

Процесс линеаризации выпуклых ограничений (на примере ограничения i ) 1. Выбирается достаточное количество точек x ik таких, что q i (x ik )=b i. 2. Составляются линейные уравнения гиперплоскостей, проходящих через каждый набор из n ближайших друг к другу точек x ik (n число переменных исходной задачи). 3. Если ограничение i неравенство, получившиеся линейные уравнения тоже трансформируются в неравенства таким образом, чтобы (почти) все точки, удовлетворяющие новому линейному неравенству, удовлетворяли бы и исходному неравенству i. таким образом, чтобы (почти) все точки, удовлетворяющие новому линейному неравенству, удовлетворяли бы и исходному неравенству i. 4. Ограничение i заменяется множеством получившихся линейных неравенств. 7/ 17

8/ 17 Пример целочисленного представления невыпуклой области Сепарабельное представление Последнее ограничение «держит» всегда, среднее – только при x3=0, первое – только при x4=0. "Тысяча" может быть любым числом, превышающим коэффициент при той же переменной в другом уравнении. Пример сепарабельного представления невыпуклой области

Прикладные модели нелинейного программирования Учёт эффекта масштаба Учёт эффекта масштаба Моделирование рынка: зависимость цены от расстояния Моделирование рынка: зависимость цены от расстояния Олигопольные рынки: зависимость цены от объёма поставок Олигопольные рынки: зависимость цены от объёма поставок 9/ 17

Учёт эффекта масштаба Для производства двух видов продукции используется единственный ресурс. Найти план производства, обеспечивающий максимальную прибыль, при следующих условиях: Цены продуктов – 10 и 20 у.е.; ресурса – 0,03 у.е. Цены продуктов – 10 и 20 у.е.; ресурса – 0,03 у.е. Расход ресурса на выпуск каждого продукта при объёме выпуска 100 ед. – соответственно 80 и 150 ед. Расход ресурса на выпуск каждого продукта при объёме выпуска 100 ед. – соответственно 80 и 150 ед. При увеличении объёма производства первого продукта на 1% удельный расход ресурса возрастает на 0,05%, второго – на 0,1% При увеличении объёма производства первого продукта на 1% удельный расход ресурса возрастает на 0,05%, второго – на 0,1% Минимально возможный объём производства продуктов – соответственно 90 и 80 ед. Минимально возможный объём производства продуктов – соответственно 90 и 80 ед. Имеется ед. ресурса Имеется ед. ресурса Удельный расход ресурса при выпуске 100 ед. продукта 1: 80/100 = 0,8 ед.р./ед.пр.1 При выпуске 101 ед.: 0,8*1,0005 = 0,8004 ед.р./ед.пр.1 Валовые затраты при выпуске 101 ед.пр.1: 0,8004·101=80,8404 ед.р. При выпуске 100 ед. продукта 2: 150/100 = 1,5 ед.р./ед.пр.2 При выпуске 101 ед.: 1,5*1,001 = 1,5015 ед.р./ед.пр.2 Валовые затраты при выпуске 101 ед.пр.2: 1,5015·101=151,6515 ед.р. Удельный расход ресурса при выпуске 100 ед. продукта 1: 80/100 = 0,8 ед.р./ед.пр.1 При выпуске 101 ед.: 0,8*1,0005 = 0,8004 ед.р./ед.пр.1 Валовые затраты при выпуске 101 ед.пр.1: 0,8004·101=80,8404 ед.р. При выпуске 100 ед. продукта 2: 150/100 = 1,5 ед.р./ед.пр.2 При выпуске 101 ед.: 1,5*1,001 = 1,5015 ед.р./ед.пр.2 Валовые затраты при выпуске 101 ед.пр.2: 1,5015·101=151,6515 ед.р. 10/ 17

Учёт эффекта масштаба Для производства двух видов продукции используется единственный ресурс. Найти план производства, обеспечивающий максимальную прибыль, при следующих условиях: Цены продуктов – 10 и 20 у.е.; ресурса – 0,03 у.е. Цены продуктов – 10 и 20 у.е.; ресурса – 0,03 у.е. Расход ресурса на выпуск каждого продукта при объёме выпуска 100 ед. – соответственно 80 и 150 ед. Расход ресурса на выпуск каждого продукта при объёме выпуска 100 ед. – соответственно 80 и 150 ед. При увеличении объёма производства первого продукта на 1% удельный расход ресурса возрастает на 0,05%, второго – на 0,1% При увеличении объёма производства первого продукта на 1% удельный расход ресурса возрастает на 0,05%, второго – на 0,1% Минимально возможный объём производства продуктов – соответственно 90 и 80 ед. Минимально возможный объём производства продуктов – соответственно 90 и 80 ед. Имеется ед. ресурса Имеется ед. ресурса (100 -0,1 1,50 (100 -0,1 )·1,50 11/ 17

Учёт эффекта масштаба Вывод формулы (100 -0,1 )·1,50 Известно, что a·x 2 0,1 = 1,5 при x 2 = 100 Найти a a = 1,5 / (x 2 0,1 ) = 1,5·100 -0,1 8.3 Экономические приложения выпуклого программирования: числовые модели © Н.М. Светлов, / 17

13/ 17

Зависимость цены от расстояния Для производства двух видов продукции используется единственный ресурс. Найти план производства, обеспечивающий максимальную прибыль, при следующих условиях: Продукция реализуется на заключённой в окружность площади, пропорциональной объёму производства, из расчёта 15 и 20 единиц продукции первого и второго вида на 1 км 2 Продукция реализуется на заключённой в окружность площади, пропорциональной объёму производства, из расчёта 15 и 20 единиц продукции первого и второго вида на 1 км 2 Доставка к местам реализации осуществляется по прямой согласно тарифу 1,5 у.е. за 1 км Доставка к местам реализации осуществляется по прямой согласно тарифу 1,5 у.е. за 1 км Цена реализации продукции первого вида растёт с расстоянием согласно закону (5+0,5d), а второго – (10+0,5d) у.е., где d – расстояние в километрах. Цена реализации продукции первого вида растёт с расстоянием согласно закону (5+0,5d), а второго – (10+0,5d) у.е., где d – расстояние в километрах. Затраты ресурса на продукцию – 10 и 25 единиц. Затраты ресурса на продукцию – 10 и 25 единиц. Имеется 10 млн. единиц ресурса. Имеется 10 млн. единиц ресурса. 14/ 17

Зависимость цены от расстояния Для производства двух видов продукции используется единственный ресурс. Найти план производства, обеспечивающий максимальную прибыль, при следующих условиях: Продукция реализуется на заключённой в окружность площади, пропорциональной объёму производства, из расчёта 15 и 20 единиц продукции первого и второго вида на 1 км 2 Продукция реализуется на заключённой в окружность площади, пропорциональной объёму производства, из расчёта 15 и 20 единиц продукции первого и второго вида на 1 км 2 Доставка к местам реализации осуществляется по прямой согласно тарифу 1,5 у.е. за 1 км Доставка к местам реализации осуществляется по прямой согласно тарифу 1,5 у.е. за 1 км Цена реализации продукции первого вида растёт с расстоянием согласно закону (5+0,5d), а второго – (10+0,5d) у.е., где d – расстояние в километрах. Цена реализации продукции первого вида растёт с расстоянием согласно закону (5+0,5d), а второго – (10+0,5d) у.е., где d – расстояние в километрах. Затраты ресурса на продукцию – 10 и 25 единиц. Затраты ресурса на продукцию – 10 и 25 единиц. Имеется 10 млн. единиц ресурса. Имеется 10 млн. единиц ресурса. Задача не выпуклая! Ограничения 2 и 3 вогнуты 15/ 17