Solved

JavaScript Simplex Problem(s)

Posted on 2012-03-21
7
719 Views
Last Modified: 2012-03-28
I'm trying to create a simple web application that solves (relatively) simple Linear Programming problems through the Two Phase Simplex Method. I've built a class in JavaScript to handle this functionality and checking its results against the tool found here:

http://www.zweigmedia.com/RealWorld/simplex.html

At the moment though, its not working and I'm stuck. Below is the problem that I'm hanging up on, and attached is an excel document showing what should happen (table by table).

If anyone has any suggestions, answers, or knows of a pre-existing library that can solve this I would be ever grateful.
I am all ears at this point.

Thanks in advance,
-JWW


**Problem for Web Site
minimize p = 99x1 + 99x2 + 99x3 + 1x4 

0.229744x1 + 0x2 + 0x3 + 0.200913x4>= 62.5
0.025641x1 + 0x2 + 0.236047x3 + 0.118265x4>= 37.5
0.00923077x1 + 1x2 + 0.0296512x3 + 0.149772x4>= 11.1111111111111
0.229744x1 + 0x2 + 0x3 + 0.200913x4<= 62.5
0.025641x1 + 0x2 + 0.236047x3 + 0.118265x4<= 37.5
0.00923077x1 + 1x2 + 0.0296512x3 + 0.149772x4<= 11.1111111111111

Open in new window



**Implementation
<script type="text/javascript">  
  z = [
    [0.229744,0,0,0.200913,62.5,1],
    [0.025641,0,0.236047,0.118265,37.5,1],
    [0.00923077,1,0.0296512,0.149772,11.1111111111111,1],
    [0.229744,0,0,0.200913,62.5,-1],
    [0.025641,0,0.236047,0.118265,37.5,-1],
    [0.00923077,1,0.0296512,0.149772,11.1111111111111,-1],
    [99,99,99,1,0,-1],
  ];
  
  b = new clsSIMPLEX;
  c = b.SOLVE(z);
  
  for(x in b.PostMortem)
  {
    document.write(b.PostMortem[x]);
  }
  for(x in b.Pivots)
  {
    document.write(b.Pivots[x] + "<br/>");
  }
</script>

Open in new window



**Simplex Class
//**************************************************
//Function:     clsSIMPLEX
//Description:  JavaScript Class object to Solve Linear
//              inequalities
//
//Caveats:
//  1.) ALL Variables need a coeffecient on
//      ALL lines. If there is no variable, it
//      STILL NEEDS A ZERO (0)
//
//  2.) Greater than / less than signs
//      are in the Far Right column
//
//       1 = >=
//      -1 = <=
//
//Example
//Maximize p = .5x + 3y + z + 4w subject to
//                  x +  y + z + w <= 40
//                 2x +  y - z - w >= 10
//                    -  y       w >= 10
//
//         z = [[1,1,1,1,40,-1],
//              [2,1,-1,-1,10,1],
//              [0,-1,0,1,10,1],
//              [-.5,-3,-1,-4,0,1]];
//
//         b = new clsSIMPLEX
//         c = b.SOLVE(z)
//**************************************************

