Flashcards
Answer
Standard Form
Standard form is the clean algebraic form used to study basic solutions, basic feasible solutions, reduced costs, and the simplex method.
In this course, the standard form of a linear program is:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]See
-
Converting Max to Min
- How to rewrite maximization problems as minimization problems.
-
Slack Variables
- How to convert $\le$ constraints into equalities.
-
Surplus Variables
- How to convert $\ge$ constraints into equalities.
-
Free Variables
- How to replace unrestricted variables by nonnegative variables.
-
Sign-Restricted Variables
- How to handle variables constrained by $x_j\le 0$ or other sign rules.
-
Equality and Inequality Constraints
- How different constraint types are converted.
-
Canonical Form
- How a standard-form LP is written relative to a chosen basis.
Standard Form Definition
A linear program is in standard form if it is written as:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]where:
\[A\in\mathbb{R}^{m\times n}\] \[b\in\mathbb{R}^m\] \[c,x\in\mathbb{R}^n\]Meaning of Each Part
| Part | Meaning |
|---|---|
| $x$ | decision vector |
| $c$ | objective coefficient vector |
| $A$ | constraint matrix |
| $b$ | right-hand side vector |
| $Ax=b$ | equality constraints |
| $x\ge 0$ | nonnegativity constraints |
Why Standard Form Matters
Standard form is important because simplex theory is built on it.
In standard form, we can define:
- columns of $A$
- basis matrices
- basic solutions
- basic feasible solutions
- reduced costs
- optimality conditions
General LP to Standard Form
A general LP may contain:
- maximization instead of minimization
- $\le$ constraints
- $\ge$ constraints
- equality constraints
- nonnegative variables
- nonpositive variables
- free variables
Each can be converted into standard form.
Conversion Rules
| Original feature | Standard-form conversion |
|---|---|
| $\max f(x)$ | minimize $-f(x)$ |
| $a^Tx\le b$ | add slack variable $s\ge 0$ |
| $a^Tx\ge b$ | subtract surplus variable $s\ge 0$ |
| $x_j\le 0$ | replace $x_j=-y_j$, $y_j\ge 0$ |
| $x_j$ free | replace $x_j=x_j^+-x_j^-$ |
| equality constraint | keep as equality |
Example
Convert:
\[\max 3x_1+x_2\]subject to:
\[6x_1+2x_2\le 12\] \[x_2\le 4\] \[x_1,x_2\ge 0\]First convert max to min:
\[\min -3x_1-x_2\]Add slack variables:
\[6x_1+2x_2+s_1=12\] \[x_2+s_2=4\]with:
\[x_1,x_2,s_1,s_2\ge 0\]So the standard form is:
\[\min -3x_1-x_2\]subject to:
\[6x_1+2x_2+s_1=12\] \[x_2+s_2=4\] \[x_1,x_2,s_1,s_2\ge 0\]Matrix Form of the Example
Let:
\[\tilde{x}=\begin{bmatrix}x_1\\x_2\\s_1\\s_2\end{bmatrix}\]Then:
\[A=\begin{bmatrix} 6&2&1&0\\ 0&1&0&1 \end{bmatrix}\] \[b=\begin{bmatrix}12\\4\end{bmatrix}\] \[c=\begin{bmatrix}-3\\-1\\0\\0\end{bmatrix}\]and the problem is:
\[\min c^T\tilde{x}\]subject to:
\[A\tilde{x}=b\] \[\tilde{x}\ge 0\]Standard Form Does Not Change the Problem
The converted problem is equivalent to the original problem.
This means:
- feasible solutions correspond to feasible solutions
- objective values correspond after the sign change if needed
- solving the standard-form problem solves the original problem
Checklist
You understand standard form if you can:
- state $\min c^Tx$ subject to $Ax=b$, $x\ge 0$
- convert max to min
- add slack variables for $\le$
- subtract surplus variables for $\ge$
- handle free and sign-restricted variables
- write the final matrix $A$, $b$, and $c$
See Also
- Matrix Form of LP Problems
- Basic Solutions
- Basic Feasible Solutions
- Reduced Costs
-
Simplex Method
Added exam practice
- Standard Form Worked Examples
- Standard Form Common Exam Conversions
- Standard Form With Equality Greater Less Constraints
- Standard Form Drill Set
Exam checkpoint
For standard-form questions, use the course convention $\min c^Tx$ subject to $Ax=b$, $x\ge0$. Convert max objectives, add slack to $\le$, subtract surplus from $\ge$, and split free variables.