第五章线性规划 ☒ 线性规划模型 ☑ 线性规划的图解 单纯形法原理 单纯形法 单纯形表 单纯形的理论分析 D人工变量法
1 第五章 线性规划 线性规划模型 线性规划的图解 单纯形法原理 单纯形法 单纯形表 单纯形的理论分析 人工变量法
§5.1孩性规划的数学摸型 一、问题的提出 例1：生产计划问题： 设备 A B C 利润 产 (元/公斤) 甲 3 5 9 70 乙 9 5 3 30 限制工时 540 450 720 间：甲乙各生产多少，使企业利阀最大？ 2
2 §5.1 线性规划的数学模型 一、问题的提出 例1：生产计划问题： 问：甲乙各生产多少，使企业利润最大？ 设备 产品 A B C 利润 (元/公斤) 甲 3 5 9 70 乙 9 5 3 30 限制工时 540 450 720
设备 A C 利润 产 B (元/公斤) 甲 3 5 9 70 乙 9 5 3 30 限制工时 540 450 720 解：设产品甲、乙各生产x1,x2公斤 设总利润为Z,则：maxZ=70x1+30x2 3x1+9x2≤540 5x+5x2≤450 资源约束 s.t 9x,+3x2≤720 X1,x2≥0 ----变量非负约束3
3 解:设产品甲、乙各生产x1， x2公斤 max 70 30 Z x x = +1 2 1 2 1 2 1 2 1 2 3 9 540 5 5 450 . 9 3 720 , 0 x x x x s t x x x x + + + 设总利润为Z，则： 设备 产品 A B C 利润 (元/公斤) 甲 3 5 9 70 乙 9 5 3 30 限制工时 540 450 720 资源约束 变量非负约束
线性规划模型的一般特点 1 决策变量：向量(X…X)T 行动方案 2、 目标函数：Z=f(X1…X)线性式 一一一一一+明确的目标要求，极大或极小 3、 约束条件：线性等式或不等式 反映了客观限制条件。 线性规划模型的一般形式： C为价值集数 Max(Min)zcXj+c2X2+......+cnXn a1X1+a12X2+..+a1nx≥(=或≤)b1 a2X+a22x2+..+a2mX≥(=或≤)b2 约束方程 s.t. amlX+am2X2+..+ammX.≥(=或≤)bm Xj=1,n)≥()0， 或者没有限制 变量约束
4 二、线性规划模型的一般特点 Max(Min) z=c1 x1+c2 x2+……+cn xn a11x1+a12x2+……+a1n xn ≥(=或≤)b1 a21x1+a22x2+……+a2n xn ≥(=或≤)b2 …… am1 x1+am2 x2+……+amnxn ≥(=或≤)bm xj (j=1,…,n) ≥(≤) 0，或者没有限制 s.t. cj为价值系数 反映了客观限制条件。 明确的目标要求，极大或极小 行动方案 线性规划模型的一般形式： 1、决策变量：向量(x1…xn ) T 2、目标函数：Z=ƒ(x1… xn )线性式， 3、约束条件：线性等式或不等式 变量约束 约束方程
三、常用的线性规划模型 例2：资源合理利用问题： 某厂生产A、B两种产品，都需用煤、金属材料、电力等资 源，各产品对三种资源的消耗及可供利用的资源如表2示： 表2： 资源 煤（吨） 金属材料 电力 产品利润 产品 (公斤) (千瓦) (元吨) A 6 80 50 6000 B 8 50 10 5000 资源供应量 540 4000 2000 间：寇品何安排生产，使企业获利最大？
5 资源 产品 煤（吨） 金属材料 （公斤） 电力 （千瓦） 产品利润 （元/吨） A 6 80 50 6000 B 8 50 10 5000 资源供应量 540 4000 2000 表2： 例2：资源合理利用问题： 某厂生产A、B两种产品，都需用煤、金属材料、电力等资 源，各产品对三种资源的消耗及可供利用的资源如表2示： 问：应如何安排生产，使企业获利最大？ 三、常用的线性规划模型
解：设产品A、B产量分别为变量x1,x2(吨)，则： max Z=6x1 +5x2 6x1+8x2≤540 80x1+50x2≤4000 s.t 50x1+10x2≤2000 x1,X2≥0 资源 煤（吨） 金属材料 电力 产品利润 产品 (公斤) (千瓦) (元吨) A 6 80 50 6000 B 8 50 10 5000 资源供应量 540 4000 2000
6 解：设产品A、B产量分别为变量x1 ， x2（吨），则： + + + = + , 0 50 10 2000 80 50 4000 6 8 540 . max 6 5 1 2 1 2 1 2 1 2 1 2 x x x x x x x x st Z x x 资源 产品 煤（吨） 金属材料 （公斤） 电力 （千瓦） 产品利润 （元/吨） A 6 80 50 6000 B 8 50 10 5000 资源供应量 540 4000 2000
例3、合理下料问题： 有一批长度为180厘米的钢管，需截成70、52和35厘米3 种管料。它们的需求量分别不少于100、150和100根。问如 何下料才能使钢管的消耗量为最少？ 先找出各种可能的下料方式： (再在各种可能的下料方案中去 选择) 设在180厘米长的钢管上能下出u个70厘米管料，v个52厘米 管料，w个35厘米，则满足约束条件： 70u+52v+35w≤180，其中，u,V,w只能是正整数。 从最大尺寸管料下起：
7 例3、合理下料问题： 有一批长度为180厘米的钢管，需截成70、52和35厘米3 种管料。它们的需求量分别不少于100、150和100根。问如 何下料才能使钢管的消耗量为最少？ 先找出各种可能的下料方式：（再在各种可能的下料方案中去 选择） 设在180厘米长的钢管上能下出u个70厘米管料，v个52厘米 管料， w个35厘米，则满足约束条件： 70u+52v+35w≤180，其中，u，v，w只能是正整数。 从最大尺寸管料下起：
各种可能的下料方案： I II III IV V VI VII VIII 70 2 1 1 1 0 0 0 0 52 0 2 1 0 3 2 1 0 35 1 0 1 3 0 2 3 5 合计 175 174 157 175 156 174 157 175 余料 5 6 23 5 24 6 23 5 8
8 I II III IV V VI VII VIII 70 2 1 1 1 0 0 0 0 52 0 2 1 0 3 2 1 0 35 1 0 1 3 0 2 3 5 合计 175 174 157 175 156 174 157 175 余料 5 6 23 5 24 6 23 5 各种可能的下料方案：
解：设按第种方素下料的原材料为根 min Z=5.x1+6x2十23x3+5x4+24x5+6x6+23x7+5x8 2x1+X2+比3t比4 ≥100 2x2+x3+ 3x5+2x6+比7 ≥150 ×1 +比3+3x4+ x6+3x7+5x≥100 x,≥0（位=1,8），且为整数
9 2x1 + x2 +x3+x4 ≥100 2x2 +x3+ 3x5+2x6+x7 ≥150 x1 +x3+3x4+ x6+3x7+5x8≥100 xi 0 (i =1,…,8)，且为整数 min Z= 5x1 + 6x2＋23x3+5x4+24x5+6x6+23x7+5x8 解：设按第j种方案下料的原材料为xj根
例4：运输问题 治炼厂 B B2 B, Ba 总产量 矿山 A 1.5 2 0.3 3 100 A2 7 0.8 1.4 2 80 A3 1.2 0.3 2 2.5 50 总需求量 50 70 80 30 230 问：如何安排运输，使运输费用最小？ 10
10 例4：运输问题 问：如何安排运输，使运输费用最小？ 冶炼厂 矿山 B1 B2 B3 B4 总产量 A1 1.5 2 0.3 3 100 A2 7 0.8 1.4 2 80 A3 1.2 0.3 2 2.5 50 总需求量 50 70 80 30 230