====== 第十四课 ====== 张老师语：请大家在网上做一下课堂笔记，因为我把这个作为平时成绩，用这个来做一次软性的报到。也希望通过这个环节大家练练自己的笔头，对于大家的听课效果也做一次反馈，希望通过这个来让大家课后看一下课件。在网上有几个keynote的链接，点进去就可以，反正名单大家可以看到，如果对这门课比较感兴趣的同学可以看看别的同学写的如果有不正确的地方，或者甚至我的课件有不正确的地方，可以通过这种方式进行一些修改，当然在写课堂笔记的过程当中，如果你们写作上面有困难，大家可以参考前面一年的同学写的内容，因为我2009和2010年已经让同学这样做了，大家要注意到这件事情，这个呢作为我这门课平时成绩中比较重要的一个环节，那我们就回到上课的内容。 那么今天呢继续来讲最优化方法第二次课，因为我最近一段时间人的状态不是很好，今天的内容可能是一种回顾的内容加上一些新的内容，讨论的主题我们仍旧是线性规划的问题，因为线性规划是上节课我们讲的一个这样的想法，这样一个线性的问题加上约束之后呢，其实没那么简单的，需要用一套方法来做。到底是怎么去做呢，那我们就是从一些几何的直观，然后又从几何的直观，来转换成代数可以思考的问题来一步步地去解出来。主要的话我们的参考第一本是《线性规划》，第二本是《最优化理论和方法》，第三本是《数学规划》。因为我们这门课还是需要考试的，大家回去做些复习以及做些练习的话，建议大家去看第三本书，本次的考试很可能从这么书里出，因为这本书比较有用比较标准一点，会比较好出题。那么大家都知道线性规划是整个运筹学里面的一部分的内容也是最早发展起来的一个分支，那么最早呢1947年是G. B. Dantzig提出来的线性规划的单纯形方法，后面我们会看到其实这个方法呢并不是很好，我们会一点点来看他的解法，但不管怎么样那当时能够提出这么一种想法已经是一种非常了不起的事情，能够解决实际中的某些问题，所以在上世纪的六七十年代有好长一段时间很多大型的计算机都是在运行各种各样的线性规划问题，因为它能产生巨大的经济利益，来解决一些最优化的问题，那么上节课我们开始的时候举了一个例子，有一些中端系统和高端系统怎么设计才能达到最大利润，那么这样一个问题实际上就可以转化成，一系列线性约束以及一个目标函数，那么有了这个目标函数就可以构造出一个线性规划的问题，那么所有的这方面的研究就是怎么去把这个问题给解出来，当然在日常生活中我们会遇到千千万万个这样的问题，那么数学家就在研究问题的时候就把它抽象成一般化，就是这样一个形式化的问题，这是一个非常不错的想法，那么这样的线性规划的问题其实是五花八门的，有的时候一个未知数是大于零的或者是小于零的，在这样的情况下构造一个标准的形式是非常重要的，一般会思考一下能不能把这个问题划归，划归到一个比较简单地基本可解问题。 当然在开始做的时候可以做的一件事情是把它给矩阵化，在数学算法里面大家可能最欣赏的一点是，你把前面的这么一个复杂的表示抽象成一个矩阵，矩阵其实是一种比较好的形式，大家一定要尝试着把自己的一个问题写成矩阵形式，一个是他非常简单，第二个是能够引人一些计算的思考。 比方说我们的线性规划问题，就可以用矩阵来形式化成这么一个形式 目标函数我们就写成一个向量C，其实是一个列向量，我们为了简单表示成一个行向量，X是一个未知的函数，通过这样对未知数进行线性组合之后的一个值，那么这个值作为目标函数我们希望他最小，然后底下是一系列的约束条件，约束条件其实是一些不等式，每个不等式里面都是关于未知数，x1到xn的一个线性的表达，就写成了Ax=0这样解下去。那么因此我们引入了一些基本概念。 大家回去想一想什么叫仿射集，什么叫凸集，区别在哪里？用在什么地方？然后极点和极方向到底是怎么回事情，那么从几何的直观上面来讲极点一定是这些边界上面凸出来的地方，因为是个多面体，多面体肯定有些顶点，那些顶点就是极点；而极方向，当有些极点会聚在一起就形成了一个退化的方向，像某个方向发展起来就会形成一个极方向了。 那么这个几何的概念和我们要解的这个问题有什么样的联系呢，其实上节课我们引出过一个定理，这个定理是非常重要的定理，说明了在线性规划问题里面，给了一个基本可行解，意思是这个解是在可行区域D之内的而且是一个基本解。如果说这样一个基本解，跟两件事情等价，一是它一定是在某一个极点上面，这是一个几何性质，这个几何性质和代数性质是一一对应关系，而另外一个代数性质也是一样，即x的正分量所对应的列向量一定是线性无关的。这三件事情联系在一起就能展开线性规划的讨论。 因为我今天搜了一下互联网上面，我发现现在中学教育中都讲了线性规划我觉得简直就不可思议，后来看看书还是挺简单的，区分在哪里？就是没有讲到这一层里面的内容，所以我有的时候发起感叹，可能并不适合把一些相对来说高级的方法放到这么低层次去讲或许这是有害的。 不管怎么样这里面必须考虑到可行区域的极方向因为只有把极方向考虑进去之后我们知道，产生的可行区域有这样基本表示定理，这个基本表示定理利用几何性质：可行区域D里面每一个点就可以用这些极点和极方向通过线性组合的方式表达出来，而且这里面线性表达过程当中有一些限制，要求极点必须在凸集里面，即所谓的lambda是要大于等于0，和等于1的。但有一个例外，因为有退化，退化的时候miu是要大于等于0，如果排除掉极方向，则成为一个凸组合。跟大家平常想象的一个凸的多面体是完全吻合的，所以要用几何直观去看这个问题定理就记住了。 有了这个基本的可行区域表示定理之后我们就可以把原有的线性规划问题求解了。那么这时候就可以证明，若存在有限最优值的情况下，这个最优值一定是在可行区域D的某个极点上达到，因为可以进行以上表达，这个表达一定可以表示成线性组合，线性组合在其他都lambda都等于0，在某一个lambda等于1时达到。 如果存在有限最优值，且如果存在极方向，极方向和cost vector一定是满足以下关系，即cost vector和d做内积时要大于等于0的，意味着价值向量和极方向不能使相反的。 有了这些理论就可以设计方法了，但可能当时设计单纯形方法时候是反过来，后来才把理论给建立起来的，当然我们现在来看这个关系应该是正向的。 有了这个标准化的问题，一定是在上面去遍历极点来找到点。图解法只能构造一个图，这个图里描绘了所有顶点，然后在这个图上面去找最优解，但这个方法当你的A很复杂的或者多包形很复杂的时候设计图解法就变得很困难，一定要想一种利用A本身的性质的一种方法来做更好的搜索，单纯形方法只是其中的一种。 我们回顾一下单纯形方法，单纯形方法从一个基本可行解开始，即一个极点开始首先判断他是不是最优解，这是有条件的，如果不是的话我们就找下一个极点，再判断是不是最优解，要不就是在某一个时刻判断它是无界的，这样是一个相对好一点点的搜索，这个搜索是有方向的。 那么在单纯形方法里面，很有意思的是一般问题的方法都是这样两步，第一步是有一个开始，就如同宇宙大爆炸，需要一个开始，这里也一样，有一个初始解，初始解之后有一个图和判别和迭代的过程，迭代是基本的更新，而判别主要就是意味着要去找什么时候能够找到最优解，即找到一个终止，可以停下来。但单纯形方法的很有意思的特点是自包含，开始的时候先是研究一般性的问题，如果已经有一个初始解的时候怎样判断这个解是不是好的，然后再做下一步的搜索。这个问题如果能解的话，反过来再做一个辅助问题，去帮我特殊的单纯形方法能解的时候才能把初始解给找到。 我们这节课把单纯形方法展开一下来帮助大家复习一下，一个是矩阵代数里面的基本的内容，大家可以去看一下一个迭代方法是怎样设计起来的。 基本解要跟矩阵A有一个密切的关系，因为我们知道A我们需要对他进行分析，一般我们把它进行一个分拆，因为矩阵A一般是个长方形的矩阵，这个矩阵未必是满秩的，肯定是把前面的m个作为列向量，作为一个基矩阵，因为这部分是线性无关的，那么除此之外，构造了一个零矩阵，所以把这两部分叫做B和N，完成拆分。拆完之后b矩阵本身又拆成一些列向量，P1、P2……Pn。它跟对应的自变量的形成关系，为了方便起见，就是前面m个列向量，而非基变量就是m+1到n，对应到一些没有出现在基里面的一些自变量。可以知道自变量的个数要大于矩阵行的个数。 这个时候，可以把矩阵A拆分成B和N，把X也拆分成两部分，一个写成矩阵本身形式，第二个是求和的形式，那么求和形式里因为X本身被拆分成两部分，所以这个时候就可以对两者进行研究。实际上就是一个空间分解的概念，分成可行基对应的部分和不可行的部分，这样可以把X由可行的XB的向量和非基向量XN来表达出来。令非基变量部分等于0，等于零之后比较简单， 则xB=B-1b, x=(B-1b, 0)称为约束方程组的基本解。这个解肯定是可行的 有了这个之后可以来思考一些基本的问题。从一个基本可行解开始，对目标函数也要进行拆分。 讲了这么多，大家应该对线性规划的单纯形方法有了了解，但这看似简单地方法在实际计算起来并不那么容易，大家需要通过对一个例子的分析，来对单纯形方法有感性的认识。所以接下来我们就看一个例子，大家动手算一算。 首先是一个线性规划的标准形式的例子： {{:keynote:线性规划标准形式例题.png}} 首先从中提取出各个变量： {{:keynote:2222.png}} 可以看到A矩阵的第四第五列正好是单位矩阵，可以得到一个基本可行解。此时取X4，X5为基变量，如下所示： {{:keynote:3333.png}} 当把非基变量设为0之后，可以得到基变量的值以及Z： {{:keynote:4444.png}} 初始时Z=-1，接下来看看它是否最优： {{:keynote:5555.png}} 从上可见，通过求检验向量，有两个数大于0，所以肯定不是最优解。 所以需要继续改进。 首先确定换入变量：由于x3对应的检验变量最大，所以选择x3作为换入变量 接着确定换出变量： {{:keynote:6666.png}} 所以选取x4作为换出变量。至此可进行第二轮试验，此时的基变量是x3和x5，非基变量为x1,x2,x4。 但此时由x3和x5对应的A矩阵并非为单位阵，所以需要先进行初等变换： {{:keynote:7777.png}} 这样就可以得到改进的基本可行解以及目标函数值： {{:keynote:8888.png}} 可见，现在的Z是15，比以前的-1增加了不少，但这是不是最优解呢？需要进一步检验： {{:keynote:9999.png}} 可以看到sigma1仍然大于0，所以仍然不是最优，需要第三轮改进。 还是一样，确定换入变量为sigma中最大的对应的变量，为x1，而换出为： {{:keynote:aaaa.png}} 所以进入下一轮，基变量为x1,x3，非基变量为x2,x4,x5。此时需要在刚才基础上，再对A|b的增广矩阵进行一轮初等行变换，目的是把第一列和第三列的矩阵变为单位矩阵： {{:keynote:bbbb.png}} 重复刚才的方法，得出基本可行解和Z值： {{:keynote:cccc.png}} 可见Z又一次增加了，检验其是否最优： {{:keynote:dddd.png}} 其检验向量都小于等于0，所以这就是最优解。Z*=81/5在X=(6/5,0,17/5,0,0)处取得。 --- [[傅唯威]] (ID 11121003) 编写了最优化方法导论与前言 + 单纯形方法例子 ========================================================= \\ \\ ---------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------- ==== 1. 线性规划问题的标准形式==== 线性规划问题（LP）的标准形式为\\ min $c^{T} x$\\ $\qquad s.t. Ax \le b$\\ $\qquad x \ge 0$\\ 1.1 问题定义 X：满足约束条件，称为可行解或可行点。 D：所有可行点的集合,称为可行区域。 LP问题： D = Ø, 无解或不可行 D ≠ Ø，但目标函数在D上无上界：无界 D ≠ Ø，且目标函数有限的最优解：有最优解 1.2 标准化 目标函数的转换 max z → min (-z) 约束条件的转换（引入松弛变量）{{:keynote:约束条件的转换.jpg}} 变量的非负约束 {{:keynote:非负约束.jpg}} --- [[zhaogala@foxmail.com|赵志为]] (ID 11121002) 编写了线性规划问题的标准形式 ====2. LP问题的解==== LP问题的可行解（feasible point）形成的区域称为可行区域（feasible region），记号为D。 2.1 可行区域D 下面讨论可行区域 D={x | Ax = b, x≥0} 的结构 首先讨论集合 K={ x | Ax = b } {{keynote:可行域.jpg}} 2.2 基本可行解定理 “可行解x是基本可行解”的充要条件是“x的正分量所对应的列向量线性无关”。 “可行解x是基本可行解”的充要条件是“x为D的极点”。 可行区域的极方向： 极方向的代数性质： D={x | Ax=b, x≥0}的方向d有k个非零分量，则d为D的极方向的充要条件是d的非零分量对应的列向量组秩为k-1 极方向的几何性质：d为D的极方向的充要条件是d为D的某个半直线界面方向 如果D有极方向，显然D为无界集；反之若D为无界集，则D有方向，且有极方向 1.3 线性规划基本定理 根据LP问题的基本定理一（表示定理），LP问题的任一解可以表示为\\ \\ $x=\sum_{i=1}^{k}\lambda_i x^i + \sum_{j=1}^{l}\mu_j d^j$\\ \\ 其中$x^i$为基本可行解，是x的正分量所对应的列向量，是线性无关的。$d^j$为极方向向量。 基本定理1（表示定理） 设D = {x | Ax=b, x≧0}的所有极点为x1, ..., xk，所有极方向为d1, ..., dl，则x∈D的充要条件是存在一组λi(i = 1, ..., k)和μj (j = 1, ..., l)，使得 {{keynote:lp基本定理1.jpg}} 基本定理2 给定LP问题{{keynote:lp基本定理2.jpg}} （1）若存在有限最优值（即有最优解），则最优值必在可行 区域D的某个极点上达到。 （2）目标函数存在有限最优值的充要条件是对D的所有极方向 dj，均有cdj≥0 LP问题的最优解在极点处取得。求解LP问题的基本方法：单纯型方法的基本原理既是逐个检查可行区域的各个极点，直至找到最优解。 --- //[[zhaogala@zju.edu.cn|赵志为]] 2011/06/14 13:26// --- [[zhaogala@foxmail.com|赵志为]] (ID 11121002) 编写了LP问题的解 ====3. 单纯型方法==== 单纯型方法的步骤为:\\ 1. 找到一个初始解（一个极点）。\\ 2. 检查改点是否为最优解。\\ 3. 若不是最优解，则移动到下一个极点，重复上述步骤。\\ 因此要实现单纯型方法，要解决三个问题，第一个问题是如何找到第一个极点，第二个问题是如何检验一个极点处的解是否是最优解，最后一个问题是如何移动到下一个极点。 ===3.1 找到初始解=== 将约束矩阵$A$拆分成$(\matrix{B&N})$，其中B是一个列向量线性无关的矩阵。 通过解方程： $Ax=b \quad=>\quad \pmatrix{B&N}\pmatrix{x_B\cr x_N}=B x_B+ N x_n = b \quad => \quad x_b=B^{-1}b - B^{-1}Nx_n$ 既得到了一个基本可行解，即可作为初始解。 ===3.2 检测一个解是否为最优=== 计算$\sigma_N=C_N - C_B B^{-1} N$, 若$C_N$的所有分量均小于等于0，则该解为最优解；否则该解不是最优解。 ===3.3 迭代至下一个解=== 将$C_N$中值最大分量的下标作为要N中换入的列向量的下标。\\ 然后计算$B^{-1}b$和$B^{-1}p$, p为换入的变量，将所得两个向量的各分量逐个相除，取值最小的下标作为换出的下标。 确定了换入下标和换出下标后，对增广矩阵$\pmatrix{A b}$做初等变换，将换入下标所在列替换为换出下标所在列，并经初等变换成单位阵。将变换后的b带入上述方程中计算，既得到新的解。 ==== ==== 单纯型方法重复上述过程直到找到最优解。 ===3.4 防止退化和循环=== 在单纯型方法迭代的过程中，可能会发生退化现象或者循环。其解决方法是字典序和Bland规则。 Bland规则是，在选取换入向量的下标时，不取值最大的下标，而是按照下标的顺序，取第一个可以被换入的下标。 因此采用该改进的方法会比原始方法慢。 --- [[xie_8628@hotmail.com|谢越]] (ID 11121005) 编写了LP问题的解和单纯型方法 ====4. 对单纯型方法的改进==== 当LP问题的规模很大时，如何减少存储量和计算时间，就是一个必须加以考虑的问题。在实际中，大多采用修改单纯形法。 **逆矩阵法** 一般单纯形表为 {{:keynote:一般单纯形表.jpg|}} 逆矩阵法对每一张单纯形表，仅存贮下列数据 {{:keynote:修改单纯形表.jpg|}} 该表称为修改单纯形表。 根据这张表和原始数据进行迭代计算，由 确定Xsub（i）为进基变量，再求 ，用最小比确定离基变量 得到新的基 ，最后构造对应于 的修改单纯形表。如果每一次迭代都必须从构造 ，则计算量显然难以令人满意。 定理：对应基B的修改单纯形表的右边添加一列 以 为转轴元选着，就得到了对应于基 修改单纯形表。 --- [[zcy@nit.zju.edu.cn|朱朝艳]] (ID 11024014) 编写了对单纯型法的改进 ====5. 最优性条件和对偶理论==== 对于每一个线性规划P，总存在着另一个线性规划D。如果前者称为原始问题，后者就称为“对偶”问题。对偶问题D是对原问题P从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系。在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 ===5.1 一个对偶的例子=== 某工厂可以生产A、B和C三种产品，每件产品需要的工时和材料，以及总体工时和材料拥有量如下所示： ^ ^产品A ^产品B ^产品C ^拥有量 ^ ^工 时 | 1 | 1 | 1 | 3 | ^材 料 | 1 | 4 | 7 | 9 | ^利 润 | 2 | 3 | 3 | - | 用$y_{1}$，$y_{2}$和$y_{3}$分别表示产品A，B和C的生产数量，那么计算公司所能得到的最大利润问题转化为如下线性规划问题：\\ \max 2y_{1}+3y_{2}+3y_{3} s.t. \cases{y_{1}+y_{2}+y_{3}\le 3\cr y_{1}+4y_{2}+7y_{3}\le 9\cr y_{1}\ge 0,y_{2}\ge 0, y_{3}\ge 0} 假设客户提出要求，购买工厂拥有的工时和材料，为客户加工其他产品。那么工厂给工时和材料制订的最低价格应是多少？\\ * 约束：卖资源获利应不少于生产产品的获利 * 目标：价格应该尽量低，这样才有竞争力 * 约束：价格是非负的 用$x_{1}$和$x_{2}$分别表示工时和材料的出售价格，那么上述问题转化为如下线性规划问题： \min 3x_{1}+9x_{2} s.t. \cases{x_{1}+x_{2} \ge 2\cr x_{1}+4x_{2} \ge 3\cr x_{1}+7x_{2} \ge 3\cr x_{1}\ge 0,x_{2}\ge 0} 对上述两个线性规划问题做如下形式化描述： A=\pmatrix{1& 1\\1& 4\\1& 7} \mathbf{x}=(x_{1},x_{2})^T \mathbf{y}=(y_{1},y_{2},y_{3})^T \mathbf{b}=(2,3,3)^T \mathbf{c}=(3,9)^T 线性规划一表示成 \max\mathbf{b^T}\mathbf{y} s.t. \cases{A^T\mathbf{y}\le \mathbf{c}\cr \mathbf{y}\ge 0} 线性规划二表示成 \min\mathbf{c^T}\mathbf{x} s.t. \cases{A\mathbf{x}\ge \mathbf{b}\cr \mathbf{x}\ge 0} 线性规划一就是线性规划二的对偶线性规划，对线性规划一min的结果就是线性规划二max的结果，可以在matlab中得到验证，两个线性规划的最终结果都是8。 ===5.2 Karush-Kuhn-Tucker条件=== K-T条件非线性规划最优时的必要条件，同时给出了一些要满足的正则条件。我们考虑如下非线性优化问题： \min f(x) \;\; s.t. \; g_{i}(x) \le 0, h_{j}(x)=0, i=1,\ldots,m, j=1,\ldots,l 可以看出，非线性规划问题中的K-T方法是对Lagrange乘子法的推广，因为Lagrange乘子法只允许等式约束。K-T条件原先是以第一发表者Harold W. Kuhn和Albert W. Tucker命名的，后来研究者发现Karush在他的硕士学位论文中已经发现了非K-T条件中的必要条件。 K-T的最优化条件，也就是必要条件，就是得到最优解的$x^*$必须满足如下约束： \nabla f(x^*)+\sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda_i \nabla h_j(x^*)=0 g_i(x^*) \le 0,\;\;for\;\;all\;\;i = 1, \ldots, m h_j(x^*) = 0,\;\;for\;\;all\;\;j = 1, \ldots, l \mu_i \ge 0,\;\;for\;\;all\;\;i = 1, \ldots, m \mu_i g_i(x^*) = 0\;\;for\;\;all\;\;i = 1, \ldots, m ===5.3 线性规划中的K-T条件=== 设A为$m\times n$阶矩阵，$\mathbf{b}\in E^m$，$\mathbf{c}\in E^n$，$\mathbf{x}\in E^n$，则$x^*$为LP问题 \min\mathbf{c^T}\mathbf{x} s.t. \cases{A\mathbf{x}\ge \mathbf{b}\cr \mathbf{x}\ge 0} 的最优解的充要条件是存在$\mathbf{w}\in E^m$，$\mathbf{v}\in E^n$，使得下列K-T条件得到满足 A\mathbf{x^*}\ge \mathbf{b}, \;\; \mathbf{x^*}\ge 0 \mathbf{c-w^T A -v=0, \;\; w\ge 0, \; v\ge 0} \mathbf{w^T (Ax^* -b)=0, \;\; v^T x^* =0} 若将$\mathbf{v}$消去（利用$\mathbf{c-w^T A -v=0}$），可得K-T条件的另一种形式 A\mathbf{x^*}\ge \mathbf{b}, \;\; \mathbf{x^*}\ge 0 \mathbf{w^T A\le c, \;\; w\ge 0} \mathbf{w^T (Ax^* -b)=0, \;\; (A^T w -c)x^* =0} 我们将标准形式的LP问题的K-T条件，只要将$\mathbf{Ax=b}$改写成$\mathbf{\pmatrix{A\\-A} x\ge \pmatrix{b\\-b}}$，可推出相应的K-T条件 \mathbf{Ax=b, \; x\ge 0} \mathbf{c-w^T A -v=0, \;\; w\ge 0, \; v\ge 0} \mathbf{v^T x =0} 或等价的 \mathbf{Ax=b, \; x\ge 0} \mathbf{w^T A\le c} \mathbf{(w^T A-c)x =0} 线性规划中，一个基本可行解$\mathbf{\pmatrix{x_B\\x_N}=\pmatrix{\overline{b}\\0},\; \overline{b} >0}$为最优解的充要条件是检验向量$\zeta \le 0$。同时，我们知道K-T条件是线性规划取得最优解的必要条件，因此其中必有对检验向量的隐式约束。\\ 由$\mathbf{vx=v_B x_B + v_N x_N}$且$\mathbf{x_B >0}$，可知$\mathbf{v_B=0}$ 条件$\mathbf{c-w^T A-v=0}$可以改写为$\mathbf{(c_B,c_N)-w^T(B,N)-(v_B,v_N)=0}$，于是有 \mathbf{\cases{c_B-w^TB=0\cr c_N-w^TN-v_N=0} \Rightarrow \cases{w=c_BB^{-1}\cr v_N=c_N-wN} \Rightarrow v_N=c_N-c_BB^{-1}N} 这就是说，如果一个基本可行解$x$取 \mathbf{v_B=0, \; w=c_BB^{-1}, \; v_N=c_N-wN=c_N-c_BB^{-1}N} K-T条件除了$\mathbf{v \ge 0}$外，其余条件都已满足，所以$\mathbf{v \ge 0 \Leftrightarrow \zeta \le 0}$ \\ ===5.4 对偶理论=== 对偶问题可以看做是原始问题的“行列装置”，\\ 对于标准型LP问题， \mathbf{min\; c^Tx \;\;\;\; s.t. \;\;\; Ax=b, \; x\ge 0} 等价于 \mathbf{min\;c^Tx \;\;\;\; s.t. \;\;\; \pmatrix{A\\-A}x \ge \pmatrix{b\\-b}, \; x\ge 0} 其对偶问题是 \mathbf{\max{\pmatrix{b^T& -b^T}\pmatrix{y_1\\y_2}} \;\;\;\; s.t. \;\;\; \pmatrix{A^T& -A^T}\pmatrix{y_1\\y_2} \le c} 其中$y_1$和$y_2$分别对应与约束项$Ax\ge b$和$-Ax\ge b$的对偶变量组。令$y=y_1-y_2$，可得 \mathbf{\max\; b^Ty \;\;\;\; s.t. \;\;\; A^Ty\le c} 对偶规划生成规则如下所示：\\ {{:keynote:对偶关系对应表.png?300}}\\ 若原LP问题(P)为：$\mathbf{min\; cx \;\;\;\; s.t. \;\;\; Ax\ge b, \; x\ge 0}$\\ 则其对偶问题(D)为:$\mathbf{max\; wb \;\;\;\; s.t. \;\;\; wA\le c, \; w\ge 0}$\\ 对于标准LP问题：$\mathbf{min\; cx \;\;\;\; s.t. \;\;\; Ax=b, \; x\ge 0}$\\ 其对偶问题为：$\mathbf{max\; wb \;\;\;\; s.t. \;\;\; wA\le c}$\\ ===5.5 对偶定理=== 设$\mathbf{x}$和$\mathbf{w}$分别为(P)和(D)的可行解，则有$\mathbf{cx\ge wb}$。\\ 设$\mathbf{x^*}$和$\mathbf{w^*}$分别为(P)和(D)的可行解，则$\mathbf{x^*}$和$\mathbf{w^*}$分别为(P)和(D)的最优解的充要条件是$\mathbf{cx^*=w^*b}$。\\ 推论：若(P)有最优解$\mathbf{x^*}$，则(D)有最优解$\mathbf{w^*}$，且$\mathbf{cx^*=w^*b}$\\ 若(P)无界，则(D)无解，反之亦然。 若原线性规划有最优解$\mathbf{x^*}$，则对偶线性规划有最优解$\mathbf{w^*}$，其K-T条件可以解释成 * 原始可行性：$\mathbf{Ax^*\ge b, \; x^*\ge 0}$ * 对偶可行性：$\mathbf{w^*A\le c, \; w*\ge 0}$ * 互补松弛性：$\mathbf{w^*(Ax^*-b)=0, (w^*A-c)x^*=0}$ 从K-T条件与单纯形方法的最优准则的关系中可以看出，在单纯形方法中，除了K-T条件的$\mathbf{v\ge 0}$外，其余都得到满足。即单纯形法就是保持了原始可行性、互补松弛性、$\mathbf{c-wA-v=0}$得到满足的条件下逐步改善基本可行解，使得对偶可行性中的$\mathbf{v=c-wA\ge 0}$得到满足。 启发：也可以在保证对偶可行性和互补松弛性满足的条件下，改善解使得原始可行性得到满足。 ===5.6 对偶单纯形法=== \mathbf{(P)\min cx \;\;\;\; s.t. \;\;\; Ax=b, \;\; x\ge 0} \mathbf{(D)\max wb \;\;\;\; s.t. \;\;\; wA\le c} D的基本可行解：设$\mathbf{A=(B,N)}$，其中$\mathbf{B}$为满秩方阵，则$\mathbf{wB=c_B}$的解$\mathbf{\overline{w}=c_BB^{-1}}$为(D)的基本解。若$\mathbf{\overline{w}N\le c_N}$，则称$\mathbf{\overline{w}}$为(D)的基本可行解。 P的正则解\\ 若原问题(P)的一个基本解$\mathbf{x=\pmatrix{B^{-1}b\\0}}$对应的检验向量$\mathbf{\zeta=(0,c_BB^{-1}N-c_N)\le0}$，则称$x$为问题(P)的正则解。\\ 此时的基$B$称为正则基。 D的基本可行解和P的正则解是一一对应的 同单纯形法一样，求解对偶规划(D)从(D)的一个基本可行解迭代到另一个基本可行解，使得目标函数值增加。等价地，求解原规划(P)从一个正则解开始，迭代到另一个正则解， 使目标函数$\mathbf{z=wb=c_BB^{-1}b=cx}$增加，直到$\mathbf{B^{-1}b}\ge0$，即正则解满足原始可行性时，也就找到最优解。这种方法称为对偶单纯性法。 算法具体步骤 - 找一个正则基$\mathbf{B}$，建立单纯形表 - 若$\mathbf{\overline{b}=B^{-1}b\ge0}$，停止，已找到原问题最优解；否则令$\mathbf{\overline{b}_r=\min\{\overline{b}_i|i=1,\ldots,m\}}$ - 若$\mathbf{\overline{a}^r\ge0}$停止，原问题无解；否则令$\mathbf{\frac{\zeta_k}{\overline{a}_{rk}}=\min\{\frac{\zeta_j}{\overline{a}_{rj}}|a_{rj}<0\}}$ - 以$\mathbf{\overline{a}_{rk}}$为转轴元旋转，返回2。 ===5.7 原始－对偶单纯形法=== 同时对对偶问题和第一阶段地辅助问题求解。从对偶问题的任意可行解开始，同时在迭代过程中保持对偶可行性和互补松弛性以及$\mathbf{x\ge0}$的情况下,通过剔除人工变量使$\mathbf{Ax=b}$成立。\\ 在(P)中引入人工变量后，得到辅助问题 \mathbf{\min\; g=1x_a \;\;\;\; s.t. \;\;\; Ax+x_a=b, \; b\ge0, \; x,x_a\ge0} 若已知(D)的一个可行解$\mathbf{\overline{w}}$，为了保持互补松弛性（$\mathbf{x(\overline{w}A-c)=0}$），令$\mathbf{x_j=0}$（当$\mathbf{\overline{w}a_j\not=c_j}$），于是辅助问题为 \mathbf{(P')\min \; g=1x_a} \mathbf{s.t. \cases{Ax+x_a=b\cr x_j=0, \; j\notin Q\cr x_j\ge0, \; j\in Q\cr x_a\ge0}} 其中$Q=\{j|\overline(w)a_j=c_j, j=1,\ldots,n\}$。问题(P')称为对应于$\mathbf{\overline(w)}$的限定问题。\\ 求解问题(P')，得到最优解$\mathbf{\pmatrix{x^*\\x_a^*}}$，则它是(P)的辅助问题的基本可行解。\\ * 若$\mathbf{x_a^*}=0$，则$\mathbf{x^*}$为问题(P)的最优解，因为$\mathbf{x^*}$和$\mathbf{\overline{w}}$分别是(P)和(D)的可行解，且满足互补松弛性。 * 若$\mathbf{x_a^*}\not=0$，找到(D)的另一个基本可行解$\mathbf{\hat{w}}$，使得(D)目标函数值有所增加，同时对应于$\mathbf{\hat{w}}$的限定问题的最优值将较对应于$\mathbf{\overline{w}}$的限定问题的最优值有所减少（等价于剔除人工变量）。 考虑(P')的对偶问题(D') \mathbf{(D')\max \; vb} \mathbf{s.t. \cases{va_j\le0, \; j\in Q\cr v\le1}} 令$\mathbf{v^*}$为其最优解，若对于所有的$\mathbf{j=1,\ldots,n}$，都要$\mathbf{v^*a_j\le0}$，则说明$\mathbf{v^*}$还是辅助问题的对偶问题的最优解，于是$\mathbf{\pmatrix{x^*\\x_a^*}}$就是辅助问题的最优解。如果$\mathbf{x_a^*\not=0}$，原问题(P)无解。\\ 构造$\mathbf{\hat{w}=\overline{w}+\theta v^*}$，其中 \mathbf{\theta =min\{-\frac{\overline{w}a_j-c_j}{v^*a_j}|v^*a_j>0,j=1,\ldots,n\}} 可以证明$\mathbf{\hat{w}}$满足要求，同时$\mathbf{\pmatrix{x^*\\x_a^*}}$还是对应于$\mathbf{\hat{w}}$的限定问题的一个基本可行解，因此可以使用它来作为初值来求解对应于$\mathbf{\hat{w}}$的限定问题。如此循环。。。 --- [[huangxuezhen@cad.zju.edu.cn|黄学真]] (ID 11121004) 编写了最优性条件和对偶理论 ----------------------------------------------------------------------------------------------------------------------------------------------