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

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

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

3 Аналитические методы решения задач математического программирования 2. Необходимое условие экстремума функции Лагранжа есть: Дифференцируя (3.2) по всем переменным получим соотношения: (3.3) Соотношения (3.3) удобно представить в виде системы уравнений дополняющих нежесткостей: (3.4)

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

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

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

7 Аналитические методы решения задач математического программирования Задача 1.(Решение, продолжение) Функция Лагранжа имеет вид: Составляются уравнения дополняющих нежесткостей в виде: Из вида функции следуют следующие ограничения: x 1 >0; x 2 >0; (x 1 +х ) >0 откуда – λ=0 Решение системы уравнений (3.3) есть: X 1 =30.61; x 2 =18.37; x 0 =51.02; λ=0 (3.3)

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

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

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

11 Аналитические методы решения задач математического программирования Задача 2. (Продолжение решения) Складывая последние два уравнения, получим: (λ 1 - λ 2 ) (х 1 +x 2 – 20) = 0 Рассматриваем два случая : х 1 (10x 1 ) = 0 х 2 (10x ) =0 10x 1 = 0 10x = 0, или x 1 = 0 x 2 = -10 (Не удовлетворяет смыслу задачи) х 1 (10x 1 + λ 1 – λ 2 ) = 0 х 2 (10x λ 1 – λ 2 ) =0 (х 1 +x 2 – 20) = 0 Если х 1 >0; x 2 >0, то имеем (10x 1 + λ 1 – λ 2 ) = 0 (10x λ 1 – λ 2 )=0 (х 1 +x 2 – 20) = 0 Вычитая из первого уравнения второе, получим: 10х 1 -10х 2 = 10 х 1 = 10.5 x 1 + х 2 = 20 х 2 = 9.5 (λ1 - λ2) = 0. Тогда Случай 1. (λ1 - λ2) = 0. Тогда (λ1 - λ2) 0. Тогда Случай 2. (λ1 - λ2) 0. Тогда

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

13 Аналитические методы решения задач математического программирования 3. Экономический смысл множителей Лагранжа Качественная интерпретация множителя Лагранжа. λ i *φ i (x 1,x 2,…,x n )=0 -условие дополняющей нежесткостей. λ i *φ i (x 1,x 2,…,x n )=0 -условие дополняющей нежесткостей. λ i 0- оптимальное решение лежит на границе φ i (x 1,x 2,…,x n )=0 Экономический смысл – i-ый ресурс расходуется полностью. Его увеличение приведет к повышению эффективности системы. λ i = 0 – оптимальное решение не принадлежит границе φ i (x 1,x 2,…,x n )=0 Экономический смысл – запас i-го ресурса избыточен. Его уменьшение не приведет к снижению эффективности системы. Экономический смысл – запас i-го ресурса избыточен. Его уменьшение не приведет к снижению эффективности системы.

14 Аналитические методы решения задач математического программирования 3.2. Количественная интерпретация множителя Лагранжа. Зависит от контекста экономической задачи. Пример. Задача об оптимизации выпуска продукции. λ i > 0 означает, что данный ресурс λ i > 0 означает, что данный ресурс будет израсходован полностью и это огра- будет израсходован полностью и это огра- ничивает повышение производства. ничивает повышение производства. Вопрос. Как изменится оптимальное решение при небольшом изменении запаса этого ресурса? Тогда: Х={x 1 (b),x(b),…,x n (b)}; F(X)=F(X(b)=F(b); φ(X(b))=φ(b) dF/db i =Σ(dF/dx i )(dx i /db i ); dφ/db i =Σ(dφ/dx i )(dx i /db i ) В седловой точке: L(X(b), λ) =F(X(b)); dF(X*)/db i = λ i * Прирост производства за счет увеличения ресурса b i пропорционален λ i. dF = λ i *db i одновременно dF = с i *db i Если с i цена ресурса i, то увеличение его запаса выгодно, если λ i db i >c i db i λ i – предельная цена ресурса, при которой производство остается прибыльным. > max F(X) > max φ i (x) b i φ i (x) b i x i 0, i=1,2,…,n