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