线性规划-课件.ppt

《线性规划-课件.ppt》由会员分享，可在线阅读，更多相关《线性规划-课件.ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、线性规划线性规划第二讲第二讲线性规划线性规划线性规划2.1 引言引言 线性规划是运筹学的重要分枝，也是运筹学最基本的部分。20 世纪 30 年代末，前苏联学者康托洛维奇首先研究了线性规划问题。1939 年，他撰写的生产组织与计划中的数学方法一书，是线性规划应用于工业生产问题的经典著作。然而这项工作长期不为人们所知。线性规划 第二次世界大战期间，由于战争的需要，柯勃门(T.C.Koopmans)重行、独立地研究了运输问题。后来丹西格(G.B.Dantzig)于 1947 年发现了单纯形方法，并将其应用于与国防有关的诸如人员的轮训、任务的分派等问题。此后，线性规划的理论和方法日渐趋于成熟。线性规划

2、 线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。和其它最优化问题一样，在建立线性规划问题的数学模型时，应首先明确三个基本要素：决决策策变变量量(decision variables)：它们是决策者(你)所控制的那些数量，它们取什么数值需要决策者来决策，问题的求解就是找出决策变量的最优值。线性规划 约约束束条条件件(constraints)：它们是决策者在现实世界中所受到的限制，或者说决策变量在这些限制范围之内才有意义。目目标标函函数数(objective function)：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。线性规划问题的特特征征是目标函数和约束条

3、件中的函数都是决策变量的线性函数，并且约束是必不可少的(否则不存在有实际意义的解)。线性规划2.2 引例：食用油加工计划引例：食用油加工计划 加工一种食用油需要精炼若干种原油并把它们混合起来。原油来源有两类共 5 种：植物油：VEG1，VEG2 非植物油：OIL1，OIL2，OIL3购买每种原油的价格(镑/吨)见表 2.2.1：线性规划VEG1VEG2OIL1OIL2OIL3110120130110115表 2.2.1：最终产品以 150 镑/吨价格出售。植物油和非植物油需要在不同的生产线上进行精炼。每月能够精炼的植物油不超过 200吨，非植物油不超过 250 吨；在精炼过程中，重量没有损失，

4、精炼费用可忽略不计。线性规划VEG1VEG2OIL1OIL2OIL38.86.12.04.25.0 最终产品要符合硬度的技术条件。按照硬度计量单位，它必须在 36 之间。假定硬度的混合是线性的，而原油的硬度见表 2.2.2：表 2.2.2 问：为使利润最大，应该怎样制定它的月采购和加工计划？线性规划 要建立表述这个问题的数学模型，首先需要确定它的三个要素。1确定决策变量 设 x1,x5 分别代表需要采购的 5 种原油的吨数，y 代表需要加工的成品油的吨数。线性规划2确定约束条件生产能力限定：x1+x2 200(植物油 200 吨)x3+x4+x5 250(非植物油 250 吨)技术指标(硬度)

5、限定：8.8x1+6.1x2+2x3+4.2x4+5x5 6y 8.8x1+6.1x2+2x3+4.2x4+5x5 3y连续性(均衡性)：x1+x2+x3+x4+x5=y非负性：xi 0(i=1,5)，y 0线性规划 3确定目标函数 目标是使利润最大，即出售产品的收入扣除原油成本之后所得最大：150y 110 x1 120 x2 130 x3 110 x4 115x5 最大线性规划 显然这是一个线性规划问题，可以用下面的数学模型来表述这个问题：线性规划2.3 线性规划模型线性规划模型2.3.1 线性规划模型的一般形式 线性规划问题有各种不同形式，其目标函数可以是实现最大化，也可以是实现最小化；

6、约束条件可以是“”，也可以是“”，还可以是“=”的形式；决策变量可以非负，也可以是无符号限制。线性规划 归纳起来，线性规划问题的数学模型的一一般形式般形式为：线性规划或者：这里“s.t.”是“subject to”的缩写，即“满足于”的意思。线性规划如果我们设 线性规划一般形式也可用矩阵形式描述为：线性规划2.3.2 线性规划模型的标准形式 为理论研究之便，人们规定线性规划模型的标准形式为：线性规划 若给定问题的目标函数是求 min Z=CTX，则可化为求 max Z =CTX；若给定问题的约束条件中含有不等式：ai1x1 ai2x2 ainxn(或 )bi，则可等价地化为：ai1x1 ai2

