1612726833-e6f68fc32d761b4e64266f5c195a8f96 (828578), страница 2
Текст из файла (страница 2)
Базисно допустимые решения2. Критерий разрешимостиСимплекс-метод (С.-м.)1. Идея метода-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: понятие базисного допустимого решения (б.д.р.).Базис — любой набор Aσ(1), . . . , Aσ(m) из m линейно независимых столбцов матрицы системы ограничений A.Матрица B = [Aσ(1), . . . , Aσ(m)] называется базисной.Обозначения:0S = {σ(1), . .
. , σ(m)}, S = {1, . . . , n} \ S, A = [B, N ],где N = [Aj ]j∈S 0 , x = (xB , xN ), xB = (xσ(1), . . . , xσ(m)) —базисные, а xN = (xj )j∈S 0 — небазисные переменные.E xB + B −1N xN = B −1b0(6 )Определение 3. Решение (xB , xN ) = (B −1b, 0) системыуравнений (6) назовем базисным (соответствующим базисуB).-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: понятие б.д.р.Лемма 3. Вектор x — базисное решение системы (6) тогдаи только тогда, когда множество столбцов с индексами измножества S(x) = {j|xj 6= 0} — линейно независимо.Определение 4.
Базисным допустимым решением (б.д.р.)называется любой элемент множества Q, являющийся базисным решением системы уравнений (6).Замечание 2. Решение соответствующее базису B — б.д.р. ⇐⇒B −1b ≥ 0.-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: понятие б.д.р.Определение 5. Вектор x ∈ Q — крайняя точка или вершинамножества Q, если не существует допустимых решений x1 6= x2 из Qтаких, что x = αx1 + (1 − α)x2, где 0 < α < 1.Теорема 3. Вектор x — б.д.р. тогда и только тогда, когда x— крайняя точка множества Q.Доказательство. Пусть x — крайняя точка, но не б.д.р.
Из леммы 3=⇒∃ y 6= 0 : Ay = 0.(∗)-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: понятие б.д.р.При этом можем считать, что (xj = 0 =⇒ yj = 0) =⇒{j|yj 6= 0} ⊆ {j|xj > 0}.(∗∗)Т.к. x ∈ Q, то из (∗) =⇒∀ t ∈ R : z(t) = x + t y — решение (6),тогда из (∗∗) =⇒∀ малого t ∈ R : z(t) ∈ Q.=⇒∃ ε > 0 : x1 = x + εy ∈ Q, x2 = x − εy ∈ Q,=⇒x1 6= x2 и x =1x1 + x2 ⇒→←⇒ x — б.д.р..221-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: понятие б.д.р.Пусть x — б.д.р., но∃ 0 < α < 1, ∃ x1 6= x2, x1, x2 ∈ Q : x = αx1 + (1 − α)x2.По условию Ax1 = Ax2(= b) =⇒ A(x1 − x2) = 0, ноA(x1 − x2) = 0 ⇐⇒ {Aj |x1j 6= x2j } — линейно зависимо ⇒{Aj |αx1j + (1 − α)x2j > 0} — линейно зависимо ⇒{Aj |xj > 0} — линейно зависимо ⇒→←,т.е. если x — б.д.р., то x — крайняя точка множества Q.
-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: Критерий разрешимостиТеорема 4 (Критерий разрешимости). Задача линейногопрограммирования (5)-(7) разрешима тогда и только тогда,когда множество допустимых решений не пусто и целеваяфункция ограничена на нем.Доказательство. Необходимость очевидна. Для доказательства достаточности покажем, что∀ x0 ∈ Q ∃ б.д.р. x : w(x) ≤ w(x0).Пустьx ∈ Q0 = {x ∈ Q|w(x) ≤ w(x0)} 6= ∅и имеет минимальное число ненулевых компонент (supp(x)).Докажем, что x — б.д.р. Допустим противное.
=⇒-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: Критерий разрешимостимножество{Aj |xj > 0} линейно зависимо =⇒∃ y 6= 0 : Ay = 0 и если xj = 0, то yj = 0.Пусть w(y) ≤ 0 (если необходимо, то возьмем −y ). Положимx(t) = x + ty. Выполняется следующее свойство∀ малого t ∈ R : x(t) ∈ Q.1). Пусть ∀j : yj ≥ 0 ⇒ ∀t ≥ 0 x(t) ≥ 0 ⇒ ∀t ≥ 0 x(t) ∈ Qотсюда и неравенства w(x(t)) = w(x)+tw(y) ≥ const(по условию)учитывая, что w(y) ≤ 0 и t ≥ 0 — произвольно,имеем: w(y) = 0 и, следовательно, w(x(t)) = w(x) ∀t.-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: Критерий разрешимостиТ.к. из условия yj > 0 ⇒ xj > 0, то∀ малого по абсолютной величине t < 0 : x(t) ∈ Q.Найдем такое t наибольшее по абсолютной величине из условия:∀j(yj > 0 ⇒ xj + tyj ≥ 0)которое эквивалентно условию:∀j(yj > 0 ⇒ xj ≥ (−t)yj ) ⇐⇒(−t) = minyj >0xjyj⇐⇒ t = − minyj >0xjyj.Итак x(t) ∈ Q и w(x(t)) = w(x) ≤ w(x0) ⇒ x(t) ∈ Q0.Получили противоречие.
Т.к. supp(x(t)) = supp(x) − 1.-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: Критерий разрешимости2). Пусть ∃j : yj < 0. Тогда∀ достаточно малых t ≥ 0 : x(t) ∈ Q.Найдем наибольшее такое t из условия:∀j(yj < 0 ⇒ xj + tyj ≥ 0)которое эквивалентно условию:∀j(yj < 0 ⇒ xj ≥ t(−yj )) ⇐⇒⇐⇒ t = minxj.−yjИтак x(t) ∈ Q и т.к. t > 0, d ≤ 0, то w(x(t)) = w(x) + dt ≤yj <0≤ w(x0) ⇒ x(t) ∈ Q0.Получили противоречие. Т.к.
supp(x(t)) = supp(x) − 1.-10•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛП: Критерий разрешимостиТ.к. по условию Q 6= ∅, то множество базисных допустимых решенийзадачи не пусто. Т.к. оно конечно, то∃ x∗ — б.д.р.: w(x∗) ≤ w(x) ∀ б.д.р. x.Из ранее доказанного следует, что x∗ — оптимальное решение. Следствие 3. Если множество допустимых решений задачиЛП не пусто, то существуют базисные допустимые решения.Следует из доказательства теоремы 4 (взять w(x) ≡ 0).Следствие 4. Если задача ЛП разрешима, то существует оптимальное базисное решение.-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitОпределение грани множества Q00Пусть S ∪ S = {1, .
. . , n}, S ∩ S = ∅. Множество решений системы уравнений0Ax = b, xj = 0, j ∈ S , xj ≥ 0, j ∈ S,называется гранью множества допустимыхрешений (6)-(7).-12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitОпределение грани множества Q0Величина n − m − |S | — размерность данной0грани (здесь m + |S | – ранг системы уравнений).0Так как x – б.д.р., то |S | = n−m, следовательно, x – грань размерности 0.0Если |S | = n − m − 1, то получим граньразмерности 1, т.е. ребро: ограниченное или неограниченное.-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИдея симплекс-методаПусть x — б.д.р., B = (Aσ(1), . .
. , Aσ(m)) —базисная матрица. ТогдаExB + B −1N xN = B −1b,0(6 )следовательноExB = B −1b − B −1N xN , иw(x) = cB B −1b + (cN − cB B −1N )xN ,0(5 )-14•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\s(10)-15•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИдея симплекс-методаz0j = cj − cB B −1Aj , j = 1, . . . , n,Величины z0j называются оценками замещения.Знак оценки замещения определяет характер изменения целевой функции при движении по ребру.(z10, . .
. , zm0)> = B −1b,(z1j , . . . , zmj )> = B −1Aj , j = 1, . . . , n.-16•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛемма 4 (признак оптимальности). Если оценки замещения неотрицательны, тотекущее базисное допустимое решение xявляется оптимальным решением задачи(5)–(7).Пусть x ∈ Q. Так как z0j ≥ 0 и xj ≥ 0,00j ∈ S , то из (5 ) следует, чтоX−1w(x) = cB B b+z0j xj ≥ cB B −1b =j∈S 0= w(x) -17•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИдея симплекс-методаЛемма 5 (о неразрешимости). Если дляномера s оценка замещения z0s < 0 и длявсех индексов i коэффициенты замещенияzis неположительны, то в задаче (5)–(7)не существует оптимального решения.-18•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИдея симплекс-методаЛемма 6 (о существовании лучшей вершины). Если оценка замещения z0s < 0 исуществуют базисные переменные с коэффициентами замещения zis > 0, то элементарное преобразование приведёт либов вершину с меньшим значением целевойфункции, либо вершина останется прежней, но изменится её базис.-19•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИдея симплекс-методаПустьt=xσ(r)zrs=zr0zrs=minzi0zis>0, i≥1 zis.Предположим, что t > 0.
Тогда∀i∀t < t : xσ(i)(t) = xσ(i) − zist > 0,xσ(r)(t) = 0 и для ∀t > t имеем xσ(r)(t) < 0=⇒-20•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИдея симплекс-методаСемейство векторов x(t), 0 ≤ t ≤ t – ограниченное ребро множества Q.Вектор x(t) – б.д.р.:(z1s, . . .
, zms)> = B −1As ⇐⇒As = B(z1s, . . . , zms)> ⇐⇒mXAs =zisAσ(i) (отсюда и условия) zrs > 0i=10следует, что матрица B со столбцами-21•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИдея симплекс-метода[Aσ(1), . . . , Aσ(r−1), As, Aσ(r+1), . . . , Aσ(m)]невырождена.0Следовательно B – базис б.д.р. x(t). Т.к.∀t, 0 < t ≤ t, w(x(t)) = −z00+z0st < −z00,то x(t) – искомое б.д.р. с меньшим значением целевой функции.-22•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИдея симплекс-методаПусть t = 0. В силу выбора r : xσ(r)(t) == xσ(r)(0) = xσ(i) = zr0 = 0.0Т.к. zrs > 0, то матрица B со столбцами[Aσ(1), .
. . , Aσ(r−1), As, Aσ(r+1), . . . , Aσ(m)]0снова невырождена. Следовательно B – другойбазис вершины x. -23•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛЕКЦИЯ № 3Симплекс-метод1. Симплекс-таблица (с.-т.)2. Элементарное преобразование б.д.р., базиса и с.-т.3. Алгоритм симплекс-метода4. Лексикографический симплекс-метод-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-таблица (с.-т.)x – допустимое решение задачи (5–7) со значениемцелевой функции (c, x) = w ⇔ пара (w, x) –00решение системы уравнений (5 ), (6 ), (7) илисистемы−w + (cN − cB B −1N )xN = −cB B −1b,0(5 )0−1−1ExB + B N xN = B b,(6 )x≥0-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-таблица (с.-т.)X−w +z0j xj = z00,00(5 )j∈S 0xσ(i) +гдеX00zij xj = zi0, i = 1, m, (6 )j∈S 0z00 = −cB B −1b = −w(x),z0j = cj − cB B −1Aj , j = 1, . . .
, n,(z10, . . . , zm0)> = B −1b,(z1j , . . . , zmj )> = B −1Aj , j = 1, . . . , n.-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-таблица (с.-т.)−wxσ(1).xσ(i).xσ(m)z00z10...zi0...zm0x1z01z11...zi1...zm1.....................xjz0jz1j...zij...zmj.....................xnz0nz1n...zin...zmn-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-таблица (с.-т.)−wx1:xi:xmz00z10:zi0:zm0x101:0:0.
. . xi . . . xm... 0 ... 0... 0 ... 0::... 1 ... 0::... 0 ... 1xm+1z0m+1z1m+1:zim+1:zmm+1. . . xn. . . z0n. . . z1n:. . . zin:. . . zmn-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСимплекс-таблица (с.-т.)Определение 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
