H101 Linear Optimization Using the Simplex Algorithm

Subroutine subprograms RSMPLX and DSMPLX calculate the quantities $x$₁,x₂,...,x_m for which the linear form, or objective function,

$z\; =\; z$₀- ∑_i=1^mb_ix_i

assumes a maximum value subject to the $n$₁ inequality constraints

$\sum$_i=1^ma_ikx_i≤c_k(k = 1,2,...,n₁)

and the $n-n$₁ equality constraints

$\sum$_i=1^ma_ikx_i= c_k(k = n₁+1,n₁+2,...,n).

A number $m$₁≤m of the variables $x$_i, (i=1,2,...,m₁)

can be restricted to non-negative values ($x$_i≥0 ). The remaining $m-m$₁ variables $x$_i, (i=m₁+1,...,m) are then unrestricted (_i<&inf; ). In the case $m$₁=0 , all variables $x$_i

are unrestricted. These subprograms can also be used for the so-called degenerate case.

On computers other than CDC or Cray, only the double-precision version DSMPLX is available. On CDC and Cray computers, only the single precision version RSMPLX is available.

Structure:

SUBROUTINE subprograms
User Entry Names: RSMPLX, DSMPLX
Internal Entry Names: H101S1, H101S2
Files Referenced: Unit 6
External References: MTLMTR (N002), ABEND (Z035)

Usage:

For $t=R$ (type REAL), $t=D$ (type DOUBLE PRECISION),

    CALL tSMPLX(A,B,C,Z0,IDA,M,M1,N,N1,LW,IDW,W,X,Z,ITYPE)

A

(type according to t) Two-dimensional array of dimension $(IDA,\ge N)$ . Contains, on entry, the coefficients $a$_i,k, (i = 1,2,...,m; k =1,2,...,n) . Destroyed during execution.

B

(type according to t) One-dimensional array of dimension $\ge M$ . Contains, on entry, the coefficients $b$_i, (i = 1,2,...,m) . Destroyed during execution.

C

(type according to t) One-dimensional array of dimension $\ge N$ . Contains, on entry, the coefficients $c$_k, (k = 1,2,...,n) . Destroyed during execution.

Z0

(type according to t) Contains, on entry, the initial value of the objective function.

IDA

( INTEGER) Declared first dimension of A in the calling program ($IDA\; \ge M$ ).

M

( INTEGER) The total number m of variables $x$_i

($M\; \ge 0$ ).

M1

( INTEGER) The number $m$₁ of restricted variables $x$_i≥0 ($0\; \le M1\; \le M)$ .

N

( INTEGER) The total number n of constraints ($N\; \ge 0$ ).

N1

( INTEGER) The number $n$₁ of inequality constraints ($0\; \le N1\; \le N)$ .

LW

( INTEGER) Two-dimensional array of dimension $(IDW,\; \ge 5)$ . Used as working space.

IDW

( INTEGER) Declared first dimension of LW in the calling program ($IDW\; \ge M+2*N$ ).

W

(type according to t) One-dimensional array of dimension $\ge M+N$ . Used as working space.

X

(type according to t) One-dimensional array of dimension $\ge M+N$ . If $ITYPE=1$ or $ITYPE=2$ , its first m elements X(1),...,X(M) contain, on exit, the or a solution $x$₁,...,x_m , respectively. The next n elements X(M+1),...,X(M+N) contain the values of the so-called slack variables $x$_m+1,...,x_m+n . If $ITYPE=3$ or $ITYPE=4$ , the elements $X(1),...,X(M+N)$ are undefined.

Z

(type according to t) If $ITYPE=1$ or $ITYPE=2$ , Z contains, on exit, the result z of the objective function. Undefined for $ITYPE=3$ and $ITYPE=4$ .

ITYPE

( INTEGER) Defines, on exit, the type of the result:

$=1:$ There is exactly one finite solution.

$=2:$ There is more than one solution.

$=3:$ There is no finite solution.

$=4:$ There is no feasable initial solution.

Method:

The method is described in Ref. 1 and Ref. 2.

Error handling:

Error H101.1: $M\; \le 0$ or $N\; \le 0$ .
Error H101.2: or $M1\; >\; M$

or or $N1\; >\; N$ .
In both cases, a message is written on Unit 6, unless subroutine MTLSET (N002) has been called.

References:

1. H.P. Künzi, H.G. Tzschach and C.A. Zehnder, Numerical methods of mathematical optimization, (Academic Press, New York 1968)
2. E. Stiefel, Einführung in die Numerische Mathematik, (B.G. Teubner, Stuttgart 1965)

H301