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


 

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

6629. Введение в медицинскую генетику 19.74 KB
  Введение в медицинскую генетику Относительный рост доли генетически обусловленной патологии в структуре заболеваемости, смертности, синдромах социальной дезадаптации в настоящее время связан с быстрым прогрессом диагностических возможностей. Наследс...
6630. Структура ДНК, репликация, транскрипция, трансляция, структура генов и код передачи генетической информации 30.73 KB
  Структура ДНК, репликация, транскрипция, трансляция, структура генов и код передачи генетической информации. Аминокислотная последовательность и структура всех белков определяется информацией, закодированной в структуре дезоксирибонуклеиновой кислот...
6631. Организация и структура генома, генетические карты 22.94 KB
  Организация и структура генома, генетические карты. В настоящее время термин геном используется для обозначения полной генетической системы клетки, определяющей характер развития организма и наследственную передачу всех его структурных и функциона...
6632. Методы современного генетического анализа 21.01 KB
  Методы современного генетического анализа ДНК может быть изолирована из любого типа тканей или клеток, содержащих ядра. У человека ДНК обычно выделяют из лейкоцитов крови, для чего собирают от 0,5 до 2-3 мл венозной крови. В плазме, обогащенной лейк...
6633. Хромосомные болезни 14.35 KB
  Хромосомные болезни Хромосомные болезни - клинические синдромы, обусловленные изменениями числа или структуры хромосом. Частота хромосомных болезней среди новорожденных детей составляет около 1%. Значительные аномалии хромосом несовместимы с жизнью ...
6634. Аномалии половых хромосом 23.26 KB
  Аномалии половых хромосом а) Синдром Шерешевского - Тернера (моносомия X - ХО) Впервые больная с первичной аменореей, недостаточным развитием вторичных половых признаков и низким ростом была описана Н.А. Шерешевским в 1925 г. В 1938 г. H. Turner при...
6635. Аномалии аутосом 23.66 KB
  Аномалии аутосом Известно три основных клинических синдрома с трисомией по аутосомам. Наиболее распространенным является болезнь Дауна. а) Болезнь Дауна Заболевание было описано J. Down в 1866 г., который отметил выраженное снижение интеллекта, соче...
6636. Наследственные болезни обмена веществ с поражением нервной системы 47.91 KB
  Наследственные болезни обмена веществ с поражением нервной системы. В настоящее время известно около 2.000 наследственных болезней и генетически детерминированных синдромов. Большую группу наследственных заболеваний составляют болезни обмена веществ...
6637. Факоматозы, нейроэктодермальные или эктомезодермальные дисплазии 18.64 KB
  Факоматозы Факоматозы - нейроэктодермальные или эктомезодермальные дисплазии, представляют собой группу наследственных заболеваний, имеющих прогрессирующее течение, при которых на ранних стадиях эмбриогенеза происходят нарушения роста и диффере...