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.
댓글