第1章 线性规划.ppt

《第1章 线性规划.ppt》由会员分享，可在线阅读，更多相关《第1章 线性规划.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 线性规划1.1 原始问题1.2 对偶问题1.3 敏感分析1.4 模型讨论数学规划（mathematical programming）是运筹学的一个主要分支，它是研究在一些给定的条件下（即约束条件下），求的考察函数（即目标函数）在某种意义下的极值（极小或极大）。对于数学规划，我们研究其中应用最为广泛的线性规划问题线性规划的基本特点：是运筹学中应用最广泛的方法之一网络分析、整数规划、目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大研究对象：有一定的人力、财力、资源条件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，

2、使之最省典型应用合理利用线材问题：如何下料使用材最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调动方案，使总运费最小为什么要使用线性规划？线性规划很容易且有效率地被求解如果存在最优解，则肯定能够找到功能强大的敏感性分析许多实际问题本质上是线性的1.1 原始问题例1.1（产品组合问题）某公司现有三条生产线来生某公司现有三条生产线来生产两种新产品，其主要数据如表产两种新产品，其主要数据如表1.11.1所示。请问如何所示。请问如何生产可以让

3、公司每周利润最大？生产可以让公司每周利润最大？表1.1 产品组合问题的数据表生产线生产单位产品所需时间生产线每周可用时间产品甲产品乙一104二0212三3218单位产品的利润35此问题是在生产线可利用时间受到限制的情形下寻求每周利润最大化的产品组合问题。在建立产品组合模型的过程中，以下问题需要得到回答：（1）要做出什么决策？（2）做出的决策会有哪些条件限制？（3）这些决策的全部评价标准是什么？（1）变量的确定要做出的决策是两种新产品的生产水平，记x1为每周生产产品甲的产量，x2为每周生产产品乙的产量。一般情况下，在实际问题中常常称为变量（决策变量）（2）约束条件求目标函数极值时的某些限制称为约

4、束条件。如两种产品在相应生产线上每周生产时间不能超过每条生产线的可得时间，对于生产线一，有x14，类似地，其它生产线也有不等式约束（3）目标函数对这些决策的评价标准是这两种产品的总利润，即目标函数是要求每周的生产利润（可记为z，以百元为计量单位）为最大这样，可以把产品组合问题抽象地归结为一个数学模型：max z=3x1+5x2 s.t.x1 4 2x2 12 3x1+2x2 18 x1 0，x2 0其中，max是最大化（maximize）的英文简称，s.t.是受约束于（subject to）的简称。上面数学模型中的决策变量为可控的连续变量，目标函数和约束条件都是线性的，称为线性规划（linea

5、r programming）问题，是最基本的数学规划问题。线性规划问题隐藏了如下假定：比例性假定：意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数可加性假定：每个决策变量对目标函数和约束条件的影响是独立于其它变量的，目标函数值是每个决策变量对目标函数贡献的总和连续性假定：决策变量应取连续值确定性假定：所有参数都是确定的，不包含不确定因素上述隐含的假定条件是很强的。因此在使用线性规划时必须注意问题在什么程度上满足这些假定。当不满足的程度较大时，应考虑使用其它方法。如：整数规划(integer programming，简记为IP)模糊线性规划(fuzzy linear pro

6、gramming)非线性规划(nonlinear programming，简记为NP或NLP)组合优化(combinatorial optimization)参数规划(parametric programming)多目标规划(multi-objective programming)随机规划(stochastic programming)下面我们把例1.1推广为一般产品组合问题。设有m种资源用于生产n种不同产品，各种资源的拥有量分别为bi（i=1,2,m）。又生产单位第j种产品（j=1,2,n）时将消费第i种资源aij单位，利润为cj元。表1.2给出线性规划模型所需的数据。表1.2 线性规划模型

