Re: Simplex method

From

Galina O Ivanova (2:5036/32.29)

To

All

Date

2002-06-11T09:45:19Z

Area

RU.ALGORITHMS

Sergey Radkevich <sergeyr@moscow.vestedev.com> wrote:


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

> Есть задача линейного программирования
> и алгоритм решения - двухфазный симплекс метод
если правильно поняла, первая фаза -- нахождение допустимого базисного
решения (ДБР) методом искусственного базиса?

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

> Проблема в том, что исходные переменные не входят в базис, а коэффициенты
> при них в новой целевой функции равны нулю.
Прежде чем записывать "новую целевую функцию" в симплекс-таблицу (равно как и
любую другую функцию, ограничение -- на любом шаге решения), ее нужно выразить
через свободные (небазисные) переменные (в данном примере -- x1, x2, x3).

> система такая:
> 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}
w(x) = - a4 - a5 - a6 = (1*x1 + 0*x2+1*x3 - 1) + (-1*x1+1*x2+0*x3 - 0) +
(0*x1+1*x2+1*x3 - 1) = 0*x1 + 2*x2 + 2*x3 - 2

если в результате максимизации w(x) получилось ненулевое значение, исходная
система не имеет допустимых (x >= 0) решений.
Функцию f(x) при этом просто таскаешь за собой, постоянно пересчитывая или
находишь ее коэффициенты в конце, когда ДБР уже найдено.

Надеюсь, поможет ...

С уважением, 
Галина О. Иванова
-- 
Если бы я умел читать, я бы работал преподавателем в универе ...
--- tin/1.4.1-19991201 ("Polish") (UNIX) (Linux/2.2.14-15mdk (i586))
 * Origin: -= HomeNet =- (2:5036/32.29@fidonet)