第二章线性规划与单纯形法 +2.1 LP(linear programming) 的基本概念 LP是在有限资源的条件下,合理分配和 利用资源,以期取得最佳的经济效益的优 化方法 LP有一组有待决策的变量, 个线性的目标函数, 组线性的约束条件 ORI
OR1 1 第二章 线性规划与单纯形法 2.1 LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和 利用资源，以期取得最佳的经济效益的优 化方法。 LP有一组有待决策的变量， 一个线性的目标函数， 一组线性的约束条件
2.1.1LP的数学模型 例题1—生产计划问题 ◆某厂生产两种产品,需要三种资源,已知 各产品的利润、各资源的限量和各产品的 资源消耗系数如下表: 口口 A 口口 B资源限量 劳动力9 45 360 设备4 200 原材料3 10 300 利润元g70 120 ORI
OR1 2 2.1.1 LP的数学模型 例题1—生产计划问题 某厂生产两种产品，需要三种资源，已知 各产品的利润、各资源的限量和各产品的 资源消耗系数如下表： 产品A 产品B 资源限量 劳动力 设 备 原材料 9 4 3 4 5 10 360 200 300 利润元/kg 70 120
例题1建模 问题:如何安排生产计划,使得获利最多? 步骤: 1、确定决策变量:设生产A产品Ⅹkg,B产品Ⅹzkg 2、确定目标函数:maxZ=70X1+120X2 3、确定约東条件:人力约束9X1+4X20X2≥0 ORI 3
OR1 3 例题1建模 问题：如何安排生产计划，使得获利最多？ 步骤： 1、确定决策变量：设生产A产品x1kg,B产品x2kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件：人力约束 9X1+4X2≤360 设备约束 4X1+5X2 ≤200 原材料约束3X1+10X2 ≤300 非负性约束X1≥0 X2≥0
例题2配方问题 ◆养海狸鼠饲料中营养要求:VA每天至少700克,VB每天 至少30克,Vc每天刚好200克。现有五种饲料,搭配使 用,饲料成分如下表: 饲料 Va Vc价格元/KG 0.5 0.5 0.202 27495 0.50.8 营养要求70030200 ORI
OR1 4 例题2——配方问题 养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天 至少30克，VC每天刚好200克。现有五种饲料，搭配使 用，饲料成分如下表： 饲料 Va Vb Vc 价格元/KG I II III IV V 3 2 1 6 18 1 0.5 0.2 2 0.5 0.5 1 0.2 2 0.8 2 7 4 9 5 营养要求 700 30 200
例题2建模 ◆设抓取饲料IXkg;饲料Ⅱⅹkg;饲料Ⅲxkg ◆目标函数:最省钱minZ=2x1+7x2+4x+9X4+5X5 ◆约束条件:3x2+2x2+x3+6x4+18x≥700 营养要求:x1+0.5x2+02x3+2x4+0.5X5≥30 0.5X1+X2+0.2x3+2x4+0.8X5=200 用量要求:x1<50,x2<60,x3<50,x4<70,x5<40 非负性要求:x1≥0,x2≥0,x3≥0.x4≥0,x5≥0 ORI 5
OR1 5 例题2建模 设抓取饲料I x1kg;饲料II x2kg;饲料III x3kg…… 目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5 约束条件：3x2+2x2+x3+6x4+18x5 ≥700 营养要求： x1+0.5x2+0.2x3+2x4+0.5x5 ≥30 0.5x1+x2+0.2x3+2x4+0.8x5 =200 用量要求： x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40 非负性要求：x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0
例题3:人员安排问题 医院护士24小时值班,每次值班8小时 不同时段需要的护士人数不等。据统计: 序号 时段 最少人数安排人数 061060 10-1470 234 141860 18-22 52 00 XXXX 2345 2202 02-0630 X6 ORI
OR1 6 例题3：人员安排问题 医院护士24小时值班，每次值班8小时。 不同时段需要的护士人数不等。据统计： 序号 时段 最少人数 安排人数 1 06—10 60 X1 2 10—14 70 X2 3 14—18 60 X3 4 18—22 50 X4 5 22—02 20 X5 6 02—06 30 x6
例题3建模 目标函数:minZ=x+x2+x3+x4+x+x6 ◆约東条件:x1+x2>70 X2+X3>60 x3+x4≥50 X4+X5>20 X5+X6>30 非负性约束:x>0j=1,2,.6 ORI
OR1 7 例题3建模 目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 ≥70 x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非负性约束：xj ≥0,j=1,2,…6
归纳:线性规划的一般模式 ◆目标函数:max(min)Z=cx+cxtc3x+.+cxn ◆约束条件:ax+ax2+a3x+.+axn(=2)b a21X1+a22X2ta23X3+.. +a2nXn )b2 amlXitam2X2tam3X3.. tamnXn )bn 非负性约束:x1≥0,x2≥0,,xn≥0 ORI
OR1 8 归纳：线性规划的一般模式 目标函数：max(min)Z=c1x1+c2x2+c3x3+…+cnxn 约束条件：a11x1+a12x2+a13x3+…+a1nxn ≤(= ≥)b1 a21x1+a22x2+a23x3+…+a2nxn ≤(= ≥)b2 … … … … am1x1+am2x2+am3x3+…+amnxn ≤(= ≥)bn 非负性约束：x1 ≥0,x2 ≥0,…,xn ≥0
2.1.2线性规划图解法 ◆由中学知识可知:y=ax+b是一条直线,同 理:Z=70x1+120x2→x2=70/120X1-Z/120也 是一条直线,以Z为参数的一族等值线。 9x1+4x2<360→X1<360/94/9x2 是直线x1=360/94/9X2下方的半平面 所有半平面的交集称之为可行域,可行域 内的任意一点,就是满足所有约束条件的 解,称之为可行解。 ORI
OR1 9 2.1.2线性规划图解法 由中学知识可知：y=ax+b是一条直线，同 理：Z=70x1+120x2→x2=70/120x1-Z/120也 是一条直线，以Z为参数的一族等值线。 9x1+4x2 ≤360 → x1 ≤360/9-4/9x2 是直线 x1=360/9-4/9x2 下方的半平面。 所有半平面的交集称之为可行域，可行域 内的任意一点，就是满足所有约束条件的 解，称之为可行解
例1图示 X2 90+A 80 9X1+4X2<360 4X1+5X2<200 40B ∠=70x1+120X2 20 3X1+10X2<300 X1 20 4060 80100 ORI
OR1 10 例1图示 . 90 80 60 40 20 0 20 40 60 80 100 x1 x2 9x1+4x2 ≤ 360 4x1+5x2 ≤200 3x1+10x2 ≤300 A B C D E F G H I Z=70x1+120x2