Решение задач линейного программирования

ЛАБОРАТОРНАЯ РАБОТА № 11

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

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

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

Стандартная задача линейного программирования состоит из трех частей:

целевой функции (на максимум или минимум) - формула (1.1), основных oграничений - формула (1.2), ограничений не отрицательности переменных (есть, нет) - формула (1.3)

(1.1)

i = 1,… m (1.2)

(1.3)

Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид , когда целевая функция стремится к максимуму (если стремилась к минимуму, то функцию надо умножить на -1, на станет стремиться к максимуму), основные ограничения имеют вид равенства (для приведения к равенствам в случае знака надо в правую часть каждогo такого k-го неравенства добавить искусственную переменную u_k , а в случае знака , u_k надо отнять ее из правой части основных ограничений), присутствуют ограничения не отрицательности переменных (если их нет для некоей переменной х_k , то их можно ввести путем замены всех вхождений этой

переменной комбинацией x¹ _k - х ² _k = х _k , где х ¹ _k и х ² _k ). При этом для решения задачи линейного программирования необходимо иметь базис , т.е. набор переменных х _i , в количестве, равным числу основных ограничений, причем чтобы каждая из этих переменных присутствовала лишь в одном основном oграничении и имела свой множитель а _ij = 1 . Если таких переменных нет, то они искусственно добавляются в основные ограничения и получают индексы х _m+1 , x_m+2 и т.д. Считается при этом, что они удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате приведения задачи к каноническому виду, то целевая функция задачи остается без изменений, а если переменные добавляются искусственно к основным ограничениям, имеющим вид равенств, то из целевой функции вычитается их сумма, умноженная на М, т.е. (так называемый модифицированный симплекс-метод ). Мы не будем рассматривать задачи, относящиеся к модифицированному симплекс-методу. Для практической рабо-ты по нахождению решения задачи линейного программирования (по варианту простого симплекс-метода )будут использоваться алгоритм итерационного (многошагового) процесса нахождения решения и два типа оперативных оце-нок, позволяющих делать переходы от одного шага к другому, а также показы-вающих, когда итерационный процесс остановится и результат будет найден.

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

(1.4)

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

(1.5)

Т.е. по номеру k, найденному по дельта-оценке, мы получаем выход на пере-менную х_k и элементы столбца Х^B делим на соответствующие (только положи

тельные) элементы столбца матрицы А, соответствующего переменой x_k . Из полученных результатов выбираем минимальный, он и будет тетта-оценкой, а_i -й элемент столбца B , лежащий в одной строке с тетта-оценкой, будет выво-диться из базиса, заменяясь элементом x_k , полученным по дельт