21820

Нелинейное программирование (НП)

Лекция

Менеджмент, консалтинг и предпринимательство

нелинейное программирование НП Постановка задачи НП Экологоэкономическая интерпретация задачи НП Геометрическая интерпретация задачи НП Метод множителей Лагранжа ММЛ Обзор рассмотренных методов. Постановка задачи НП В общем виде задача НП состоит в определении max min значения f x1 x2 xn 1 при условии что ее переменные удовлетворяют соотношениям gix1 x2 xn  bi i = 1 k gix1 x2 xn = bi i = k 1 m где f и gi некоторые известные функции n переменных а bi – заданные числа. Имеется в виду что в...

Русский

2013-08-03

131 KB

44 чел.

Тема 5. лекция 6.

нелинейное программирование (НП)

  1.  Постановка задачи НП
  2.  Эколого-экономическая интерпретация задачи НП
  3.  Геометрическая интерпретация задачи НП
  4.  Метод множителей Лагранжа (ММЛ)
  5.  Обзор рассмотренных методов.

1. Постановка задачи НП

В общем виде задача НП состоит в определении max/min значения

f (x1, x2, … xn)         (1)

при условии, что ее переменные удовлетворяют соотношениям

 gi(x1, x2, …, xn) bi (i = 1, k)

gi(x1, x2, …, xn) = bi (i = k + 1, m),

где f и gi  некоторые известные функции n переменных, а bi – заданные числа.

Имеется в виду, что в результате решения задачи будет определена точка     Х* = (х1*, х2*, … хn*), координаты которой удовлетворяют соотношению (2), причем для всякой другой точки, отвечающей условиям (2), выполняется

F* (x*1, x*2, … x*n) f (x1, x2, … xn)

Если f и gi – линейные функции, то это будет задача линейного программирования.

Соотношения (2), образующие систему ограничений, включают в себя и условия неотрицательности переменных, если таковые имеются. Последние могут быть заданы и отдельно.

В евклидовом пространстве En система ограничений (2) определяет ОДР. В отличие от задачи ЛП она не всегда является выпуклой.

Если определена ОДР, то нахождение решения задачи НП сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f (x1, x2, … xn) = h, причем эта точка может находиться как на границе ОДР, так и внутри нее.

2. Эколого-экономическая интерпретация задач НП

На проведение мероприятий по повышению экологичности производства предприятие располагает 220 тыс. руб. Эти средства могут быть распределены между тремя подразделениями. Каждый вариант распределения снижает в определенной степени ущерб от загрязнения окружающей среды и дает определенный эффект, равный предотвращенному ущербу. Требуется определить такой вариант распределения капиталовложений, при котором эффект, получаемый предприятием будет максимальным.

Подраз-деления

Капитало-вложения, тыс.р.

Эффект, тыс. руб.

Капитало-вложения, тыс.р.

Эффект, тыс. руб.

Капитало-вложения, тыс.р.

Эффект, тыс. руб.

I

От 10 до 30

7,3

30…60

8,0

60

10

II

От 10 до 40

6,2

40…70

8,6

70

9,1

III

От 10 до 50

9,1

50…60

9,8

60

9,5

Математическая модель

Обозначим капиталовложения, распределенные между тремя подразделениями х1, х2, х3.

Эффект по каждому подразделению: С11), С22), С33).

F = C1(X1) X1 + C2(X2)X2 + C3(X3)X3 = f (X1, X2, X3) max

X1 + X2 + X3 = 220

X1, X2, X3  0.

Известно, что можно регулировать степень чистоты ОС путем нормирования, т.е. введения допустимого уровня загрязнителя в среде. Такое регулирование можно осуществлять путем выдачи производителю лицензий, условием для получения которых являлось бы соблюдение установленных норм качества ОС. Естественно, что каждое предприятие – источник загрязнения несет определенные затраты на устранение загрязнения.

Полные затраты (С) на устранение загрязнения складываются из суммы затрат Сi для каждого загрязняющего среду:

,

