Решение транспортных задач венгерским методом

Дипломная работа - Компьютеры, программирование

Другие дипломы по предмету Компьютеры, программирование



if(C[i][j]<min)

min=C[i][j];

if (min!=0)

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

C[i][j]-=min;

}

Predv();

//Создание матрицы опорного плана

Xn=Cn;

Xm=Cm;

X=new int*[Xn];

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

X[i]=new int[Xm];

for (int j=0; j<Cm; j++){

for (int i=0; i<Cn; i++){

if(C[i][j]==0){

//Если ограничение меньше

if(D[i][j]<=P[j] && D[i][j]<=Z[i]){

X[i][j]=D[i][j];

P[j]-=X[i][j];

Z[i]-=X[i][j];

}

else{

if(P[j]<Z[i]){

X[i][j]=P[j];

P[j]-=X[i][j];

Z[i]-=X[i][j];

}

else{

X[i][j]=Z[i];

P[j]-=X[i][j];

Z[i]-=X[i][j];

}

}

}

else

X[i][j]=0;

}

}

//проверка опитимальности

OPrz=0;

OPtr=0;

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

OPrz+=Z[i];

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

OPtr+=P[i];

if((OPrz+OPtr)==0){

//Заполнения таблицы издержек

Izderg->RowCount=Cn;

Izderg->ColCount=Cm;

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

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

Izderg->Cells[j][i]=FormatFloat("",C[i][j]/100.0);

//Заполнения таблицы опорного плана

Plan->RowCount=Xn;

Plan->ColCount=Xm;

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

for(int j=0;j<Xm;j++){

if(X[i][j]==0)

Plan->Cells[j][i]="";

else

Plan->Cells[j][i]=FormatFloat("",X[i][j]/100.0);

}

L=0;

Lstr="L=";

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

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

if(X[i][j]>0)

{

L+=X[i][j]*C0[i][j];

Lstr+=FormatFloat("",C0[i][j]/100.0)+"*"+FormatFloat("",X[i][j]/100.0)+"+";

}

Lstr.Delete(Lstr.Length(),1);

Lstr+="="+FormatFloat("",L/10000.0);

Edit2->Text=Lstr;

MessageDlg(L"План оптимизирован.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

return;

}

//создание матрицы нулей

Nn=Cn;

Nm=Cm;

N=new int*[Nn];

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

N[i]=new int[Nm];

//Начало итерации-----------------------------------------------------------

while((OPrz+OPtr)!=0)

{

posl=-1;

pstr=-1;

int v=0;

int *Q=new int[Cn*Cm];

//определение нулей

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

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

{

if(C[i][j]==0)

{

if(X[i][j]==D[i][j])

N[i][j]=2;//полный ноль

else{

if(X[i][j]==0)

N[i][j]=0; //обычный ноль

else

N[i][j]=1; //неполный ноль

}

}

else

N[i][j]=-1; //не ноль

}

//массив для выделения строк

Fn=Zn;

F=new int[Fn];

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

F[i]=0;

//выделение столбцов

Gm=Pm;

G=new int[Gm];

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

{

if(P[i]==0)//Потребление равно нулю

G[i]=1; //Выделение

else

G[i]=0; //нет

}

bool kor=false; //необходимость коррекции

bool np; //необходимостть нового поиска

while(kor==false)

{

np=false;

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

{

if(G[j]==1) //если выделен столбец

continue;

else

{

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

{

if(F[i]==1) //если выделена строка

continue;

if(N[i][j]==0 || N[i][j]==1)//если неполный ноль

{

N[i][j]=3;//обозначение штрихом

if(Z[i]==0) //если запас равен нулю

{

F[i]=1; //выделение строки

for(int k=0;k<Cm;k++) //проход по строке

{

if(G[k]==0) //если строка невыделена

continue;

if(N[i][k]==1 || N[i][k]==2)//если сущ. ноль

{

N[i][k]=4; //обозначение звездочкой

G[k]=0; //снятие выделения

np=true; //необходимость поиска заново

}

}

}

else

{

kor=true; //необходимость коррекции плана

Q[v]=Z[i]; //запоминание невязки по строке

v++; //увеличение количества

Q[v]=D[i][j]-X[i][j]; //резервы насыщения

v++;

posl=j; //запоминание места

pstr=i; //первого элемента

}

}

if(np==true || kor==true)

break;

}

}

if(np==true || kor==true)

break;

}

//эквивалентне преобразования

if(np==false && kor==false)

{

bool go=false;

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

{

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

{

if((F[i]==1 && G[j]==0) || (F[i]==0 && G[j]==1))

continue;

else

{

if(F[i]==1 && G[j]==1)

{

if(C[i][j]<0)

{

go=true;

break;

}

}

else

{

if(C[i][j]>0)

{

go=true;

break;

}

}

}

}

if(go==true)

break;

}

if(go==false)

{

MessageDlg(L"Задача неразрешима.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

Edit2->Text="L=0";

return;

}

bool first=true;

int min=0;

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

{

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

{

//если один раз выделена ячейка

if((F[i]==1 && G[j]==0) || (F[i]==0 && G[j]==1))

continue;

else

{

//если дважды выделена

if(F[i]==1 && G[j]==1)

{

//если первый раз

if(first==true)

{

if(C[i][j]<0)

{

min=abs(C[i][j]);

first=false;

}

}

else

{

if(C[i][j]<0)

{

if(abs(C[i][j])<min)

min=abs(C[i][j]);

}

}

}

//если невыделена

if(F[i]==0 && G[j]==0)

{

if(first==true)

{

if(C[i][j]>0)

{

min=C[i][j];

first=false;

}

}

else

{

if(C[i][j]>0)

{

if(C[i][j]<min)

min=C[i][j];

}

}

}

}

}

}

//вычитание элемента

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

{

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

{

//если один раз выделена

if((F[i]==1 && G[j]==0) || (F[i]==0 && G[j]==1))

continue;

else

{

//если дважды

if(G[j]==1 && F[i]==1)

C[i][j]+=min;

else

C[i][j]-=min;

}

}

}

//новая разметка

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

{

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

{

if(C[i][j]==0)

{

if(X[i][j]==D[i][j])

N[i][j]=2;

else

{

if(X[i][j]==0)

N[i][j]=0;

else

N[i][j]=1;

}

}

else

N[i][j]=-1;

}

}

delete []F;

F=NULL;

Ecviv();

//массив для выделения строк

Fn=Zn;

F=new int[Fn];

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

F[i]=0;

}

}

NKor=0;

//составление цепочки

int* Str=new int[Cn*Cm];

int* Stol=new int[Cn*Cm];

int str=0;

int stol=0;

Str[str]=pstr;

Stol[stol]=posl;

Cep[nomer][pstr][posl]=1; //стрела вправо

str++;

stol++;

Stol[stol]=posl; //для начала цепочки

stol++;

int stroka=-1;(1)

{(int i=0;i<Cn;i++)

{

if(N[i][Stol[stol-1]]==4) //если сущ. 0*

{

stroka=i;

Str[str]=i;

if(Str[str]<Str[str-1]) //если новый 0* выше 0'

{

if (Stol[stol-2]<Stol[stol-1])//если старый 0* левее 0'

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=2;//слева вверх

for(int i=Str[str]+1;i<Str[str-1];i++)

{

if(Cep[nomer][i][Stol[stol-1]]==3)

Cep[nomer][i][Stol[stol-1]]=12; //крест

elseCep[nomer][i][Stol[stol-1]]=4; //вертикально

}

}

else

{

if (Stol[stol-2]>Stol[stol-1])//если старый 0* правее 0'

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=5;//справа наверх

for(int i=Str[str]+1;i<Str[str-1];i++)

{

if(Cep[nomer][i][Stol[stol-1]]==3)

Cep[nomer][i][Stol[stol-1]]=12; //крест

else

Cep[nomer][i][Stol[stol-1]]=4; //вертикально

}

}

else //если начало цепочки

{

for(int i=Str[str]+1;i<=Str[str-1];i++)