Further Examples: LinearProgramming

This solves an equality-constrained problem. The expression is minimized subject to . The zero indicates equality.

In[1]:=

Out[1]=

This solves a problem with no constraints other than bounds. The expression is minimized subject to and .

In[2]:=

Out[2]=

This solves a problem with only lower bounds. The expression is minimized subject to .

In[3]:=

Out[3]=

This solves a problem with no bounds on the second variable. The expression is minimized subject to and . The number indicates "".

In[4]:=

Out[4]=

This solves a problem with the second variable fixed to be . The expression is minimized subject to , and .

In[5]:=

Out[5]=

The above problem can also be solved by writing the fixed variable y as the equality constraint, and setting its bounds to any that catch the value , such as .

In[6]:=

Out[6]=

This solves a problem with both equality and inequality constraints as well as bounds. The expression is minimized subject to , , and .

In[7]:=

Out[7]=

The Klee-Minty problem of dimension 5 is

Maximize 10000 y[1] + 1000 y[2] + 100 y[3] + 10 y[4] + y[5]

subject to y[1] 1,

20 y[1] + y[2] 100,

200 y[1] + 20 y[2] + y[3]

2000 y[1] + 200 y[2] + 20 y[3] + y[4]

20000 y[1] + 2000 y[2] + 200 y[3] + 20 y[4] + y[5]

y[1] 0, y[2] 0, y[3] 0, y[4] 0, y[5] 0.

This expresses the Klee-Minty problem of dimension in the LinearProgramming syntax.

In[8]:=

Without scaling, the simplex algorithm takes an exponential number of iterations to converge. Evaluate the previous cell to define KleeMinty.

In[9]:=

Out[9]=

With scaling, which is applied by default, the simplex algorithm converges very quickly.

In[10]:=

Out[10]=

In[11]:=