运筹学第一章线性规划及单纯形法

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

1、第一章线性规划及单纯形法目录线性规划介绍线性规划数学模型线性规划的图解法线性规划的单纯形法问题的提出在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优；或为了达到取其目标，确定使资源消耗最少的方案。问题的提出例1美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表1-1所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。例2、生产计划问题AB备用资源煤1230劳动日3260仓库0224利润4050x1+2x2

2、303x1+2x2602x224x1，x20maxZ=40x1+50x2解:设产品A,B产量分别为变量x1，x2问题的提出例3：捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资，已知各月所需仓库面积如表1-2。仓库租借费用随合同期限而定，合同期越长，折扣越大，具体见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。该厂可在任何一月办理租借合同，每次办理一份或若干份均可。为使租借费用最小，公司应如何选择签订合同的最优决策？月份1234所需仓库面积15102012合同租借期限1个月2个月3个月4个月合同期内的

3、租费2800450060007300例4求：最低成本的原料混合方案原料ABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)补充作业、运输问题从仓库到工厂运送单位原材料的成本，工厂对原材料的需求量，仓库目前库存分别如表所示，求成本最低的运输方案。工厂仓库123库存121350222430334

4、210需求401535设xij为i仓库运到j工厂的原棉数量(i＝1，2，3，j＝1，2，3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x1350x21+x22+x2330x31+x32+x3310x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij0一、线性规划模型特点决策变量：向量(x1…xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小线性规划介绍二、线性规划解决

5、的管理问题：合理利用线材问题；配料问题；投资问题；产品生产计划；劳动力安排；运输问题。线性规划介绍要求达到某些数量上的最大化或最小化；在一定的约束条件下追求其目标。三、线性规划问题的共同点：线性规划介绍线性规划的数学模型一、线性规划数学模型的一般形式二、线性规划数学模型的标准形式用数学语言描述目标函数约束条件解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。线性规划的一般式max(min)Z=C1x1+C2x2+…+Cnxna11x1+a12x2+…+a1nxn(=,)b1a21x1+a22x2+…+a2nxn(=,)b2……

6、…am1x1+am2x2+…+amnxn(=,)bmxj0(j=1,…,n)19简写为：用矩阵和向量形式表示：线性规划标准形式线性规划的标准形式目标函数：max约束条件：=变量符号：≥0（一）一般式（二）矩阵式（三）向量式返回线性规划标准型的几种表示法(一)一般型MaxZ=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn=b1a21X1+a22X2+…+a2nXn=b2…………am1X1+am2X2+…+amnXn=bmXj0(j=1,2,…,n)其中bi0(i=1,2,…,m)返回(二)矩阵型maxZ=CXAX

7、=bX0P1P2………Pna11a12………a1n其中A=a21a22………a2n…………………am1am2………amn…X1X=X2XnC=(C1C2…Cn)b1b=b2bm…返回(三)向量型X1AX=(P1P2…Pn)X2=bXn…P1X1+P2X2+…+PnXn=b返回(四)化标准型1.约束条件3.变量2.目标函数返回4.右端项系数1.约束条件x3为松弛变量x4为剩余变量松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。当约束条件为“≤”时，当约束条

8、件为“≥”时，例1maxZ=2X1+X2+0·X3+0·X4+0·X55x2156x1+2x224x1+x25xi0+X3=15+X4=24+