7、所需数据资源单位活动对资源的使用量资源可利用量12n1a11a12a1nb12a21a22a2nb2mam1am2amnbm单位活动对z的贡献c1c1cn仍用xj（j=1,2,n）代表第j种产品的生产数量，则线性规划模型为 max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm x1，x2，xn 0其中，目标函数可以为min的形式，函数约束中“”可以为“”或“”，变量的非负性限制也可以取消。以上模型可简写为：用向量形式表达时，上述模型可简写为：其中，c=(c1,c2,cn)，x=(x

8、1,x2,xn)T，pj=(a1j,a2j,amj)T，b=(b1,b2,bm)T.用矩阵形式表达时，上述模型可简写为：max z=cxs.t.Ax b x 0其中，c=(c1,c2,cn)，x=(x1,x2,xn)T，b=(b1,b2,bm)T，A=(aij)mn被称为约束方程组的（消耗）系数矩阵.在求解例1.1之前，先复习并引入一些基本概念（1）决策变量（2）目标函数，目标函数值（3）约束条件：非负约束与函数约束（4）参数：模型的参数是数学模型中的常数（5）解：决策变量的任何一个取值称为模型的解（6）满足所有约束条件的解称为可行解。反之，一个非可行解至少违反一个约束条件。全部可行解的集合称

9、为可行域（7）使目标函数达到最大值的可行解称为最优解，该目标函数值称为最优值。下面用图解法求解例1.1图1.1 产品组合问题(0,9)(0,6)(6,0)(4,0)(2,6)(4,3)(4,6)可行域z=3x1+5x2x2x1(0,0)x1=03x1+2x2=18x1=42x2=12x2=0思考，此最优解是唯一的吗？在一般情况下，解的情况还可能出现下列几种：（1）无穷多最优解（2）无界解（3）无可行解无穷最优解(0,9)(0,6)(6,0)(4,0)(2,6)(4,3)(4,6)可行域x2x1(0,0)x1=03x1+2x2=18x1=42x2=12x2=0z=3x1+2x2无界解可行域x2x

10、1(0,0)x1=0 x1=4x2=0(4,0)z=3x1+5x2无可行解(0,9)(0,6)(6,0)(4,0)(2,6)(4,3)(4,6)x2x1(0,0)x1=03x1+2x2=18x1=42x2=12x2=03x1+5x2=50若线性规划问题的决策变量超过2个时，应用图解法求解时便会显得很困难。这里需要解决线性规划问题的更一般的代数的方法单纯形法。单纯形法可以解决成千上万个变量或约束条件的线性规划问题。在使用单纯形法解决问题中，必须对线性规划的一般形式进行变形，化为标准形式。线性规划的标准形式：目标函数取极大化，约束条件全为等式，约束条件右端常数项均为非负值，变量取值为非负。对于非标

11、准形式的线性规划问题，可通过下列方法化为标准形式：（1）目标函数求极小值。即min z=cjxj，令z=-z即可。（2）约束条件为不等式。当为“”时，如x14时，可添加x30，使得x1+x3=4；当为“”时，如6x1+4x29，可添加x40，使得6x1+4x2-x4=9。这里x3和x4是新加上去的变量，取值均为非负，加到原约束条件中去的目的是使不等式转化为等式。其中，x3称为松弛变量，x4一般称为剩余变量，其实质与x3相同，故也有统称为松弛变量的。松弛变量或剩余变量在目标函数中的系数均为零。（3）变量xj0。令xj=-xj 即可。（4）取值无约束的变量x。令x=x-x，其中x0，x0。例：将以

12、下线性规划问题转化为标准形式 min f=-3 x1+5 x2+8 x3 -7 x4s.t.2 x1 -3 x2+5 x3+6 x4 28 4 x1+2 x2+3 x3-9 x4 39 6 x2+2 x3+3 x4 -58 x1,x3 ,x4 0解：首先，将目标函数转换成极大化：令 z=f=3x15x28x3+7x4；其次考虑约束，有3个不等式约束，引进松弛变量x5,x6,x7 0；由 于 x2无 非 负 限 制，可 令 x2=x2-x2,其 中x20，x20；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：max z=3x15x2+5x

13、28x3+7x4 s.t.2x13x2+3x2+5x3+6x4+x5=28 4x1+2x2-2x2+3x3-9x4-x6=39 -6x2+6x2-2x3-3x4-x7=58 x1,x2,x2,x3,x4,x5,x6,x7 0练习：把例1.1中的模型化成标准形式 max z=3x1+5x2 s.t.x1 4 2x2 12 3x1+2x2 18 x1 0，x2 0解：标准形式为：max z=3x1+5x2+0 x3+0 x4+0 x5 s.t.x1 +x3 =4 2x2 +x4 =12 3x1+2x2 +x5=18 x1，x2，x3，x4，x5 0需要指出的是：线性规划问题的标准形式与其原始形式是

