第二章线性规划的图解法(简)

1、第二章第二章线性规划的图解法线性规划的图解法 主要内容： 1 问题的提出 （什么是线性规划）2 图解法3 图解法的灵敏度分析重点和难点o 重点：重点： （1）线性规划问题的主要概念）线性规划问题的主要概念 （2）线性规划问题的数学模型）线性规划问题的数学模型 （3）线性规划图解法的过程）线性规划图解法的过程 （4）阴影价格的定义和灵敏度分析）阴影价格的定义和灵敏度分析o 难点：难点： 灵敏度分析灵敏度分析第一节 问题的提出 线性规划是运筹学最成熟的一个分支。开始是在生产组织管理和制定交通运输方案方面，后来波及更广的范围，小到一个班组的计划安排，大至整个部门，以至国民经济计划的最优化方案分析，它

2、都有用武之地。 第一节 问题的提出1线性规划的典型应用 合理利用线材问题 配料问题 投资问题 产品生产计划 劳动力安排 运输问题第一节 问题的提出例例1 1某工厂在计划期内要安排某工厂在计划期内要安排I I、两种产品的生产两种产品的生产, ,已知生已知生产单位产品所得的设备台时及、产单位产品所得的设备台时及、B B两种原材料的消耗，以两种原材料的消耗，以及资源的限制如表所示。该工厂每生产一单位产品及资源的限制如表所示。该工厂每生产一单位产品I I可获利可获利5050元，每生产一单位产品元，每生产一单位产品可获利可获利100100元，问工厂应分别生元，问工厂应分别生产多少个产多少个I I产品和产

3、品和产品才能使工厂获利最多产品才能使工厂获利最多? ?III资源限制设备11300台时原料A21400kg原料B01250kg第一节 问题的提出这个问题可以用以下的数学模型来加以描述。这个问题可以用以下的数学模型来加以描述。 x x1 1生产生产I I产品的数量产品的数量 x x2 2= =生产生产产品的数量。产品的数量。决策变量（Decision variables） 第一节 问题的提出数学模型：数学模型：目标函数：目标函数：MAX Z=50XMAX Z=50X1 1 +100X +100X2 2满足约束条件：满足约束条件： X X1 1+X+X2 2 300 300 2X 2X1 1+X+

4、X2 2 400 400 X X 250250 X X1 1、X X2 2 0 0第一节 问题的提出 、数学模型的目标函数为变量的线性函数，、数学模型的目标函数为变量的线性函数，约束条件也为变量的约束条件也为变量的线性等式或不等式线性等式或不等式，故此，故此模型称之为模型称之为线性规划线性规划。 、如果目标函数是变量的非线性函数，或约、如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数束条件中含有变量非线性的等式或不等式的数学模型则称之为学模型则称之为非线性规划非线性规划。第一节 问题的提出 、把满足所有约束条件的解称为该线性规划、把满足所有约束条件的解称为该线性规划

5、的的可行解可行解。、把使得目标函数值最大、把使得目标函数值最大( (即利润最大即利润最大) )的可行的可行解称为该线性规划的解称为该线性规划的最优解最优解，此目标函数值称，此目标函数值称为最优为最优目标函数值目标函数值，简称，简称最优值最优值。第一节 问题的提出建立线性规划问题数学模型的步骤：建立线性规划问题数学模型的步骤：、定义决策变量定义决策变量，每个问题都用一组决策变量（，每个问题都用一组决策变量（X X1 1X X2 2X X3 3XXN N）表示某一方案；这组决策变量的值就代）表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量的取值是非负的表一个具体方案，一般这些变量的取

6、值是非负的 、用决策变量的线性函数形式写出所要追求的目标，称、用决策变量的线性函数形式写出所要追求的目标，称之为之为目标函数目标函数。 具有上述具有上述3 3个特征的问题为个特征的问题为线性规划问题。线性规划问题。第一节 问题的提出 我们的任务就是要选择一组或多组方案，使目我们的任务就是要选择一组或多组方案，使目标函数值最大或最小。从选择方案的角度说，标函数值最大或最小。从选择方案的角度说，这是规划问题。从使目标函数值最大或最小的这是规划问题。从使目标函数值最大或最小的角度说，就是优化问题。角度说，就是优化问题。线性规划数学模型的一般表示方式线性规划数学模型的一般表示方式技术系数右端项价值系数

7、线性规划问题的规模约束行数变量个数: ;: ;: ;: ;:0,),(),(),(.)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf思考题 某公司由于生产需要，共需要，B两种原料至少350吨(A，B两种材料有一定替代性)，其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元试问在满

8、足生产需要的前提下，在公司加工能力的范围内，如何购买A、B两种原料，使得购进成本最低?解：设X1为购进原料A的吨数，X2为购进原料B的吨数。第二节 图解法Z=27500例1的数学模型：目标函数：MAX Z=50X1 +100X2约束条件：X1+X2300 2X1+X2400 X 250 X1、X2 0可行解可行解可行域可行域等值线等值线第二节 图解法 这样就得到了例1的最优解B点，B点的坐标为(50，250)，因此最佳决策为X1=50，X2=250,此时Z27500这说明该厂的最优生产计划方案是生产I产品50单位，生产产品250单位，可得最大利润27500元。 把X1=50，X2=250代入约

