Practice: Converting a Linear Program to Standard Form

Recognition · Direct application

A linear program contains the constraint $2 x_{1} + x_{2} \geq 6$ . Which rewriting puts this constraint into standard form?

2 hints available, least help first.

Hint 1: Retrieval cue

Does the left-hand side fall short of the bound, or exceed it?

Hint 2: Concept cue

The introduced variable must be nonnegative. Decide whether that quantity has to be added to or removed from the left-hand side to reach equality.

Classification

A program is being put into standard form. It has original variables $x_{1} \geq 0$ and $x_{2}$ free, a surplus variable $e_{1}$ introduced for a $\geq$ constraint, and a slack variable $s_{1}$ introduced for a $\leq$ constraint. The free variable is split as $x_{2} = x_{2}^{+} - x_{2}^{-}$ .

In the final standard-form program, select every variable that carries a nonnegativity restriction.

Select every option that applies

Every option that applies, and only those. The set is checked as a whole.

Direct application · Interpretation

A program asks to maximise $3 x_{1} + 2 x_{2}$ . Standard form is a minimisation. What replaces the objective, and what happens to the answer?

1 hint available, least help first.

Hint 1: Retrieval cue

If $a > b$ , what is the relationship between $- a$ and $- b$ ?

Classification

A program contains the free variable $x_{3}$ , which is replaced by $x_{3} = x_{3}^{+} - x_{3}^{-}$ with $x_{3}^{+}, x_{3}^{-} \geq 0$ .

Select every statement that must hold after this replacement.

Select every option that applies

Every option that applies, and only those. The set is checked as a whole.

The substitution is applied in the objective and in every constraint containing $x_{3}$ .
Both $x_{3}^{+}$ and $x_{3}^{-}$ carry nonnegativity restrictions.
The pair $(x_{3}^{+}, x_{3}^{-})$ representing a given value of $x_{3}$ is unique.
The replacement adds one variable to the program, since $x_{3}$ is removed and two are added.
The substitution is needed only in constraints where $x_{3}$ has a positive coefficient.

Direct application · Construction

Convert the following linear program to standard form, showing the resulting objective, constraints, and sign restrictions. State how the optimal value of your converted program relates to the optimal value of the original.

\begin{aligned} max & 5 y_{1} - y_{2} \\ subject to & y_{1} + 2 y_{2} \leq 10, \\ y_{1} - y_{2} \geq 3, \\ y_{1} \geq 0, y_{2} free . \end{aligned}

Write your answer

Write your answer, then compare it with the worked solution.

2 hints available, least help first.

Hint 1: Retrieval cue

Which of the three standard-form conditions does this program currently violate?

Hint 2: Strategy cue

Handle the objective direction, then each constraint in turn, then the free variable. Substitute the split variable everywhere it appears.

Compare with the worked solution

Comparing does not record a result. Judging your own written answer cannot show that you can do this without help.

Objective: minimize $- 5 y_{1} + y_{2}^{+} - y_{2}^{-}$ . Constraints: $y_{1} + 2 y_{2}^{+} - 2 y_{2}^{-} + s_{1} = 10$ ; $y_{1} - y_{2}^{+} + y_{2}^{-} - e_{1} = 3$ . Sign restrictions: $y_{1}, y_{2}^{+}, y_{2}^{-}, s_{1}, e_{1} \geq 0$ . If the converted program attains minimum $v$ , the original maximum is $- v$ , and the original $y_{2}$ is recovered as $y_{2}^{+} - y_{2}^{-}$ .

A complete answer does each of these:

equivalence statement
free variable split
nonnegativity complete
objective direction
slack surplus sign

Error diagnosis · Explanation

A student converts the constraint $4 x_{1} + 3 x_{2} \geq 12$ into $4 x_{1} + 3 x_{2} + s = 12$ with $s \geq 0$ , and reports that the program is now in standard form.

Identify the error, explain why the rewritten constraint does not describe the same feasible set, and give a specific point that satisfies the original constraint but not the student's version.

Write your answer

Write your answer, then compare it with the worked solution.

2 hints available, least help first.

Hint 1: Retrieval cue

Solve the student's equation for $4 x_{1} + 3 x_{2}$ and read off what it now requires.

