# JavaScript Simplex Problem(s)

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;
}
}
//--------------------------------------------------
``````
LVL 1
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Author Commented:
I guess its really not.
0
IT ExpertCommented:
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
Commented:
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
Author Commented:
@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

Experts Exchange Solution brought to you by