9、束条件得： 1*(50)+1*(250)300台时设备 2*(50)+l*(250)=350千克原料A， 1*(250)250千克原料B第二节 图解法 在线性规划中，对一个约束条件中没使用的资源或能力的大小称在线性规划中，对一个约束条件中没使用的资源或能力的大小称之为之为松弛量松弛量。记为记为Si Si。第二节 图解法 像这样把所有的约束条件都写成等式，称为线性规划模型的标准化，所得结果称为线性规划的标准形式。第二节 图解法同样对于约束条件中，可以增加一些代表最低限约束的超过量，称之为剩余变量，把约束条件变为等式约束条件，加了松弛变量与剩余变量后，思考题的数学模型为：线性规划问题的几个特点：o

10、 线性规划问题的可行解的集合是凸集o 线性规划问题的基础可行解一般都对应于凸集的极点o 凸集的极点的个数是有限的o 最优解只可能在凸集的极点上，而不可能发生在凸集的内部第三节 图解法的灵敏度分析“心有灵犀一点通”灵敏度分析又称为后优化分析Post-optimization Analysis第三节 图解法的灵敏度分析o 线性规划是静态模型o 参数发生变化，原问题的最优解还是不是最优o 哪些参数容易发生变化n C, b, Ao 每个参数发生多大的变化不会破坏最优解o 灵敏度越小，表示解的稳定性越好。第三节 图解法的灵敏度分析 所谓所谓灵敏度分析灵敏度分析就是在建立数学模型和就是在建立数学模型和求得

11、最优解之后，研究线性规划的一些系求得最优解之后，研究线性规划的一些系数数C Ci i、a aij ij、b bj j变化时，对最优解产生什么影变化时，对最优解产生什么影响响? ?第三节 图解法的灵敏度分析 灵敏度分析的作用：1、Ci、aij、bj这些系数都是估计值和预测值，不一定非常精确。2、即使这些系数值在某一时刻是精确值，它们也会随着市场条件的变化而变化。有了灵敏度分析就不必为了应付这些变化而不停地建立新的模型和求其新的最优解，也不会由于系数的估计和预测的精确性而对所求得的最优解存有不必要的怀疑。第三节 图解法的灵敏度分析一、目标函数中的系数i的灵敏度分析 例1中生产一个单位的I产品可以获

12、利50元(C150)，生产一个单位的产品可以获利100元(C2100)。在目前的生产条件下求得生产I产品50单位生产产品250单位可以获得最大利润。当I、产品中的某一产品的单位利润增加或减少时，为了获取最大利润就应该增加或减少这一产品的产量，也就是改变最优解。3.1 目标函数中的系数Ci的灵敏度分析 目标函数的斜率在直线E(设备约束条件)的斜率与直线F(原料B的约束条件)的斜率之间变化时，坐标X150，X2250的顶点B仍然是最优解。如果目标函数的直线反时针旋转，当目标函数的斜率等于直线F的斜率时，则可知直线AB上的任一点都是其最优解。如果继续反针旋转，则可知A点为其最优解。3.1 目标函数中

13、的系数Ci的灵敏度分析 如果目标函数直线顺时针方向旋转，当目标函效的斜率等于直线E的斜率时，则可知直线BC上的任一点都是其最优解。如果继续顺时针方向旋转，当目标函数的斜率在直线E的斜率与直线G的斜率之间，则顶点C为其最优解。3.1 目标函数中的系数Ci的灵敏度分析The 100 percent rule百分之百法则百分之百法则目标函数系数同时变动的百分之百法则目标函数系数同时变动的百分之百法则(The 100 percent rule for simultaneous changes in objective function coefficients)：如果目标函数的系数同时变动，计算出每一

14、系数变动量占该系数最优域允许变动量的百分比，而后，将各个系数的变动百分比相加，如果所得的和不超过百分之一百，最优解不会改变，如果超过百分之一百，则不能确定最优解是否改变。 3.2 约束条件中右边系数bj的灵敏度分析3.2 约束条件中右边系数bj的灵敏度分析在约束条件右边常量增加一个单位而在约束条件右边常量增加一个单位而使最优目标函数值得到改进的数量称之为使最优目标函数值得到改进的数量称之为这个约束条件的这个约束条件的对偶价格对偶价格。3.2 约束条件中右边系数bj的灵敏度分析第三节 图解法的灵敏度分析 在目标函数求最大值的情况下，除了对偶价格大于零、等于零的情况外，还存在着对偶价格小于零的情况

15、。当某约束条件对偶价格小于零时，约束条件右边常数增加一个单位，就使得最优目标函数值减少一个其对偶价格。第三节 图解法的灵敏度分析 对目标函数值求最小值的情况下，当对偶价格大于零时，约束条件右边常数增加一个单位就使其最优目标函数值减少一个其对偶价格；当对偶价格等于零时，约束条件右边常数增加一个单位，并不影响其最优目标函数值；当对偶价格小于零时，约束条件右边常数增加一个单位，就使得其最忧目标函数值增加一个其对偶价格。第三节 图解法的灵敏度分析 当约束条件右边常数增加个单位时：1.如果对偶价格大于零，则其最优目标函数值得到改进，即求最大值时变得更大；求最小值时，变得更小。2.如果对偶价格小于零，则其最优目标函数值变大，即求最大值时，变得小了；求最小值时变得大了。3.如果对偶价格等于零，则其最优目标函数值不变。习题一、一、Excelo Excel 的线性规划的线性规划二、二、WinQSBo QSB-Quantitative System for Business 作业：Specific Motors公司汽车模型生产问题o Specific Motors公司生产三种类型的汽车，型号分别为X、Y和Z。三种产品的净收入分别