simplex {boot} | R Documentation |

## Simplex Method for Linear Programming Problems

### Description

This function will optimize the linear function `a%*%x`

subject
to the constraints `A1%*%x <= b1`

, `A2%*%x >= b2`

,
`A3%*%x = b3`

and `x >= 0`

. Either maximization or
minimization is possible but the default is minimization.

### Usage

```
simplex(a, A1 = NULL, b1 = NULL, A2 = NULL, b2 = NULL, A3 = NULL,
b3 = NULL, maxi = FALSE, n.iter = n + 2 * m, eps = 1e-10)
```

### Arguments

`a` |
A vector of length |

`A1` |
An |

`b1` |
A vector of length |

`A2` |
An |

`b2` |
A vector of length |

`A3` |
An |

`b3` |
A vector of length |

`maxi` |
A logical flag which specifies minimization if |

`n.iter` |
The maximum number of iterations to be conducted in each phase of
the simplex method. The default is |

`eps` |
The floating point tolerance to be used in tests of equality. |

### Details

The method employed by this function is the two phase tableau simplex
method. If there are `\geq`

or equality constraints an initial feasible
solution is not easy to find. To find a feasible solution an
artificial variable is introduced into each `\geq`

or equality
constraint and an auxiliary objective function is defined as the sum
of these artificial variables. If a feasible solution to the set of
constraints exists then the auxiliary objective will be minimized when
all of the artificial variables are 0. These are then discarded and
the original problem solved starting at the solution to the auxiliary
problem. If the only constraints are of the `\leq`

form, the origin is
a feasible solution and so the first stage can be omitted.

### Value

An object of class `"simplex"`

: see `simplex.object`

.

### Note

The method employed here is suitable only for relatively small
systems. Also if possible the number of constraints should be reduced
to a minimum in order to speed up the execution time which is
approximately proportional to the cube of the number of constraints.
In particular if there are any constraints of the form ```
x[i] >=
b2[i]
```

they should be omitted by setting `x[i] = x[i]-b2[i]`

,
changing all the constraints and the objective function accordingly
and then transforming back after the solution has been found.

### References

Gill, P.E., Murray, W. and Wright, M.H. (1991)
*Numerical Linear Algebra and Optimization Vol. 1*. Addison-Wesley.

Press, W.H., Teukolsky, S.A., Vetterling, W.T. and Flannery, B.P. (1992)
*Numerical Recipes: The Art of Scientific Computing (Second Edition)*.
Cambridge University Press.

### Examples

```
# This example is taken from Exercise 7.5 of Gill, Murray and Wright (1991).
enj <- c(200, 6000, 3000, -200)
fat <- c(800, 6000, 1000, 400)
vitx <- c(50, 3, 150, 100)
vity <- c(10, 10, 75, 100)
vitz <- c(150, 35, 75, 5)
simplex(a = enj, A1 = fat, b1 = 13800, A2 = rbind(vitx, vity, vitz),
b2 = c(600, 300, 550), maxi = TRUE)
```

*boot*version 1.3-30 Index]