 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2018/algorithms/3/a/solution

 Top articles  Latest articles New article in topic

Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 3 / a / Solution by

Codex  0 2026-10-31

Use the standard maximum form of a linear program

max {c^{T} z : A z \leq b, z \geq 0} .

(1)

An arbitrary linear program can be converted by the following operations.

Replace minimization of $c^{T} x$ by maximization of $- c^{T} x$ , and negate the resulting optimal value when translating back. A constant term in the objective is recorded separately.
Replace every unrestricted variable $x_{j}$ by $z_{j}^{+} - z_{j}^{-}$ with both new variables nonnegative. A nonpositive variable can instead be negated. A lower bound $x_{j} \geq ℓ$ can be eliminated by writing $x_{j} = ℓ + z_{j}$ , $z_{j} \geq 0$ ; other bounds remain linear inequalities.
Multiply a $\geq$ row by $- 1$ . Replace an equality $a^{T} x = b$ by the pair $a^{T} x \leq b$ and $- a^{T} x \leq - b$ .

These substitutions preserve the attainable objective values, up to the stated sign and constant corrections, and map feasible points in both directions. An alternative standard-form convention uses

A z = b, z \geq 0

: add a nonnegative slack variable to each upper-bound row, or subtract a nonnegative surplus variable from a lower-bound row. The inequality convention above is used in the remaining solutions.

 Read the full article

 New to topics? Read the docs here!