NO - Summary of Chapter 2

An LP (Linear Program) is a special case of MP, where:

• variables are all real numbers ($x\in \mathbb{R}$)
• constraints and objective function are all linear ($a^{t}x\ge b$, $\min c^{t}x$)

---

An LP, can always be brought in its standard form:

$$\begin{array}{rl}& \min \overline{c}{}^t\cdot \overline{x}\\ & \overline{\overline{A}}\cdot \overline{x}=\overline{b}\\ & \overline{x}\ge 0\end{array}$$

Because:

$$\max f(z)=-\min f(-z)$$

Inequalities can be written as equalities using slack variables (for less-or-equal inequalities):

$$\begin{array}{lllc}& ax\le b& \to & \begin{array}{l}ax=(b-s)\\ s\ge 0\end{array}\end{array}$$

or surplus variables (for greater-or-equal inequalities):

$$\begin{array}{lllc}& ax\ge b& \to & \begin{array}{l}ax=(b+t)\\ t\ge 0\end{array}\end{array}$$

---

We can describe an LP geometrically:

---

A problem is defined as:

• feasible and bounded, if a solution exist and is finite
• feasible and unbounded, if a solution exist and is infinite
• unfeasible if a solution does not exist

---

Given a polyhedron we have a vertex is defined as one of its extreme points:

==If the LP admits an optimal solution, then it exist at least one optimal vertex.==