《《线性规划的图解法》ppt课件》由会员分享，可在线阅读，更多相关《《线性规划的图解法》ppt课件（49页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性规划的图解法,一、线性规划问题及其数学模型,二、图解法,三、线性规划问题的一般形式和 标准形式,四、图解法的灵敏度分析,本章主要内容,一、线性规划问题及其数学模型,（1）实际模型：建筑设计师运用小型模型帮助他们设计新大楼；汽车设计师建立新型汽车的模型来检测设计指标，或用撞车试验来模拟乘车人在汽车事故中所受的影响等。,（2）数学模型：运筹学模型是数学模型或计算机模 型。在运筹学模型中，反映现实世界的关系用 数学等式或逻辑描述表示。,（3）线性规划模型：属于最优化模型。最优化模型 解决求最大利润、最小成本、最大回报率等问 题。例如：P11的例1。,1、关于模型,2. 几个概念：,（1）
2、线性变量之间呈正比例关系或一次相 加关系；如：y=2x；y=x+6；y=5x1+9x2 等。,（2）函数两个变量x和y，对于某一范围内 的、x的每一个取值，y都有一个或几个值和 它对应，y就是x的函数。,（3）目标函数问题中要确定的未知量（称 决策变量）的函数关系式； 如：max z=2x1+x2,（4）约束条件决策变量取值时受到的各种 资源条件的限制，通常表达为含决策变量的 线性方程或不等式。,（1）由决策变量构成，反映决策 的目标是线性函数；,3. 线性规划模型的特征,（2）一组由决策变量的线性等式 或不等式构成约束条件；,（3）对决策变量取值范围加以 限制的非负约束。,4. 建立一个问题
3、的线性规划 模型的一般步骤,（1）确定决策变量； （2）确定目标函数； （3）确定约束条件； （4）确定变量是否有非负约束。,练习1： 资源利用问题,要求：在资源有限情况下求总利润最大的生产计划。,解：,设产品、各生产 x1、x2 件，总利润Z ；,Max Z = 2 x1 +3 x2,2x1 +2x2 12,x1 +2x2 8,4x1 16,4x2 12,x1，x2 0,（资源1）,（资源2）,（资源3）,（资源4）,目标函数,约束条件,练习2： 污水处理问题,(1000元/万M3),(800元/万M3),污水进入河道后20%自然净化，要求污水含量2,求总费用最少的处理方案。,解：,设甲乙厂
4、各处理 x1、x2 万M3/天 ； 总费用 Z 元/天； 考虑 A、B 两点：,则有： 目标函数 Min Z = 1000 x1 +800 x2 x1 1 （ A点） 0.8x1 + x2 1.6 （ B 点） x1 2 （甲排放量限制） x2 1.4 （乙排放量限制） x1，x2 0,约束条件,练习3：生产计划问题,某车间在每个生产期5天所需要的某种刀具的统计资料如下：,每一把刀具成本为0.6元，用过的刀具送到机修车间研磨，每把刀具需要花费0.2元（考虑内部核算）。刀具每天用过后，如果立即送去磨，第三天可以磨好送回，供当天的需用。第五天后，刀具应全部换新，每期开始时，该车间没有任何刀具。问这
5、个车间需要多少刀具才能应付需要，而成本又最低？试建立其线性规划模型。,解：,设决策变量 xi (i=1,2,3,4,5)为第i天使用的新刀具，yj(j=1,2,3)为第j天送去研磨的刀具数；Z为刀具所花的成本。,考虑送去研磨的刀具第三天才能使用： 第1、2天所使用的只能是新刀具，从第三天起，每天使用的刀具可以是新的，也可以是磨好后送回的，所以：,x1=120， x2=85， x3+y1=160， x4+y2=145， x5+y3=300,则有：,约束条件,X1 =120,X2 =85,x3+y1 = 160,x4+y2 =145,y1 120,y2 85 + (120-y1),y3 160 +
6、 (120-y1) + (85-y2),xi 0 (I=1,2,3,4,5) 且均为整数,yj 0（j=1,2,3）且均为整数,x5+y3 =300,Max Z = 2 x1 +3 x2,只适用于 n = 2 的情况。,二、图 解 法,例：,1.几个名词：,图解法通过在平面上作图求解 的方法；,可行解满足约束条件（包括非 负条件）的解， 即可行方案；,可行域全体可行解；,最优解使目标函数取得最优的 可行解。,（1）在直角坐标系中分别作出各 约束条件，从而确定可行域；,2. 图解法步骤：,（2）作出一条目标函数等值线；,（3）将目标函数等值线沿目标函数 值增大（或减小）方向移动，以 求得最优解或
7、确定线性规划无解。,例1： 求最优解： 教材第13-14页,例2：,(0.5,0.5),Min Z=x+2y,y,x,可行解,例3：用图解法求最优解,A,可行解,Min Z=1000x1+800x2,=1640,. .,.,解：,1. 无可行解（约束方程组矛盾），也就无最优解；,2. 有可行解，但目标函数 Z（X） +（求Max） 或 Z（X） （求Min） 也就无最优解；,L.P. 最优解的可能情况：,3. 有唯一最优解，即 X* 和Z *都有唯一值；,4.有无穷多个最优解，即X* 有无穷多个值，Z *都有 唯一值。,练习： 教材第24页的2.a,作业： 教材第24页的2.c、d、e,例 4
8、：图解法综合应用举例,试分别求以下目标时的最优生产计划： 1、总产值最大； 2、总人力最少； 3、人均产值最大。,解： 设 、 产品各生产 x1、x2 （百件） 总产值 Z（百元） 总人力 W（百人月） 人均产值 T（百元/百人月） 特殊零件（百个）,写出数学模型：,Max Z=1000x1+500x2,Min W=5x1+2x2,1. 总产值 Z 最大，BC 线段最优：,2. 总人力 W 最少，A 点最优：,3. 人均产值 T 最大,三、线性规划问题的一般形式和标准形式,1.一般形式：,最优解：,Z 称为目标函数； c i称为目标系数； X=（x 1，x n）T 称为方案向量； x i称为方
9、案变量； n 为变量个数； m 为约束条件个数； b j 称为约束条件右端常数项； b j0，否则两端乘以（-1）。,式中字母含义：,注释：,2. 标准形式：,标准形式的矩阵形式：,标准形式的特点：,1.目标函数为求极大值；,2.约束条件均为等式；,3.右端常数项均为非负值；,4.决策变量的取值均为非负值。,其它形式转换成标准型：,（1）求 Min Z = CX,则只须令 Z = - Z = - CX =（ - C）X = CX,可转换为求 Max Z = CX,而最优解为 : X* 不变,Z* = (Z )*,“ ”： a11 x1 + + a1n x n b1 只须改为 a11 x1 +
10、+ a1n x n + x n+1 b1 且 x n+1 0 ， c n+1 = 0,(2) 约束条件：,“ ”： a21 x1 + + a2n x n b2 只须改为 a21 x1 + + a2n x n x n+2 b2 且 x n+2 0 ， c n+2 = 0,其中x n+1和x n+2 称为 松弛变量和剩余变量，,其经济意义：未被充分利用的资源数和超出的资源数。,x i * = xi * x i *,（3）若变量 xi是自由变量，即可正可负：,则只须引入两个新变量,x i , x i 0 ，,作变量替换,xi = x i x i 即可；,而最优解 X* 中有,(4) 若变量x i取值
11、为负：,则只需令： x i = x i ,x i 0,例：,化线性规划的非标准式为标准式,x1 + x2 + (x3 x3) + x4 = 7 x1 x2 + (x3 x3） x5 = 2 3x1 + x2 +2 (x3 x3） = 10 x1，x2，x3 ，x3，x4，x5 0,Max Z = x12x2 +3 (x3 x3）+ 0 x4 + 0 x5,解：,令 Z = Z ， x3 = x3 x3,在第1个和第2个约束条件中引入松弛变量 x4 和剩余变量 x5,则标准式为：,原最优解：,X* =（x1*，x2*，x3*x3*，x4*，x5*）T,Z* = Z *,作业：教材第25页的3.c
12、, 第26页的5。,四、图解法的灵敏度分析,1. 概 念：,灵敏度分析是在建立数学模型和求得最优解之后，研究线性规划的一些系数（ ci、aij、bj）变化时，对最优解产生什么影响的过程。,2. Ci的灵敏度分析：,约束条 件不变,可行域 不变,改变 ci,目标函 数的斜 率改变,最优解改变,例：P20-21,3. bj的灵敏度分析：,约束条 件改变,可行域 改变,目标函 数的斜 率不变,最优解改变,例：P22-23,改变 bj,Ci 不变,关 于 对 偶 价 格,1. 对偶价格的概念：,在约束条件右边常量增加一个单位而使最优目标函数值得到改进的数量，称为这个约束条件的对偶价格。,2. 对偶价格与最优目标函数值的关系：,练习： 教材第26页的7.,作业： 教材第26页的6.,
