7H (Optimisation)

Introduce nonnegative dual variables

y

and

z

maximise subject to t y + rz b_{i} y + c_{i} z \leq a_{i} (1 \leq i \leq n), y, z \geq 0.

Indeed, if

x

and

(y, z)

are feasible, then

t y + rz \leq y \sum_{i} b_{i} x_{i} + z \sum_{i} c_{i} x_{i} = \sum_{i} (b_{i} y + c_{i} z) x_{i} \leq \sum_{i} a_{i} x_{i},

b

The dual from part (a) is

maximise subject to 7 y + 11 z y + z \leq 3, y \leq 2, z \leq 2, y + 2 z \geq 2, qq u a d y, z \geq 0.

The point

(y, z) = (1, 2)

is dual feasible and has value

29

. The primal point

(x_{1}, x_{2}, x_{3}, x_{4}) = (7, 0, 4, 0)

is feasible and also has objective value

3 (7) + 2 (4) = 29.

By weak duality, neither point can be improved, so

min = 29, (x_{1}, x_{2}, x_{3}, x_{4}) = (7, 0, 4, 0) .

x_{2}

and

x_{4}

x_{2} = x_{4} = 0

at any optimum; the two tight primal constraints then force

x_{1} = 7

and

x_{3} = 4

. Thus the displayed minimizer is unique.

There are no discussions about this article yet.

There are currently no matching articles.