14、等价的，即一个线性规划问题的最优解与其标准形式的最优解的值是一样的。一个问题的标准形式并不改变问题的本质，它只是改变对问题约束条件的写法。我们已经说过，单纯形法需要标准形式。但对于单纯形法，我们不做深入探讨，这里只给出几个必要的基本概念。在例1.1的标准形式中，有3个等式约束，5个未知变量。根据线性代数知识可知，有2个变量是自由变量。例如，根据约束方程组的系数矩阵可知矩阵A的秩不大于3,而是一个33的满秩矩阵，故(p3,p4,p5)是一个基，对应的变量x3,x4,x5是基变量，x1,x2是非基变量。令非基变量x1x20，解得x34，x412，x518，则x(0,0,4,12,18)T是一个基解

15、。因该基解中所有变量取值为非负，满足线性规划问题的所有约束条件，故也是基可行解。1.2 对偶问题例1.3（委托加工）对于例对于例1.11.1的产品组合问的产品组合问题，公司从交易市场上得到另一信息：某中题，公司从交易市场上得到另一信息：某中间商得到一笔生产与公司相同产品的合同。间商得到一笔生产与公司相同产品的合同。但该中间商并没有生产这些产品的设备，欲但该中间商并没有生产这些产品的设备，欲委托该公司为其加工产品。现在的问题是公委托该公司为其加工产品。现在的问题是公司应该让中间商至少付出多少代价，才能放司应该让中间商至少付出多少代价，才能放弃这两种新产品的生产，为中间商委托生产弃这两种新产品的生

16、产，为中间商委托生产？公司放弃自己组织生产活动的条件是：对同等数量资源出让的代价应不低于该公司自己组织生产活动时的利润。这时，应该把公司的三条生产线的可用时间作为三类资源，用yi代表收买该公司一单位i种资源时付给的代价，则总收买价为w=4y1+12y2+18y3该公司出让相当于生产一单位第j种产品的资源消耗的价值应不低于第j种产品的单位利润价值cj元，有 y1 +3y33 2y2+2y35中间商的目标是用最小的代价把公司的资源收买过来，于是可得模型min w=4y1+12y2+18y3 s.t.y1 +3y33 2y2+2y35 y10,y20,y30对比原问题与对偶问题 z=3x1+5x2

17、w=4y1+12y2+18y3 s.t.s.t.x1 4 y1 +3y3 3 2x2 12 2y2+2y3 5 3x1+2x2 18 y10,y20,y30 x1 0，x2 0 原问题 对偶问题2个函数约束3个函数约束maxmin2个变量3个变量对于线性规划的一般模型，有如下表格关系表1.4 线性规划原问题与对偶问题的比较表中右上角是原问题，左下角部分旋转90就是对偶问题。原问题（求极大）c1c2cn右边x1x2xn对偶问题（求极小）b1y1a11a12a1nb1b2y2a21a22a2nb2bmymam1am2amnbm右边c1c2cn例：写出原问题的对偶问题 max z=1500 x1+2

18、500 x2 s.t.3x1+2x2 65 2x1+x2 40 3x2 75 x1,x2 0对偶问题为 min f=65y1+40y2+75y3 s.t.3y1+2y2 1500 2y1+y2+3y3 2500 y1,y2,y3 0我们有时把“max，”（或“min，”）的形式称为对称形式。对于求更一般形式（有时也称为非对称形式）的原问题的对偶问题，可以按照下面的对应关系直接给出其对偶规划，也可参见课本P23表1.5。（1）将模型统一为“max，”或“min，”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变

19、量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。例 写出下面线性规划的对偶规划模型解：先将约束条件变形为“”形式再根据非对称形式的对应关系，直接写出对偶规划需要指出，当我们讨论对偶问题时，它必定是与原问题成对出现的，它们互为对偶，一个是原问题，则另一个就为对偶问题。关于对偶问题，我们给出一个结论：对偶问题的对偶是原问题。对偶问题的经济解释从对偶问题可以看出，bi是线性规划原问题约束条件的右边项，表示第i各资源的可用量。在对偶问题目标函数中，将w对bi求偏导数得w/bi=yi，说明yi的值相当于在给定生产条件下，bi每增加一个单位时目标函

