Flashcards

1 / 1 0 learned
Loading…

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

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

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.