Simplex Method:
Simplex method is an iterative procedure for solving Linear programming problem in a finite number of steps. In below, explain the simplex method and use simple example for the better understand of how to solve LPP with using simplex method.
Definition of Linear Programming Problem(LPP):
A mathematical technique used to obtain an optimum solution in resource allocation problem, such as production planning. It is a mathematical technique for efficient and effective utilization of limited resources to achieve organization objectives (maximize profits or minimize cost).
Java Program to Solve the LPP By Simplex Method:
import java.util.*;
class simplexlpp
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Example of the Question.");
System.out.println("Solve the LPP by simplex method.");
System.out.println("Max Z = 3x1+2x2+5x3 [Object Function]");
System.out.println("Subject To x1+2x2+x3<=430 [1st Set of Constant]");
System.out.println(" 3x1+2x3<=460 [2nd Set of Constant]");
System.out.println(" x1+4x2<=420 [3nd Set of Constant]");
System.out.println(" x1,x2,x3>=0 [Non -ve restriction]");
System.out.println("If question is Minimization problem, Then enter 'min'");
System.out.println("If question is Maximization problem, Then enter 'max'");
System.out.println("Enter what type of question, Minimize or Maximize : ");
String qtype=sc.next();
System.out.println("If no of Set of Constant is 2 or no of equation is 2, Then enter '2'");
System.out.println("If no of Set of Constant is 3 or no of equation is 3, Then enter '3'");
System.out.println("Enter no of Set of Constant or no of equation is : ");
int etype=sc.nextInt();
System.out.println("if Objective functon symble x1 or x2 or x3 then enter x1");
System.out.println("if Objective functon symble x or y or z then enter x");
System.out.println("Example Max Z = 3x+4y+7zthen enter x");
System.out.println("Example Max Z = 3x1+2x2+5x3 then enter x1");
System.out.println("Enter Objective functon symble : ");
String s=sc.next();
String x111= "",x112= "",x113= "",s1= "s1",s2= "s2",s3= "s3";
int table=0;
if(s.equals("x1"))
{
x111="x1";
x112="x2";
x113="x3";
}
else if(s.equals("x"))
{
x111="X";
x112="Y";
x113="Z";
}
int x11,x12,x13,x21,x22,x23,x31,x32,x33,xb1,xb2,xb3,s11=1,s12=0,s13=0,s21=0,s22=1,s23=0,s31=0,s32=0,s33=1;
if(etype==2)
{
int mz1,mz2,mz3=0,mz4=0;
System.out.println("Example "+qtype+" Z = 4x1+5x2 then value of objective function value is 4 5");
System.out.println("Example "+qtype+" Z = 3x1+2x2 then value of objective function value is 3 2 ");
System.out.println("Enter value of objective function value");
mz1=sc.nextInt();
mz2=sc.nextInt();
System.out.println("Enter 1st Set of Constant means question is x1 +x2 <=4 then enter 1 1 4");
x11=sc.nextInt();
x12=sc.nextInt();
xb1=sc.nextInt();
System.out.println("Enter 2st Set of Constant means question is x1 -x2 <=2 then enter 1 -1 2");
x21=sc.nextInt();
x22=sc.nextInt();
xb2=sc.nextInt();
System.out.println("\nstep-1 (Standard form)");
System.out.println("------- ------------------");
System.out.println("Rewrite the constraint into equation by adding slack variables s1,s2. The standard form of LPP becames-");
if(qtype.equals("min"))
{
mz1= -mz1;
mz2= -mz2;
System.out.println(" "+qtype+" z' = "+mz1+x111+" + "+mz2+x112+" + 0s1 + 0s2");
}
else
{
System.out.println(" "+qtype+" z = "+mz1+x111+" + "+mz2+x112+" + 0s1 + 0s2");
}
System.out.println("Subject to "+x11+x111+" + "+x12+x112+" + s1 = "+xb1);
System.out.println(" "+x21+x111+" + "+x22+x112+" + s2 = "+xb2);
System.out.println(" "+x111+","+x112+",s1,s2 >=0");
System.out.println("\nstep-2 (Matrix form)");
System.out.println(" AX=B");
System.out.println("That is | "+x11+" "+x12+" "+s11+" "+s12+" | | "+x111+" | = | "+xb1+" |");
System.out.println(" | "+x21+" "+x22+" "+s21+" "+s22+" | | "+x112+" | = | "+xb2+" |");
System.out.println(" | s1 |");
System.out.println(" | s2 |");
System.out.println("\nstep-3 (To Find Initial Basic Feasible Solution)");
System.out.println(" Put "+x111+" = "+x112+" = 0");
System.out.println(" s1="+xb1);
System.out.println(" s2="+xb2);
String sb[]={"s1","s2"};
int cj[]={mz1,mz2,mz3,mz4};
float cj1[]={xb1,x11,x12,s11,s12};
float cj2[]={xb2,x21,x22,s21,s22};
int cb1=0,cb2=0,i=0,feasible=0;
while(feasible==0)
{
if(table==0)
{
System.out.println("\n Initial Table");
}
else if(table==1)
{
System.out.println("\n First Iteration");
}
else if(table==2)
{
System.out.println("\n Second Iteration");
}
else
{
System.out.println("\n Third Iteration");
}
table++;
System.out.println(" ---------------\n");
System.out.println(" --------------------------------------------------------");
System.out.println(" | Cj\t| "+mz1+"\t| "+mz2+"\t| 0\t| 0 |");
System.out.println(" | SB | CB XB\t| "+x111+"\t| "+x112+"\t| S1\t| S2 |");
System.out.println(" --------------------------------------------------------");
System.out.println(" | "+sb[0]+" | "+cb1+" "+cj1[0]+"\t| "+cj1[1]+"\t| "+cj1[2]+"\t| "+cj1[3]+"\t| "+cj1[4]+" |");
System.out.println(" | "+sb[1]+" | "+cb2+" "+cj2[0]+"\t| "+cj2[1]+"\t| "+cj2[2]+"\t| "+cj2[3]+"\t| "+cj2[4]+" |");
System.out.println(" --------------------------------------------------------");
float z[]= new float[5];
float dj[]= new float[5];
for(i=0;i<=4;i++)
{
z[i]=(cb1*cj1[i])+(cb2*cj2[i]);
}
for(i=0;i<4;i++)
{
dj[i+1]=z[i+1]-cj[i];
}
System.out.println(" | | zj="+z[0]+" \t| "+z[1]+"\t| "+z[2]+"\t| "+z[3]+"\t| "+z[4]+" |");
System.out.println(" | |del j=zj-cj\t| "+dj[1]+"\t| "+dj[2]+"\t| "+dj[3]+"\t| "+dj[4]+" |");
System.out.println(" --------------------------------------------------------");
float small=0;
int inp=0;
String x[]={x111,x112,s1,s2};
if(dj[1] >=0 && dj[2] >=0 && dj[3] >=0 && dj[4] >=0 )
{
float ans[]={0,0};
for(i=0;i<2;i++)
{
if(sb[0]==x[i])
ans[i]=cj1[0];
if(sb[1]==x[i])
ans[i]=cj2[0];
}
System.out.println("Since all zj-cj >=0,optimal basic feasible solution is obtained.");
if(qtype.equals("min"))
{
System.out.println(qtype+"z="+-(z[0])+","+x111+"="+ans[0]+","+x112+"="+ans[1]+".");
}
else
{
System.out.println("Max z="+z[0]+","+x111+"="+ans[0]+","+x112+"="+ans[1]+".");
}
feasible=1;
}
else if(dj[1]<0 && (cj1[1]==0 || cj1[1]<0) && (cj2[1]==0 || cj2[1]<0) )
{
System.out.println("Unbounded ");
feasible=1;
}
else if(dj[2]<0 && (cj1[2]==0 || cj1[2]<0) && (cj2[2]==0 || cj2[2]<0) )
{
System.out.println("Unbounded ");
feasible=1;
}
else if(dj[3]<0 && (cj1[3]==0 || cj1[3]<0) && (cj2[3]==0 || cj2[3]<0) )
{
System.out.println("Unbounded ");
feasible=1;
}
else if(dj[4]<0 && (cj1[1]==0 || cj1[1]<0) && (cj2[1]==0 || cj2[1]<0) )
{
System.out.println("Unbounded ");
feasible=1;
}
else
{
System.out.println("Find incoming vector and outgoing vector.");
for(i=0;i<4;i++)
{
if(small>dj[i+1])
{
small=dj[i+1];
inp=i;
}
}
System.out.println("Incoming vector is : "+small);
float min=0,min1=0,min2=0,pivot=0;
int outp=0;
for(i=0;i<4;i++)
{
if(small==dj[i+1])
{
if(cj1[i+1]>0 && cj2[i+1]>0)
{
min1=cj1[0]/cj1[i+1];
min2=cj2[0]/cj2[i+1];
min=(min1<min2)?min1:min2;
}
else if(cj1[i+1]>0 && cj2[i+1]<=0 )
{
min1=cj1[0]/cj1[i+1];
min=min1;
}
else if(cj2[i+1]>0 && cj1[i+1]<=0 )
{
min2=cj2[0]/cj2[i+1];
min=min2;
}
if(min==min1)
{
pivot=cj1[i+1];
outp=0;
}
else if(min==min2)
{
pivot=cj2[i+1];
outp=1;
}
}
}
System.out.println("Outgoing vector is : "+min);
System.out.println("Pivot1 element is : "+pivot);
float pivot1=cj1[inp+1],pivot2=cj2[inp+1];
for(i=0;i<=4;i++)
{
if(outp==0)
{
sb[0]=x[inp];
cj1[i]=cj1[i]/pivot;
cj2[i]=cj2[i]-(cj1[i]*pivot2);
}
else if(outp==1)
{
sb[1]=x[inp];
cj2[i]=cj2[i]/pivot;
cj1[i]=cj1[i]-(cj2[i]*pivot1);
}
}
for(i=0;i<4;i++)
{
if(sb[0]==x[i])
cb1=cj[i];
if(sb[1]==x[i])
cb2=cj[i];
}
}
}
}
else if(etype==3)
{
int mz1,mz2,mz3,mz4=0,mz5=0,mz6=0;
System.out.println("Example "+qtype+" Z = 7x1+12x2+4x3 then value of objective function value is 7 12 4");
System.out.println("Example "+qtype+" Z = 3x1+2x2+5x3 then value of objective function value is 3 2 5");
System.out.println("Enter value of objective function value");
mz1=sc.nextInt();
mz2=sc.nextInt();
mz3=sc.nextInt();
System.out.println("Enter 1st Set of Constant means question is x1 +2x2 +x3 <=430 then enter 1 2 1 430");
x11=sc.nextInt();
x12=sc.nextInt();
x13=sc.nextInt();
xb1=sc.nextInt();
System.out.println("Enter 2st Set of Constant means question is 3x1 +2x3 <=460 then enter 3 0 2 460");
x21=sc.nextInt();
x22=sc.nextInt();
x23=sc.nextInt();
xb2=sc.nextInt();
System.out.println("Enter 3rd Set of Constant means question is x1 +4x2 <=420 then enter 1 4 0 420");
x31=sc.nextInt();
x32=sc.nextInt();
x33=sc.nextInt();
xb3=sc.nextInt();
System.out.println("\nstep-1 (Standard form)");
System.out.println("------- ------------------");
System.out.println("Rewrite the constraint into equation by adding slack variables s1,s2,s3. The standard form of LPP becames-");
if(qtype.equals("min"))
{
mz1= -mz1;
mz2= -mz2;
mz3= -mz3;
System.out.println(" "+qtype+"z' = "+mz1+x111+" + "+mz2+x112+" + "+mz3+x113+" + 0s1 + 0s2 + 0s3");
}
else
{
System.out.println(" "+qtype+"z = "+mz1+x111+" + "+mz2+x112+" + "+mz3+x113+" + 0s1 + 0s2 + 0s3");
}
System.out.println("Subject to "+x11+x111+" + "+x12+x112+" + "+x13+x113+" + s1 = "+xb1);
System.out.println(" "+x21+x111+" + "+x22+x112+" + "+x23+x113+" + s2 = "+xb2);
System.out.println(" "+x31+x111+" + "+x32+x112+" + "+x33+x113+" + s3 = "+xb3);
System.out.println(" "+x111+","+x112+","+x113+",s1,s2,s3 >=0");
System.out.println("\nstep-2 (Matrix form)");
System.out.println(" AX=B");
System.out.println("That is | "+x11+" "+x12+" "+x13+" "+s11+" "+s12+" "+s13+" | | "+x111+" | = | "+xb1+" |");
System.out.println(" | "+x21+" "+x22+" "+x23+" "+s21+" "+s22+" "+s23+" | | "+x112+" | = | "+xb2+" |");
System.out.println(" | "+x31+" "+x32+" "+x33+" "+s31+" "+s32+" "+s33+" | | "+x113+" | = | "+xb3+" |");
System.out.println(" | s1 |");
System.out.println(" | s2 |");
System.out.println(" | s3 |");
System.out.println("\nstep-3 (To Find Initial Basic Feasible Solution)");
System.out.println(" Put "+x111+" = "+x112+" = "+x113+" = 0");
System.out.println(" s1="+xb1);
System.out.println(" s2="+xb2);
System.out.println(" s3="+xb3);
String sb[]={"s1","s2","s3"};
int cj[]={mz1,mz2,mz3,mz4,mz5,mz6};
float cj1[]={xb1,x11,x12,x13,s11,s12,s13};
float cj2[]={xb2,x21,x22,x23,s21,s22,s23};
float cj3[]={xb3,x31,x32,x33,s31,s32,s33};
int cb1=0,cb2=0,cb3=0,i=0,feasible=0;
while(feasible==0)
{
if(table==0)
{
System.out.println("\n Initial Table");
}
else if(table==1)
{
System.out.println("\n First Iteration");
}
else if(table==2)
{
System.out.println("\n Second Iteration");
}
else
{
System.out.println("\n Third Iteration");
}
table++;
System.out.println(" ---------------\n");
System.out.println(" ------------------------------------------------------------------------");
System.out.println(" | Cj\t| "+mz1+"\t| "+mz2+"\t| "+mz3+"\t| 0\t| 0\t| 0 |");
System.out.println(" | SB | CB XB\t| "+x111+"\t| "+x112+"\t| "+x113+"\t| S1\t| S2\t| S3 |");
System.out.println(" ------------------------------------------------------------------------");
System.out.println(" | "+sb[0]+" | "+cb1+" "+cj1[0]+"\t| "+cj1[1]+"\t| "+cj1[2]+"\t| "+cj1[3]+"\t| "+cj1[4]+"\t| "+cj1[5]+"\t| "+cj1[6]+" |");
System.out.println(" | "+sb[1]+" | "+cb2+" "+cj2[0]+"\t| "+cj2[1]+"\t| "+cj2[2]+"\t| "+cj2[3]+"\t| "+cj2[4]+"\t| "+cj2[5]+"\t| "+cj2[6]+" |");
System.out.println(" | "+sb[2]+" | "+cb3+" "+cj3[0]+"\t| "+cj3[1]+"\t| "+cj3[2]+"\t| "+cj3[3]+"\t| "+cj3[4]+"\t| "+cj3[5]+"\t| "+cj3[6]+" |");
System.out.println(" ------------------------------------------------------------------------");
float z[]= new float[7];
float dj[]= new float[7];
for(i=0;i<=6;i++)
{
z[i]=(cb1*cj1[i])+(cb2*cj2[i])+(cb3*cj3[i]);
}
for(i=0;i<6;i++)
{
dj[i+1]=z[i+1]-cj[i];
}
System.out.println(" | | zj="+z[0]+" \t| "+z[1]+"\t| "+z[2]+"\t| "+z[3]+"\t| "+z[4]+"\t| "+z[5]+"\t| "+z[6]+" |");
System.out.println(" | |del j=zj-cj\t| "+dj[1]+"\t| "+dj[2]+"\t| "+dj[3]+"\t| "+dj[4]+"\t| "+dj[5]+"\t| "+dj[6]+" |");
System.out.println(" ------------------------------------------------------------------------");
float small=0;
int inp=0;
String x[]={x111,x112,x113,s1,s2,s3};
if(dj[1] >=0 && dj[2] >=0 && dj[3] >=0 && dj[4] >=0 && dj[5] >=0 && dj[6] >=0 )
{
float ans[]={0,0,0};
for(i=0;i<3;i++)
{
if(sb[0]==x[i])
ans[i]=cj1[0];
if(sb[1]==x[i])
ans[i]=cj2[0];
if(sb[2]==x[i])
ans[i]=cj3[0];
}
System.out.println("Since all zj-cj >=0,optimal basic feasible solution is obtained.");
if(qtype.equals("min"))
{
System.out.println("Min z="+-(z[0])+","+x111+"="+ans[0]+","+x112+"="+ans[1]+","+x113+"="+ans[2]+".");
}
else
{
System.out.println("Max z="+z[0]+","+x111+"="+ans[0]+","+x112+"="+ans[1]+","+x113+"="+ans[2]+".");
}
feasible=1;
}
else if(dj[1]<0 && (cj1[1]==0 || cj1[1]<0) && (cj2[1]==0 || cj2[1]<0) && (cj3[1]==0 || cj3[1]<0))
{
System.out.println("Unbounded ");
feasible=1;
}
else if(dj[2]<0 && (cj1[2]==0 || cj1[2]<0) && (cj2[2]==0 || cj2[2]<0) && (cj3[2]==0 || cj3[2]<0))
{
System.out.println("Unbounded ");
feasible=1;
}
else if(dj[3]<0 && (cj1[3]==0 || cj1[3]<0) && (cj2[3]==0 || cj2[3]<0) && (cj3[3]==0 || cj3[3]<0))
{
System.out.println("Unbounded ");
feasible=1;
}
else if(dj[4]<0 && (cj1[1]==0 || cj1[1]<0) && (cj2[1]==0 || cj2[1]<0) && (cj3[1]==0 || cj3[1]<0))
{
System.out.println("Unbounded ");
feasible=1;
}
else if(dj[5]<0 && (cj1[2]==0 || cj1[2]<0) && (cj2[2]==0 || cj2[2]<0) && (cj3[2]==0 || cj3[2]<0))
{
System.out.println("Unbounded ");
feasible=1;
}
else if(dj[6]<0 && (cj1[3]==0 || cj1[3]<0) && (cj2[3]==0 || cj2[3]<0) && (cj3[3]==0 || cj3[3]<0))
{
System.out.println("Unbounded ");
feasible=1;
}
else
{
System.out.println("Find incoming vector and outgoing vector.");
for(i=0;i<6;i++)
{
if(small>dj[i+1])
{
small=dj[i+1];
inp=i;
}
}
System.out.println("Incoming vector is : "+small);
float min=0,min1=0,min2=0,min3=0,pivot=0;
int outp=0;
for(i=0;i<6;i++)
{
if(small==dj[i+1])
{
if(cj1[i+1]>0 && cj2[i+1]>0 && cj3[i+1]>0)
{
min1=cj1[0]/cj1[i+1];
min2=cj2[0]/cj2[i+1];
min3=cj3[0]/cj3[i+1];
min=(min1<min2)?(min1<min3)?min1:min3:(min2<min3)?min2:min3;
}
else if(cj1[i+1]>0 && cj2[i+1]>0)
{
min1=cj1[0]/cj1[i+1];
min2=cj2[0]/cj2[i+1];
min=(min1<min2)?min1:min2;
}
else if(cj2[i+1]>0 && cj3[i+1]>0)
{
min2=cj2[0]/cj2[i+1];
min3=cj3[0]/cj3[i+1];
min=(min2<min3)?min2:min3;
}
else if(cj1[i+1]>0 && cj3[i+1]>0)
{
min1=cj1[0]/cj1[i+1];
min3=cj3[0]/cj3[i+1];
min=(min1<min3)?min1:min3;
}
else if(cj1[i+1]>0 && cj2[i+1]<=0 && cj3[i+1]<=0)
{
min1=cj1[0]/cj1[i+1];
min=min1;
}
else if(cj2[i+1]>0 && cj1[i+1]<=0 && cj3[i+1]<=0)
{
min2=cj2[0]/cj2[i+1];
min=min2;
}
else if(cj3[i+1]>0 && cj2[i+1]<=0 && cj1[i+1]<=0)
{
min3=cj3[0]/cj3[i+1];
min=min1;
}
if(min==min1)
{
pivot=cj1[i+1];
outp=0;
}
else if(min==min2)
{
pivot=cj2[i+1];
outp=1;
}
else if(min==min3)
{
pivot=cj3[i+1];
outp=2;
}
}
}
System.out.println("Outgoing vector is : "+min);
System.out.println("Pivot1 element is : "+pivot);
float pivot1=cj1[inp+1],pivot2=cj2[inp+1],pivot3=cj3[inp+1];
for(i=0;i<=6;i++)
{
if(outp==0)
{
sb[0]=x[inp];
cj1[i]=cj1[i]/pivot;
cj2[i]=cj2[i]-(cj1[i]*pivot2);
cj3[i]=cj3[i]-(cj1[i]*pivot3);
}
else if(outp==1)
{
sb[1]=x[inp];
cj2[i]=cj2[i]/pivot;
cj1[i]=cj1[i]-(cj2[i]*pivot1);
cj3[i]=cj3[i]-(cj2[i]*pivot3);
}
else if(outp==2)
{
sb[2]=x[inp];
cj3[i]=cj3[i]/pivot;
cj1[i]=cj1[i]-(cj3[i]*pivot1);
cj2[i]=cj2[i]-(cj3[i]*pivot2);
}
}
for(i=0;i<6;i++)
{
if(sb[0]==x[i])
cb1=cj[i];
if(sb[1]==x[i])
cb2=cj[i];
if(sb[2]==x[i])
cb3=cj[i];
}
}
}
}
}
}
Output : 1
Example of the Question.
Solve the LPP by simplex method.
Max Z = 3x1+2x2+5x3 [Object Function]
Subject To x1+2x2+x3<=430 [1st Set of Constant]
3x1+2x3<=460 [2nd Set of Constant]
x1+4x2<=420 [3nd Set of Constant]
x1,x2,x3>=0 [Non -ve restriction]
If question is Minimization problem, Then enter 'min'
If question is Maximization problem, Then enter 'max'
Enter what type of question, Minimize or Maximize :
max
If no of Set of Constant is 2 or no of equation is 2, Then enter '2'
If no of Set of Constant is 3 or no of equation is 3, Then enter '3'
Enter no of Set of Constant or no of equation is :
2
if Objective functon symble x1 or x2 or x3 then enter x1
if Objective functon symble x or y or z then enter x
Example Max Z = 3x+4y+7zthen enter x
Example Max Z = 3x1+2x2+5x3 then enter x1
Enter Objective functon symble :
x1
Example max Z = 4x1+5x2 then value of objective function value is 4 5
Example max Z = 3x1+2x2 then value of objective function value is 3 2
Enter value of objective function value
7 6
Enter 1st Set of Constant means question is x1 +x2 <=4 then enter 1 1 4
1 1 4
Enter 2st Set of Constant means question is x1 -x2 <=2 then enter 1 -1 2
2 1 6
step-1 (Standard form)
------- ------------------
Rewrite the constraint into equation by adding slack variables s1,s2. The standard form of LPP becames-
max z = 7x1 + 6x2 + 0s1 + 0s2
Subject to 1x1 + 1x2 + s1 = 4
2x1 + 1x2 + s2 = 6
x1,x2,s1,s2 >=0
step-2 (Matrix form)
AX=B
That is | 1 1 1 0 | | x1 | = | 4 |
| 2 1 0 1 | | x2 | = | 6 |
| s1 |
| s2 |
step-3 (To Find Initial Basic Feasible Solution)
Put x1 = x2 = 0
s1=4
s2=6
Initial Table
-------------
--------------------------------------------------------
| Cj | 7 | 6 | 0 | 0 |
| SB | CB XB | x1 | x2 | S1 | S2 |
--------------------------------------------------------
| s1 | 0 4.0 | 1.0 | 1.0 | 1.0 | 0.0 |
| s2 | 0 6.0 | 2.0 | 1.0 | 0.0 | 1.0 |
--------------------------------------------------------
| | zj=0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| |del j=zj-cj | -7.0 | -6.0 | 0.0 | 0.0 |
--------------------------------------------------------
Find incoming vector and outgoing vector.
Incoming vector is : -7.0
Outgoing vector is : 3.0
Pivot1 element is : 2.0
First Iteration
---------------
--------------------------------------------------------
| Cj | 7 | 6 | 0 | 0 |
| SB | CB XB | x1 | x2 | S1 | S2 |
--------------------------------------------------------
| s1 | 0 1.0 | 0.0 | 0.5 | 1.0 | -0.5 |
| x1 | 7 3.0 | 1.0 | 0.5 | 0.0 | 0.5 |
--------------------------------------------------------
| | zj=21.0 | 7.0 | 3.5 | 0.0 | 3.5 |
| |del j=zj-cj | 0.0 | -2.5 | 0.0 | 3.5 |
--------------------------------------------------------
Find incoming vector and outgoing vector.
Incoming vector is : -2.5
Outgoing vector is : 2.0
Pivot1 element is : 0.5
Second Iteration
----------------
--------------------------------------------------------
| Cj | 7 | 6 | 0 | 0 |
| SB | CB XB | x1 | x2 | S1 | S2 |
--------------------------------------------------------
| x2 | 6 2.0 | 0.0 | 1.0 | 2.0 | -1.0 |
| x1 | 7 2.0 | 1.0 | 0.0 | -1.0 | 1.0 |
--------------------------------------------------------
| | zj=26.0 | 7.0 | 6.0 | 5.0 | 1.0 |
| |del j=zj-cj | 0.0 | 0.0 | 5.0 | 1.0 |
--------------------------------------------------------
Since all zj-cj >=0,optimal basic feasible solution is obtained.
Max z=26.0,x1=2.0,x2=2.0.
Output : 2
Example of the Question.
Solve the LPP by simplex method.
Max Z = 3x1+2x2+5x3 [Object Function]
Subject To x1+2x2+x3<=430 [1st Set of Constant]
3x1+2x3<=460 [2nd Set of Constant]
x1+4x2<=420 [3nd Set of Constant]
x1,x2,x3>=0 [Non -ve restriction]
If question is Minimization problem, Then enter 'min'
If question is Maximization problem, Then enter 'max'
Enter what type of question, Minimize or Maximize :
max
If no of Set of Constant is 2 or no of equation is 2, Then enter '2'
If no of Set of Constant is 3 or no of equation is 3, Then enter '3'
Enter no of Set of Constant or no of equation is :
3
if Objective functon symble x1 or x2 or x3 then enter x1
if Objective functon symble x or y or z then enter x
Example Max Z = 3x+4y+7zthen enter x
Example Max Z = 3x1+2x2+5x3 then enter x1
Enter Objective functon symble :
x1
Example max Z = 7x1+12x2+4x3 then value of objective function value is 7 12 4
Example max Z = 3x1+2x2+5x3 then value of objective function value is 3 2 5
Enter value of objective function value
3 2 5
Enter 1st Set of Constant means question is x1 +2x2 +x3 <=430 then enter 1 2 1 430
1 2 1 430
Enter 2st Set of Constant means question is 3x1 +2x3 <=460 then enter 3 0 2 460
3 0 2 460
Enter 3rd Set of Constant means question is x1 +4x2 <=420 then enter 1 4 0 420
1 4 0 420
step-1 (Standard form)
------- ------------------
Rewrite the constraint into equation by adding slack variables s1,s2,s3. The standard form of LPP becames-
Max z = 3x1 + 2x2 + 5x3 + 0s1 + 0s2 + 0s3
Subject to 1x1 + 2x2 + 1x3 + s1 = 430
3x1 + 0x2 + 2x3 + s2 = 460
1x1 + 4x2 + 0x3 + s3 = 420
x1,x2,x3,s1,s2,s3 >=0
step-2 (Matrix form)
AX=B
That is | 1 2 1 1 0 0 | | x1 | = | 430 |
| 3 0 2 0 1 0 | | x2 | = | 460 |
| 1 4 0 0 0 1 | | x3 | = | 420 |
| s1 |
| s2 |
| s3 |
step-3 (To Find Initial Basic Feasible Solution)
Put x1 = x2 = x3 = 0
s1=430
s2=460
s3=420
Initial Table
-------------
------------------------------------------------------------------------
| Cj | 3 | 2 | 5 | 0 | 0 | 0 |
| SB | CB XB | x1 | x2 | x3 | S1 | S2 | S3 |
------------------------------------------------------------------------
| s1 | 0 430.0 | 1.0 | 2.0 | 1.0 | 1.0 | 0.0 | 0.0 |
| s2 | 0 460.0 | 3.0 | 0.0 | 2.0 | 0.0 | 1.0 | 0.0 |
| s3 | 0 420.0 | 1.0 | 4.0 | 0.0 | 0.0 | 0.0 | 1.0 |
------------------------------------------------------------------------
| | zj=0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| |del j=zj-cj | -3.0 | -2.0 | -5.0 | 0.0 | 0.0 | 0.0 |
------------------------------------------------------------------------
Find incoming vector and outgoing vector.
Incoming vector is : -5.0
Outgoing vector is : 230.0
Pivot1 element is : 2.0
First Iteration
---------------
------------------------------------------------------------------------
| Cj | 3 | 2 | 5 | 0 | 0 | 0 |
| SB | CB XB | x1 | x2 | x3 | S1 | S2 | S3 |
------------------------------------------------------------------------
| s1 | 0 200.0 | -0.5 | 2.0 | 0.0 | 1.0 | -0.5 | 0.0 |
| x3 | 5 230.0 | 1.5 | 0.0 | 1.0 | 0.0 | 0.5 | 0.0 |
| s3 | 0 420.0 | 1.0 | 4.0 | 0.0 | 0.0 | 0.0 | 1.0 |
------------------------------------------------------------------------
| | zj=1150.0 | 7.5 | 0.0 | 5.0 | 0.0 | 2.5 | 0.0 |
| |del j=zj-cj | 4.5 | -2.0 | 0.0 | 0.0 | 2.5 | 0.0 |
------------------------------------------------------------------------
Find incoming vector and outgoing vector.
Incoming vector is : -2.0
Outgoing vector is : 100.0
Pivot1 element is : 2.0
Second Iteration
----------------
------------------------------------------------------------------------
| Cj | 3 | 2 | 5 | 0 | 0 | 0 |
| SB | CB XB | x1 | x2 | x3 | S1 | S2 | S3 |
------------------------------------------------------------------------
| x2 | 2 100.0 | -0.25| 1.0 | 0.0 | 0.5 | -0.25| 0.0 |
| x3 | 5 230.0 | 1.5 | 0.0 | 1.0 | 0.0 | 0.5 | 0.0 |
| s3 | 0 20.0 | 2.0 | 0.0 | 0.0 | -2.0 | 1.0 | 1.0 |
------------------------------------------------------------------------
| | zj=1350.0 | 7.0 | 2.0 | 5.0 | 1.0 | 2.0 | 0.0 |
| |del j=zj-cj | 4.0 | 0.0 | 0.0 | 1.0 | 2.0 | 0.0 |
------------------------------------------------------------------------
Since all zj-cj >=0,optimal basic feasible solution is obtained.
Max z=1350.0,x1=0.0,x2=100.0,x3=230.0.
 by Using Java Program){kind=link}
0 Comments