运筹学教程第二节 图解法2.1图解法步骤图解法就是用几何作图的方法分析并求出 其最优解的过程求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可 行域），然后结合目标函数的要求从可行 域中找出最优解运筹学教程图解法举例图解法举例 实施图解法，以求出最优最优生产计划（最优解最优解） maxZ=2x1+3x2s.t.运筹学教程由于线性规划模型中只有两个决策变量，因此 只需建立平面直角系就可以进行图解了第一步：建立平面直角坐标系，标出坐标原点, 坐标轴的指向和单位长度 用x1轴表示产品A的产量，用x2轴表示产品B的产量第二步：对约束条件加以图解 第三步：画出目标函数等值线，结合目标函数 的要求求出最优解-----最优生产方案运筹学教程约束条件的图解:每一个约束不等式在平面直角坐标系中都 代表一个半平面，只要先画出该半平面的边先画出该半平面的边 界界，然后确定是哪个半平面确定是哪个半平面 第一个约束条件1/3 x1+1/3 x2 1运筹学教程令1/3 x1+1/3 x2 ＝1， 即直线AB1/3 x1+1/3 x2 1 所代表的半平面的边界:运筹学教程两个约束条件两个约束条件 及非负条件及非负条件x x1 1,x ,x2 2 0 0所代表的公共部分所代表的公共部分 －－图中阴影区，就是满足所有约束条件和非－－图中阴影区，就是满足所有约束条件和非 负条件的点的集合，即可行域。
在这个区域中负条件的点的集合，即可行域在这个区域中 的每一个点都对应着一个可行的生产方案的每一个点都对应着一个可行的生产方案 第二个约束条件的边界第二个约束条件的边界 －－－－直线直线CD: CD: 1/3x 1/3x1 1+4/3 x+4/3 x2 2=3 =35– 4– l1 3B 2 D （1/3）x1+(4/3)x2=3 l2 1– 0 1〡 2〡 3A 4〡 5〡 6〡 7〡 8〡 9〡C (1/3)x1+(1/3)x2=1 运筹学教程令 Z=2x1+3x2=c,其中c c为任选的一个常数为任选的一个常数，在图中画出直线 2x1+3x2=c, 这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达 到c这样的直线有无数条，而且相互平行，称这样的直线为目标函数等值线目标函数等值线只只 要要画出两条目标函数等值线两条目标函数等值线，比如令c＝0和c=6，就能看出目标函数值递增的方向目标函数值递增的方向，用箭头标出箭头标出这个方向。
图中两条虚线 l1和l2就分别代表 目标函数等值线 2x1+3x2=0 和 2x1+3x2=6,箭头表示使两种产品的总利润递增的方向沿着箭头沿着箭头的方向平移平移目标函数等值线，使其达到达到 可行域中的最远点可行域中的最远点E E, E点就是要求的最优点，它对应 的相应坐标 x1=1,x2=2 就是最有利的产品组合，即生 产A产品等于1，B产品等于2能使两种产品的总利润 达到最大值 max Z=21+32=8，x x1 1=1,x=1,x2 2=2=2就是线性规 划模型的最优解最优解，ZmaxZmax=8=8就是相应的目标函数最优就是相应的目标函数最优 值值 运筹学教程尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精 确地看出一个解答是比较困难的所以，通 常总是用解联立方程的方法求出最优解的精 确值比如E点对应的坐标值我们可以通过求 解下面的联立方程，即求直线AB和CD的交点来求得直线AB: 1/3x1+1/3x2=1直线CD: 1/3x1+4/3x2=3运筹学教程0 1 2 3 4 5 6 7 8 9 x15 4 3 2 1x2（3，0）C=6（9，0）（0，9/4）E E（（1 1，，2 2））C=0（0，3）运筹学教程设三种产品的产量分别是设三种产品的产量分别是x x1 1、、x x2 2、、x x3 3吨，由吨，由 于有三个决策变量，用图解法求解下面的线性规于有三个决策变量，用图解法求解下面的线性规 划时，必须首先建立空间直角坐标系。
划时，必须首先建立空间直角坐标系变量超过变量超过2 2个情况个情况运筹学教程0x1x25x2=156x1+2x2=24x1+x2=5x2=-2x1+Z最优解的确定:可行域使目标函数达到 最优的点,目标函数的Z值逐渐增大， 一直移动到目标函数的直线与约束条 件包围成的凸多边形相切时为止，切 点就是最优解x1,x2)=(3.5,1.5),z=8.5运筹学教程1 1、无穷多个最优解：将目标函数、无穷多个最优解：将目标函数 max Z=xmax Z=x1+x+x22 2、、无界解：可行域可伸展到无穷，导致目标函数增大到无界解：可行域可伸展到无穷，导致目标函数增大到 无限产生无界解的原因是由于在建立实际问题的数学无限产生无界解的原因是由于在建立实际问题的数学 模型中遗漏某些必要的资源约束模型中遗漏某些必要的资源约束3 3、无解：不存在满足约束条件的可行域无解：不存在满足约束条件的可行域2.2线性规划求解的各种可能的结局运筹学教程2.2.1无穷多个最优解无穷多个最优解该线性规划的可行域为上图中四边形 OAED（即阴影区），虚线为目标函数等值线 ，箭头为目标函数值递增的方向。
沿着箭头 的方向平移目标函数等值线，发现平移的最 终结果是目标函数等值线将与可行域的一条 边界－－线段AE重合，这个结果表明，该线 性规划有无穷多个最优解无穷多个最优解－－线段AE上的 所有点都是最优点，它们都使目标函数取得 相同的最大值Zmax=3 运筹学教程2.2.22.2.2无界解无界解X1X2运筹学教程本例中的可行域是一个无界区域，如图中阴影区所示虚线为目函数等值线，沿着箭头所指的方向平移可以使目标函数值无限制地增大，因此找不到最优解如果实际问题是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理此时应重新 检查和修改模型，否则就没有实际意义x1x2运筹学教程2.2.32.2.3无解无解x1X2运筹学教程2.32.3图解法得到的启示图解法得到的启示 1、求解线性规划问题时，解的情况：唯一最优解、无穷多个最优解、无界解，无解2、若线性规划的可行域存在，则可行域一定是凸多边形（凸集）3、若线性规划的最优解存在，则最优解（或最优解之一）一定是可行域凸集的一个顶点4、解题思路：先找任一个顶点，计算目标函数；比较周围顶点的目标函数的值是否比此值大，一直找到使目标函数达到最大的顶点。
运筹学教程图解法小结 使用条件： 仅有两个至多不超过三个决策变量的线性规划 基本步骤： 第一步－－建立平面直角坐标系； 第二步－－根据约束条件和非负条件画出可行域 第三步－－作出目标函数等值线（至少两条），结合目标 函数优化要求，平移目标函数等值线求出最优解 图解法的优缺点： 简单、直观但有局限性 运筹学教程第三节 单纯形法原理1.3.1线性规划问题解概念：可行解：满足所有约束条件的解 最优解：使目标函数达到最大值的可行解运筹学教程基:设A 为约束方程组的m×n阶系数矩阵(n>m),R(A)=m,B是矩阵A中的一个m×m阶满秩子 矩阵,称B是线性规划问题的一个基,设列向量Pj(j=1,2,…m) 为基向量,Pj 所对应的变量xj 基变量,其余变量为非基变量.秩:设在矩阵A中存在一个不等于零的r阶子式D,且所有的r+1阶子式全等于零,那么D为A的最高阶非零子式,数r称为A的秩.P1 P2…Pj…Pm运筹学教程基解:在约束方程组中,令所有的非基变量,有因为有 根据克莱姆法则,有m个约束方程可解出m 个变量的唯一解, 将此解加上非基变量取0的值有此解为线性规划问题的基解.基解的个数不会超过基可行解：基解当中的可行解。
可行基：对应于基可行解的基称为可行基．运筹学教程例题 找出全部基解，指出其中的基可行解，确定 最优解．P1 P2 P3 P4 P5B1=(P3,P4,P5)B2=(P2,P3,P4)B3=(P1,P4,P5)B4=(P2,P3,P5)B5=(P1,P3,P5)B6=(P1,P2,P5)B7=(P1,P2,P4)B8=(P1,P2,P3)B9=(P3,P4,P1)B10=(P2,P4,P5)运筹学教程基x1x2x3x4x5Z是否基可行解P3,P4,P50051045P2,P3,P40452017P1,P4,P55005410P2,P3,P50550-120P1,P3,P5100-50415P1,P2,P552.5001.517.5P1,P2,P4540-3022P1,P2,P32430019运筹学教程基的概念的理解 对于线性规划的约束条件 AX=b X≥0 设B是A矩阵中的一个非奇异的m×m子矩阵，则称B为线性 规划的一个基 设B是线性规划的一个基，则A可以表示为 A=[ B, N ] X也可相应地分成运筹学教程其中XB为m×1向量，称为基变量，其分量与基B的列向量对 应；XN为(n-m)×1向量，称为非基变量，其分量与非基矩 阵N的列对应。
这时约束等式AX=b可表示为或 BXB+NXN=b 若XN取确定的值，则XB有唯一的值与之对应 XB=B-1b-B-1NXN运筹学教程特别，取XN=0，这时有XB=B-1b 线性规划的解称为线性规划与基B对应的基解若其中基变量的值XB=B-1b0，则称以上的基解为 一基可行解，相应的基B称为可行基 运筹学教程基本概念：基本概念： 凸集凸集——如果集合C中任意两个点X1,X2，其连线上的所有 点也都是集合C中的点，则称C为凸集．用数学解析式表示：若任意两点X１∈C，X2∈C的连线上的一切点：αXαX1 1+ +（（1-α1-α））X X2 2∈∈ C C（0XX 的正分量所对应的系数列向量线性无关的正分量所对应的系数列向量线性无关必要性必要性→→由基本可行解定义直接证得由基本可行解定义直接证得充分性充分性←←正分量K个线性无关线性无关k=m →X=(x1,x2,…,xm,0,…0)T即为基本可行解 k
2、线性规划的基本可行解和可行域的顶 点是一一对应的（类似于。