Semenalidery.com

IT Новости из мира ПК
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Задача нелинейного программирования формулируется следующим образом:

определить минимальное значение функции

f(x) → min (7.1)

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

где f(x), gi(x), i = 1:m − некоторые известные функции (необязательно линейные) n переменных, а bi − заданные числа. Считаем, что все функции fi(x), gi(x), i = 1:m определены на некотором открытом множестве X E n . Для упрощения ограничимся случаем Х = Е n .

Условие неотрицательности переменных xj ³ 0, j = 1:n, входящее в постановки многих задач нелинейного программирования, можно записать в виде неравенств (7.3), положив gj(x) = —xj , bj = 0.

В евклидовом пространстве E n система ограничений (7.2) … (7.3) определяет область допустимых решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.

Cформулированная задача (7.1) … (7.3) представляет собой частный случай общей задачи математического программирования, заключающийся в определении наименьшего значения целевой функции f(x) на допустимом множестве

Х = <х Х | gi(х) = bi, i = 1:l, gi(х) ≤ bi, i = (l+1):m>.

Отметим, что если все функции gi(х) непрерывны в Е n , то множество Х замкнуто.

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

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

Если определена область допустимых решений, то нахождение решения задачи (7.1) … (7.3) сводится к определению такой точки этой области, через которую проходит гиперплоскость наинизшего уровня: f(x) = α , где α − произвольное число.

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

1. Находят область допустимых решений задачи, определяемую соотношениями (7.2) … (7.3).

2. Строят гиперплоскость f(x) = α.

3. Определяют гиперплоскость наинизшего уровня или устанавливают неразрешимость задачи из-за неограниченности функции (7.1) снизу на множестве допустимых решений.

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

Пример 7.1.Найти максимальное значение функции

(7.5)

Решение.Так как целевая функция (7.4) нелинейная, то задача (7.4) … (7.6) является задачей нелинейного программирования. Областью допустимых решений данной задачи является многоугольник 0АВС (рис. 7.4). Следовательно, для нахождения её решения нужно определить такую точку многоугольника 0АВС, в которой функция (7.4) принимает максимальное значение. Построим линию уровня f(х) = x2x1 2 + 6x1 = α , где α – некоторая постоянная, и исследуем её поведение при различных значениях α.. При каждом значении α получаем параболу, которая чем дальше отдалена от оси 0x1, тем больше значение α.. Значит, функция f принимает максимальное значение в точке касания одной из парабол с границей многоугольника 0АВС. В данном случае это точка D (рис. 7.4), в которой линия уравнения f = x2x1 2 + 6x1 = 13 касается стороны АВ многоугольника 0АВС.

Координаты точки D можно найти из системы уравнений

Решая эту систему, получим x1 * = 3; x2 * = 4. Итак, fmax = 13 при x * (3;4).

Рис. 7.4. Область допустимых решений

Для нахождения гиперплоскости наинизшего уровня можно руководствоваться следующими соотношениями: точка x * = (x1 min, x2 min) принадлежит прямой x2 = 0 и параболе fmin = x2x1 2 +6x1 , а потому обоим этим уравнениям, т. е. может быть определена как решение системы

(7.7)

Однако, так как нам не известно f* − оптимальное значение целевой функции f(x1, x2), то в этой системе оказывается три переменных и всего два уравнения, поэтому систему необходимо дополнить ещё одним уравнением, связывающим переменные x1, x2, fmin.

Нужное уравнение можно получить, если учесть, что угловой коэффициент касательной к параболе, по которой целевая функция достигает своего минимального значения, равен 1: касательной в этой точке является прямая x2 = 0. Как мы знаем, угловой коэффициент касательной к кривой x2 = f(x1) в точке x1 равен ∂x2 / ∂x1. Поэтому в нашем случае имеем

Вычислим теперь производную целевой функции fmin. Для этого продифференцируем левую и правую часть этого соотношения по x1. Получим:

Первое слагаемое дифференцируем, как сложную функцию от x2:

Откуда из (7.9) следует 0 = 2x1 +6. Если учесть (7.8), то окончательно получим:

Дополняя этим последним соотношением систему (7.7), окончательно получим:

Для нахождения максимального значения функции поступаем аналогичным образом. Получаем систему:

Решая её, получим fmax = 13.

