Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Двойственный симплекс-метод.






    Двойственный симплекс метод состоит в том, что если мы не можем подобрать базисный план для задачи (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






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.