Программирование
<<  Разработка основной образовательной программы основного общего образования Концептуальная информатика и терминосистемы в информатике: проблемно-ориентированный анализ  >>
Аналитический метод решения задач математического программирования
Аналитический метод решения задач математического программирования
Аналитическое решение задач математического программирования
Аналитическое решение задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задачи математического программирования
Аналитические методы решения задачи математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования
Аналитические методы решения задач математического программирования

Презентация на тему: «Аналитический метод решения задач математического программирования». Автор: Администратор. Файл: «Аналитический метод решения задач математического программирования.ppt». Размер zip-архива: 195 КБ.

Аналитический метод решения задач математического программирования

содержание презентации «Аналитический метод решения задач математического программирования.ppt»
СлайдТекст
1 Аналитический метод решения задач математического программирования

Аналитический метод решения задач математического программирования

2 Аналитическое решение задач математического программирования

Аналитическое решение задач математического программирования

1. Метод неопределенных множителей Лагранжа. Пусть задача имеет вид: Z = F(X) ?> min ?(X) ?0 (3.1) X={x1, x2,…,xn} Определение. Функция L(x1, x2,…,xn, ?1,?2,…,?n) =F(x1, x2,…,xn) + ??i ? i(X), где ?1,?2,…,?n множители Лагранжа называется функцией Лагранжа задачи (3.1). Определение. Седловой точкой функции Лагранжа задачи математического программирования называется точка (X*,?*) в пространстве переменных размерностью (N*M), в которой для функции Лагранжа выполняются условия: L (X,?*)? L (X*,?*)? L (X*,?) для всех X?0 и ? ?0

(3.2)

3 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

2. Необходимое условие экстремума функции Лагранжа есть:

Дифференцируя (3.2) по всем переменным получим соотношения:

(3.3)

Соотношения (3.3) удобно представить в виде системы уравнений дополняющих нежесткостей:

(3.4)

4 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

Теорема. Если функция Лагранжа задачи (3.1) имеет седловую точку (X*, ?*), в неотрицательном ортанте xi? 0, ?i ? 0, то вектор Х* является решением этой задачи.

5 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

5. Примеры решения задач. Задача 1. Я собираюсь разместить 100 ден. ед. в банк. Банк предлагает два вида срочных вкладов: - сроком на 1 год под 20% годовых - сроком на 2 года под 25% годовых Мои предпочтения в использовании денег описываются функцией полезности: Z = F(x) = (3/5)tln(x) где: t – период времени использования денег; х – сумма денег. Вопрос. Как мне с большей пользой распорядиться деньгами?

6 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

Задача 1. (Решение) 1.1. Формализация задачи. Пусть х1 и х2 суммы денег, которые я предполагаю разместить по вкладам 1 и 2. Размеры вкладов ограничены моим ресурсом: х1 + х2 ? 100 Как я могу воспользоваться деньгами: при t =0, (100 - х1 - х2) с пользой z0 =(3/5)0ln (100 - х1 - х2); при t =1, (1+0.2)*х1 с пользой z1 =(3/5)1ln(1.2x1); при t =2, (1+0.25)2*x2 с пользой z2 =(3/5)2ln(1.5625x2)

В результате задача принимает вид:

7 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

Задача 1.(Решение, продолжение) Функция Лагранжа имеет вид:

(3.3)

Составляются уравнения дополняющих нежесткостей в виде:

Из вида функции следуют следующие ограничения: x1>0; x2>0; (x1+х2-100) >0 откуда – ?=0 Решение системы уравнений (3.3) есть: X1 =30.61; x2 =18.37; x0=51.02; ?=0

8 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

Задача 2. (Ограничения равенства) Предприятию на двух участках необходимо изготовить 20 изделий. Затраты на изготовление Х1 изделий на участке 1 есть 5*Х12(руб), а на изготовление Х2 изделий на участке 2 – 10Х2+5Х22(руб). Найти план выпуска изделий с минимальными затратами.

9 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

Задача 2. (Решение) Формализация задачи. Z=F(x1,x2) = 5*Х12 + 10Х2+5Х22 ?> min х1+x2 = 20 (ограничение 1) x1?0; x2 ?0; Ограничение 1 заменяется на два: х1+x2 – 20 ? 0 -х1 -x2 + 20 ? 0

10 Аналитические методы решения задачи математического программирования

Аналитические методы решения задачи математического программирования

