|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Galina O Ivanova 2:5036/32.29 11 Jun 2002 09:45:19
To : All
Subject : Re: Simplex method
--------------------------------------------------------------------------------
Доброго времени суток.
> Есть задача линейного программирования
> и алгоритм решения - двухфазный симплекс метод
если правильно поняла, первая фаза -- нахождение допустимого базисного
решения (ДБР) методом искусственного базиса?
> По описанию алгоритма, нужно добавить в каждое уравнение по одной
> дополнительной (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) при этом просто таскаешь за собой, постоянно пересчитывая или
находишь ее коэффициенты в конце, когда ДБР уже найдено.
Hадеюсь, поможет ...
С уважением,
Галина О. Иванова
--
Если бы я умел читать, я бы работал преподавателем в универе ...
--- tin/1.4.1-19991201 ("Polish") (UNIX) (Linux/2.2.14-15mdk (i586))
* Origin: -= HomeNet =- (2:5036/32.29@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