20、数w的增量。yi的意义是：在当前基解中对一个单位的第i种资源的估价（或对目标函数的利润贡献）。这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价，为区别起见，称为影子价格（shadow price），也称为对偶价格（dual price）。资源的市场价格是已知数，相对比较稳定，而其影子价格则有赖于资源的利用情况，是未知数。系统内部资源数量和价格的任何变化都会引起影子价格的变化，即公司生产任务、产品结构等情况一旦发生变化，资源的影子价格一般也会随之改变。从这种意义上讲，影子价格是一种动态价格。从另一个角度讲，资源的影子价格实际上又是一种机会成本。一般地，线性规划问题的求解是确定

21、资源的最优分配方案；对偶问题的求解是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。例如，在公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。从宏观调控层面看，对于一些紧缺资源，可借助于价格机制规定使用一单位这种资源时必须上交的利润额，以控制一些经济效益低的公司自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。又如，如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。1.3 敏感分析影子价格的经济含义，是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范

22、围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题就是灵敏度分析要讨论的。一般地，灵敏度分析（敏感分析）就是研究当一个线性规划问题中的参数变化时，对最优解的影响程度，包括目标函数参数和约束条件右边参数的变化分析。灵敏度分析有以下几个明显的作用：（1）线性规划模型的许多参数在建模时是很难精确确定的，只能是对一些数据的估计（如单位利润）。通过灵敏度分析可以表明，参数估计值必须精确到怎样的程度，才能避免得出错误的最优解，而且可以找出哪些参数是需要重新精确定义的灵敏度参数。（2）若在研究结束后，问题条件发生变化，通过灵敏度分析，即使不求解，也可以表明参数变化是否改变最优解。（3）当

23、模型特定的参数反映管理决策时，灵敏度分析可以表明改变这些决策对结果的影响，从而有效指导管理者做出最终决策。在一些情形下，灵敏度分析会进一步给管理部门提供更有帮助的指导，如分析问题环境朝不同的方向发展会产生的结果等。灵敏度分析有以下几个内容：当资源可用量发生变化，即右边系统变化而其它系统都不变时原问题的解的变化情况当产品单位利润发生变化，即目标函数系数而其它系数都不变时原问题的解的变化情况当产品单位利润与资源可用量同时发生变化时，即多系数同时变化时原问题的解的变化情况当系数系统性变化时，如约束条件右边某一资源连续变化时对原问题的解的影响（参数规划）下面仅针对上面三类作进行软件实现分析。用LIND

24、O求解产品组合模型时，点击打靶图样的按钮，在对话框 Do Rerange(Sensitivity)Analysis的问题选择Yes，则有下面的结果 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)36.00000 VARIABLE VALUE REDUCED COST X1 2.000000 0.000000 X2 6.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)2.000000 0.000000 3)0.000000 1.500000 4)0.000000 1.000000

25、NO.ITERATIONS=2表示单纯形法在2次迭代（旋转）后得到最优解表示最优值给出最优解中各变量的值给出松驰变量的值:第3、4 行松驰变量均为0,说明对于最优解来讲，两个约束（第3、4 行）均取等号对偶价格,表示当对应约束有微小变动时 目标函数的变化率.输出结果中对应于每一个约束有一个对偶价格 若其数值为p,表示对应约束中不等式右端项若增加1个单位,目标函数将增加p个单位（max 型问题）。表示用单纯形法进行了两次迭代缩减成本，表示当变量有微小变动时,目标函数的变化率.其中基变量的reduced cost值应为0，对于非基变量xj,相应的reduced cost值表示当某个变量xj增加一个

26、单位时目标函数减少的量(max型问题)，即该产品不值得生产。若要使该产品进入生产，则应提高该产品的单位利润。由于产品价格主要由市场决定，企业应主要从内部降低产品成本着手，即该产品单位成本应该减少的最少量为xj RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 3.000000 4.500000 3.000000 X2 5.000000 INFINITY 3.000000 RIGHTHAND SID

27、E RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 4.000000 INFINITY 2.000000 3 12.000000 6.000000 6.000000 4 18.000000 6.000000 6.000000灵敏度分析:系统报告当目标函数的系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基保持不变。目标函数中x1的变量系数为3，当它在3-3,3+4.5=0,7.5 变化时，最优基保持不变。当它在12-6,12+66,18范围变化时，最优基保持不变。演示教材P27例1.6 以上我们应用

