Быстрый поиск

Решение оптимизационной задачи линейного программирования - (курсовая)

p>Добавим к нашей финальной симлекс-таблице строку и столбец, соответствующие построенному ограничению и новой базисной переменнойХ9:

    БП
    X1
    X2
    X3
    X4
    X5
    X6
    X7
    X8
    X9
    БР
    E
    1, 67
    1, 67
    0
    0
    0
    0
    2, 5
    2, 5
    0
    40
    X3
    1
    1
    1
    0
    0
    0
    1
    0
    0
    8
    X6
    -0, 67
    -0, 67
    0
    0
    0
    1
    -0, 5
    0, 5
    0
    0
    X4
    0, 44
    0, 11
    0
    1
    0
    0
    0, 17
    0, 17
    0
    2, 67
    Х5
    0, 22
    0, 55
    0
    0
    1
    0
    0, 33
    0, 33
    0
    5, 33
    X9
    -0, 44
    -0, 11
    0
    0
    0
    0
    -0, 17
    -0, 17
    1
    -0, 67
    Таблица 8. Симплекс-таблица №7.

Как видно, полученная симплекс-таблица содержит недопустимое решение (переменнаяХ9 имеет отрицательное значение). Произведем дальнейший пересчет таблицы, причем ведущую строку определяем максимальным по модулю отрицательным элементом столбца решений, а ведущий столбец– минимальным по модулю отношением элемента Е-строки к отрицательным элементам ведущей строки. Пересчет симплекс-таблицы осуществляется на основе стандартных процедур симплекс-метода. Итак, переменная, исключаемая из базиса – это X9, т. к. ее значение –0, 67- это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменнуюX1, т. к. |1, 67/(-0, 44)|=3, 8, |1, 67/(-0, 11)|=15, 2, |2, 5/(-0, 17)|=14, 7, 3, 8 – минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен –0, 44. Получим новую симплекс-таблицу: БП

    X1
    X2
    X3
    X4
    X5
    X6
    X7
    X8
    X9
    БР
    E
    0
    1, 25
    0
    0
    0
    0
    1, 875
    1, 875
    3, 75
    37, 5
    X3
    0
    0, 75
    1
    0
    0
    0
    0, 625
    -0, 375
    2, 25
    6, 5
    X6
    0
    -0, 5
    0
    0
    0
    1
    -0, 25
    0, 75
    -1, 5
    1
    X4
    0
    0
    0
    1
    0
    0
    0
    0
    1
    2
    Х5
    0
    0, 5
    0
    0
    1
    0
    0, 25
    0, 25
    0, 5
    5
    X1
    1
    0, 25
    0
    0
    0
    0
    0, 375
    0, 375
    -2, 25
    1, 5
    Таблица 9. Симплекс-таблица №8.

Все значения базисных переменных стали неотрицательными, это означает остановку вычислительного процесса на данной итерации и анализ полученных результатов. Как видно из таблицы, в базис вошла новая переменнаяХ1, переменные Х3, Х4 и Х5 уменьшили свое значение, а переменная Х6 увеличилась. Значение целевой функции уменьшилось и стало равно 37, 5, что объясняется тем, что оптимальное нецелочисленное решение было отсечено нашим дополнительным ограничением, и для поиска оптимального целочисленного решения мы ушли вглубь области допустимых решений, где значение целевой функции меньше оптимального. Наше решение все еще нецелочисленное, поэтому составим новое ограничение.

Переменная, имеющая максимальную дробную часть – это Х3 ({6, 5}=0, 5) (Х1 имеет такую же дробную часть, поэтому выбрали любую из них, например, Х3), она должна быть целой, переменные Х7 , Х8 и Х9 могут быть дробными, переменная Х2должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменнойХ3 и небазисных переменных Х2 , Х7 , Х9 ? 0 (0, 75? 0, 0, 625? 0, 2, 25? 0), то коэффициент при переменной Х2 рассчитаем по формуле (3): L1={0, 75}=0, 75, коэффициенты при переменных Х7 и Х9 рассчитаем по формуле (1): L3=0, 625, L4=2, 25. Так как коэффициент на пересечении базисной переменной Х3 и небазисной переменной Х8
Или, после приведения к стандартному виду, получим:
-0, 25Х2 – 0, 625Х7 – 0, 375Х8 – 2, 25Х9 + Х10 = -0, 5

Добавим это ограничение к нашей предыдущей симплекс-таблице:

    БП
    X1
    X2
    X3
    X4
    X5
    X6
    X7
    X8
    X9
    X10
    БР
    E
    0
    1, 25
    0
    0
    0
    0
    1, 875
    1, 875
    3, 75
    0
    37, 5
    Х3
    0
    0, 75
    1
    0
    0
    0
    0, 625
    -0, 375
    2, 25
    0
    6, 5
    X6
    0
    -0, 5
    0
    0
    0
    1
    -0, 25
    0, 75
    -1, 5
    0
    1
    X4
    0
    0
    0
    1
    0
    0
    0
    0
    1
    0
    2
    X5
    1
    0, 5
    0
    0
    1
    0
    0, 2
    0, 25
    0, 5
    0
    5
    Х1
    1
    0, 25
    0
    0
    0
    0
    0, 375
    0, 375
    -2, 25
    0
    1, 5
    X10
    0
    -0, 25
    0
    0
    0
    0
    -0, 375
    -0, 375
    -2, 25
    1
    -0, 5
    Таблица 10. Симплекс-таблица №9.