package zainab_broject_or;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Zainab_broject_or {
static int a[][]=new int[10][10];
static int b[][]=new int[10][10];
static int a1[][]=new int[10][10];
static int x[][]=new int[10][10];
static int loop[][]=new int[10][10];
static int nbc[][]=new int[10][10];
static int s[]=new int[10];
static int s1[]=new int[10];
static int d[]=new int[10];
static int d1[]=new int[10];
static int pi[]=new int[10];//??? ???????
static int pj[]=new int[10];//??? ????????
static int ss=0,sd=0,min,min1,min2,maxp=0;
static char sign[][]=new char[10][10];//??? ????????
static int u[]=new int[10];
static int v[]=new int[10];
static int r,c,i,j,k,lc=0,mi,mj,max=0,tc=0;
static int flag=0,opt;//?????? ??? ?????? ?? ?? switcch
public static void main(String[] args) throws IOException {
boolean m=true;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
while(m==true)
{
System.out.println("***************");
System.out.println(" MODI METHOD ");
System.out.println("***************");
System.out.println(" 1. North West Corner Rule+");
System.out.println(" 2. minimum Cost Method+");
System.out.println(" 3. Vogal's Approximation Method+");
System.out.println(" 4. Exit");
System.out.println("Enter the Choice : ");
opt=Integer.parseInt(br.readLine());//instead of String z=JOptioPane.show input dialog(null,"enter obt");
switch(opt)
{
case 1:input();//nwc();
m=true;
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
System.out.println("The Initial Basic Feasible Solution Using NWC Rule");
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
display();
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
break;
case 2:input();lcm();m=true;
System.out.println("The Initial Basic Feasible Solution Using MCM");
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
display();
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
break;
case 3:input();vam();m=true;
System.out.println("The Initial Basic Feasible Solution Using VAM");
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
display();
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
break;
case 4:m=false;
default:
m=false;// ??? ??? ?? ???? ????? ???? ?? m
}
k=0;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
//??? ???? ???? ?? demand ?? ?? source
b[i][j]=a[i][j];
// ?? ??????? ?????? ??????? ?????? ???? ?? product ai
if(x[i][j]!=0)
k++;
}
//?? resource
for(i=0;i<r;i++)
// ?? cost
for(j=0;j<c;j++)
{
nbc[i][j]=0;
loop[i][j]=0;
}
for(i=0;i<r;i++)
// ??? ?????? ?? ?? stepping store ?? ?????? ???? ??? ?? basic ? ?? non basic
u[i]=0;
for(j=0;j<c;j++)
v[j]=0;
mi=0;mj=0;
while(k==r+c-1)
{
/* FOR BASIC CELL */
/* Counting the no.of allocations in row & column */
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(x[i][j]!=0)// ?? product
u[i]++;
for(j=1;j<=c;j++)
for(i=1;i<=r;i++)
if(x[i][j]!=0)
v[j]++;
/* Selecting the row or column having max no.of allocations */
max=0;flag=0;
for(i=1;i<=r;i++)
if(max<u[i])
{
max=u[i];
mi=i;
flag=1;
}
for(j=1;j<=c;j++)
if(max<v[j])
{
max=v[j];
mj=j;
flag=2;
}
for(i=1;i<=r;i++)
u[i]=0;
for(j=1;j<=c;j++)
v[j]=0;
/* Assigning value for u and v */
if(flag==1) {
for(j=1;j<=c;j++)
if(x[mi][j]!=0)
v[j]=b[mi][j];
for(k=1;k<=r;k++)
{
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(x[i][j]!=0 && v[j]!=0)
u[i]=b[i][j]-v[j];
for(j=1;j<=c;j++)
for(i=1;i<=r;i++)
if(x[i][j]!=0 && u[i]!=0)
v[j]=b[i][j]-u[i];
}
}
if(flag==2)
{
for(i=1;i<=r;i++)
if(x[i][mj]!=0)
u[i]=b[i][mj];
for(k=1;k<=r;k++)
{
for(j=1;j<=c;j++)
for(i=1;i<=r;i++)
if(x[i][j]!=0 && u[i]!=0)
v[j]=b[i][j]-u[i];
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(x[i][j]!=0 && v[j]!=0)
u[i]=b[i][j]-v[j];
}
}
/* FOR NON BASIC CELL */
max=0;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(x[i][j]==0)
{
nbc[i][j]=b[i][j]-(u[i]+v[j]);
if(max>nbc[i][j])
{
max=nbc[i][j];
mi=i;
mj=j;
}
}
if(max>=0)
break;
/* Loop Formation */
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
if(x[i][j]!=0)
loop[i][j]=1;
else
loop[i][j]=0;
sign[i][j]=' ';
}
for(k=1;k<=r;k++){
for(i=1;i<=r;i++){
for(j=1;j<=c;j++)
if(loop[i][j]==1)
lc++;
if(lc==1 && i!=mi)
for(j=1;j<=c;j++)
loop[i][j]=0;
lc=0;
}
lc=0;
for(j=1;j<=c;j++){
for(i=1;i<=r;i++)
if(loop[i][j]==1)
lc++;
if(lc==1 && j!=mj)
for(i=1;i<=r;i++)
loop[i][j]=0;
lc=0;
}
}
/* Assigning the Sign */
sign[mi][mj]='+';
i=mi;
for(k=1;k<=3;k++)
{
for(j=1;j<=c;j++)
if(loop[i][j]==1 && sign[i][j]==' ')
{
sign[i][j]='-';
break;
}
for(i=1;i<=r;i++)
if(loop[i][j]==1 && sign[i][j]==' ')
{
sign[i][j]='+';
break;
}
}
/* Finding @ Value */
min=9999;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(sign[i][j]=='-' && min>x[i][j])
min=x[i][j];
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(sign[i][j]=='+')
x[i][j]+=min;
else if(sign[i][j]=='-')
x[i][j]-=min;
/* Checking m+n-1 Condition */
k=0;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(x[i][j]!=0)
k++;
} /* End of While */
System.out.println("The Optimum Solution Using Modi Method");
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
display();
}
}
/* To get input values */
static void input()throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(" Enter the Row Value : ");
r=Integer.parseInt(br.readLine());
System.out.println(" Enter the Column Value : ");
c=Integer.parseInt(br.readLine());
System.out.println("Enter the Matrix Values ");
for(i=1;i<=r;i++)
{
for(j=1;j<=c;j++)
{
a[i][j]=Integer.parseInt(br.readLine());
a1[i][j]=b[i][j]=a[i][j];
}
}
for(i=0;i<10;i++)
for(j=0;j<10;j++)
x[i][j]=0;
System.out.println("Enter the Supply values");
for(i=1;i<=r;i++)
{
s[i]=Integer.parseInt(br.readLine());
s1[i]=s[i];
ss+=s[i];
}
System.out.println("Enter the Demand Values");
for(j=1;j<=c;j++)
{
d[j]=Integer.parseInt(br.readLine());
d1[j]=d[j];
sd+=d[j];
}
/* Checking for Balanced */
if(ss==sd)
System.out.println(" It is Balanced");
if(ss<sd)
{
r++;
s[r]=sd-ss;
ss+=s[r];
for(j=1;j<=c;j++)
a[r][j]=0;
System.out.println("It is Unbalanced");
}
if(ss>sd)
{
c++;
d[c]=ss-sd;
sd+=d[c];
for(i=1;i<=r;i++)
a[i][c]=0;
System.out.println(" It is Unbalanced");
}
}
/* Function of North West Corner Rule */
static void nwc()
{
k=0;i=1;j=1;
while(k<(r+c)-1)
{
if(s[i]>d[j])
{
k++;
x[i][j]=d[j];
s[i]=s[i]-d[j];
ss-=d[j];
sd-=d[j];
d[j]=0;
j++;
}
else if(s[i]<d[j])
{
k++;
x[i][j]=s[i];
d[j]=d[j]-s[i];
ss-=s[i];
sd-=s[i];
s[i]=0;
i++;
}
else
{
k++;
x[i][j]=s[i];
ss-=s[i];
sd-=s[i];
s[i]=0;
d[j]=0;
i++;
j++;
}
if((ss==0) && (sd==0))
break;
}
}
/* Function of Least Cost Method */
static void lcm()
{
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
b[i][j]=a[i][j];
k=0;mi=1;mj=1;
while(k<(r+c)-1)
{
min=9999;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(min>b[i][j] && b[i][j]!=-1)
{
min=b[i][j];
mi=i;mj=j;
}
if(s[mi]>d[mj])
{
k++;
x[mi][mj]=d[mj];
s[mi]=s[mi]-d[mj];
ss-=d[mj];
sd-=d[mj];
d[mj]=0;
for(i=1;i<=r;i++)
b[i][mj]=-1;
}
if(s[mi]<d[mj])
{
k++;
x[mi][mj]=s[mi];
d[mj]=d[mj]-s[mi];
ss-=s[mi];
sd-=s[mi];
s[mi]=0;
for(j=1;j<=c;j++)
b[mi][j]=-1;
}
if(s[mi]==d[mj])
{
k++;
x[mi][mj]=s[mi];
ss-=s[mi];
sd-=s[mi];
s[mi]=0;
d[mj]=0;
for(i=1;i<=r;i++)
b[i][mj]=-1;
for(j=1;j<=c;j++)
b[mi][j]=-1;
}
if((ss==0)&&(sd==0))
break;
}
}
/* Function of Vogel's Approximation Method */
static void vam()
{
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
b[i][j]=a[i][j];
k=0;mi=0;mj=0;
while(k<(r+c)-1)
{
/* Selecting Penalty Value for Row */
for(i=1;i<=r;i++)
{
min1=9999;min2=9999;
for(j=1;j<=c;j++)
if(min1>b[i][j] && b[i][j]!=-1)
{
min1=b[i][j];
mj=j;
}
for(j=1;j<=c;j++)
if(min2>b[i][j] && b[i][j]!=-1 && min2>=min1 && j!=mj)
min2=b[i][j];
pi[i]=min2-min1;
if(pi[i]>9000)
pi[i]=min1;
}
/* Selecting Penalty Value for Column */
for(j=1;j<=c;j++)
{
min1=9999;min2=9999;
for(i=1;i<=r;i++)
if(min1>b[i][j] && b[i][j]!=-1)
{
min1=b[i][j];
mi=i;
}
for(i=1;i<=r;i++)
if(min2>b[i][j] && b[i][j]!=-1 && min2>=min1 && i!=mi)
min2=b[i][j];
pj[j]=min2-min1;
if(pj[j]>9000)
pj[j]=min1;
}
/* Selecting Max. Penalty Value */
maxp=0;flag=0;
for(i=1;i<=r;i++)
if(maxp<pi[i])
{
maxp=pi[i];
mi=i;
flag=1;
}
for(j=1;j<=c;j++)
if(maxp<pj[j])
{
maxp=pj[j];
mj=j;
flag=2;
}
/* Selecting min value in max penalty row or column */
min1=9999;
if(flag==1)
for(j=1;j<=c;j++)
if(min1>b[mi][j] && b[mi][j]!=-1)
{
min1=b[mi][j];
mj=j;
}
if(flag==2)
for(i=1;i<=r;i++)
if(min1>b[i][mj] && b[i][mj]!=-1)
{
min1=b[i][mj];
mi=i;
}
/* Allocation */
if(s[mi]>d[mj])
{
k++;
x[mi][mj]=d[mj];
s[mi]=s[mi]-d[mj];
ss-=d[mj];
sd-=d[mj];
d[mj]=0;
for(i=1;i<=r;i++)
b[i][mj]=-1;
}
if(s[mi]<d[mj])
{
k++;
x[mi][mj]=s[mi];
d[mj]=d[mj]-s[mi];
ss-=s[mi];
sd-=s[mi];
s[mi]=0;
for(j=1;j<=c;j++)
b[mi][j]=-1;
}
if(s[mi]==d[mj])
{
k++;
x[mi][mj]=s[mi];
ss-=s[mi];
sd-=s[mi];
s[mi]=0;
d[mj]=0;
for(i=1;i<=r;i++)
b[i][mj]=-1;
for(j=1;j<=c;j++)
b[mi][j]=-1;
}
if((ss==0)&&(sd==0))
break;
}
}
static void display()
{
System.out.println("Cost Matrix");
for(i=1;i<=r;i++)
{
for(j=1;j<=c;j++)
{
System.out.print(" "+a[i][j]);
}
System.out.println();
System.out.println(" "+s1[i]);
}
System.out.println();
for(j=1;j<=c;j++)
System.out.println(" "+d1[j]); System.out.println("Allocated Matrix ");
for(i=1;i<=r;i++)
{
for(j=1;j<=c;j++)
if(x[i][j]!=0)
{
System.out.print(x[i][j]+"| "+a[i][j]+" ");
System.out.println();
}
else
System.out.print(" "+a[i][j]);
}
tc=0;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
tc=tc+(a[i][j]*x[i][j]);
System.out.println("Total Cost is "+tc);
return;
}
}