\newcommand{\R}{{\bf R}}
| Name | Brad Bell (http://www.seanet.com/~bradbell/) |
| Office Location | Room 471 of Henderson Hall (http://www.washington.edu/home/maps/northwest.html?HND) |
| Office Phone | 206-543-6855 |
| Paging | 206-543-1300 |
| brad at apl dot washington dot edu |
\pi
appears as \pi instead of the
corresponding Greek letter, you are viewing home.htm
.
If your browser supports XHTML + MathML, you will get a better view
of these and other pages in this site by starting with
home.xml
.
Printable versions of this web site can be found in the files
_printable.htm
and _printable.xml
.
| Tuesday | 06/21 | 06/28 | 07/05 | 07/12 | 07/19 | 07/26 | 08/02 | 08/09 | 08/16 |
| Thursday | 06/23 | 06/30 | 07/07 | 07/14 | 07/21 | 07/28 | 08/04 | 08/11 | 08/18 |
| Author | Chvatal, Vasek |
| Title | Linear programming |
| Pub info | New York : W.H. Freeman, c1983 |
| 06/23 | 06/30 | 07/07 | 07/19 | 07/26 | 08/02 | 08/09 |
Makeups for tests must be arranged with the instructor ahead of time.
If a student misses a test with out arranging a makeup
ahead of time, a score of zero will be assigned
for that test.
If this only happens for one quiz,
it becomes the quiz that does not count.
If this happens for the final,
and the student had an emergency that,
in the instructors opinion,
prevented the student from taking the final,
she or he will receive an
incomplete
(http://www.washington.edu/students/reg/incomplete.html)
(instead of a zero for the final).
Math 407 Summer 2005 Class Web Page: home:
Table of Contents: _contents: 1
The Simple Method: SimplexMethod: 2
Dictionary Method Solution of Equation 2.1 in Chvatal: Dictionary2.1: 2.1
Tableau Method Solution of Equation 2.1 in Chvatal: Tableau2.1: 2.2
Neos Input and Output File for Equation 2.1 in Chvatal: Equation2.1: 2.3
Preform a Pivot Operation: Pivot: 2.4
Using Pivot Function to solve Equation 2.1: Pivot2_1: 2.4.1
Multiple Solutions: Multiple: 2.5
Neos Input and Output File for Problem 2.2 in Chvatal: Problem2.2: 2.5.1
Two Phase Simplex Method: TwoPhase: 2.6
Neos Input and Output File for Problem 3.9a in Chvatal: Problem3.9a: 2.6.1
Degeneracy: Degeneracy: 2.7
The Cycling of Simplex Method: Basis: 2.8
Bland's Pivot Rule: Bland: 2.9
Example Use of Bland's Method: BlandExample: 2.9.1
Linear Programming Duality Theory: Duality: 3
A Linear Programming Duality Example: DualExample: 3.1
Duality With Inequality Constraints: DualIneq: 3.2
The Duality Theorem: DualTheorem: 3.3
The Complementary Slackness Condition: CompSlack: 3.4
An Example Computing the Dual Variables: DualComp: 3.5
Relation Between Dual and Perturbed Upper Bound: PerturbUpper: 3.6
Duality with Equality and Inequality Constraints: DualEqIneq: 3.7
Zero Sum Matrix Games: MatrixGame: 4
Problem 15.1 of the Text: Problem15.1: 4.1
Rock Paper Scissor as a Zero Sum Matrix Game: RockPaperScissor: 4.2
Part II: Selected Applications: Applications: 5
Product Manufacturing: Manufacture: 5.1
Toll Booth Scheduling: Schedule: 5.2
Electronics Company: Electronic: 5.3
A Forestry Example: Forestry: 5.4
Neos Interface to the Clp Linear Program Solver: NeosClp: 6
The MPS Input Format: MpsInputFile: 6.1
Some of The Clp Executable Commands: ClpCommand: 6.2
Math 407 Summer 05 Tests: Test: 7
Math 407 Summer 05 Quiz 06-23: Quiz0623: 7.1
Math 407 Summer 05 Quiz 06-30: Quiz0630: 7.2
Math 407 Summer 05 Quiz 07-05: Quiz0705: 7.3
Math 407 Summer 05 Quiz 07-19: Quiz0719: 7.4
Math 407 Summer 05 Quiz 07-26: Quiz0726: 7.5
Math 407 Summer 05 Quiz 08-02: Quiz0802: 7.6
Math 407 Summer 05 Quiz 08-09: Quiz0809: 7.7
Math 407 Summer 05 Final Exam: Final: 7.8
Bibliography: Bib: 8
Alphabetic Listing of Cross Reference Tags: _reference: 9
Keyword Index: _index: 10
maximize 5*x1 + 4*x2 + 3*x3
subject to 2*x1 + 3*x2 + x3 <= 5
4*x1 + x2 + 2*x3 <= 11
3*x1 + 4*x2 + 2*x3 <= 8
x1 , x2 , x3 >= 0
maximize z = 5*x1 + 4*x2 + 3*x3
subject to s1 = 5 - 2*x1 - 3*x2 - x3
s2 = 11 - 4*x1 - x2 - 2*x3
s3 = 8 - 3*x1 - 4*x2 - 2*x3
x1, x2, x3, s1, s2, s3 >= 0
x1=0, x2=0, x3=0, s1=5, s2=11, s3=8, z=0
z increases as we increase x1
and keep x2 = x3 = 0 (because the x1 coefficient
in the equation for z is positive).
If the resulting point is feasible,
0 <= s1 = 5 - 2*x1; i.e., x1 <= 5/2
0 <= s2 = 11 - 4*x1; i.e., x1 <= 11/4
0 <= s3 = 8 - 3*x1; i.e., x1 <= 8/3
We notice that if we choose x1 so that s1 is zero,
all the constraints will be satisfied.
This corresponds exchanging the roles of x1 and s1
in the set of equations.
x1 in the row corresponding to s1; i.e,
x1 = 2.5 - .5*s1 - 1.5*x2 - .5*x3
We replace the row corresponding to s1 with this equation and
we use this equation to replace all other occurrences of x1
in the problem; i.e.,
maximize z = 5*(2.5 - .5*s1 - 1.5*x2 - .5*x3) + 4*x2 + 3*x3
subject to x1 = 2.5 - .5*s1 - 1.5*x2 - .5*x3
s2 = 11 - 4*(2.5 - .5*s1 - 1.5*x2 - .5*x3) - x2 - 2*x3
s3 = 8 - 3*(2.5 - .5*s1 - 1.5*x2 - .5*x3) - 4*x2 - 2*x3
x1, x2, x3, s1, s2, s3 >= 0
Regrouping terms we have the equivalent problem
maximize z = 12.5 - 2.5*s1 - 3.5*x2 + .5*x3
subject to x1 = 2.5 - .5*s1 - 1.5*x2 - .5*x3
s2 = 1 + 2*s1 + 5*x2
s3 = .5 + 1.5*s1 + .5*x2 - .5*x3
x1, x2, x3, s1, s2, s3 >= 0
The basic feasible solution corresponding to the representation above is
x1=2.5, x2=0, x3=0, s1=0, s2=1, s3=.5, z=12.5
We note that the vale of z has increased from the previous
problem representation.
z increases as we increase x3
and keep s1 = x2 = 0 (because the x3 coefficient
in the equation for z is positive).
If the resulting point is feasible,
0 <= x1 = 2.5 - .5*x3; i.e., x3 <= 5
0 <= s2 = 1; i.e., 0 <= 1
0 <= s3 = .5 - .5*x3; i.e., x3 <= 1
We notice that if we choose x3 so that s3 is zero,
all the constraints will be satisfied.
This corresponds exchanging the roles of x3 and s3
x3 in the row corresponding to s3; i.e,
maximize z = 12.5 - 2.5*s1 - 3.5*x2 + .5*(1 + 3*s1 + x2 - 2*s3)
subject to x1 = 2.5 - .5*s1 - 1.5*x2 - .5*(1 + 3*s1 + x2 - 2*s3)
s2 = 1 + 2*s1 + 5*x2
x3 = 1 + 3*s1 + x2 - 2*s3
x1, x2, x3, s1, s2, s3 >= 0
Regrouping terms we have the equivalent problem
maximize z = 13 - s1 - 3*x2 - s3
subject to x1 = 2 - 2*s1 - 2*x2 + s3
s2 = 1 + 2*s1 + 5*x2
x3 = 1 + 3*s1 + x2 - 2*s3
x1, x2, x3, s1, s2, s3 >= 0
The basic feasible solution corresponding to the representation above is
x1=2, x2=0, x3=1, s1=0, s2=1, s3=0, z=13
We note that the vale of z has increased from the previous
problem representation.
This is the optimal solution (because there is no feasible direction
in which the objective function increases).
maximize 5*x1 + 4*x2 + 3*x3
subject to 2*x1 + 3*x2 + x3 <= 5
4*x1 + x2 + 2*x3 <= 11
3*x1 + 4*x2 + 2*x3 <= 8
x1 , x2 , x3 >= 0
maximize 5*x1 + 4*x2 + 3*x3 - z = 0
subject to 2*x1 + 3*x2 + x3 + s1 = 5
4*x1 + x2 + 2*x3 + s2 = 11
3*x1 + 4*x2 + 2*x3 + s3 = 8
x1 , x2 , x3 >= 0
\[
\begin{array}{cccccccc}
x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\
2 & 3 & 1 & 1 & 0 & 0 & 0 & 5 \\
4 & 1 & 2 & 0 & 1 & 0 & 0 & 11 \\
3 & 4 & 2 & 0 & 0 & 1 & 0 & 8 \\
5 & 4 & 3 & 0 & 0 & 0 & -1 & 0
\end{array}
\]
(Note that we have moved the equation for
z
to the last row.)
The corresponding basic feasible solution is
x_1 = x_2 = x_3 = 0
,
s_1 = 5
,
s_2 = 11
,
s_3 = 8
,
z = 0
.
z
(last row) for a positive entry and find
the value 5 in the
x_1
column.
Thus was can increase the objective by increasing
the value of
x_1
and holding
x_2
,
x_3
at zero.
We now solve for the value of
x_1
that results in
\[
\begin{array}{llll}
s_1 = 0 & \Leftrightarrow & x_1 = 5/2 & = 2.5 \\
s_2 = 0 & \Leftrightarrow & x_1 = 11/4 & = 2.75 \\
s_3 = 0 & \Leftrightarrow & x_1 = 8/3 & = 2.66 \cdots
\end{array}
\]
Thus we can pivot on the pair
(x_1, s_1)
and obtain
a new basic feasible solution with an improved
value for the objective.
\[
\begin{array}{cccccccc}
x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\
1 & 1.5 & .5 & .5 & 0 & 0 & 0 & 2.5 \\
4 & 1 & 2 & 0 & 1 & 0 & 0 & 11 \\
3 & 4 & 2 & 0 & 0 & 1 & 0 & 8 \\
5 & 4 & 3 & 0 & 0 & 0 & -1 & 0
\end{array}
\]
x_1
times the row corresponding to the pivot element:
\[
\begin{array}{cccccccc}
x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\
1 & 1.5 & .5 & .5 & 0 & 0 & 0 & 2.5 \\
0 & -5 & 0 & -2 & 1 & 0 & 0 & 1 \\
0 & -.5 & .5 & -1.5 & 0 & 1 & 0 & .5 \\
0 & -3.5 & .5 & -2.5 & 0 & 0 & -1 & -12.5
\end{array}
\]
The corresponding basic feasible solution is
s_1 = x_2 = x_3 = 0
,
x_1 = 2.5
,
s_2 = 1
,
s_3 = .5
,
z = 12.5
.
z
(last row) for a positive entry and find
.5 in the
x_3
column.
Thus we can increase the objective by increasing
x_3
and holding
x_2
,
s_1
at zero.
We now solve for the value of
x_3
that results in
\[
\begin{array}{lll}
x_1 = 0 & \Leftrightarrow & x_3 = 5 \\
s_2 = 1& {\rm for \; all} & x_3 \\
s_3 = 0 & \Leftrightarrow & x_3 = 1
\end{array}
\]
Thus we can pivot on the pair
(x_3, s_3)
and
obtain a new basic feasible solution with an improved
value for the objective.
\[
\begin{array}{cccccccc}
x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\
1 & 1.5 & .5 & .5 & 0 & 0 & 0 & 2.5 \\
0 & -5 & 0 & -2 & 1 & 0 & 0 & 1 \\
0 & -1 & 1 & -3 & 0 & 2 & 0 & 1 \\
0 & -3.5 & .5 & -2.5 & 0 & 0 & -1 & -12.5
\end{array}
\]
\[
\begin{array}{cccccccc}
x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\
1 & 2 & 0 & 2 & 0 & -1 & 0 & 2 \\
0 & -5 & 0 & -2 & 1 & 0 & 0 & 1 \\
0 & -1 & 1 & -3 & 0 & 2 & 0 & 1 \\
0 & -3 & 0 & -1 & 0 & -1 & -1 & -13
\end{array}
\]
s_1 = x_2 = s_3 = 0
,
x_1 = 2
,
s_2 = 1
,
x_3 = 1
,
z = 13
.
This is an optimal solution because all of the coefficients
in the row corresponding to the objective
z
are less than zero.
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Equation 2.1 in Vasek Chvatal's book: Linear Programming
maximize 5*x1 + 4*x2 + 3*x3
subject to 2*x1 + 3*x2 + x3 <= 5
4*x1 + x2 + 2*x3 <= 11
3*x1 + 4*x2 + 2*x3 <= 8
x1 , x2 , x3 >= 0
The solution is x1 = 2, x2 = 0, x3 = 1
The residuals are 0=s1=5-r1, 1=s2=11-r2, 0=s3=8-r3
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------ Name2--- Value2------
*23 56789012 56789012 567890123456 01234567 012345678901
NAME CE-2.1
ROWS
N z
L r1
L r2
L r3
COLUMNS
x1 z 5 r1 2
x1 r2 4 r3 3
*
x2 z 4 r1 3
x2 r2 1 r3 4
*
x3 z 3 r1 1
x3 r2 2 r3 2
RHS
b r1 5
b r2 11
b r3 8
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 2.0 , 2.0 , 2.0 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME CE-2.1
At line 5 ROWS
At line 10 COLUMNS
At line 19 RHS
At line 23 ENDATA
Problem CE-2.1 has 3 rows, 3 columns and 9 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 3 (0) rows, 3 (0) columns and 9 (0) elements
0 Obj -0 Dual inf 7.47056 (3)
4 Obj 13
Optimal - objective value 13
Optimal objective 13 - 4 iterations time 0.002
Clp:
0 r1 5 1
1 r2 10 -0
2 r3 8 1
0 x1 2 -2.8223853e-16
1 x2 0 -3
2 x3 1 5.647295e-16
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
s1 = 5 - r1 = 0
s2 = 11 - r2 = 1
s3 = 8 - r3 = 0
x1 = 2
x2 = 0
x3 = 1
| Syntax |
= Pivot(A, r, c)
|
m
(
n
) be the number of rows (columns)
in the matrix A.
The output matrix B and the same number of rows
and columns and
for
i = 1 , \ldots , m
,
i \neq r
,
j = 1 , \ldots , n
\[
\begin{array}{rcl}
B_{r,j} & = & A_{r,j} \frac{1}{ A_{r,c} }
\\
B_{i, j} & = & A_{i,j} - A_{r,j} \frac{ A_{i,c} }{ A_{r, c} }
\end{array}
\]
It follows that
\[
B_{i,c} = \left\{ \begin{array}{ll}
1 & {\rm if} \; i = r \\
0 & {\rm otherwise}
\end{array} \right.
\]
Pivot function.
function B = Pivot(A, r, c)
[m, n] = size(A);
B = zeros(m, n);
B(r, :) = A(r, :) / A(r, c);
for i = 1 : m
if i ~= r
B(i, :) = A(i, :) - A(i, c) * B(r, :);
end
end
A = [ 2 3 1 1 0 0 0 5
4 1 2 0 1 0 0 11
3 4 2 0 0 1 0 8
5 4 3 0 0 0 -1 0 ]
The result of this operation is:
A = {
[ 2 , 3 , 1 , 1 , 0 , 0 , 0 , 5 ]
[ 4 , 1 , 2 , 0 , 1 , 0 , 0 , 11 ]
[ 3 , 4 , 2 , 0 , 0 , 1 , 0 , 8 ]
[ 5 , 4 , 3 , 0 , 0 , 0 , -1 , 0 ]
}
r = 1;
c = 1;
B = Pivot(A, r, c)
The result of this operation is:
B = {
[ 1 , 1.5 , 0.5 , 0.5 , 0 , 0 , 0 , 2.5 ]
[ 0 , -5 , 0 , -2 , 1 , 0 , 0 , 1 ]
[ 0 , -0.5 , 0.5 , -1.5 , 0 , 1 , 0 , 0.5 ]
[ 0 , -3.5 , 0.5 , -2.5 , 0 , 0 , -1 , -12.5 ]
}
r = 3;
c = 3;
C = Pivot(B, r, c);
The result of this operation is:
C = {
[ 1 , 2 , 0 , 2 , 0 , -1 , 0 , 2 ]
[ 0 , -5 , 0 , -2 , 1 , 0 , 0 , 1 ]
[ 0 , -1 , 1 , -3 , 0 , 2 , 0 , 1 ]
[ 0 , -3 , 0 , -1 , 0 , -1 , -1 , -13 ]
}
x1 x2 x3 x4 s1 s2 z b
1 2 3 1 1 0 0 5
1 1 2 3 0 1 0 3
2 3 5 4 0 0 -1 0
(x3, s2) for our first pivot operation.
The result of the pivot will be:
x1 x2 x3 x4 s1 s2 z b
-.5 .5 0 -3.5 1 -1.5 0 .5
.5 .5 1 1.5 0 .5 0 1.5
-.5 .5 0 -3.5 0 -2.5 -1 -7.5
(we used Pivot: 2.4
to do the arithmetic in this operation.)
(x2, s1) for our second pivot operation.
The result of the pivot will be:
x1 x2 x3 x4 s1 s2 z b
-1 1 0 -7 2 -3 0 1
1 0 1 5 -1 2 0 1
0 0 0 0 -1 -1 -1 -8
(we used Pivot: 2.4
to do the arithmetic in this operation.)
x1 = 0, x2 = 1, x3 = 1, x4 = 0, s1 = 0, s2 = 0, z = 8
It follows that this is an optimal solution
because all the variable coefficients in the last row are
less than or equal zero
(not counting the b coefficient which is also <= 0).
maximize z = 8 - s1 - s2
subject to x2 = 1 + x1 + 7*x4 - 2*s1 + 3*s2
x3 = 1 - x1 - 5*x4 + s1 - 2*s2
Thus, for any choice of a >= 0 and b >= 0,
the solution
s1 = 0, s2 = 0, z = 8, x1 = a, x4 = b, x2 = 1 + a + 7*b, x3 = 1 - a - 5*b
is also an optimal for this problem.
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Problem 2.2 in Vasek Chvatal's book: Linear Programming
maximize 2*x1 + 3*x2 + 5*x3 + 4*x4
subject to x1 + 2*x2 + 3*x3 + x4 <= 5
x1 + x2 + 2*x3 + 3*x4 <= 3
x1 , x2 , x3 , x4 >= 0
For any choice of a >= 0 and b >= 0, the values
x1 = a, x4 = b, x2 = 1 + a + 7*b, x3 = 1 - a - 5*b
yield an optimal for this problem.
The corresponding slack variable values are given by
0 = s1 = 5 - r1, 0 = s2 = 3 - r2
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------ Name2--- Value2------
*23 56789012 56789012 567890123456 01234567 012345678901
NAME CP-2.2
ROWS
N z
L r1
L r2
COLUMNS
x1 z 2 r1 1
x1 r2 1
*
x2 z 3 r1 2
x2 r2 1
*
x3 z 5 r1 3
x3 r2 2
*
x4 z 4 r1 1
x4 r2 3
RHS
b r1 5
b r2 3
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 2.09 , 2.05 , 2.01 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME CP-2.2
At line 5 ROWS
At line 9 COLUMNS
At line 21 RHS
At line 24 ENDATA
Problem CP-2.2 has 2 rows, 4 columns and 8 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 2 (0) rows, 4 (0) columns and 8 (0) elements
0 Obj -0 Dual inf 10.642 (4)
2 Obj 8
Optimal - objective value 8
Optimal objective 8 - 2 iterations time 0.002
Clp:
0 r1 5 1
1 r2 3 1
0 x1 1 -7.9526954e-17
1 x2 2 1.282961e-16
2 x3 0 3.3210123e-16
3 x4 0 -1.2220844e-15
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
z, r1, and r2
are as expected.
If we chose a = 1 and b = 0, the corresponding
optimal solution is
x1 = 1, x4 = 0, x2 = 2, x3 = 0
which agrees with the Clp output.
maximize z = 3*x1 + x2
subject to s1 = - x1 + x2 - 1
s2 = x1 + x2 - 3
s3 = - 2*x1 - x2 + 4
x1, x2, s1, s2, s3 >= 0
Note that the basic solution corresponding to this dictionary
x1 = 0, x2 = 0, s1 = -1, s2 = -3, s3 = 4, z = 0
is not feasible
because s1 and s2 are less than zero.
maximize y = - x0
subject to s1 = x0 - x1 + x2 - 1
s2 = x0 + x1 + x2 - 3
s3 = x0 - 2*x1 - x2 + 4
x0, x1, x2, s1, s2, s3 >= 0
Note that in the basic solution, s2 has the smallest
(most negative) value.
Thus, if we pivot on the pair of variables (x0, s2),
the resulting basic solution will be feasible.
x0 = -x1 - x2 + s2 + 3
We replace all occurrences of x0 with the right hand side and obtain:
maximize y = - (-x1 - x2 + s2 + 3)
subject to s1 = (-x1 - x2 + s2 + 3) - x1 + x2 - 1
x0 = -x1 - x2 + s2 + 3
s3 = (-x1 - x2 + s2 + 3) - 2*x1 - x2 + 4
x0, x1, x2, s1, s2, s3 >= 0
maximize y = x1 + x2 - s2 - 3
subject to s1 = - 2*x1 + s2 + 2
x0 = - x1 - x2 + s2 + 3
s3 = - 3*x1 - 2*x2 + s2 + 7
x0, x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x0 = 3, x1 = 0, x2 = 0, s1 = 2, s2 = 0, s3 = 7, y = -3
x2 in the
auxiliary objective y is positive.
The corresponding feasibility constraint is
x2 = min( 3/1, 7/2 ) = 3
The corresponding pivot pair is (x2, x0).
The corresponding equation for x2 is
x2 = - x1 - x0 + s2 + 3
The corresponding dictionary is
maximize y = x1 - (x1 + x0 - s2 - 3) - s2 - 3
subject to s1 = - 2*x1 + s2 + 2
x0 = - x1 + (x1 + x0 - s2 - 3) + s2 + 3
s3 = - 3*x1 + 2*(x1 + x0 - s2 - 3) + s2 + 7
x0, x1, x2, s1, s2, s3 >= 0
maximize y = - x0
subject to s1 = - 2*x1 + s2 + 2
x2 = - x0 - x1 + s2 + 3
s3 = 2*x0 - x1 - s2 + 1
x0, x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x0 = 0, x1 = 0, x2 = 3, s1 = 2, s2 = 0, s3 = 1, y = 0
We note that x0 is zero.
Hence this must be an optimal value for the auxiliary problem
and a feasible point for the original problem.
x0 = 0,
are equivalent to the constraints in the original problem.
Thus the following problem is equivalent to the original problem.
maximize z = 3*x1 + x2
subject to s1 = - 2*x1 + s2 + 2
x2 = - x1 + s2 + 3
s3 = - x1 - s2 + 1
x1, x2, s1, s2, s3 >= 0
Now we use the constraint equations to replace the
basic variables in the objective; i.e.,
z = 3*x1 + (- x1 + s2 + 3)
The resulting feasible dictionary representation is
maximize z = 2*x1 + s2 + 3
subject to s1 = - 2*x1 + s2 + 2
x2 = - x1 + s2 + 3
s3 = - x1 - s2 + 1
x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x1 = 0, x2 = 3, s1 = 2, s2 = 0, s3 = 1, z = 3
s2 for our next pivot column.
The corresponding feasibility constraint is
s2 = 1
The corresponding pivot pair is (s2, s3).
The corresponding equation for s2 is
s2 = - x1 - s3 + 1
The corresponding dictionary is
maximize z = 2*x1 + (- x1 - s3 + 1) + 3
subject to s1 = - 2*x1 + (- x1 - s3 + 1) + 2
x2 = - x1 + (- x1 - s3 + 1) + 3
s2 = - x1 - s3 + 1
x1, x2, s1, s2, s3 >= 0
maximize z = x1 - s3 + 4
subject to s1 = - 3*x1 - s3 + 3
x2 = - 2*x1 - s3 + 4
s2 = - x1 - s3 + 1
x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x1 = 0, x2 = 4, s1 = 3, s2 = 1, s3 = 0, z = 4
x1 for our next pivot column.
The corresponding feasibility constraint is
x1 = min(3/3, 4/2, 1/1) = 1
We choose (x1, s2) for the corresponding pivot pair
(we could have chosen (x1, s1)).
The corresponding equation for x1 is
x1 = - s2 - s3 + 1
The corresponding dictionary is
maximize z = (- s2 - s3 + 1) - s3 + 4
subject to s1 = - 3*(- s2 - s3 + 1) - s3 + 3
x2 = - 2*(- s2 - s3 + 1) - s3 + 4
x1 = - s2 - s3 + 1
x1, x2, s1, s2, s3 >= 0
maximize z = - s2 - 2*s3 + 5
subject to s1 = 3*s2 + 2*s3 + 0
x2 = 2*s2 + s3 + 2
x1 = - s2 - s3 + 1
x1, x2, s1, s2, s3 >= 0
The corresponding basic feasible solution is
x1 = 1, x2 = 2, s1 = 0, s2 = 0, s3 = 0, z = 5
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
maximize 3*x1 + x2
subject to x1 - x2 <= - 1
- x1 - x2 <= - 3
2*x1 + x2 <= 4
x1 , x2 >= 0
The corresponding optimal solution is
x1 = 1, x2 = 2, r1 = -1, r2 = -3, r3 = 4
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------ Name2--- Value2------
*23 56789012 56789012 567890123456 01234567 012345678901
NAME CP-2.2
ROWS
N z
L r1
L r2
L r3
COLUMNS
x1 z 3 r1 1
x1 r2 -1 r3 2
*
x2 z 1 r1 -1
x2 r2 -1 r3 1
RHS
b r1 -1
b r2 -3
b r3 4
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 4.01 , 4.0 , 3.91 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME CP-2.2
At line 5 ROWS
At line 10 COLUMNS
At line 16 RHS
At line 20 ENDATA
Problem CP-2.2 has 3 rows, 2 columns and 6 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 0 (-3) rows, 0 (-2) columns and 0 (-6) elements
Empty problem - 0 rows, 0 columns and 0 elements
Optimal - objective value 5
After Postsolve, objective 5, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 5 - 0 iterations time 0.002, Presolve 0.00
Clp:
0 r1 -1 0.33333333
1 r2 -3 -0
2 r3 4 1.3333333
0 x1 1 1.6653345e-16
1 x2 2 5.5511151e-17
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
x1 x2 x3 x4 x5 x6 z b
0 0 2 1 0 0 0 1
2 -4 6 0 1 0 0 3
-1 3 4 0 0 1 0 2
2 -1 8 0 0 0 -1 0
The corresponding basic feasible solution is
x1 = 0, x2 = 0, x3 = 0, x4 = 1, x5 = 1, x6 = 1, z = 0
Note that if we choose x3 for the new basic variable,
its value after the pivot will be
x3 = min (1/2, 3/6, 2/4) = 1/2
The important point here is that if we increase x3 to 1/2,
the basic variables x4, x5, x6 will all be zero and hence
we could choose any one of them for the new non-basic variable.
(x3, x4).
The resulting tableau is:
x1 x2 x3 x4 x5 x6 z b
0, 0, 1, .5, 0, 0, 0, .5
2, -4, 0, -3, 1, 0, 0, 0
-1, 3, 0, -2, 0, 1, 0, 0
2, -1, 0, -4, 0, 0, -1, -4
The corresponding basic feasible solution is
x1 = 0, x2 = 0, x3 = .5, x4 = 0, x5 = 0, x6 = 0, z = 4
Note that x1 is the only possible choice for the new basic variable,
its value after the next pivot will be
x1 = 0/2 = 0
The important point here is that x1 will not increase
when we change the basis.
Hence the objective function value corresponding to the basic
solution for the new basis will be the same as the objective
function value for this basis.
(x1, x5).
The resulting tableau is:
x1 x2 x3 x4 x5 x6 z b
0 0 1 .5 0 0 0 .5
1 -2 0 -1.5 .5 0 0 0
0 1 0 -3.5 .5 1 0 0
0 3 0 -1 -1 0 -1 -4
The corresponding basic feasible solution is
x1 = 0, x2 = 0, x3 = .5, x4 = 0, x5 = 0, x6 = 0, z = 4
Note that x2 is the only possible choice for the new basic variable,
its value after the next pivot will be
x2 = 0/1 = 0
(x2, x6).
The resulting tableau is:
x1 x2 x3 x4 x5 x6 z b
0 0 1 0.5 0 0 0 .5
1 0 0 -8.5 1.5 2 0 0
0 1 0 -3.5 .5 1 0 0
0 0 0 9.5 -2.5 -3 -1 -4
The corresponding basic feasible solution is
x1 = 0, x2 = 0, x3 = .5, x4 = 0, x5 = 0, x6 = 0, z = 4
Note that x4 is the only possible choice for the new basic variable,
its value after the next pivot will be
x2 = .5/.5 = 1
(x4, x3).
The resulting tableau is:
x1 x2 x3 x4 x5 x6 z b
0 0 2 1 0 0 0 1
1 0 17 0 1.5 2 0 8.5
0 1 7 0 .5 1 0 3.5
0 0 -19 0 -2.5 -3 -1 -13.5
The corresponding basic feasible solution is
x1 = 8.5, x2 = 3.5, x3 = 0, x4 = 1, x5 = 0, x6 = 0, z = 13.5
Note that this is the optimal solution because
none of the coefficients in the last row are greater than zero.
\[
B : \{ 1 , \ldots , m \} \rightarrow \{ 1 , \ldots , n \}
\]
where
m
is the number of constraints in the tableau
and
n
is the number of variables.
The basis corresponding to an iteration of the simplex
method is the mapping
B
such that column
B(k)
of the Tableau contains the k-th column
of the
m \times m
identity matrix.
B
be that basis and
S \in \R^{(m+1) \times (n+2)}
,
T \in \R^{(m+1) \times (n+2)}
,
be the tableaus corresponding to the two iterations.
It follows that there is an invertible matrix
A \in \R^{m \times m}
such that
\[
A S = T
\]
For
k = 1 , \ldots , m
,
we use
e^k
to denote the k-th column of the
m \times m
identity matrix.
It follows that
e^k
is equal to column
B(k)
of both
S
and
T
.
Thus, for
i = 1, \ldots , m
,
\[
\begin{array}{rcl}
\sum_{j=1}^m A_{i,j} S_{j,B(k)} & = & T_{i,B(k)} \\
\sum_{j=1}^m A_{i,j} e_i^k & = & e_i^k \\
A_{i,k} & = & \left\{ \begin{array}{ll}
1 & {\rm if} \; i = k \\
0 & {\rm otherwise}
\end{array} \right.
\end{array}
\]
It follows that
A
is the identity matrix
and hence
S = T
.
n ! / (n-m) !
to be exact.
Thus the basis must repeat itself and hence
the entire tableau must repeat itself.
\newcommand{\notin}{
\mathml{ <mi mathvariant='normal'> &\#x02209; </mi> }
}
B^k : \{ 1 , \ldots , m \} \rightarrow \{ 1 , \ldots , n \}
to denote the basis corresponding to the k-th iteration of the
Simplex Algorithm.
We use
j \in B^k
to denote the fact that
j
is
in the range of
B^k
; i.e., there exists an
i
such that
j = B^k (i)
.
We use
B^{-k}
to denote the inverse of
B^k
(defined on the range of
B^k
); i.e., for
i = 1 , \ldots , m
,
B^{-k} [ B^k (i) ] = i
.
\[
\begin{array}{rcl}
x_{B^k (i)} & = & b^k_i - \sum_{j \notin B^k} A^k_{i,j} x_j
\hspace{1cm}
(i = 1 , \ldots , m)
\\
z & = & v^k + \sum_{j \notin B^k} c^k_j x_j
\end{array}
\]
where
A^k \in \R^{m \times n}
,
b^k \in \R^m
,
c^k \in \R^n
,
v^k \in \R
.
J(k)
as
the minimum column index in the set
\[
\left\{ j : c^k_j > 0 \right\}
\]
Choose the pivot row index
I(k)
such that
B^k [ I(k) ]
is the minimum column index in the set of indices
\[
\left\{
B^k (i) : i \in \{ 1, \ldots , m \} \; {\rm and} \; A^k_{i, J(k)} > 0
\right\}
\]
B^k
to be the same as
B^{k+\ell}
for some positive integer
\ell
.
B^0
is the same as
B^\ell
.
We will prove the theorem by showing that this leads to a contradiction.
Define the iteration
p
by
\[
J(p) = \max \{ J(k) : k = 1 , \ldots , \ell \}
\]
It follows that
J(p) \notin B^{p}
and
J(p) \in B^{p+1}
.
Thus there is an iteration
q
such that
J(p) \in B^{q}
and
J(p) \notin B^{q+1}
.
We now define the function
X : \R \rightarrow \R^n
\[
X_j ( \lambda ) = \left\{ \begin{array}{ll}
0
& {\rm if} \; j \notin B^q \; {\rm and} \; j \neq J(q)
\\
\lambda
& {\rm if} \; j = J(q)
\\
b^q_{B^{-q} (j)} - \lambda A^q_{B^{-q}(j) \; , \; J(q)}
& {\rm if} \; j \in B^q
\end{array} \right.
\]
(note
i = B^{-q} (j)
means that
B^q (i) = j
).
It follows that for
i = 1 , \ldots m
,
\[
X_{B^q (i)} ( \lambda )
=
b^q_i - \sum_{j \notin B^q} A^q_{i,j} X_j ( \lambda )
\]
Thus the objective function evaluated at
X_j ( \lambda )
must have the same value in the dictionary at iteration
p
and the dictionary at iteration
q
; i.e.,
\[
v^p + \sum_{j \notin B^p} c^p_j X_j ( \lambda )
=
v^q + \sum_{j \notin B^q} c^q_j X_j ( \lambda )
\]
The objective function value corresponding to the basic
feasible solution at iteration
k
is
v^k
.
In addition, the Simplex algorithm ensures that
v^{k+1} \geq v^k
.
On the other hand, the fact that
B^1 = B^\ell
ensures
that
v^1 = v^\ell
.
It follows that
v^1 = v^k
for all
k
and
\[
\sum_{j \notin B^q} c^q_j X_j ( \lambda )
=
\sum_{j \notin B^p} c^p_j X_j ( \lambda )
\]
If
X_j ( \lambda )
is a non-zero component of
X( \lambda )
,
either
j \in B^q
or
j = J(q)
.
Thus we have
\[
\begin{array}{rcl}
c^q_{J(q)} X_{J(q)} ( \lambda )
& = &
c^p_{J(q)} X_{J(q)} ( \lambda )
+
\sum_{j \in B^q} c^p_j X_j ( \lambda )
\\
\lambda \left[
c^q_{J(q)} - c^p_{J(q)} +
\sum_{j \in B^q} c^p_j A^q_{B^{-q} (j) \; , \; J(p)}
\right]
& = &
\sum_{j \in B^q} c^p_j b^q_{B^{-q} (j)}
\end{array}
\]
This equation holds for all
\lambda \in \R
, hence
\[
\begin{array}{rcl}
c^q_{J(q)} - c^p_{J(q)} +
\sum_{j \in B^q} c^p_j A^q_{B^{-q} (j) \; , \; J(p)}
=
0
\end{array}
\]
We know that
c^q_{J(q)} > 0
because
J(q)
is chosen as the pivot column at iteration
q
.
We also know that
c^p_{J(q)} \leq 0
because
J(p)
is chosen as the pivot column at iteration
p
and
J(p) > J(q)
.
Thus, it follows that there is a column index
N
such that
\[
c^p_N A^q_{B^{-q} (N) \; , \; J(p)} \; < \; 0
\]
We know that
J(p) \in B^q
and
J(p) \notin B^{q+1}
It follows that
\[
A^q_{B^{-q} [ J(p) ] \; , \; J(p)} \; > \; 0
\]
We also know that
c^p_{J(p)} > 0
thus,
N \neq J(p)
.
We note also have that
c^p_j
is zero for all
j \in B^p
whence,
N \notin B^p
.
We also have that
N \in B^q
(because
c_N^q \neq 0
), whence
N = J(k)
for some
k
and
N < J(p)
.
It now follows that
c^p_N \leq 0
(otherwise
it would have been chosen at iteration
p
as
J(p)
) and thus
\[
A^q_{B^{-q} (N) \; , \; J(p)} \; > \; 0
\]
Thus,
N < J(p)
and
N
is in the set
\[
\left\{
B^q (i) : i \in \{ 1, \ldots , m \} \; {\rm and} \; A^q_{i, J(p)} > 0
\right\}
\]
This contradicts the fact that
J(p)
is the minimal element
of the set above
(which follows form
J(p) \in B^q
and
J(p) \notin B^{q+1}
).
This contradiction completes the proof of the theorem.
maximize z subject to:
x5 = -.5*x1 + 5.5*x2 + 2.5*x3 - 9*x4
x6 = -.5*x1 + 1.5*x2 + .5*x3 - x4
x7 = 1 - x1
z = 10*x1 - 57*x2 - 9*x3 - 24*x4
(x1, x2, x3, x4, x5, x6, x7) >= 0
z equation.
Thus, so long at the column candidate with the largest coefficient
is also the column candidate with the smallest index,
the result will be the same as for Bland's rule.
z = 10*x1 - 57*x2 - 9*x3 - 24*x4
Hence is only one column with z coefficient greater than zero.
Hence the pivot with Bland's rule would be the same as for the example.
z = 53*x2 + 41*x3 - 204*x4 - 20*x5
Hence there are two candidate columns, the one corresponding to x2
and the one corresponding to x3.
The one with the smaller index is also the one with the larger
coefficient.
Hence the pivot with Bland's rule would be the same as for the example.
z = 14.5*x3 - 98*x4 - 6.75*x5 - 13.25*x6
Hence is only one column with z coefficient greater than zero.
Hence the pivot with Bland's rule would be the same as for the example.
z = - 29*x1 + 18*x4 + 15*x5 - 93*x6
Hence there are two candidate columns, the one corresponding to x4
and the one corresponding to x5.
The one with the smaller index is also the one with the larger
coefficient.
Hence the pivot with Bland's rule would be the same as for the example.
z = -20*x1 - 9*x2 + 10.5*x5 - 70.5*x6
Hence is only one column with z coefficient greater than zero.
Hence the pivot with Bland's rule would be the same as for the example.
x5 = 4*x1 - 8*x2 - 2*x3 + 9*x6
x4 = - .5*x1 + 1.5*x2 + .5*x3 - x6
x7 = 1 - x1
z = 22*x1 - 93*x2 - 21*x3 + 24*x6
The corresponding tableau is
x1 x2 x3 x4 x5 x6 x7 z b
-4.00 8.00 2.00 0.00 1.00 -9.00 0.00 0.00 0.00
0.50 -1.50 -0.50 1.00 0.00 1.00 0.00 0.00 0.00
1.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 1.00
22.00 -93.00 -21.00 0.00 0.00 24.00 0.00 -1.00 0.00
(x6, x4).
The result of this pivot on Tableau A is:
x1 x2 x3 x4 x5 x6 x7 z b
0.50 -5.50 -2.50 9.00 1.00 0.00 0.00 0.00 0.00
0.50 -1.50 -0.50 1.00 0.00 1.00 0.00 0.00 0.00
1.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 1.00
10.00 -57.00 -9.00 -24.00 0.00 0.00 0.00 -1.00 0.00
(x1, x4).
The result of this pivot on Tableau A we call Tableau B:
x1 x2 x3 x4 x5 x6 x7 z b
0.00 -4.00 -2.00 8.00 1.00 -1.00 0.00 0.00 0.00
1.00 -3.00 -1.00 2.00 0.00 2.00 0.00 0.00 0.00
0.00 3.00 1.00 -2.00 0.00 -2.00 1.00 0.00 1.00
0.00 -27.00 1.00 -44.00 0.00 -20.00 0.00 -1.00 0.00
(x3, x7).
The result of this pivot on Tableau B we call Tableau C:
x1 x2 x3 x4 x5 x6 x7 z b
0.00 2.00 0.00 4.00 1.00 -5.00 2.00 0.00 2.00
1.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 1.00
0.00 3.00 1.00 -2.00 0.00 -2.00 1.00 0.00 1.00
0.00 -30.00 0.00 -42.00 0.00 -18.00 -1.00 -1.00 -1.00
We see that this is the basic feasible solution
x1 = 1, x2 = 0, x3 = 1, x4 = 0, x5 = 2, x6 = 0, x7 = 0
is optimal and the corresponding objective value is one.
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 4.0 , 4.02 , 3.95 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME Cycle
At line 5 ROWS
At line 10 COLUMNS
At line 22 RHS
At line 26 ENDATA
Problem Cycle has 3 rows, 4 columns and 9 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Clp:Presolve 2 (-1) rows, 3 (-1) columns and 6 (-3) elements
0 Obj -0 Dual inf 16.0282 (1)
2 Obj 1
Optimal - objective value 1
After Postsolve, objective 1, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 1 - 2 iterations time 0.002, Presolve 0.00
Clp:
0 r1 -2 -0
1 r2 8.0135898e-13 18
2 r3 1 1
0 x1 1 -1.110223e-15
1 x2 0 -30
2 x3 1 0
3 x4 0 -42
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Problem at top of page 31 in Chvatal
maximize 10*x1 - 57*x2 - 9*x3 - 24*x4
subject to .5*x1 - 5.5*x2 - 2.5*x3 + 9*x4 <= 0
.5*x1 - 1.5*x2 - .5*x3 + x4 <= 0
x1 <= 1
x1 , x2 , x3 , x4 >= 0
The solution is x1 = 1, x2 = 0, x3 = 1, x4 = 0
The row values are r1 = -2, r2 = 0, r3 = 1
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------ Name2--- Value2------
*23 56789012 56789012 567890123456 01234567 012345678901
NAME Cycle
ROWS
N z
L r1
L r2
L r3
COLUMNS
x1 z 10 r1 .5
x1 r2 .5 r3 1
*
x2 z -57 r1 -5.5
x2 r2 -1.5
*
x3 z -9 r1 -2.5
x3 r2 -.5
*
x4 z -24 r1 9
x4 r2 1
RHS
b r1 0
b r2 0
b r3 1
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalPivot dantzig
primalSimplex
solution -
]]></param>
</document>
\R_+^n
to denote the set of
x \in \R^n
such that
x \geq 0
; i.e.,
x_j \geq 0
for
j = 1 , \ldots , n
.
\[
\begin{array}{rrrrrrrrrr}
{\rm maximize} & 4 x_1 & + & x_2 & + & 5 x_3 & + & 3 x_4 & & \\
{\rm subject \; to} & x_1 & - & x_2 & - & x_3 & + & 3 x_4 & \leq & 1 \\
& 5 x_1 & + & x_2 & + & 3 x_3 & + & 8 x_4 & \leq & 55 \\
& - x_1 & + & 2 x_2 & + & 3 x_3 & - & 5 x_4 & \leq & 3 \\
& x_1 & , & x_2 & , & x_3 & , & x_4 & \geq & 0
\end{array}
\]
The feasible set for this problem is defined by
\[
X = \left\{ x \in \R_+^4 \; : \; \begin{array}{rrrrrrrrr}
x_1 & - & x_2 & - & x_3 & + & 3 x_4 & \leq & 1 \\
5 x_1 & + & x_2 & + & 3 x_3 & + & 8 x_4 & \leq & 55 \\
- x_1 & + & 2 x_2 & + & 3 x_3 & - & 5 x_4 & \leq & 3
\end{array} \right\}
\]
The extended primal objective function for this problem
f : \R_+^4 \rightarrow \R \cup \{ - \infty \}
is defined by
\[
f(x) = \left\{ \begin{array}{ll}
4 x_1 + x_2 + 5 x_3 + 3 x_4 & {\rm if} \; x \in X \\
- \infty & {\rm otherwise}
\end{array} \right.
\]
Solving the primal problem is equivalent to finding
an argument
x
that maximizes the value of
f(x)
with respect to
x \in \R_+^4
.
L : \R_+^4 \times \R_+^3 \rightarrow \R
is defined by
\[
\begin{array}{rcl}
L(x,y) & = &
4 x_1 + x_2 + 5 x_3 + 3 x_4
\\
& + &
y_1 ( 1 - x_1 + x_2 + x_3 - 3 x_4 )
\\
& + &
y_2 ( 55 - 5 x_1 - x_2 - 3 x_3 - 8 x_4 )
\\
& + &
y_3 ( 3 + x_1 - 2 x_2 - 3 x_3 + 5 x_4 )
\end{array}
\]
It follows from this definition that for all
x \in \R_+^4
\[
f(x) = \inf \; L(x, y) \; {\rm with \; respect \; to} \; y \in \R_+^3
\]
Regrouping terms in the definition of
L
,
we have
\[
\begin{array}{rcl}
L(x,y)
& = & y_1 + 55 y_2 + 3 y_3
\\
& + & x_1 ( 4 - y_1 - 5 y_2 + y_3 )
\\
& + & x_2 ( 1 + y_1 - y_2 - 2 y_3 )
\\
& + & x_3 ( 5 + y_1 - 3 y_2 - 3 y_3 )
\\
& + & x_4 ( 3 - 3 y_1 - 8 y_2 + 5 y_3 )
\end{array}
\]
g : \R_+^3 \rightarrow \R \cup \{ + \infty \}
is defined by
\[
g(y) = \sup \; L(x, y) \; {\rm with \; respect \; to} \; x \in \R_+^4
\]
The corresponding feasible set for the dual problem is
\[
Y = \left\{ y \in \R_+^3 \; : \; \begin{array}{rrrrrrr}
y_1 & + & 5 y_2 & + & y_3 \geq & 4 \\
- y_1 & + & y_2 & + & 2 y_3 \geq & 1 \\
- y_1 & + & 3 y_2 & + & 3 y_3 \geq & 5 \\
3 y_1 & + & 8 y_2 & - & 5 y_3 \geq & 3
\end{array} \right\}
\]
And the dual objective can be represented by
\[
g(y) = \left\{ \begin{array}{ll}
y_1 + 55 y_2 + 3 y_3 & {\rm if} \; y \in Y \\
+ \infty & {\rm otherwise}
\end{array} \right.
\]
The dual problem is to find an argument value
y
that minimizes
g(y)
with respect to
y \in \R_+^3
.
This is equivalent to the following problem:
\[
\begin{array}{rrrrrrrrrr}
{\rm minimize} & y_1 & + & 55 y_2 & + & 3 y_3 & & \\
{\rm subject \; to} & y_1 & + & 5 y_2 & + & y_3 & \geq & 4 \\
- y_1 & + & y_2 & + & 2 y_3 & \geq & 1 \\
- y_1 & + & 3 y_2 & + & 3 y_3 & \geq & 5 \\
3 y_1 & + & 8 y_2 & - & 5 y_3 & \geq & 3 \\
y_1 & , & y_2 & , & y_3 & \geq & 0
\end{array}
\]
A \in \R^{m \times n}
,
b \in \R^m
, and
c \in \R^n
,
the corresponding primal problem is
\[
\begin{array}{ll}
{\rm maximize} & c^T x \; {\rm with \; respect \; to} \; x \in \R_+^n
\\
{\rm subject \; to} & A x \leq b
\end{array}
\]
The extended primal objective function
f : \R_+^n \rightarrow \R \cup \{ - \infty \}
is defined by
\[
f(x) = \left\{ \begin{array}{ll}
c^T x & {\rm if} \; b - A x \geq 0 \\
- \infty & {\rm otherwise}
\end{array} \right.
\]
Solving the primal problem is equivalent to finding
an argument
x
that maximizes the value of
f(x)
with respect to
x \in \R_+^n
.
L : \R_+^n \times \R_+^m \rightarrow \R
is defined by
\[
\begin{array}{rcl}
L(x, y)
& = & c^T x + y^T ( b - A x )
\\
& = & b^T y + x^T ( c - A^T y )
\end{array}
\]
It follows that
\[
f(x) = \inf \; L(x, y) \; {\rm with \; respect \; to} \; y \in \R_+^m
\]
g : \R_+^m \rightarrow \R \cup \{ + \infty \}
is defined by
\[
g(y) = \sup \; L(x, y) \; {\rm with \; respect \; to} \; x \in \R_+^n
\]
It follows that
\[
g(y) = \left\{ \begin{array}{ll}
b^T y & {\rm if} \; c - A^T y \leq 0 \\
+ \infty & {\rm otherwise}
\end{array} \right.
\]
The dual problem is to find an argument value
y
that minimizes
g(y)
with respect to
y \in \R_+^m
.
This is equivalent to the following problem:
\[
\begin{array}{ll}
{\rm minimize} & b^T y \; {\rm with \; respect \; to} \; y \in \R_+^m
\\
{\rm subject \; to} & A^T y \geq c
\end{array}
\]
\hat{x} \in \R_+^n
and
\hat{y} \in \R_+^m
,
the corresponding duality gap is
g( \hat{y} ) - f( \hat{x} )
.
The duality gap is always non-negative and if it is zero,
\hat{x}
solves the primal problem
and
\hat{y}
solves the dual problem.
\[
\begin{array}{rcl}
g( \hat{y} )
& = &
\sup L( x , \hat{y} ) \; {\rm with \; respect \; to} \; x \in \R_+^n
\\
& \geq &
L( \hat{x} , \hat{y} )
\\
& \geq &
\inf \; L( \hat{x} , y ) \; {\rm with \; respect \; to} \; y \in \R_+^m
\\
& = &
f( \hat{x} )
\end{array}
\]
Thus we conclude that the duality gap is non-negative.
Further if it equals zero then for all
x \in \R_+^n
and
y \in \R_+^m
\[
\begin{array}{rcccl}
g( y ) & \geq & f( \hat{x} ) & = & g( \hat{y} )
\\
f( \hat{x} ) & = & g( \hat{y} ) & \geq & f( x )
\end{array}
\]
which completes the proof of the lemma.
A \in \R^{m \times n}
,
b \in \R^m
,
and
c \in \R^n
define the
primal problem: 3.2.a
with extended objective
f(x)
and the
dual problem: 3.2.c
with extended objective
g(y)
.
Q \in \R^{m \times m}
to be the identity matrix and the slack vector
s \in \R_m
are defined by
\[
b = A x + Q s
\]
The scalar
e \in \R
and the
coefficient vector
y \in \R^m
are defined by
e = 0
,
y = 0
.
The primal problem has the following tableau form:
\[
\begin{array}{llclcl}
{\rm maximize} & z
\\
{\rm subject \; to} & b = A x & + & Q s
\\
& e = c^T x & - & y^T s & - & z
\\
& x \geq 0 & , & s \geq 0
\end{array}
\]
\hat{c} \leq 0
and
\hat{y} \geq 0
,
means that the Simplex method has reached a point
where all the objective coefficients are negative.
In addition, the objective coefficients corresponding
to the basic variables are all zero, hence
\[
0 = \hat{c}^T \hat{x} - \hat{y}^T \hat{s}
\]
were
( \hat{x} , \hat{s} )
is the basic feasible
solution corresponding to the tableau.
x \in \R^n
,
s \in \R^m
,
and
z \in \R
satisfies the constraints in the tableau above
if and only if it satisfies the constraints in the following form:
\[
\begin{array}{llclcl}
{\rm maximize} & z
\\
{\rm subject \; to} & \hat{b} = \hat{A} x & + & \hat{Q} s
\\
& \hat{e} = \hat{c}^T x & - & \hat{y}^T s & - & z
\\
& x \geq 0 & , & s \geq 0
\end{array}
\]
Further suppose,
\hat{c} \leq 0
,
\hat{y} \geq 0
, and there is a feasible pair
( \hat{x} , \hat{s} )
such that
\[
0 = \hat{c}^T \hat{x} - \hat{y}^T \hat{s}
\]
It follows that
\hat{x}
solves the primal problem
and
\hat{y}
solves the dual problem.
Q
is the identity matrix,
d = 0
, and
e = 0
.
Thus for all
x \in \R_+^n
, by setting
s = b - A x
we have
\[
\begin{array}{rcl}
\sum_{j=1}^n c_j x_j
& = &
- \hat{e} + \sum_{j=1}^n \hat{c}_j x_j - \sum_{i=1}^m \hat{y}_i s_i
\\
& = &
- \hat{e}
+ \sum_{j=1}^n \hat{c}_j x_j
- \sum_{i=1}^m \hat{y}_i \left( b_i - \sum_{j=1}^n A_{i,j} x_j \right)
\\
\sum_{i=1}^m b_i \hat{y}_i + \hat{e}
& = &
\sum_{j=1}^n \left(
- c_j + \hat{c}_j + \sum_{i=1}^m \hat{y}_i A_{i,j}
\right) x_j
\hspace{1cm} (\star)
\end{array}
\]
From equation
(\star)
, choosing
x = 0
, we obtain
\[
\begin{array}{rcl}
\sum_{i=1}^m b_i \hat{y}_i + \hat{e} & = & 0
\\
\sum_{i=1}^m b_i \hat{y}_i & = & - \hat{e}
\end{array}
\]
Form equation
(\star)
, choosing
x = 0
except for the j-th component which is one,
we obtain the following equation for
j = 1 , \ldots , n
:
\[
\begin{array}{rcl}
0 & = & - c_j + \hat{c}_j + \sum_{i=1}^m \hat{y}_i A_{i,j}
\\
c_j & \leq & \sum_{i=1}^m \hat{y}_i A_{i,j}
\end{array}
\]
Note that we used
\hat{c}_j \leq 0
to obtain the
inequality above.
It follows that
\hat{y}
is dual feasible,
\hat{x}
is primal feasible, and
\[
f( \hat{x} ) =
- \hat{e} + \hat{c}^T \hat{x} - \hat{y}^T \hat{s}
=
- \hat{e}
=
b^T \hat{y}
=
g( \hat{y} )
\]
The conclusion of the theorem now follows from the
Duality Gap Lemma: 3.2.d
.
A \in \R^{m \times n}
,
b \in \R^m
,
and
c \in \R^n
define the
primal problem: 3.2.a
with extended objective
f(x)
and the
dual problem: 3.2.c
with extended objective
g(y)
.
\hat{x} \in \R_+^n
and
\hat{y} \in \R_+^m
satisfy the complementary slackness condition if the following conditions
hold:
for
i = 1 , \ldots , m
,
and
j = 1 , \ldots , n
\[
\begin{array}{rcl}
0 & = & \left( b_i \; - \; \sum_{k=1}^n A_{i,k} \hat{x}_k \right) \hat{y}_i
\\
0 & = & \left( \sum_{k=1}^m \hat{y}_k A_{k,j} \; - \; c_j \right) \hat{x}_j
\end{array}
\]
\hat{x} \in \R_+^n
is feasible for the primal problem,
\hat{y} \in \R_+^m
is feasible for the dual problem,
and they satisfy the complementary slackness condition.
It follows that the corresponding
duality gap: 3.2.d
is zero.
\[
\begin{array}{rcl}
b_i \hat{y}_i & = & \hat{y}_i \left( \sum_{k=1}^n A_{i,k} \hat{x}_k \right)
\\
c_j \hat{x}_j & = & \left( \sum_{k=1}^m \hat{y}_k A_{k,j} \right) \hat{x}_j
\end{array}
\]
The vector
\hat{x} \in \R_+^n
is feasible for the primal problem
and
\hat{y} \in \R_+^m
is feasible for the dual problem.
Hence,
\[
\begin{array}{rcl}
g(\hat{y}) & = &
\sum_{i=1}^m \hat{y}_i \left( \sum_{k=1}^n A_{i,k} \hat{x}_k \right)
\\
f(\hat{x}) & = &
\sum_{j=1}^n \left( \sum_{k=1}^m \hat{y}_k A_{k,j} \right) \hat{x}_j
\end{array}
\]
Rearranging the indexing we conclude that
\[
\begin{array}{rcl}
g(\hat{y})
= \sum_{i=1}^m \sum_{j=1}^n \hat{y}_i A_{i,j} \hat{x}_j
= f(\hat{x})
\end{array}
\]
It follows from the
and
\hat{y}
solves the dual problem.
\hat{x} \in \R_+^n
and
\hat{y} \in \R_+^m
are such that the corresponding
duality gap: 3.2.d
is zero.
It follows that they satisfy the complementary slackness condition.
g(y)
are plus infinity
and the only infinite values for
f(x)
are minus infinity.
Thus, the duality gap being zero implies that
\hat{x} \in \R_+^n
is primal feasible,
\hat{y} \in \R_+^m is dual feasible
, and
\[
\sum_{j=1}^n c_j \hat{x}_j = \sum_{i=1}^m b_i \hat{y}_i
\]
We now suppose that the first complementary condition is false; i.e.,
there is an index
I
such that
\[
0 \neq \left( b_I \; - \; \sum_{j=1}^n A_{I,j} \hat{x}_j \right) \hat{y}_I
\]
It follows from the fact that
\hat{x}
is feasible
and
\hat{y} \in \R_+^m
that
\[
\begin{array}{rcl}
0
& < & \left( b_I \; - \; \sum_{j=1}^n A_{I,j} \hat{x}_j \right) \hat{y}_I
\\
b_I \hat{y}_I
& > & \sum_{j=1}^n \hat{y}_I A_{I,j} \hat{x}_j
\\
\sum_{i=1}^m b_i \hat{y}_i
& > & \sum_{i=1}^m \sum_{j=1}^n \hat{y}_i A_{i,j} \hat{x}_j
\\
& > & \sum_{j=1}^n \hat{x}_j \sum_{i=1}^m \hat{y}_i A_{i,j}
\end{array}
\]
We now apply the fact that
\hat{y}
is feasible to conclude that
\[
\sum_{i=1}^m b_i \hat{y}_i > \sum_{j=1}^n \hat{x}_j c_j
\]
Which contradicts the fact that the duality gap is zero.
Thus the first complementary condition must be satisfied for all indices.
We now suppose that the second complementary condition is false; i.e.,
there is an index
J
such that
\[
0 \neq \left( \sum_{i=1}^n \hat{y}_i A_{i,J} \; - \; c_J \right) \hat{x}_J
\]
It follows from the fact that
\hat{y}
is feasible
and
\hat{x} \in \R_+^n
that
\[
\begin{array}{rcl}
0
& < & \left( \sum_{i=1}^n \hat{y}_i A_{i,J} \; - \; c_J \right) \hat{x}_J
\\
c_J \hat{x}_J
& < & \sum_{i=1}^m \hat{y}_i A_{i,J} \hat{x}_J
\\
\sum_{j=1}^n c_j \hat{x}_j
& < & \sum_{j=1}^n \sum_{i=1}^m \hat{y}_i A_{i,j} \hat{x}_j
\\
& < & \sum_{i=1}^m \hat{y}_i \sum_{j=1}^n A_{i,j} \hat{x}_j
\end{array}
\]
We now apply the fact that
\hat{x}
is feasible to conclude that
\[
\sum_{j=1}^n c_j \hat{x}_j
<
\sum_{i=1}^m \hat{y}_i b_i
\]
Which contradicts the fact that the duality gap is zero.
Thus the second complementary condition must be satisfied for all indices.
This completes the proof.
\[
\begin{array}{c}
\begin{array}{lll}
{\rm maximize} & c^T x
\\
{\rm subject \; to} & A x \leq b & x \in \R_+^3
\end{array}
\\
{\rm where} \;
A = \left( \begin{array}{cccccc}
2 & 3 & 1 \\
4 & 1 & 2 \\
3 & 4 & 2
\end{array} \right)
\; , \;
b = \left( \begin{array}{ccc}
5 \\
11 \\
8
\end{array} \right)
\; , \;
c = \left( \begin{array}{ccc}
5 \\
4 \\
3
\end{array} \right)
\end{array}
\]
\hat{x} = (2, 0, 1)^T
is a solution
of this problem.
\hat{y} = (1, 0, 1)^T
was computed by hand
during Quiz0719: 7.4
.
Clp:
0 r1 5 1
1 r2 10 -0
2 r3 8 1
0 x1 2 -2.8223853e-16
1 x2 0 -3
2 x3 1 5.647295e-16
Clp:
This output has the following significance:
\[
\begin{array}{rclcrcl}
5 & = & \sum_{j=1}^3 A_{1,j} \hat{x}_j & \; & \hat{y}_1 & = & 1 \\
10 & = & \sum_{j=1}^3 A_{2,j} \hat{x}_j & \; & \hat{y}_2 & = & 0 \\
8 & = & \sum_{j=1}^3 A_{3,j} \hat{x}_j & \; & \hat{y}_3 & = & 1 \\
2 & = & \hat{x}_1 & \; & c_1 - \sum_{i=1}^3 \hat{y}_i A_{i,1} & = & 0 \\
0 & = & \hat{x}_2 & \; & c_2 - \sum_{i=1}^3 \hat{y}_i A_{i,2} & = & -3 \\
1 & = & \hat{x}_3 & \; & c_3 - \sum_{i=1}^3 \hat{y}_i A_{i,3} & = & 0
\end{array}
\]
\newcommand{\notin}{ \mathml{&\#x02209;} }
\beta : \{ 1 , \ldots , m \} \rightarrow \{ 1 , \ldots , n \}
,
a matrix
M \in \R^{m \times n}
,
and a column vector
v \in \R^n
,
we define the matrix
M_\beta \in \R^{m \times m}
,
the column vector
M_k \in \R^m
, and
the column vector
v_\beta \in \R^m
, by
\[
M_\beta = \left( \begin{array}{ccc}
M_{1,\beta(1)} & \cdots & M_{1,\beta(m)} \\
\vdots & \ddots & \vdots \\
M_{m,\beta(1)} & \cdots & M_{m,\beta(m)}
\end{array} \right)
\; , \;
M_k = \left( \begin{array}{c}
M_{1,k} \\
\vdots \\
M_{m,k}
\end{array} \right)
\; , \;
v_\beta = \left( \begin{array}{c}
v_{\beta(1)} \\
\vdots \\
v_{\beta(m)}
\end{array} \right)^T
\]
We use the notation
j \in \beta
to denote the condition that
j
is in the range of
\beta
; i.e.,
there exists an
i
such that
j = \beta(i)
.
A \in \R^{m \times n}
,
a vector
b \in \R^m
,
a vector
\Delta b \in \R^m
,
and a vector
c \in \R^n
.
The corresponding
primal problem: 3.2.a
is
\[
\begin{array}{ll}
{\rm maximize} & c^T x \; {\rm with \; respect \; to} \; x \in \R_+^n
\\
{\rm subject \; to} & A x \leq ( b + \Delta b)
\end{array}
\]
We introduce the objective
z \in \R
,
the slack variables
s \in \R^m
,
and the combined variable vector
u \in \R^{n + m}
defined by
\[
\begin{array}{rcl}
z & = & c^T x \\
s & = & b + \Delta b - A x \\
u & = & \left( \begin{array}{c} x \\ s \end{array} \right)
\end{array}
\]
We define the tableau representation by
T \in \R^{m \times (n+m)}
and
d \in \R^{n+m}
by
\[
T = [ A \; | \; I ] \; , \; d^T = ( c^T , 0 , \cdots , 0 )
\]
where
I \in \R^{m \times m}
is the identity matrix.
It follows that our primal problem is to maximize
z
with respect to
u \in \R_+^{n+m}
and subject to
\[
\begin{array}{rcrrl}
T u & & & = & b + \Delta b \\
d^T u & - & z & = & 0
\end{array}
\]
We use
B : \{ 1 , \ldots , m \} \rightarrow \{ 1 , \ldots , n + m \}
to denote the current basis and
define the non-basis mapping
N : \{ 1 , \ldots , n \} \rightarrow \{ 1 , \ldots , n + m \}
by
\[
N(k) = \min \left\{ j \left| \begin{array}{l}
j \notin B \\
j \neq N( \ell ) \; {\rm for} \; \ell = 1 , \ldots , k - 1
\end{array} \right. \right\}
\]
z
with respect to
u \in \R_+^{n+m}
and subject to
\[
\begin{array}{rrrrrrl}
T_B u_B & + & T_N u_N & & & = & b + \Delta b \\
d_B^T u_B & + & d_N^T u_N & - & z & = & 0
\end{array}
\]
The simplex method solves for the basic variables
u_B
in terms of the other variables:
\[
\begin{array}{rrrrrrl}
u_B & + & T_B^{-1} T_N u_N & & & = & T_B^{-1} ( b + \Delta b ) \\
d_B^T u_B & + & d_N^T u_N & - & z & = & 0
\end{array}
\]
It also zeros out the coefficient of
u_B
in the row
in terms of the other variables.
The is done by multiplying the first
m
rows by
d_B^T
and subtracting the result from the bottom row.
\[
\begin{array}{rrrrrrrl}
u_B
& + & T_B^{-1} T_N u_N & & & = & T_B^{-1} ( b + \Delta b)
\\
& + &
( d_N^T - d_B^T T_B^{-1} T_N ) u_N & - & z & = &
- d_B^T T_B^{-1} (b + \Delta b)
\end{array}
\hspace{1cm} ( \star )
\]
We use
\hat{z}( \Delta b )
to represent
the value of
z
corresponding to the
basic solution (
u_N = 0
) for
b + \Delta b
.
It follows that
\[
\hat{z}( \Delta b ) - \hat{z}(0)
=
d_B^T T_B^{-1} \Delta b
\]
\hat{x} ( \Delta b ) \in \R^n
and
\hat{s} ( \Delta b ) \in \R^m
to be the basic solution corresponding to the tableau
(\star)
;
i.e.,
\[
\begin{array}{rcl}
\hat{x} ( \Delta b )_j
& = & \left\{ \begin{array}{ll}
[ T_B^{-1} (b + \Delta b) ]_i
& {\rm if} \; j = B(i) \; {\rm for \; some} \; i \\
0
& {\rm if} \; j \in N
\end{array} \right.
\\
\hat{s} ( \Delta b )_i
& = & \left\{ \begin{array}{ll}
[ T_B^{-1} (b + \Delta b) ]_k
& {\rm if} \; n + i = B(k) \; {\rm for \; some} \; k \\
0
& {\rm if} \; n + i \in N
\end{array} \right.
\end{array}
\]
We define
\hat{c} \in \R^n
and
\hat{y} \in \R^m
to be the objective coefficients of
x
and
minus the objective coefficient of
s
in the tableau
(\star)
;
i.e.,
\[
\begin{array}{rcl}
\hat{c}_j & = & \left\{ \begin{array}{ll}
( d_N^T - d_B^T T_B^{-1} T_N )_k
& {\rm if} \; j = N(k) \; {\rm for \; some} \; k \\
0
& {\rm if} \; j \in B
\end{array} \right.
\\
\hat{y}_i & = & \left\{ \begin{array}{ll}
( d_B^T T_B^{-1} T_N - d_N^T )_k
& {\rm if} \; n + i = N(k) \; {\rm for \; some} \; k \\
0
& {\rm if} \; n + i \in B
\end{array} \right.
\end{array}
\]
\hat{c} \leq 0
,
\hat{x} ( \Delta b ) \geq 0
,
\hat{s} ( \Delta b ) \geq 0
, and
\hat{y} \geq 0
,
then
\hat{x} ( \Delta b )
solves the primal problem
(that corresponds to
\Delta b
)
and
\hat{y}
solves the dual problem.
j = 1 , \ldots , n
,
\hat{c}_j \hat{x} ( \Delta b)_j = 0
.
We also have
for
i = 1 , \ldots , m
,
\hat{y}_i \hat{s} ( \Delta b)_i = 0
.
The conclusion of the lemma now follow from the
Duality Theorem: 3.3
.
\[
\hat{y}^T = d_B^T T_B^{-1}
\]
i + n = N(k)
for some
k
\[
\begin{array}{rcl}
y_i
& = & ( d_B^T T_B^{-1} T_N - d_N^T )_k
\\
& = & d_B^T T_B^{-1} T_{N(k)} - d_{N(k)}
\\
& = & d_B^T T_B^{-1} I_i
\\
& = & ( d_B^T T_B^{-1} )_i
\end{array}
\]
If
i + n = B(k)
for some
k
\[
\begin{array}{rcl}
T_B^{-1} T_B & = & I
\\
T_B^{-1} I_i & = & I_k
\\
d_B^T T_B^{-1} I_i & = & d_B^T I_k
\\
( d_B^T T_B^{-1} )_i & = & d_{B(k)} = 0 = y_i
\end{array}
\]
(\star)
with
\Delta b = 0
is feasible, optimal, and non-degenerate.
It follows that there is an
\delta > 0
such that
for all
| \Delta b | < \delta
,
\hat{x} ( \Delta b)
solves the primal problem
(corresponding to
\Delta b
),
\hat{y}
solves the dual problem,
and
\[
c^T \hat{x} ( \Delta b ) - c^T \hat{x} (0) = \hat{y}^T \Delta b
\]
\[
c^T \hat{x} ( \Delta b ) - c^T \hat{x} (0)
=
\hat{z} ( \Delta b ) - \hat{z} (0)
=
\hat{y}^T \Delta b
\]
Hence, it suffices to show that
\hat{x} ( \Delta b )
is optimal for the corresponding primal problem
and
\hat{y}
is optimal for the dual.
Using the Optimality Lemma: 3.6.e
,
it suffices to show that
\hat{c} \leq 0
,
\hat{x} ( \Delta b ) \geq 0
,
\hat{s} ( \Delta b ) \geq 0
, and
\hat{y} \geq 0
.
The solution corresponding to
\Delta b = 0
is non-degenerate
implies that there is a
\varepsilon > 0
such that
T_B^{-1} b \geq \varepsilon
; i.e.,
all its components are greater than or equal
\varepsilon
.
Suppose that there is an index
j
such that
\hat{c}_j > 0
or
an index
i
with
\hat{y}_i < 0
.
It would follow from
T_B^{-1} b > 0
that one
iteration of the Simplex algorithm,
applied to
(\star)
with
\Delta b = 0
,
would obtain a basic feasible
solution that had a higher objective value than the value
corresponding to
\hat{x} (0)
.
This contradicts the assumption of the theorem and
we conclude that
\hat{c} \leq 0
and
\hat{y} \geq 0
.
The mapping
\hat{x} (0) \geq \varepsilon
and
\hat{s} (0) \geq \varepsilon
.
Hence there is a
\delta > 0
such that for
| \Delta b | < \delta
,
\hat{x} ( \Delta ) \geq 0
and
\hat{s} (0) \geq 0
.
This completes the proof of the theorem.
m(=)
,
a number of inequality constraints
m(\leq)
,
a number of free variables
n(\pm)
,
and a number of non-negative variables
n(+)
.
These constraints are define by
A_{=,\pm} \in \R^{m(=) \times n(\pm)}
,
A_{=,+} \in \R^{m(=) \times n(+)}
,
A_{\leq,\pm} \in \R^{m(\leq) \times n(\pm)}
,
A_{\leq,+} \in \R^{m(\leq) \times n(+)}
,
b_= \in \R^{m(=)}
,
b_\leq \in \R^{m(\leq)}
,
c_\pm \in \R^{n(\pm)}
, and
c_+ \in \R^{n(+)}
.
\[
\begin{array}{ll}
{\rm maximize} & c_\pm^T x_\pm \; + \; c_+^T x_+
\; {\rm with \; respect \; to}
x_\pm \in \R^{n(\pm)} \; , \; x_+ \in \R_+^{n(+)}
\\
{\rm subject \; to}
& A_{=,\pm} x_\pm \; + \; A_{=,+} x_+ \; = \; b_=
\\
& A_{\leq ,\pm} x_\pm \; + \; A_{\leq ,+} x_+ \; \leq \; b_\leq
\end{array}
\]
x_\pm = x_\pm^+ - x_\pm^-
where
x_\pm^+ \in \R_+^{n(\pm)}
, and
x_\pm^- \in \R_+^{n(\pm)}
.
The primal problem above is equivalent to
\[
\begin{array}{ll}
{\rm maximize} & c_\pm^T x_\pm^+ \; - \; c_\pm^T x_\pm^- \; + \; c_+^T x_+
\; {\rm w.r.t.} \;
x_\pm^+ \in \R_+^{n(\pm)} \; , \;
x_\pm^- \in \R_+^{n(\pm)} \; , \;
x_+ \in \R_+^{n(+)}
\\
{\rm subject \; to}
& + A_{=,\pm} x_\pm^+ \; - \;
A_{=,\pm} x_\pm^- \; + \; A_{=,+} x_+ \; \leq \; + b_=
\\
& - A_{=,\pm} x_\pm^+ \; + \;
A_{=,\pm} x_\pm^- \; - \; A_{=,+} x_+ \; \leq \; - b_=
\\
& + A_{\leq ,\pm} x_\pm^+ \; - \;
A_{\leq ,\pm} x_\pm^- \; + \; A_{\leq ,+} x_+ \; \leq \; + b_\leq
\end{array}
\]
\[
\begin{array}{ll}
{\rm maximize} & b_=^T y_=^+ \; - \; b_=^T y_=^- \; + \; b_\leq^T y_\leq
\; {\rm w.r.t.} \;
y_=^+ \in \R_+^{m(=)} \; , \;
y_=^- \in \R_+^{m(=)} \; , \;
y_\leq \in \R_+^{m(\leq)}
\\
{\rm subject \; to}
& + A_{=,\pm}^T y_=^+ \; - \;
A_{=,\pm}^T y_=^- \; + \; A_{\leq,\pm}^T y_\leq \; \geq \; + c_\pm
\\
& - A_{=,\pm}^T y_=^+ \; + \;
A_{=,\pm}^T y_=^- \; - \; A_{\leq,\pm}^T y_\leq \; \geq \; - c_\pm
\\
& + A_{=,+}^T y_=^+ \; - \;
A_{=,+}^T y_=^- \; + \; A_{\leq,+}^T y_\leq \; \geq \; + c_+
\end{array}
\]
y_= = y_=^+ - y_=^-
where
y_= \in \R^{m(=)}
.
The primal problem above is equivalent to
\[
\begin{array}{ll}
{\rm minimize} & b_=^T y_= \; + \; b_\leq^T y_\leq
\; {\rm with \; respect \; to}
y_= \in \R^{m(=)} \; , \; y_\leq \in \R_+^{m(\leq)}
\\
{\rm subject \; to}
& A_{=,\pm}^T y_= \; + \; A_{\leq,\pm}^T y_\leq \; = \; c_\pm \\
\\
& A_{=,+}^T y_= \; + \; A_{\leq,+}^T y_\leq \; \geq \; c_+
\end{array}
\]
\newcommand{\P}{{\bf P}}
X
and
Y
and a matrix
A \in \R^{m \times n}
If player
X
makes choice
j \in \{ 1 , \ldots , n \}
and player
Y
makes choice
i \in \{ 1 , \ldots , m \}
,
player
X
wins (player
Y
looses)
A_{i,j}
units.
P(n)
to denote the set of
probability measures on the indices
\{ 1 , \ldots , n \}
; i.e.,
\[
\P ( n ) = \left\{
x \in \R_+^n {\rm \; such \; that \;} \sum_{i=1}^n x_i = 1
\right\}
\]
If player
X
adopts a strategy
x \in P(n)
and player adopts a strategy
y \in P(m)
,
the expected winnings for player
X
(loosing for player
Y
) is
\[
y^T A x = \sum_{i=1}^m \sum_{j=1}^n y_i A_{i,j} x_j
\]
\hat{x} \in \R^n
and
\hat{y} \in \R^m
,
\[
\begin{array}{rcl}
\inf_{y \in \P(m)} y^T A \hat{x} & = &
\min_{i=1, \ldots , m} \; \sum_j^n A_{i,j} \hat{x}_j
\\
\sup_{x \in \P(n)} \hat{y}^T A x & = &
\max_{j=1, \ldots , n} \; \sum_i^m \hat{y}_i A_{i,j}
\end{array}
\]
k \in \{ 1 , \ldots , m \}
be an index such that
\[
\begin{array}{rcl}
\min_{i=1, \ldots , m} \; \sum_j^m A_{i,j} \hat{x}_j & = &
\sum_j^n A_{k,j} \hat{x}_j
\end{array}
\]
Choosing
y \in \P (m)
by
y_k = 1
and
for
i \neq k
,
y_i = 0
, we conclude that
\[
\begin{array}{rcl}
\inf_{y \in \P(m)} y^T A \hat{x} & \leq &
\sum_j^n A_{k,j} \hat{x}_j
\\
& \leq &
\min_{i=1, \ldots , m} \; \sum_j^n A_{i,j} \hat{x}_j
\end{array}
\]
But it also follows that
\[
\begin{array}{rcl}
y^T A \hat{x} & = &
\sum_{i=1}^m y_i \sum_{j=1}^n A_{i,j} \hat{x}_j
\\
& \geq &
\sum_{i=1}^m y_i \sum_{j=1}^n A_{k,j} \hat{x}_j
\\
& \geq &
\left( \sum_{j=1}^n A_{k,j} \hat{x}_j \right)
\sum_{i=1}^m y_i
\\
& \geq &
\sum_{j=1}^n A_{k,j} \hat{x}_j
\\
\inf_{y \in \P(m)} y^T A \hat{x} & \geq &
\min_{i=1, \ldots , m} \; \sum_j^n A_{i,j} \hat{x}_j
\end{array}
\]
The completes the proof of the first equation in the lemma.
The proof of the second equation is similar.
X
chooses her strategy first
and then player
Y
gets to choose his strategy.
It follows that player
X
should solve the problem
the problem
\[
{\rm maximize} \;
\left[ \min_{y \in \P(m)} \; y^T A x \right]
{\rm \; w.r.t. \;} x \in \P (n)
\]
This problem is equivalent to
\[
\begin{array}{ll}
{\rm maximize}
& z {\rm \; w.r.t. \;} z \in \R \; , \; x \in \R_+^n
\\
{\rm subject \; to}
& 1 = \sum_{j=1}^n x_j
\\
& z \leq \sum_{j=1}^n A_{i,j} x_j \; (i = 1, \ldots , m)
\end{array}
\]
We use the notation
0_{m \times n}
(
1_{m \times n}
) to denote the
m \times n
matrix of zeros (ones).
The problem above can be written as
\[
\begin{array}{ll}
{\rm maximize}
& (1 , 0_{1 \times n} )
\left( \begin{array}{c} z \\ x \end{array} \right)
{\rm \; w.r.t. \;} z \in \R \; , \; x \in \R_+^n
\\
{\rm subject \; to}
& \left( \begin{array}{ll}
0 & 1_{1 \times n} \\
1_{m \times 1} & - A
\end{array} \right)
\left( \begin{array}{c}
z \\
x
\end{array} \right)
\begin{array}{cc}
= & 1 \\
\leq & 0_{m \times 1}
\end{array}
\end{array}
\]
\[
\begin{array}{ll}
{\rm minimize}
& (1 , 0_{1 \times m} )
\left( \begin{array}{c} w \\ y \end{array} \right)
{\rm \; w.r.t. \;} w \in \R \; , \; y \in \R_+^m
\\
{\rm subject \; to}
& \left( \begin{array}{ll}
0 & 1_{1 \times m} \\
1_{n \times 1} & - A^T
\end{array} \right)
\left( \begin{array}{c}
w \\
y
\end{array} \right)
\begin{array}{cc}
= & 1 \\
\geq & 0_{n \times 1}
\end{array}
\end{array}
\]
This problem is equivalent to
\[
\begin{array}{ll}
{\rm minimize}
& w {\rm \; w.r.t. \;} w \in \R \; , \; y \in \R_+^m
\\
{\rm subject \; to}
& 1 = \sum_{i=1}^m y_i
\\
& w \geq \sum_{i=1}^m y_i A_{i,j} \; (j = 1, \ldots , n)
\end{array}
\]
Which is also equivalent to
\[
{\rm minimize} \;
\left[ \max_{x \in \P(n)} \; y^T A x \right]
{\rm \; w.r.t. \;} y \in \P (m)
\]
This is the problem that player
Y
should solve
if
Y
chooses his strategy first
and then player
X
gets to choose here strategy.
\[
\min_{y \in \P (m)} \;
\left[ \max_{x \in \P(n)} \; y^T A x \right]
=
\max_{x \in \P (n)} \;
\left[ \min_{y \in \P(m)} \; y^T A x \right]
\]
\newcommand{\P}{{\bf P}}
A
and
B
simultaneously choose a coin (which they own) of value
x
or
y
where
x \neq y
.
If the chosen coins have the same value, player
A
gets
to keep them.
Otherwise player
B
gets to keep them.
We use
P( b , a )
to denote the payoff from
player
B
to player
A
when
A
chooses
a
and
B
chooses
b
.
The following table gives the payoff from player
B
to player
A
for each of the possible cases:
\[
\begin{array}{ll}
P(x, x) = x & P(x, y) = -y \\
P(y, x) = -x & P(y, y) = y
\end{array}
\]
A
(if the strategy is discovered by
B
) solves the problem
\[
{\rm maximize} \left[ \inf_{b \in \P(2)}
b_1 x a_1 - b_1 y a_2 - b_2 x a_1 + b_2 y a_2
\right] \; w.r.t. \; a \in \P(2)
\]
Applying the inf: 4.c
part of the lemma for matrix games,
we obtain the equivalent problem:
\[
{\rm maximize} \left[
\min \left( x a_1 - y a_2 \; , \; - x a_1 + y a_2 \right)
\right] \; w.r.t. \; a \in \P(2)
\]
Because there are only two components of
a
,
we can use
a_2 = 1 - a_1
to replace
a_2
in the objective
and obtain the equivalent problem
\[
{\rm maximize} \left[
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\right] \; w.r.t. \; a_1 \in [0, 1]
\]
The function
\[
f( a_1 ) =
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\]
has constant derivative on the interval
[0,1]
except for
three points.
Thus, there are three possible solutions for the maximum:
a_1 = 0
,
a_1 = 1
or the solution of the following
equation
\[
\begin{array}{rcl}
(x + y) a_1 - y & = & y - (x + y) a_1 \\
a_1 & = & y / (x + y)
\end{array}
\]
The corresponding objective function values are
\[
\begin{array}{rclcrcl}
0 & = & a_1 & \Rightarrow & -y & = &
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\\
1 & = & a_1 & \Rightarrow & -x & = &
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\\
y / (x + y) & = & a_1 & \Rightarrow & 0 & = &
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\end{array}
\]
It follows
(from the fact that
x > 0
and
y > 0
)
that the optimal strategy for
A
is to choose
x
with probability
y/(x + y)
and to choose
y
with probability
x/(x + y)
.
In this case, the expected payoff of the game is zero
(provided that player
B
plays in an optimal fashion).
B
(if the strategy is discovered by
A
) solves the problem
\[
{\rm minimize} \left[ \sup_{a \in \P(2)}
b_1 x a_1 - b_1 y a_2 - b_2 x a_1 + b_2 y a_2
\right] \; w.r.t. \; b \in \P(2)
\]
Applying the sup: 4.c
part of the lemma for matrix games,
we obtain the equivalent problem:
\[
{\rm minimize} \left[
\max \left( b_1 x - b_2 x \; , \; - b_1 y + b_2 y \right)
\right] \; w.r.t. \; b \in \P(2)
\]
Because there are only two components of
b
,
we can use
b_2 = 1 - b_1
to replace
b_2
in the objective
and obtain the equivalent problem
\[
{\rm minimize} \left[
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\right] \; w.r.t. \; b_1 \in [0, 1]
\]
The function
\[
g( b_1 ) =
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\]
has constant derivative on the interval
[0,1]
except for
three points.
Thus, there are three possible solutions for the maximum:
b_1 = 0
,
b_1 = 1
or the solution of the following
equation
\[
\begin{array}{rcl}
x ( 2 b_1 - 1 ) & = & ( 1 - 2 b_1 ) y
\\
2 (x + y) b_1 & = & (x + y)
\\
b_1 & = & 1 / 2
\end{array}
\]
The corresponding objective function values are
\[
\begin{array}{rclcrcl}
0 & = & b_1 & \Rightarrow & y & = &
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\\
1 & = & b_1 & \Rightarrow & x & = &
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\\
1 / 2 & = & b_1 & \Rightarrow & 0 & = &
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\end{array}
\]
It follows
(from the fact that
x > 0
and
y > 0
)
that the optimal strategy for
B
is to choose
x
with probability
1/2
and to choose
y
with probability
1/2
.
In this case, the expected payoff of the game is zero
(provided that player
A
plays in an optimal fashion).
\newcommand{\P}{{\bf P}}
X
and
Y
simultaneously (and repeatedly) choose one of the
following options: Rock, Paper, or Scissor.
The following table gives the payoff from player
Y
to player
X
for each of the possible cases
X
| ||||
| Rock | Paper | Scissor | ||
| Rock | 0 | -1 | 1 | |
Y
| Paper | 1 | 0 | -1 |
| Scissor | -1 | 1 | 0 |
\[
A = \left( \begin{array}{ccc}
0 & -1 & 1 \\
1 & 0 & -1 \\
-1 & 1 & 0
\end{array} \right)
\]
The optimal strategy for
X
(if the strategy is discovered by
Y
) solves the following problem
\[
{\rm maximize} \left[ \min_{ y \in \P (3) } y^T A x \right]
{\rm \; w.r.t \; } x \in \P (3)
\]
The optimal strategy for
Y
(if the strategy is discovered by
X
) solves the following problem
\[
{\rm minimize} \left[ \max_{ x \in \P (3) } y^T A x \right]
{\rm \; w.r.t \; } y \in \P (3)
\]
X
and
Y
are
\hat{x} = (1 , 1 , 1) / 3
and
\hat{y} = (1 , 1 , 1) / 3
.
In this case we also think that the corresponding payoff value is zero; i.e.,
\[
0 = \hat{y}^T A \hat{x}
\]
We can check this by checking that
\hat{x}
is feasible for the corresponding primal problem,
\hat{y}
is feasible for the corresponding dual problem,
and the primal and dual have the same object value zero at these points.
\[
\begin{array}{ll}
{\rm maximize}
& (1 , 0 , 0 , 0 )
\left( \begin{array}{c} z \\ x \end{array} \right)
{\rm \; w.r.t. \;} z \in \R \; , \; x \in \R_+^3
\\
{\rm subject \; to}
& \left( \begin{array}{lllll}
0 & 1 & 1 & 1 \\
1 & 0 & 1 & -1 \\
1 & -1 & 0 & 1 \\
1 & 1 & -1 & 0
\end{array} \right)
\left( \begin{array}{c}
z \\
x_1 \\
x_2 \\
x_3
\end{array} \right)
\begin{array}{cc}
= & 1 \\
\leq & 0 \\
\leq & 0 \\
\leq & 0
\end{array}
\end{array}
\]
Using the argument value
( \hat{z} , \hat{x}^T ) = (0, 1/3, 1/3, 1/3)
,
the corresponding primal objective is zero and
the primal feasibility conditions check out because
\[
\begin{array}{ll}
& \left( \begin{array}{lllll}
0 & 1 & 1 & 1 \\
1 & 0 & 1 & -1 \\
1 & -1 & 0 & 1 \\
1 & 1 & -1 & 0
\end{array} \right)
\left( \begin{array}{c}
0 \\
1/3 \\
1/3 \\
1/3
\end{array} \right)
\begin{array}{cc}
= & 1 \\
\leq & 0 \\
\leq & 0 \\
\leq & 0
\end{array}
\end{array}
\]
\[
\begin{array}{ll}
{\rm minimize}
& (1 , 0 , 0 , 0 )
\left( \begin{array}{c} w \\ y \end{array} \right)
{\rm \; w.r.t. \;} w \in \R \; , \; y \in \R_+^3
\\
{\rm subject \; to}
& \left( \begin{array}{lllll}
0 & 1 & 1 & 1 \\
1 & 0 & -1 & 1 \\
1 & 1 & 0 & -1 \\
1 & -1 & 1 & 0
\end{array} \right)
\left( \begin{array}{c}
w \\
y_1 \\
y_2 \\
y_3
\end{array} \right)
\begin{array}{cc}
= & 1 \\
\geq & 0 \\
\geq & 0 \\
\geq & 0
\end{array}
\end{array}
\]
Using the argument value
( \hat{w} , \hat{y}^T ) = (0, 1/3, 1/3, 1/3)
,
the corresponding dual objective is zero and
the primal feasibility conditions check out because
\[
\begin{array}{ll}
& \left( \begin{array}{lllll}
0 & 1 & 1 & 1 \\
1 & 0 & -1 & 1 \\
1 & 1 & 0 & -1 \\
1 & -1 & 1 & 0
\end{array} \right)
\left( \begin{array}{c}
0 \\
1/3 \\
1/3 \\
1/3
\end{array} \right)
\begin{array}{cc}
= & 1 \\
\geq & 0 \\
\geq & 0 \\
\geq & 0
\end{array}
\end{array}
\]
\newcommand{\notin}{ \mathml{&\#x02209;} }
Manufacturing this product requires cooling water and each unit of
large, medium, and small sizes produced require
21, 17, and 9 gallons of water, respectively.
The centers 1, 2, and 3 have 10,000, 7000, and 420 gallons
of cooling water available per day, respectively.
Market studies indicate that there is a market for 700, 900, and 340 units
of the large, medium, and small sizes, respectively, per day.
By company policy, the fraction
(scheduled production) / (center's capacity)
must be the same at all the centers.
How many units of each of the sizes should be produced
at the various centers in order to maximize the profit?
| Variable | Meaning |
c
|
center index,
c \in \{1, 2, 3 \}
|
s
| size index, 1 = large, 2 = medium, 3 = small |
x_{3 (c - 1) + s}
| units per day of size s produced at center c |
z
| net company profit in dollars per day |
p_c
|
percentage of production capacity scheduled at center
c
|
r_s
|
rate of production in units per day for size
s
|
w_c
|
units of cooling water used per day at center
c
|
\alpha
|
we use
\alpha
to denote
1 / 5.50
|
\beta
|
we use
\beta
to denote
1 / 7.50
|
\gamma
|
we use
\gamma
to denote
1 / 2.75
|
\[
\begin{array}{rrrrrrrrrr}
&
x_1 & x_2 & x_3 &
x_4 & x_5 & x_6 &
x_7 & x_8 & x_9
\\
z = &
12 & 10 & 9 &
12 & 10 & 9 &
12 & 10 & 9
\\
p_1 - p_2 = &
\alpha & \alpha & \alpha &
-\beta & -\beta & -\beta &
& &
\\
p_1 - p_3 = &
\alpha & \alpha & \alpha &
& & &
-\gamma & -\gamma & -\gamma
\\
p_1 = &
\alpha & \alpha & \alpha &
& & &
& &
\\
r_1 = &
1 & & &
1 & & &
1 & &
\\
r_2 = &
& 1 & &
& 1 & &
& 1 &
\\
r_3 = &
& & 1 &
& & 1 &
& & 1
\\
w_1 = &
21 & 17 & 9 &
& & &
& &
\\
w_2 = &
& & &
21 & 17 & 9 &
& &
\\
w_3 = &
& & &
& & &
21 & 17 & 9
\end{array}
\]
z
with respect to
x \in \R_+^{3 \times 3}
and subject to the following constraints:
\[
p_1 - p_2 = 0 \; , \; p_1 - p_3 = 0
\]
\[
p_1 \leq 100
\]
\[
w_1 \leq 10^4 \; , \;
w_2 \leq 7 \times 10^3 \; , \;
w_3 \leq 420
\]
z
is only valid
if we stay below the market capacities; i.e.,
\[
r_1 \leq 700 \; , \;
r_2 \leq 900 \; , \;
r_3 \leq 340
\]
c \in \R^9
,
the vector
b \in \R^11
and
the matrix
A \in \R^{11 \times 9}
by
\[
\begin{array}{rcl}
c & = & ( 12, 10, 9, 12, 10, 9, 12, 10, 9 )^T
\\
b & = & (0, 0, 0, 0, 100, 700, 900, 340, 10^4, 7 \times 10^3, 420)
\\
A & = & \left( \begin{array}{rrrrrrrrr}
\alpha & \alpha & \alpha &
-\beta & -\beta & -\beta &
& &
\\
-\alpha & -\alpha & -\alpha &
\beta & \beta & \beta &
& &
\\
\alpha & \alpha & \alpha &
& & &
-\gamma & -\gamma & -\gamma
\\
-\alpha & -\alpha & -\alpha &
& & &
\gamma & \gamma & \gamma
\\
\alpha & \alpha & \alpha &
& & &
& &
\\
1 & & &
1 & & &
1 & &
\\
& 1 & &
& 1 & &
& 1 &
\\
& & 1 &
& & 1 &
& & 1
\\
21 & 17 & 9 &
& & &
& &
\\
& & &
21 & 17 & 9 &
& &
\\
& & &
& & &
21 & 17 & 9
\end{array} \right)
\end{array}
\]
It follows that
\hat{x} \in \R_+^9
solves the
problem submitted to Neos: 5.1.b.c
if and only if it solves
\[
\begin{array}{rcl}
{\rm maximize} & c^T x & {\rm with \; respect \; to} \; x \in \R_+^9
\\
{\rm subject \; to} & A x \leq b
\end{array}
\]
Furthermore
\hat{y} \in \R_+^11
solves the corresponding
dual problem if and only if it solves
\[
\begin{array}{rcl}
{\rm minimize} & b^T y & {\rm with \; respect \; to} \; y \in \R_+^11
\\
{\rm subject \; to} & A^T y \geq b
\end{array}
\]
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 4.0 , 4.0 , 3.93 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME Manufacture
At line 5 ROWS
At line 16 COLUMNS
At line 68 RHS
At line 78 ENDATA
Problem Manufacture has 9 rows, 9 columns and 33 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 9 (0) rows, 9 (0) columns and 33 (0) elements
Perturbing problem by 0.001 % of 540.46 - largest nonzero change 5.09017e-05 (% 0.000152787) - largest zero change 0
0 Obj -0 Dual inf 71.8437 (9)
6 Obj 3067.28
Optimal - objective value 3067.27
Optimal objective 3067.272727 - 6 iterations time 0.002
Clp:
0 p1p2 0 -90
1 p1p3 0 156
2 p1 16.969697 -0
3 r1 220.60606 -0
4 r2 0 -0
5 r3 46.666667 -0
6 w1 1960 -0
7 w2 2672.7273 -0
8 w3 420 7.3030303
0 x1 93.333333 -8.7777262e-16
1 x2 0 -2
2 x3 0 -3
3 x4 127.27273 5.2000976e-16
4 x5 0 -2
5 x6 0 -3
6 x7 0 -84.636364
7 x8 0 -57.424242
8 x9 46.666667 -1.9160035e-15
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
We use the notation
\[
\hat{y} = (
\hat{z}_1^+ , \hat{z}_1^- , \hat{z}_2^+ , \hat{z}_2^- ,
\hat{z}_3 , \hat{z}_4 , \hat{z}_5 , \hat{z}_6 ,
\hat{z}_7 , \hat{z}_8 , \hat{z}_9 )^T
\]
The solution determined by Clp
(see Neos Input File: 5.1.e
below) is
\[
\begin{array}{c}
\hat{x}_1 = 93.33333 \; , \;
\hat{x}_4 = 127.2727 \; , \;
\hat{x}_9 = 46.66667
\\
\hat{z}_1^- = 90 \; , \;
\hat{z}_2^+ = 156 \; , \;
\hat{z}_9 = 7.30303
\end{array}
\]
The other components of
x \in \R_+^9
and
\hat{y} \in \R_+^11
are zero.
A \hat{x} \leq b
:
\[
\begin{array}{rrrrrrrrrrrr}
A \hat{x} = &
( 0, & 0, & 0, & 0, &
16.97, & 220.61, & 0, & 46.667, & 1960, & 2672.7, & 420 )^T
\\
b = &
(0, & 0, & 0, & 0, &
100, & 700, & 900, & 340, & 10^4, & 7 \times 10^3, & 420)
\end{array}
\]
A^T \hat{y} \geq c
:
\[
\begin{array}{rrrrrrrrrr}
A^T \hat{y} = &
(12, & 12, & 12, & 12, & 12, & 12, & 96.6366, & 67.424, & 9)^T
\\
c = &
( 12, & 10, & 9, & 12, & 10, & 9, & 12, & 10, & 9 )^T
\end{array}
\]
i = 1 , \ldots , 11
and
j = 1 , \ldots 9
\[
\begin{array}{rcl}
0 & = & \hat{y}_i \left( b_i - \sum_{k=1}^9 A_{i,k} \hat{x}_k \right)
\\
0 & = & \hat{x}_j \left( \sum_{k=1}^{11} \hat{y}_k A_{k,j} - c_j \right)
\end{array}
\]
It suffices to check the complimentary slackness conditions
for the indices
i
such that
\hat{y}_i \neq 0
and the indices
j
such that
\hat{x}_j \neq 0
; i.e.
it suffices to check the complimentary slackness conditions
for
i \in \{ 2 , 3 , 11 \}
and for
j \in \{ 1 , 4, 9 \}
\[
\begin{array}{rcl}
b_i & = & \sum_{k=1}^9 A_{i,k} \hat{x}_k
\\
c_j & = & \sum_{k=1}^{11} \hat{y}_k A_{k,j}
\end{array}
\]
Comparing indices 2, 3, 11 in
A \hat{x}
with
b
we get agreement.
Comparing indices 1, 4, 9 in
A^T \hat{y}
with
c
also gives agreement.
Thus the complimentary slackness conditions are satisfied,
\hat{x}
is optimal for the primal problem, and
\hat{y}
is optimal for the dual problem.
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
maximize z = 12(x1 + x4 + x7) + 10(x2 + x5 + x8) + 9(x3 + x6 + x9)
subject to p1p2 = (x1 + x2 + x3)/5.50 - (x4 + x5 + x6)/7.50 = 0
p1p3 = (x1 + x2 + x3)/5.50 - (x7 + x9 + x9)/2.75 = 0
p1 = (x1 + x2 + x3)/5.50 <= 100
r1 = x1 + x4 + x7 <= 700
r2 = x2 + x5 + x8 <= 900
r3 = x3 + x6 + x9 <= 340
w1 = 21 x1 + 17 x2 + 9 x3 <= 10000
w2 = 21 x4 + 17 x5 + 9 x6 <= 7000
w3 = 21 x7 + 17 x8 + 9 x9 <= 4200
1/5.50 = .181818...
1/7.50 = .133333...
1/2.75 = .363636...
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------
*23 56789012 56789012 567890123456
NAME Manufacture
ROWS
N z
E p1p2
E p1p3
L p1
L r1
L r2
L r3
L w1
L w2
L w3
COLUMNS
*Op Name0--- Name1--- Value1------
x1 z 12
x1 p1p2 .18181818181
x1 p1p3 .18181818181
x1 p1 .18181818181
x1 r1 1
x1 w1 21
*
x2 z 10
x2 p1p2 .18181818181
x2 p1p3 .18181818181
x2 p1 .18181818181
x2 r2 1
x2 w1 17
*
x3 z 9
x3 p1p2 .18181818181
x3 p1p3 .18181818181
x3 p1 .18181818181
x3 r3 1
x3 w1 9
*
x4 z 12
x4 p1p2 -.1333333333
x4 r1 1
x4 w2 21
*
x5 z 10
x5 p1p2 -.1333333333
x5 r2 1
x5 w2 17
*
x6 z 9
x6 p1p2 -.1333333333
x6 r3 1
x6 w2 9
*
x7 z 12
x7 p1p3 -.3636363636
x7 r1 1
x7 w3 21
*
x8 z 10
x8 p1p3 -.3636363636
x8 r2 1
x8 w3 17
*
x9 z 9
x9 p1p3 -.3636363636
x9 r3 1
x9 w3 9
RHS
rhs p1p2 0
rhs p1p3 0
rhs p1 100
rhs r1 700
rhs r2 900
rhs r3 340
rhs w1 10000
rhs w2 7000
rhs w3 420
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
| Hours | 00-06 | 06-12 | 12-18 | 18-00 |
| Collectors Needed | 2 | 8 | 5 | 4 |
w_h
|
The number of collectors that start work at hour
h
|
z
| is the total number of collectors scheduled to work each day |
N_h
|
is the number of collectors working from hour
h
to hour
[h + 4]
|
\[
\begin{array}{rclcl}
& & z & = & w_{00} + w_{04} + w_{08} + w_{12} + w_{16} + w_{20}
\\
2 & \leq & N_{00} & = & w_{20} + w_{00}
\\
8 & \leq & N_{04} & = & w_{00} + w_{04}
\\
8 & \leq & N_{08} & = & w_{04} + w_{08}
\\
5 & \leq & N_{12} & = & w_{08} + w_{12}
\\
5 & \leq & N_{16} & = & w_{12} + w_{16}
\\
3 & \leq & N_{20} & = & w_{16} + w_{20}
\end{array}
\]
x \in \R^6
by
x_i = w_{4 (i - 1)}
.
We define the matrix
A \in \R^{6 \times 6}
and vectors
b \in \R^6
,
c \in \R^6
by
\[
\begin{array}{rcl}
c & = & - (1, 1, 1, 1, 1, 1)^T \\
b & = & - (2, 8, 8, 5, 5, 3)^T \\
A & = & - \left( \begin{array}{rrrrrr}
% w00 & w04 & w08 & w12 & w16 & w20 \\
1 & & & & & 1 \\
1 & 1 & & & & \\
& 1 & 1 & & & \\
& & 1 & 1 & & \\
& & & 1 & 1 & \\
& & & & 1 & 1
\end{array} \right)
\end{array}
\]
It follows the problem above can be represented as
\[
\begin{array}{rcl}
{\rm maximize} & c^T x & {\rm with \; respect \; to} \; x \in \R_+^6
\\
{\rm subject \; to} & A x \leq b
\end{array}
\]
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 9.0 , 9.0 , 9.0 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME Manufacture
At line 5 ROWS
At line 13 COLUMNS
At line 40 RHS
At line 47 ENDATA
Problem Manufacture has 6 rows, 6 columns and 12 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 6 (0) rows, 6 (0) columns and 12 (0) elements
Perturbing problem by 0.001 % of 5.16668 - largest nonzero change 4.93443e-05 (% 0.00246722) - largest zero change 0
0 Obj 0 Primal inf 30.9999 (6) Dual inf 1.2e+11 (6)
5 Obj 16
Optimal - objective value 16
Optimal objective 16 - 5 iterations time 0.002
Clp:
0 N00 3 0
1 N04 8 1
2 N08 8 0
3 N12 5 1
4 N16 5 0
5 N20 3 1
0 w00 3 0
1 w04 5 0
2 w08 3 0
3 w12 2 0
4 w16 3 0
5 w20 0 0
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
The solution above determined using Clp and the
Neos Input File: 5.2.e
below is
\[
\begin{array}{rcl}
\hat{x} & = & (3, 5, 3, 2, 3, 0) \\
\hat{y} & = & (0, 1, 0, 1, 0, 1)
\end{array}
\]
A \hat{x} \leq b
:
\[
\begin{array}{rcl}
A \hat{x} & = & - (3, 8, 8, 5, 5, 3)^T \\
b & = & - (2, 8, 8, 5, 5, 3)^T
\end{array}
\]
A^T \hat{y} \geq c
:
\[
\begin{array}{rcl}
A^T \hat{y} & = & - (1, 1, 1, 1, 1, 1)^T \\
c & = & - (1, 1, 1, 1, 1, 1)^T
\end{array}
\]
i = 1 , \ldots , 6
and
j = 1 , \ldots 6
\[
\begin{array}{rcl}
0 & = & \hat{y}_i \left( b_i - \sum_{k=1}^6 A_{i,k} \hat{x}_k \right)
\\
0 & = & \hat{x}_j \left( \sum_{j=1}^6 \hat{y}_k A_{k,j} - c_j \right)
\end{array}
\]
Given the zero components of
\hat{x}
and
\hat{y}
,
it suffices to check that for
i = 2, 4, 6
and for
j = 1 , \ldots , 5
\[
\begin{array}{rcl}
b_i & = & \sum_{k=1}^6 A_{i,k} \hat{x}_k
\\
c_j & = & \sum_{j=1}^6 \hat{y}_k A_{k,j}
\end{array}
\]
All these equations follow from the formulas
for
A \hat{x}
and
A^T \hat{y}
above.
Thus, the solution "checks out".
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
minimize z = w00 + w04 + w08 + w12 + w16 + w20
subject to 2 <= N00 = w20 + w00
8 <= N04 = w00 + w04
8 <= N08 = w04 + w08
5 <= N12 = w08 + w12
5 <= N16 = w12 + w16
3 <= N20 = w16 + w20
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------
*23 56789012 56789012 567890123456
NAME Manufacture
ROWS
N z
G N00
G N04
G N08
G N12
G N16
G N20
COLUMNS
*Op Name0--- Name1--- Value1------
*
w00 z 1
w00 N00 1
w00 N04 1
*
w04 z 1
w04 N04 1
w04 N08 1
*
w08 z 1
w08 N08 1
w08 N12 1
*
w12 z 1
w12 N12 1
w12 N16 1
*
w16 z 1
w16 N16 1
w16 N20 1
*
w20 z 1
w20 N20 1
w20 N00 1
*
RHS
rhs N00 2
rhs N04 8
rhs N08 8
rhs N12 5
rhs N16 5
rhs N20 3
ENDATA
*]]></MPS>
<param><![CDATA[
minimize
primalSimplex
solution -
]]></param>
</document>
Week # Experienced # Assemblers # Trainees # Idle
1 E1 A1 T1 I1
2 E2 A2 T2 I2
3 E3 A3 T3 I3
4 E4 A4 T4 I4
z = 750 * A1 - 200 * E1 - 100 * T1
+ 650 * A2 - 200 * E2 - 100 * T2
+ 550 * A3 - 200 * E3 - 100 * T3
+ 450 * A4 - 200 * E4 - 100 * T4
40 = E1eq = E1
0 = E2eq = E2 - E1 - T1
0 = E3eq = E3 - E2 - T2
0 = E4eq = E4 - E3 - T3
0 >= -I1 = - E1 + A1 + T1/3
0 >= -I2 = - E2 + A2 + T2/3
0 >= -I3 = - E3 + A3 + T3/3
0 >= -I4 = - E4 + A4 + T4/3
20,000 = R = 50 * A1 + 50 * A2 + 50 * A3 + 50 * A4
q for the dual objective and
Constraint Dual Variable Constraint Dual Variable
E1eq e1eq -I1 i1
E2eq e2eq -I2 i2
E3eq e3eq -I3 i3
E4eq e4eq -I4 i4
R r
40 * u1 + 20000 * w
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 1.0 , 1.0 , 1.0 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME Electron
At line 5 ROWS
At line 16 COLUMNS
At line 67 RHS
At line 70 ENDATA
Problem Electron has 9 rows, 12 columns and 26 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 5 (-4) rows, 7 (-5) columns and 17 (-9) elements
Perturbing problem by 0.001 % of 61.0056 - largest nonzero change 2.15098e-05 (% 6.16904e-05) - largest zero change 0
0 Obj -32000 Primal inf 458.881 (1) Dual inf 2.99952e+10 (4)
7 Obj 127000
Optimal - objective value 127000
After Postsolve, objective 127000, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 127000 - 7 iterations time 0.002, Presolve -0.00
Clp:
0 E1eq 40 550
1 E2eq 0 262.5
2 E3eq 0 75
3 E4eq 0 -12.5
4 minusI1 -2.3906224e-14 487.5
5 minusI2 0 387.5
6 minusI3 0 287.5
7 minusI4 0 187.5
8 R 20000 5.25
0 E1 40 0
1 A1 10 6.9277917e-14
2 T1 90 4.146683e-14
3 E2 130 -2.8421709e-14
4 A2 130 1.2612134e-13
5 T2 0 -154.16667
6 E3 130 0
7 A3 130 6.9277917e-14
8 T3 0 -208.33333
9 E4 130 0
10 A4 130 4.0856207e-14
11 T4 0 -162.5
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
The primal solution above determined using Clp and the
Neos input file: 5.3.e
below is
E = ( 40 , 130 , 130 , 130 )^T
A = ( 10 , 130 , 130 , 130 )^T
T = ( 90 , 0 , 0 , 0 )^T
The dual solution is
e*eq = ( 550 , 262.5 , 75 , -12.5 )^T
i = ( 487.5 , 387.5 , 287.5 , 187.5 )^T
r = 5.25
40 = E1 = 40
0 = E2 - E1 - T1 = 130 - 40 - 90
0 = E3 - E2 - T2 = 130 - 130 - 0
0 = E4 - E3 - T3 = 130 - 130 - 0
20000 = 50 * (A1 + A2 + A3 + A4) = 50 * (10 + 130 + 130 + 130)
0 >= - E1 + A1 + T1/3 = - 40 + 10 + 90/3
0 >= - E2 + A2 + T2/3 = - 130 + 130 + 0/3
0 >= - E3 + A3 + T3/3 = - 130 + 130 + 0/3
0 <= - E4 + A4 + T4/3 = - 130 + 130 + 0/3
z = 750 * A1 - 200 * E1 - 100 * T1
+ 650 * A2 - 200 * E2 - 100 * T2
+ 550 * A3 - 200 * E3 - 100 * T3
+ 450 * A4 - 200 * E4 - 100 * T4
= 750 * 10 - 200 * 40 - 100 * 90
+ 650 * 130 - 200 * 130 - 100 * 0
+ 550 * 130 - 200 * 130 - 100 * 0
+ 450 * 130 - 200 * 130 - 100 * 0
= 127000
E1: -200 <= eq1eq - eq2eq - i1 = 550 - 262.5 - 487.5 = -200
E2: -200 <= eq2eq - eq3eq - i2 = 262.5 - 75 - 387.5 = -200
E3: -200 <= eq3eq - eq4eq - i3 = 75 + 12.5 - 287.5 = -200
E4: -200 <= eq4eq - i4 = -12.5 - 187.5 = -200
A1: 750 <= i1 + 50 * r = 487.5 + 50 * 5.25 = 750
A2: 650 <= i2 + 50 * r = 387.5 + 50 * 5.25 = 650
A3: 550 <= i3 + 50 * r = 287.5 + 50 * 5.25 = 550
A4: 450 <= i4 + 50 * r = 187.5 + 50 * 5.25 = 450
T1: -100 <= - e2eq + i1 / 3 = - 262.5 + 487.5 / 3 = -100
T2: -100 <= - e3eq + i2 / 3 = - 75 + 387.5 / 3 = 54.167
T3: -100 <= - e4eq + i3 / 3 = + 12.5 + 287.5 / 3 = 108.33
T4: -100 <= i4 / 3 = 187.5 / 3 = 62.5
q = 40 * u1 + 20000 * w
= 40 * 550 + 20000 * 5.25
= 127000
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
z = net profit
R = number of radios = 20000
Week # Experienced # Assemblers # Trainees # Idle
1 E1 A1 T1 I1
2 E2 A2 T2 I2
3 E3 A3 T3 I3
4 E4 A4 T4 I4
Change in number experienced
40 = E1eq
0 = E2eq = E2 - E1 - T1
0 = E3eq = E3 - E2 - T2
0 = E4eq = E4 - E3 - T3
Minus number of idle employees
0 >= -I1 = - E1 + A1 + T1/3
0 >= -I2 = - E2 + A2 + T2/3
0 >= -I3 = - E3 + A3 + T3/3
0 >= -I4 = - E4 + A4 + T4/3
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------
*23 56789012 56789012 567890123456
NAME Electron
ROWS
N z
E E1eq
E E2eq
E E3eq
E E4eq
L minusI1
L minusI2
L minusI3
L minusI4
E R
COLUMNS
*Op Name0--- Name1--- Value1------
E1 z -200
E1 E1eq 1
E1 E2eq -1
E1 minusI1 -1
*
A1 z 750
A1 minusI1 1
A1 R 50
*
T1 z -100
T1 E2eq -1
T1 minusI1 .3333333333
*
E2 z -200
E2 E2eq 1
E2 E3eq -1
E2 minusI2 -1
*
A2 z 650
A2 minusI2 1
A2 R 50
*
T2 z -100
T2 E3eq -1
T2 minusI2 .3333333333
*
E3 z -200
E3 E3eq 1
E3 E4eq -1
E3 minusI3 -1
*
A3 z 550
A3 minusI3 1
A3 R 50
*
T3 z -100
T3 E4eq -1
T3 minusI3 .3333333333
*
E4 z -200
E4 E4eq 1
E4 minusI4 -1
*
A4 z 450
A4 minusI4 1
A4 R 50
*
T4 z -100
T4 minusI4 .3333333333
RHS
rhs E1eq 40
rhs R 20000
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
| Forest Type |
| Index |
| Available Acres |
| 1000 Hoppus-ft per Acre |
| High volume hardwood | 1 | 2754 | 2 | |||
| Medium volume hardwood | 2 | 850 | 1.2 | |||
| Low volume hardwood | 3 | 855 | .7 | |||
| Conifer high forest | 4 | 1598 | 4. | |||
| Mixed high forest | 5 | 405 | 2.5 | |||
| Bare land | 6 | 1761 | --- |
| Complete | Partial | None | Total | |||||
| High volume | 357 | 500 | 1,897 | 2754 | ||||
| Medium volume | 197 | 130 | 523 | 850 | ||||
| Low volume | 39 | 170 | 646 | 855 | ||||
| Activity | Index |
| plant conifer | 0 |
| Fell and plant conifer or hardwood | 1 |
| Fell and retain undergrowth | 2 |
| Fell and enrich undergrowth | 3 |
| Do nothing | 4 |
| Index | 1 | 2 | 3 | 4 | ||||
| 1 | 215 | 228 | 292 | 204 | ||||
| 2 | 135 | 148 | 212 | 148 | ||||
| 3 | 85 | 98 | 162 | 112 | ||||
| 4 | 415 | --- | --- | 371 | ||||
| 5 | 265 | --- | --- | 264 | ||||
| 6 | 15 | --- | --- | 61 |
X_{i,j} \geq 0
as the number of acres of
forest with index
i
that receive activity with index j.
\[
\begin{array}{rcl}
z
& = &
72 X_0
\\
& + &
215 X_{1,1} +
135 X_{2,1} +
85 X_{3,1} +
415 X_{4,1} +
265 X_{5,1} +
15 X_{6,1}
\\
& + &
228 X_{1,2} +
148 X_{2,2} +
98 X_{3,2}
\\
& + &
292 X_{1,3} +
212 X_{2,3} +
162 X_{3,3}
\\
& + &
204 X_{1,4} +
148 X_{2,4} +
112 X_{3,4} +
371 X_{4,4} +
264 X_{5,4} +
61 X_{6,4}
\end{array}
\]
\[
\begin{array}{rclr}
2754 & = & F_1 = X_{1,1} + X_{1,2} + X_{1,3} & + X_{1,4} \\
850 & = & F_2 = X_{2,1} + X_{2,2} + X_{2,3} & + X_{2,4} \\
855 & = & F_3 = X_{3,1} + X_{3,2} + X_{3,3} & + X_{3,4} \\
1598 & = & F_4 = X_{4,1} + & + X_{4,4} \\
405 & = & F_5 = X_{5,1} + & + X_{5,4} \\
1761 & = & F_6 = X_{6,1} + & + X_{6,4}
\end{array}
\]
\[
\begin{array}{lrl}
X_{1,2} \leq 357 & , & X_{1,3} \leq 500 \\
X_{2,2} \leq 197 & , & X_{2,3} \leq 130 \\
X_{3,2} \leq 39 & , & X_{3,3} \leq 170
\end{array}
\]
\[
\begin{array}{rcl}
5000
\geq
A_t & = & \sum_{i=1}^3 \sum_{j=0}^3 X_{i,j} + \sum_{i=4}^5 \sum_{j=0}^1 X_{i,j}
\\
2247
\geq
A_c & = & X_0 - X_{4,1}
\\
2440
\geq
V_h & = & 2 ( X_{1,1} + X_{1,2} + X_{1,3} )
\\
& + &
1.2 ( X_{2,1} + X_{2,2} + X_{2,3} )
\\
& + &
.7 ( X_{3,1} + X_{3,2} + X_{3,3} )
\\
4160
\geq
V_c & = & 4. X_{4,1} + 2.5 X_{5,1}
\\
\alpha
\leq
A_h & = & X_{1,1} + X_{2,1} + X_{3,1} + X_{4,1} + X_{5,1} + X_{6,1} - X_0
\end{array}
\]
\alpha = 0
is
From neos@mcs.anl.gov Mon Aug 8 16:49:50 2005
Date: Mon, 8 Aug 2005 18:49:48 -0500
From: neos@mcs.anl.gov
To: Math407 Summer05 <m407s05@u.washington.edu>
Subject: NEOS Results for Job #607105
You are using the solver clp-mps.
\%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 4.0 , 4.0 , 4.0 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME Forestry
At line 5 ROWS
At line 19 COLUMNS
At line 107 RHS
At line 119 BOUNDS
At line 126 ENDATA
Problem Forestry has 11 rows, 19 columns and 50 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 8 (-3) rows, 15 (-4) columns and 41 (-9) elements
0 Obj 807199 Primal inf 4743.04 (3) Dual inf 9.74621e+10 (14)
10 Obj 1.86366e+06
Optimal - objective value 1.86366e+06
After Postsolve, objective 1.86366e+06, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 1863659.5 - 10 iterations time 0.012, Presolve 0.01
Clp:
0 F1 2754 204
1 F2 850 148
2 F3 855 112
3 F4 1598 371
4 F5 405 264
5 F6 1761 61
6 AT 4087 -0
7 AC 2247 26
8 VH 2440 28.5
9 VC 4160 29
10 AH -9.094947e-13 -46
0 X0 3287 -3.5527137e-15
1 X11 582.5 -7.1054274e-15
2 X12 0 -33
3 X13 500 31
4 X14 1671.5 0
5 X21 0 -1.2
6 X22 0 -34.2
7 X23 130 29.8
8 X24 720 0
9 X31 0 -0.95
10 X32 0 -33.95
11 X33 170 30.05
12 X34 685 0
13 X41 1040 1.7763568e-14
14 X44 558 0
15 X51 0 -25.5
16 X54 405 0
17 X61 1664.5 0
18 X64 96.5 0
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
5.4.g.b: Alpha = 500
\alpha = 500
is
From neos@mcs.anl.gov Mon Aug 8 16:58:27 2005
Date: Mon, 8 Aug 2005 18:58:25 -0500
From: neos@mcs.anl.gov
To: Math407 Summer05 <m407s05@u.washington.edu>
Subject: NEOS Results for Job #607106
You are using the solver clp-mps.
\%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 4.0 , 4.0 , 4.0 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME Forestry
At line 5 ROWS
At line 19 COLUMNS
At line 107 RHS
At line 119 BOUNDS
At line 126 ENDATA
Problem Forestry has 11 rows, 19 columns and 50 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 8 (-3) rows, 15 (-4) columns and 41 (-9) elements
0 Obj 807199 Primal inf 5243.04 (4) Dual inf 1.51144e+11 (14)
12 Obj 1.84007e+06
Optimal - objective value 1.84007e+06
After Postsolve, objective 1.84007e+06, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 1840069.769 - 12 iterations time 0.002, Presolve 0.00
Clp:
0 F1 2754 204
1 F2 850 148
2 F3 855 112
3 F4 1598 371
4 F5 405 264
5 F6 1761 62.461538
6 AT 4587 -0
7 AC 2247 24.538462
8 VH 2440 29.230769
9 VC 4160 29
10 AH 500 -47.461538
0 X0 3287 -3.5527137e-15
1 X11 365.23077 -7.1054274e-15
2 X12 0 -34.461538
3 X13 500 29.538462
4 X14 1888.7692 0
5 X21 0 -0.61538462
6 X22 0 -35.076923
7 X23 130 28.923077
8 X24 720 0
9 X31 620.76923 -1.0116907e-14
10 X32 0 -34.461538
11 X33 170 29.538462
12 X34 64.230769 0
13 X41 1040 1.7763568e-14
14 X44 558 0
15 X51 0 -24.038462
16 X54 405 0
17 X61 1761 0
18 X64 0 -1.4615385
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
5.4.h: Column Representation
\[
\begin{array}{rrrrrrrr}
X_0 & 72 & & & 1 & & & -1 \\
& Z & F_1 & A_t & A_c & V_h & V_c & A_h \\
X_{1,1} & 215 & 1 & 1 & & 2 & & 1 \\
X_{1,2} & 228 & 1 & 1 & & 2 & & \\
X_{1,3} & 292 & 1 & 1 & & 2 & & \\
X_{1,4} & 204 & 1 & & & & & \\
& Z & F_2 & A_t & A_c & V_h & V_c & A_h \\
X_{2,1} & 135 & 1 & 1 & & 1.2 & & 1 \\
X_{2,2} & 148 & 1 & 1 & & 1.2 & & \\
X_{2,3} & 212 & 1 & 1 & & 1.2 & & \\
X_{2,4} & 148 & 1 & & & & & \\
& Z & F_3 & A_t & A_c & V_h & V_c & A_h \\
X_{3,1} & 85 & 1 & 1 & & .7 & & 1 \\
X_{3,2} & 98 & 1 & 1 & & .7 & & \\
X_{3,3} & 162 & 1 & 1 & & .7 & & \\
X_{3,4} & 112 & 1 & & & & & \\
& Z & F_4 & A_t & A_c & V_h & V_c & A_h \\
X_{4,1} & 415 & 1 & 1 & -1 & & 4. & 1 \\
X_{4,4} & 371 & 1 & & & & & \\
& Z & F_5 & A_t & A_c & V_h & V_c & A_h \\
X_{5,1} & 265 & 1 & 1 & & & 2.5 & 1 \\
X_{5,4} & 264 & 1 & & & & & \\
& Z & F_6 & A_t & A_c & V_h & V_c & A_h \\
X_{6,1} & 15 & 1 & 1 & & & & 1 \\
X_{6,4} & 61 & 1 & & & & &
\end{array}
\]
\alpha = 0
is
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Forestry example problem in Chapter 11 of Chvatal
Xij : Number of acres of forest with index i that receives activity j
Fi : Number of acres of forest with index i
AT : Total number of acres that receive activity
AC : Conifer area after activity
VH : Volume corresponding to felled hardwood only forest
VC : Volume corresponding to felled conifer and mixed forest
AH : Area planted in hardwood
i : Description
--------------------------
1 : High volume hardwoods
2 : Medium volume hardwoods
3 : Low volume hardwoods
4 : Conifer high forest
5 : Mixed high forest
6 : Bare land
j : Description
---------------------------
0 : Fell trees and plant conifers
1 : Fell trees and plant hardwoods or conifers
2 : Fell and retain undergrowth
3 : Fell and enrich undergrowth
4 : Do nothing
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------
*23 56789012 56789012 567890123456
NAME Forestry
ROWS
N Z
E F1
E F2
E F3
E F4
E F5
E F6
L AT
L AC
L VH
L VC
G AH
*Op Name0--- Name1--- Value1------
COLUMNS
X0 Z 72
X0 AH -1
X0 AC 1
*
X11 Z 215
X11 F1 1
X11 AT 1
X11 VH 2
X11 AH 1
*
X12 Z 228
X12 F1 1
X12 AT 1
X12 VH 2
*
X13 Z 292
X13 F1 1
X13 AT 1
X13 VH 2
*
X14 Z 204
X14 F1 1
*
X21 Z 135
X21 F2 1
X21 AT 1
X21 VH 1.2
X21 AH 1
*
X22 Z 148
X22 F2 1
X22 AT 1
X22 VH 1.2
*
X23 Z 212
X23 F2 1
X23 AT 1
X23 VH 1.2
*
X24 Z 148
X24 F2 1
*
X31 Z 85
X31 F3 1
X31 AT 1
X31 VH .7
X31 AH 1
*
X32 Z 98
X32 F3 1
X32 AT 1
X32 VH .7
*
X33 Z 162
X33 F3 1
X33 AT 1
X33 VH .7
*
X34 Z 112
X34 F3 1
*
X41 Z 415
X41 F4 1
X41 AT 1
X41 AC -1
X41 VC 4
X41 AH 1
*
X44 Z 371
X44 F4 1
*
X51 Z 265
X51 F5 1
X51 AT 1
X51 VC 2.5
X51 AH 1
*
X54 Z 264
X54 F5 1
*
X61 Z 15
X61 F6 1
X61 AT 1
X61 AH 1
*
X64 Z 61
X64 F6 1
RHS
rhs F1 2754
rhs F2 850
rhs F3 855
rhs F4 1598
rhs F5 405
rhs F6 1761
rhs AT 5000
rhs AC 2247
rhs VH 2440
rhs VC 4160
rhs AH 0
BOUNDS
UP bnd X12 357
UP bnd X13 500
UP bnd X22 197
UP bnd X23 130
UP bnd X32 39
UP bnd X33 170
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
http://www-neos.mcs.anl.gov/neos/faq.html#who
This is a description of how to use e-mail and the
Neos E-mail interface to Clp
(http://www-neos.mcs.anl.gov/neos/solvers/lp:Clp/MPS-help.html)
to solve linear programming problems.
To field of your e-mail message should contain the address
neos@mcs.anl.gov
Questions about using Neos, and user feedback,
can be sent to the address
neos-comments@mcs.anl.gov
Subject field of the e-mail message
(where problem name is replaced by the name of
the particular problem that is being solved).
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Problem Description
]]></comments>
<MPS><![CDATA[*
MPS Input File
*]]></MPS>
<param><![CDATA[
Clp Commands
]]></param>
</document>
where
Problem Description,
MPS Input File,
and
Clp Commands
are described below:
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Example 2.4.3 in Paul Tseng's notes Math 407: Linear Optimization
maximize x1 + x2
subject to x1 + 1.5*x2 <= 30
2*x1 + x2 <= 40
x2 <= 14
x1 , x2 >= 0
The solution is x1 = 15, x2 = 10
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------
*23 56789012 56789012 567890123456
NAME T-2.4.3
ROWS
N z
L r1
L r2
COLUMNS
x1 z 1
x1 r1 1
x1 r2 2
*
x2 z 1
x2 r1 1.5
x2 r2 1
RHS
rhs r1 30
rhs r2 40
BOUNDS
UP bounds x2 14
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
Load Avg: ( 2.0 , 2.0 , 2.0 )
Coin LP version 1.02.02, build Aug 3 2005
At line 4 NAME T-2.4.3
At line 5 ROWS
At line 9 COLUMNS
At line 17 RHS
At line 20 BOUNDS
At line 22 ENDATA
Problem T-2.4.3 has 2 rows, 2 columns and 4 elements
Model was imported from ./clp.mps in 0 seconds
Switching to line mode
Clp:Clp:Clp:Presolve 2 (0) rows, 2 (0) columns and 4 (0) elements
0 Obj -0 Dual inf 2 (2)
2 Obj 25
Optimal - objective value 25
Optimal objective 25 - 2 iterations time 0.002
Clp:
0 r1 30 0.5
1 r2 40 0.25
0 x1 15 -0
1 x2 10 -0
Clp:
%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%
x \in \R^n
to denote the problem variable vector,
b \in \R^m
to denote the problem right hand side vector,
and
A \in \R^{m \times n}
to denote the problem matrix.
Name Record
Rows Record
Columns Record
Rhs Record
Bounds Record
Endata
| Field | Keyword | Op | Name0 | Name1 | Value1 | Name2 | Value2 |
| Columns | 1-* | 2-3 | 5-12 | 15-22 | 25-36 | 40-47 | 50-61 |
It is unspecified if leading and trailing white space has
any significance in the fields Name0, Name1, and
Name2.
For example, the seven characters
"x1 "
may or may not signify the same information as the seven characters
" x1"
.
* is column 1
and any characters in the rest of the line.
NAME Name1
where NAME begins in column 1 and
the string in the Name1
field is the problem name for this input file.
ROWS
where ROW begins in column 1.
Each of the other lines has the following structure:
Op Name0
The string in the Name0 field
in the i-th line below ROWS
specifies the name of the i-th row of the matrix; i.e.,
the name associated with the value
\[
A_{i,1} x_1 + \ldots + A_{i,n} x_n
\]
The character in the Op field
specifies the type of the row and is one of the following values:
| Op | Equation or inequality |
E |
A_{i,1} x_1 + \ldots + A_{i,n} x_n = b_i
|
G |
A_{i,1} x_1 + \ldots + A_{i,n} x_n \geq b_i
|
L |
A_{i,1} x_1 + \ldots + A_{i,n} x_n \leq b_i
|
N |
A_{i,1} x_1 + \ldots + A_{i,n} x_n = z
|
z
is associated with the
first row with the Op field equal to N.
The other rows with the Op field equal to N are ignored.
x_1
, through
x_n
and
the value of the non-zero coefficients in the matrix
A
(zero is the default value for
A_{i,j}
).
The first line of the Columns record contains the text
COLUMNS
where COLUMNS begins in column 1.
Each of the other lines has the structure
Name0 Name1 Value1
or it has the structure
Name0 Name1 Value1 Name2 Value2
The string in the Name0 specifies the name corresponding
to the variable
x_j
for the information on the line.
All of the lines corresponding to one variable
(all the lines with the same value for Name0)
must be grouped together.
The record is called Columns because each variable
corresponds to a column of the matrix
A
.
The string in the Name1 field must be equal
to one of the row names in the Rows: 6.1.d
record.
The floating point number in the Value1 field specifies
the value of A_{i,j}
where
i
corresponds to the string in the Name1 field
and
j
corresponds to the string in the Name0 for this line.
If a string is present in the Name2 field it must be equal
to one of the row names in the Rows: 6.1.d
record.
In this case,
the floating point number in the Value2 field specifies
the value of A_{i,j}
where
i
corresponds to the string in the Name2 field
and
j
corresponds to the string in the Name0 for this line.
RHS
where RHS begins in column 1.
Each of the other lines has the structure
Name0 Name1 Value1
The string in the Name0 field is a name
for the entire right hand side vector
b \in \R^m
.
It must be the same for all of these lines.
The string in the Name1 field must be equal
to one of the row names in the Rows: 6.1.d
record.
It specifies the row index
i
corresponding to the information
on this line.
The floating point number in the Value1 field specifies the value
for this right hand side coefficient
b_i
.
\[
0 \leq x_j < \infty
\]
If these are the only bounds you want,
you need not include a Bounds record.
The first line of the Bounds record contains the text
BOUNDS
where BOUNDS begins in column 1.
Each of the other lines has the structure
Op Name0 Name1 Value1
or the structure
Op Name0 Name1
| Op | Description | |
LO | lower bound |
\ell_j \leq x_j < +\infty
|
UP | upper bound |
0 \leq x_j \leq u_j
|
FX | fixed variable |
x_j = e_j
|
FR | free variable |
-\infty < x_j < +\infty
|
MI | minus infinity |
-\infty < x_j \leq 0
|
PL | plus infinity |
0 \leq x_j < +\infty
|
x
(which column)
is having it's bounds modified by the current line.
The string in the Name1 field must be equal
to one of the variable names in a Name0 field of the
Columns: 6.1.e
record.
LO, UP, or FX
the floating point number in the Value1 field defines
\ell_j
,
u_j
,
e_j
respectively.
Otherwise, the Value1 field should be left empty.
ENDATA
where ENDATA begins in column 1.
*Op Name0--- Name1--- Value1------
*23 56789012 56789012 567890123456
NAME T-2.4.3
ROWS
N z
L r1
L r2
COLUMNS
x1 z 1
x1 r1 1
x1 r2 2
*
x2 z 1
x2 r1 1.5
x2 r2 1
RHS
rhs r1 30
rhs r2 40
BOUNDS
UP bounds x2 14
ENDATA
This input file corresponds to the following optimization problem:
Example 2.4.3 in Paul Tseng's notes Math 407: Linear Optimization
maximize x1 + x2
subject to x1 + 1.5*x2 <= 30
2*x1 + x2 <= 40
x2 <= 14
x1 , x2 >= 0
The solution is x1 = 15, x2 = 10
abcd(efgh)
means that the leading characters abcd
must appear in the command and that any number of the characters
efgh may follow (in that order and are optional).
The characters ( and ) do not appear in the command.
Some of the commands below are of limited use
or not helpful at all when using e-mail with the
Neos interface to Clp
(http://www-neos.mcs.anl.gov/neos/solvers/LP:CLP-MPS/) .
In this case,
a comment to this effect is added at the end of the command description.
direction min(imize)
direction max(imize)
direction zero
This sets the objective direction for optimization
(the default is minimize).
You can also set the objective direction using the commands
ClpCommand: 6.2.e
and
ClpCommand: 6.2.f
.
directory default_directory
This sets the default directory for reading and writing files; i.e.,
for commands like import: 6.2.d
.
This default directory
is initialized to the current working directory; i.e. ./
This command is not useful with the e-mail Neos interface to Clp.
import mps_file_name
This will read the MPS format file specified by mps_file_name.
It will use the default
directory as specified by the directory: 6.2.c
command.
If mps_file_name is equal to $,
the previous value for the file name is used.
The file name is initially empty; i.e. it must be set.
If you have libgz, Clp can read compressed
files by ending mps_file_name with the three characters .gz.
This command is not useful with the e-mail Neos interface to Clp.
max(imize)
This sets the optimization direction to maximize.
(The default optimization direction is to minimize.)
You can also use the command
direction: 6.2.b
to set the optimization
direction to maximize.
min(imize)
This sets the optimization direction to minimize.
(the default optimization direction).
You can also use the command
direction: 6.2.b
to set the optimization
direction to minimize.
primalP(ivot) selection
This command determines the primal pivot selection method.
The possible values for selection are:
auto(matic),
exa(ct),
dant(zig),
part(ial),
steep(est),
change,
sprint.
The Dantzig method is implemented
to show a simple method but its use is deprecated.
Exact devex is the method of choice and there
are two variants which keep all weights updated but only
scan a subset each iteration.
Partial switches this on while change initially does dantzig until the
factorization becomes denser.
This is still a work in progress.
primalS(implex)
This command solves the current model using the primal simplex algorithm.
The default is to use the exact devex column selection method.
The time and iterations may be affected by settings such as
presolve, scaling, crash and also by column selection method,
infeasibility weight and dual and primal tolerances.
solu(tion) solu_file_name
print the current solution to the file specified by
solu_file_name.
This will use the default directory as specified
by the previous directory: 6.2.c
command.
If solu_file_name is $,
the previous value for the solution file name is used.
This solution file name is initialized to stdout
(but using this default does not seem to work).
We use
m
for the number of rows and
n
for the number of columns in the matrix specified by the
MPS input file.
The solution is output in two parts:
The first part is the following values
for
i = 0 , \ldots , m-1
i row_name_i row_primal_i row_dual_value_i
The second part is the following values
for
j = 0 , \ldots , n-1
j column_name_j column_primal_j column_dual_j
If you are using this command with the e-mail Noes interface to Clp,
you should use solu_file_name equal to - which
instructs Clp to write the solution to standard output.
Name: ___________________________
_ characters
(where each _ corresponds to a missing character).
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Problem 2.1 in Vasek Chvatal's book: Linear Programming
maximize 5*x1 + 4*x2 + 3*x3
subject to 2*x1 + 3*x2 + x3 <= 5
4*x1 + x2 + 2*x3 <= 11
3*x1 + 4*x2 + 2*x3 <= 8
x1 , x2 , x3 >= 0
The solution is x1 = 2, x2 = 0, x3 = 1
]]></comments>
<MPS><![CDATA[*
*Op Name0 Name1 Value1
*23 56789012 56789012 567890123456
NAME Prob 2.1
ROWS
N z
L r1
L r2
L r3
COLUMNS
__ z 4
__ r3 4
__ r1 3
__ r2 1
x1 z _
x1 r3 _
x1 r2 _
x1 r1 _
x3 _ 3
x3 __ 2
x3 r3 _
x3 __ 1
RHS
b1 r1 5
__ r2 11
__ r3 8
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Problem 2.1 in Vasek Chvatal's book: Linear Programming
maximize 5*x1 + 4*x2 + 3*x3
subject to 2*x1 + 3*x2 + x3 <= 5
4*x1 + x2 + 2*x3 <= 11
3*x1 + 4*x2 + 2*x3 <= 8
x1 , x2 , x3 >= 0
The solution is x1 = 2, x2 = 0, x3 = 1
]]></comments>
<MPS><![CDATA[*
*Op Name0--- Name1--- Value1------
*23 56789012 56789012 567890123456
NAME Prob 2.1
ROWS
N z
L r1
L r2
L r3
COLUMNS
x2 z 4
x2 r3 4
x2 r1 3
x2 r2 1
*
x1 z 5
x1 r3 3
x1 r2 4
x1 r1 2
*
x3 z 3
x3 r2 2
x3 r3 2
x3 r1 1
RHS
b1 r1 5
b1 r2 11
b1 r3 8
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
| Variable | Description |
| AlkA (AlkB) | # barrels of Alkylate blended for Avgas A (B) |
| CatA (CatB) | # barrels of Catalytic-cracked blended for Avgas A (B) |
| StrA (StrB) | # barrels of Straight-run blended for Avgas A (B) |
| IsoA (IsoB) | # barrels of Isopentane blended for Avgas A (B) |
_
below so that the resulting problem is equivalent to Problem 1.7 of the text:
maximize
____*(3814-AlkA-AlkB+2666-CatA-CatB+4016-StrA-StrB+1300-IsoA-IsoB)
+ ____*(AlkA+CatA+StrA+IsoA)
+ ____*(AlkB+CatB+StrB+IsoB)
subject to
____ + AlkB <= 3814
CatA + ____ <= 2666
StrA + StrB <= ____
IsoA + IsoB <= ____
(100-___)*AlkA + (100-__)*CatA + (100-__)*StrA + (100-___)*IsoA <= 0
(5-_)*AlkA + (8-_)*CatA + (4-_)*StrA + (21-_)*IsoA <= 0
________*AlkB + _______*CatB + _______*StrB + ________*IsoB <= 0
_____*AlkB + _____*CatB + _____*StrB + ______*IsoB <= 0
AlkA , AlkB , CatA , CatB , StrA , StrB , IsoA , IsoB >= 0
Hint:
If
a \in \R
,
b \in \R
,
c \in \R
,
and
a + b \neq 0
,
the following inequalities are equivalent:
\[
\begin{array}{rcl}
\frac{a * AlkA + b * CatA}{AlkA + CatA} & \leq & c
\\
a * AlkA + b * CatA & \leq & (AlkA + CatA) * c
\\
(a-c) * AlkA + (b-c) * CatA & \leq & 0
\end{array}
\]
maximize
4.83*(3814-AlkA-AlkB+2666-CatA-CatB+4016-StrA-StrB+1300-IsoA-IsoB)
+ 6.45*(AlkA+CatA+StrA+IsoA)
+ 5.91*(AlkB+CatB+StrB+IsoB)
subject to
AlkA + AlkB <= 3814
CatA + CatB <= 2666
StrA + StrB <= 4016
IsoA + IsoB <= 1300
(100-107)*AlkA + (100-93)*CatA + (100-87)*StrA + (100-108)*IsoA <= 0
(5-7)*AlkA + (8-7)*CatA + (4-7)*StrA + (21-7)*IsoA <= 0
(91-107)*AlkB + (91-93)*CatB + (91-87)*StrB + (91-108)*IsoB <= 0
(5-7)*AlkB + (8-7)*CatB + (4-7)*StrB + (21-7)*IsoB <= 0
AlkA , AlkB , CatA , CatB , StrA , StrB , IsoA , IsoB >= 0
Name: ___________________________
maximize z = 2*x1 + x2
subject to s1 = 3 - 2*x1 - 3*x2
s2 = 1 - x1 - 5*x2
s3 = 4 - 2*x1 - x2
s4 = 5 - 4*x1 - x2
x1, x2, s1, s2, s3, s4 >= 0
x1 = 0 , x2 = 0 , s1 = 3 , s2 = 1 , s3 = 4 , s4 = 5 , z = 0
x1 for the non-basic pivot variable,
what will be the value of x1 after
one pivot of the simplex algorithm ?
The value corresponding to the basic feasible solution is
x1 = min (3/2 , 1/1 , 4/2 , 5/4) = 1
The equation for x1 after the pivot operation is
x1 = 1 - s2 - 5*x2
Both of the equation and value for x1 above will be considered correct
(and similarly for the questions below).
What will be the corresponding value of z ?
The value corresponding to the basic feasible solution is
z = 2*x1 + x2 = 2
The equation for z after the pivot operation is
z = 2*(1 - s2 - 5*x2) + x2 = 2 - 2*s2 - 9*x2
x2 for the non-basic pivot variable,
what will be the value of x2 after
one pivot of the simplex algorithm ?
x2 = min (3/3 , 1/5 , 4/1 , 5/1) = 1/5
The equation for x2 after the pivot operation is
x2 = 1/5 - (1/5)*x1 - (1/5)*s2
What will be the corresponding value of z ?
z = 2*x1 + x2 = 1/5
The equation for z after the pivot operation is
z = 2*x1 + 1/5 - (1/5)*x1 - (1/5)*s2 = 1/5 + (9/5)*x1 - (1/5)*s2
x1 x2 s1 s2 s3 s4 z b
2 3 1 0 0 0 0 3
1 5 0 1 0 0 0 1
2 1 0 0 1 0 0 4
4 1 0 0 0 1 0 5
2 1 0 0 0 0 -1 0
where s1 and s2 are slack variables and z
is the objective.
Suppose that we preform the pivot operation on the tableau above
that makes the variable x1 basic and the variable s2 non-basic.
What is the resulting tableau ?
x1 x2 s1 s2 s3 s4 z b
0 -7 1 -2 0 0 0 1
1 5 0 1 0 0 0 1
0 -9 0 -2 1 0 0 2
0 -19 0 -4 0 1 0 1
0 -9 0 -2 0 0 -1 -2
Is the corresponding (resulting) basic feasible solution optimal
and why or why not ?
It is optimal because all the coefficients in the last row (which
corresponds to the objective) are negative; i.e., any increase
in the non-basic variables would result in a decrease of the objective.
Name: ___________________________
z
subject to
x \geq 0
,
c^T x - z = b_3
,
A x = ( b_1 , b_2 )^T
,
which has the special form:
\[
\begin{array}{rrrrrrrrrrrrr}
A_{1,1} x_1
& + & A_{1,2} x_2
& + & x_3
& &
& + & A_{1,5} x_5
& &
& = & b_1
\\
A_{2,1} x_1
& + & A_{2,2} x_2
& + &
& + & x_4
& + & A_{2,5} x_5
& &
& = & b_2
\\
c_1 x_1
& + & c_2 x_2
& + &
& &
& + & c_5 x_5
& - & z
& = & b_3
\end{array}
\]
We refer to
x \in \R^5
as the vector of variables
and
z \in \R
as the objective.
The matrix
A \in \R^{2 \times 5}
,
the vector
b \in \R^3
,
and the vector
c \in \R^5
,
are referred to as values.
The basic variables are
\{ x_3 , x_4 \}
and the non-basic variables are
\{ x_1 , x_2 , x_5 \}
.
\[
x_1 = 0 , \; x_2 = 0 , \; x_3 = b_1 \; x_4 = b_2 \; x_5 = 0 \; z = - b_3
\]
b
for the basic solution to be degenerate ?
If
b_1 = 0
, the basic solution is degenerate.
Another possible answer is
b_2 = 0
.
The necessary and sufficient condition
b_1 = 0
or
b_2 = 0
is also a possible answer to this problem.
b
for the basic solution to not be degenerate ?
The basic solution is not degenerate if and only if
b_1 \neq 0
and
b_2 \neq 0
.
b
for the corresponding basic solution to be feasible ?
The basic solution is feasible if and only if
b_1 \geq 0
and
b_2 \geq 0
.
A_{1,1} < 0
,
A_{2,1} < 0
and
c_1 > 0
.
Can you determine anything about the optimal solutions
from this information ?
There are no optimal solutions because the problem is unbounded; i.e.,
given any feasible solution, there is another feasible solution with a larger
objective function value.
b_1 \geq 0
,
b_2 \geq 0
,
c_1 > 0
,
c_2 < 0
,
c_5 < 0
,
A_{1,1} < 0
,
A_{2,1} > 0
.
What is the value of the objective function corresponding to the
basic solution after one pivot of the Simplex Method ?
After the pivot,
x_1 = b_2 / A_{2,1}
and
z = - b_3 + c_1 x_1 = - b_3 + c_1 b_2 / A_{2,1}
.
{1, 2} into the integer
{1, 2, 3}.
We can prescribe such a mapping as a vector
v \in \R^2
; e.g.,
the basis
B : {1, 2} --> {1, 2, 3}
where B(1) = 2, B(2) = 1 can be represented as
the vector (2, 1).
Using this representation,
what are all the possible basis for two equations and three variables ?
(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)
.
Name: ___________________________
\[
\begin{array}{c}
\begin{array}{lll}
{\rm maximize} & c^T x
\\
{\rm subject \; to} & A x = b & x \in \R_+^6
\end{array}
\\
{\rm where} \;
A = \left( \begin{array}{cccccc}
1 & 2 & 3 & 0 & 0 & 1 \\
4 & 5 & 6 & 0 & 1 & 0 \\
7 & 8 & 9 & 1 & 0 & 0
\end{array} \right)
\; , \;
b = \left( \begin{array}{ccc}
4 \\
10 \\
16
\end{array} \right)
\; , \;
c = (0, 1, 2, 0 , 0 , 0)^T
\end{array}
\]
Suppose we use Bland's pivot rule.
B
can be represented by
B(1) = 6
,
B(2) = 5
, and
B(3) = 4
.
You can also represent this mapping by
( x_6 , x_5 , x_4 )
or by
(6, 5, 4)
.
j
such that
c_j > 0
; i.e., the candidates are
x_2
and
x_3
.
Bland's rule chooses the candidate with the smaller index; i.e.,
x_2
.
K
as the set of row indices
k
such that
A_{k,2} > 0
.
The candidate variable indices are
B(i)
for each row index
i
such that
\[
b_i / A_{i,2} = \min \{ b_k / A_{k,2} : k \in K \}
\]
Thus the candidate variables are
x_6
,
x_5
and
x_4
.
Bland's rule chooses the candidate with the smaller index; i.e.,
x_4
.
A
corresponds
to the next pivot operation ?
Row 3 and Column 2.
Row 3 corresponds to the leaving variable
because
B(3) = 4
.
Column 2 corresponds to the entering variable
because
x_2
corresponds to column 2.
\[
\begin{array}{c}
\begin{array}{lll}
{\rm maximize} & c^T x
\\
{\rm subject \; to} & A x \leq b & x \in \R_+^3
\end{array}
\\
{\rm where} \;
A = \left( \begin{array}{cccccc}
2 & 3 & 1 \\
4 & 1 & 2 \\
3 & 4 & 2
\end{array} \right)
\; , \;
b = \left( \begin{array}{ccc}
5 \\
11 \\
8
\end{array} \right)
\; , \;
c = \left( \begin{array}{ccc}
5 \\
4 \\
3
\end{array} \right)
\end{array}
\]
According to Equation (2.6) of the text
\hat{x} = (2, 0, 1)^T
is a solution
of this problem.
\hat{x}
is feasible ?
It follows from the definitions above
\hat{x} \in \R_+^3
and
\[
A \hat{x} = (5, 10, 8)^T \leq b
\]
Thus
\hat{x}
is a feasible point for the primal problem.
\hat{y} \in \R^3
satisfies
the following complementary slackness conditions:
\[
\begin{array}{rcl}
0 & = &
( \hat{y}_1 A_{1,1} + \hat{y}_2 A_{2,1} + \hat{y}_3 A_{3,1} - c_1 ) \hat{x}_1
\\
0 & = &
( b_2 - A_{2,1} \hat{x}_1 - A_{2,2} \hat{x}_2 - A_{2,3} \hat{x}_3 ) \hat{y}_2
\\
0 & = &
( \hat{y}_1 A_{1,3} + \hat{y}_2 A_{2,3} + \hat{y}_3 A_{3,3} - c_3 ) \hat{x}_3
\end{array}
\]
We have
\[
\begin{array}{rcl}
10 & = & A_{2,1} \hat{x}_1 + A_{2,2} \hat{x}_2 + A_{2,3} \hat{x}_3
\\
11 & = & b_2
\end{array}
\]
It follows that
\hat{y}_2 = 0
and
\[
\begin{array}{rcl}
c_1 & = &
\hat{y}_1 A_{1,1} + \hat{y}_3 A_{3,1}
\\
c_3 & = &
\hat{y}_1 A_{1,3} + \hat{y}_3 A_{3,3}
\\
5 & = & 2 \hat{y}_1 + 3 \hat{y}_3
\\
3 & = & \hat{y}_1 + 2 \hat{y}_3
\end{array}
\]
which yields
\hat{y} = (1, 0, 1)^T
.
\hat{y}
is a feasible point for the
dual problem ?
It follows from this definition that
\hat{y} \in \R_+^3
and
\[
A^T \hat{y} = (5, 7, 3)^T \geq c
\]
\[
\begin{array}{rcl}
0 & = &
( b_1 - A_{1,1} \hat{x}_1 - A_{1,2} \hat{x}_2 - A_{1,3} \hat{x}_3 ) \hat{y}_1
\\
0 & = &
( \hat{y}_1 A_{1,2} + \hat{y}_2 A_{2,2} + \hat{y}_3 A_{3,2} - c_2 ) \hat{x}_2
\\
0 & = &
(b_3 - A_{3,1} \hat{x}_1 - A_{3,2} \hat{x}_2 - A_{3,3} \hat{x}_3 ) \hat{y}_3
\end{array}
\]
We have
\hat{x}_2 = 0
, hence the second equation above is satisfied.
The other two follow form
A \hat{x} = (5, 10, 8)^T
because
\[
\begin{array}{rcl}
A_{1,1} \hat{x}_1 + A_{1,2} \hat{x}_2 + A_{1,3} \hat{x}_3
& = & 5
\\
& = & b_1
\\
A_{3,1} \hat{x}_1 + A_{3,2} \hat{x}_2 + A_{3,3} \hat{x}_3
& = & 8
\\
& = & b_3
\end{array}
\]
Name: ___________________________
A \in \R^{2 \times 2}
,
b \in \R^2
, and
c \in \R^2
.
The corresponding primal problem is
\[
\begin{array}{rcl}
{\rm maximize} & c_1 x_1 + c_2 x_2 &
{\rm with \; respect \; to} \; x \in \R_+^2
\\
{\rm subject \; to} & A_{11} x_1 + A_{12} x_2 \leq b_1 \\
& A_{21} x_1 + A_{22} x_2 \leq b_2
\end{array}
\]
Our tableau form for this problem is to maximize
z \in \R
with respect to
x \in \R_+^2
,
s \in \R_+^2
, and subject to
\[
\left( \begin{array}{rrrrrr}
A_{11} & A_{12} & 1 & 0 & 0 \\
A_{21} & A_{22} & 0 & 1 & 0 \\
c_1 & c_2 & 0 & 0 & -1
\end{array} \right)
\left( \begin{array}{c} x \\ s \\ z \end{array} \right)
=
\left( \begin{array}{c} b_1 \\ b_2 \\ 0 \end{array} \right)
\hspace{1cm} ( \bullet )
\]
If
A_{11}
is not zero,
the following equation is equivalent to the equation above
\[
\left( \begin{array}{ccccc}
1 &
A_{12} A_{11}^{-1} &
A_{11}^{-1} &
0 &
0
\\
0 &
A_{22} - A_{21} A_{12} A_{11}^{-1} &
- A_{21} A_{11}^{-1} &
1 &
0
\\
0 &
c_2 - c_1 A_{12} A_{11}^{-1} &
- c_1 A_{11}^{-1} &
0 &
-1
\end{array} \right)
\left( \begin{array}{c} x_1 \\ x_2 \\ s_1 \\ s_2 \\ z \end{array} \right)
\left( \begin{array}{c}
b_1 A_{11}^{-1}
\\
b_2 - A_{21} b_1 A_{11}^{-1}
\\
- c_1 b_1 A_{11}^{-1}
\end{array} \right)
\hspace{1cm} (\star)
\]
A
,
b
and
c
; i.e.,
x
,
s
, and
z
must be expressed in terms of
A
,
b
and
c
.
(x, s)
that
corresponds to
(\star)
?
\[
x_1 = b_1 A_{11}^{-1} \; , \;
x_2 = 0 \; , \;
s_1 = 0 \; , \;
s_2 = b_2 - A_{21} b_1 A_{11}^{-1}
\]
z
corresponds to the basic solution ?
\[
z = c_1 b_1 A_{11}^{-1}
\]
\[
b_1 A_{11}^{-1} \geq 0 \; {\rm and} \;
b_2 - A_{21} b_1 A_{11}^{-1} \geq 0
\]
\[
c_2 - c_1 A_{12} A_{11}^{-1} \leq 0 \; {\rm and} \;
- c_1 A_{11}^{-1} \leq 0
\]
\[
b_1 A_{11}^{-1} \neq 0 \; {\rm and} \;
b_2 - A_{21} b_1 A_{11}^{-1} \neq 0
\]
Note that
\neq 0
could be replace by
> 0
in this answer.
y \in \R_+^2
that solves the dual problem ?
What is the corresponding value of the dual objective
b^T y
?
\[
\begin{array}{rcl}
y_1 & = & c_1 A_{11}^{-1} \\
y_2 & = & 0 \\
b^T y & = & b_1 y_1 + b_2 y_2 = b_1 c_1 A_{11}^{-1}
\end{array}
\]
A^T y \geq c
.
It suffices to show that
A^T y - c \geq 0
.
\[
A^T y - c
=
\left(
\begin{array}{c}
A_{11} y_1 + A_{21} y_2
\\
A_{12} y_1 + A_{22} y_2
\end{array}
\right)
- c
=
\left(
\begin{array}{c}
0
\\
c_1 A_{12} A_{11}^{-1} - c_2
\end{array}
\right)
\]
This must be greater than or equal zero
for the basic solution to be optimal.
B : \{ 1, 2 \} \rightarrow \{ 1 , 2 , 3 , 4 \}
that corresponds to
(\star)
?
\[
B(1) = 1 \; , \; B(2) = 4
\]
B
as in the previous question and
we define
T
to be the first two rows
and first four columns of the
3 \times 5
matrix in
( \bullet )
.
We use
T_B \in \R^{2 \times 2}
to denote the matrix with i-th column
equal to column
B(i)
of
T
.
What are the matrices
T_B
and
T_B^{-1}
?
\[
T_B
=
\left( \begin{array}{rrrrrr}
A_{11} & 0 \\
A_{21} & 1
\end{array} \right)
\; , \;
T_B^{-1}
=
\left( \begin{array}{rrrrrr}
1 & 0 \\
- A_{21} & 1
\end{array} \right)
\left( \begin{array}{rrrrrr}
A_{11}^{-1} & 0 \\
0 & 1
\end{array} \right)
=
\left( \begin{array}{rrrrrr}
1 & 0 \\
- A_{21} & 1
\end{array} \right)
=
\left( \begin{array}{rrrrrr}
A_{11}^{-1} & 0 \\
-A_{21} A_{11}^{-1} & 1
\end{array} \right)
\]
Note that if you got a different result for
B
in the previous
question, this question will be graded as if your result for
B
is the correct.
Name: ___________________________
Nutritional
|
Corn
|
Tankage
|
Alfalfa
|
Requirements
|
| Ingredient | (units/kg) | (units/kg) | (units/kg) | (units/day) |
| Carbohydrates | 90 | 20 | 40 | 200 |
| Protein | 30 | 80 | 60 | 180 |
| Vitamins | 10 | 20 | 50 | 150 |
| Cost | 35 | 30 | 25 |
x_1
(
x_2
,
x_3
)
be the number of kilograms of corn
(tankage, alfalfa) that the farmer
feeds to each pig each day.
A \in \R^{3 \times 3}
,
b \in \R^3
and
c \in \R^3
does the problem above
correspond to
\[
\begin{array}{rcl}
{\rm maximize} & c^T x & {\rm with \; respect \; to} \; x \in \R_+^3 \\
{\rm subject \; to} & A x \leq b
\end{array}
\]
The values are
\[
A = \left( \begin{array}{lll}
-90 & -20 & -40 \\
-30 & -80 & -60 \\
-10 & -20 & -50
\end{array} \right)
\; , \;
b = \left( \begin{array}{l} -200 \\ -180 \\ -150 \end{array} \right)
\; , \;
c = \left( \begin{array}{l} -35 \\ -30 \\ -25 \end{array} \right)
\]
D \in \R^{3 \times 3}
,
e \in \R^3
and
f \in \R^3
such that the dual problem is equivalent to
\[
\begin{array}{rcl}
{\rm maximize} & f^T y & {\rm with \; respect \; to} \; y \in \R_+^3 \\
{\rm subject \; to} & D y \leq e
\end{array}
\]
The dual, of the problem in the previous question, is
\[
\begin{array}{rcl}
{\rm minimize} & b^T y & {\rm with \; respect \; to} \; y \in \R_+^3 \\
{\rm subject \; to} & A^T y \geq c
\end{array}
\]
It follows that
\[
D = - A^T = \left( \begin{array}{lll}
90 & 30 & 10 \\
20 & 80 & 20 \\
40 & 60 & 50
\end{array} \right)
\; , \;
f = -b = \left( \begin{array}{l} 200 \\ 180 \\ 150 \end{array} \right)
\; , \;
e = - c = \left( \begin{array}{l} 35 \\ 30 \\ 25 \end{array} \right)
\]
\[
\hat{y} = ( .36585 , 0 , .20731 )^T
\]
what is the solution of the problem in the first question ?
Hint, treat the equality above as approximately equal and treat nearly
zero values as zero when applying the complementary slackness conditions.
\[
A^T y - c = \left( \begin{array}{rrrrr}
- 90 \times .36585 & - & 10 \times .20731 & + & 35 \\
- 20 \times .36585 & - & 20 \times .20731 & + & 30 \\
- 40 \times .36585 & - & 50 \times .20731 & + & 25
\end{array} \right)
=
\left( \begin{array}{c} .0004 \\ 18.5368 \\ .0005 \end{array} \right)
\]
We use
\hat{x}
to denote the solution of the problem in
the first question.
It follows from the result above
(and the complementary slackness conditions) that
\hat{x}_2 = 0
.
It also follows from
\hat{y}_1 \neq 0
and
\hat{y}_3 \neq 0
that
\[
\begin{array}{rcrrr}
b_1 & = & A_{1,1} \hat{x}_1 & + & A_{1,3} \hat{x}_3 \\
b_3 & = & A_{3,1} \hat{x}_1 & + & A_{3,3} \hat{x}_3 \\
200 & = & 90 \hat{x}_1 & + & 40 \hat{x}_3 \\
150 & = & 10 \hat{x}_1 & + & 50 \hat{x}_3 \\
20 & = & 9 \hat{x}_1 & + & 4 \hat{x}_3 \\
15 & = & \hat{x}_1 & + & 5 \hat{x}_3 \\
115 & = & & & 41 \hat{x}_3 \\
20 & = & 9 \hat{x}_1 & + & 4 \times 115 / 41.
\end{array}
\]
It follows that
\[
\hat{x} = ( .97561 , 0 , 2.80488 )^T
\]
As a check of this solution we note that
\[
A_{1,2} \hat{x}_1 + A_{2,2} \hat{x}_2 + A_{3,3} \hat{x}_3
=
-30 \times .97561 - 60 \times 2.80488
=
-197.567
\leq
-180
= b_2
\]
This implies that all the complimentary slackness conditions are satisfied and
both
\hat{x}
and
\hat{y}
are feasible,
thus they are also optimal.
(It is ok if your answer was left as a fraction; for example,
\hat{x}_3 = 115 / 41
.)
| corn | .97561 |
| tankage | 0 |
| alfalfa | 2.80488 |
Name: ___________________________
\[
\begin{array}{rrrrl}
{\rm maximize} & 3 x_1 & + 2 x_2 & + 4 x_3 &
{\rm with \; respect \; to} \; x \in \R_+^3
\\
{\rm subject \; to} & x_1 & + x_2 & + 2 x_3 & \leq 4 \\
& 2 x_1 & & + 3 x_3 & \leq 5 \\
& 2 x_1 & + x_2 & + 3 x_3 & \leq 7
\end{array}
\]
A \in \R^{3 \times 3}
,
b \in \R^3
and
c \in \R^3
does the problem above
correspond to
\[
\begin{array}{rcl}
{\rm maximize} & c^T x &
{\rm with \; respect \; to} \; x \in \R_+^3 \\
{\rm subject \; to} & A x \leq b
\end{array}
\]
The values are
\[
A = \left( \begin{array}{lll}
1 & 1 & 2 \\
2 & 0 & 3 \\
2 & 1 & 3
\end{array} \right)
\; , \;
b = \left( \begin{array}{l} 4 \\ 5 \\ 7 \end{array} \right)
\; , \;
c = \left( \begin{array}{l} 3 \\ 2 \\ 4 \end{array} \right)
\]
\hat{x} \in \R_+^3
to the problem above ?
\[
\hat{x}_1 = 2.5 \; , \; \hat{x}_2 = 1.5 \; , \; \hat{x}_3 = 0
\]
A \hat{x}
and
does
\hat{x}
satisfy the primal feasibility conditions
\hat{x} \geq 0
and
A \hat{x} \leq b
(equation 5.14 of text) ?
\[
A \hat{x} = (4 , 5 , 6.5 )^T
\]
and yes,
\hat{x} \geq 0
and
A \hat{x} \leq b
.
\[
\begin{array}{rcl}
{\rm minimize} & b^T y & {\rm with \; respect \; to} \; y \in \R_+^3 \\
{\rm subject \; to} & A^T y \geq c
\end{array}
\]
The optimal solution to the dual
\hat{y} \in \R_+^3
is given by the optimal dictionary as
\[
\hat{y}_1 = 2 \; , \; \hat{y}_2 = .5 \; , \; \hat{y}_3 = 0
\]
One can also compute this solution using the complementarity conditions.
To be specific,
\hat{y}_3
must be zero because
\[
b_3 - ( A \hat{x} )_3 \neq 0
\]
The value of the other components of
\hat{y}
follow from
\hat{x}_1 \neq 0
and
\hat{x}_2 \neq 0
and
\[
\begin{array}{rcl}
c_1 & = & \hat{y}_1 A_{1,1} + \hat{y}_2 A_{2,1} \\
c_2 & = & \hat{y}_1 A_{1,2} + \hat{y}_2 A_{2,2} \\
3 & = & \hat{y}_1 + 2 \hat{y}_2 \\
2 & = & \hat{y}_1
\end{array}
\]
What is the value of
A^T \hat{y}
?
Does
\hat{y}
satisfy the
dual feasibility conditions
\hat{y} \geq 0
and
A^T \hat{y} \geq c
(equation 5.15 of the text) ?
\[
A^T \hat{y} = (3, 2, 5.5)^T
\]
and yes,
\hat{y} \geq 0
and
A^T \hat{y} \geq c
.
\hat{y}
?
What is the value of the primal objective function at the point
\hat{x}
?
Are the primal and dual objective values equal (equation 5.16 of the text) ?
The primal objective value is
\[
b^T \hat{y} = 8 + 2.5 = 10.5
\]
The dual objective value is
\[
c^T \hat{x} = 7.5 + 3 = 10.5
\]
Yes, they are equal.
\newcommand{\P}{{\bf P}}
n = 2
is
maximize 10 * x1 + x2
subject to x1 <= 1
20 * x1 + x2 <= 100
x1 , x2 >= 0
Use the dictionary simplex method to solve this problem
(find the optimal value for x1 and x2)
starting from the representation
maximize z = 10 * x1 + x2
subject to s1 = 1 - x1
s2 = 100 - 20 * x1 - x2