2第二章线性规划图解法.pptVIP免费

11运筹学任课教师：徐咏梅博士教授80613111@qq.comOperationsResearch22第2章线性规划图解法33第第22章线性规划图解法章线性规划图解法2.12.1线性规划问题线性规划问题2.22.2图解法图解法2.32.3极点和最优解极点和最优解2.42.4计算机求解计算机求解2.52.5最小化问题最小化问题2.62.6特例特例442.12.1线性规划问题线性规划问题在一定的约束条件（限制条件）下，使得某一目标函数取得最大（或最小）值，当规划问题的目标函数与约束条件都是线性函数，便称为线性规划。Linearprogramming（LP）552.12.1线性规划问题线性规划问题产品A产品B资源限制劳动力设备原材料9434510360工时200台时300公斤单位产品利润（元）70120例1：某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：生产计划问题66问题：如何安排生产计划，使得获利最多？问题：如何安排生产计划，使得获利最多？步骤：步骤：11、确定决策变量：设生产、确定决策变量：设生产AA产品产品xx11kgkg,,BB产品产品xx22kgkg22、、确定目标函数：确定目标函数：maxZ=70XmaxZ=70X11+120X+120X2233、、确定约束条件：人力约束确定约束条件：人力约束99XX11+4X+4X22≤360≤360设备约束设备约束44XX11+5X+5X22≤200≤200原材料约束原材料约束33XX11+10X+10X22≤300≤300非负性约束非负性约束XX11≥0≥0XX22≥0≥077线性规划示意图线性规划示意图maxZ=70X1+120X29X1+4X2≤3604X1+5X2≤2003X1+10X2≤300X1≥0X2≥088标准袋高档袋资源限制切割印染缝合完成检查包装7/101/211/1015/62/31/4630小时600小时708小时135小时单位产品利润（美元）910例例22：高尔夫球袋：高尔夫球袋2.12.1线性规划问题线性规划问题992.12.1线性规划问题线性规划问题决策变量目标函数约束条件设产品标准袋、高档袋分别生产X1、X2个Obj:maxZ=9X1+10X2S.t.0.7X1+X2≤6300.5X1+0.83333X2≤6001X1+0.33333X2≤7080.1X1+0.25X2≤135X1≥0X2≥010102.12.1线性规划问题线性规划问题一般形式一般形式目标函数：ObjectiveFunctionMax(min)z=c1x1+c2x2+…+cnxn约束条件：Constrainta11x1+a12x2+…a1nxn≤(=,≥)b1a21x1+a22x2+…a2nxn≤(=,≥)b2……am1x1+am2x2+…amnxn≤(=,≥)bmx1,x2,…,xn≥011112.12.1线性规划问题线性规划问题几个概念几个概念可行解：若向量X=(x1,x2,…,xn)满足所有的约束条件，则称其为可行解。最优解：使目标函数达...