Solved

# JavaScript Simplex Problem(s)

Posted on 2012-03-21
719 Views
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.

-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
``````

**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>
``````

**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;
}
}
//--------------------------------------------------
``````
0
Question by:JustinW
• 3

LVL 1

Author Comment

I guess its really not.
0

LVL 75

Expert Comment

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;
}
}
//--------------------------------------------------
``````
0

LVL 31

Expert Comment

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

JustinW earned 0 total points
@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

found an easy to work with, stand alone library to do what I wanted that I converted
0

## Featured Post

### Suggested Solutions

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…