Задача 2.(Продолжение решения) Функция Лагранжа задачи имеет вид: L(x1,x2,?1,?2) = 5*Х12 +10Х2+5Х22 + ?1(х1+x2 –20) + ?2(-х1-x2+20) Уравнения дополняющих нежесткостей: х1(10x1 + ?1 – ?2) = 0 х2(10x2 + 10 + ?1 – ?2) =0 ?1(х1+x2 – 20) = 0 -?2(х1+x2 – 20) = 0 ? 1>0 и ?2>0, т.к по условию (х1+x2 – 20) = 0

11 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

Задача 2. (Продолжение решения) Складывая последние два уравнения, получим: (?1 - ?2) (х1+x2 – 20) = 0 Рассматриваем два случая:

Случай 2. (?1 - ?2) ? 0. Тогда

Случай 1. (?1 - ?2) = 0. Тогда

х1(10x1 + ?1 – ?2) = 0 х2(10x2 + 10 + ?1 – ?2) =0 (х1+x2 – 20) = 0 Если х1>0; x2>0, то имеем (10x1 + ?1 – ?2) = 0 (10x2 + 10 + ?1 – ?2)=0 (х1+x2 – 20) = 0 Вычитая из первого уравнения второе, получим: 10х1 -10х2 = 10 х1 = 10.5 x1 + х2 = 20 х2 = 9.5

х1(10x1 ) = 0 х2(10x2 + 10) =0 10x1 = 0 10x2 + 10 = 0, или x1 = 0 x2 = -10 (Не удовлетворяет смыслу задачи)

12 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

4. Теорема Куна-Таккера. Теорема формулирует необходимые условия существования решения задачи МП. Теорема. Точка Х* может являться решением задачи математического программирования F(X) ?min/max gi(X)?0 при i=1,2,…,m hj(X)=0 при j=1,2,…,k если в ней выполняются следующие условия: 1. Условие стационарности: grad(gi(X*,?,?)=0 2. Условие дополняющих нежесткостей: ?igi(X*)=0 4. Условия принадлежности решения границе: hj(X) = 0 4. Условие нетривиальности: все ?i и ?j ? 0 При этом: ?i ?0 соответствует минимуму целевой функции; ?i ?0 соответствует максимуму целевой функции.

13 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

3. Экономический смысл множителей Лагранжа. 3.1. Качественная интерпретация множителя Лагранжа. ?i*?i(x1,x2,…,xn)=0 -условие дополняющей нежесткостей. ? i ? 0 - оптимальное решение лежит на границе ?i(x1,x2,…,xn)=0 Экономический смысл – i-ый ресурс расходуется полностью. Его увеличение приведет к повышению эффективности системы. ? i = 0 – оптимальное решение не принадлежит границе ?i(x1,x2,…,xn)=0 Экономический смысл – запас i-го ресурса избыточен. Его уменьшение не приведет к снижению эффективности системы.

14 Аналитические методы решения задач математического программирования

Аналитические методы решения задач математического программирования

3.2. Количественная интерпретация множителя Лагранжа. Зависит от контекста экономической задачи. Пример. Задача об оптимизации выпуска продукции. ? i > 0 означает, что данный ресурс будет израсходован полностью и это огра- ничивает повышение производства. Вопрос. Как изменится оптимальное решение при небольшом изменении запаса этого ресурса? Тогда: Х={x1(b),x(b),…,xn(b)}; F(X)=F(X(b)=F(b); ?(X(b))=?(b) dF/dbi =?(dF/dxi)(dxi/dbi); d?/dbi=?(d?/dxi)(dxi/dbi) В седловой точке: L(X(b), ?) =F(X(b)); dF(X*)/dbi = ?i* Прирост производства за счет увеличения ресурса bi пропорционален ?i. dF = ?i*dbi одновременно dF = сi*dbi Если сi цена ресурса i, то увеличение его запаса выгодно, если ?idbi>cidbi ?i – предельная цена ресурса, при которой производство остается прибыльным.

F(X) ?> max ?i(x)? bi xi ? 0, i=1,2,…,n

«Аналитический метод решения задач математического программирования»
http://900igr.net/prezentacija/informatika/analiticheskij-metod-reshenija-zadach-matematicheskogo-programmirovanija-237846.html
cсылка на страницу

Программирование

31 презентация о программировании
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Программирование > Аналитический метод решения задач математического программирования