运筹学线性规划和单纯形法

《运筹学线性规划和单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学第一章线性规划及单纯形法LinearProgrammingandSimplexMethod1本章内容提要线性规划问题及其数学模型线性规划解的概念单纯形法原理及算法步骤线性规划应用——建模2如何合理地利用有限的人、财、物等资源，得到最好的经济效果?1.1问题的提出线性规划是以数学为工具，研究在一定的人、财、物等资源条件下，用最少的资源耗费，取得最大的经济效果。§1.线性规划问题及数学模型3例1.1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下

2、表所示：问题：工厂应如何安排生产可获得最大的总利润？产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）150025004解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1+2x2≤65；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1+x2≤40；5对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2≤7

3、5；另外，产品数不可能为负，即x1,x2≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：6目标函数maxz=1500x1+2500x2约束条件s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0这是一个典型的利润最大化的生产计划问题。其中，“max”是英文单词“maximize”的缩写，含义为“最大化”；“s.t.”是“su

4、bjectto”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。7营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？8各种食物的营养成分表9解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x430

5、0050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，x3，x4010线性规划数学模型的构成三要素决策变量表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施，用x1,x2,···,xn表示目标函数决策变量的函数，目标可以是最大化或最小化约束条件对决策变量取值的限制条件，由决策变量x1,x2,···,xn的不等式组或方程组构成11一般形式max(min)z=c1x1+c2x2+…+cnxnSubjecttoa11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a2

6、2x2+…+a2nxn≤(=,≥)b2...am1x1+am2x2+…+amnxn≤(=,≥)bmx1,x2,…,xn≥01213标准形式maxz=c1x1+c2x2+…+cnxnSubjecttoa11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmx1,x2,…,xn≥0其中bi≥0，i=1,2,…,m14标准形式15标准形式：用向量和矩阵表述16可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的

7、线性规划问题，我们总可以通过以下变换，将其转化为标准形式。171.极小化目标函数的问题：设目标函数为minf=c1x1+c2x2+…+cnxn则可以令z＝-f，该极小化问题与下面的极大化问题有相同的最优解，即maxz=-c1x1-c2x2-…-cnxn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即minf＝-maxz182、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的变量xn+1，使它等于约束右边与左边之差xn+1=bi–(ai1x1+ai2x2+…+ain

8、xn)显然，xn+1也具有非负约束(xn+1≥0)，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+xn+1=bi19当约束