第五章 线性规划

《第五章 线性规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章线性规划线性规划模型线性规划的图解单纯形法原理单纯形法单纯形表单纯形的理论分析人工变量法1§5.1线性规划的数学模型一、问题的提出例1：生产计划问题：问：甲乙各生产多少，使企业利润最大？设备产品ABC利润(元/公斤)甲35970乙95330限制工时5404507202解:设产品甲、乙各生产x1，x2公斤设总利润为Z，则：设备产品ABC利润(元/公斤)甲35970乙95330限制工时540450720资源约束变量非负约束3二、线性规划模型的一般特点Max(Min)z=c1x1+c2x2+……+cnxna11x1+a12x2+……+a1nxn≥(=或≤)b1a21x1+a22x2

2、+……+a2nxn≥(=或≤)b2……am1x1+am2x2+……+amnxn≥(=或≤)bmxj(j=1,…,n)≥(≤)0，或者没有限制s.t.cj为价值系数反映了客观限制条件。明确的目标要求，极大或极小行动方案线性规划模型的一般形式：1、决策变量：向量(x1…xn)T2、目标函数：Z=ƒ(x1…xn)线性式，3、约束条件：线性等式或不等式变量约束约束方程4资源产品煤（吨）金属材料（公斤）电力（千瓦）产品利润（元/吨）A680506000B850105000资源供应量54040002000表2：例2：资源合理利用问题：某厂生产A、B两种产品，都需用煤、金属材料、电力等资源，各产

3、品对三种资源的消耗及可供利用的资源如表2示：问：应如何安排生产，使企业获利最大？三、常用的线性规划模型5解：设产品A、B产量分别为变量x1，x2（吨），则：资源产品煤（吨）金属材料（公斤）电力（千瓦）产品利润（元/吨）A680506000B850105000资源供应量540400020006例3、合理下料问题：有一批长度为180厘米的钢管，需截成70、52和35厘米3种管料。它们的需求量分别不少于100、150和100根。问如何下料才能使钢管的消耗量为最少？先找出各种可能的下料方式：（再在各种可能的下料方案中去选择）设在180厘米长的钢管上能下出u个70厘米管料，v个52厘米管料，

4、w个35厘米，则满足约束条件：70u+52v+35w≤180，其中，u，v，w只能是正整数。从最大尺寸管料下起：7IIIIIIIVVVIVIIVIII702111000052021032103510130235合计175174157175156174157175余料56235246235各种可能的下料方案：82x1+x2+x3+x4≥1002x2+x3+3x5+2x6+x7≥150x1+x3+3x4+x6+3x7+5x8≥100xi0(i=1,…,8)，且为整数minZ=5x1+6x2＋23x3+5x4+24x5+6x6+23x7+5x8解：设按第j种方案下料的原材料为xj根9例

5、4：运输问题问：如何安排运输，使运输费用最小？冶炼厂矿山B1B2B3B4总产量A11.520.33100A270.81.4280A31.20.322.550总需求量5070803023010解：设xij为第i个矿山运到第j个冶炼厂的矿石量MinZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34(万元)x11+x12+x13+x14=100x21+x22+x23+x24=80x31+x32+x33+x34=50x11+x21+x31=50x12+x22+x32=70x13+x23+x3

6、3=80x14+x24+x34=30xij≥0(i=1,2,3。　j=1,2,3,4)第i个矿山的产量第j个冶炼厂的需求量11方案序号技改方案内容决策变量投资（万元）年收益(万元)第一年第二年1更新旧装置，提高炼油能力500桶/天x12001001002建造新装置，提高炼油能力1000桶/天x23001502003往新厂建输油管，提高炼油能力100桶/天x315050504往老厂建输油管，提高炼油能力50桶/天x410070305增加槽车运输能力，能提高出油20桶/天x5504020例5：投资方案选择问题（0－1规划）12又要求：方案1和2只能选择其中一种，不能兼而实现，并且，选择

7、方案2，则方案3必须与2同时选择，或者都不选择。现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。要求技改后，至少增加出油能力500桶/天，但又不得超过1100桶/天，确定该公司总经济效益最大的投资方案。解：1）确定决策变量：方案的选择只有两种状态，选或不选，设xj（j=1,…,5）为第j方案的取舍，有：2）目标函数：maxZ=100x1+200x2+50x3+30x4+20x513200x1+300x2+150x3+100x4+50x5≤650