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


 

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

35545. Рихтер – личность, мыслитель, музыкант (на материале: «Монсенжон Б. Рихтер. Диалоги. Дневники») 2.35 MB
  Целью данной работы является выявление масштаба личности Святослава Рихтера, многогранности его таланта, осмысление различных граней творческой деятельности великого музыканта, обусловленной его незаурядными личностными качествами.
35546. Исследование свойств графов. Построение основных матриц. Решение системы линейных алгебраических уравнений методом графов 306 KB
  Исключив общее ребро е из двух несовпадающих циклов, мы превратим эти циклы в две несовпадающие простые цепи, объединение которых, в силу свойств цепей, будет содержать простой цикл (естественно, без ребра е).
35547. ПРОЕКТИРОВАНИЕ ФАСОННОГО ДИСКОВОГО РЕЗЦА С ПРИМЕНЕНИЕМ ЭВМ 835.5 KB
  Приведены методика проектирования дискового фасонного резца на базе системы автоматизированного проектирования металла режущего инструмента САПР РИ и характеристики фасонных резцов их конструктивные особенности технические условия на проектирование резцов программа коррекционного расчета профиля дискового фасонного резца на ЭВМ СМ4. По конструктивной форме фасонные резцы подразделяются на стержневые призматические и дисковые Наибольшее распространение получили дисковые резцы так как они более технологичны в изготовлении и...
35548. Проектирование фасонных резцов 111 KB
  Целью работы является ознакомление с различными формами и видами фасонных резцов, правилами установки, правилами назначения передних и задних углов, алгоритмом проектирования профиля фасонного резца
35549. Двухступенчатый цилиндрический редуктор 553.5 KB
  Определение силовых и кинематических параметров редуктора. Конструирование зубчатого редуктора. Конструирование и расчет элементов корпуса редуктора. Редуктор двухступенчатый несоосный Кинематическая схема редуктора: вращающий момент на тихоходном валу редуктора; угловая скорость выходного вала редуктора; ч.
35550. Редуктор двухступенчатый соосный двухпоточный с внутренним зацеплением тихоходной ступени 1.7 MB
  Кинематический расчет и выбор электродвигателя Исходные данные: потребный момент на валу исполнительного механизма ИМ Тим=30Нм; угловая скорость вала ИМ ωим=58с1; Определяем мощность на валу ИМ Nим= Тимх ωим=30х58=174Вт. Определяем общий КПД привода по схеме привода ηобщ=ηкп ηшп ηм ηп1. =097209820994=0868 Определяем потребную мощность электродвигателя [1 с. Определяем номинальную частоту вращения электродвигателя по формуле 5 [1c.
35551. Кибернетика. Курс лекций 887.5 KB
  Уже давно ученые обнаружили сходство некоторых процессов управления в системах различной материальной природы и попытались использовать эти аналоги в исследованиях и практических приложениях. Она показала плодотворность использования аналогии процессов управления для их познания и совершенствования. Именно на этой почве формируются конкретные приложения кибернетики в экономике предметом изучения которой являются процессы управления и связанные с ними процессы передачи и обработки информации в экономических системах. Это обуславливается...
35552. АНАЛИЗ МЕДИАРЫНКОВ 524 KB
  Существуют ли другие продукты которые будут покупать потребители что ограничит потенциал нового продукта услуги Сила поставщиков или Рыночная власть поставщиков Достаточно ли продукции на рынке Существует ли какойнибудь компонент добавленной стоимости позволяющий конкурировать с другими поставщиками Противостояние существующих производителей или Угроза от существующих конкурентов Сколько компаний борются за рынок Какова в целом позиция конкурентов Какие методы конкуренции используются Угроза новых участников рынка или...
35553. Система управления летательного аппарата (СУЛА) 2.06 MB
  В основе процесса управления лежит информация о задачах управления заданной цели и текущем состоянии системы. В соответствие с эти процесс управления включает следующие основные этапы: получение необходимой информации о задачах управления; получение информации о текущем состоянии объекта управления ЛА; анализ полученной информации и выработку решения управляющего воздействия; реализацию принятого решения. Из этих же элементов состоит процесс управления ЛА.