Standard Form

286. Standard Form

\begin{aligned} min & 𝑐^{𝑇} 𝑥 \\ 𝑠 . 𝑡 . & 𝐴 𝑥 = 𝑏 \\ 𝑥 \geq 0 \end{aligned}

Example

\begin{aligned} max 4 & 𝑥_{1} & + & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . 2 & 𝑥_{1} & + & 𝑥_{2} & \leq & 8 \\ 𝑥_{1} & + & 2 & 𝑥_{2} & \leq & 6 \end{aligned}

Step 1. Convert inequality ( $\leq$ ) to equality ( $=$ )

Add slack variables $𝑠_{1}, 𝑠_{2} \geq 0$

\begin{aligned} max 4 & 𝑥_{1} & + & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . 2 & 𝑥_{1} & + & 𝑥_{2} & + & 𝑠_{1} & = & 8 \\ 𝑥_{1} & + & 2 & 𝑥_{2} & + & 𝑠_{2} & = & 6 \end{aligned}

Step 2. Convert Max to Min

Multiply the objective by −1:

\begin{aligned} min & - 4 & 𝑥_{1} & - & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . & 2 & 𝑥_{1} & + & 𝑥_{2} & + & 𝑠_{1} & = & 8 \\ 𝑥_{1} & + & 2 & 𝑥_{2} & + & 𝑠_{2} & = & 6 \end{aligned}

Example

\begin{aligned} min 4 & 𝑥_{1} & + & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . 2 & 𝑥_{1} & + & 3 & 𝑥_{2} & \geq & 6 \\ 𝑥_{1} & + & 4 & 𝑥_{2} & \geq & 8 \end{aligned}

Step 1. Convert inequality ( $\geq$ ) to equality ( $=$ )

Add slack variables $𝑠_{1}, 𝑠_{2} \geq 0$

\begin{aligned} min 4 & 𝑥_{1} & + & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . 2 & 𝑥_{1} & + & 3 & 𝑥_{2} & - & 𝑠_{1} & = & 6 \\ 𝑥_{1} & + & 4 & 𝑥_{2} & - & 𝑠_{2} & = & 8 \end{aligned}