Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск
Вхід в абонемент


Интернет реклама УБС






1. Свойства задач линейного прогр-ния. Критерий опт-е опорного плана.

Пусть xi = (xi1 ..., xin) еEn, i = 1, ..., r, r2. Выпуклой линейной оболочкой точек x1, ..., xr называется совокупность точек вида

, где, i = 1, ..., r, - любые числа, удовлетворяющие условиям

Любая точка выпуклой линейной оболочки называется выпуклой линейной комбинацией точек x1, ..., xr.

При r = 2 выпуклая линейная оболочка называется отрезком, соединяющим точки x1, x2, i обозначается [x1, x2], то есть

[x1, x2] = {x: x = бx1 + (1-б) x2, 0? бы? 1}.

Множество W называется выпуклой, если для любых x1, x2еW выполняется [x1, x2] W.

Напомним также, что множество

называется пiвпростором в En, а множество (1)

гiперплощиною в En.

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

Л1 Пересечение выпуклых множеств является выпуклым множеством.

Доказательство. Пусть A и B выпуклые множества, A? B - их сечение. Рассмотрим произвольные точки x1, x2 есть A? B. По определению пересечения множеств x1, x2еA, x1, x2еB. Поскольку A и B - выпуклые множества, то [x1, x2] A, [x1, x2] B. Отсюда по определению пересечения [x1, x2] A? B.

Л2 Пiвпростiр является выпуклым множеством.

Доказательство. Рассмотрим, например, пiвпростiр

и пусть x1, x2 еP. Это означает, что

(2), где x1k ..., xnk - координаты точки xk. Рассмотрим некоторую произвольную точку x отрезка

[x1, x2] i покажем, что она также принадлежит Р. Пусть

х = АХ1 + (первой) х2, 0 <а <1. Имеем с учетом (2)

Это означает, что произвольная точка x отрезка [x1, x2] принадлежит P. Итак пiвпростiр является выпуклым множеством.

Л3. Гiперплощина является выпуклым множеством. Доказательство. Гiперплощина (1.4) является пересечение пiвпросторiв и

являющиеся выпуклыми множествами согласно леммы 2, следовательно, гiперплощина является выпуклым множеством согласно леммы 1.1.

озн. Многогранна множеством называется пересечение конечных числа пiвпросторiв. Ограниченная многогранна множество называется многогранником.

Понятно, что допустимая множество D ЗЛП является многогранна множеством (если она не пустая). Иногда область D называют многогранником, добавляя слова "ограниченный" или "неограниченный".

Непосредственным следствием этих определений и доказанных утверждений является следующая теорема.

Т1 Допустимая множество D ЗЛП является выпуклой многогранна множеством.

Итак, ЗЛП состоит в нахождении минимума (максимума) линейной функции L (x) на выпуклой многограннiй множестве D.

озн. Точка x выпуклой мн-ны X называется угловой (крайней), если ее нельзя представить в виде x = бx1 + (1-б) x2, деx1, x2 еX, x1? X2, 0 <б <1.

С геометрической точки зрения точка x является крайней точкой множества X, если ее нельзя расположить внутри отрезка, концы которого принадлежат X.

Угловые точки выпуклой многогранна множества называются ее вершинами.

Критерий оптимальности.

Признак неограниченности целевой функции

Приведенные в предыдущем параграфе соображения составляют основу симплекс-метода решения ЗЛП.

Прежде, чем сформулировать алгоритм этого метода, докажем несколько необходимых для его обоснования утверждений.

Т2 (критерий оптимальности базисного решения ЗЛП). Если для некоторого базисного решения x * оправдываются неравенства? J? 0, j = 1, ..., n, то x * - оптимальное решение ЗЛП.

Доказательство. Пусть для базисного решения x * = (у1, ..., Вm 0, ..., 0), что определяется канонической форме ограничений ЗЛП

бх = у, х0, у0, выполняется условие теоремы, то есть

Мы должны доказать, что для любого допустимого решения y = (y1, ..., yn)

(бy = у, y 0) выполняется неравенство L (y) L (x *), а это и будет означать, что x * - оптимальное решение ЗЛП.

Действительно, из условия теоремы и из допустимости решения y имеем

что и доказывает теорему.

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

Пусть ф-ция:, i = 1, ..., m. - Имеют определенные свойства гладкости.

озн. Гладкой конечно-мерной зад. с ограничениями типа равенств и неравенств наз. такую задачу: extr,, = 1, ...,. Рассмотрим зад. на min. Точка = (), для которой испол. ум.:; наз. т. locmin, если окрестность такой, что:;.

2. Необходимые и достаточные условия extr. а) принцип Лагранжа. Теорема 1.

Пусть точка, ф-ции является непрерывно дифференцированными в окрестности т., тогда существует ненулевой вектор множителей Лагранжа такой, что для ф-ции Лагранжа испол. условия: а) стационарности:,. б) доп. нежесткости:

в) условие неотрицательности:, Замечание: Если рассматривается задача на max, то в условии в). В задачи (Р) ограничения типа равенств всегда можно записать в виде:,,. Для такого случая принцип Лагранжа также подтверждается и дает те же критические точки, то есть те точки, удовлетворяющие условию а)-в).

б) Необходимые и достаточные условия extr второго порядка.

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

Теорема 3. Достаточное условие extr. Пусть ф-ции является дважды непрерывно дифференцированными в окрестности т., векторы - лин. независимы и существует вектор множителей Лагранжа такой, что для ф-ции задачи Лагранжа испол. условие а) и условие, где - положительные стала. Тогда K, L те же, что в теореме 2. Формулировка теоремы (2), (3) для случая задачи на max отр. тем, что, а ф-ция.

Алгоритм получения решения.

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

4. Задача выпуклого программирования. Теорема Куна-Таккера.

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

озн Точка является допустимой точкой в с-чи, если Понятно, что множество допустимых точек является выпуклой. Точка, если,.

Теорема Куна-Таккера: 1), тогда существует ненулевой вектор множителей Лагранжа:, такой, что и выполняются условия: а) - условие


Страницы: 1 2 3