где Qi – масса устраненного загрязняющего вещества i-м предприятиям.

Для обеспечения установленного уровня качества ОС полная масса загрязняющего вещества Q, подлежащего устранению, определяется как:

Поскольку затраты предприятий на устранение загрязнений ложатся также и на потребителей продукции (удорожание ее), то обществу в целом выгодна минимизация полных затрат на обеспечение качества ОС.

Таким образом целевая функция

.

Ограничения: .

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

3. Геометрическая интерпретация задачи нелинейного

   программирования

При числе переменных не более двух задачу НП можно решить геометрическим способом.

Процесс нахождения решения задачи НП (1), (2) с использованием ее геометрической интерпретации включает следующие этапы:

  1.  Находят ОДР задачи, определяемую соотношением (2); если она пуста, то задача не имеет решения.
  2.  Строят гиперповерхность f (x1, x2, … xn) = h.
  3.  Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (1) сверху (снизу) на множестве допустимых решений.
  4.  Находят точку ОДР, через которую проходит гиперповерхность наивысшего (наинизшего) уровня, и определяют значение функции (1).

Пример.

Найти max функции f = x2  x12 + 6x1     (3)

При условиях

1 + 3х2  24

х1 + 2х2  15

1 + 2х2  24

х2  4,

х12  0.

Решение: F нелинейна, следовательно, это задача НП;

  1.  ОАВС - ОДР

Следовательно, нужно определить такую точку многоугольника ОАВС, в которой функция принимает max значение.

  1.  Построим линию уровня F = x2  x12 +6x1 = h,

где h – некоторая постоянная, и исследуем ее поведение при различных h. При каждом h получаем параболу, которая тем выше относительно ОХ, чем больше h.

Действительно,

F = x2  x12 +6x1 = h = парабола  x2 = x12 - 6x1h или  х2 = (х1 – 3)2+h-9.

Рассмотрим h = 9          х2 = (х1 – 3)2

 h = 11          х2 = (х1 – 3)2 + 2

                  h = 13           х2 = (х1 – 3)2 + 4

Функция F принимает максимальное значение в точке касания одной из парабол с границей многоугольника ОАВС. В данном случае это точка Д, в которой линия уровня F = x2  x12 +6x1 = 13 касается стороны многоугольника ОАВС.

При каждом h получаем параболу, которая тем выше отн. ОХ, чем больше h.

Действительно,

F = x2  x12 +6x1 = h = парабола  x2 = x12 - 6x1h или  х2 = (х1 – 3)2+h-9

Рассмотрим h = 9          х2 = (х1 – 3)2

 h = 11          х2 = (х1 – 3)2 + 2

                  h = 13           х2 = (х1 – 3)2 + 4

Координаты точки D находим из уравнений, соответствующих преобразованным ограничениям (1) и (2):

x2  x12 +6x1 = 13, х2 = 4, откуда х1* = 3; х2* = 4.

Umax, Fmax = 13 при х* = (3;4).

Таким образом в этой задаче точка Fmax не является вершиной треугольника решений. Поэтому процедура перебора вершин, которая использована в задачах ЛП неприменима.

4. Метод множителей Лагранжа

Математическая постановка. Рассмотрим частный случай общей задачи НП (1), (2), предполагая, что система ограничений (2) содержит только уравнение, отсутствуют условия неотрицательности переменных, и f (X1, X2Xn) и qi (X1, X2,…Xn) – функции, непрерывные вместе со своими частными производными.

f (X1, X2 …Xn) max (min)

qi (X1, X2,…Xn) = bi (I = 1, m).

Это так называемая задача на условный экстремум или классическая задача оптимизации.

Чтобы найти решение этой задачи, вводят набор переменных 1, 2,…n, называемых множителями Лагранжа, составляют функцию Лагранжа.

f (X1, X2Xn, 1, 2,…n) = f (X1, X2Xn) +

находят частные производные.

и рассматривают систему n + m уравнений.

с n+m неизвестными Х1, Х2,…Хn, n, 1, 2,… m.

