一、本章内容简要回顾 在这一章里,我们首先由一个生产计划....

1、一、本章内容简要回顾一、本章内容简要回顾 在这一章里，我们首先由一个生产计划的实际问题引在这一章里，我们首先由一个生产计划的实际问题引出了线性规划的数学模型，线性规划问题实际就是在一组出了线性规划的数学模型，线性规划问题实际就是在一组线性不等式或等式约束条件下，求某一线性目标函数的最线性不等式或等式约束条件下，求某一线性目标函数的最大或最小值的优化问题。我们通过具有两个决策变量的线大或最小值的优化问题。我们通过具有两个决策变量的线性规划问题的图解法，对线性问题的解、可行解、可行域性规划问题的图解法，对线性问题的解、可行解、可行域及最优解有了一个初步直观的认识，那就是：具有两个决及最优解有了一个

2、初步直观的认识，那就是：具有两个决策变量的线性规划问题的可行域是凸多边形；若线性规划策变量的线性规划问题的可行域是凸多边形；若线性规划问题存在最优解，则一定在可行域的某个顶点得到。问题存在最优解，则一定在可行域的某个顶点得到。 接着，我们规定了线性规划的标准型，给出了线性规接着，我们规定了线性规划的标准型，给出了线性规划的基、基解以及基可行解的概念；还给出了凸集及其顶划的基、基解以及基可行解的概念；还给出了凸集及其顶点的定义，在此基础上，通过三个定理的论证，对图解法点的定义，在此基础上，通过三个定理的论证，对图解法的结论加以拓展，得出了如下结论：的结论加以拓展，得出了如下结论：第一章线性规划与

3、单纯形法第一章线性规划与单纯形法1.线性规划问题的可行域是凸集；线性规划问题的可行域是凸集；2.该凸集的每个顶点都对应一个基可行解，因基可行解个该凸集的每个顶点都对应一个基可行解，因基可行解个数是有限的，从而凸集的顶点也是有限的；数是有限的，从而凸集的顶点也是有限的；3.若线性规划问题存在最优解，则一定能在可行域的某个若线性规划问题存在最优解，则一定能在可行域的某个顶点达到，也就是在有限个基可行解中找到。上述结论顶点达到，也就是在有限个基可行解中找到。上述结论就是求解线性规划的通用方法就是求解线性规划的通用方法单纯形法的理论基础。单纯形法的理论基础。第一章线性规划与单纯形法第一章线性规划与单纯

4、形法单纯形法全过程的计算，可以用列表的方法计算更为简单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表。洁，这种表格称为单纯形表。随后，我们详细讲述了单纯性表的结构、最优解判定定随后，我们详细讲述了单纯性表的结构、最优解判定定理、无界解判定定理和单纯形法的解题步骤。理、无界解判定定理和单纯形法的解题步骤。计算步骤计算步骤：1.求初始基可行解，列出初始单纯形表，求出检验数。其中求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；基变量的检验数必为零； 2.判断：判断： （a）若）若j（j，n）得到最优解；）得到最优解； （b）某个）某个k0且且aik（i

