РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Цель работы
ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Обычная задача линейного программирования состоит из трех частей:
целевой функции (на максимум или минимум) – формула (1.1),
основных ограничений– формула (1.2),
ограничений не отрицательности переменных (есть или нет) - формула (1.3)
(1.1)
i = 1,… m (1.2)
(1.3)
Чтобы решить задачу линейного программирования, необходимо привести ее к каноническому виду , когда целевая функция стремится к максимуму. Если целевая функция стремится к минимуму, то необходимо умножить ее на -1.
Основные ограничения имеют вид равенства (для приведения к равенствам в случае знака надо в правую часть каждого такого k-го неравенства добавить искусственную переменную u k , а в случае знака , искусственную переменную u k надо отнять от правой части основных ограничений).
Существуют ограничения не отрицательности переменных (если их нет для некоторой переменной х k , то их можно ввести путем замены всех вхождений этой переменной комбинацией x 1 k - х 2 k = х k , где х 1 k и х 2 k ). При этом для решения задачи линейного программирования необходимо иметь базис , т.е. набор переменных х i , в количестве, равным числу основных ограничений, причем каждая из этих переменных должна входить лишь в одно основное ограничение с множителем а 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 , полученным по дельта-оценке. Для осуществления такой замены нужно в i-ю строку k- гo столбца матрицы А поставить единицу, а остальные элементы k- го столбца заменить нулями. Подобное преобразование является одним шагом итерационного процесса.
Используем метод Гаусса для поведения преобразования. В соответствии с ним i-я строка всей матрицы А, а также i-я координата Х B делятся на a ik (получаем единицу в i-ой строке вводимого в базис элемента). Затем вся i-я строка (если i не единица), а также i-я координата Х B умножаются на элемент ( -а 1k ). После этого производится поэлементное суммирование чисел в соответствующих столбцах 1-ой и i-ой строк, суммируются также Х B 1 , и ( -а 1k ) *Х B i . Для всех остальных строк кроме i-ой (базисной) строки производятся аналогичных действия. В результате получается, что в i-ой строке k-го элемента стоит 1, а во всех остальных его строках находятся 0. Так осуществляется один шаг итерационного алгоритма. Пошаговое выполнение алгоритма симплекс-метода продолжается до тех пор, пока не будет получен один из следующих результатов:
•
Все небазисные дельта-оценки больше нуля
. Решение задачи линейного программирования представляет вектор с компонентами х, значения которых либо равны нулю, либо равны элементам столбца Х. Компоненты вектора стоят на базисных местах (например, если базис образуют переменные
х
2
, x
4
, х
5
, то ненулевые компоненты стоят в векторе решения задачи линейного программирования на 2-м, 4-м и 5-м местах).
• Имеются небазисные дельта-оценки, равные нулю . Задача линейного программирования имеет бесчисленное множество решений, представляемое лучом или отрезком.
• Возможен вариант получения столбца отрицательных элементов на отрицательной рассчитанной дельта-оценке. В такой ситуации вычислить тетта-оценки невозможно, и необходимо сделать вывод, что система ограничений задачи линейного программирования несовместна, и у задачи линейного программирования нет решения.
Единственное решение задачи линейного программирования следует записывать в виде Х* = (..., ..., ...) - вектора решения и значения целевой функции в точке решения L*(Х*). В других случаях необходимо словесно описать полученный результат. Если решение задачи линейного программирования не будет получено в течение 10–12 итераций симплекс-метода, то необходимо сделать вывод, что решение отсутствует в связи с неограниченностью функции цели.
При практическом решении задачи линейного программирования симплекс-методом удобно пользоваться таблицей вида (табл. 1.1):
Таблица 1.1
|
B |
C B |
X B |
A 1 |
… |
A n |
Q |
|
Базисные |
Целевые |
Правые |
|
|
|
|
|
компоненты |
Коэффиц. |
Части |
|
|
|
|
|
|
Базиса |
ограничен |
|
|
|
|
|
D |
|
|
D1 |
|
D n |
|
Задание
Решить задачу линейного программирования.
L(x) = x 1 – 2x 2 + 3x 3
x 1 – 3x 2 3
2x 1 – x 2 + x 3 3
-x 1 + 2x 2 – 5x 3 3
Все x i 0 i = 1, …3
1. Вначале сведем задачу к каноническому виду
L(x) = x 1 – 2x 2 + 3x 3
x 1 – 3x 2 + x 4 = 3
2x 1 – x 2 + x 3 + x 5 = 3
-x 1 + 2x 2 – 5x 3 + x 6 = 3
Все x i 0 i = 1, …6
2. Составим таблицу симплекс-метода (табл. 1.2)
В данном случае базис образуют компоненты x 4 , x 5 , x 6 .
|
B |
C B |
X B |
A 1 |
A 2 |
A 3 |
A 4 |
A 5 |
A 6 |
Q |
|
A 4 |
0 |
3 |
1 |
-3 |
0 |
1 |
0 |
0 |
- |
|
A 5 |
0 |
3 |
2 |
-1 |
1 |
0 |
1 |
0 |
3 |
|
A 6 |
0 |
3 |
-1 |
2 |
-5 |
0 |
0 |
1 |
- |
|
D |
|
|
-1 |
2 |
-3 |
0 |
0 |
0 |
|
|
A 4 |
0 |
3 |
1 |
-3 |
0 |
1 |
0 |
0 |
|
|
A 3 |
3 |
3 |
2 |
-1 |
1 |
0 |
1 |
0 |
|
|
A 6 |
0 |
3 |
-1 |
2 |
0 |
0 |
0 |
1 |
|
|
D |
|
9 |
5 |
2 |
0 |
0 |
3 |
0 |
|
После вычисления дельта-оценок можно сделать вывод.
Данная задача будет иметь единственное решение, т.к. все небазисные дельта-оценки положительны.
3. Решение задачи будет выглядеть следующим образом
X* = (0, 0, 3, 3 ,0, 3), L*(X*) = 9.