Simplex and Dual Simplex Method

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

  1. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    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. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    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.
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Linear programming problem.
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  6. Blast

    Blast New Member

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

    mathewhogard Banned

    Joined:
    Oct 27, 2010
    Messages:
    45
    Likes Received:
    1
    Trophy Points:
    0
    Location:
    Delhi
    Home Page:
    http://www.edreamztech.com/about_us.php
    Great. Keep sharing this type of information.
     
  8. juliaandrews

    juliaandrews New Member

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

    MatBar New Member

    Joined:
    Nov 15, 2012
    Messages:
    2
    Likes Received:
    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
     
  10. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    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. MatBar

    MatBar New Member

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

    omidrezak New Member

    Joined:
    May 18, 2013
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    hi.how can i change this code for 10 variable?? please.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice