Simplex method

From

Sergey Radkevich ()

To

All

Date

2002-06-10T16:04:38Z

Area

RU.ALGORITHMS

From: "Sergey Radkevich" <sergeyr@moscow.vestedev.com>


Доброго времени суток.

Есть задача линейного программирования
и алгоритм решения - двухфазный симплекс метод

Не понятно, как провести первую фазу.

По описанию алгоритма, нужно добавить
в каждое уравнение по одной
дополнительной (artificial) переменной,
эти переменных образуют начальный базис.
Затем нужно минимизировать сумму этих переменных,
чтобы найти базис исходной системы.

Проблема в том, что исходные
переменные не входят в базис, а коэффициенты
при них в новой целевой функции равны нулю.
Т.е. симплекс метод не будет даже начинать работать,
(так как от их введения значение целевой функции не изменится).
Если же позволить ему вводить в базис эти переменные
все равно, то алгоритм зацикливается не смотря на то,
что в нем реализована защита против зацикливания...

система такая:
min x1+x2+x3
x1 + x3 = 1
- x1 + x2 = 0
- x2 - x3 = -1
Ответ к ней
x1 = 0, x2 = 0, x3 = 1

Решение:
1*x1 + 0*x2+1*x3+1*a4+0*a5+0*a6=1
-1*x1+1*x2+0*x3+0*a4+1*a5+0*a6=0
0*x1+1*x2+1*x3+0*a4+0*a5+1*a6=1
базис {a4,a5,a6}
Введем x1 в базис, в первое уравнение
1*x1 + 0*x2+1*x3+1*a4+0*a5+0*a6=1
0*x1+1*x2+1*x3+1*a4+1*a5+0*a6=1
0*x1+1*x2+1*x3+0*a4+0*a5+1*a6=1
базис {x1,a5,a6}
Введем x2 в базис, во второе уравнение
(во второе потому, что правило против зацикливания
гласит, что в случае неоднозначности в выборе
уравнения нужно выбирать такое уравнение,
где из базиса выйдет переменная с меньшим индексом)
1*x1 + 0*x2+1*x3+1*a4+0*a5+0*a6=1
0*x1+1*x2+1*x3+1*a4+1*a5+0*a6=1
0*x1+0*x3+0*x3-1*a4-1*a5+1*a6=0
базис {x1,x2,a6}
Дальше x3 войдет в базис вытесняя x1 и так далее,
однако a6 никогда не выйдет из базиса.
Здесь алгоритм зацикливается.

мне нужно реализацию метода отладить,
чтобы быть уверенным в его работоспособности
на любых данных.



--- ifmail v.2.15dev5
 * Origin: Golden Telecom (2:5020/400)