Introduction to linear programming

15.1 Brief History of Linear Programming

---

생략

 

15.2 Simple Examples of Linear Programs 

---

Formally, a linear program is an optimization problem of the form

$$\begin{array}{cl} \operatorname{maximize} & \boldsymbol{c}^{\top} \boldsymbol{x} \\ \text { subject to } & \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \\ & \boldsymbol{x} \geq \mathbf{0} \end{array}$$

where $\boldsymbol{c} \in \mathbb{R}^{n}, \boldsymbol{b} \in \mathbb{R}^{m},$ and $\boldsymbol{A} \in \mathbb{R}^{m \times n}$. The vector inequality $x \geq 0$ means that each component of $x$ is nonnegative. 

 이 번 Section은 LP의 중요성과 다양한 응용 문제를 풀어보는 간단한 예제를 다룬다.

the problem can be written in the compact form 

$$\begin{array}{cl} \operatorname{maximize} & c^{\top} x \\ \text { subject to } & A x \leq b \\ & x \geq 0 \end{array}$$

where

$$\begin{array}{l} \boldsymbol{c}^{\top}=[6,4,7,5] \\ \boldsymbol{A}=\left[\begin{array}{llll} 1 & 2 & 1 & 2 \\ 6 & 5 & 3 & 2 \\ 3 & 4 & 9 & 12 \end{array}\right], \quad \boldsymbol{b}=\left[\begin{array}{l} 20 \\ 100 \\ 75 \end{array}\right] \end{array}$$

 

15.3 Two-Dimensional Linear Programs 

---

Many fundamental concepts of linear programming are easily illustrated in two-dimensional space. Therefore, we consider linear problems in R2 before discussing general linear programming problems. Consider the following linear program

$$\begin{array}{cl} \operatorname{maximize} & \boldsymbol{c}^{\top} \boldsymbol{x} \\ \text { subject to } & \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \\ & \boldsymbol{x} \geq \mathbf{0} \end{array}$$

where $\boldsymbol{x}=\left[x_{1}, x_{2}\right]^{\top}$ and

$$\begin{aligned} \boldsymbol{c}^{\top} &=[1,5] \\ \boldsymbol{A} &=\left[\begin{array}{ll} 5 & 6 \\ 3 & 2 \end{array}\right], \quad \boldsymbol{b}=\left[\begin{array}{l} 30 \\ 12 \end{array}\right] \end{aligned}$$

 

15.4 Convex Polyhedra and Linear Programming 

---

The goal of linear programming is to minimize (or maximize) a linear objective function 

$$\boldsymbol{c}^{\top} \boldsymbol{x}=c_{1} x_{1}+c_{2} x_{2}+\cdots+c_{n} x_{n}$$

subject to constraints that are represented by linear equalities and/or inequalities.

생략

 

15.5 Standard Form Linear Programs

---

We refer to a linear program of the form 

$$\begin{array}{cl} 
\operatorname{maximize} & \boldsymbol{c}^{\top} \boldsymbol{x} \\ 
\text { subject to } & \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \\ 
& \boldsymbol{x} \geq \mathbf{0} 
\end{array}$$

as a linear program in standard form. Here A is an $m \times n$ matrix composed of real entries, $m<n, \operatorname{rank} A=m$.  Without loss of generality, we assume that $b \geq 0$. If a component of $b$ is negative, say the ith component, we multiply the ith constraint by —1 to obtain a positive right-hand side.