Всякое решение этой системы уравнений определяет точку Х* = (Х1*, Х2, … Хn), в которой может иметь место экстремум функции f (x1, x2,…xn).

Следовательно, решив систему уравнений, получают все точки, в которых функция f (x1, x2,…xn) может иметь экстремальные значения.

Таким образом, определение экстремальных точек задачи НП методом множителей Лагранжа включают следующие этапы:

  1.  Составляют функцию Лагранжа.
  2.  Находят частные производные от функции Лагранжа по переменным Х1 и 1 и приравнивают их нулю.
  3.  Решая полученную систему уравнений, находят точки, в которых целевая функция задачи может иметь экстремум.
  4.  Среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, а вычисляют значения целевой функции в этих точках.

Пример:

По плану производства предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве Х1 изделий I способом приведенная масса токсичных отказов равна 4Х1 + Х12 кг, а при изготовлении Х2 изделий II способом они составляют 8х2 + х22 кг.

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

Решение:

Математическая постановка задачи состоит в определении минимального значения функции

f = 4x1 + x12 + 8x2 + x22

при условиях х1 + х2 = 180, х1, х2  0.

Теперь решим задачу, используя метод множителей Лагранжа. Найдем min целевой функции при условии х12 = 180, но без учета требований неотрицательных переменных.

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

F(x1, x2,) = 4x1+x12+8x2+x22+(180-x1 – x2)

                              

  1.  Вычисляем  частные производные и приравниваем к нулю:

Перенося в правые части первых двух уравнений и приравнивая их левые части:

4 + 2х1 = 8+2х2 или х1 – х2 = 2

Решая это уравнение совместно с последним:

х1 – х2 = 2

180-х12 = 0, находим: х2 = х1-2

180-х1 – х1+2 = 0 х1 = 91; х2 = 89.

Этот результат и был получен выше, однако ММЛ более универсален, т.к. применим при n  2.   

5. Обзор рассмотренных методов. Математическое

   программирование и исследование операций

Рассмотренные нами методы линейного и нелинейного программирования (а также целочисленное программирование, динамическое программирование) объединяются понятием математическое программирование. Математическое программирование как и другие методы решения экстремальных задач составляют основу аппарата исследования операций - дисциплины, которая является одним из истоков системного анализа. Фактически, основные концепции, принципы анализа систем являются развитием теории исследования операций, и ее методы являются сегодня одной из основных глав системного анализа.

Сам термин «исследование операций» возник в послевоенные годы, когда стало ясно, что задачи широкого класса, возникшие в самых различных сферах человеческой деятельности, имеют, несмотря на их качественное различие, одно общее - они сводятся к выбору способа действия, варианта плана, параметров конструкции и т.п., т.е. к принятию решений, и этого общего достаточно для построения единой теории и единой системы методов. Создание сложных технических систем, проектирование сложных народнохозяйственных комплексов, анализ экологических ситуаций и многие другие направления инженерной, научной и хозяйственной деятельности требовали развития междисциплинарных, системных исследований. В этих условиях возник и весьма общий термин - «операция», означающий любое целенаправленное действие. Говоря об операции, мы всегда связываем с ней некоторого субъекта (оперирующую сторону), который формулирует цель операции и в интересах которого последняя проводится. Цель операции - обычно некоторый внешний (экзогенный) элемент - считается заданной.

Наряду с субъектом, т.е. с оперирующей стороной, мы всегда имеем дело еще и с исследователем операции. Он действует в интересах оперирующей стороны, и его задача состоит в том, чтобы найти способ использования ресурса (т.е. возможностей оперирующей стороны), обеспечивающий достижение цели.

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

Первым шагом исследования операций является формализация операции, ее описание с помощью языка математики. От того, как будет формализована задача, будет зависеть судьба  исследования. Так простое описание делает и анализ более простым, но если модель не будет в достаточной степени адекватна реальности, то мы получим сомнительную достоверность результатов. Наоборот, переусложненная задача, учитывающая разнообразные детали процесса и с большими подробностями описывающая реальность, может привести к такой затрате машинного времени (большие системы), которую даже высокая точность результата не сможет оправдать.

