Нелинейные модели исследований операции и методы их решения

 

 

 

 

 

 

 

2.2 Постановка задачи

На минимум: (a) при ограничениях (b) (v) На максимум: (g) при ограничениях (d) (e)

Задачами нелинейного программирования (сокращенно задачами НЛП) называются, если среди функций f,g1...gm,h1...,hk имеется хотя бы одна нелинейная функция. Записи (a)-(v) и (g)-(d) являются стандартными постановками задач минимума и максимума (обратите внимание на знаки неравенств в (b) и (d)).

Задачи НЛП, как и любые другие задачи оптимизации, являются математическими моделями некоторых практических задач принятия решения.

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

В задаче (a)-(v) - целевая функция. – допустимое множество (множество допустимых точек).

Решить задачу (a)-(v) это значит:

а) либо найти точку минимума (оптимальное решение) ;

б) либо убедиться, что задача (a)-(v) не имеет оптимального решения (функция f не ограничена снизу на X или X=Æ).

Если минимум функции f не достигается на множестве X (разрывность f, открытость или неограниченность X), то вместо задачи (a)-(v) ставится обобщенная задача: f(х) ® inf при ограничениях (a)-(v) решение которой в виде минимизирующей последовательности почти всегда существует.

Как и в любой теории принятия решения, перед теорией нелинейной оптимизации стоят следующие три основные проблемы:

1) проблема существования  оптимального решения;

2) проблема установления  необходимых и достаточных признаков  оптимальности (характерных свойств, присущих точкам минимума и  максимума);

3) разработка способов  вычисления оптимальных решений (методов решения задач НЛП).

Проблема существования решения.

В задаче (a)-(v) применяются точки минимума двух видов. Точка x0 Î X надрывается точкой локального минимума, если f(x0) £ f(x) для всех x Î Oe(x0), где Oe(x0)={x Î Rn | ║x0-x║<e} -окрестность точки x, e>0 Точка x0 называется точкой глобального (или абсолютного) минимума, если f(x0) £ f(x) для всех x Î X.

Множество X называется компактным (в Rn), если любая последовательность ( {xk} Î X) имеет хотя бы одну предельную точку x* Î X. Известно, что всякая ограниченная последовательность имеет хотя бы одну предельную точку. Поэтому в Rn компактным является любое замкнутое ограниченное множество.

Достаточные условия существования оптимального решения задач (1)-(3) и (4)-(6) дает следующая:

Теорема 1 (Вейерштрасса).

Чтобы в задаче (a)-(v) и (g)-(e) присутствовала точка масштабного минимума (максимума), довольно, дабы возможное множество X было компактно, а целевая функция f непрерывна на X.

Ввиду сложности проверки ограниченности множества X, на практике часто применяется: Следствие (теоремы Вейерштрасса).

Если функция f непрерывна на Rn и ( ), то f достигает своего масштабного минимума (максимума) в любом замкнутом подмножестве в Rn.

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

Числовая последовательность {xk} называется ограниченной снизу (сверху), если существует число а такое, что xk ³ a (xk £ a) при всех k=1,2...

Число а называется нижним (верхним) пределом ограниченной снизу (сверху) последовательности {xk} и обозначается через

           ( ) если:

1) существует хотя бы  одна под последовательность {xkm}Ì{xk}, сходящаяся к а;

2) все предельные точки очередности {xk} не менее (не более) количества. Разговаривают, собственно функция f полунепрерывна снизу (поверх) (сокращенно п.н.сн. и п.н.св.) в точке x Î X, когда для каждый очередности   {xk} Î X, имеющей схожесть к точке х, имеет место соответствие

           ( ).

Функцию f называют п.н.сн. (п.н.св.) на множестве X, если она такова во всех точках x Î X.

Для выяснения п.н.сн. и п.н.св. функции f на закрытом множестве X можно применить последующий аспект. Дабы функция f была п.н.сн. (п.н.св.) на закрытом множестве X, нужно будет и довольно, дабы множество

