# 什么是线性规划

• 一个需要极大化的线性函数，例如：

$$c_1 x_1 + c_2 x_2$$

• 以下形式的问题约束，例如：

$$a_{11} x_1 + a_{12} x_2 \le b_1$$

$$a_{21} x_1 + a_{22} x_2 \le b_2$$

$$a_{31} x_1 + a_{32} x_2 \le b_3$$

• 非负变量，例如：

$$x_1 \ge 0$$

$$x_2 \ge 0$$

# 单纯形法

①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。

②若基本可行解不存在，即约束条件有矛盾，则问题无解。

③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

④按步骤③进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。

⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

# 线性规划解决实际问题

with human lives at stake, an air traffic controller has to schedule the airplanes that are landing at an airport in order to avoid airplane collision. Each airplane $i$ has a time window $[s_i,t_i]$ during which it can safely land. You must compute the exact time of landing for each airplane that respects these time windows. Furthermore, the airplane landings should be stretched out as much as possible so that the minimum time gap between successive landings is as large as possible. For example, if the time window of landing three airplanes are [10:00-11:00], [11:20-11:40], [12:00-12:20], and they land at 10:00, 11:20, 12:20 respectively, then the smallest gap is 60 minutes, which occurs between the last two airplanes. Given n time windows, denoted as [s_1,t_1], [s_2,t_2], · · ·, [s_n,t_n] satisfying s_1 <t_1 < s_2 < t_2 < · · · < s_n < t_n, you are required to give the exact landing time of each airplane, in which the smallest gap between successive landings is maximized.

Please formulate this problem as an LP.


$$s_i\leq x_i \leq t_i$$

$$max(min(x_{i+1}-x_i))$$

\begin{align*} &max~y \\ s.t.~ &s_i\leq x_i \leq t_i i=1,2,3 \cdots n \\ &y \leq x_{i+1}-x_i & i=1,2,3 \cdots n \end{align*}