28、LINDO软件对一个线性规划问题进行了完整的分析。需要指出的是，LINDO默认变量约束是非负的，其它非标准变量在“end”后面要加上变量说明，常用 的有free 变量名!变量可以取任何数值gin 变量名!一个非负的整数值Int 变量名!0-1变量数值slb 变量名 数值!变量的一个下界sub 变量名 数值!变量的一个上界1.4 模型讨论以下讨论是对所有规划模型都适用1.4.1 单一模型（1）规定目标函数单目标多目标（2）约束条件的规定生产能力约束条件。如某一生产工序中所用资源供应的限制，比如加工能力或劳力等原材料可获量。如某项活动（如产品的生产）用原材料的供应受到限制销售需要量和限额 xu，x

29、l材料平衡约束条件 xj-xk=0品质条件 食品中营养物的含量、石油的辛烷值、材料的强度等硬/软约束条件矛盾约束条件 目标规划模型多余约束条件简单界和广义上界非常约束条件 如整数规划模型中讨论的限制条件，需要建立整数变量建立模型1.4.2 组合模型例1.10（多工厂模型）一家公司有一家公司有A和和B两个工厂。两个工厂。每个工厂生产两种同样的产品，一种是普通的，一每个工厂生产两种同样的产品，一种是普通的，一种是精制的。普通产品每件可盈利种是精制的。普通产品每件可盈利10元，精制产品元，精制产品每件可盈利每件可盈利15元。两个厂采用相同的加工工艺元。两个厂采用相同的加工工艺研磨和抛光来生产这些产品

30、。研磨和抛光来生产这些产品。A厂每周的研磨能力厂每周的研磨能力为为80小时，抛光能力为小时，抛光能力为60小时。小时。B厂每周的研磨能厂每周的研磨能力为力为60小时，抛光能力为小时，抛光能力为75小时。两厂生产各类单小时。两厂生产各类单位产品所需的研磨和抛光工时（以小时计）如表位产品所需的研磨和抛光工时（以小时计）如表1.7所示。另外，每类每件产品都消耗所示。另外，每类每件产品都消耗4公斤原材料，该公斤原材料，该公司每周可获得原材料公司每周可获得原材料120公斤。问：应该如何制定公斤。问：应该如何制定生产计划？生产计划？工厂AB产品普通精制普通精制研磨4253抛光2556表1.7 多工厂模型生

31、产数据 分析：先假定每周分配原材料给A厂75公斤，B厂45公斤。设x1为A厂的普通产品产量，x2为A厂的精制产品产量，x3为B厂的普通产品产量，x4为B厂的精制产品产量，则模型为 A厂模型 B厂模型 max z=10 x1+15x2max z=10 x3+15x4 s.t.s.t.4x1+4x2 75 4x3+4x4 45 4x1+2x2 80 5x3+3x4 60 2x1+5x2 60 5x3+6x4 75 x1 0，x2 0 x3 0，x4 0求解可知A厂模型的最优解为x1=11.25，x2=7.5，利润为225元，剩余20小时的研磨工时。B厂模型的最优解为x3=0，x4=11.25，利润

32、为168.75元，剩余26.25小时的研磨工时和7.5小时的抛光工时。假定建立一个整个公司的模型，让模型来确定原材料的分配，则公司模型为：max z=10 x1+15x2+10 x3+15x4 s.t.4x1+4x2+4x3+4x4 120 4x1+2x2 80 2x1+5x2 60 5x3+3x4 60 5x3+6x4 75 x1，x2，x3，x4 0求解公司模型的最优解为x1=9.17，x2=8.33，x3=0，x4=12.5，总利润为404.1667元，A厂和B厂分别有26.67和22.5小时的剩余研磨工时。把这个解与A，B两厂各自所得的解进行对比，可得到若干有价值的论据：（1）总利润达404.15元，大于A，B两厂各自获得的利润之和225168.75393.75元（2）在总利润中，A厂占216.5（以前是225元），B厂占187.5元（以前只有168.75元）（3）现在A厂消耗70公斤原材料，B厂消耗50公斤原材料此整个公司模型对于B厂的生产比以前更重视。即把50公斤而不是过去的45公斤原料分配为B厂，同时把A厂的供应减少5公斤。若在建立此公司模型之前已能决定按70：50的比例分配原料，那就没有必要建立公司模型了。