Hint 2: Concept cue

With $s \geq 0$ , does $4 x_{1} + 3 x_{2} = 12 - s$ allow the left-hand side to exceed $12$ ?

Compare with the worked solution

Comparing does not record a result. Judging your own written answer cannot show that you can do this without help.

The surplus must be subtracted, not added: the correct conversion is $4 x_{1} + 3 x_{2} - e = 12$ with $e \geq 0$ . Because $s \geq 0$ , the student's equation forces $4 x_{1} + 3 x_{2} = 12 - s \leq 12$ , which reverses the original requirement that the left-hand side be at least $12$ . Any point with $4 x_{1} + 3 x_{2} > 12$ is a counterexample; for instance $x_{1} = 3$ , $x_{2} = 1$ gives $15 \geq 12$ , which satisfies the original constraint, but would require $s = - 3 < 0$ in the student's version.

A complete answer does each of these:

slack surplus sign
equivalence statement

Transfer · Construction

A plant blends two feedstocks. Let $t_{1}$ be tonnes of feedstock A and $t_{2}$ the net adjustment applied to a baseline of feedstock B, where $t_{2}$ may be negative if the baseline is reduced. The planner writes:

\begin{aligned} max & 40 t_{1} + 25 t_{2} \\ subject to & t_{1} + t_{2} \leq 60 & (kiln capacity, tonnes) \\ 2 t_{1} + t_{2} \geq 50 & (minimum output, tonnes) \\ t_{1} \geq 8 & (contracted minimum for A) \\ t_{2} unrestricted in sign. \end{aligned}

Convert this program to standard form. Note that $t_{1} \geq 8$ is a lower bound other than zero; handle it so that every variable in your final program is nonnegative. State the relationship between the converted optimum and the planner's optimum.

Write your answer

Write your answer, then compare it with the worked solution.

3 hints available, least help first.

Hint 1: Retrieval cue

Standard form requires $x \geq 0$ , not $x \geq 8$ . What substitution shifts the lower bound to zero?

Hint 2: Concept cue

Introduce $u = t_{1} - 8$ and rewrite every occurrence of $t_{1}$ , including inside both constraints and the objective.

Hint 3: Strategy cue

Shift the bounded variable first, then split the free variable, then convert each inequality. Track the constant the shift introduces into the objective.

Compare with the worked solution

Comparing does not record a result. Judging your own written answer cannot show that you can do this without help.

Substitute $u = t_{1} - 8$ with $u \geq 0$ , so $t_{1} = u + 8$ , and split $t_{2} = t_{2}^{+} - t_{2}^{-}$ with $t_{2}^{+}, t_{2}^{-} \geq 0$ . Objective: maximize $40 (u + 8) + 25 (t_{2}^{+} - t_{2}^{-}) = 40 u + 25 t_{2}^{+} - 25 t_{2}^{-} + 320$ , so minimize $- 40 u - 25 t_{2}^{+} + 25 t_{2}^{-}$ and carry the constant $320$ separately. Capacity: $(u + 8) + t_{2}^{+} - t_{2}^{-} + s_{1} = 60$ , i.e. $u + t_{2}^{+} - t_{2}^{-} + s_{1} = 52$ , $s_{1} \geq 0$ . Output: $2 (u + 8) + t_{2}^{+} - t_{2}^{-} - e_{1} = 50$ , i.e. $2 u + t_{2}^{+} - t_{2}^{-} - e_{1} = 34$ , $e_{1} \geq 0$ . Sign restrictions: $u, t_{2}^{+}, t_{2}^{-}, s_{1}, e_{1} \geq 0$ . If the converted minimization attains value $v$ , the planner's maximum is $- v + 320$ ; $t_{1} = u + 8$ and $t_{2} = t_{2}^{+} - t_{2}^{-}$ .

A complete answer does each of these:

equivalence statement
free variable split
nonnegativity complete
objective direction
slack surplus sign

Practice: Converting a Linear Program to Standard Form

Recognition · Direct application

Classification

Direct application · Interpretation

Classification

Direct application · Construction

Error diagnosis · Explanation

Transfer · Construction

Session complete

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history