1612726833-e6f68fc32d761b4e64266f5c195a8f96 (828578), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Симплекс–таблица прямо допустима, если zi0 ≥ 0, i = 1, . . . , m.Базис B, соответствующий ей, также называется прямо допустимым.Определение 7. Симплекс–таблица двойственнодопустима, если z0j ≥ 0, j = 1, . . . , n.Базис B, соответствующий этой таблице, также называется двойственно допустимым.-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЭлементарное преобразование б.д.р.x(t), t ≥ 0 :xσ(i)(t) = xσ(i) − zist,xs(t) = t,xj (t) = 0, j ∈ S 0\st=xσ(r)zrs=zr0zrs=min(10)zi0zis>0, i≥1 zis.-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-таблица (с.-т.)0 , z 0 , . . .

, z 0 ) (i = 0, m) строкиα0i = (zi0i1inновой симплекс– таблицы:zis0αr , i 6= r, αi = αi −zrs(11)1 α0r =αr .zrsr-я строка, s-й столбец и элемент zrs называютсяведущими.-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-таблица (с.-т.)Соотношения (11) эквивалентны следующимziszrj0, i 6= r, zij = zij −zrszrj0 zrj =.zrsЗамечание 3. Элементарные преобразования сохраняют прямо допустимость с.-т.-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-метод0) Построить симплекс–таблицу, соответствующую заданному базисному допустимому решению(таблица, естественно, будет прямо допустимой, т.е.zi0 ≥ 0, i = 1, m).1) Если симплекс–таблица двойственно допустима,т.е. z0j ≥ 0, j = 1, n, то КОНЕЦ (получено оптимальное решение)2) Иначе, выбрать ведущий столбец s : zos <0, s ≥ 1.-10•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-метод3) Если {i | zis > 0, i ≥ 1} 6= ∅, то выбратьведущую строку r по правилу:zi0zr0= min{| zis > 0, i ≥ 1},zrszisиначе КОНЕЦ (задача неразрешима из-за неограниченности целевой функции).4) Преобразовать симплекс–таблицу, положитьσ(r) := s и перейти на шаг 1.-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛексикографический с.

- м.Пусть α0, α00 ∈ Rn+1.Вектор α0 лексикографически больше вектора α00(α0  α00) ⇔ α0 − α00  0.Симплекс-таблица нормальна, если каждая ее строка αi, i = 1, . . . , m лексикографически большенуля.-12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛексикографический с. - м.0) Начать с нормальной симплекс–таблицы.3) Если {i | zis < 0, i ≥ 1} 6= ∅, то выбратьведущую строку r по правилу:11αr = lex min{αi | zis > 0, i ≥ 1},zrszisиначе КОНЕЦ (задача неразрешима).-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСохранение нормальности с.-т. на шаге 4:1. αr  0, zrs > 0 ⇒ z1 αr  0zis rs2.

zis ≤ 0 ⇒ αi − z αi αi  0rs3. zrs > 0 ⇒ zis[ z1 αi − z1 αr ]  0.rsisЛекскографическое возрастанение 0-й строки:z0s < 0, zrs > 0 и αr  0, тоz0sαr  α0 .α0 −zrsИтак базисы не могут повторятся, следовательно,метод конечен.-14•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛЕКЦИЯ № 4Симплекс-метод, теория двойственности ЛП1. Двухфазный симплекс-метод или метод искусственного базиса2. Теоремы двойственности ЛП-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетод искусственного базисаПусть x = (x1, .

. . , xn), u = (u1, . . . , um).Рассмотрим вспомогательную задачу:ξ = u1 + · · · + um −→ minAx + Eu = b ≥ 0(aix + ui = bi ≥ 0, i = 1, m)x, u ≥ 0z 0 = (0, b) ∈ Rn+m – б.д.р.-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетод искусственного базисаВспомогательная задача разрешима и min ξ ≥ 0.Пусть z ∗ = (x∗, u∗) – оптимальное решениеA. min ξ > 0 ⇐⇒ Q = ∅B.

