|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Shatalov 2:5020/400 10 Jun 2002 18:46:22
To : Sergey Radkevich
Subject : Re: Simplex method
--------------------------------------------------------------------------------
Привет, Сергей!
> Есть задача линейного программирования и алгоритм решения - двухфазный
> симплекс метод
Обычный или Revised?
Вообще-то для программирования лучше брать Revised Simplex Method. Он
дает меньшую вычислительную нагрузку и оперирует с матрицами и
векторами, что опять - таки легко реализовать.
> По описанию алгоритма, нужно добавить в каждое уравнение по одной
> дополнительной (artificial) переменной, эти переменных образуют
> начальный базис.
> Затем нужно минимизировать сумму этих переменных, чтобы найти базис
> исходной системы.
Все правильно.
> Введем x2 в базис, во второе уравнение (во второе потому, что правило
> против зацикливания
> гласит, что в случае неоднозначности в выборе уравнения нужно выбирать
> такое уравнение,
> где из базиса выйдет переменная с меньшим индексом)
Странное правило. Обычное правило против зацикливания - выбор самого
первого подходящего элемента.
> Дальше x3 войдет в базис вытесняя x1 и так далее, однако a6 никогда не
> выйдет из базиса.
> Здесь алгоритм зацикливается.
Еще одно правило, которое поможет тебе - как только искусственная
пременная вышла из базиса, она должна быть удалена. Тогда она никогда не
сможет попасть в базис снова. И это тоже предотвращает зацикливание.
> мне нужно реализацию метода отладить, чтобы быть уверенным в его
> работоспособности
> на любых данных.
Еще раз рекомендую использовать Revised Simplex Method.
Его программировать - одно удовольствие :))
Пока,
Олег.
--- ifmail v.2.15dev5
* Origin: Golden Triangle On Line Inc. (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