7、x2 ainxn xn+1=bi，xn+1 0或ai1x1 ai2x2 ainxn xn+1=bi，xn+1 0 我们称新增加的变量 xn+1 为松弛变量松弛变量。线性规划2.3.3 线性规划问题解的概念 对于线性规划问题，我们定义：可行解可行解：满足全部约束条件的决策向量。可可行行域域：全部可行解构成的集合(它是 n 维欧氏空间 Rn 中的点集，而且是一个“凸多面体”)。最最优优解解：使目标函数达到最优值(最大值或最小值，并且有界)的可行解。无无界界解解：若求极大化则目标函数在可行域中无上界；若求极小化则目标函数在可行域中无下界。线性规划 线性规划问题的最优解有下列几种情况：(1)有最优解时

8、，可能有唯一最优解，也可能有无穷多个最优解。如果最优解不唯一，最优解一定有无穷多个，不可能为有限个。最优解的目标函数值均相等。(2)没有最优解时，也有两种情形。一是可行域为空集，二是目标函数值无界(求最大时无上界，求最小时无下界)。线性规划 定定理理：当线性规划问题有最优解时，一定可以在可行域的某个顶点上取到。当有唯一解时，最优解就是可行域的某个顶点。当有无穷多个最优解时，其中至少一个是可行域的一个顶点。线性规划2.3.4 几何解释 在这部分，我们给出一种求解两个变量的线性规划问题的几何方法，目的是阐明线性规划问题的基本原理及其直观的几何意义。线性规划 例 2.3.1 求解线性规划问题 max

9、 Z=x1 x2 s.t.2x1 3x2 6 3x1 2x2 6 xi 0(i=1,2)我们把 x1,x2 看成坐标平面上的坐标，则满足约束条件的点集，即可行域，如图 2.3.1 阴影部分所示。线性规划图 2.3.1可行域线性规划 目标函数 x1+x2=c 在坐标平面上是一簇平行线，称为目标函数的等值线，在同一等值线上目标值相等。箭头表示目标函数值增大的方向，其方向与目标函数的梯度方向(1,1)T 相同。线性规划 由于是求最大值问题，目标函数的等值线应沿梯度方向移动，到临界状态，即可行域的顶点(6/5,6/5)处，目标函数取得最大值 12/5。继续沿梯度方向上升，目标函数值会更大，但与可行域无

10、交点，即找不到满足所有约束条件的点使得目标值比 12/5 大。线性规划图 2.3.1线性规划 因此，线性规划问题的最优解为临界等值线与可行域的交点：x*=(6/5,6/5)，最优值为12/5。线性规划 例 2.3.2 求解线性规划问题 max Z=2x1 3x2 s.t.2x1 3x2 6 3x1 2x1 6 xi 0(i=1,2)线性规划问题的可行域仍如图 2.3.1 所示；目标函数的等值线为 2x1 3x2=c；目标函数的梯度方向为(2,3)T。线性规划图 2.3.1线性规划 由于是求最大值问题，目标函数的等值线应沿梯度方向推进，临界等值线为2x1 3x2=6与可行域交于一线段 PQ，其中

11、 P(0,2)，Q(6/5,6/5)，最优解为 PQ 上任一点，最优值为 6。线性规划图 2.3.1线性规划 例 2.3.3 求解线性规划问题 min Z=2x1 x2，s.t.x1 x2 2 x1 4x2 2 xi 0(i=1,2)线性规划问题的可行域如图 2.3.2 所示，目标函数的梯度方向为(2,1)T。由于是求最小值问题，目标函数的等值线应沿负梯度方向推进，可一直进行下去，得不到临界等值线，此问题目标值无下界，无最优解。线性规划线性规划 例 2.3.4 求解线性规划问题 min Z=2x1 5x2，s.t.x1 x2 2 x1 x2 3 xi 0(i=1,2)线性规划问题的可行域如图

12、2.3.3 所示，是一空集。此问题无最优解。线性规划线性规划2.4 用用 Matlab 解线性规划解线性规划 在 Matlab 软件的优化工具箱中，求解线性规划的函数为：linprog。其调用格式为x=linprog(c,A,b,Aeq,beq,xLB,xUB)线性规划适用模型为：其中 Aeq、beq 表示约束条件中的等式约束部分AeqX=beq 的系数矩阵和常数向量。使用使用 Matlab 求解线性规划问题，求解线性规划问题，必须是这样的必须是这样的“标准形式标准形式”。线性规划 例 2.4.1 在2.2 的引例中，我们对食用油加工计划问题建立了如下的线性规划模型：线性规划 将上述模型改写成