Рассмотрим задачу нелинейного программирования, в которой все ограничения заданы линейными функциями, на переменные x1,…, xn наложены условия неотрицательности, а целевая функция нелинейная.

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

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

Эффект по каждому подразделению: С 1 (Х 1 ), С 2 (Х 2 ), С 3 (Х 3 ).

F = C 1 (X 1 ) X 1 + C 2 (X 2 )X 2 + C 3 (X 3 )X 3 = f (X 1 , X 2 , X 3 )  max

X 1 + X 2 + X 3 = 220

X 1 , X 2 , X 3  0.

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

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

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

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

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

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

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

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

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

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

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

Найти max функции f = x 2  x 1 2 + 6 x 1 (3)

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

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

  1. Построим линию уровня F = x 2  x 1 2 +6 x 1 = h ,
Читать еще:  Матлаб язык программирования

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

F = x 2  x 1 2 +6 x 1 = h =  парабола x 2 = x 1 2 — 6 x 1 – h или х 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 = x 2  x 1 2 +6 x 1 = 13 касается стороны многоугольника ОАВС.

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

F = x 2  x 1 2 +6 x 1 = h =  парабола x 2 = x 1 2 — 6 x 1 – h или х 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):

x 2  x 1 2 +6 x 1 = 13, х 2 = 4, откуда х 1 * = 3; х 2 * = 4.

U max , F max = 13 при х* = (3;4).

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

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

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

f (X 1 , X 2 …X n )  max (min)

q i (X 1 , X 2 ,…X n ) = b i (I = 1, m).

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

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

f ( X 1 , X 2 … X n ,  1 ,  2 ,…  n ) = f ( X 1 , X 2 … X n ) +

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

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

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

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

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

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

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

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

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

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

f = 4 x 1 + x 1 2 + 8 x 2 + x 2 2

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

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

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

F(x 1 , x 2 ,  ) = 4x 1 +x 1 2 +8x 2 +x 2 2 +  (180-x 1 – x 2 )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В евклидовом пространстве Еn система ограничений gi (x1, x2, . xn)=bi, i=1, 2, . k, определяет область допустимых решений задачи (ОДР). В отличие от ЗЛП она не всегда является выпуклой.

Читать еще:  Как вызвать безопасный режим на ноутбуке

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

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

Рассмотрение ЗНЛП начинают с классической задачи оптимизации. Задачи такого рода имеют место, если система (3.2) содержит только уравнения, отсутствуют условия не отрицательности и цело численности переменных, а функции gi (x1, x2, . xn) и f (x1, x2, . xn) непрерывны и имеют частные производные не ниже второго порядка. Классические методы оптимизации при этом являются теоретическим аппаратом, позволяющим в ряде случаев обосновать разработку соответствующего вычислительного метода.

Глобальный (абсолютный) и локальный экстремум функции

Т . Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Условный экстремум функции

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

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

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

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

1. Составление функции Лагранжа.

2. Нахождение частных производных от функции Лагранжа по переменным xj и li и приравнивание их к нулю.

3. Решая систему уравнений находят точки, в которых целевая функция задачи может иметь экстремум.

4. Среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значение функции в этих точках.


54. Определение выпуклой и вогнутой функции

Точка А, для которой выполняются условия (2.44) и (2.45), называется выпуклой линейной комбинацией точек А1 и А2. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя произвольными точками полностью принадлежит и прямолинейный отрезок, их соединяющий.

Общая постановка задачи выпуклого программирования. Теорема о существовании решения задачи ВП (формулировка)

Рассмотрим задачу нелинейного программирования:

Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и gi, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения ЗНЛП (3.3) — (3.5) при условии, что f — вогнутая (выпуклая) функция и ОДР, определяемая ограничениями (3.4) — (3.5), — выпуклая.

Функция f(x1, x2, . xn), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек X1 и X2 из X и любого 0£l£1 выполняется соотношение

Функция f(x1, x2, . xn), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X1, X2 из X и любого 0£l£1 выполняется соотношение

Если f (X) — выпуклая функция, то –f (X) — вогнутая функция, и наоборот.

Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция. Задача (3.3) — (3.5) является задачей выпуклого программирования, если функция f(x1, x2, . xn) является вогнутой (выпуклой), а функции gi (X) (i=1, . m) — выпуклыми.