min ξ = 0 =⇒ u∗i = 0, i = 1, m, =⇒вектор x∗ – доп. реш. задачи (5)-(7) =⇒ x∗ –б.д.р. задачи (5)-(7).0{Aj |j ∈ S} ∪ {Ei|i ∈ I } – базис z ∗, где0S ⊆ {1, . . . , n}, I ⊆ {1, . . . , m} и-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетод искусственного базиса0|S| + |I | = m. ТогдаXXAk =zjk Aj +µik Eij∈Si∈I0Возможны случаи:0B1. I = ∅.00B2. I 6= ∅ и ∃r ∈ I , ∃s 6∈ S µrs 6= 0.00B3. I 6= ∅ и ∀r ∈ I , ∀s = 1, n µrs = 0.-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетод искусственного базиса0B1. I = ∅ =⇒ |S| = m =⇒ множество {Aj |j ∈S} – базис б.д.р. x∗.Преобразовать оптимальную с.-т.:1. Вычеркнуть столбцы для переменных:u1, . .

. , um.2. Пересчитать 0-строку: z00 = −(c, x∗),Pz0k = 0, k ∈ S, z0k = ck − j∈I cj zjk , k 6∈S.-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетод искусственного базиса00B2. I 6= ∅ и ∃r ∈ I , ∃s 6∈ S µrs 6= 0 =⇒Выполнить элементарное преобразование с.-т. с ведущим элементом µrs 6= 0. Новая с.-т.

соответствует базису0{Aj |j ∈ S ∪ {s}} ∪ {Ei|i ∈ I \ {r}}.-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетод искусственного базиса00B3. I 6= ∅ и ∀r ∈ I , ∀s = 1, n : µrs = 0.Ограничения aix = bi системы (6) с номерами0i ∈ I являются избыточными.-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПервая теорема двойственностиТеорема 5 (Первая теорема двойственности). Прямая и двойственная к ней задачилибо одновременно разрешимы, либо одновремно неразрешимы.При этом в первом случае оптимальные значения целевых функций этих задачсовпадают, а во втором случае по крайнеймере одна из задач неразрешима в силунесовместности ее ограничений.-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: двойственная задачаПрямая задачаnXw(x) =cj xj → minДвойственная задачаmXz(y) =biyi → maxj=1aix ≥ biaix = bixj ≥ 0xj − своб.i=1iijj∈∈∈∈I1I2J1J2yi ≥ 0yi − своб.yAj ≤ cjyAj = cj .Упражнение.Техника получения этой схемы: либо повторить выкладки, приведшие к задаче (8), (9), либо воспользоваться сводимостью общей задачиЛП к задаче ЛП в канонической форме и применить готовый рецепт(задача (8), (9)).-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitВторая теорема двойственностиТеорема 6 (Вторая теорема двойственности или теорема о дополняющей нежесткости).

Допустимые решения x и y соответственно прямой и двойственной задачи оптимальны тогда и только тогда, когда выполняются условия:yi(aix − bi) = 0 (i ∈ I),(cj − yAj )xj = 0 (j ∈ J ).-10•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛЕКЦИЯ № 5Теория двойственности ЛП (продолжение)1. Теоремы Фаркаша – Минковского и ГорданаНеобходимые условия экстремума2. Необходимые условия оптимальностиФритца–Джона3.

Необходимые условия оптимальностиКуна–Таккера-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitТеорема 7 (теорема Фаркаша–Минковского).Система уравнений Ax = b, x ≥ 0 разрешима в том и только в том случае когда неравенство (b, y) ≤ 0 выполняется для всех решений системы уравнений yA ≤ 0.Доказательство. Необходимость. Пусть ∃xAx = b, x ≥ 0 и пусть y — произвольное решение системы yA ≤ 0.

Тогда(b, y) = (Ax, y) = (x, yA) ≤ (x, 0) = 0.-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitДостаточность. Пусть неравенство (b, y) ≤0 выполняется для всех решений системы неравенств yA ≤ 0.-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСледствие 5. Система уравнений Ax ≤ bразрешима в том и только в том случаекогда неравенство (b, y) ≥ 0 выполняется для всех решений системы уравненийyA = 0, y ≥ 0.Ax ≤ b разрешима ⇐⇒ разрешима системаAx1 − Ax2 + Eu = b, x1, x2, u ≥ 0 ⇐⇒ когда неравенство (b, y) ≤ 0 выполняется для всехрешений системы уравнений yA ≤ 0, −yA ≤0, Ey ≤ 0 ⇐⇒ неравенство (b, y) ≥ 0 выполняется для всех решений системы уравнений yA =0, y ≥ 0.