function clsSIMPLEX()
{

		this.PostMortem = [];
		this.Pivots = [];

		this.SOLVE = function(TBL_0)
		{
			var vFIN;                                       				//Final 'Results' Table
			var lROW = 0;                                   				//variable Row to Be Pivoted On
			var lCOL = 0;                                   				//variable Column to Be Pivoted On
			var oldWDTH = TBL_0[0].length - 1; 
			var oldLNGT = TBL_0.length - 1;
			var newWDTH = 0;
			

			
			vFIN = TBL_BLD(TBL_0);        									//Build the Tableaux
				newWDTH = vFIN[0].length;									//Keep Table's Wdth
				this.PostMortem.push(this.EchoTable(vFIN));					//Store Table's Result

			
				
			//Phase 1  

		  for (i = 0; i < TBL_0.length - 1 ; i++)
				{
				   
					if (TBL_0[i][oldWDTH] == 1)
						{
							lCOL = P1_ColFind(i, vFIN);					//This is the Column to Pivot On
							lROW = GetPivotRow(lCOL, vFIN);         	//This is the Row to Pivot On         
							PIVOT(lROW, lCOL, vFIN);
							this.Pivots.push(['1' , lROW, lCOL]);
							this.PostMortem.push(this.EchoTable(vFIN));		//Store Table's Result
						}
						
				}

				//Phase 2
			while(P2_ColFind(vFIN)!=-1)
					{
						lCOL = P2_ColFind(vFIN);
						lROW = GetPivotRow(lCOL, vFIN);
						PIVOT(lROW,lCOL,vFIN);
						
						this.Pivots.push(['2' , lROW, lCOL]);
						
						this.PostMortem.push(this.EchoTable(vFIN));			//Store Table's Result
				   }

		  
		}


		//**************************************************
		//Function:    DimArray
		//Args:        D1,D2
		//
		//Description: Create a blank 2d Array that is
		//             D1 tall. D2 exists to make the function
		//             act like a VBA array (eg var(1 to 100, 1 to 10))
		//**************************************************
		var DimArray = function(D1,D2)
		//-------------------------------------------------
		   {
			var arr = [[0][0]];                           //1.) Instantiate a new 2d Array
			var i = 0;

			   for (i=0; i<D1; i++)
				   {arr[i] = [];}                         //2.) For every element in the 1st
			   return arr;                                //    dimension; add a blank array
		   }
		//--------------------------------------------------


		//**************************************************
		//Function:    PivotRow
		//Args:        lCOL = Column to Search
		//             xARR = Array Housing it all
		//
		//Description: Function to find the pivot
		//             row by looking for the smallest
		//             ratio of RHS / Current Column
		//             where the current column > 0
		//**************************************************

			var GetPivotRow = function (lCOL, xARR)
			{
				   var tmp=1000000;
				   var lLNG = xARR.length-1;
				   var lWDE = xARR[0].length-1;
				   var lROW = 0; var j = 0;
				   for (j = 0; j < lLNG; j++)
					   {
							if((xARR[j][lCOL]>0) && (xARR[j][lWDE] > 0))
								{
									if((xARR[j][lWDE]/xARR[j][lCOL])<tmp)
										{
											tmp = (xARR[j][lWDE]/xARR[j][lCOL]);
											lROW = j;
										}
								}
					   }
			return lROW;
			}
		//**************************************************
		//Function:    	P1_ColFind
		//Args:		   	lROW = Row To Scan
		//			   	vARR = Simplex Tableaux
		//
		//Description: 	Scan the current row, left to right
		//			   	looking for the largest positive number
		//				and return it's column.
		//
		//				If nothing is found, it returns -1
		//**************************************************
			var P1_ColFind = function(lROW, vARR)
			{
				var iTMP = -1;
				var tst = 0;
				for (var i = 0; i < vARR[lROW].length - 1; i++)
					{
						if (vARR[lROW][i]>tst)
							{
								tst = vARR[lROW][i];
								iTMP = i;
							}
					}
				return iTMP;
			}


		//**************************************************
		//Function:    	P2_ColFind
		//Args:		   	xARR = Simplex Tableaux
		//
		//Description: 	Scan the bottom row, left to right
		//			   	looking for the largest negative number
		//				and return it's column.
		//
		//				If nothing is found, it returns -1
		//**************************************************
			var P2_ColFind = function(xARR)
			   {
				   var tmp=1;
				   var iCOL = -1;
				   var lLNG = xARR.length -1;
				   var lWDE = xARR[lLNG].length -1;

				   for (var i=0; i<lWDE ; i++)
					   {                                                //LOOP START
						  if ((xARR[lLNG][i] < 0) && (xARR[lLNG][i]< tmp))
						   {
							   iCOL = i;
							   tmp = xARR[lLNG][i];
						   }
					   }
			   return iCOL;
			   }


		//**************************************************
		//Function:     TBL_BLD
		//Description:  Convert an Array into the initial tableaux
		//
		//Example
		//         z = [[1,1,1,1,40,-1],
		//              [2,1,-1,-1,10,1],
		//              [0,-1,0,1,10,1],
		//              [.5,3,1,4,0,0]];
		//
		//         b = TBL_BLD(z)
		//**************************************************
		var TBL_BLD = function(x)
		//--------------------------------------------------
		   {
		   var old_HI = x.length;
		   var old_WD = x[0].length;
		   var new_HI = old_HI;
		   var new_WD = old_WD + old_HI;
		   var i = 0; var j = 0;

		   var new_arr = DimArray(new_HI, new_WD);

		   for (i=0;i<new_HI;i++)
			   {
					for(j=0;j<new_WD-1;j++)
						{
							if(j<old_WD - 2)                			//1.) Move all Variables
							{                               			//      from the 1st Array
								new_arr[i][j]               			//      to the new array
									=x[i][j];               			//      
							}
							else if(j==old_WD -2 + i)       			//2) Convert Gtr Thn from
							{                               			//     1 to -1; and vice versa
								new_arr[i][j]               			//     and place slack variables
									= (x[i][old_WD-1])*-1;  			//     in the diagnol
							}
							else if(j==new_WD-2)            			//3) Move the equity constraints
							{                               			//   to the far right of the table
								new_arr[i][new_WD-2]
								   =x[i][old_WD-2];
							}
							else
							{
								new_arr[i][j]=0;            			//4) Otherwise; fill the new table
							}                               			//   with a 0
						}
			   }
			return new_arr;
			}
		//--------------------------------------------------


		//**************************************************
		//Function:     PIVOT
		//Description:  Perform Row operations on a tableaux
		//              given a Row, Column, and Array to Pivot on
		//Args:         lROW = Pivot Row
		//              lCOL = Pivot Col
		//              xARR = Targte Array
		//**************************************************

		//--------------------------------------------------
		var PIVOT = function(lROW, lCOL, xARR)
			{
				var tmp = xARR[lROW][lCOL]                              //1.)Get the value at the
																		//   pivot location and store
																		//   in the tmp Variable
				var lLNG = xARR.length -1;
				var lWDE = xARR[lLNG].length -1;

				for (var i=0;i<=lWDE;i++)                               //2.) Divide everything in the
					{xARR[lROW][i]=xARR[lROW][i]/tmp;}                  //    pivot row by the Pivot Value
																		//    changing the value of the pivot
																		//    to 1.
				tmp = 0;

																		//3.) Place Zeros (0's) above
																		//    the pivot element
				for (i = 0; i<=lLNG; i++)
					{
						if(i!=lROW)                                     //3a) Don't touch the pivot row
							{
								tmp = -xARR[i][lCOL];                   //3b) Set tmp = NEGATIVE [Current Row][Pivot Column]
								for (var j=0;j<=lWDE;j++)                   //3c) Loop through all elements in current row
									{
										xARR[i][j] = tmp *              //3d) This thing...
											xARR[lROW][j] +             //
												xARR[i][j];
									}
							}
					}
			}
		//--------------------------------------------------


		//**************************************************
		//Function:     EchoTable
		//Description:  Store a 2d array as an HTML Table in
		//				a string
		//              
		//Args:         tbl = 2d Array
		//**************************************************

		//--------------------------------------------------
			
			
		this.EchoTable = function(tbl)
			{
				var s = '<table><tbody>';
				for(x in tbl)
				{
					s += '<tr>';
					for(y in tbl[x])
					{
						s += '<td>' + tbl[x][y] + '</td>';
					}
					s += '</tr>'
				}
				s += '</tbody></table><br /><br /><br />';
				
				return s;
			}
}
//--------------------------------------------------