Еще более сложные проблемы возникают при формировании критерия - способа оценки качества наших действий, когда необходимо сравнивать различные варианты стратегий, различные альтернативы. Здесь типична ситуация, когда операция оценивается несколькими показателями. В этом случае говорят о неопределенности целей. (Н.Н. Моисеев Математические задачи системного анализа. М.: Наука, 1981.)


Рис.1

4

(2)

(1)

(3)

15

12

8

3

0

h=9

h=11

h=13

h=9

h=11

h=13

Рис.1

4

8

(2)

(1)

(3)

15

12

8

3

0

h=9

h=11

h=13

h=9

h=11

h=13


 

А также другие работы, которые могут Вас заинтересовать

81922. Управление в системе рыночных отношений 36.96 KB
  Функции контроля в такой экономике исполняет механизм конкуренции. Сколько и каких товаров производить по каким ценам их продавать куда вкладывать капиталы все это определяется не распоряжениями сверху а механизмом спроса и предложения прибылью курсом акций ссудным процентом курсом валют Менеджмент в рыночных условиях представляет собой средство рационального управления экономикой прежде всего экономикой в масштабах организации фирмы предприятия.
81923. Менеджмент и предпринимательство 37.56 KB
  Предпринимательство инициативная деятельность направленная на насыщение рынка товарами услугами и на получение прибыли или личного дохода и осуществляемая от своего имени на свой риск и ответственность. Предпринимательство предшествует менеджменту.
81924. Этапы развития и совершенствование менеджмента 39.25 KB
  Точка отсчета в накоплении знаний в области управления. обширный опыт управления государственным хозяйством был накоплен в Древнем Египте. Сформирован достаточно развитый государственный аппарат управления.
81925. Происхождение и эволюция менеджмента 39.4 KB
  За эти долгие годы развитие теории и практики менеджмента происходило в основном эволюционно путём непрерывного накопления опыта отражающего изменения которые происходили в обществе экономике и всей системе социальноэкономических отношений. Вместе с тем на этом долгом пути выделяют ряд этапов и революционных преобразований в подходах к проблемам менеджмента. Началом истории менеджмента принято считать зарождение письменности в древнем Шумере.
81926. Основные подходы в развитии теории и практики менеджмента 39.52 KB
  Первый из них это школы : Научного управления Создатели школы научного управления исходили из того что используя наблюдения замеры логику и анализ можно усовершенствовать большинство операций ручного труда добиться более эффективного их выполнения. административного управления классическая школа Сторонники научного направления пренебрегали материальным стимулированием сотрудников таким как заработная плата. количественных методов управления Количественная школа с 1950 года по настоящее время связана с развитием и...
81928. Классическая (административная) школа управления 37.06 KB
  Он разделил весь процесс управления на пять основных функций которые мы до сих пор используем в управлении организацией: это планирование организация подбор и расстановка кадров руководство мотивация и контроль. Суть разработанных им принципов управления сводится к следующему: разделение труда; авторитет и ответственность власти; дисциплина; единство руководства; единство распорядительства; подчинение частного интереса общему; вознаграждение за труд; координация менеджеров одного уровня; порядок; справедливость; доброта и порядочность;...
81929. Школа человеческих отношений и поведенческих наук 38.48 KB
  Родоначальником школы человеческих отношений принято считать Э. В результате движение человеческих отношений стало противовесом всему научному движению. Это связано с тем что акцент в движении человеческих отношений делался на заботе о людях а в движении научного управления на заботе о производстве.
81930. Психологічні чинники формування лідерських якостей у майбутніх фахівців 401 KB
  Мета: теоретично вивчити та експериментально дослідити психологічні чинники формування лідерських якостей у майбутніх фахівців. Гіпотеза: рівень розвитку лідерських якостей у майбутніх фахівців є обумовленим такими психологічними чинниками як: рівень розвитку комунікативних та організаторських здібностей, потреби в досягненнях.