Т е о р е м а. Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Говорят, что множество допустимых решений задачи (3.3) — (3.5) удовлетворяет условию регулярности, если существует по крайней мере одна точка Xi, принадлежащая ОДР такая, что gi (Xi)

Дата добавления: 2018-05-12 ; просмотров: 570 ;

Линейное программирование (ЛП). Геометрическая интерпретация задачи ЛП

Задана ф

т.о. ЛП – мат. Дисциплина, к-я изучает методы нахождения наибольшего или наименьшего знач-я ф-ции нескольких переменных, при условии, что эти переменные удовлетворяют конечному числу линейных ур-ий и неравенств.

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

Любое неотриц. решения системы наз-ся допустимы решение, из этих допустимых решений выбираем min(max) и оно наз-ся оптимальным решением. Оптимальное решение не обязательно единственное.

Суть ЛП: из множ-ва допустимых решений выбрать то, к-е обращает линейную форму минимум.

Задачу нахождения оптимальной ф-ции ЛП можно интерпретировать геометрически. Для этого все ограничения представляют в виде неравенств, тогда каждое нер-во в n-мерном пространстве определяет полупространство расположенное по одну сторону от плоскости, к-е записывается:

— полупространство

— плоскость

Геометрический смысл ЛП – отыскание в многоугольнике Ω точки, к-я наиболее (наименее) уклонена от z=0.

Нелинейное программирование (НП). Аналитические условия решения задач НП. Типы методов НП. Методы решения задач одномерной минимизации. Метод дихотомии. Метод золотого сечения. Методы решения задач многомерной оптимизации. Метод случайного поиска. Метод деформируемого многогранника Нелдера-Мида.

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

В краткой форме задачу н. п. можно записать так:

F (x) → max при условиях g (x) ≤ b, x ≥ 0, где x — вектор искомых переменных; F (x) — целевая функция; g (x) — функция ограничений (непрерывно дифференцируемая); b — вектор констант ограничений (выбор знака ≤ в первом условии здесь произволен, его всегда можно изменить на обратный).

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

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

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

Задачи математического программирования

max (min) Z = ƒ(x); (6.1)

в которой либо целевая функция (6.1), либо ограничения (6.2), либо и то и другое не линейны, называются нелинейными.

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

Читать еще:  Семантика в программировании это

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

Общая постановка задачи нелинейного планирования может быть сформулирована следующим образом: найти параметры Х * (х1, х2,…, хп), обращающих целевую функцию W = ƒ(х1, х2,…, хп) в mах(min) при условии наложенных ограничений

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

Нелинейные задачи составляют широкий класс настолько сложных задач, что до сих пор невозможно разработать общие методы, подобные симплекс-методу в линейном программировании, которые позволяли бы решать любые нелинейные задачи. Но, несмотря на отсутствие универсальных методов, разработаны способы решения специальных классов задач, и прежде всего задач с выпуклыми (вогнутыми) функциями ƒ(х) и φi(x).

Особенности решения задач нелинейного программирования.

При решении задач нелинейного программирования очень важно знать: 1) выпукло или не выпукло множество решений? 2) является ли критериальная функция W = ƒ(х) выпуклой или вогнутой, или не относится ни к тому, ни к другому классу?

Множество выпукло, если оно содержит точки А и В, а так же все точки прямой АВ.

Функция у = ƒ(х), определенная на выпуклом множестве Х, называется выпуклой, если отрезок, соединяющий любые две его точки, принадлежит графику или располагается выше его (рис. 6.1. а). Функция у= ƒ(х), определенная на выпуклом множестве Х, называется вогнутой, если отрезок, соединяющий любые две его точки, принадлежит графику или располагается ниже его (рис. 6.1. б).

Аналогичные понятия можно привести и для функций многих переменных.

В математике доказывается ряд теорем, которые позволяют определять глобальные экстремумы. Так, для задач, в которых множество допустимых решений выпукло: 1) если ƒ(х) – выпуклая функция, то локальный минимум, определенный на выпуклом множестве Х, совпадает с ее глобальным минимумом на этом множестве; 2) если ƒ(х) – вогнутая функция на заданном выпуклом множестве Х, то локальный максимум ƒ(х) является глобальным.

