Додаток

Лістинг програми

// // Цей файл визначає клас симплекс методу

##include <vcl.h>

##include <list>

##include "CD.cpp"

##ifndef CSM2_H

##define CSM2_H

namespace SM

{

//----------------//----------------Симплекс-метод------------------------------

class CSM

{

public:

CSM( int n, int m );

void SetBaz( int * baz );

int SetT( CD ** T );

void Show();

AnsiString GetWord();

AnsiString GetTacker();

AnsiString Get_Rap();

int operator<<=( CSM * csm );

CD get_CF();

CD** get_ogr(){ return T; }

int* get_baz(){ return baz; }

int get_rez(){ return rez; }

void get_nm( int* nIn, int* mIn ){ *nIn = n; *mIn = m; }

void get_ij( int* i, int* j ){ *i = a_i; *j = a_j; }

~CSM( );

private:

static int iter; // Число ітерацій

int optim(); // перевірка рішення (0 - оптимальне, 1 - не існує, 2 - не оптимальне)

int n; // Число змінних

int m; // Число обмежень

int a_i;

int a_j; // Координати дозволяючого елементу

int * baz; // Масив базисних змінних

CD ** T; // Симплекс таблиця

int rez;

};

int CSM::iter = 0; // Число ітерацій

CSM::CSM( int nIn, int mIn )

{

n = nIn;

m = mIn;

baz = new int [m];

T = new CD * [m + 1]; // m + 1 оскільки ще рядок цільової функції

for( int i = 0; i < m + 1; i++ )

T[i] = new CD [n + 1]; // n + 1 оскільки ще вільний член

iter += 1;

rez = 2;

}

CSM::~CSM( )

{

delete baz;

for( int i = 0; i < m + 1; i++ )

delete T[i];

delete T;

iter -= 1;

}

void CSM::SetBaz( int * bazIn )

{

for( int i = 0; i < m; i++ )

baz[i] = bazIn[i];

}

int CSM::SetT( CD ** TIn ) // Копіювання таблиці, що входить, і перевірка рішення з пошуком дозволяючого елементу

{

for( int i = 0; i < m + 1; i++ )

for( int j = 0; j < n + 1; j++ )

T[i][j] = TIn[i][j];

return optim();

}

int CSM::optim()

{

a_i = a_j = 0; // Ініціалізація координат дозволяючого елементу

// // Перевірка на отрицательность серед вільних членів

for( int i = 1; i < m; i++ ) // перевірка вільного члена

if( T[i][0].get_d() < T[a_i][0].get_d() ) // Шукаємо мінімальний

a_i = i;

if( T[a_i][0].get_d() < 0 ) // Якщо мінімальний елемент негативний (подвійний СМ)

{

for( int j = 1; j < n + 1; j++ ) // перевірка на наявність негативних эл-тов в рядку

if( T[a_i][j].get_d() < 0 ) // є негативні елементи

{

a_j = j; // Перший негативний елемент

break; // Вихід з циклу пошуку

}

if( a_j == 0 ) return rez = 1; // Немає оптимального рішення // вихід

for( int j = a_j + 1; j < n + 1; j++ ) // Прохідний по рядку ще раз для знаходження мінімального відношення

if( T[a_i][j].get_d() < 0 ) // Негативний

if( fabs( (T[m][j]/T[a_i][j]).get_d() )< fabs( (T[m][a_j]/T[a_i][a_j]).get_d() )) // Найменше відношення

a_j = j;

return rez = 2; // продовження виконань ітерацій // вихід

}

// // Перевірка на отрицательность серед елементів цільової функції

a_j = 1;

a_i = m;

for( int j = 2; j < n + 1; j++ ) // Прохідний по рядку цільової функції

if( T[m][j].get_d() < T[m][a_j].get_d() ) // Шукаємо мінімальний

a_j = j;

if( T[m][a_j].get_d() < 0 ) // Є негативний елемент в цільовій функції

{

for( int i = 0; i < m; i++ ) // Прохідний по стовпцю

if( T[i][a_j].get_d() > 0 )

{

a_i = i; // Перший позитивний елемент

break; // Вихід з циклу пошуку

}

if( a_i == m ) return rez = 1; // Немає оптимального рішення // вихід

for( int i = a_i + 1; i < m; i++ ) // Прохідний по стовпцю ще раз для знаходження мінімального відношення

if( T[i][a_j].get_d() > 0 ) // Позитивний

if( fabs( (T[i][0]/T[i][a_j]).get_d() )< fabs( (T[a_i][0]/T[a_i][a_j]).get_d() )) // Найменше відношення

a_i = i;

return rez = 2; // продовження виконань ітерацій // вихід

}

return rez = 0; // оптимальне рішення // вихід

}

int CSM::operator<<=( CSM * csmIn ) // Тут з попередньої таблиці виходить нова

{

a_i = csmIn ->a_i;

a_j = csmIn ->a_j;

// // Ділимо на дозволяючий елемент дозволяючий рядок і міняємо базисну змінну

for( int j = 0; j < n + 1; j++ )

T[a_i][j] = csmIn ->T[a_i][j] / csmIn ->T[a_i][a_j];

// // Домножаем дозволяючий рядок на эл-т в дозволяючому стовпці, соотв-щий цьому рядку, і складаємо з цим рядком

for( int i = 0; i < m + 1; i++)

{

if( i == a_i) continue;

for( int j = 0; j < n + 1; j++ )

T[i][j] = csmIn ->T[i][j] - T[a_i][j] * csmIn ->T[i][a_j];

}

// // Вводимо нову змінну в базис

for( int i = 0; i < m; i++ )

baz[i] = csmIn ->baz[i];

baz[a_i] = a_j;

return optim();

}

CD CSM::get_CF()

{

return T[m][0];

}

void CSM::Show( )

{

AnsiString tab;

tab = "БП\tСЧ";

for( int j = 0; j < n; j++)// шапка

tab = tab + "\tX" + AnsiString( j + 1 );

for( int i = 0; i < m + 1; i++ )

{

if( i == m ) tab = tab + "\nY";

else tab = tab + "\n" + baz[i];

for( int j = 0; j < n + 1; j++)

tab = tab + "\t" + T[i][j].get_a();

}

// // ShowMessage(tab);

}

AnsiString CSM::GetWord()

{

// // Таблиця

AnsiString tab;

tab = "\n<table border=3 cellpadding=5 ><tr bgcolor=\"#aaaaaa\">";

tab += "<td align=\"center\">БП</td><td>СЧ</td>";

for( int j = 0; j < n; j++)// шапка

{

tab += "<td align=\"center\">";

tab = tab + "X_{" + (j+1) + "}";

tab += "</td>";

}

tab += "</tr>";

for( int i = 0; i < m + 1; i++ )

{

tab += "<tr>";

tab += "<td bgcolor=\"#aaaaaa\" align=\"center\">";

if( i == m ) tab += "F'";

else tab = tab + "X_{" + baz[i] + "}";

tab += "</td>";

for( int j = 0; j < n + 1; j++)

{

if( i == a_i && j == a_j && rez == 2 ) tab += "<td bgcolor=\"#cccccc\">";

else tab += "<td align=\"center\">";

tab += T[i][j].get_a();

tab += "</td>";

}

tab += "</tr>";

}

tab += "</table>";

return tab;

/*

AnsiString tab;

tab = "БП;СЧ;";

for( int j = 0; j < n; j++)// шапка

if( j == n - 1 ) tab = tab + "X" + AnsiString( j + 1 );

else tab = tab + "X" + AnsiString( j + 1 ) + ";";

for( int i = 0; i < m + 1; i++ )

{

if( i == m ) tab = tab + "\nF';";

else tab = tab + "\nX" + baz[i] + ";";

for( int j = 0; j < n + 1; j++)

if( j == n ) tab = tab + T[i][j].get_a();

else tab = tab + T[i][j].get_a() + ";";

}

return tab;

*/

}

AnsiString CSM::GetTacker()

{

AnsiString tab;

for( int i = 0; i < m; i++ )

{

tab += AnsiString("X") + baz[i] + " = ";

tab += T[i][0].get_a() + " - ( " + T[i][1].get_a() + "*X1";

for( int j = 2; j < n + 1; j++)

{

bool is_b = false;

for( int d = 0; d < m; d++ )

if( j == baz[d] )

{

is_b = true;

break;

}

if( !is_b )

tab += T[i][j].get_s() + "*X" + AnsiString( j );

}

tab += " )\n";

}

tab += "\nЦелевая функція :";

tab += "\nF' = " + T[m][0].get_a() + " - ( " + T[m][1].get_a() + "*X1";

for( int j = 2; j < n + 1; j++)

{

bool is_b = false;

for( int d = 0; d < m; d++ )

if( j == baz[d] )

{

is_b = true;

break;

}

if( !is_b )

tab += T[m][j].get_s() + "*X" + AnsiString( j );

}

tab += " )\n";

return tab;

}

AnsiString CSM::Get_Rap()

{

AnsiString Rap;

if( rez == 0 )

{

if( T[m][0] == 0 )

Rap = "Рішення оптимальне. Штучний базис отриманий. Далі підставляємо нові бвазисные пременные в цільову функцію".;

else Rap = "Рішення оптимальне, але цільова функція не дорівнює 0. штучного базису немає".;

}

else if( rez == 1 )

{

if( a_j == 0 ) Rap = AnsiString( "Рішення не існує. Цільова функція необмежена, оскільки вільний член при X" ) + baz[a_i] + " негативний, а інші елементи рядки не негативні".;

else if( a_i == m ) Rap = AnsiString( "Рішення не існує. Цільова функція необмежена, оскільки елемент в рядку цільової функції при X" ) + a_j + " негативний, а інші елементи стовпця не позитивні".;

}

else if( rez == 2 )

{

Rap = AnsiString( "Рішення триває. З базису виводиться X") + baz[a_i] + " і вводиться X" + a_j + "".;

}

return Rap;

}

}