-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСледствие 6 (теорема Гордана). Имеет место одно и только одно из следующих двухусловий:1. Разрешима система уравнений Ax <0;2. существует такой 6= 0 вектор y, чтоyA = 0, y ≥ 0.Действительно, система уравнений Ax < 0 разрешима ⇐⇒ разрешима система уравнений Ax ≤(−1, −1, . . . , −1)>. По теореме Ф.–М. разрешимость последней системы эквивалентна выполнению условия:-5•First •Prev •Next •Last •Go Back •Full Screen •Close •Quitесли вектор y решение системы yA = 0, y ≥0, то выполняется неравенство −y ≥ 0. Т.е. несуществует ненулевого вектора y такого, что yA =0, y ≥ 0.Теперь пусть существует ненулевой вектор y такой, что yA = 0, y ≥ 0.

Но тогда не выполняется неравенство −y ≥ 0 =⇒ не выполнено условие теоремы Ф.–М. =⇒ система Ax ≤(−1, −1, . . . , −1)> неразрешима =⇒ неразрешима системаAx < 0.-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitРассмотрим задачу нелинейного программированияНайти:min f (x)(1)при условии, чтоϕi(x) ≤ 0, i = 1, m.(2)Здесь f, ϕi : Rn −→ R и f, ϕi ∈ C 1.Определение 8. Направление s 6= 0 называется возможным в точке x ∈ Q, если существует такое число β, что x + βs ∈ Q, ∀β ∈[0, β].-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitОграничение ϕi называется активным в точкеx, если ϕi(x) = 0.

I(x) – множество номеровограничений активных в данной точке.Лемма 7. Если вектор s 6= 0 удовлетворяет системе0(ϕi(x), s) + σ ≤ 0, i ∈ I(x),при некотором σ > 0, то направление sявляется возможным в точке x.Доказательство. Считаем, что I(x) 6= ∅( т.к. иначе любое направление s 6= 0 являетсявозможным)-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЕсли i 6∈ I(x), то малое перемещение не нарушает строгое ограничение ϕi(x) < 0 =⇒ найдется подходящее βi.Пусть i ∈ I(x)(≡ ϕi(x) = 0).

Далее рассуждаем от противного. Допустим, что ϕi(x+βs) >0, для достаточно малых β > 0 =⇒ϕi(x+βs)/β = (ϕi(x+βs)−ϕi(x))/β −→0−→ (ϕi(x), s) ≥ 0 (при β → 0).Противоречие. Т.к. по условиям леммы0(ϕi(x), s) < 0, -9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitГеометрическая форма необходимых условий оптимальностиТеорема 8. Для того, чтобы точка x ∈ Qявлялась точкой локального минимума функции f на множестве Q необходимо, чтобыдля любого решения (s, σ) системы0(ϕi(x), s) + σ ≤ 0, i ∈ I(x),0(f (x), s) + σ ≤ 0,выполнялось условиеσ ≤ 0.(12)(13)(14)•First-10•Prev •Next •Last •Go Back •Full Screen •Close •QuitТеорема 9 (Необходимые условия оптимальности Фритца–Джона).

Пусть x∗ — локальный экстремум задачи (1), (2), функции f ,ϕi, i = 1, m, непрерывны и непрерывнодифференцируемы. Тогда найдутся такиене все равные 0 множители λi ≥ 0, i =0, m, чтоmX00∗λ0f (x ) +λiϕi(x∗) = 0n,(15)i=1λiϕi(x∗) = 0, i = 1, m.(16)-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСледовательно0λ0f (x∗) +X0λiϕi(x∗) = 0n,i∈I(x∗)λ0 +Xλi = 1.(17)i∈I(x∗)Положим λi = 0, i 6∈ I(x∗) и получимmX00∗λ0f (x ) +λiϕi(x∗) = 0n,i=1λiϕi(x∗) = 0, i = 1, m. -12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitТеорема 10 (Необходимые условия оптимальности Куна–Таккера).

Характеристики

Список файлов лекций