Simplex-method (linear programming).

Version 1.0 (April 2005)

Authors: S.Yu.Orevkov, Yu.P.Orevkov

         orevkov@picard.ups-tlse.fr


1. Installation:
----------------

Just compile the C-program file using e.g. the command

     gcc o-simplex.c -o simplex


2. Usage:
---------

     simplex [ options ] [ <input_file ] [ >output ]

 Options (the case is ignored, e.g., -i is the same as -I):

 -i     the input data are interpreted as a system of simultaneous
        Inequalities for non-negative variables (by default, they
        are interpreted as a system of simultaneous equations
        for non-negative variables)
 -m     
 -mnnn  print the resulting Matrix with nnn digits after the decimal 
        point (default: nnn=2)

 -t     Trace intermediate steps

 -d/-n  (only if -i is switched on) force usage/Non-usage of the 
        Dual problem. By default the dual problem is used when the 
        number of inequalities is greater that the number of variables.

 -pnnn  absolute Precision is 10^(-nnn). Default: 11.


3. Input:
---------

 The standard input (the input file if `<file' is used) must contain
 2+(n+1)*(m+1) decimal numbers where n is the number of variables
 and m is the number of equations/inequalities followed by the names
 of variables. If the number of variable names is less than the
 number of variables (e.g. is zero) then the variables are denoted
 by X1, X2, ...

 The numerical data may be arbitrarily separated by spaces, tabs, and
 newlines. They must be ordered as follows:

 n  m
 A[0,0]  A[0,1] ... A[0,n]
 A[1,0]  A[1,1] ... A[1,n]

    . . . . . . . . . 

 A[m,0]  A[m,1] ... A[m,n]
  [ var1 var2 ... var_n ]

 This means that you ask to minimize 

       A[0,0] - Sum( A[0][j]*x_j, j=1..n )

 (attention for the signs!)
 under the primary constraints 

       x_j >= 0,  j=1..n

 and the secondary constraints

      Sum( A[i][j]*xj, j=1..n ) = A[i][0],  i=1,...,m

 (if -i option is switched off) or

      Sum( A[i][j]*xj, j=1..n ) <= A[i][0],  i=1,...,m

 (if -i option is switched on).


4. Example:
-----------

Suppose that we want to find  the maximum of the function  
 5 + 3a + 4b + c  under the constraints:

   a >= b >= c >= 0
   a + b/2 + 3c = 6

First, we must replace the problem by searching the minimum
of  -5-3a-4b-c.

There are two possible ways to solve this problem: 
with or without the -i option.


4.1. Solution using equations (without -i).

Let us rewrite the constraints as 

   a - b = z1
   b - c = z2
   a + b/2 + 3c = 6

   a,b,c,z1,z2 >= 0

So, we prepare the input file  example1.sx

====================
 5 
 3
 -5   3  4  1  0  0
  0   1 -1  0 -1  0
  0   0  1 -1  0 -1
  6   1 0.5 3  0  0
      a  b  c  z1 z2
====================

and run

   simplex <example1.sx

The output is:

----------------------------------------------------------
Variable names:

1-th variable is a
2-th variable is b
3-th variable is c
4-th variable is z1
5-th variable is z2

A feasible solution is found.

Solution:

a =  4.000000000000
b =  4.000000000000
c =  0.000000000000
z1 =  0.000000000000
z2 =  4.000000000000

The value of the objective function is  -33.000000000000
----------------------------------------------------------


4.2. Solution using inequalities (with -i).

Let us rewrite the constraints as 


   -a + b        <=  0
        -b  + c  <=  0
    a + b/2 + 3c <=  6
   -a - b/2 - 3c <= -6

   a,b,c >= 0

So, we prepare the input file  example2.sx ...

=================
   3 
   4
 -5   3  4    1
  0  -1  1    0
  0   0 -1    1
  6   1  0.5  3
 -6  -1 -0.5 -3
      a  b    c
=================

...and run

   simplex -i <example2.sx

The output is:

---------------------------------------------------------
Variable names:

1-th variable is a
2-th variable is b
3-th variable is c

A feasible solution is found.

Solution:

a =  4.000000000000
b =  4.000000000000
c = -0.000000000000

The value of the objective function is  33.000000000000
---------------------------------------------------------


5. Implementation featurs:
--------------------------

We use the standard simplex-method algorithm but our implementation
has the following defeat: in the case of inequalities we create an 
additional identity  m x m  matrix.

However, this is not as bad as one could expect because in the case
when  m > n  we pass to the dual problem where the roles of  m  and 
n  are exchanged. Thus, we at most double the memory.

This is why we do not recommend to use the -n option when the number
of inequalities is big.