##endif // CSM_H

// // Цей файл визначає клас дробу

##include <vcl.h>

##include <math.h>

##ifndef CD_H

##define CD_H

##define PR_COUNT 5000

int mas[PR_COUNT] = {0};

void Generate_Prost();

class CD // Клас дріб

{

public:

CD::CD( int = 0, int = 1 );

bool Set( int hi, int lo );

bool Set( double d );

bool Set( AnsiString d );

bool SetInv( AnsiString d );

int hi(){ return m_hi; }; // чисельник

int lo(){ return m_lo; }; // знаменник

double get_d(); // повертає десяткове значення

AnsiString get_a(); // повертає рядок звичайного дробу

AnsiString get_s(); // повертає рядок звичайного дробу

CD get_dr();

int get_cel();

CD get_abs();

CD operator*(CD d);

CD operator*(int num);

CD operator/(CD d);

CD operator/(int num);

CD operator+(CD d);

CD operator+(int num);

CD operator -(CD d);

CD operator -(int num);

CD operator=(CD d);

CD operator=(int num);

bool operator==(CD d);

bool operator==(int num);

bool operator!=(CD d);

bool operator!=(int num);

private:

int m_hi; // чисельник

int m_lo; // знаменник

double m_d;

bool overflow;

void optim();

static bool gen;

};

