Re: Simplex method

From

Oleg Shatalov ()

To

Sergey Radkevich

Date

2002-06-10T18:46:22Z

Area

RU.ALGORITHMS

From: Oleg Shatalov <oleg@lakes-environmental.com>


Привет, Сергей!

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

Обычный или 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)