Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Simplex and Dual Simplex Method (http://www.go4expert.com/articles/simplex-dual-simplex-method-t13660/)

shabbir 9Sep2008 14:17

Simplex and Dual Simplex Method
 
C Program to solves linear programming problem or LPP by "SIMPLEX" and "DUAL SIMPLEX" method.

The code



Simplex Method Code
Code: C

#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: C

#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");
}


xpi0t0s 9Sep2008 15:07

Re: Simplex and Dual Simplex Method
 
What's an LPP? (Yes I did try Googling it, also tried "lpp simplex duplex" but still no clue).

shabbir 9Sep2008 18:43

Re: Simplex and Dual Simplex Method
 
Quote:

Originally Posted by xpi0t0s
What's an LPP? (Yes I did try Googling it, also tried "lpp simplex duplex" but still no clue).

Linear programming problem.

shabbir 2Oct2008 21:42

Re: Simplex and Dual Simplex Method
 
Nominated for article of the month for September 2008

shabbir 17Oct2008 09:15

Re: Simplex and Dual Simplex Method
 
Start Voting for article of the month for September 2008

Blast 22Apr2011 03:45

Re: Simplex and Dual Simplex Method
 
I have not tried it yet but if it works it is perfect dude. Thanks for your work.

mathewhogard 28Apr2011 17:00

Re: Simplex and Dual Simplex Method
 
Great. Keep sharing this type of information.

juliaandrews 19May2011 17:56

Re: Simplex and Dual Simplex Method
 
Thanks for great sharing.

MatBar 16Nov2012 01:10

Re: Simplex and Dual Simplex Method
 
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

shabbir 16Nov2012 09:07

Re: Simplex and Dual Simplex Method
 
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.


All times are GMT +5.5. The time now is 14:03.