## 线性规划的基本定理的证明

Now that we have a Phase I algorithm and a variant of the simplex method that is guaranteed to terminate, we can summarize in the following theorem:

Theorem 1.

For an arbitrary linear program in standard form, the following statements are true:
(1) If there is no optimal solution, then the problem is either infeasible or unbounded.
(2) If a feasible solution exists, then a basic feasible solution exists.
(3) If an optimal solution exists, then a basic optimal solution exists.

Proof .

The Phase I algorithm either proves that the problem is infeasible or produces a basic feasible solution. The Phase II algorithm either discovers that the problem is unbounded or finds a basic optimal solution. These statements depend, of course, on applying a variant of the simplex method that does not cycle, which we now know to exist.

## 线性规划的基本定理的几何意义

The set of feasible solutions for a problem in two dimensions is the intersection of a number of halfplanes, i.e., a polygon. In three dimensions, the situation is similar. Consider, for example, the following problem:

maximize $x_{1}+2 x_{2}+3 x_{3}$
subject to $x_{1} \quad+2 x_{3} \leq 3$
\begin{aligned} x_{2}+2 x_{3} & \leq 2 \ x_{1}, x_{2}, x_{3} & \geq 0 . \end{aligned}

The set of points satisfying $x_{1}+2 x_{3}=3$ is a plane. The inequality $x_{1}+2 x_{3} \leq 3$ therefore consists of all points on one side of this plane; that is, it is a halfspace. The same is true for each of the other four inequalities. The feasible set consists of those points in space that satisfy all five inequalities, i.e., those points lying in the intersection of these halfspaces. This set is the polyhedron shown in Figure 3.1. This polyhedron is bordered by five facets, each facet being a portion of one of the planes that was defined by replacing a constraint inequality with an equation. For example, the “front” facet in the figure is a portion of the plane $x_{1}+2 x_{3}=3$. The facets acquire a particularly simple description if we introduce slack variables into the problem:

The set of points satisfying $x_{1}+2 x_{3}=3$ is a plane. The inequality $x_{1}+2 x_{3} \leq 3$ therefore consists of all points on one side of this plane; that is, it is a halfspace. The same is true for each of the other four inequalities. The feasible set consists of those points in space that satisfy all five inequalities, i.e., those points lying in the intersection of these halfspaces. This set is the polyhedron shown in Figure 3.1. This polyhedron is bordered by five facets, each facet being a portion of one of the planes that was defined by replacing a constraint inequality with an equation. For example, the “front” facet in the figure is a portion of the plane $x_{1}+2 x_{3}=3$. The facets acquire a particularly simple description if we introduce slack variables into the problem:
Indeed, each facet corresponds precisely to some variable (either original or slack) vanishing. For instance, the front facet in the figure corresponds to $w_{1}=0$ whereas the “left” facet corresponds to $x_{2}=0$.

The correspondences can be continued. Indeed, each edge of the polyhedron corresponds to a pair of variables vanishing. For example, the edge lying at the interface of the left and the front facets in the figure corresponds to both $w_{1}=0$ and $x_{2}=0$.
Going further yet, each vertex of the polyhedron corresponds to three variables vanishing. For instance, the vertex whose coordinates are $(1,0,1)$ corresponds to $w_{1}=0, x_{2}=0$, and $w_{2}=0$.

Now, let’s think about applying the simplex method to this problem. Every basic feasible solution involves two basic variables and three nonbasic variables. Furthermore, the three nonbasic variables are, by definition, zero in the basic feasible solution. Therefore, for this example, the basic feasible solutions stand in one-to-one correspondence with the vertices of the polyhedron. In fact, applying the simplex method to this problem, one discovers that the sequence of vertices visited by the algorithm is
$$(0,0,0) \quad \longrightarrow \quad(0,0,1) \quad \longrightarrow \quad(1,0,1) \quad \longrightarrow \quad(3,2,0)$$

## 运筹学的三个特点代写

• 优化——运筹学的目的是在给定的条件下达到某一机器或者模型的最佳性能。优化还涉及比较不同选项和缩小潜在最佳选项的范围。
• 模拟—— 这涉及构建模型，以便在应用解决方案刀具体的复杂大规模问题之前之前尝试和测试简单模型的解决方案。
• 概率和统计——这包括使用数学算法和数据挖掘来发现有用的信息和潜在的风险，做出有效的预测并测试可能的解决方法。

BS equation代写