| # включва алгоритъм> |
| # включва iostream> |
| # включва вектор> |
| # включва cstdio> |
| # включва cassert> |
| използване на пространство от имена std; |
| typedef double ElementType; |
| typedef вектор> матрица; |
| const int NO_SOLUTION = - 1; |
| const int BOUNDED_SOLUTION = 0; |
| const int INFINITY_SOLUTION = 1; |
| const ElementType C_THRESHOLD = 0.0000001; |
| const ElementType DELTA_RATIO_THRESHOLD = 0; // 0,0001; |
| const ElementType DELTA_COMPARE_EPSILON = 0.0000001; |
| // внедрява PIVOT от CLRS |
| void pivot ( |
| вектор int> & неосновни, |
| вектор int> & основи, |
| матрица & A, |
| вектор & b, |
| вектор и c, |
| ElementType & v, |
| int l, |
| int e) |
| // в CLRS това е N - |
| вектор int> otherNonbasics; |
| за (int n: неосновни) |
| ако (n! = e) |
| другиНеосновни. push_back (n); |
| > |
| > |
| // променливите e & l предоставят индексите на променливите, които влизат и излизат, но |
| // те не са същите като реда в A, който ще бъде обработен. row_l осигурява това картографиране |
| // (известен още като реда в A, който в момента представлява основната променлива x [l]) |
| int row_l = - 1; |
| за (size_t i = 0; i size (); ++ i) |
| ако (основи [i] == l) |
| ред_l = i; |
| почивка; |
| > |
| > |
| // изчисляваме коефициентите на уравнението за нова основна променлива x [e]. |
| // с други думи, ние решаваме за x [e], като използваме ограничението, индексирано от l. |
| // за да направим това, ние мащабираме ограничението чрез разделяне на A [l] [e], което задава коефициента |
| // в A в ограничение l за x [e] до 1.0 и ефективно го решава |
| b [row_l] = b [row_l]/A [row_l] [e]; |
| за (int j: otherNonbasics) |
| A [row_l] [j] = A [row_l] [j]/A [row_l] [e]; |
| > |
| A [row_l] [l] = 1.0/A [row_l] [e]; |
| A [row_l] [e] = 0.0; |
| // изчисляваме коефициентите на останалите ограничения. |
| // На практика това актуализира ограниченията, които не са индексирани от l |
| // чрез заместване на RHS на уравнението за x [e] във всяко ограничение |
| // за всяко появяване на x [e] |
| за (size_t i = 0; i size (); ++ i) |
| ако (i == ред_l) |
| продължи; |
| > |
| b [i] - = A [i] [e] * b [row_l]; |
| за (int j: otherNonbasics) |
| A [i] [j] - = A [i] [e] * A [row_l] [j]; |
| > |
| A [i] [l] = -A [i] [e] * A [row_l] [l]; |
| A [i] [e] = 0,0; |
| > |
| // изчисляване на целевата функция |
| // чрез заместване в ограничение l (решено за x [e]) |
| v + = c [e] * b [ред_l]; |
| за (int j: otherNonbasics) |
| c [j] - = c [e] * A [ред_l] [j]; |
| > |
| c [l] = -c [e] * A [ред_l] [l]; |
| c [e] = 0,0; |
| // изчисляваме нови набори от основни и неосновни променливи чрез размяна на e & l |
| за (size_t n = 0; n size (); ++ n) |
| ако (неосновни [n] == e) |
| неосновни [n] = l; |
| почивка; |
| > |
| > |
| за (size_t n = 0; n size (); ++ n) |
| ако (основи [n] == l) |
| основи [n] = e; |
| почивка; |
| > |
| > |
| връщане; |
| > |
| typedef struct SlackForm |
| вектор int> неосновни, основни; |
| матрица А; |
| вектор b, c; |
| ElementType v; |
| > SlackForm; |
| име на тип на шаблон T> |
| std: ostream & оператор const vector & v) |
| навън " < "; |
| за (size_t i = 0; i size (); ++ i) |
| out if (i! = v. size () - 1) |
| навън ","; |
| > |
| > |
| навън ">"; |
| връщане навън; |
| > |
| std: ostream & оператор "N =" неосновни "B =" основни "A = < "; |
| за (вектор и ред: s. A) |
| out ">" "b =" b "c =" c "v =" v връщане навън; |
| > |
| чифт int, vector> SimplexIterations (SlackForm & slack) |
| вектор int> |
| & nonbasics = отпуснатост. неосновни, |
| & basics = хлабав. Основи; |
| матрица & A = хлабина. A; |
| вектор |
| & b = отпуснатост. б, |
| & c = отпуснатост. ° С; |
| Тип на елемента & v = отпуснат. v; |
| // това изпълнява редове 2 - 17 на SIMPLEX от CLRS |
| векторна делта (основи. размер (), std: numeric_limits: infinity ()); |
| за (вектор: итератор j = std: max_element (c. begin (), c. end ()); |
| * j> C_THRESHOLD; |
| j = std: max_element (c. begin (), c. end ())) |
| int e = std: distance (c. begin (), j); |
| // изберете l, индексът на променливите, които ще бъдат напускащата променлива. |
| // направете това, като видите кое от ограниченията позволява най-голямата стойност на |
| // x [e], като същевременно не нарушава ограниченията за отрицателност на x |
| за (size_t i = 0; i size (); ++ i) |
| делта [i] = (A [i] [e]> DELTA_RATIO_THRESHOLD)? b [i]/A [i] [e]: std: numeric_limits: infinity (); |
| > |
| // сега намерете "най-малката" делта, но има фактор за измама за "връзки". Ако делта [i] = |
Понастоящем не можете да извършите това действие.
Влезли сте с друг раздел или прозорец. Презаредете, за да опресните сесията си. Излязохте от друг раздел или прозорец. Презаредете, за да опресните сесията си.