Convert LP Problem into Standard Form

Objective Function Conversion

To turn a maximization problem into a minimization problem, just multiply the coefficients of the objective function by -1

Inequality Constraint ⇒ Equation

To turn an inequality constraint ∑i=1naixi≤b\sum_{i=1}^n a_i x_i \le b into an equation:

introduce a new variable ss (slack variable)

∑i=1naixi+s=bs≥0\sum_{i=1}^n a_ix_i + s = b \\ s \ge 0

Equality Constraint ⇒ Inequality

To turn an equality constraint ∑i=1naixi=b\sum_{i=1}^n a_i x_i = b:

∑i=1naixi≤b,∑i=1naixi≥b\sum_{i=1}^n a_i x_i \le b, \sum_{i=1}^n a_i x_i \ge b

Variable with unrestricted sign x∈Rx \in \mathbb{R}:

Introduce

x+,x−≥0x^+, x^- \ge 0

then replace xx with (x+−x−)(x^+ - x^-)

MinMax Problem

min⁡max⁡{y1,y2,…,yn}\min \max\{ y_1, y_2, \dots, y_n \}

Can be rewritten as:

min⁡zs.t.∀i,z≥yi\min z \\ s.t. \forall i, z \ge y_i