Решение задач линейного программирования симплекс-методом Калькулятор онлайн

Симплексный метод является универсальным методом решения оптимизационных задач. За исходное решение берётся одно из возможных базисных решений (или «план», «программа»). Затем эта программа улучшается до тех пор, пока не будет найдена оптимальная программа. Наш калькулятор онлайн позволяет решать задачи как на максимум целевой функции, так и на минимум. При решении задач на минимум исходная задача линейного программирования сводится к двойственной задаче. При выполнении этих операций на бумаге часто возникают ошибки, а наш калькулятор онлайн поможет своевременно проверить ошибки.

Симплекс метод онлайн

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

Как онлайн калькулятор находит решение задачи линейного программирования?

Он выдаёт шаги решения задачи симплекс методом, на которых преобразуется система ограничений и целевая функция. Это значит, что на соответствующем шаге функция цели не принимает оптимального значения и по определённому правилу совершается переход от одной вершины многогранника решений к другой пока функция цели не примет оптимального значения. По шагам решения можно наблюдать, как переменные, которые входят в выражение целевой функции с коэффициентом 0, являются неосновными, а остальные — основными. Таким образом осуществляется перевод переменных в основные и неосновные.

Материалы по теме Линейное программирование

Поделиться с друзьями

Введите данные вашей задачи, и вы получите подробное решение.
Используются лучшие онлайн-калькуляторы интернета.

Математический анализ

Предел

Производная

Производная функции от одной переменной

Производная функции от двух переменных

Производная функции от трех переменных

Производная параметрической функции

Вторая и третья производные

Интеграл

Разложение дроби на сумму элементарных дробей (для метода неопределнных коэффициентов)

Построение графиков

Построение графика функции (2D) в декартовых координатах

Построение графика функции в полярных координатах

Построение графика функции, заданного параметрически

Построение поверхности (3D)

Сумма числового ряда(см. пример…)

Разложение в ряд Фурье

Дифференциальные уравнения:

Линейное однородное уравнение

Линейное неоднородное уравнение

Уравнение в полных дифференциалах

Линейное однородное уравнение второго порядка с постоянными коэффициентами

Линейное однородное уравнения 2-го порядка вида ay»+by’+cy=0 с начальными условиями

Линейное неоднородное уравнение второго порядка с постоянными коэффициентами

Векторная алгебра и аналитическая геометрия

Пирамида. Задача расчета параметров пространственной пирамиды по координатам вершин. Позволяет найти длины ребер, площади граней, объем пирамиды, длины высот, углы между ребрами, углы между гранями, углы между ребрами и гранями.

Получить уравнение прямой по двум точкам

Получить уравнение плоскости по трем точкам

Разложение вектора по базису

Линейная алгебра

Матрицы

Разложение определителя по строке или столбцу

Обратная матрица (метод алгебраических дополнений)

Обратная матрица (метод присоединенной матрицы)

Характеристическое уравнение матрицы

Собственные значения (числа)

Возведение матрицы в степень

Приведение матрицы к треугольному виду

Системы уравнений

Решение системы линейных уравнений методом Крамера

Решение системы линейных уравнений методом Гаусса

Решение системы линейных уравнений методом обратной матрицы (матричный метод)

Любая система уравнений

Теория вероятностей и математическая статистика

Биномиальное распределение: расчет Pn(k) при данных p и n

Гистограмма: группировка результатов эксперимента, подсчет частот

Обработка выборки (простой статистической совокупности) — будут построены: статистические ряды частот, полигоны частот, гистограмма, функция распределения, найдены точечные оценки математического ожидания и дисперсии.

Особенности задач нелинейного программирования

Обработка группированного ряда абсолютных частот — будут построены: статистические ряды относительных частот, полигоны частот, гистограмма, функция распределения, найдены точечные оценки математического ожидания и дисперсии. ( см.пример…)

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

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

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

(15.3)

с n + m неизвестными , . Решив систему уравнений (15.3), получают все точки, в которых функция (15.1) может иметь экстремальные значения.

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

Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (15.3), как правило, имеет несколько решений.

Пример. Найти точку условного экстремума функции при ограничениях

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

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

Из второго и третьего уравнений следует, что ; тогда

Решив данную систему, получим:

и

Ссылка на основную публикацию
Adblock
detector