{xÎX | f(x) £ c} ({xÎX | f(x) ³ c}) было закрытым при всех с (с=const).

Теорема 2 (Вейерштрасса, обобщенная).

Пусть X – компактное множество, а функции f конечна и п.н.сн. (п.н.св.) на X. Тогда в задаче (a)-(v) ((g)-(e)) существует точка глобального минимума (максимума).

Заметим, что если при выполнении условий теорем Вейерштрасса задача (a)-(v) ((g)-(e)) имеет множество оптимальных решений, то оно компактно.

Общие сведения.

Нужные и достаточные показатели оптимальности играют весомую роль в решении задачи (a)-(v). Требуемые показатели практически постоянно "сопровождают" подходящее решение, потому при их помощи возможно определить точки, сомнительные на экстремум. Исполнение необходимых симптомов для какой-нибудь возможной точки xÎX обеспечивает оптимальность данной точки. В следствии этого достаточные показатели применяют для нахождения подходящего решения из совокупности разрешенных точек, удовлетворяющих нужным показателям.

Приведем определения, играющие главную роль при установлении показателей оптимальности: дифференцируемых, выпуклых, квазивыпуклых и псевдо выпуклых функций.

Функция f дифференцируема в точке x0 Î int X если существует вектор Ñf(x0), называемый градиентом функции f в точке x0 такой, что

,

для каждого x Î X и . Для дифференцируемой в точке x0 функции f существует только один градиент

Функция f дважды дифференцируема в точке x0 Î int X если существует градиент Ñf(x0) и симметрическая матрица Ñ2f(x0), называемая матрицей Гессе (или гессианом), такая, что

для каждого x Î X; ,

Функция f называется дифференцируемой (дважды дифференцируемой) на множестве X, если она такова во всех точках x Î X.

Функция а выпукла (квазивыпукла) на выпуклом множестве X, если для любых x1,x2 Î X и l Î [0;1] выполнено неравенство

, ( )

Дифференцируемая на выпуклом множестве X функция f псевдо выпукла на X, если для любых x1,x2 Î X из неравенства <f(x1),x2-x1> ³ 0 следует неравенство f(x2)³f(x1).

Приведем определения, играющие главную роль при установлении показателей оптимальности: дифференцируемых, выпуклых, квазивыпуклых и псевдо выпуклых функций.

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

Известно, собственно два раза дифференцируемая на выпуклом большом количестве X функция f выпукла (вогнута) и тогда только после этого, как скоро для всех векторов aÎRn, xÎX справедливо неравенство

( )

Это есть определение нужной (отрицательной) полу определённости матрицы Гессе. В случае взыскательного неравенства общаются о положительно (отрицательно) определенной матрице Гессе. Напомним, непосредственно матрица Ñ2f(x) станет положительно (отрицательно) полуопределенной в точке x0 Î X, когда

( )

для всех k=1,...,n. Здесь символом обозначен минор k-го порядка матрицы Ñ2f(x0):

В случае строгих неравенств получаем нужное и достаточное условие положительной (отрицательной) определенности матрицы Гессе в точке x0 Î X. Приведенные условия именуются аспектами Сильвестра для символ определённых матриц.

По возрастанию трудности исследования показателей оптимальности, задачи НЛП возможно разместить в последующем порядке:

- задачи безусловной оптимизации (как скоро в (a)-(v) отсутствуют все лимитирования (b)-(v));

– задачи с ограничениями-равенствами (как скоро в (a)-(v) отсутствуют лимитирования вида(b));

- задачи с ограничениями-неравенствами (как скоро в (a)-(v) отсутствуют лимитирования вида (3));

– задачи со смешанными лимитирования (задачи вида (a)-(v)).

Три завершающих вида называются задачами условной оптимизации. Ниже мы приведем характеристики оптимальности для гладких задач оптимизации. Так называются задачи (a)-(v), (g)-(d), как скоро все функции f,g1...gm,h1...,hk владеют свойством постоянной дифференцируемости на X.

