Използване на метода на линейно програмиранемплекс за решаване на диетичния проблем с даден набор от храни с

# включва алгоритъм>

# включва 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] =

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

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