|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Kukushkin 2:5025/37.216 19 May 2003 21:40:17
To : Vladimir Andreyev
Subject : Симплекс-метод
--------------------------------------------------------------------------------
Воскресенье Май 18 2003 в 23:42 Vladimir Andreyev писал Roman Kukushkin:
VA> Hу хоpошо! Обсудим одну задачку, котоpую pешим не гpафическим методом
VA> (ведь мы обсуждаем давно откpытые алгоpитмы, не так ли?), а, как и
VA> положено, симплекс-методом. Впpочем, гpафический метод на понадобится
VA> для сpавнения pезультатов.
VA> Целевая функция
VA> -3*X1 - 4*X2 = Z
Hадеюсь, минимум?
VA> Огpаничения
VA> X1 , X2 >= 0
VA> X1 >=10
VA> X2 <= 5
VA> X1 + X2 <=20
VA> -X1 + 4*X2 <=20
VA> Как бы мы стандаpтно постpоили симплекс-таблицу, а по итеpациям пpишли
VA> к оптимальному базису? Если можно, pазвёpнутое pешение?
Реализации есть конечно разные. Можно так:
Приводим ограничения к виду
x1-u1=10
x2+u2=5
x1+x2+u3=20
-x1+4x2+u4=20
Добавляем одну m переменную,
получаем задачу для M-метода
0 0 0 0 0 0 1 t->min
1 0 -1 0 0 0 1 10
0 1 0 1 0 0 0 t= 5
1 1 0 0 1 0 0 20
-1 4 0 0 0 1 0 20
вычисляем остатки
1 0 -1 0 0 0 0
выбираем любой положительный (если нет, целевая функция неограничена на
допустимом множестве).
вычисляем b_i/A_i, выбираем минимальное положительное,
вводим в базис
получаем
1 0 -1 0 0 0 1 10
0 1 0 1 0 0 0 5
0 1 1 0 1 0 -1 10
0 4 -1 0 0 1 1 30
удаляем столбец, меняем целевую функцию
с -3 -4 0 0 0 0
A 1 0 -1 0 0 0 10
0 1 0 1 0 0 5
0 1 1 0 1 0 10
0 4 -1 0 0 1 30
Вычисляем остатки
0 0 3 0 0 0
(если задача на max, прекращаем вычисления, получаем x_1=10, x_2=0)
вводим в базис t_3, выводим t_5,полуем
с -3 -4 0 0 0 0
A 1 1 0 0 1 0 20
0 1 0 1 0 0 5
0 1 1 0 1 0 10
0 5 0 0 1 1 40
Остатки
0 -3 0 0 -3 0
Конец.
Hо вообще руками это редко делают. Я читал доказательства теорем об этом методе
и графическую интерпретацию. Меня убедили. А что, какие-то места у тебя вызвали
сомнения, или не читал?
Легко показать, что графической интерпретацией M-метода является движение по
ребрам в сторону допустимого множества, а графической интерпретацией симплекс
метода будет движение по любому из ребер границы допустимой области в
направлении убывания целевой функции. Поэтому графический метод должен дать то
же самое.
А в чем вопрос?
C уважением, Roman Kukushkin.
---
* Origin: (2:5025/37.216)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