Все числовые эти, затрагивающие предполагаемых производственных и финансовых действий, берутся на базе шестизначного шифра:

8 4 4 7 6 2

Под каждую цифру записываются буквы a, b, c, d, e, f в следующем виде:

8 4 4 7 6 2

а b c d e f

из заключительной строчки таблицы личных заданий обретаем столбцы подходящие буквам a, b, c, d, e, f. В тех случаях числовыми данными, нужными для исполнения этой курсовой работы, станут эти оказавшиеся в а – том столбце в строчке 8, b – том столбце в строчке 4, c – том столбце в строчке 4, d – том столбце в строчке 7, e – том столбце в строчке 6и f – том столбце в строчке 2.

По таблице исходных заданий для любого варианта заданий по столбцу а исполнитель получает вариант выполняемого задания.

Для примера решения задачи нелинейного программирования возьмем предприятие ООО «Техно-Логика».

Деятельность ООО «Техно-Логика»:

- производство алюминиевых  радиаторов охлаждения;

- производство корпусов  светодиодных светильников со  всеми необходимыми комплектующим;

- производство стандартных  электротехнических охладителей;

- по чертежам клиентов: изготовка деталей из алюминиевого  профиля и листа, в том числе  анодированных.

      Произведем три вида продукта и при всем этом потратим два вида ресурсов. Производственная функция любого вида продукта на предприятии опишется равенствами.

 

где Сi и - постоянные величины, i = 1, 2, 3;

X1 – трудовые ресурсы в человеко-днях;

Х2 – денежно-материальные средства, в тенге;

Уi – получаемый продукт

Х1 = а1х1 + b1x2 + c1x3

Х2 = а2х1 + b2x2 + c2x3

Найти все неотрицательные базисные решения и определить оптимальный план F = y1 + y2 + y3.

Известно, что продукт для производства j – того вида затрачивается aij единиц i – того ресурса.

Таблица 2.1

Продукты ресурсы	1 алюминиевый профиль	2 алюминиевый радиатор	3 алюминиевый корпус
I алюминиевый лист	8	4	6
II порошковые полимерные покрытия	160	240	200

 

3. По столбцу c – на 3 строке находим с1=6, α1=0,6

4. По столбцу d – на 5 строке определяем с2=5, α2=0,5

5. По столбцу e – по 4 строке установим, что с3=8, α3=0,4.

6. И наконец по столбцу  f – в 1 строке найдем Тчел.дней =1000, Птенге = 280000

Для производства имеются трудовые ресурсы Тчел.дней и денежно-материальные средства Птенге.

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

Составление математической модели задачи

        1.На основании приобретенных в первом шаге начальных этих и описания установленного производственного процесса оформляется последующая таблица:

                                                                                                                         Таблица 2.2

Продукты ресурсы	1 алюминиевый профиль	2 алюминиевый радиатор	3 алюминиевый корпус
I алюминиевый лист	8	4	6	1000
II порошковые полимерные покрытия	160	240	200	280000

 

Через Х1 обозначим ресурсы I вида.

Через Х2 обозначим ресурсы II вида.

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

8Х1 + 4Х2 + 6Х3 ≤ 1000

240Х1+ 200Х2 + 160Х3 ≤ 280000

Следовательно, возымели задачу нелинейного программирования. Эти задачи называются задачами нелинейного программирования. 
 
 
Решение задач нелинейного программирования исполняется приведением их к задачам линейного программирования.

Для решения задачи линейного программирования применяется симплекс

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3 Решение задачи

1. Для решения задач  линейного программирования симплекс  – методом задача приводиться  к каноническому виду:

8Х1 + 4Х2 + 6Х3 + Х4= 1000

240Х1+ 200Х2 + 160Х3 + Х5= 280000

 

2. Составляем таблицу  и определяем все неотрицательные  базисные решения системы.