Лабораторная работа №1 (Задача 16)
.docЗадача 16. Зерно из трех зернохранилищ доставляется на грузовиках четырем птицеводческим фермам, при этом некоторые зернохранилища не могут непосредственно поставлять зерно определенным фермам. Пропускная способность маршрутов от зернохранилищ до птицеводческих ферм ограничена количеством используемых грузовиков и числом выполняемых ежедневно рейсов. В следующей таблице показаны ежедневные предложения зернохранилищ и ежедневный спрос птицеводческих ферм (в тысячах фунтов), в ячейках таблицы указаны пропускные способности соответствующих маршрутов.
Фермы
Зернохранилища
Решим как задачу о нахождении максимального потока:
1 - Исток
2 - З1 зернохранилище
3 - З2 зернохранилище
4 - З3 зернохранилище
5 - Ф1 ферма
6 - Ф2 ферма
7 - Ф3 ферма
8 - Ф4 ферма
9 - Cток
Итерация 1:
N1 = {1,4,5,9}
f1 = min{∞, 200, 100, 200} = 100
Итерация 2:
N2 = {1,4,6,9}
f1 = min {∞, 100, 40, 10} = 10
Итерация 3:
N3 = {1,4,8,9}
f1 = min {∞, 90, 40, 20} = 20
Итерация 4:
N4 = {1,4,7,9}
f1 = min {∞, 70, 30, 60} = 30
Итерация 5:
N5 = {1,2,5,9}
f1 = min {∞, 20, 30, 100} = 20
Итерация 6:
N6 = {1, 3, 7, 9}
f1 = min {∞, 20, 5, 30} = 5
Итерация 7:
Из каждого зернохранилища в фермы поступит следующее количество зерна:
З1 → Ф1 = 20
З2 → Ф3 = 5
З3 → Ф1 = 100
З3 → Ф2 = 10
З3 → Ф3 = 30
З3 → Ф4 = 20
В итоге всего фермы получат зерна:
Ф1 = 120
Ф2 = 10
Ф3 = 35
Ф4 = 20
- что не является достаточным, чтобы удовлетворить спрос ферм.
Вывод:
Спрос ферм не будет удовлетворен.
Листинг программы:
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <iostream.h>
int MAX (int, int, int);
int i=0, j=0,
max, y=0, t=0, label = 0, n_i,n_j;
int ferma[4]={200, 10, 60, 20}, zerno [3] = {20,20,200},
proizvod [3][4] = {30, 5, 0, 40, 0, 0, 5, 90, 100, 40, 30, 40};
int f=4, z=3, p=0, k, l, I, min=0;
int matrica[45][45], matrica_2[45][45];
int func[45], N_i[45], N_j[45], N[45];
int S[45],nom[45], nom_2[45],T=0;
int MAX (int i,int t, int max)
{
S[0]=0;
for (j=0;j<=l;j++)
{
if (matrica[i][j] != 0 && nom_2[j]!=j)
if( j!=n_i)
{
S[j] = matrica[i][j];
nom[t]=j;
t++;
}
if (j==n_i)
{
nom_2[j]=j;
T++;
}
if (T==8 && nom_2[j]==j )
{
matrica_2[0][n_j]=matrica[0][n_j];
T=0;
for(j=0;j<=l;j++)
{
nom_2[j]=0;
matrica_2[n_j][j]=matrica[n_j][j];
matrica[n_j][j]=0;
matrica_2[j][n_j]=matrica[j][n_j];
matrica[j][n_j]=0;
}
matrica[0][n_j]=0;
break;
}
}//for
for (int m=0;m<t;m++)
for(j=0; j<=l; j++)
if (S[j]>S[max] && (nom[m]==j))
max=j;
i=max;
return i;
}
void main ()
{
int F;
k=f+z+2;
l=k;
cout<<"Спрос: ";
for(int t=0; t<k;t++)
for( p=0;p<l;p++)
matrica[t][p]=0;
matrica_2[t][p]=0;
for (i=0;i<f;i++)
{
cout<<ferma[i]<<" ";
matrica[1+z+i][8]=ferma[i];
matrica_2[1+z+i][8]=ferma[i];
}
cout<<endl<<endl;
cout<<"Преложение : ";
for ( j=0;j<z;j++)
{
cout<<zerno[j]<<" ";
matrica[0][1+j]=zerno[j];
matrica_2[0][1+j]=zerno[j];
}
cout<<endl<<endl;
cout<<"Propusknie sposobnosty : "<<endl;
for(j=0;j<z; j++)
{
for (i=0;i<f; i++)
{
cout<<proizvod[j][i]<<" ";
matrica[j+1][1+z+i]=proizvod[j][i];
matrica_2[j+1][1+z+i]=proizvod[j][i];
}
cout<<endl;
}
cout<<endl;
//Матрица
for( t=0; t<k;t++)
{
for( p=0;p<l;p++)
cout<<matrica[t][p]<<"\t";
cout<<endl;
}
int x=0, y=0,p=0;
int p1=0, S1, S2, h=0;
cout<<"//-------------------------------------------------------------------//"<<endl;
while (1){
x=0, y=1,p=0;
p1=0, S1, S2, h=0;
N[0]=0;
int R=0;
while(1)
{
func[min]=func[1];
I=MAX(x,0,0);
if (I==0)
label++;
N[p+1]=I;
y=(p+1)%2;
if ( y == 0)
{
N_i[x]=I;
n_i=N_i[x];
}
else
{
N_j[x]=I;
n_j=N_j[x];
}
func[R]=matrica[x][I];
x=I;
if(func[R] == 0)
{
h=1;
break;
}
if (x == (l-1))
{
T=0;
for (j=0; j<=R; j++)
if (func[j]<=func[min] && func[j]!=func[min])
min=j;
F=min;
for(i=0;i<=R;i++)
{
S1=N[i];
S2=N[i+1];
matrica[S2][S1] = matrica[S2][S1]+func[F];
matrica_2[S2][S1] = matrica_2[S2][S1]+func[F];
matrica[S1][S2] = matrica[S1][S2]-func[F];
matrica_2[S1][S2] = matrica_2[S1][S2]-func[F];
}
break;
}
p++;
R++;
}//while
if (label==9)
break;
}
cout<<endl;
for( t=0; t<k;t++)
{
for( i=0;i<l;i++)
cout<<matrica_2[t][i]<<"\t";
cout<<endl;
}
cout<<endl<<endl<<"Схема траспортировки: "<<endl<<endl;
cout<<"\t Зернохранилища"<<endl;
cout<<" \t";
//cout<<" -----------------------"<<endl<<"\t";
for (j=1;j<=z;j++)
cout<<" "<<j<<"\t";
cout<<endl;
for (i=(z+1);i<(1+z+f);i++)
{
cout<<"Ферма_"<<i-z<<" ";
for (j=1;j<(1+z);j++)
{
cout<<matrica_2[i][j]<<"\t";
}
cout<<endl;
}
getch();