# включва алгоритъм>
# включва 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] =

Понастоящем не можете да извършите това действие.

използване

Влезли сте с друг раздел или прозорец. Презаредете, за да опресните сесията си. Излязохте от друг раздел или прозорец. Презаредете, за да опресните сесията си.