#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <assert.h>
#define M 20
#define N 20
static const double epsilon = 1.0e-8;
int equal(double a, double b) { return fabs(a-b) < epsilon; }
typedef struct {
int m, n; // m=rows, n=columns, mat[m x n]
double mat[M][N];
} Tableau;
void nl(int k){ int j; for(j=0;j<k;j++) putchar('-'); putchar('\n'); }
void print_tableau(Tableau *tab, const char* mes) {
static int counter=0;
int i, j;
printf("\n%d. Tableau %s:\n", ++counter, mes);
nl(70);
printf("%-6s%5s", "col:", "b[i]");
for(j=1;j<tab->n; j++) { printf(" x%d,", j); } printf("\n");
for(i=0;i<tab->m; i++) {
if (i==0) printf("max:"); else
printf("b%d: ", i);
for(j=0;j<tab->n; j++) {
if (equal((int)tab->mat[i][j], tab->mat[i][j]))
printf(" %6d", (int)tab->mat[i][j]);
else
printf(" %6.2lf", tab->mat[i][j]);
}
printf("\n");
}
nl(70);
}
/* Example input file for read_tableau:
4 5
0 -0.5 -3 -1 -4
40 1 1 1 1
10 -2 -1 1 1
10 0 1 0 -1
*/
void read_tableau(Tableau *tab, const char * filename) {
int err, i, j;
FILE * fp;
fp = fopen(filename, "r" );
if( !fp ) {
printf("Cannot read %s\n", filename); exit(1);
}
memset(tab, 0, sizeof(*tab));
err = fscanf(fp, "%d %d", &tab->m, &tab->n);
if (err == 0 || err == EOF) {
printf("Cannot read m or n\n"); exit(1);
}
for(i=0;i<tab->m; i++) {
for(j=0;j<tab->n; j++) {
err = fscanf(fp, "%lf", &tab->mat[i][j]);
if (err == 0 || err == EOF) {
printf("Cannot read A[%d][%d]\n", i, j); exit(1);
}
}
}
printf("Read tableau [%d rows x %d columns] from file '%s'.\n",
tab->m, tab->n, filename);
fclose(fp);
}
void pivot_on(Tableau *tab, int row, int col) {
int i, j;
double pivot;
pivot = tab->mat[row][col];
assert(pivot>0);
for(j=0;j<tab->n;j++)
tab->mat[row][j] /= pivot;
assert( equal(tab->mat[row][col], 1. ));
for(i=0; i<tab->m; i++) { // foreach remaining row i do
double multiplier = tab->mat[i][col];
if(i==row) continue;
for(j=0; j<tab->n; j++) { // r[i] = r[i] - z * r[row];
tab->mat[i][j] -= multiplier * tab->mat[row][j];
}
}
}
// Find pivot_col = most negative column in mat[0][1..n]
int find_pivot_column(Tableau *tab) {
int j, pivot_col = 1;
double lowest = tab->mat[0][pivot_col];
for(j=1; j<tab->n; j++) {
if (tab->mat[0][j] < lowest) {
lowest = tab->mat[0][j];
pivot_col = j;
}
}
printf("Most negative column in row[0] is col %d = %g.\n", pivot_col, lowest);
if( lowest >= 0 ) {
return -1; // All positive columns in row[0], this is optimal.
}
return pivot_col;
}
// Find the pivot_row, with smallest positive ratio = col[0] / col[pivot]
int find_pivot_row(Tableau *tab, int pivot_col) {
int i, pivot_row = 0;
double min_ratio = -1;
printf("Ratios A[row_i,0]/A[row_i,%d] = [",pivot_col);
for(i=1;i<tab->m;i++){
double ratio = tab->mat[i][0] / tab->mat[i][pivot_col];
printf("%3.2lf, ", ratio);
if ( (ratio > 0 && ratio < min_ratio ) || min_ratio < 0 ) {
min_ratio = ratio;
pivot_row = i;
}
}
printf("].\n");
if (min_ratio == -1)
return -1; // Unbounded.
printf("Found pivot A[%d,%d], min positive ratio=%g in row=%d.\n",
pivot_row, pivot_col, min_ratio, pivot_row);
return pivot_row;
}
void add_slack_variables(Tableau *tab) {
int i, j;
for(i=1; i<tab->m; i++) {
for(j=1; j<tab->m; j++)
tab->mat[i][j + tab->n -1] = (i==j);
}
tab->n += tab->m -1;
}
void check_b_positive(Tableau *tab) {
int i;
for(i=1; i<tab->m; i++)
assert(tab->mat[i][0] >= 0);
}
// Given a column of identity matrix, find the row containing 1.
// return -1, if the column as not from an identity matrix.
int find_basis_variable(Tableau *tab, int col) {
int i, xi=-1;
for(i=1; i < tab->m; i++) {
if (equal( tab->mat[i][col],1) ) {
if (xi == -1)
xi=i; // found first '1', save this row number.
else
return -1; // found second '1', not an identity matrix.
} else if (!equal( tab->mat[i][col],0) ) {
return -1; // not an identity matrix column.
}
}
return xi;
}
void print_optimal_vector(Tableau *tab, char *message) {
int j, xi;
printf("%s at ", message);
for(j=1;j<tab->n;j++) { // for each column.
xi = find_basis_variable(tab, j);
if (xi != -1)
printf("x%d=%3.2lf, ", j, tab->mat[xi][0] );
else
printf("x%d=0, ", j);
}
printf("\n");
}
void simplex(Tableau *tab) {
int loop=0;
add_slack_variables(tab);
check_b_positive(tab);
print_tableau(tab,"Padded with slack variables");
while( ++loop ) {
int pivot_col, pivot_row;
pivot_col = find_pivot_column(tab);
if( pivot_col < 0 ) {
printf("Found optimal value=A[0,0]=%3.2lf (no negatives in row 0).\n",
tab->mat[0][0]);
print_optimal_vector(tab, "Optimal vector");
break;
}
printf("Entering variable x%d to be made basic, so pivot_col=%d.\n",
pivot_col, pivot_col);
pivot_row = find_pivot_row(tab, pivot_col);
if (pivot_row < 0) {
printf("unbounded (no pivot_row).\n");
break;
}
printf("Leaving variable x%d, so pivot_row=%d\n", pivot_row, pivot_row);
pivot_on(tab, pivot_row, pivot_col);
print_tableau(tab,"After pivoting");
print_optimal_vector(tab, "Basic feasible solution");
if(loop > 20) {
printf("Too many iterations > %d.\n", loop);
break;
}
}
}
Tableau tab = { 4, 5, { // Size of tableau [4 rows x 5 columns ]
{ 0.0 , -0.5 , -3.0 ,-1.0 , -4.0, }, // Max: z = 0.5*x + 3*y + z + 4*w,
{ 40.0 , 1.0 , 1.0 , 1.0 , 1.0, }, // x + y + z + w <= 40 .. b1
{ 10.0 , -2.0 , -1.0 , 1.0 , 1.0, }, // -2x - y + z + w <= 10 .. b2
{ 10.0 , 0.0 , 1.0 , 0.0 , -1.0, }, // y - w <= 10 .. b3
}
};
int main(int argc, char *argv[]){
if (argc > 1) { // usage: cmd datafile
read_tableau(&tab, argv[1]);
}
print_tableau(&tab,"Initial");
simplex(&tab);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1hdGguaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CgojZGVmaW5lIE0gMjAKI2RlZmluZSBOIDIwCgpzdGF0aWMgY29uc3QgZG91YmxlIGVwc2lsb24gICA9IDEuMGUtODsKaW50IGVxdWFsKGRvdWJsZSBhLCBkb3VibGUgYikgeyByZXR1cm4gZmFicyhhLWIpIDwgZXBzaWxvbjsgfQoKdHlwZWRlZiBzdHJ1Y3QgewogIGludCBtLCBuOyAvLyBtPXJvd3MsIG49Y29sdW1ucywgbWF0W20geCBuXQogIGRvdWJsZSBtYXRbTV1bTl07Cn0gVGFibGVhdTsKCnZvaWQgbmwoaW50IGspeyBpbnQgajsgZm9yKGo9MDtqPGs7aisrKSBwdXRjaGFyKCctJyk7IHB1dGNoYXIoJ1xuJyk7IH0KCnZvaWQgcHJpbnRfdGFibGVhdShUYWJsZWF1ICp0YWIsIGNvbnN0IGNoYXIqIG1lcykgewogIHN0YXRpYyBpbnQgY291bnRlcj0wOwogIGludCBpLCBqOwogIHByaW50ZigiXG4lZC4gVGFibGVhdSAlczpcbiIsICsrY291bnRlciwgbWVzKTsKICBubCg3MCk7CgogIHByaW50ZigiJS02cyU1cyIsICJjb2w6IiwgImJbaV0iKTsKICBmb3Ioaj0xO2o8dGFiLT5uOyBqKyspIHsgcHJpbnRmKCIgICAgeCVkLCIsIGopOyB9IHByaW50ZigiXG4iKTsKCiAgZm9yKGk9MDtpPHRhYi0+bTsgaSsrKSB7CiAgICBpZiAoaT09MCkgcHJpbnRmKCJtYXg6Iik7IGVsc2UKICAgIHByaW50ZigiYiVkOiAiLCBpKTsKICAgIGZvcihqPTA7ajx0YWItPm47IGorKykgewogICAgICBpZiAoZXF1YWwoKGludCl0YWItPm1hdFtpXVtqXSwgdGFiLT5tYXRbaV1bal0pKQogICAgICAgIHByaW50ZigiICU2ZCIsIChpbnQpdGFiLT5tYXRbaV1bal0pOwogICAgICBlbHNlCiAgICAgICAgcHJpbnRmKCIgJTYuMmxmIiwgdGFiLT5tYXRbaV1bal0pOwogICAgICB9CiAgICBwcmludGYoIlxuIik7CiAgfQogIG5sKDcwKTsKfQoKLyogRXhhbXBsZSBpbnB1dCBmaWxlIGZvciByZWFkX3RhYmxlYXU6CiAgICAgNCA1CiAgICAgIDAgICAtMC41ICAtMyAtMSAgLTQgCiAgICAgNDAgICAgMSAgICAgMSAgMSAgIDEgCiAgICAgMTAgICAtMiAgICAtMSAgMSAgIDEgCiAgICAgMTAgICAgMCAgICAgMSAgMCAgLTEgIAoqLwp2b2lkIHJlYWRfdGFibGVhdShUYWJsZWF1ICp0YWIsIGNvbnN0IGNoYXIgKiBmaWxlbmFtZSkgewogIGludCBlcnIsIGksIGo7CiAgRklMRSAqIGZwOwoKICBmcCAgPSBmb3BlbihmaWxlbmFtZSwgInIiICk7CiAgaWYoICFmcCApIHsKICAgIHByaW50ZigiQ2Fubm90IHJlYWQgJXNcbiIsIGZpbGVuYW1lKTsgZXhpdCgxKTsKICB9CiAgbWVtc2V0KHRhYiwgMCwgc2l6ZW9mKCp0YWIpKTsKICBlcnIgPSBmc2NhbmYoZnAsICIlZCAlZCIsICZ0YWItPm0sICZ0YWItPm4pOwogIGlmIChlcnIgPT0gMCB8fCBlcnIgPT0gRU9GKSB7CiAgICBwcmludGYoIkNhbm5vdCByZWFkIG0gb3IgblxuIik7IGV4aXQoMSk7CiAgfQogIGZvcihpPTA7aTx0YWItPm07IGkrKykgewogICAgZm9yKGo9MDtqPHRhYi0+bjsgaisrKSB7CiAgICAgIGVyciA9IGZzY2FuZihmcCwgIiVsZiIsICZ0YWItPm1hdFtpXVtqXSk7CiAgICAgIGlmIChlcnIgPT0gMCB8fCBlcnIgPT0gRU9GKSB7CiAgICAgICAgcHJpbnRmKCJDYW5ub3QgcmVhZCBBWyVkXVslZF1cbiIsIGksIGopOyBleGl0KDEpOwogICAgICB9CiAgICB9CiAgfQogIHByaW50ZigiUmVhZCB0YWJsZWF1IFslZCByb3dzIHggJWQgY29sdW1uc10gZnJvbSBmaWxlICclcycuXG4iLAogICAgdGFiLT5tLCB0YWItPm4sIGZpbGVuYW1lKTsKICBmY2xvc2UoZnApOwp9Cgp2b2lkIHBpdm90X29uKFRhYmxlYXUgKnRhYiwgaW50IHJvdywgaW50IGNvbCkgewogIGludCBpLCBqOwogIGRvdWJsZSBwaXZvdDsKCiAgcGl2b3QgPSB0YWItPm1hdFtyb3ddW2NvbF07CiAgYXNzZXJ0KHBpdm90PjApOwogIGZvcihqPTA7ajx0YWItPm47aisrKQogICAgdGFiLT5tYXRbcm93XVtqXSAvPSBwaXZvdDsKICBhc3NlcnQoIGVxdWFsKHRhYi0+bWF0W3Jvd11bY29sXSwgMS4gKSk7CgogIGZvcihpPTA7IGk8dGFiLT5tOyBpKyspIHsgLy8gZm9yZWFjaCByZW1haW5pbmcgcm93IGkgZG8KICAgIGRvdWJsZSBtdWx0aXBsaWVyID0gdGFiLT5tYXRbaV1bY29sXTsKICAgIGlmKGk9PXJvdykgY29udGludWU7CiAgICBmb3Ioaj0wOyBqPHRhYi0+bjsgaisrKSB7IC8vIHJbaV0gPSByW2ldIC0geiAqIHJbcm93XTsKICAgICAgdGFiLT5tYXRbaV1bal0gLT0gbXVsdGlwbGllciAqIHRhYi0+bWF0W3Jvd11bal07CiAgICB9CiAgfQp9CgovLyBGaW5kIHBpdm90X2NvbCA9IG1vc3QgbmVnYXRpdmUgY29sdW1uIGluIG1hdFswXVsxLi5uXQppbnQgZmluZF9waXZvdF9jb2x1bW4oVGFibGVhdSAqdGFiKSB7CiAgaW50IGosIHBpdm90X2NvbCA9IDE7CiAgZG91YmxlIGxvd2VzdCA9IHRhYi0+bWF0WzBdW3Bpdm90X2NvbF07CiAgZm9yKGo9MTsgajx0YWItPm47IGorKykgewogICAgaWYgKHRhYi0+bWF0WzBdW2pdIDwgbG93ZXN0KSB7CiAgICAgIGxvd2VzdCA9IHRhYi0+bWF0WzBdW2pdOwogICAgICBwaXZvdF9jb2wgPSBqOwogICAgfQogIH0KICBwcmludGYoIk1vc3QgbmVnYXRpdmUgY29sdW1uIGluIHJvd1swXSBpcyBjb2wgJWQgPSAlZy5cbiIsIHBpdm90X2NvbCwgbG93ZXN0KTsKICBpZiggbG93ZXN0ID49IDAgKSB7CiAgICByZXR1cm4gLTE7IC8vIEFsbCBwb3NpdGl2ZSBjb2x1bW5zIGluIHJvd1swXSwgdGhpcyBpcyBvcHRpbWFsLgogIH0KICByZXR1cm4gcGl2b3RfY29sOwp9CgovLyBGaW5kIHRoZSBwaXZvdF9yb3csIHdpdGggc21hbGxlc3QgcG9zaXRpdmUgcmF0aW8gPSBjb2xbMF0gLyBjb2xbcGl2b3RdCmludCBmaW5kX3Bpdm90X3JvdyhUYWJsZWF1ICp0YWIsIGludCBwaXZvdF9jb2wpIHsKICBpbnQgaSwgcGl2b3Rfcm93ID0gMDsKICBkb3VibGUgbWluX3JhdGlvID0gLTE7CiAgcHJpbnRmKCJSYXRpb3MgQVtyb3dfaSwwXS9BW3Jvd19pLCVkXSA9IFsiLHBpdm90X2NvbCk7CiAgZm9yKGk9MTtpPHRhYi0+bTtpKyspewogICAgZG91YmxlIHJhdGlvID0gdGFiLT5tYXRbaV1bMF0gLyB0YWItPm1hdFtpXVtwaXZvdF9jb2xdOwogICAgcHJpbnRmKCIlMy4ybGYsICIsIHJhdGlvKTsKICAgIGlmICggKHJhdGlvID4gMCAgJiYgcmF0aW8gPCBtaW5fcmF0aW8gKSB8fCBtaW5fcmF0aW8gPCAwICkgewogICAgICBtaW5fcmF0aW8gPSByYXRpbzsKICAgICAgcGl2b3Rfcm93ID0gaTsKICAgIH0KICB9CiAgcHJpbnRmKCJdLlxuIik7CiAgaWYgKG1pbl9yYXRpbyA9PSAtMSkKICAgIHJldHVybiAtMTsgLy8gVW5ib3VuZGVkLgogIHByaW50ZigiRm91bmQgcGl2b3QgQVslZCwlZF0sIG1pbiBwb3NpdGl2ZSByYXRpbz0lZyBpbiByb3c9JWQuXG4iLAogICAgICBwaXZvdF9yb3csIHBpdm90X2NvbCwgbWluX3JhdGlvLCBwaXZvdF9yb3cpOwogIHJldHVybiBwaXZvdF9yb3c7Cn0KCnZvaWQgYWRkX3NsYWNrX3ZhcmlhYmxlcyhUYWJsZWF1ICp0YWIpIHsKICBpbnQgaSwgajsKICBmb3IoaT0xOyBpPHRhYi0+bTsgaSsrKSB7CiAgICBmb3Ioaj0xOyBqPHRhYi0+bTsgaisrKQogICAgICB0YWItPm1hdFtpXVtqICsgdGFiLT5uIC0xXSA9IChpPT1qKTsKICB9CiAgdGFiLT5uICs9IHRhYi0+bSAtMTsKfQoKdm9pZCBjaGVja19iX3Bvc2l0aXZlKFRhYmxlYXUgKnRhYikgewogIGludCBpOwogIGZvcihpPTE7IGk8dGFiLT5tOyBpKyspCiAgICBhc3NlcnQodGFiLT5tYXRbaV1bMF0gPj0gMCk7Cn0KCi8vIEdpdmVuIGEgY29sdW1uIG9mIGlkZW50aXR5IG1hdHJpeCwgZmluZCB0aGUgcm93IGNvbnRhaW5pbmcgMS4KLy8gcmV0dXJuIC0xLCBpZiB0aGUgY29sdW1uIGFzIG5vdCBmcm9tIGFuIGlkZW50aXR5IG1hdHJpeC4KaW50IGZpbmRfYmFzaXNfdmFyaWFibGUoVGFibGVhdSAqdGFiLCBpbnQgY29sKSB7CiAgaW50IGksIHhpPS0xOwogIGZvcihpPTE7IGkgPCB0YWItPm07IGkrKykgewogICAgaWYgKGVxdWFsKCB0YWItPm1hdFtpXVtjb2xdLDEpICkgewogICAgICBpZiAoeGkgPT0gLTEpCiAgICAgICAgeGk9aTsgICAvLyBmb3VuZCBmaXJzdCAnMScsIHNhdmUgdGhpcyByb3cgbnVtYmVyLgogICAgICBlbHNlCiAgICAgICAgcmV0dXJuIC0xOyAvLyBmb3VuZCBzZWNvbmQgJzEnLCBub3QgYW4gaWRlbnRpdHkgbWF0cml4LgoKICAgIH0gZWxzZSBpZiAoIWVxdWFsKCB0YWItPm1hdFtpXVtjb2xdLDApICkgewogICAgICByZXR1cm4gLTE7IC8vIG5vdCBhbiBpZGVudGl0eSBtYXRyaXggY29sdW1uLgogICAgfQogIH0KICByZXR1cm4geGk7Cn0KCnZvaWQgcHJpbnRfb3B0aW1hbF92ZWN0b3IoVGFibGVhdSAqdGFiLCBjaGFyICptZXNzYWdlKSB7CiAgaW50IGosIHhpOwogIHByaW50ZigiJXMgYXQgIiwgbWVzc2FnZSk7CiAgZm9yKGo9MTtqPHRhYi0+bjtqKyspIHsgLy8gZm9yIGVhY2ggY29sdW1uLgogICAgeGkgPSBmaW5kX2Jhc2lzX3ZhcmlhYmxlKHRhYiwgaik7CiAgICBpZiAoeGkgIT0gLTEpCiAgICAgIHByaW50ZigieCVkPSUzLjJsZiwgIiwgaiwgdGFiLT5tYXRbeGldWzBdICk7CiAgICBlbHNlCiAgICAgIHByaW50ZigieCVkPTAsICIsIGopOwogIH0KICBwcmludGYoIlxuIik7Cn0KCnZvaWQgc2ltcGxleChUYWJsZWF1ICp0YWIpIHsKICBpbnQgbG9vcD0wOwogIGFkZF9zbGFja192YXJpYWJsZXModGFiKTsKICBjaGVja19iX3Bvc2l0aXZlKHRhYik7CiAgcHJpbnRfdGFibGVhdSh0YWIsIlBhZGRlZCB3aXRoIHNsYWNrIHZhcmlhYmxlcyIpOwogIHdoaWxlKCArK2xvb3AgKSB7CiAgICBpbnQgcGl2b3RfY29sLCBwaXZvdF9yb3c7CgogICAgcGl2b3RfY29sID0gZmluZF9waXZvdF9jb2x1bW4odGFiKTsKICAgIGlmKCBwaXZvdF9jb2wgPCAwICkgewogICAgICBwcmludGYoIkZvdW5kIG9wdGltYWwgdmFsdWU9QVswLDBdPSUzLjJsZiAobm8gbmVnYXRpdmVzIGluIHJvdyAwKS5cbiIsCiAgICAgICAgdGFiLT5tYXRbMF1bMF0pOwogICAgICBwcmludF9vcHRpbWFsX3ZlY3Rvcih0YWIsICJPcHRpbWFsIHZlY3RvciIpOwogICAgICBicmVhazsKICAgIH0KICAgIHByaW50ZigiRW50ZXJpbmcgdmFyaWFibGUgeCVkIHRvIGJlIG1hZGUgYmFzaWMsIHNvIHBpdm90X2NvbD0lZC5cbiIsCiAgICAgIHBpdm90X2NvbCwgcGl2b3RfY29sKTsKCiAgICBwaXZvdF9yb3cgPSBmaW5kX3Bpdm90X3Jvdyh0YWIsIHBpdm90X2NvbCk7CiAgICBpZiAocGl2b3Rfcm93IDwgMCkgewogICAgICBwcmludGYoInVuYm91bmRlZCAobm8gcGl2b3Rfcm93KS5cbiIpOwogICAgICBicmVhazsKICAgIH0KICAgIHByaW50ZigiTGVhdmluZyB2YXJpYWJsZSB4JWQsIHNvIHBpdm90X3Jvdz0lZFxuIiwgcGl2b3Rfcm93LCBwaXZvdF9yb3cpOwoKICAgIHBpdm90X29uKHRhYiwgcGl2b3Rfcm93LCBwaXZvdF9jb2wpOwogICAgcHJpbnRfdGFibGVhdSh0YWIsIkFmdGVyIHBpdm90aW5nIik7CiAgICBwcmludF9vcHRpbWFsX3ZlY3Rvcih0YWIsICJCYXNpYyBmZWFzaWJsZSBzb2x1dGlvbiIpOwoKICAgIGlmKGxvb3AgPiAyMCkgewogICAgICBwcmludGYoIlRvbyBtYW55IGl0ZXJhdGlvbnMgPiAlZC5cbiIsIGxvb3ApOwogICAgICBicmVhazsKICAgIH0KICB9Cn0KClRhYmxlYXUgdGFiICA9IHsgNCwgNSwgeyAgICAgICAgICAgICAgICAgICAgIC8vIFNpemUgb2YgdGFibGVhdSBbNCByb3dzIHggNSBjb2x1bW5zIF0KICAgIHsgIDAuMCAsIC0wLjUgLCAtMy4wICwtMS4wICwgLTQuMCwgICB9LCAgLy8gTWF4OiB6ID0gMC41KnggKyAzKnkgKyB6ICsgNCp3LAogICAgeyA0MC4wICwgIDEuMCAsICAxLjAgLCAxLjAgLCAgMS4wLCAgIH0sICAvLyAgICB4ICsgeSArIHogKyB3IDw9IDQwIC4uIGIxCiAgICB7IDEwLjAgLCAtMi4wICwgLTEuMCAsIDEuMCAsICAxLjAsICAgfSwgIC8vICAtMnggLSB5ICsgeiArIHcgPD0gMTAgLi4gYjIKICAgIHsgMTAuMCAsICAwLjAgLCAgMS4wICwgMC4wICwgLTEuMCwgICB9LCAgLy8gICAgICAgIHkgICAgIC0gdyA8PSAxMCAuLiBiMwogIH0KfTsKCmludCBtYWluKGludCBhcmdjLCBjaGFyICphcmd2W10pewogIGlmIChhcmdjID4gMSkgeyAvLyB1c2FnZTogY21kIGRhdGFmaWxlCiAgICByZWFkX3RhYmxlYXUoJnRhYiwgYXJndlsxXSk7CiAgfQogIHByaW50X3RhYmxlYXUoJnRhYiwiSW5pdGlhbCIpOwogIHNpbXBsZXgoJnRhYik7CiAgcmV0dXJuIDA7Cn0=
1. Tableau Initial:
----------------------------------------------------------------------
col: b[i] x1, x2, x3, x4,
max: 0 -0.50 -3 -1 -4
b1: 40 1 1 1 1
b2: 10 -2 -1 1 1
b3: 10 0 1 0 -1
----------------------------------------------------------------------
2. Tableau Padded with slack variables:
----------------------------------------------------------------------
col: b[i] x1, x2, x3, x4, x5, x6, x7,
max: 0 -0.50 -3 -1 -4 0 0 0
b1: 40 1 1 1 1 1 0 0
b2: 10 -2 -1 1 1 0 1 0
b3: 10 0 1 0 -1 0 0 1
----------------------------------------------------------------------
Most negative column in row[0] is col 4 = -4.
Entering variable x4 to be made basic, so pivot_col=4.
Ratios A[row_i,0]/A[row_i,4] = [40.00, 10.00, -10.00, ].
Found pivot A[2,4], min positive ratio=10 in row=2.
Leaving variable x2, so pivot_row=2
3. Tableau After pivoting:
----------------------------------------------------------------------
col: b[i] x1, x2, x3, x4, x5, x6, x7,
max: 40 -8.50 -7 3 0 0 4 0
b1: 30 3 2 0 0 1 -1 0
b2: 10 -2 -1 1 1 0 1 0
b3: 20 -2 0 1 0 0 1 1
----------------------------------------------------------------------
Basic feasible solution at x1=0, x2=0, x3=0, x4=10.00, x5=30.00, x6=0, x7=20.00,
Most negative column in row[0] is col 1 = -8.5.
Entering variable x1 to be made basic, so pivot_col=1.
Ratios A[row_i,0]/A[row_i,1] = [10.00, -5.00, -10.00, ].
Found pivot A[1,1], min positive ratio=10 in row=1.
Leaving variable x1, so pivot_row=1
4. Tableau After pivoting:
----------------------------------------------------------------------
col: b[i] x1, x2, x3, x4, x5, x6, x7,
max: 125 0 -1.33 3 0 2.83 1.17 0
b1: 10 1 0.67 0 0 0.33 -0.33 0
b2: 30 0 0.33 1 1 0.67 0.33 0
b3: 40 0 1.33 1 0 0.67 0.33 1
----------------------------------------------------------------------
Basic feasible solution at x1=10.00, x2=0, x3=0, x4=30.00, x5=0, x6=0, x7=40.00,
Most negative column in row[0] is col 2 = -1.33333.
Entering variable x2 to be made basic, so pivot_col=2.
Ratios A[row_i,0]/A[row_i,2] = [15.00, 90.00, 30.00, ].
Found pivot A[1,2], min positive ratio=15 in row=1.
Leaving variable x1, so pivot_row=1
5. Tableau After pivoting:
----------------------------------------------------------------------
col: b[i] x1, x2, x3, x4, x5, x6, x7,
max: 145 2 0 3 0 3.50 0.50 0
b1: 15 1.50 1 0 0 0.50 -0.50 0
b2: 25 -0.50 0 1 1 0.50 0.50 0
b3: 20 -2 0 1 0 0 1 1
----------------------------------------------------------------------
Basic feasible solution at x1=0, x2=15.00, x3=0, x4=25.00, x5=0, x6=0, x7=20.00,
Most negative column in row[0] is col 2 = 0.
Found optimal value=A[0,0]=145.00 (no negatives in row 0).
Optimal vector at x1=0, x2=15.00, x3=0, x4=25.00, x5=0, x6=0, x7=20.00,