Студопедия

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

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

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






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    Сам записывает клиентов и напоминает им о визите;
    Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом
  • Табличный симплекс-метод






    Процесс решения ЗЛП можно представить в виде последовательности заполняемых таблиц. Покажем это на примере.

     

    Пример 3.5. Рассмотрим предыдущий пример 3.4. После выделения базиса заполняется таблица (табл. 3.1), где r – число базисных переменных, х 1, …, хr – базисные переменные.

    Таблица 3.1

    Исходная таблица для симплекс-метод.

    Базисные переменные Свободные члены x 1 x 2 xi xr xr+ 1 xj xn
    x 1 b1         a 1 r+ 1 a 1 j a 1 n
    x 2 b2         a 2 r+ 1 a 2 j   a 2 n  
    xi bi         ai, r+ 1 ai j   ai n  
    xr bn             ar, r+ 1 a r j   a r n  
    c 0         c r+ 1 cj   cn  

    r – число базисных переменных

     

    при минимизации по системе вида

    и целевой функции вида (перенос через знак равенства свободных переменных):

    + с r+ 1 x r+ 1 +…+ c j x j +…+ c n x n = c 0.

    Для нашего случая имеем:

    Исходная таблица имеет вид (табл. 3.2).

    Таблица 3.2

    Исходная таблица для симплекс-метода

    Базисные переменные Свободные члены x 1 x 2 x 3 x4 x5
    x 1           -2
    x 2         -2  
    x 3            
            -1  

     

    1) Выбирают разрешающий p -й столбец из условия: оценка с р > 0 и хотя бы один элемент в этом столбце a i p > 0 (в нашем случае р = 5).

    2) Выбирают q-ю разрешающую строку из условия для aip > 0 (в нашем случае: элемент 15 = -2 < 0 и поэтому отношение не рассматривается) ; откуда q = 2.

    3) Производят перерасчёт элементов q-й (2-й) разрешающей строки по формуле:

    a'qk = a qk / a qp, k = 0, 1, …, n.

    a’2k = a 2k / a 25, k = 0, 1, …, 5,

    т.е. все элементы разрешающей строки делят на элемент а 25, находящийся на пересечении разрешающего столбца и разрешающей строки и полученные результаты размещают в новой таблице (табл. 3.3).

    4) Вычисляют элементы всех остальных строк (при k p) по формуле

    a'ik = a ik – a’qk a ip, i = 0, 1, …, r.

    Иначе говоря, к каждой из остальных строк прибавляют вновь полученную разрешающую строку, умноженную на такое число, чтобы в клетках столбца для х 5 появились нули, и записывают преобразованные строки на месте прежних в новой таблице (табл. 3.3). Базис в новой таблице изменится с х 1, х 2, х 3 на х 1, х 5, х 3. Далее все рассуждения повторяются.

    Таблица 3.3

    Таблица с новым базисом х1, х2, х3

    Базисные переменные Свободные члены x 1 x 2 x 3 x4 x5
    x 1         -3  
    x 5         -2  
    x 3   1/5     -1 -1/5   1/5        
    -2   -1      
                             

    Для таблицы 3.3 разрешающий столбец с переменной х 4, т. к. с 4 = 1> 0,

    а 34 = 5> 0. В качестве разрешающей строки выбирается строка с базисной переменной х 3, т. к. а 34 = 5> 0. Все элементы базисной строки нормируются делением на 5. С помощью вновь полученной базисной строки в разрешающем столбце с х 4 формируются нули (см. табл. 3.4).

    Таблица 3.4

    Итоговая таблица с оптимальным решением

    Базисные переменные Свободные члены x 1 x 2 x 3 x 4 x 5
    x 1 28/5   7/5 3/5    
    x 2 12/5   3/5 3/5    
    x 4 1/5   -1/5 1/5    
    -11/5   -4/5 -1/5    

     

    Строка с не имеет положительных оценок сj в последней 5-й строке. Следовательно, достигнуто оптимальное решение , которое соответствует .

    Для сведения задачи на max к задаче на min надо целевую функцию умножить на (-1), а далее все рассуждения и преобразования остаются прежними. Полученное оптимальное значение опять-таки умножается на (-1), что является max значением целевой функции.

     






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