5.Описание программы
Данная программа предназначена для решения задачи оптимизации межотраслевых потоков. В ней реализован алгоритм симплекс метода.
Рис. 1
Инструкция пользователя:
На закладке «Исходные данные» (рис.1):
Ввод данных вручную.
Для ввода данных вручную необходимо задать число отраслей и заполнить поля таблиц.
Случайный ввод.
Для случайного ввода необходимо нажать кнопочку «Случайная задача»
Загрузка данных из файла.
Для загрузки данных из файла необходимо нажать «F3» или в меню «Файл» выбрать пункт «Загрузить из файла».
Имеется возможность сохранять задачи в файл с расширением omop, для этого необходимо нажать «F2», или в меню «Файл» выбрать пункт «Сохранить в файл».
В таблице «Коэффициенты прямых затрат продукции одного вида на производство продукции другого вида» каждая строка представляет собой отдельную отрасль и содержит в себе данные о количестве необходимых для производства продуктах.
Рис. 2
На закладке «Решение» (рис. 2):
1. Отображается суммарная стоимость произведенного конечного продукта.
2. Также в таблицах отображаются объем производства и объем продукта для внепроизводственного потребления.
Список использованных источников
Дегтярев Ю.И. Исследование операций. - М.: Высшая школа, 1986. – 224с.
Зайченко Ю.П. Исследование операций. - Киев: Высшая школа, 1979.
Методика по математическому программированию в электронном виде.
Приложение а.
Листинг программы
Метод искусственного базиса
bool TForm1::MIsBas()
{
int n2=2*n,n3_1=3*n+1;
SimpTabIB.Length=2*n+1;
for(int i=0;i<SimpTabIB.Length;i++)
{
SimpTabIB[i].Length=n3_1;
for(int j=0;j<SimpTabIB[0].Length;j++)
SimpTabIB[i][j]=0;
}
PerBas.Length=3*n;
PerNBasIB.Length=n2;
for(int i=0;i<n;i++)
{
PerBas[i]="Y_"+IntToStr(i+1);
PerBas[i+n]="Z1_"+IntToStr(i+1);
PerBas[i+n2]="T_"+IntToStr(i+1);
PerNBasIB[i]="X_"+IntToStr(i+1);
PerNBasIB[i+n]="Z2_"+IntToStr(i+1);
}
for(int i=1;i<=n;i++)
{
SimpTabIB[0][0]+=StrToFloat(SGDi->Cells[i][1]);
SimpTabIB[i][0]=1;
for(int j=1;j<=n;j++)
SimpTabIB[i][0]-=StrToFloat(SGAij->Cells[j][i]);
SimpTabIB[i+n][0]=-1;
SimpTabIB[0][i]=StrToFloat(SGDi->Cells[i][1]);
SimpTabIB[0][i+n]=StrToFloat(SGNi->Cells[i][1]);
SimpTabIB[0][i+n2]=SimpTabIB[0][i];
SimpTabIB[i+n][i]=-1;
SimpTabIB[i][i+n]=1;
SimpTabIB[i][i+n2]=1;
for(int j=1;j<=n;j++)
{
SimpTabIB[j][i+n2]-=StrToFloat(SGAij->Cells[i][j]);
}
SimpTabIB[i+n][i+n2]=-1;
}
if(!SimpM(SimpTabIB,PerBas,PerNBasIB))return false;
if(SimpTabIB[0][0]!=0)return false;
if(VseTNBas())return true;
return false;
}
Симплекс метод
bool TForm1::SimpM(DynamicArray<DynamicArray<long double> > &SimpTab,DynamicArray<AnsiString> &PerBas,DynamicArray<AnsiString> &PerNBas)
{
bool Opt=PrOpt(SimpTab) ? true : false;
bool NResh=PrNResh(SimpTab) ? true : false;
while(!(Opt||NResh))
{
int VStolb=VedStolb(SimpTab);
int VStr=VedStr(SimpTab,VStolb);
SimpPreobr(SimpTab,PerBas,PerNBas,VStolb,VStr);
Opt=PrOpt(SimpTab) ? true : false;
NResh=PrNResh(SimpTab) ? true : false;
}
return Opt;
}
Проверка на оптимальность
bool TForm1::PrOpt(DynamicArray<DynamicArray<long double> > &SimpTab)
{
for(int i=1;i<SimpTab.Length;i++)
if(SimpTab[i][0]>0)return false;
return true;
}
Проверка на неразрешимость
bool TForm1::PrNResh(DynamicArray<DynamicArray<long double> > &SimpTab)
{
bool a;
int n3=3*n;
for(int i=1;i<=n;i++)
if(SimpTab[i][0]>0)
{
a=true;
for(int j=1;j<=n3;j++)
if(SimpTab[i][j]>0)
{
a=false;
break;
}
}
return a;
}
Выбор ведущего столбца
int TForm1::VedStolb(DynamicArray<DynamicArray<long double> > &SimpTab)
{
int I=0;
long double q=0;
for(int i=1;i<SimpTab.Length;i++)
if(SimpTab[i][0]>q)
{
q=SimpTab[i][0];
I=i;
}
return I;
}
Выбор ведущей строки
int TForm1::VedStr(DynamicArray<DynamicArray<long double> > &SimpTab, int VStolb)
{
int VStr;
long double min;
for(int i=1;i<SimpTab[0].Length;i++)
{
if(SimpTab[VStolb][i]>0)
{
min=SimpTab[0][i]/SimpTab[VStolb][i];
VStr=i;
break;
}
}
long double a;
for(int i=VStr;i<SimpTab[0].Length;i++)
{
if(SimpTab[VStolb][i]>0)
{
a=SimpTab[0][i]/SimpTab[VStolb][i];
if(min>=a)
{
min=a;
VStr=i;
}
}
}
return VStr;
}
Преобразование симплексной таблицы
void TForm1::SimpPreobr(DynamicArray<DynamicArray<long double> > &SimpTab,DynamicArray<AnsiString> &PerBas,DynamicArray<AnsiString> &PerNBas, int VStolb, int VStr)
{
int VStr1=VStr-1;
int VStolb1=VStolb-1;
AnsiString Per=PerBas[VStr1];
PerBas[VStr1]=PerNBas[VStolb1];
PerNBas[VStolb1]=Per;
SimpTab[VStolb][VStr]=1/SimpTab[VStolb][VStr];
for(int i=0;i<SimpTab.Length;i++)
if(i!=VStolb)
for(int j=0;j<SimpTab[0].Length;j++)
if(j!=VStr)
SimpTab[i][j]=SimpTab[i][j]-(SimpTab[i][VStr]*
SimpTab[VStolb][j]*SimpTab[VStolb][VStr]);
for(int i=0;i<SimpTab.Length;i++)
{
if(i!=VStolb)SimpTab[i][VStr]*=SimpTab[VStolb][VStr];
}
for(int i=0;i<SimpTab[0].Length;i++)
{
if(i!=VStr)SimpTab[VStolb][i]*=-SimpTab[VStolb][VStr];
}
}