bool CD::gen = false;

CD::CD( int hi, int lo )

{

if( !gen )

{

Generate_Prost();

gen = true;

}

overflow = false;

Set( hi, lo );

}

bool CD::Set( int hi, int lo )

{

overflow = false;

if( lo == 0 )

{

m_hi = 0;

m_lo = 1;

return false;

}

m_hi = hi;

if( m_hi == 0 ) m_lo = 1;

else

{

m_lo = lo;

optim();

}

return true;

}

bool CD::Set( double d )

{

overflow = true;

m_d = d;

return true;

}

bool CD::Set( AnsiString d )

{

int pos = 0;

if( pos = d.LastDelimiter("/"))

{

m_hi = StrToIntDef( d.SubString( 1, pos - 1 ), 0 );

m_lo = StrToIntDef( d.SubString( pos + 1, d.Length() ), 1 );

Set( m_hi, m_lo );

}

else if( pos = d.LastDelimiter(".))

{

Set( StrToFloat( d ));

}

else

{

m_hi = StrToIntDef( d, 0 );

Set( m_hi, 1 );

}

optim();

// // ShowMessage( "m_hi = " + AnsiString(m_hi) + "\nm_lo = " + m_lo );

return true;

}

bool CD::SetInv( AnsiString d )

{

int pos = 0;

if( pos = d.LastDelimiter("/"))

{

m_hi = - StrToIntDef( d.SubString( 1, pos - 1 ), 0 );

m_lo = StrToIntDef( d.SubString( pos + 1, d.Length() ), 1 );

Set( m_hi, m_lo );

}

else if( pos = d.LastDelimiter(".))

{

Set( - StrToFloat( d ));

}

else

{

m_hi = - StrToIntDef( d, 0 );

Set( m_hi, 1 );

}

// // ShowMessage( "m_hi = " + AnsiString(m_hi) + "\nm_lo = " + m_lo );

return true;

}

double CD::get_d() // повертає десяткове значення

{

if( overflow ) return m_d;

if ( m_hi ) return float(m_hi)/m_lo;

else return 0;

}

AnsiString CD::get_a()

{

if( overflow ) return FloatToStrF( m_d, ffGeneral, 7, 0 );

if ( m_lo == 1 ) return AnsiString(m_hi);

else return AnsiString(m_hi) + "/" + AnsiString(m_lo);

}

AnsiString CD::get_s()

{

if( overflow )

{

if( m_d >= 0 ) return AnsiString( " + " ) + FloatToStrF( m_d, ffGeneral, 7, 0 );

else return AnsiString( " - " ) + FloatToStrF( - m_d, ffGeneral, 7, 0 );

}

if ( m_lo == 1 ) return (m_hi < 0)?AnsiString(" - ") + abs(m_hi) :" + " + AnsiString(m_hi);

else return ((m_hi < 0)?AnsiString(" - ") + abs(m_hi) :" + " + AnsiString(m_hi)) + "/" + AnsiString(m_lo);

}

CD CD::get_dr()

{

CD cd;

if( overflow )

{

cd.Set( m_d - floor(m_d));

return cd;

}

ldiv_t r;

r = ldiv( m_hi, m_lo );

if( r.rem >= 0 )

{

cd.Set( r.rem, m_lo );

}

else

{

cd.Set( m_lo + r.rem, m_lo );

}

return cd;

}

int CD::get_cel()

{

int cd;

if( overflow )

{

cd = floor( m_d );

return cd;

}

if( m_hi >= 0 )

cd = ldiv( m_hi, m_lo ).quot;

else

cd = ldiv( m_hi, m_lo ).quot - 1;

return cd;

}

CD CD::get_abs()

{

CD cd;

if( overflow )

{

if( m_d >= 0 ) cd.Set( m_d );

else cd.Set( - m_d );

return cd;

}

if( m_hi < 0 ) cd.Set( - m_hi, m_lo );

else cd.Set( m_hi, m_lo );

return cd;

}

CD CD::operator+(CD d)

{

CD cd;

if( overflow || d.overflow )

{

cd.Set( get_d() + d.get_d() );

return cd;

}

cd.Set( m_hi*d.m_lo + d.m_hi*m_lo, m_lo*d.m_lo );

return cd;

}

CD CD::operator+(int num)

{

CD cd;

if( overflow )

{

cd.Set( get_d() + num );

return cd;

}

cd.Set( m_hi + num*m_lo, m_lo );

return cd;

}

CD CD::operator -(CD d)

{

CD cd;

if( overflow || d.overflow )

{

cd.Set( get_d() - d.get_d() );

return cd;

}

cd.Set(m_hi*d.m_lo - d.m_hi*m_lo, m_lo*d.m_lo );

return cd;

}

CD CD::operator -(int num)

{

CD cd;

if( overflow )

{

cd.Set( get_d() - num );

return cd;

}

cd.Set( m_hi - num*m_lo, m_lo );

return cd;

}

CD CD::operator*(CD d)

{

CD cd;

if( overflow || d.overflow )

{

cd.Set( get_d() * d.get_d() );

return cd;

}

cd.Set( m_hi*d.m_hi, m_lo*d.m_lo );

return cd;

}

CD CD::operator*(int num)

{

CD cd;

if( overflow )

{

cd.Set( get_d() * num );

return cd;

}

cd.Set( m_hi*num, m_lo );

return cd;

}

CD CD::operator/(CD d)

{

CD cd;

if( overflow || d.overflow )

{

cd.Set( get_d() / d.get_d() );

return cd;

}

cd.Set( m_hi*d.m_lo, m_lo*d.m_hi );

return cd;

}

CD CD::operator/(int num)

{

CD cd;

if( overflow )

{

cd.Set( get_d() / num );

return cd;

}

cd.Set( m_hi, m_lo*num );

return cd;

}

CD CD::operator=(CD d)

{

if( d.overflow)

{

Set( d.get_d() );

return *this;

}

Set( d.m_hi, d.m_lo );

return *this;

}

CD CD::operator=(int num)

{

Set( num, 1 );

return *this;

}

bool CD::operator==(CD d)

{

if( overflow || d.overflow )

{

return get_d() == d.get_d();

}

if( m_hi == d.m_hi )

if( m_lo == d.m_lo )

return true;

return false;

}

bool CD::operator==(int num)

{

if( overflow )

{

return get_d() == num;

}

if( m_hi == num )

if( m_lo == 1 )

return true;

return false;

}

bool CD::operator!=(CD d)

{

if( overflow || d.overflow )

{

return get_d() != d.get_d();

}

if( m_hi == d.m_hi )

if( m_lo == d.m_lo )

return false;

return true;

}

bool CD::operator!=(int num)

{

if( overflow )

{

return get_d() != num;

}

if( m_hi == num )

if( m_lo == 1 )

return false;

return true;

}

void CD::optim()

{

if( overflow ) return;

m_hi *= m_lo/abs(m_lo); // для знаку

m_lo = abs(m_lo);

if( m_hi ) // далі скорочення дробу

{

int i = 0;

while(1)

{

while( ldiv( m_hi, mas[i] ).rem == 0 && ldiv( m_lo, mas[i] ).rem == 0 )

{

m_hi /= mas[i];

m_lo /= mas[i];

}

if( (mas[i + 1] > abs(m_hi) && mas[i + 1] > m_lo) || i + 1 > PR_COUNT - 1 ) break;

i++;

}

if( abs(m_hi)> mas[PR_COUNT - 1] || m_lo > mas[PR_COUNT - 1] )

{

overflow = true;

m_d = double(m_hi)/m_lo;

return;

}

}

}

void Generate_Prost()

{

bool is_prost;

float per;

int kol = 1;

mas[0] = 2;

int i = 3;

while(1)

{

is_prost = true;

for( int j = 0; j < kol; j++ )

if( ldiv( i, mas[j] ).rem == 0 )

{

is_prost = false;

break;

}

if( is_prost )

{

mas[kol] = i;

kol++;

}

if( kol >= PR_COUNT ) return;

i++;

}

/*

AnsiString p;

for( int i = 0; i < kol; i++ )

p = p + mas[i] + " ";

// // ShowMessage( p );

//*/

}

##endif // CD_H

Размещено на Allbest.ru