Решение транспортных задач венгерским методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
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++)