Summary of Chapter 4

Section 4.4 Summary of Chapter 4

We recall that at each corner or extreme point solution, this solution lies on the intersection of

n

bounding hyperplanes of the feasible region. We also note that the orthogonal vector for the objective plane may be written as a linear combination of the orthogonal vectors for these bounding hyperplanes, and in particular, the coefficients of the linear combination are exactly the negative of the

c_{j}^{'} s

in the corresponding tableau.

$x_{1}$	$x_{2}$	$\dots$	$x_{m}$	$- 1$
$a_{11}$	$a_{12}$	$\dots$	$a_{1 m}$	$b_{1}$	$= - t_{1}$
$a_{21}$	$a_{22}$	$\dots$	$a_{2 m}$	$b_{2}$	$= - t_{2}$
$⋮$	$⋮$	$⋱$	$⋮$	$⋮$	$⋮$
$a_{n 1}$	$a_{n 2}$	$\dots$	$a_{n m}$	$b_{n}$	$= - t_{n}$
$c_{1}$	$c_{2}$	$\dots$	$c_{m}$	$d$

🔗

In some sense what

- c_{j}

tells us is how much

f

increases if the corresponding

x_{j}

decreases by one, i.e. the bound associated with

x_{j}

were relaxed by one. This gives us a way of determining how relaxing each of the constraints compare to each other, and their relative value to each other. So in the case of Exploration 4.1.1, We have

$x_{1}$	$x_{2}$	$- 1$
$3$	$1$	$34$	$= - t_{1}$
$1$	$1$	$14$	$= - t_{2}$
$3$	$2$	$0$	$= f$

We have that the normal vector for the objective plane,

[\begin{matrix} 3 \\ 2 \end{matrix}]

may be written as

[\begin{matrix} 3 \\ 2 \end{matrix}] = - 3 [\begin{matrix} - 1 \\ 0 \end{matrix}] + (- 2) [\begin{matrix} 0 \\ - 1 \end{matrix}],

and lowering

x_{1}

by 1 decreases the objective by 3, and lowering

x_{2}

by 1. decreases it by 2.

🔗

But should we pivot to

$t_{1}$	$t_{2}$	$- 1$
$1 / 2$	$- 1 / 2$	$10$	$= - t_{1}$
$- 1 / 4$	$3 / 2$	$4$	$= - t_{2}$
$- 1 / 2$	$- 3 / 2$	$- 38$	$= f$

🔗

Then

[\begin{matrix} 3 \\ 2 \end{matrix}] = \frac{1}{2} [\begin{matrix} 3 \\ 1 \end{matrix}] + \frac{3}{2} [\begin{matrix} 1 \\ 1 \end{matrix}]

and decreasing

t_{1}

by 1 increases the objective by

\frac{1}{2}

and decreasing

t_{2}

by 1 increases the objective by

\frac{3}{2} .

Note that this is equivalent to saying how much value would be gained should there by one more newt eye or frog respectively.

🔗

This inspires us to define the dual problem of a primal maximization problem in Definition 4.1.5, where the

y_{i}

are the weights or coefficients of the normal vectors for bounding hyperplanes of the feasible region. We may define the

s_{j}

to be the slack variable for each dual constraint so that

(\sum_{i = 1}^{n} a_{i j} y_{i}) + s_{j} = c_{j} x,

or equivalently:

🔗

\begin{aligned} [\begin{array}{c} c_{1} \\ c_{2} \\ ⋮ \\ c_{m} \end{array}] & = y_{1} [\begin{array}{c} a_{11} \\ a_{12} \\ ⋮ \\ a_{1 m} \end{array}] + y_{2} [\begin{array}{c} a_{21} \\ a_{22} \\ ⋮ \\ a_{2 m} \end{array}] + \dots + y_{n} [\begin{array}{c} a_{n 1} \\ a_{n 2} \\ ⋮ \\ a_{n m} \end{array}] \\ + s_{1} [\begin{array}{c} 1 \\ 0 \\ ⋮ \\ 0 \end{array}] + s_{2} [\begin{array}{c} 0 \\ 1 \\ ⋮ \\ 0 \end{array}] + \dots + s_{m} [\begin{array}{c} 0 \\ 0 \\ ⋮ \\ 1 \end{array}] \end{aligned}

and we have feasibility if and only if each

y_{i}, s_{j} \geq 0 .

🔗

Figure 4.4.1. Normal Vectors and Sensitivity Analysis.

🔗

We then note that by reformulating the primal and dual problem using matrix algebra, then for feasible

x, y,

we have that

🔗

f = c^{⊤} x \leq c^{⊤} A b \leq y^{⊤} b = g

which is the statement of the Weak Duality Theorem Proposition 4.2.3. In particular, if

f = g

for feasible

x, y,

then both

f, g

are optimal.

🔗

It turns out the converse to this statement is true as well. To show this, we suppose that

f

achieves optimality at

$t_{?}$	$x_{?}$	$\dots$	$t_{?}$	$- 1$
$a_{11}^{*}$	$a_{12}^{*}$	$\dots$	$a_{1 m}^{*}$	$b_{1}^{*}$	$= - x_{?}$
$a_{21}^{*}$	$a_{22}^{*}$	$\dots$	$a_{2 m}^{*}$	$b_{2}^{*}$	$= - x_{?}$
$⋮$	$⋮$	$⋱$	$⋮$	$⋮$	$⋮$
$a_{n 1}^{*}$	$a_{n 2}^{*}$	$\dots$	$a_{n m}^{*}$	$b_{n}^{*}$	$= - t_{?}$
$c_{1}^{*}$	$c_{2}^{*}$	$\dots$	$c_{m}^{*}$	$d^{*}$

🔗

We let

- c_{j} = t_{i}, s_{j}

depending on which variable

c_{j}

is the coefficient for, and by letting each other

y_{i}, s_{j} = 0,

we have that

🔗

\begin{aligned} f = \sum_{i = 1} c_{j} x_{j} - d & = \sum_{i = 1}^{n} (- y_{i}) t_{i} + \sum_{j = 1}^{m} (- s_{j}) x_{j} - d^{*} \\ = \sum_{i = 1}^{n} (- y_{i}) (b_{i} - \sum_{j = 1}^{m} a_{i j} x_{j}) + \sum_{j = 1}^{m} (- s_{j}) x_{j} - d^{*} \\ = \sum_{j = 1}^{m} ((\sum_{i = 1}^{n} y_{i} a_{i j}) - s_{j}) x_{j} - (d^{*} + \sum_{i = 1}^{n} y_{i} b_{i}) \end{aligned}

🔗

We note that since the above tableau satisfies the conditions for an optimal basic solution, each

y_{i}, s_{j} \geq 0 .

Since the above equality is an equality of functions of

x_{1}, \dots, x_{m},

by comparing coefficients of

x_{j},

we have

\sum_{i = 1}^{n} y_{i} a_{i j} \geq c_{j}

and

y

is a feasible solution. Then we also have that

- d^{*} = \sum_{i = 1}^{n} y_{i} b_{i} - d .

The left hand side is the optimal value for

f,

and the right hand side is the current value of

g

for this choice of

y .

So by Proposition 4.2.3, we prove the Strong Duality Theorem Theorem 4.2.4.

🔗

Figure 4.4.2. Proofs of the duality theorems.

🔗

We then note that the dual problem may be recorded simultaneously as the primal problem within the same tableau

	$x_{1}$	$\dots$	$x_{m}$	$- 1$
$y_{1}$	$a_{11}$	$\dots$	$a_{1 m}$	$b_{1}$	$= - t_{1}$
$⋮$	$⋮$	$⋱$	$⋮$	$⋮$	$⋮$
$y_{n}$	$a_{n 1}$	$\dots$	$a_{n m}$	$b_{n}$	$= - t_{n}$
$- 1$	$c_{1}$	$\dots$	$c_{m}$	$d$	$= f$
	$= s_{1}$	$\dots$	$= s_{m}$	$= g$

and that by using similar arguments as we did in Chapter 2, we may establish conditions for determining the feasibility, optimality, and boundedness if the dual problem. A basic dual variable is feasible if and only if each

c_{j} \leq 0,

and if we had a

c_{j} >

but each

a_{i j} \leq 0

for that problem, then the problem is infeasible, since this inequality can never be satisfied. If the basic dual is feasible then it is also optimal if and only if

b_{i} \geq 0 .

However, if the basic dual is feasible but there is a row

i

where

a_{i j} \geq 0,

then the dual region is unbounded, and if additionally

b_{i} < 0,

then the dual problem is unbounded below. These boundedness conditions are sufficient but not necessary, the reader is encouraged to come up with their own counterexamples to necessity.

🔗

We conclude by observing that if a primal problem has an unconstrained variable, the corresponding dual variable must be zero, since the associated hyperplane is not a bounding hyperplane. Similarly, if we had an equality constraint in the primal with corresponding slack set to zero, the corresponding dual is allowed to be unconstrained, since it is no longer relevant whether pivoting away from this plane improves the primal objective.

🔗

Figure 4.4.3. The dual problem as recorded in tableaus.

🔗

Prev Top Next