| Library: | nummath |
| See also: | nmlinprogmaxel nmlinprogpivot nmlinprogexchange |
| Quantlet: | nmlinprog | |
| Description: | simplex method for linear programming problem in normal form |
| Usage: | sol = nmlinprog(coef,ncon {,nvar,tol}) | |
| Input: | ||
| coef | (ncon+1) x (nvar+1) matrix, input tableau of the linear programming problem; first row has to contain coefficients for the objective function, followed by coefficients of "<=", ">=" and "=" constraints (in this order!) in next rows. First column corresponds to a constant term, (i+1)-th column is a coefficient corresponding to x_i, i=1..nvar. | |
| ncon | 3 x 1 vector, numbers of constraints of the type sum(a_ij x_j) <= b_i, sum(a_ij x_j) >= b_i and sum(a_ij x_j) = b_i, respectively. | |
| nvar | (optional) scalar, number of (original) variables in the problem; default nvar = cols(coef)-1 | |
| tol | (optional) scalar, tolerance for assessing the computed coefficients as equal to zero. Default tol = 1e-7; you may want to adjust it to the scale of variables in your problem. | |
| Output: | ||
| sol.xmax | nvar x 1 vector, solution; NaN's if no feasible solution exists or if the objective function is unbounded | |
| sol.fmax | scalar, maximum of the objective function under given constraints; NaN if no feasible solution exists | |
| sol.type | scalar, type of solution; type = NaN if no feasible solution exists, type = Inf if the objective function is unbounded, type = 0 if a feasible solution was found | |
| sol.coefout | (ncon+1) x (nvar+1) matrix, output tableau | |
| sol.lvar | ncon x 1 vector, indices of left-hand variables in the output tableau | |
| sol.rvar | nvar x 1 vector, indices of right-hand variables in the output tableau | |
Linear programming (LP) solves the problem
maximize the function z = sum(a_0i x_i), i = 1..n
subject to the primary constraints x_i >= 0, i = 1..n
and m1 + m2 + m3 constraints of the forms
sum(a_ji x_i) <= b_j, b_j >= 0, j = 1..m1 ("<=" constraints)
sum(a_ji x_i) >= b_j, b_j >= 0, j = m1+1..m1+m2 (">=" constraints)
sum(a_ji x_i) = b_j, b_j >= 0, j = m1+m2+1..m1+m2+m3 ("=" constraints)
;
A linear programming problem is said to be in normal form if it has only primary constraints and equality constraints. Each LP problem can be transformed into normal form by adding or subtracting so called nonnegative slack variables to/from the respective inequality constraints, for example, x1 + x2 >= 8 <=> x1 + x2 - y1 = 8. To produce the respective coefficient row for the input matrix coef, you will need to rewrite this constraint into the form 8 - x1 - x2 + y1 = 0. The matrix coef contains only coefficients corresponding to the variables xi, you don't need to specify coefficients for yi's.
; example as in Numerical Recipes, p. 431-438:
; maximize z = x1 + x2 + 3*x3 - 0.5*x4
; subject to constraints
; xi >= 0, i = 1..4
; x1 + 2*x3 <= 740
; 2*x2 - 7*x4 <= 0
; x2 - x3 + 2*x4 >= 0.5
; x1 + x2 + x3 + x4 = 9
;
library("nummath")
coef=#(0,740,0,0.5,9)~#(1,-1,0,0,-1)~#(1,0,-2,-1,-1)~#(3,-2,0,1,-1)~#(-0.5,0,7,-2,-1)
coef
; two "<=", one ">=" and one "=" constraints:
linprog = nmlinprog(coef,2|1|1,4)
linprog
Contents of coef ; input tableau [1,] 0 1 1 3 -0.5 [2,] 740 -1 0 -2 0 [3,] 0 0 -2 0 7 [4,] 0.5 0 -1 1 -2 [5,] 9 -1 -1 -1 -1 Contents of linprog.xmax ; maximizer [1,] 0 [2,] 3.325 [3,] 4.725 [4,] 0.95 Contents of linprog.fmax ; maximum [1,] 17.025 Contents of linprog.type ; finite maximizer exists [1,] 0 Contents of linprog.coefout ; output tableau [1,] 17.025 -0.95 -0.05 -1.05 1.95 [2,] 3.325 -0.35 -0.15 0.35 0.35 [3,] 4.725 -0.55 0.05 -0.45 0.55 [4,] 0.95 -0.1 0.1 0.1 0.1 [5,] 730.55 0.1 -0.1 0.9 -1.1 Contents of linprog.lvar ; rows of output tableau correspond to x2, x3, x4 and y1 (= x5) [1,] 2 [2,] 3 [3,] 4 [4,] 5 Contents of linprog.rvar ; cols of output tableau correspond to x1, y2, y3 y4 [1,] 1 [2,] 6 [3,] 7 [4,] 8
; example with unbounded objective function:
; maximize z = x1 + x2
; subject to constraints
; xi >= 0, i = 1,2
; x1 - x2 <= 1
;
library("nummath")
coef=#(0,1)~#(1,-1)~#(1,1)
coef
; only one "<=" constraint:
linprog = nmlinprog(coef,1|0|0)
linprog
Contents of coef ; input tableau [1,] 0 1 1 [2,] 1 -1 1 Contents of linprog.xmax [1,] +NAN [2,] +NAN Contents of linprog.fmax ; maximum [1,] +INF Contents of linprog.type ; unbounded objective function [1,] +INF Contents of linprog.coefout ; output tableau [1,] 1 2 -1 [2,] 1 1 -1 Contents of linprog.lvar [1,] 1 Contents of linprog.rvar [1,] 2 [2,] 3
; example without feasible solution:
; maximize z = x1 + x2
; subject to constraints
; xi >= 0, i = 1,2
; x1 + x2 >= 2
; x1 + 2*x2 <= 1
;
library("nummath")
coef=#(0,1,2)~#(1,-1,-1)~#(1,-2,-1)
coef
; one "<=" and one ">=" constraints:
linprog = nmlinprog(coef,1|1|0)
linprog
Contents of coef ; input tableau [1,] 0 1 1 [2,] 1 -1 -2 [3,] 2 -1 -1 Contents of linprog.xmax [1,] +NAN [2,] +NAN Contents of linprog.fmax [1,] +NAN Contents of linprog.type [1,] +NAN ; no feasible solution exists! Contents of linprog.coefout [1,] 1 -1 -1 [2,] 1 -2 -1 [3,] 1 1 1 Contents of linprog.lvar [1,] 1 [2,] 4 Contents of linprog.rvar [1,] 2 [2,] 3