Пример 7.3.1
Решим следующую задачу ЛП вышеописанным методом решения задач с ограниченными переменными.
при ограничениях
х,+у + 2x3<14,
2 л:, + 4у + 3х3<43,
О < х, < 4, 7 < у < 10, 0 < х3 < 3.
Поскольку переменная у ограничена положительной константой не только сверху, но и снизу, производим замену у = х2 + 7, где 0 < х2 < 10 - 7 = 3.
Во избежание излишних вычислительных сложностей здесь мы применим не модифицированный симплекс-метод, а обычный симплекс-метод в виде компактных симплекс-таблиц.
Итерация 0
Базис Xi хг хз Х4 х5 Решение
z -3 -5 -2 0 0 35
xt 112 10 7
хъ 2 4 3 0 1 15
Имеем В = В"1 = I и Хв = (л:4, л:5)г = B~b = (7,15). Принимая переменную х2 в качестве вводимой в базис переменной (z2 -с2 = -5), получаем B~lP2 = (1, 4). Отсюда следует
02 = °° (поскольку В 1Р2 > 0).
Так как по условию л:2 < 3, получаем значение, принимаемое переменной х2.
х2 = min{3,75, ее, 3} = 3 = иг.
Поскольку л:2 = и2, базис остается неизменным; переменная х2 в базис не вводится (остается небазисной), но принимает значение своей верхней границы. После подстановки х2 = 3 - х\ получаем новую симплекс-таблицу.
Выполненная подстановка изменяет исходный вектор правых частей ограничений с Ь = (7, 15)г на Ь = (4, 3)г. Эти изменения должны учитываться в последующих вычислениях.
Максимизировать z = Зл:, + 5у + 2х.
8, = ггагн-, - > = 3,75 , что соответствует переменной хй,
Итерация 1. Определяем вводимую в базис переменную де,. Базисный вектор Хв и обратная матрица В"1 (= I) такие же, как на предыдущей итерации. Вычисляем
в-р.-а.г).
Отсюда следует
6, = rran j у, - > = 1,5 , что соответствует переменной де5,
92 = оо (поскольку В-1Р, > 0).
Так как по условию задачи де, < 4, получаем значение, принимаемое переменной де,.
jeI-min{l,5,oo, 4} = 1,5 (=9,).
В данной ситуации переменная де, становится базисной со значением 1,5, переменная дс5 выводится из базиса и принимает нулевое значение. Получаем следующую симплекс-таблицу.
Итерация 2. Имеем новую обратную матрицу.
В =
Значения базисных переменных определяются так:
Хв = (*4> xj = В1 V = (5/2, 3/2)т,
где Ь = (4, 3)г- значения правых частей ограничений, вычисленные в конце нулевой итерации.
Определяем хг как вводимую в базис переменную. Учитывая, что К = -Р2, получаем
Далее вычисляем
5 2 1
Вр; =(1,-2)г
= 2,5 , что соответствует базисной переменной дс4,
= 1,25 , что соответствует базисной переменной хг.
Так как по условию хг < 3, получаем значение, принимаемое переменной х\.
х2 = min{2,5,1,25, 3} = 1,25 (= 82).
Таким образом, переменная х\ вводится в базис (со значением 1,25), из которого
исключается переменная дс, с ненулевым значением, равным ее верхней границе. Применяем подстановку xt = 4 - х\ и получаем следующую симплекс-таблицу.
Базис | | | | | | Решение |
| | | | | | 109/2 |
| | | | | -1/2 | |
| | | | | | -5/2 |
Далее в базис вводится переменная | х и исключается х\ | , что приводит к следующей |
симплекс-таблиц | | | | | | |
Базис | | | | | | Решение |
| | | | | | 223/4 |
| 1/2 | | | | -1/4 | |
| | | -3/4 | | -1/4 | |
Данная таблица представляет допустимое оптимальное решение. Оптимальные значения переменных х1У хг и х3 получаем обратной подстановкой: дс, = их - х\ =4-0 = 4, хг = и2 - х2 = 3 - 5/4 = 7/4 и х3 = 0. Теперь вычисляем значение переменной у: у = 12 + х2=7 + 7/4 = 35/4. Оптимальное значение целевой функции равно z = 223/4.
УПРАЖНЕНИЯ 7.3.1
1. Дана следующая задача линейного программирования.
Максимизировать z = 2xt + х2
при ограничениях
х1 + х2<3, 0 < х, < 2, 0 < х2 < 2.
a) Решите задачу графическим способом и определите последовательность крайних точек пространства решений, ведущих к оптимальному решению.
b) Решите задачу с использованием метода решения задач с ограниченными переменными и покажите, что данный метод порождает ту же последовательность крайних точек пространства решений, приводящую к оптимальному решению, что и графический способ.
c) Как алгоритм решения задач с ограниченными переменными распознает крайние точки пространства решений?
2. Решите следующую задачу ЛП методом решения задач с ограниченными переменными.
Максимизировать z = бя, + 2х2 + 8х3 + 4xt + 2xs + 10х6 при ограничениях
8jc, + х2 + 8х3 + 2xt + 2хъ + 4х6 < 13, 0<x<l,j = l,2, ...,6.