# Simplex and Dual Simplex Method

Discussion in 'C' started by shabbir, Sep 9, 2008.

Joined:
Jul 12, 2004
Messages:
15,285
364
Trophy Points:
83
C Program to solves linear programming problem or LPP by "SIMPLEX" and "DUAL SIMPLEX" method.

### The code

Simplex Method Code
Code:
```#include <stdio.h>
#include <conio.h>
#define INFINITY 999
#define N 3
#define M 6
/************************************************************/
/***** Solves the LPP by "SIMPLEX" method i.e. by table *****/
/************************************************************/
void minimum(float *arr,int *arrminpos,int n);
/* Calculates the minimum valued position among the array arr having n elements. */
void display (float c[],float b[],float a[][M],int basic[]);
/* Display the table */
void displayframe(float c[M]);
/* Displays the frame of the table */
void calctemp(float *,float [][M],float [],int []);
/* Calculates Zj-Cj */
/*--------------------------------------------------------------------------*\
Cj        5        4        3        0        0        0        miniRatio
cB       xB        b        a1       a2       a3       a4       a5       a6    bi/aij
0        x4        5        2        3        1        1        0        0        2.5
0        x5        11       4        1        2        0        1        0        2.75
0        x6        8        3        4        2        0        0        1        2.66
----------------------------------------------------------------------------
Zj-Cj              -5       -4       -3       0        0        0
----------------------------------------------------------------------------
5        x1        2.5      1        1.5      0.5      0.5      0        0        5
0        x5        1        0        -5       0        -2       1        0        infinity
0        x6        105      0        -0.5     0.5      -1.5     0        1        1
----------------------------------------------------------------------------
Zj-Cj              0        3.5      -0.5     2.5      0        0
----------------------------------------------------------------------------
5        x1        2        1        2        0        2        0        -1
0        x5        1        0        -5       0        -2       1        0
3        x3        1        0        -1       1        -3       0        2
----------------------------------------------------------------------------
Zj-Cj              0        3        0        1        0        1
----------------------------------------------------------------------------
So the solution is :-
x1=2        x2=0        x3=1        x4=0        x5=1        x6=0
max(z) = 5*2 + 4*0 + 3*1 = 13.
\*--------------------------------------------------------------------------*/

void main()
{
float c[M]={{5},{4},{3},{0},{0},{0}};
/* Stores co-efficient of the objective function Max(z) */
float a[N][M]={
{2,3,1,1,0,0},
{4,1,2,0,1,0},
{3,4,2,0,0,1}
};
/* Stores the co-efficent of the constraints */
float b[N]={{5},{11},{8}};
/* Stores the values on RHS of constraints */
float temp[M]={{0},{0},{0},{0},{0},{0}};
/* Stores the values of Zj-Cj*/
int tempminpos;      /* Stores the minimum valued position
of {Zj-Cj} i.e. coming in variable */
float miniratio[N];   /* Stores the value of the ratio b[i]/a[i][j] */
int miniratiominpos;  /* Stores the minimum valued position of
b[i]/a[i][j] i.e. going out variable */
float key;          /* Stores the key element */
int gooutcol;        /* Stores the column number which goes out */
float z;          /* Stores the value of the objective function */
float x[M];        /* Stores the value of the variables */
int i,j;        /* Loop variables */
int basic[N];        /* Stores the basic variable */
int nonbasic[N];    /* Stores the non-basic variable */
int flag=0;      /* Terminating variable */
//clrscr();
/*** Initializing basic variables to 3,4,5 i.e. x4,x5,x6 ***/
for(i=0;i<N;i++)
{
basic[i]=(i+N);
nonbasic[i]=i;
}
printf("\nMax z = c1x1 + c2x2 + c3x3\n");
printf("\na11x1 + a12x2 + a13x3 <= b1\n");
printf("\na21x1 + a22x2 + a23x3 <= b2\n");
printf("\na31x1 + a31x2 + a32x3 <= b3\n");
printf("\nEnter values of ci's\n");
/*** Inputing requisite amount of data ***/
for(i=0;i<N;i++)
{
printf("\nEnter c[%d]\t",i+1);
scanf("%f",&c[i]);
}
printf("\nEnter values of ai's\n");
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
printf("\nEnter a[%d][%d]\t",i+1,j+1);
scanf("%f",&a[i][j]);
}
}
printf("\nEnter values of bi's\n");
for(i=0;i<N;i++)
{
printf("\nEnter b[%d]\t",i+1);
scanf("%f",&b[i]);
}
/*** Calculation for actual table ***/
while(flag==0)
{
z=0;
calctemp(temp,a,c,basic);
printf("\n");

/*** Determining the incoming column ***/

minimum(temp,&tempminpos,M);
display(c,b,a,basic);
printf("\nZj-Cj\t\t\t");
for(i=0;i<M;i++)
printf("%.4g\t",temp[i]);
printf("\n\n");
for(i=0;i<N;i++)
{
x[basic[i]]=b[i];
x[nonbasic[i]]=0;
printf("x[%d]=%g\n",basic[i]+1,b[i]);
}
for(i=0;i<N;i++)
z=z+c[i]*x[i];
printf("Max(z) = %g",z);

/*** Determining the outgoing column ***/

for(i=0;i<N;i++)
{
if(a[i][tempminpos]==0)
{
miniratio[i]=INFINITY;
continue;
}
if(a[i][tempminpos]<0)
{
miniratio[i]=INFINITY;
continue;
}
miniratio[i]=b[i]/a[i][tempminpos];
}
minimum(miniratio,&miniratiominpos,N);
for(i=0;i<N;i++)
if(miniratiominpos==i)
gooutcol=basic[i];
printf("\nComing in variable = X%d\t",tempminpos+1);
printf("Going out variable = X%d\n",gooutcol+1);

/*** Changing the basic and non-basic variable ***/

basic[miniratiominpos]=tempminpos;
nonbasic[tempminpos]=gooutcol;

/*** Performing the operations to bring similar expressions in
in-coming variable as out-going variable by row operations ***/

key=a[miniratiominpos][tempminpos];
b[miniratiominpos]=b[miniratiominpos]/key;
for(i=0;i<M;i++)
a[miniratiominpos][i]=a[miniratiominpos][i]/key;
for(i=0;i<N;i++)
{
if(miniratiominpos==i)
continue;
key=a[i][tempminpos];
for(j=0;j<M;j++)
{
a[i][j]=a[i][j]-a[miniratiominpos][j]*key;
}
b[i]=b[i]-b[miniratiominpos]*key;
}
getch();

/*** Terminating condition ***/

for(i=0;i<M;i++)
{
flag=1;
if(temp[i]<0)
{
flag=0;
break;
}
}
}
printf("\nPress any key to exit...\n");
getch();
}
void calctemp(float *temp,float a[N][M],float c[M],int basic[N])
{
int i,j;
for(i=0;i<M;i++)
{
temp[i]=0;
for(j=0;j<N;j++)
temp[i]=temp[i]+c[basic[j]]*a[j][i];
temp[i]=temp[i]-c[i];
}
}
void minimum(float *arr,int *arrminpos, int n)
{
int i;
float arrmin;
arrmin=arr[0];
*arrminpos=0;
for(i=0;i<n;i++)
if(arr[i]<arrmin)
{
arrmin=arr[i];
*arrminpos=i;
}
printf("\n%d\n",*arrminpos);
}
void display (float c[N],float b[N],float a[N][M],int basic[N])
{
int i,j;
displayframe(c);
for(i=0;i<N;i++)
{
printf("\n%.4g\tX%d\t%.4g\t",c[basic[i]],basic[i]+1,b[i]);
for(j=0;j<M;j++)
printf("%.4g\t",a[i][j]);
printf("\n");
}
}
void displayframe(float c[M])
{
printf("\t\tc[j]\t");
printf("%g\t%g\t%g\t%g\t%g\t%g\n",c[0],c[1],c[2],c[3],c[4],c[5]);
printf("\nc[B]\tB\tb\ta1\ta2\ta3\ta4\ta5\ta6\n");
}
```
Dual Simplex Method
Code:
```#include <stdio.h>
#include <conio.h>
#define INFINITY -999
#define N 10
#define M 20
/***************************************************/
/***** Solves the LPP by "DUAL SIMPLEX" method *****/
/***************************************************/
void minimum(float *arr,int *arrminpos,int n);
/* Calculates the minimum valued position among the array arr having n elements. */
void maximum(float *arr,int *arrminpos,int n);
/* Calculates the minimum valued position among the array arr having n elements. */
void display (float c[],float b[],float a[][M],int basic[]);
/* Display the table */
void displayframe(float c[M]);
/* Displays the frame of the table */
void calctemp(float *,float [][M],float [],int []);
/* Calculates Zj-Cj */

int countmaxzterms;
int constraint;

void main()
{
float c[M];
/* Stores co-efficient of the objective function Max(z) */
float a[N][M];    /* Stores the co-efficent of the constraints */
float b[N];      /* Stores the values on RHS of constraints */
float temp[M];    /* Stores the values of Zj-Cj*/
int bminpos;     /* Stores the minimum valued position
of {Zj-Cj} i.e. coming in variable */
float maxratio[M];   /* Stores the value of the ratio Zj-Cj/a[i][j] */
int maxratiomaxpos;  /* Stores the minimum valued position of
b[i]/a[i][j] i.e. going out variable */
float key;      /* Stores the key element */
int gooutcol;     /* Stores the column number which goes out */
int incomingcol;
float z;       /* Stores the value of the objective function */
float x[M];     /* Stores the value of the variables */
int i,j;      /* Loop variables */
int basic[N];     /* Stores the basic variable */
int flag=0;    /* Terminating variable */

/*** Initializing basic variables ***/

for(i=0;i<M;i++)
c[i]=x[i]=temp[i]=0;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
a[i][j]=0;

/*** Inputing requisite amount of data ***/

printf("\nEnter number of terms in objective function\n");
scanf("%d",&countmaxzterms);
printf("\nEnter the co-efficient\n");
for(i=0;i<countmaxzterms;i++)
scanf("%f",&c[i]);
printf("\nYou have entered the function as follows:-\n");
printf("\nMax z = ");
for(i=0;i<countmaxzterms;i++)
{
if(i==0)
printf("%g*x%d",c[i],i+1);
else
printf(" + %g*x%d",c[i],i+1);
}
printf("\nEnter number of constraint\n");
scanf("%d",&constraint);
printf("\nEnter the co-efficient of constraints\n");
for(i=0;i<constraint;i++)
for(j=0;j<countmaxzterms;j++)
scanf("%f",&a[i][j]);
for(i=0;i<constraint;i++)
a[i][j++]=1;
printf("\nEnter values of bi's\n");
for(i=0;i<constraint;i++)
scanf("%f",&b[i]);
for(i=0;i<countmaxzterms+constraint;i++)
basic[i]=(i+countmaxzterms);
printf("\nYou have entered the function as follows:-\n");
for(i=0;i<constraint;i++)
{
for(j=0;j<countmaxzterms;j++)
{
if(j==0)
printf(" %g*x%d ",a[i][j],j+1);
else
printf(" + %g*x%d ",a[i][j],j+1);
}
printf(" <= %g\n",b[i]);
}
getch();

/*** Calculation for actual table ***/

do
{

/*** Terminating condition ***/

for(i=0;i<constraint;i++)
{
flag=1;
if(b[i]<=0)
{
flag=0;
break;
}
}

z=0;
calctemp(temp,a,c,basic);
printf("\n");

display(c,b,a,basic);
printf("\n\tZj-Cj\t\t");
for(i=0;i<constraint+countmaxzterms;i++)
printf("%0.3g\t",temp[i]);
printf("\n\n");

/*** Determining the outgoing column ***/

minimum(b,&bminpos,constraint);
gooutcol=basic[bminpos];

/*** Determining the incoming column ***/
for(i=0;i<M;i++)
maxratio[i]=INFINITY;

for(i=0;i<constraint+countmaxzterms;i++)
{
if(a[bminpos][i]==0)
{
maxratio[i]=INFINITY;
continue;
}
if(a[bminpos][i]>0)
{
maxratio[i]=INFINITY;
continue;
}
maxratio[i]=temp[i]/a[bminpos][i];
}
maximum(maxratio,&maxratiomaxpos,2*constraint);
incomingcol=maxratiomaxpos;
for(i=0;i<constraint+countmaxzterms;i++)
x[i]=0;
for(i=0;i<constraint;i++)
{
x[basic[i]]=b[i];
printf("x[%d]=%0.3g\n",basic[i]+1,b[i]);
}
for(i=0;i<constraint;i++)
z=z+c[i]*x[i];
printf("Max(z) = %g",z);
printf("\nComing in variable = X%d\t",incomingcol+1);
printf("Going out variable = X%d\n",gooutcol+1);

/*** Changing the basic and non-basic variable ***/

basic[bminpos]=incomingcol;

/*** Performing the operations to bring similar expressions in
in-coming variable as out-going variable by row operations ***/

key=a[bminpos][incomingcol];
b[bminpos]=b[bminpos]/key;
for(i=0;i<constraint+countmaxzterms;i++)
a[bminpos][i]=a[bminpos][i]/key;
for(i=0;i<constraint;i++)
{
if(bminpos==i)
continue;
key=a[i][incomingcol];
for(j=0;j<(constraint+countmaxzterms);j++)
a[i][j]=a[i][j]-a[bminpos][j]*key;
b[i]=b[i]-b[bminpos]*key;
}
getch();

}while(flag==0);

printf("\nPress any key to exit...\n");
getch();
}
void calctemp(float *temp,float a[N][M],float c[M],int basic[N])
{
int i,j;
for(i=0;i<constraint+countmaxzterms;i++)
{
temp[i]=0;
for(j=0;j<constraint;j++)
temp[i]=temp[i]+c[basic[j]]*a[j][i];
temp[i]=temp[i]-c[i];
}
}
void maximum(float *arr,int *arrmaxpos, int n)
{
int i;
int arrmax;
arrmax=arr[0];
*arrmaxpos=0;
for(i=0;i<n;i++)
if(arr[i]>arrmax)
{
arrmax=arr[i];
*arrmaxpos=i;
}
}

void minimum(float *arr,int *arrminpos, int n)
{
int i;
int arrmin;
arrmin=arr[0];
*arrminpos=0;
for(i=0;i<n;i++)
if(arr[i]<arrmin)
{
arrmin=arr[i];
*arrminpos=i;
}
}
void display (float c[N],float b[N],float a[N][M],int basic[N])
{
int i,j;
displayframe(c);
for(i=0;i<constraint;i++)
{
printf("\n%0.3g\tX%d\t%0.3g\t",c[basic[i]],basic[i]+1,b[i]);
for(j=0;j<constraint+countmaxzterms;j++)
printf("%0.3g\t",a[i][j]);
printf("\n");
}
}
void displayframe(float c[M])
{
int i;
printf("\t\tc[j]\t");
for(i=0;i<constraint+countmaxzterms;i++)
printf("%0.2g\t",c[i]);
printf("\n");
printf("\nc[B]\tB\tb\t");
for(i=0;i<constraint+countmaxzterms;i++)
printf("a[%d]\t",i+1);
printf("\n");
}```

2. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,012
203
Trophy Points:
0
Occupation:
Senior Support Engineer
Location:
England
What's an LPP? (Yes I did try Googling it, also tried "lpp simplex duplex" but still no clue).

shabbir likes this.

Joined:
Jul 12, 2004
Messages:
15,285
364
Trophy Points:
83
Linear programming problem.

Joined:
Jul 12, 2004
Messages:
15,285
364
Trophy Points:
83

Joined:
Jul 12, 2004
Messages:
15,285
364
Trophy Points:
83
6. ### BlastNew Member

Joined:
Apr 21, 2011
Messages:
1
0
Trophy Points:
0
I have not tried it yet but if it works it is perfect dude. Thanks for your work.

7. ### mathewhogardBanned

Joined:
Oct 27, 2010
Messages:
45
1
Trophy Points:
0
Location:
Delhi
Great. Keep sharing this type of information.

8. ### juliaandrewsNew Member

Joined:
May 12, 2011
Messages:
25
0
Trophy Points:
0
Thanks for great sharing.

9. ### MatBarNew Member

Joined:
Nov 15, 2012
Messages:
2
0
Trophy Points:
0
Hello,

thank you for your work shabbir,
I have some questions

I have LPP like this and i should solve this with dual simplex

min(9x1+9x2)
2x1 + x2 >= 14
x1 + 2x2 >= 10
x1>= 0 , x2>= 0

With your program iam getting resoults like this:

iv.pl/viewer.php?file=85574096140881554094.jpg

and iam not sure if its ok?
With my second java program its showing result = 72
and with my paper calculations its also showing me 72 result

Joined:
Jul 12, 2004
Messages:
15,285
364
Trophy Points:
83
MatBar, to be very honest this has been done by me almost 5 years back and so very difficult to suggest you what could be the issue straight away but if you are getting 72 on paper and by other Java program as well then I would agree that there may be issue in my code.

11. ### MatBarNew Member

Joined:
Nov 15, 2012
Messages:
2
0
Trophy Points:
0
Esh thats shame u cant help me,
but still thanks for response,

Joined:
May 18, 2013
Messages:
1