Open in new window

0
Comment
Question by:JustinW
  • 3
7 Comments
 
LVL 1

Author Comment

by:JustinW
Comment Utility
I guess its really not.
Sorry about that.
0
 
LVL 75

Expert Comment

by:Michel Plungjan
Comment Utility
I think this is easier to read
//**************************************************
//Function:   clsSIMPLEX
//Description:  JavaScript Class object to Solve Linear
//  inequalities
//
//Caveats:
//  1.) ALL Variables need a coeffecient on
//  ALL lines. If there is no variable, it
//  STILL NEEDS A ZERO (0)
//
//  2.) Greater than / less than signs
//  are in the Far Right column
//
//   1 = >=
//  -1 = <=
//
//Example
//Maximize p = .5x + 3y + z + 4w subject to
//  x +  y + z + w <= 40
//   2x +  y - z - w >= 10
//  -  y   w >= 10
//
//   z = [[1,1,1,1,40,-1],
//  [2,1,-1,-1,10,1],
//  [0,-1,0,1,10,1],
//  [-.5,-3,-1,-4,0,1]];
//
//   b = new clsSIMPLEX
//   c = b.SOLVE(z)
//**************************************************

function clsSIMPLEX() {

    this.PostMortem = [];
    this.Pivots = [];

    this.SOLVE = function(TBL_0) {
        var vFIN; //Final 'Results' Table
        var lROW = 0; //variable Row to Be Pivoted On
        var lCOL = 0; //variable Column to Be Pivoted On
        var oldWDTH = TBL_0[0].length - 1;
        var oldLNGT = TBL_0.length - 1;
        var newWDTH = 0;



        vFIN = TBL_BLD(TBL_0); //Build the Tableaux
        newWDTH = vFIN[0].length; //Keep Table's Wdth
        this.PostMortem.push(this.EchoTable(vFIN)); //Store Table's Result


        //Phase 1  
        for (i = 0; i < TBL_0.length - 1; i++) {

            if (TBL_0[i][oldWDTH] == 1) {
                lCOL = P1_ColFind(i, vFIN); //This is the Column to Pivot On
                lROW = GetPivotRow(lCOL, vFIN); //This is the Row to Pivot On   
                PIVOT(lROW, lCOL, vFIN);
                this.Pivots.push(['1', lROW, lCOL]);
                this.PostMortem.push(this.EchoTable(vFIN)); //Store Table's Result
            }

        }

        //Phase 2
        while (P2_ColFind(vFIN) != -1) {
            lCOL = P2_ColFind(vFIN);
            lROW = GetPivotRow(lCOL, vFIN);
            PIVOT(lROW, lCOL, vFIN);

            this.Pivots.push(['2', lROW, lCOL]);

            this.PostMortem.push(this.EchoTable(vFIN)); //Store Table's Result
        }


    }


    //**************************************************
    //Function:  DimArray
    //Args:  D1,D2
    //
    //Description: Create a blank 2d Array that is
    //   D1 tall. D2 exists to make the function
    //   act like a VBA array (eg var(1 to 100, 1 to 10))
    //**************************************************
    var DimArray = function(D1, D2)
    //-------------------------------------------------
    {
        var arr = [[0][0]]; //1.) Instantiate a new 2d Array
        var i = 0;

        for (i = 0; i < D1; i++) {
            arr[i] = [];
        } //2.) For every element in the 1st
        return arr; //  dimension; add a blank array
    }
    //--------------------------------------------------

    //**************************************************
    //Function:  PivotRow
    //Args:  lCOL = Column to Search
    //   xARR = Array Housing it all
    //
    //Description: Function to find the pivot
    //   row by looking for the smallest
    //   ratio of RHS / Current Column
    //   where the current column > 0
    //**************************************************
    var GetPivotRow = function(lCOL, xARR) {
        var tmp = 1000000;
        var lLNG = xARR.length - 1;
        var lWDE = xARR[0].length - 1;
        var lROW = 0;
        var j = 0;
        for (j = 0; j < lLNG; j++) {
            if ((xARR[j][lCOL] > 0) && (xARR[j][lWDE] > 0)) {
                if ((xARR[j][lWDE] / xARR[j][lCOL]) < tmp) {
                    tmp = (xARR[j][lWDE] / xARR[j][lCOL]);
                    lROW = j;
                }
            }
        }
        return lROW;
    }
    //**************************************************
    //Function:  P1_ColFind
    //Args:   lROW = Row To Scan
    //   vARR = Simplex Tableaux
    //
    //Description:   Scan the current row, left to right
    //   looking for the largest positive number
    //  and return it's column.
    //
    //  If nothing is found, it returns -1
    //**************************************************
    var P1_ColFind = function(lROW, vARR) {
        var iTMP = -1;
        var tst = 0;
        for (var i = 0; i < vARR[lROW].length - 1; i++) {
            if (vARR[lROW][i] > tst) {
                tst = vARR[lROW][i];
                iTMP = i;
            }
        }
        return iTMP;
    }


    //**************************************************
    //Function:  P2_ColFind
    //Args:   xARR = Simplex Tableaux
    //
    //Description:   Scan the bottom row, left to right
    //   looking for the largest negative number
    //  and return it's column.
    //
    //  If nothing is found, it returns -1
    //**************************************************
    var P2_ColFind = function(xARR) {
        var tmp = 1;
        var iCOL = -1;
        var lLNG = xARR.length - 1;
        var lWDE = xARR[lLNG].length - 1;

        for (var i = 0; i < lWDE; i++) { //LOOP START
            if ((xARR[lLNG][i] < 0) && (xARR[lLNG][i] < tmp)) {
                iCOL = i;
                tmp = xARR[lLNG][i];
            }
        }
        return iCOL;
    }


    //**************************************************
    //Function:   TBL_BLD
    //Description:  Convert an Array into the initial tableaux
    //
    //Example
    //   z = [[1,1,1,1,40,-1],
    //  [2,1,-1,-1,10,1],
    //  [0,-1,0,1,10,1],
    //  [.5,3,1,4,0,0]];
    //
    //   b = TBL_BLD(z)
    //**************************************************
    var TBL_BLD = function(x)
    //--------------------------------------------------
    {
        var old_HI = x.length;
        var old_WD = x[0].length;
        var new_HI = old_HI;
        var new_WD = old_WD + old_HI;
        var i = 0;
        var j = 0;

        var new_arr = DimArray(new_HI, new_WD);

        for (i = 0; i < new_HI; i++) {
            for (j = 0; j < new_WD - 1; j++) {
                if (j < old_WD - 2) //1.) Move all Variables
                { //  from the 1st Array
                    new_arr[i][j] //  to the new array
                    = x[i][j]; //  
                }
                else if (j == old_WD - 2 + i) //2) Convert Gtr Thn from
                { //   1 to -1; and vice versa
                    new_arr[i][j] //   and place slack variables
                    = (x[i][old_WD - 1]) * -1; //   in the diagnol
                }
                else if (j == new_WD - 2) //3) Move the equity constraints
                { //   to the far right of the table
                    new_arr[i][new_WD - 2] = x[i][old_WD - 2];
                }
                else {
                    new_arr[i][j] = 0; //4) Otherwise; fill the new table
                } //   with a 0
            }
        }
        return new_arr;
    }
    //--------------------------------------------------

    //**************************************************
    //Function:   PIVOT
    //Description:  Perform Row operations on a tableaux
    //  given a Row, Column, and Array to Pivot on
    //Args:   lROW = Pivot Row
    //  lCOL = Pivot Col
    //  xARR = Targte Array
    //**************************************************
    //--------------------------------------------------
    var PIVOT = function(lROW, lCOL, xARR) {
        var tmp = xARR[lROW][lCOL] //1.)Get the value at the
        //   pivot location and store
        //   in the tmp Variable
        var lLNG = xARR.length - 1;
        var lWDE = xARR[lLNG].length - 1;

        for (var i = 0; i <= lWDE; i++) //2.) Divide everything in the
        {
            xARR[lROW][i] = xARR[lROW][i] / tmp;
        } //  pivot row by the Pivot Value
        //  changing the value of the pivot
        //  to 1.
        tmp = 0;

        //3.) Place Zeros (0's) above
        //  the pivot element
        for (i = 0; i <= lLNG; i++) {
            if (i != lROW) //3a) Don't touch the pivot row
            {
                tmp = -xARR[i][lCOL]; //3b) Set tmp = NEGATIVE [Current Row][Pivot Column]
                for (var j = 0; j <= lWDE; j++) //3c) Loop through all elements in current row
                {
                    xARR[i][j] = tmp * //3d) This thing...
                    xARR[lROW][j] + //
                    xARR[i][j];
                }
            }
        }
    }
    //--------------------------------------------------

    //**************************************************
    //Function:   EchoTable
    //Description:  Store a 2d array as an HTML Table in
    //  a string
    //  
    //Args:   tbl = 2d Array
    //**************************************************
    //--------------------------------------------------

    this.EchoTable = function(tbl) {
        var s = '<table><tbody>';
        for (x in tbl) {
            s += '<tr>';
            for (y in tbl[x]) {
                s += '<td>' + tbl[x][y] + '</td>';
            }
            s += '</tr>'
        }
        s += '</tbody></table><br /><br /><br />';

        return s;
    }
}
//--------------------------------------------------

Open in new window

0
 
LVL 31

Expert Comment

by:GwynforWeb
Comment Utility
The problem your are attempting to code is considerable as the input is not in normal form. Going through the 2 phases ie (1) convert to normal form (2) Then solve, is a massive task.

I strongly suggest you look for pre-written code.
0
 
LVL 1

Accepted Solution

by:
JustinW earned 0 total points
Comment Utility
@Gwyn,

ended up doing exactly that. Found a bare-bones example in Java, and re-wrote to a class in JS. Seems to work well with the simple examples I've thrown at it so far, but its not friendly enough yet to easily test thouroughly.

Thanks,
JWW
0
 
LVL 1

Author Closing Comment

by:JustinW
Comment Utility
found an easy to work with, stand alone library to do what I wanted that I converted
0

Featured Post

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
Nothing in an HTTP request can be trusted, including HTTP headers and form data.  A form token is a tool that can be used to guard against request forgeries (CSRF).  This article shows an improved approach to form tokens, making it more difficult to…
The viewer will learn the basics of jQuery, including how to invoke it on a web page. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery.: (CODE)
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now