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

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

Дата добавления: март 2006г.

ЛАБОРАТОРНАЯ РАБОТА № 11
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Цель работы: изучение принципов составления оценочных характеристик для задач линейного программирования, получение навыков использования симплекс-метода для решения задач линейного программирования, усвоение различий получаемых результатов, изучение табличной формы применения симплекс-метода.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

Стандартная задача линейного программирования состоит из трех частей: целевой функции (на максимум или минимум) - формула (1. 1), основных oграничений- формула (1. 2), ограничений не отрицательности переменных (есть, нет) формула (1. 3)

    (1. 1)
    i = 1, … m (1. 2)
    (1. 3)

Алгоритм решения задач линейного программирования требует приведения их постановки вканонический вид, когда целевая функция стремится к максимуму (если стремилась к минимуму, то функцию надо умножить на -1, на станет стремиться к максимуму), основные ограничения имеют вид равенства (для приведения к равенствам в случае знаканадо в правую часть каждогo такого k-го неравенства добавить искусственную переменную uk , а в случае знака , uk надо отнять ее из правой части основных ограничений), присутствуют ограничения не отрицательности переменных (если их нет для некоей переменной хk, то их можно ввести путем замены всех вхождений этой переменной комбинацией x1k - х2k = хk, где х1k и х2k ). При этом для решения задачи линейного программирования необходимо иметь базис, т. е. набор переменных хi, в количестве, равным числу основных ограничений, причем чтобы каждая из этих переменных присутствовала лишь в одном основном oграничении и имела свой множительаij = 1. Если таких переменных нет, то они искусственно добавляются в основные ограничения и получают индексыхm+1, xm+2 и т. д. Считается при этом, что они удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате приведения задачи к каноническому виду, то целевая функция задачи остается без изменений, а если переменные добавляются искусственнок основным ограничениям, имеющим вид равенств, то из целевой функции вычитается их сумма, умноженная наМ, т. е. (так называемый модифицированный симплекс-метод). Мы не будем рассматривать задачи, относящиеся к модифицированному симплекс-методу. Для практической работы по нахождению решения задачи линейного программирования (по варианту простогосимплекс-метода) будут использоваться алгоритм итерационного (многошагового) процесса нахождения решения и два типа оперативных оценок, позволяющих делать переходы от одного шага к другому, а также показывающих, когда итерационный процесс остановится и результат будет найден.

Первая оценка - это дельта-оценка, для переменной хj она имеет вид:

(1. 4)

Здесь выражение i B означает, что в качестве коэффициентов целевой функции, представленных в сумме выражения (1. 4), используются коэффициенты переменных, входящих в базис на данном шаге итерационного процесса. Переменнымиаij являются множители матрицы коэффициентов Апри основных ограничениях, рассчитанные на данном шаге итерационного процесса. Дельта-оценки рассчитываются по всем переменнымхi, имеющимся в задаче. Следует отметить; что дельта-оценки базисных переменных равны нулю. После нахождения дельта-оценок из них выбирается наибольшая по модулю отрицательная оценка, переменнаяхk, ей соответствующая, будет вводиться в базис. Другой важной оценкой является тетта-оценка, имеющая вид:

(1. 5)