13、 Matlab 适用的模型，其形式为：线性规划建立 M 文件，编写 Matlab 程序：c=110;120;130;110;115;-150A=1,1,0,0,0,0;0,0,1,1,1,0;8.8,6.1,2,4.2,5,-6;-8.8,-6.1,-2,-4.2,-5,3;b=200;250;0;0;Aeq=1,1,1,1,1,-1;beq=0;xLB=zeros(6,1);xUB=inf*ones(6,1);x=linprog(c,A,b,Aeq,beq,xLB,xUB);x，Profit=c*x线性规划运行上述 Matlab 程序，计算得：x=159.2593 40.7407 0.000

14、0 250.0000 0 450.0000Profit=-1.7593e+004线性规划于是月采购与生产计划为：原油 VEG1VEG2OIL1OIL2OIL3采购量159.2593 40.740702500生产量：450总利润：1.7593104线性规划2.5 灵敏度分析与参数线性规划灵敏度分析与参数线性规划2.5.1 线性规划问题的灵敏度分析 灵敏度分析是指对系统因周围条件变化显示出来的敏感程度的分析。线性规划 在前面讨论线性规划问题时，我们都设定aij,bi,cj 是常数。但在许多实际问题中，包括大型线性规划问题，这些系数往往是估计值或预测值，经常有少许的变动。例如在2.2 的引例中，如果

15、市场条件发生变化，cj 值就会随之变化；生产工艺条件发生改变，会引起 bi 变化，aij 也会由于种种原因产生改变。线性规划 因此提出这样两个问题：当线性规划模型中的参数有一个或几个发生不大的变化时，已求得的线性规划问题的最优解会有什么变化；或者这些参数在什么范围内变化时，线性规划问题的最优解不变。这涉及解的稳定性问题。线性规划 当然，有一套理论方法可以进行灵敏度分析(参见1,2)，这里就不讨论了。但在实际应用中，对于不同的参数值重复求解线性规划问题，不失为一种可用的方法，特别是使用计算机求解时。线性规划2.5.2 参数线性规划 参数线性规划是研究 aij,bi,cj 这些参数中某一参数连续变

16、化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。当然，在实际应用中，给定参变量一个步长重复求解线性规划问题，以观察最优解变化情况，也是一种可用的数值方法。线性规划2.6 范例范例 载载货货问问题题：有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面表 2.6.1 所示。前舱中舱后舱 最大允许载重量(t)200030001500 容积(m3)400054001500线性规划 现有三种货物待运，已知有关数据列于下面表 2.6.2。商品数量(件)每件体积(m3/件)每件重量(t/件)运价

17、(元/件)A6001081000B100056700C80075600线性规划 又为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%。问该货轮应装载 A、B、C 各多少件，运费收入为最大？线性规划 解解：(1)确定决策变量 因为 A、B、C 三种商品在货轮的前、中、后舱均可装载，令 i =1,2,3 分别代表商品 A、B、C，用 j=1,2,3 分别代表前、中、后舱。设决策变量 xij 为装于 j 舱位的第 i 种商品的数量(件)。线性规划 (2)确定目标函数 商品 A 的件

18、数为：x11+x12+x13，即装于货轮前、中、后舱商品 A 的件数之和；商品 B 的件数为：x21+x22+x23，即装于货轮前、中、后舱商品 B 的件数之和；商品 C 的件数为：x31+x32+x33，即装于货轮前、中、后舱商品 C 的件数之和。为使运费总收入最大，目标函数为 max Z=1000(x11+x12+x13)+700(x21+x22+x23)+600(x31+x32+x33)线性规划 (3)确定约束条件 前、中、后舱位载重量限制为：8x11+6x21+5x31 2000 8x12+6x22+5x32 3000 8x13+6x23+5x33 1500 前、中、后舱位体积限制为：

19、10 x11+5x21+7x31 4000 10 x12+5x22+7x32 5400 10 x13+5x23+7x33 1500线性规划 A、B、C 三种商品数量限制为：x11+x12+x13 600 x21+x22+x23 1000 x31+x32+x33 800 根据各舱实际载重量大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%，可得舱体平衡条件为：线性规划 且各决策变量要求非负，即 xij 0，i=1,2,3，j=1,2,3。综上所述，该问题的线性规划模型如下：线性规划线性规划 为了应用 Matlab 求解上述线性规划问题，将上述模型改写成 Matlab 适用的模型，其形式为：线性规划线性规划 最后解得：总费用为：8.01105。x11=206.7722x13=75x22=0 x31=69.1646x33=0 x12=318.2278x21=0 x23=150 x32=90.8354线性规划