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


 

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

66485. Мероприятия по снижению затрат в области энергоснабжения здания конторы ООО «Агрофирмы Тукса» 1.78 MB
  Граница балансовой принадлежности тепловых сетей по первому фланцу до запорной арматуры со стороны тепловой сети на элеваторном узле. Расчётные расходы теплоносителя вода 9060 определяются на основании проекта путём деления тепловой нагрузки...
66486. Исследование влияния дыхательных упражнений по методу Бутейко на процесс оздоровления школьников 116 KB
  Лечебная физкультура известна человечеству с давних времен. Широко применялась она в Египте, Риме, использовалась также некоторыми северными народами, в том числе и среди народов, населявших территорию нашей страны. Однако обоснованное применение физкультуры при инфаркте миокарда появилось сравнительно недавно.
66487. Разработка компьютерной программы при оформлении документации очного отделения - «Учебная часть РПТ» 1.54 MB
  Применение ЭВМ в учебном процессе является естественным продолжением многолетнего процесса внедрения в обучение технических средств. Обладающие высоким быстродействием, большой памятью, способностью перерабатывать информацию, поступающую одновременно от многих пользователей...
66489. Психокоррекция энуреза у детей дошкольного и младшего школьного возраста 298 KB
  В младшем школьном возрасте проблема энуреза напрямую соприкасается с проблемой адаптации к началу обучения в школе и закономерно влияет на успешность ребенка в учебной деятельности, в овладении новыми способами межличностных коммуникаций со сверстниками.
66490. СТРАТЕГІЯ УПРАВЛІННЯ АКТИВАМИ ТОРГІВЕЛЬНОГО ПІДПРИЄМСТВА 1.65 MB
  Мета роботи - розробка стратегії управління обіговими активами підприємства. Методика дослідження: методи фінансового аналізу, економіко-статистичні та економетричні методи. Одержані насідки та їх новизна: обгрунтування тактики стратегії управління активами підприємства.
66491. Исследование ономастического пространства поэзии Владимира Высоцкого 341 KB
  Ономастика как лингвистическая наука изучает основные закономерности истории, развития и функционирования имен собственных. Обладая своим материалом и методикой изучения его, ономастика не может не быть самостоятельной дисциплиной.
66492. Анализ условий выпуска и обращения ценных бумаг коммерческих банков 522.5 KB
  Целью моей работы является рассмотрение и анализ условий выпуска и обращения ценных бумаг коммерческих банков. Для достижения данной цели я поставила следующие задачи: определить понятие ценных бумаг и их виды; рассмотреть структуру, задачи и участников рынка ценных бумаг; определить роль банка на рынке ценных бумаг...
66493. МЕЖБАНКОВСКИЙ КЛИРИНГ 556.5 KB
  В соответствии с утвержденными планами модернизации платежной системы Республики Беларусь РБ в ближайшее время намечено внедрить пусковой комплекс нового проекта межбанковских расчетов в составе: системы расчетов по срочным и крупным платежам на валовой основе...