Студопедия

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

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

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






  • Решение задачи 1.3






    Максимизировать целевую функцию:

    Y=-4x1-x2+3x3-2x4 → max

    При ограничениях:

    1x1+2x2+0x3+0x4 ≥ 3

    -2x1+0x2+0x3+2x4 ≤ -9

    -x1-x2+x3+2x4 ≤ -5

    x1+0x2-2x3+x4 ≥ 2

    x1, 2, 3, 4 ≥ 0

     

    Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x5, x6, x7 и x8.

    1x1+2x2+0x3+0x4 -1x5+0x6+0x7+0x8=3

    2x1+0x2+0x3-2x4 +0x5-1x6+0x7+0x8=9

    x1+x2-x3-2x4 +0x5+0x6-1x7+0x8=5

    x1+0x2-2x3+x4 +0x5+0x6+0x7-1x8=2

    Выразим допустимый базис в форме Таккера:

    X5=-3-(-1x1-2x2+0x3+0x4)

    X6=-9-(-2x1+0x2+0x3+2x4)

    X7=-5-(-x1-x2+x3+2x4)

    X8=-2-(-x1+0x2+2x3-x4)

    Целевая функция в форме Таккера:

    Y=0-(4x1+x2-3x3+2x4)

    На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.10).

    Таблица 1.10

    БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
    X5 -3 -1 -2            
    X6 -9 -2              
    X7 -5 -1 -1            
    X8 -2 -1     -1        
    Y       -3          

    Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X6. Результат отображен в таблице 1.11.

    Таблица 1.11

    БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
    X5 3/2   -2   -1   -1/2    
    X1 9/2       -1   -1/2    
    X7 -1/2   -1       -1/2    
    X8 5/2       -2   -1/2    
    Y -18     -3          

    Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7. Результат отображен в таблице 1.12.

    Таблица 1.12

    БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
    X5 5/2     -2 -3   1/2 -2  
    X1 9/2       -1   -1/2    
    X2 1/2     -1 -1   1/2 -1  
    X8 5/2       -2   -1/2    
    Y -37/2     -2     3/2    

    Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X8. Результат отображен в таблице 1.13.

    Таблица 1.13

    БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
    X5         -5     -2  
    X1 9/2       -1   -1/2    
    X2 7/4       -2   1/4 -1 1/2
    X3 5/4       -1   -1/4   1/2
    Y -16                

    В столбце свободных членов и в строке коэффициентов отсутствуют отрицательные элементы, а следовательно, полученный план оптимален. Произведём проверку, подставив полученные значения для переменных в начальные условия и убедившись в их верности, выписываем ответ.

     

    Ответ: Решение оптимально

    Y=-16

    X=(9/2; 7/4; 5/4; 0; 5; 0; 0; 0)

    Количество итераций=3

     

     


    Выводы к Главе 1

     

    § В первой главе на примере данных трех задач продемонстрированы основные этапы и приемы, применяемые при решении задач линейного программирования.

    § Сложность решения задач линейного программирования определяется количеством переменных и ограничений в исходной задачe. Количество итераций зависит от того, на сколько «далеко» находится начальное базисное решение от оптимального.


    Целочисленное программирование

    Решение полностью целочисленной задачи

    Максимизировать целевую функцию:

    Y=-4x1-x2+3x3-2x4 → max

    При ограничениях:

    x1+2x2+0x3+0x4 ≥ 3

    -2x1+0x2+0x3+2x4 ≤ -9

    -x1-x2+x3+2x4 ≤ -5

    x1+0x2-2x3+x4 ≥ 2

    x1, 2, 3, 4 ≥ 0 и целые






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