- Главная
- Математика
- Нелинейное программирование
Содержание
- 2. История разработки основных методов нелинейного программирования Научно-техническая революция привела к существенным преобразованиям в организационном управлении. Усложнение
- 3. На развитом предприятии владелец или лицо, управляющее им, не может самостоятельно принять решения - слишком большое
- 4. Наука, которая занимается управлением, называется кибернетикой. Теория операций - часть кибернетики. Иногда ее называют операционной кибернетикой.
- 5. Цели, задачи и актуальность методов нелинейного программирования Нелинейное программирование применяется при прогнозировании промышленного производства, управлении товарными
- 6. При решении задач нелинейного программирования для целевой функции необходимо определить глобальный максимум или глобальный минимум. Глобальный
- 7. 3. В нелинейных программах возникает проблема поиска глобального экстремума среди множества локальных. Как мы показали ранее,
- 8. Методы выпуклого программирования. Метод множителей Лагранжа Методы выпуклого программирования, реализующие поиск минимума выпуклой функции или максимума
- 9. Можно доказать, что необходимым условием экстремума исходной задачи является обращение в нуль всех частных производных функции
- 10. Метод Гаусса-Зейделя Одним из самых распространенных итерационных методов, отличающийся простотой и легкостью программирования, является метод Гаусса-Зейделя.
- 11. Зададим некоторые начальные (нулевые) приближения значений неизвестных: Подставляя эти значения в правую часть выражения (3.9.2), получаем
- 12. Итерационный процесс продолжается до тех пор, пока значения х1(k), х2(k)и х3(k)не станут близкими с заданной погрешностью
- 13. Области применения методов нелинейного программирования Задача нелинейного программирования встречается в естественных науках, технике, экономике, математике, в
- 14. Результаты решения задачи нелинейного программирования являются подспорьем при принятии государственных решений. Полученное решение является, естественно, рекомендуемым,
- 15. Графический метод решения задач нелинейного программирования Графический метод можно использовать для решения задачи нелинейного программирования(НП), которая
- 16. ПРИМЕР. В задаче выпуклого программирования требуется: найти решение графическим методом; написать функцию Лагранжа и найти ее
- 17. Затем строим функцию цели. В данном случае это окружность. Поскольку задача минимума, то ищем первое касание
- 18. 2) Найдем экстремум функции F(X) = x12+(x2-2)2: L(X, λ)=F(X)+∑(λi·φi) где F(X) - целевая функция вектора X;
- 19. б) для случая X2: x2 = λ1/2 + λ2 + 2; x1 = 5 - 2x2
- 20. ПРИМЕР. Фирма выпускает два вида изделий А и В, которые обрабатываются на станках двух типов. Известны
- 21. Решение: 1. Построение математической модели В рассматриваемой задаче следует определить х1 — план выпуска изделий А;
- 22. Найдем первые частные производные ЦФ: и , а затем ее вторые частные производные: ; ; .
- 23. Значения этих миноров не зависят от точки х = (x1, x2), причем минор первого (нечетного) порядка
- 24. Шаг 2. Согласно схеме обобщенного метода множителей Лагранжа решим задачу максимизации ЦФ («задача 2.2») с учетом
- 25. Найденная точка х2 = (45, 35) является оптимальным решением задачи 2.2. Проверим, является ли она допустимой
- 26. Из первого уравнения имеем 4x1=320-6λ → x1=80-1.5λ, а из второго уравнения 4x2=280-2λ → x2=70-0.5λ, Подставив найденные
- 28. Скачать презентацию
Слайд 2История разработки основных методов нелинейного программирования
Научно-техническая революция привела к существенным преобразованиям в
История разработки основных методов нелинейного программирования
Научно-техническая революция привела к существенным преобразованиям в
Слайд 3На развитом предприятии владелец или лицо, управляющее им, не может самостоятельно принять
На развитом предприятии владелец или лицо, управляющее им, не может самостоятельно принять
Производственный отдел хочет, чтобы продукция была однообразной (мало номенклатуры), и, если даже нет сбыта, этот отдел хочет производить продукцию, его цель - как можно больше продукции узкой номенклатуры (чтобы не перенастраивать станки для удешевления продукции). Отдел сбыта требует широкой номенклатуры продукции (чтобы было легче продать), чтобы были товары, даже редко пользующиеся спросом (они могут понадобиться все равно). Поэтому этот отдел не возражает против запасов (если и производства нет). Однако, финансовый отдел выступает против запасов, так как это связанные деньги, и его задача минимизировать эти связанные деньги (т.е. деньги в товаре), а это значит минимизировать запасы. Финансовый отдел требует сохранения производства даже, если не идет продажа товара. Отдел кадров против сохранения производства, если продажа товара не идет, так как это связано с увольнением людей, что является очень неприятной процедурой.
Задача отдела исследования заключается в том, чтобы найти правильное решение, которое принесет пользу (выгоду) всей системе в целом (всей фирме в целом), а не отдельным его подразделениям.
Таким образом, исследование операций связано с организацией, управлением системами, т.е. с исследованием оказания влияния на системы с точки зрения повышения их эффективности.
Слайд 4Наука, которая занимается управлением, называется кибернетикой. Теория операций - часть кибернетики. Иногда
Наука, которая занимается управлением, называется кибернетикой. Теория операций - часть кибернетики. Иногда
Таблица 1
Классы задач и методы их решения
Слайд 5Цели, задачи и актуальность методов нелинейного программирования
Нелинейное программирование применяется при прогнозировании промышленного
Цели, задачи и актуальность методов нелинейного программирования
Нелинейное программирование применяется при прогнозировании промышленного
В задачах нелинейного программирования в отличие от линейных задач нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся:
· методы множителей Лагранжа,
· квадратичное и выпуклое программирование,
· градиентные методы,
· приближенные методы решения,
· графический метод.
Из нелинейного программирования наиболее разработаны задачи, в которых система ограничений линейная, а целевая функция нелинейная. Однако даже для таких задач оптимальное решение может быть найдено для определенного класса целевых функций. Например, когда целевая функция сепарабельная, т.е. является суммой п функций fj(xj), или квадратичная. При этом следует отметить, что в отличие от задач линейного программирования, где точками экстремума являются вершины многогранника решений, в задачах с нелинейной целевой функцией точки могут находиться внутри многогранника, на его ребре или в вершине.
Слайд 6При решении задач нелинейного программирования для целевой функции необходимо определить глобальный максимум
При решении задач нелинейного программирования для целевой функции необходимо определить глобальный максимум
Глобальный максимум (минимум) функции -- это ее наибольшее (наименьшее) значение из локальных максимумов (минимумов).
Наличие локальных экстремумов затрудняет решение задач, так как большинство существующих методов нелинейного программирования не позволяет установить, является найденный экстремум локальным или глобальным. Поэтому имеется возможность в качестве оптимального решения принять локальный экстремум, который может существенно отличаться от глобального.
Специфика нелинейных программ и методы их решения
Многообразие методов решения линейных программ имеет в своей основе идею упорядоченного перебора опорных планов (вершин) исходной или сопряженной задачи.
Для нелинейных же программ простого метода решения, подобного cимплексному, нет по многим причинам.
1. Множество планов может оказаться невыпуклым или иметь бесконечное количество "вершин".
2. Искомые экстремумы могут достигаться как на границе множества планов, так и внутри его.
Слайд 73. В нелинейных программах возникает проблема поиска глобального экстремума среди множества локальных.
Как
3. В нелинейных программах возникает проблема поиска глобального экстремума среди множества локальных.
Как
Существующие методы нелинейного программирования можно подразделить на следующие основные классы.
Слайд 8Методы выпуклого программирования. Метод множителей Лагранжа
Методы выпуклого программирования, реализующие поиск минимума выпуклой
Методы выпуклого программирования. Метод множителей Лагранжа
Методы выпуклого программирования, реализующие поиск минимума выпуклой
Если множество планов - выпуклый многогранник, то эти методы допускают использование симплексного метода.
Наиболее эффективно эти и другие методы решения действуют для так называемых сепарабельных функций, т.е. функций, представимых в виде суммы функций одной переменной
F(X1, X2,..,Xn) = f1(X1) + f2(X2) +... + fn(Xn).
При решении многих задач нелинейного программирования определенный эффект дает метод множителей Лагранжа.
Пусть требуется найти экстремумы функции F(X) при условиях fi(X)=0 (i = 1.. m).
Функция называется функцией Лагранжа и коэффициенты ?i - множителями Лагранжа.
Можно доказать, что необходимым условием экстремума исходной задачи является обращение в нуль всех частных производных функции Лагранжа.
Слайд 9Можно доказать, что необходимым условием экстремума исходной задачи является обращение в нуль всех
Можно доказать, что необходимым условием экстремума исходной задачи является обращение в нуль всех
Например, при поиске максимума F(X1, X2) = X1+X2 при единственном условии X12+X22=1 строится функция Лагранжа
Строим систему уравнений
решение которой дает и экстремальные значения целевой функции.
Для определения типа найденного экстремума можно построить матрицу вторых производных F(X), вычисленных в экстремальной точке, и определить знаки главных ее миноров. Если все они положительны, то найден минимум; если они чередуются, начиная с минуса, то найден максимум (правило Сильвестра).
Сам по себе метод множителей Лагранжа не дает существенного эффекта из-за необходимости решать, как правило, нелинейную систему уравнений; не гарантирует тип отыскиваемого экстремума, кроме глобальных дает и множество локальных экстремумов, но полезен при генерации идей и создании методов нелинейного программирования.
Слайд 10Метод Гаусса-Зейделя
Одним из самых распространенных итерационных методов, отличающийся простотой и легкостью программирования,
Метод Гаусса-Зейделя
Одним из самых распространенных итерационных методов, отличающийся простотой и легкостью программирования,
Проиллюстрируем сначала этот метод па примере решения системы
Предположим, что диагональные элементы а11, а22, а33отличны от нуля (в противном случае можно переставить уравнения). Выразим неизвестные х1, х2и х3 соответственно из первого, второго и третьего уравнений системы (3.9.1):
(3.9.2)
(3.9.3)
(3.9.4)
Слайд 11Зададим некоторые начальные (нулевые) приближения значений неизвестных: Подставляя эти значения в правую
Зададим некоторые начальные (нулевые) приближения значений неизвестных: Подставляя эти значения в правую
Используя это значение для x1 и приближение для х3, находим из (3.9.3) первое приближение для х2:
И наконец, используя вычисленные значения находим с помощью выражения (3.9.4) первое приближение для х3:
На этом заканчивается первая итерация решения системы (3.9.2) - (3.9.4). Теперь с помощью значений х1(1), х2(1)их3(1)можно таким же способом провести вторую итерацию, в результате которой будут найдены вторые приближения к решению: х1 = х1 (2), х2 = х2(2)и х3 = х3(2)и т.д.
Приближение с номером kможно вычислить, зная приближение с номером k- 1, как
Слайд 12Итерационный процесс продолжается до тех пор, пока значения х1(k), х2(k)и х3(k)не станут близкими с заданной
Итерационный процесс продолжается до тех пор, пока значения х1(k), х2(k)и х3(k)не станут близкими с заданной
Слайд 13Области применения методов нелинейного программирования
Задача нелинейного программирования встречается в естественных науках, технике,
Области применения методов нелинейного программирования
Задача нелинейного программирования встречается в естественных науках, технике,
Нелинейное программирование, например, связано с основной экономической задачей. Так в задаче о распределении ограниченных ресурсов максимизируют либо эффективность, либо, если изучается потребитель, потребление при наличии ограничений, которые выражают условия недостатка ресурсов. В такой общей постановке математическая формулировка задачи может оказаться невозможной, но в конкретных применениях количественный вид всех функций может быть определен непосредственно. Например, промышленное предприятие производит изделия из пластмассы. Эффективность производства здесь оценивается прибылью, а ограничения интерпретируются как наличная рабочая сила, производственные площади, производительность оборудования и т.д.
Метод "затраты - эффективность" также укладывается в схему нелинейного программирования. Данный метод был разработан для использования при принятии решений в управлении государством. Общей функцией эффективности является благосостояние. Здесь возникают две задачи нелинейного программирования: первая - максимизация эффекта при ограниченных затратах, вторая - минимизация затрат при условии, чтобы эффект был выше некоторого минимального уровня. Обычно эта задача хорошо моделируется с помощью нелинейного программирования.
Слайд 14Результаты решения задачи нелинейного программирования являются подспорьем при принятии государственных решений. Полученное
Результаты решения задачи нелинейного программирования являются подспорьем при принятии государственных решений. Полученное
Задачи нелинейного программирования часто возникают и в других отраслях науки. Так, например, в физике целевой функцией может быть потенциальная энергия, а ограничениями - различные уравнения движения. В общественных науках и психологии возникает задача минимизации социальной напряженности, когда поведение людей ограничено определенными законами.
Преобразование реальной задачи в задачу нелинейного программирования является в значительной степени искусством, но это искусство направляется теорией.
Слайд 15Графический метод решения задач нелинейного программирования
Графический метод можно использовать для решения задачи нелинейного
Графический метод решения задач нелинейного программирования
Графический метод можно использовать для решения задачи нелинейного
Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:
1.Найти ОДР, определяемую ограничениями задачи. Если окажется, что эта область пуста, то это означает, что задача не имеет решения.
2.Построить семейство линий уровня целевой функции f(х1, х2) = C при различных значениях числового параметра С.
3.При решении задачи на минимум определить направление убывания, а для задачи на максимум — направление возрастания линий уровня ЦФ.
4.Найти точку ОДР, через которую проходит линия уровня с наименьшим в задаче на минимум (соответственно, наибольшим в задачи на максимум) значением параметра С.Эта точка будет оптимальным решением. Если ЦФ не ограничена снизу в задаче на минимум (сверху — в задаче на максимум), то это означает, что задача не имеет оптимального решения.
5.Найти координаты точки оптимума и определить в ней значение ЦФ.
Отметим, что в отличие от задачи ЛП точка оптимума в задаче НП не обязательно находится на границе ОДР. Ею также может быть внутренняя точка этого множества.
Слайд 16ПРИМЕР. В задаче выпуклого программирования требуется:
найти решение графическим методом;
написать функцию Лагранжа и
ПРИМЕР. В задаче выпуклого программирования требуется:
найти решение графическим методом;
написать функцию Лагранжа и
F(X) = x12+(x2-2)2 2x1+x2 ≥ 7 x1+2x2 ≥ 5
Решение. 1) Строим два ограничения, тем самым определяя ОДР.
Слайд 17Затем строим функцию цели. В данном случае это окружность.
Поскольку задача минимума, то
Затем строим функцию цели. В данном случае это окружность.
Поскольку задача минимума, то
Слайд 182) Найдем экстремум функции F(X) = x12+(x2-2)2:
L(X, λ)=F(X)+∑(λi·φi)
где F(X) - целевая функция вектора
2) Найдем экстремум функции F(X) = x12+(x2-2)2: L(X, λ)=F(X)+∑(λi·φi) где F(X) - целевая функция вектора
Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным хi и неопределенным множителям λ.
Составим систему:
∂L/∂x1 = 2*λ1+λ2+2*x1 = 0
∂L/∂x2 = λ1+2*λ2+2*x2-4 = 0
∂L/∂λ1 = 2*x1+x2-7 = 0
∂L/∂λ2 = x1+2*x2-5 = 0
Решив данную систему, получаем:
а) для случая X1: x1 = λ1/2 + λ2 + 2; x2 = 7 - 2x1
Откуда можно найти такие λ1 ≥ 0, λ2 ≥ 0. Пусть λ2 = 0. Тогда λ1 = 2; x1 = 2; x2 = 3.
Поскольку λ2 ≥ 0, то данное решение удовлетворяет условиям Куна-Таккера. Zmin(2;3)=5
Слайд 19б) для случая X2: x2 = λ1/2 + λ2 + 2; x1 = 5 -
б) для случая X2: x2 = λ1/2 + λ2 + 2; x1 = 5 -
Минимальное значение составит Zmin(2;3)=5.
Слайд 20ПРИМЕР. Фирма выпускает два вида изделий А и В, которые обрабатываются на
ПРИМЕР. Фирма выпускает два вида изделий А и В, которые обрабатываются на
Требуется:
1. Составить математическую модель нахождения оптимального плана выпуска продукции.
2. Определить оптимальный план выпуска обобщенным методом множителей Лагранжа и дать экономическую интерпретацию полученных результатов.
Слайд 21Решение:
1. Построение математической модели
В рассматриваемой задаче следует определить
х1 — план выпуска изделий А;
х2 — план
Решение: 1. Построение математической модели В рассматриваемой задаче следует определить х1 — план выпуска изделий А; х2 — план
Слайд 22Найдем первые частные производные ЦФ:
и ,
а затем ее вторые частные производные:
Найдем первые частные производные ЦФ:
и ,
а затем ее вторые частные производные:
;
;
.
Следовательно, гессиан Н функции f имеет следующий вид:
.
Главные миноры первого порядка равны –4, а главный минор второго порядка равен
= (-4)·(-4) – 0·0 = 16.
Слайд 23Значения этих миноров не зависят от точки х = (x1, x2), причем минор первого (нечетного)
Значения этих миноров не зависят от точки х = (x1, x2), причем минор первого (нечетного)
Отсюда, x11=80, x22=70. Таким образом, стационарная точка ЦФ — точка x1=(80,70). В силу вогнутости Z она является точкой ее глобального максимума. Поэтому, если окажется, что эта точка является допустимой в исходной задаче, то она будет ее точкой оптимума. Проверим выполнение ограничения (2):
2×80 + 2×70 = 160 + 140 = 300 > 160.
Найденная точка не является допустимой и, следовательно, не может являться оптимальным решением задачи (1) – (4).
Слайд 24Шаг 2. Согласно схеме обобщенного метода множителей Лагранжа решим задачу максимизации ЦФ
Шаг 2. Согласно схеме обобщенного метода множителей Лагранжа решим задачу максимизации ЦФ
Из первого уравнения имеем
4x1=320-2λ → x1=80-0.5λ,
а из второго уравнения
4x2=280-2λ → x2=70-0.5λ,
Подставив найденные выражения х1 и х2 от λ в третье уравнение, получим
160 – 2×(80 – 0.5λ) – 2×(70 – 0.5λ) = 0 → 2λ – 140 = 0 → λ = 70.
Тогда х1 = 80 – 70/2 = 45, а х2 = 70 – 70/2 = 35, т.е. решение системы:
x12 = 45, x22 = 35, λ2 = 70.
Слайд 25Найденная точка х2 = (45, 35) является оптимальным решением задачи 2.2. Проверим, является ли
Найденная точка х2 = (45, 35) является оптимальным решением задачи 2.2. Проверим, является ли
Слайд 26Из первого уравнения имеем
4x1=320-6λ → x1=80-1.5λ,
а из второго уравнения
4x2=280-2λ → x2=70-0.5λ,
Подставив найденные
Из первого уравнения имеем 4x1=320-6λ → x1=80-1.5λ, а из второго уравнения 4x2=280-2λ → x2=70-0.5λ, Подставив найденные
Итак, оптимальным решением является выпуск 20 изделий вида А и 50 изделий вида А. Реализация выпущенных изделий даст фирме максимальную прибыль, равную 14 600 руб. Выполнение этой производственной программы требует затрат 140 ст./час. из фонда рабочего времени станков первого типа и 220 ст./час. из фонда рабочего времени станков второго типа. Это означает, что первый вид оборудования недоиспользуется, а второй вид оборудования используется полностью.