5、=1，2,m）则线性规划具有无）则线性规划具有无界解界解(见例见例1.18)。 （c）若存在）若存在k0且且aik (i=1,m)不全非正，则进行换基；不全非正，则进行换基；min0,0,iiLikikikikbbaaM Maa当 时为任意大的正数第第个比值最小个比值最小 ，选最小比值对应行的基变量为出基变量，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。若有相同最小比值，则任选一个。aLk为主元素；为主元素； (c）求新的基可行解：用初等行变换方法将）求新的基可行解：用初等行变换方法将aLk 化为化为,k列列其它元素化为零（包括检验数行）得到新的可行基及基本可其它元素化为

6、零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。行解，再判断是否得到最优解。（b）选出基变量）选出基变量 ，求最小比值：，求最小比值：3.换基：换基：（a）选进基变量）选进基变量设设k=max j | j 0,xk为进基变量为进基变量二、应重点掌握的问题二、应重点掌握的问题 1. 应用图解法求解线性规划应用图解法求解线性规划 2. 根据实际问题建立线性规划数学模型；根据实际问题建立线性规划数学模型； 3. 用单纯形表求解线性规划。用单纯形表求解线性规划。 唯一最优解的判断：唯一最优解的判断：最优表中所有非基变量的检验数最优表中所有非基变量的检验数非零非零,则线规划具有唯一最

7、优解则线规划具有唯一最优解 。 多重最优解的判断多重最优解的判断: 最优表中存在非基变量的检验数最优表中存在非基变量的检验数为零为零,则线则性规划具有多重最优解。则线则性规划具有多重最优解。 无界解的判断无界解的判断: 某个某个k0且且aik（i=1，2,m）则线）则线性规划具有无界解性规划具有无界解 退化基本可行解的判断退化基本可行解的判断: 存在某个基变量为零的基本存在某个基变量为零的基本可行解。可行解。1.5 单纯形法单纯形法 Simplex Method【解】设解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为123123123123123m ax1014121.51.24

8、250031.61.21400150250260310120130,0Zxxxxxxxxxxxxxxx1.2 工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表122所示产品资源ABC资源限量材料(kg)1.51.242500设备(台时)31.61.21400利润(元/件)101412 根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大本章内容回顾本章内容回顾 在这一章里，我们首先引出了线性规划的对偶问题，阐述在这一章里，我们首先引出了线性规划的对偶问

9、题，阐述了线性规划原问题与其对偶问题的关系（表了线性规划原问题与其对偶问题的关系（表2-4）。）。 接着，论证了对偶问题的六个重要性质；在此基础上，讲接着，论证了对偶问题的六个重要性质；在此基础上，讲述了求解线性规划的对偶单纯形法，其计算步骤为：述了求解线性规划的对偶单纯形法，其计算步骤为：第二章线性规划的对偶理论第二章线性规划的对偶理论(1)将线性规划的约束化为等式，求出一组基本解，因为对偶问将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数题可行，即全部检验数j0（max）或）或j0（min）,当基本解可当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解

10、行时，则达到最优解；若基本解不可行，即有某个基变量的解bi0，则进行换基计算；，则进行换基计算；(2)先确定出基变量。先确定出基变量。 l 行对应的变量行对应的变量x出出基；基；min|0liiibb b (3)再选进基变量。求最小比值再选进基变量。求最小比值0|minljljjjkaa(4)求新的基本解，用初等变换将主元素求新的基本解，用初等变换将主元素alk化为化为l,k列其它元素化为列其它元素化为零，得到新的基本解，转到第一步重复运算。零，得到新的基本解，转到第一步重复运算。本章还介绍了对偶问题的经济意义本章还介绍了对偶问题的经济意义影子价格。影子价格。对偶最优解对偶最优解 ， yi表示

11、在原问题已取得表示在原问题已取得最优解的情况下，第最优解的情况下，第i种资源增加一个单位时总收益的增加值，种资源增加一个单位时总收益的增加值，也可以说也可以说yi是对第是对第i种资源的一种价格估计。这种价格估计并不种资源的一种价格估计。这种价格估计并不是第是第i种资源的实际价值或成本，而是由该企业在制产品的收益种资源的实际价值或成本，而是由该企业在制产品的收益来估计所用资源的单位价值，它是一种潜在的价格，称为影子来估计所用资源的单位价值，它是一种潜在的价格，称为影子价格。价格。)y,y,y(BCYn211B企业可以将资源的影子价格与市场价格比较，来决定是购企业可以将资源的影子价格与市场价格比较

12、，来决定是购入还是出让该种资源。当某资源的市场价格低于影子价格时，入还是出让该种资源。当某资源的市场价格低于影子价格时，企业应该同买进该资源用于扩大生产；而当市场价格高于影子企业应该同买进该资源用于扩大生产；而当市场价格高于影子价格时，则企业的决策者应该将已有资源买掉。这样获利会更价格时，则企业的决策者应该将已有资源买掉。这样获利会更多。多。利用单纯形表求解线性规划，在求得最优解的同时，很容利用单纯形表求解线性规划，在求得最优解的同时，很容易得到问题的各种资源的影子价格。某资源的影子价格，就是易得到问题的各种资源的影子价格。某资源的影子价格，就是该资源对应的约束条件所加松弛变量在最优表中的检验

13、数的相该资源对应的约束条件所加松弛变量在最优表中的检验数的相反数。反数。 本章最后详细讲述了线性规划某些系数或限制数变动的灵本章最后详细讲述了线性规划某些系数或限制数变动的灵敏度分析，以及参数线性规划问题。敏度分析，以及参数线性规划问题。二、应重点掌握的问题二、应重点掌握的问题 1、用对偶单纯形法求解线性规划问题；、用对偶单纯形法求解线性规划问题； 2、对偶问题的经济意义、对偶问题的经济意义影子价格；影子价格； 3、灵敏度分析、灵敏度分析。3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 7某工厂利用原材料甲、乙、丙生产产品A、B、C，有

14、关资料见表2-23 ABC每月可供原材料（Kg）甲乙丙211200123500221600每件产品利润413（1）怎样安排生产，使利润最大（2）若增加1kg原材料甲，总利润增加多少（3）设原材料乙的市场价格为1.2元/Kg，若要转卖原材料乙，工厂应至少叫价多少， 为什么？（4）单位产品利润分别在什么范围内变化时，原生产计划不变（5）原材料分别单独在什么范围内波动时，仍只生产A和C两种产品（6）由于市场的变化，产品B、C的单件利润变为3元和2元，这时应如何调整生产计划（7）工厂计划生产新产品D，每件产品D消耗原材料甲、乙、丙分别为2kg，2kg及1kg， 每件产品D应获利多少时才有利于投产3.2

15、 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 【解解】（1）设 x1、x2、x3分别为产品A、B、C的月生产量，数学模型为123123123123123max43212002350026000,0,0Zxxxxxxxxxxxxxxx最优单纯形表：C(j)413000R.H.S. XB CBX1X2X3X4X5X6X1411/503/5-1/5020X3303/51-1/52/50160X60000-1014000-8/50-9/5-2/50Z=560最优解X=（20，0，160），Z=560。工厂应生产产品A20件，产品C160种，总利润为

16、560元。j3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 12392,055yyy123123832,195131,6,(,2,125cccccc 123123100400,400100,4003500,600,100,600,200,).3bbbbbb （2）则最优表可知，影子价格为 ，故增加利润1.8元。（3）因为y2=0.4，所以叫价应不少于1.6元。（4）依据最优表计算得（5）依据最优表计算得3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming （6）变化后的检验数为2=1,4= - 2,5=0。故x2进基x1出基 C(j)432000R.H.S.Ratio XB CBX1X2X3X4X5X6X1411/503/5-1/5020100X3203/51-1/52/50160800/3X60000-101400M010-200560X225103-10100MX33-301-210100100X600