第2章 线性规划§2.1 线性规划的基本定理2.1.1 线性规划发展简史· 19世纪末，康特罗维奇和F. L. Hitchcock等研究运输问题，但其工作长期未被人们所知由于战争的需要，T. C. Koopmans重新独立研究了运输问题· 1947年，G. B. Dantzig发表单纯形法，应用于与国防有关的问题该法实用而有效单纯形法被认为是20世纪10大算法之一（其中还有快速Fourier变换算法等） · 但1972年，V. Kell和G. Minty给出病态例子，用单纯形法求解可能要检查遍所有的顶点才能得到最优解，所用时间为. 故单纯形法为指数时间算法· 1979年，前苏联数学家提出了一种求解LP的椭球算法，计算复杂性为(为输入长度)该算法在理论上很重要，但计算效率远不如单纯形法有效 · 能否找到有效的多项式时间算法？在此背景下，1984年，在美国贝尔实验室工作的印度数学家Karmarkar给出了一个求解线性规划的新的多项式时间算法，计算复杂性为通过例题试算，收敛到较好效果，人们希望借助这种算法解决一些领域中的大规模问题的计算· 对于现实生活中的大多数实际问题，单纯形法仍然有效. 基于单纯形法可以方便地讨论线性规划的对偶理论，而基于对偶理论可以设计求解LP的对偶单纯形法和原始－对偶算法及其它算法，因此单纯形法是目前应用最广泛的算法之一。
· LP之所以重要有以下方面的原因： ■ 理论算法发展较完善 ■ 现实生活中许多问题可用LP近似建模 ■ 在非线性规划的求解中，将问题局部线性化处理2.1.2 标准形式与基本定理 LP标准形： s.t. LP向量形式： s.t. 其中.约定：为决策变量，为费用（价格）系数，为目标函数，为技术系数，为右端项. 各种形式的线性规划都可以化为标准形：(i) ®(ii) ®(引入松弛变量)(iii) ®(引入剩余变量) (iv) 无非负限制，令 (v) ，令(平移变换) 例 s.t. 令标准形： s.t. ，图解法例 s.t. 有唯一最优解例 s.t. 有无穷个最优解例 s.t. 此问题无上界，从而无有限最优解例 s.t. 问题无可行解，从而无最优解。
由以上几个例子可以看出以下几个结论： (i) 可行域为空集，原问题无可行解；(不可行，无最优解) (ii) 目标函数可行域上无界；(可行，无有限最优解) (iii) 有唯一最优解；(有最优解，可在顶点达到) (iv) 有无穷多最优解；(有最优解，可在顶点达到) 猜想：求解一个LP问题可能有三种情况：不可行、无界和有最优解；线性规划若有最优解，则一定可以在可行域的某个“顶点”达到线性规划的基本定理设可行域的极点为,极方向为.根据多面集的表示定理,任何可行点可表示为：将x代入LP标准型, 得到以为变量的等价LP:s.t. (i) 可任意大, 因此若对某个j有,则随的增大无限减小, 目标函数值趋向. 对于这种情形, 称该问题是无界的, 或不存在有限最优解.(ii) 如果对于所有的j有,这时为极小化目标函数,令, LP简化为s.t. , 令, 显然当及时, 目标函数取极小值. 此时必有因此极点是原LP问题的最优解.定理(基于标准型的线性规划基本定理): 设线性规划问题 s.t. , 的可行域非空,则有下列结论:(1) LP存在有限最优解的充要条件是所有.(2) 若LP存在有限最优解, 则目标函数的最优值可在某个极点上达到. 2.1.3 极点的代数特征设，，其中为阶可逆矩阵.记，则，得.令，得称其为(LP)的基本解，对应的矩阵称为基矩阵，简称基。
的各分量称为基变量，的各分量称为非基变量注：基本解的个数最多为：个.例 引入松弛变量，得 则(最多有个基，而线性相关，故共有5个基)(i)令，则得 (ii)令，则；(iii) 令，则；(iv) 令，则；(v) 令，则； 若，称其为(LP)的基本可行解，对应的矩阵称为可行基矩阵，简称可行基 5个基本解，除外，都是基本可行解称为与基本可行解(与基)对应的单纯形乘子对于LP，可行域的基本可行解与极点是等价的 引理：设为的极点的充要条件是中与的所有正分量对应的列线性无关 定理:在(LP)的标准形中，若，则的极点集与(LP)的基本可行解集相同可行域的极点与基本可行解是一一对应的: (LP)的最优解可在某极点达到Û(LP)的最优解可在某基本可行解处达到 若，则有极点Û若，则有基本可行解．§2.2 单纯形算法2.2.1 基本原理定理: 若(LP)的可行域非空，即，且，则 (i) (LP)有基本可行解； (ii) (LP)存在有限最优解的充分必要条件是(LP)的价格系数与可行集的所有极方向的夹角小于90度，即对的所有极方向成立； (iii) 若(LP)有有限最优解，则其最优值可在某个基本可行解上达到。
线性规划解的代数特征的一个重要应用就是单纯形算法的提出 单纯形法的基本思路：用迭代法从一个基本可行解(极点)转换到另一个基本可行解(另一极点)，每一步转换只将一个非基变量(指一个分量)变为基变量，称为进基，同时将一个基变量变为非基变量，称为离基 进基变量和出基变量的确定原则：应使新的基本解可行，同时目标函数值有一定的下降 实现该思路的算法要解决以下问题： (1) 选取初始基本可行解(极点)； (2) 判断当前基本可行解是否是最优解，或判断问题无界； (3) 确定进基和离基变量 定理(判定定理)：设为(LP)的一基本可行解，对应基为1) (最优判别)若，即则为(LP)的最优基本可行解； (2) (无界判别)若存在使，且，则(LP)无有限最优解，即极小化问题无下界2.2.2 算法步骤与单纯形表极小化问题的计算步骤: 首先给定一个初始基本可行解,设初始基为B.(l)计算，令，计算目标函数值.(2)求单纯形乘子．对于所有非基变量，计算判别数．令若, 则对于所有非基变量，对应基变量的判别数总是零，停止计算，现行基本可行解是最优解．否则，进行下一步．(3)计算，若，则停止计算，问题不存在有限最优解．否则，进行步骤(4). (4)确定下标r，使.为离基变址，为进基变量. 用替换，得到新的基矩阵B，返回步骤(1).用单纯形方法求解LP问题的过程，实际上就是解线性方程组．只是在每次迭代中，要按一定规则选择自由未知量，以便能够得到改进的基本可行解．这个求解过程可以通过变换单纯形表来实现．线性规划标准型等价于如下形式(2)式两端左乘，得到即把基变量的系数矩阵化为单位矩阵.再用左乘（3）式两端，然后加到（1）式，得到等价问题：单纯形表:右端010上半部包含m个行，其中有个列,对应非基变量．是m维列向量.令非基变量, 则基变量．下半部只有1行, 各分量是对应非基变量的判别数.是在现行基本可行解处的目标函数值．¼¼¼¼1¼0¼0¼¼¼0¼1¼0¼¼¼0¼0¼1¼¼¼0¼0¼0¼¼¼例: 求解LP问题s.t. 引入松弛变量, 转化为标准型:s.t. 选择初始的可行基指标集, 依次得到的可行基指标集为, .原问题的最优解为, 目标函数最大值为11.2.2.3 启动机制1.两阶段法标准形式的线性规划问题: (5)若A中含有m阶单位矩阵，则初始基本可行解立即得到．若A中不包含m阶单位矩阵,就需要用某种方法求出一个基本可行解．两阶段法的第一阶段提供了求初始基本可行解的方法． 为使约束方程的系数矩阵中含有m阶单位矩阵，引入非负人工变量: (6)即 (7)显然，是（7）式的一个基本可行解.若从（7）式已知的基本可行解出发，能求出一个使的基本可行解，就可得到（5）式的一个基本可行解．两阶段法的第一阶段，是用单纯形方法消去人工变量，即把人工变量都变换成非基变量，求出原来问题的一个基本可行解．消去人工变量的一种方法是解下列第一阶段问题： (8)设线性规划（8)的最优基本可行解是，必有三种情形之一：(1) ，这时线性规划（5）无可行解．因为如果（5）存在可行解，则是（8）的可行解．在此点，问题（8）目标函数值而是目标函数的最优值，矛盾．(2) 且的分量都是非基变量．这时m个基变量都是原来的变量，又知是（8）的基本可行解，因此是（5）的一个基本可行解.(3) 且的某些分量是基变量．这时，可用主元消去法，把原来变量中的某些非基变量引进基，替换出基变量中的人工变量，再开始两阶段法的第二阶段．两阶段法的第二阶段，就是从得到的基本可行解出发，用单纯形方法求线性规划(5)的最优解．例: 用两阶段法求下列问题的最优解： (9)先引进松弛变量把问题化成标准形式,为使标准形式中约束方程的系数矩阵包含3阶单位矩阵，还要引进人工变量．先解一阶段问题：11-1001021-10-100111000100320-1-1000302-1101-111-10-10011010110-120。