|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Radkevich 2:5020/400 10 Jun 2002 16:04:38
To : All
Subject : Simplex method
--------------------------------------------------------------------------------
Доброго времени суток.
Есть задача линейного программирования
и алгоритм решения - двухфазный симплекс метод
Hе понятно, как провести первую фазу.
По описанию алгоритма, нужно добавить
в каждое уравнение по одной
дополнительной (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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
