1. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. Т.2: Пер с англ. - М.: Мир, 1991. - 342с., ил. Раздел Целочисленное линейное программирование
2. Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2002. - 208 с.: ил. - (Серия "Краткий курс"). Раздел 4.2 Метод Гомори
3. Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8
4. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
5. Ершов А.Т., Карандаев И.С., Шананин Н.А. Планирование производства и линейное программирование. МИУ, М., 1981.
6. Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «Высшая школа» 1993г.
7. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое программирование», Москва «Высшая школа» 1980г.
8. Вентцель Е.С. Исследование операций: задачи, принципы, методологии. М.: Изд-во «Наука», 1980.
9. Джерод Холлингворс, Дэн Баттерфилд, Боб Свот C++ Builder 5. Руководство разработчика = C++ Builder 5 Developer's Guide. — М.: «Диалектика», 2001. — С. 884. — ISBN 0-672-31972-1
10. Джаррод Холингворт, Боб Сворт, Марк Кэшмэн, Поль Густавсон Borland C++ Builder 6. Руководство разработчика = Borland C++ Builder 6 Developer's Guide. — М.: «Вильямс», 2004. — С. 976. — ISBN 0-672-32480-6
11. Леоненков А.В. Решение задач оптимизации в среде MS Excel BHV-Санкт-Петербург ISBN: 5941575033 2005 г.
Приложение 1
Листинг программы
// Этот файл определяет класс симплекс метода
#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<sub>" + (j+1) + "</sub>";
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<sub>" + baz[i] + "</sub>";
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 )