Мет.моделирования и прогнозирования эк-ки

A1

A

Q

5

X2

B

X1

Рис. 2.6.

Заметим, что линия уровня поверхности

тром (0,5). Линия уровня определяет семейство окружностей с центром

(0,5) и радиусом C . Т.к. C – произвольно, то можно найти две окружности с данным центром и касающимися области допустимых решений ВСД. Точки касания A и A1. Рассмотрим точку A1, т.к. она соответствует меньшему радиусу касания и, следовательно – меньшему значению радиуса. Линия уровня с наименьшим значением C – будет окружность, касающаяся BC в точке A.

Найдём координаты точки A.

Решаем совместно систему уравнений:

Итак найдены экстремальные значения целевой функции:

fmin 10; fmax 20.

Метод множителей Лагранжа для решения задач нелинейного программирования

Графические методы решения задач нелинейного программирования пригодны только, когда число переменных в задаче не более двух ( x1,x2 ). Уже в трёхмерной задаче теряется наглядность и появляются

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

Существо метода заключается в следующем:

1.Из целевой функции Z f( x1,x2...)и системы нелиней-

Лагранжа.

2. Функция Лагранжа исследуется на условный экстремум, для чего используются необходимые и достаточные условия его существования:

Система (2.25.) содержит n+m уравнений с n+m неизвестными. Обычно эти уравнения нелинейны и точное решение их невозможно. Поэтому ограничиваются приближённым решением (с помощью численных методов и соответствующих программ на ПК).

В качестве примера рассмотрим простой случай, когда система уравнений (2.25.) имеет точное решение.

Пример 2:

Обработка статистических данных показала, что производственная функция, связывающая выпуск готовой продукции с численностью рабочих x1 и производственными фондами x2 имеет вид Z 3x1x2 . Об-

щие затраты предприятия на заработную плату и оборудование определяются соотношением 2x1 x2 60.

Нужно определить затраты предприятия на покупку оборудования и на заработную плату, при которых выпуск продукции будет максимальным:

Решение:

Составим функцию Лагранжа:

F( x1,x2, ) 3x1x2 (2x1 x2 60).

Из необходимых условий существования экстремума имеем:

F

2x1 x2 60 0;

Убедимся, что в точке M(15,30) функция F достигает max (Здесь мы имеем функцию 3-х переменных: x1,x2, ). Составим полное прира-

щение функции F:

F F( x1 x,x2 x2, ) F( x1,x2, ) 3( x1 x1 )( x2 x2 )( )(2x1 2 x1 x2 x2 60) 3x1x2 (2x1 x2 60);

Так как 2x1 x2 60 0,то

F 3(x1 x1 )( x2 x2 ) ( )(2 x1 x2 ) 3x1x2 ;F 3( x1x2 x1 x2 x1 x2 ) ( )(2 x1 x2 );

Поставим в F значения x1 15;x2 30; 45;

F 3(30 x1 15 x2 x1 x2 ) ( 45 )(2 x1 x2 );

По условию 2 x1 x2 0 тогда x2 2 x1;

F 3(30 x1 15 2 x1 x1 x2 ) 3 x12 x2 6( x1 )2 0.

Следовательно F имеет максимум в точке M(15,30).

Метод множителей Лагранжа можно применять и в том случае, когда условия связи (2.24.) представляют собой неравенства. Так, если требуется найти экстремум функции Z=f(x) при условии g( x1,x2...) bi ,

те, координаты которых удовлетворяют системе неравенств (2.24.) и определить точки, удовлетворяющие системе уравнений:

Точки, найденные в результате решения этой системы, вместе с точками, найденными на 1-м этапе, подлежат дальнейшему исследованию по знаку полного приращения f. Если в данных точках f <0, то мы имеем max целевой функции, если f >0, то в этих точках имеется минимум.

Графическое решение задачи выпуклого программирования

Рассмотрим пример графического метода решения задач выпуклого программирования. Применяемость этого метода ограничена случаем 2-х искомых переменных x1 и x2, которые образуют оптимальный

Получим уравнение семейства окружностей радиусом R с цен-

тром x10 5;x20 7,5 . Это – выпуклая функция. Построение области до-

пустимых решений показывает, что это тоже выпуклая область (см. рис.). Таким образом, мы имеем задачу выпуклого программирования.

Опустим из центра окружности O1(5;7,5) перпендикуляр на прямую AB. Точка K – касания окружности и прямой AB определяет оптимальное решение задачи.

X2

2X1+X2=10

O1

A R

B

K

2X1+3X2=13

Рис. 2.7.

Найдём угловой коэффициент прямой AB: k1 2. Тогда угло- 3

вой коэффициент прямой O1K равен: k2 3 . Уравнение прямой O1K: 2

3

x2 7,5 2( x1 5).

Решая совместно уравнения:

получим координаты точки K: x1k 2;x2k 3. Максимум целе-

вой функции fmax 2 2 0,2 4 3 3 0,2 9 10,4.

В заключение отметим, что существуют другие методы решения задач выпуклого программирования – градиентные методы, и барьерных функций и др. Все эти методы реализуются на ПК.

КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 2

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

2.Какие приемы используются для приведения задачи линейного программирования к каноническому виду?

3.Каким образом задача максимизации может быть сведена к задаче минимизации и наоборот?

4.Приведите примеры целевой функции и ограничений модели размещения розничной торговой сети.

5.Приведите примеры целевой функции и ограничений модели планирования деятельности торгового или коммерческого предприятия.

6.Охарактеризуйте особенности постановки и решения транспортной задачи.

7.Укажите пути нахождения оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке.

8.Поясните механизм использования метода северо-западного

угла.

9.Поясните методику использования метода потенциалов.

10.В чём заключается существо метода динамического программирования?

11.Дайте определения совокупности состояний процесса и управлений этими состояниями

12.Сформулируйте принцип оптимальности Беллмана.

13.Почему расчёт по схеме динамического программирования начинается с последнего шага?

14.Дайте определение условного оптимального выигрыша и условного оптимального управления.

15.В чём заключается принципиальное различие задач нелинейного и выпуклого программирования от задачи линейного программирования?

16.Как составляется функция Лагранжа для решения задач нелинейного программирования?

17.В чём состоит существо графических методов решения нелинейных оптимизационных задач?

18.В чём состоит отличие задач нелинейного программирования от задач выпуклого программирования?

19.Дайте определение выпуклой области допустимых решений

ивыпуклой целевой функции.

ЗАДАНИЕ К ГЛАВЕ 2

Задача 1. Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Известны потребности в сырье каждого из предприятий (см. варианты задания). Сырье сосредоточено в трех местах его получения, запасы которых известны. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются соответствующей матрицей (см. варианты задания). Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Варианты заданий Вариант 1.