Т. е. по номеру k, найденному по дельта-оценке, мы получаем выход на переменную хk и элементы столбца ХB делим на соответствующие (только положи тельные) элементы столбца матрицы А, соответствующего переменой xk. Из полученных результатов выбираем минимальный, он и будет тетта-оценкой, аiй элемент столбца B, лежащий в одной строке с тетта-оценкой, будет выводиться из базиса, заменяясь элементомxk, полученным по дельта-оценке. Для осуществления такой замены нужно в i-ой строке k - гo столбца матрицы А сделать единицу, а в остальных элементах k-го столбца сделать нули. Такое преобразование и будет одним шагом итерационного процесса. Для осуществления такого преобразования используетсяметод Гаусса. В соответствии с ним i-я строка всей матрицы А, а также i-я координата ХB делятся на aik(получаем единицу в i-ой строке вводимого в базис элемента). Затем вся i-я строка (если i не единица), а такжеi-я координата ХB умножаются на элемент (-а1k). После этого производится поэлементное суммирование чисел в соответствующих столбцах 1-ой и i-ой строк, суммируются такжеХB1, и (-а1k)*ХBi; . Аналогичные действия производятся для всех остальных строк кроме i-ой (базисной) строки. В результате получается, что вi-ой строке k-го элемента стоит 1, а во всех остальных его строках находится 0. Таким образом осуществляется шаг итерационального алгоритма, Шаги алгоритма симплекс-метода продолжаются до тех пор, пока не будет получен один из следующих результатов. • Все небазисные дельта-оценки больше нуля — найдено решение задачи ли нейного программирования, оно представляет из себя вектор компонент х; , значения которых либо равны нулю, либо равны элементам столбца Х, тав кие компоненты стоят на базисных местах (скажем, если базис образуют переменныех2, x4, х5, то ненулевые компоненты стоят в векторе решения задачи линейного программирования на 2-м, 4-м и 5-м местах).

• Имеются небазисные дельта-оценки, равные нулю, тогда делается вывод о том, что задача линейного программирования имеет бесчисленное множество решений (представляемое лучом или отрезком). Подробно рассматривать случаи такого типа, а также отличия между решениями в виде луча и отрезка мы не будем.

• Возможен вариант получения столбца отрицательных элементов на отрицательной рассчитанной дельта-оценке, в такой ситуации нельзя вычислить тетта-оценки. В этом случае делается вывод, что система ограничений задачи линейного программирования несовместна; следовательно, задача линейного программирования не имеет решения.

Решение задачи линейного программирования, если оно единственное, следует записывать в виде Х* = (.... , .... , .... ) - вектора решения и значения целевой функции в точке решения L*(Х*). В других случаях (решений много или они отсутствуют) следует словесно описать полученную ситуацию. Если решение задачи линейного программирования не будет получено в течение 10-12 итераций симплекс-метода, то следует написать, что решение отсутствует в связи с неограчниченностью функции цели. Для практического решения задачи линейного программирования симплекс-методом удобно пользоваться таблицей вида (табл. 11. 1):

    Таблица 1. 1
    B
    CB
    XB
    A1
    …
    An
    Q
    Базисные
    Целевые
    Правые
    компоненты
    Коэффиц.
    Части
    Базиса
    ограничен
    D
    D1
    Dn
    Задание
    Необходимо решить задачу линейного программирования.
    L(x) = x1 – 2x2 + 3x3
    x1 – 3x2 3
    2x1 – x2 + x3 3
    -x1 + 2x2 – 5x3 3
    Все xi 0 i = 1, …3
    Для начала приведем задачу к каноническому виду:
    L(x) = x1 – 2x2 + 3x3
    x1 – 3x2 + x4 = 3
    2x1 – x2 + x3 + x5 = 3
    -x1 + 2x2 – 5x3 + x6 = 3
    Все xi 0 i = 1, …6

Составляем таблицу симплекс-метода (табл. 1. 2). Видно, что базис образуют компаненты x4, x5, x6:

    B
    CB
    XB
    A1
    A2
    A3
    A4
    A5
    A6
    Q
    A4
    0
    3
    1
    -3
    0
    1
    0
    0
    A5
    0
    3
    2
    -1
    1
    0
    1
    0
    3
    A6
    0
    3
    -1
    2
    -5
    0
    0
    1
    D
    -1
    2
    -3
    0
    0
    0
    A4
    0
    3
    1
    -3
    0
    1
    0
    0
    A3
    3
    3
    2
    -1
    1
    0
    1
    0
    A6
    0
    3
    -1
    2
    0
    0
    0
    1
    D
    9
    5
    2
    0
    0
    3
    0

Таким образом, уже на втором шаге расчетов (вычислений дельта-оценок) получено, что все небазисные дельта оценки положительны, а это означает, что данная задача имеет единственное решение:

Решение задачи запишем в виде:
X* = (0, 0, 3, 3 , 0, 3), L*(X*) = 9.