Студопедия

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

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

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






  • Решение двойственных задач






     

    Теория двойственности находит широкое практическое применение. Сформулированные теоремы двойственности позволяют получить решение одной задачи, процесс решения которой по той или иной причине затруднителен, по оптимальному решению двойственной к ней. К такой причине относится значительное превышение числа ограничений над числом переменных задачи, так как объем вычислений при решении задач линейного программирования симплекс-методом определяется, в основном, числом ограничений. Также при необходимости решения задачи с ограничениями вида «> =» можно перейти к решению двойственной, которая будет иметь ограничения вида «< =», что позволяет избежать ввода искусственных переменных.

    Рассмотрим процесс получения решения двойственной задачи на основании оптимального решения исходной. Подставим в ограничения исходной задачи значения переменных x1* = 2, x2* = 4 в оптимальном плане:

     

    6*2 +6*4 < = 36

    4*2 + 8*4 < = 40

    4*2 + 2*4< = 20

     

    На основании второй основной теоремы двойственности переменная двойственной задачи y2, соответствующая второму ограничению исходной, которое обратилось при подстановки оптимального плана в строгое неравенство, равна нулю (y2* = 0).

    Поскольку переменные x1, x2 в оптимальном плане имеют положительные значения, то соответствующие им ограничения двойственной задачи при подстановке в них ее оптимального плана обращаются в равенство. Учитывая, что y2* = 0, получим

    6y1 + 4y3 = 12,

    6y1 + 8y3 = 15.

     

    Решив полученную систему двух линейных уравнений с двумя переменными, найдем оптимальный план двойственной задачи: y1* = 3/2, y2* = 0, y3* = ¾. Согласно первой основной теореме двойственности fmax = zmin = 84.

     

    Контрольные вопросы и упражнения

    1. Какая задача называется двойственной?

    2. Сформулируйте правило построения двойственной задачи.

    3. В чем отличие симметричных задач двойственной пары от несимметричных?

    4. Как по решению исходной задачи можно найти решение двойственной?

    5. Постройте задачи, двойственные к данным:

     

    а) f = x1 – 2x2 + 3x3 – xi → max;

     

    2x1 – x2 + 2x3 – 3x4 ≤ 5,

    x1 + 2x2 – x3 + x4 ≤ 3,

    __

    xj ≥ 0 (j = 1, 4);

     

    б) f = 3x2 – x4 → max;

     
     


    x1 - 2x2 + x4 = 8,

    x2 + x3 – 3x4 = 6,

    __

    xj ≥ 0 (j = 1, 4);

     

    в) f = 5x1 + x2 → max;

     

    x1 – x2 ≤ 2,

    x1 – 3x2 ≤ 3,

     

    x1 ≥ 0, x2 ≤ 0;

     

    г) f = x1 – 2x2 → min;

     
     


    x1 – x2 ≥ 5,

    -x1 + x2 ≥ 1,

     

    x1 ≥ 0, x2 ≥ 0.

     






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