Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Двойственный симплекс-метод.
Двойственный симплекс метод состоит в том, что если мы не можем подобрать базисный план для задачи (1), то можем воспользоваться двойственной задачей. Z=сTx→ max Ax=b (1) x≥ 0 Пусть ∆ Т≤ 0 предположим, что у вектора хБ есть отрицательная координата. Возможно ли использовать данный допустимый базисный план, при поиске искомого решения Рассмотрим двойственную задачу: w=bTy→ min (2) ATy≥ c v=ATy-c≥ 0 w= bTy+0v→ min ATy-v=c v≥ 0 ∆ T=cT-cБTAБ-1A≤ 0 cБТА-1БА≥ cТ АТ(АБ-1)ТcБ≥ c у=(АБ-1)ТcБ АТу≥ c у=(АБ-1)ТcБ – допустимый план значений (2) =(y, v) D=(АТ -Е) ∆ T=bТ-bБТDБ-1D ∆ Tj=bТ-bБТDj-1D Если jϵ Б АБ=Е, то ∆ =-V, ∆ Б=0, ∆ Н≤ 0 vН≥ 0 Б=(у, vН) =vБ DБ= DН= D= =DБ +DН(vБ)=c =0 =0-(bT 0)DБ-1DН DБDН= = -(bT 0) =bТ= xБ ≥ 0 Выбранный нами базис не является решением. Оптимальный план можно улучшить х= → i0, t< 0 Вводим координату х0 в базисную. Выводим из вектора у координату уi0. Находим ϴ =min Определим, какую переменную необходимо вывести из базиса, а какую ввести в небазисный DБ +DН VБ=c DБ-1DБ +DБ-1DНvБ=DБ-1c +DБ-1DНvБ=DБ-1c +DБDНvБ=DБc + vБ= уТ-vБ=сБ vН-АНТvБ=АНТсБ-сН vН= АНТсБ-сН+ АНТvБ jϵ H vj=AjТсБ-сj+AjТvБ vj=∆ j+AjТvБ vБ= ← i0 t> 0
|