《《管理运筹学》课件01-线性规划基本性质.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》课件01-线性规划基本性质.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第 1 章章Linear ProgrammingL P线性规划线性规划基本性质基本性质1第1章 线性规划的基本性质1.1 线性规划的一般模型线性规划的一般模型1.2 线性规划的图解法线性规划的图解法1.3 线性规划的标准形式线性规划的标准形式1.4 线性规划的解及其性质线性规划的解及其性质1.5 线性规划的应用模型线性规划的应用模型第第1章章 线性规划的基本性质线性规划的基本性质2第1章 线性规划的基本性质1.1 线性规划的一般模型线性规划的一般模型1.1.1 引引 例例 例例1 1 产品配比问题（产品配比问题（范例范例）某厂拟生产甲、乙两种产品，每件利润分别为某厂拟生产甲、乙两种产品，每件
2、利润分别为3 3、5 5百元。百元。甲、乙产品的部件各自在甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、两个车间分别生产，每件甲、乙产品的部件分别需要乙产品的部件分别需要A、B车间的生产能力车间的生产能力1 1、2 2工时。两件工时。两件产品的部件最后都要在产品的部件最后都要在C车间装配，装配每件甲、乙产品分别车间装配，装配每件甲、乙产品分别需要需要3 3、4 4工时，三车间每天可用于生产这两种产品的工时分别工时，三车间每天可用于生产这两种产品的工时分别为为8 8、1212、3636，问应如何安排生产这两种产品才能获利最多？，问应如何安排生产这两种产品才能获利最多？3第1章 线性规划的
3、基本性质1.1 线性规划的一般模型线性规划的一般模型z z x1 x2决策变量决策变量z z=3x1+5x2maxmax0目标函数目标函数x1 8 2x2 12 3x1 +4x2 36 函数约束函数约束 x1 ，x2 0 非负性约束非负性约束s.t.s.t.甲甲 乙乙1030 2 4 8 12 36A B C车间车间产品产品单耗（工时单耗（工时/件）件）最大生产能力最大生产能力（工时（工时/天）天）单位利润单位利润（百元（百元/件）件）3 54第1章 线性规划的基本性质1.1 线性规划的一般模型线性规划的一般模型例例2 2 配料问题配料问题 某化工厂根据一项合同要为用户生产一种用甲、乙某化工厂
4、根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都两种原料混合配制而成的特殊产品。甲、乙两种原料都含有含有A，B，C三种化学成分三种化学成分，其含量其含量(%)是是:甲为甲为1212，2 2，3 3；乙为乙为3 3，3 3，1515。按合同规定按合同规定，产品中三种化学产品中三种化学成分的含量成分的含量(%)不得低于不得低于4 4，2 2，5 5。甲、乙原料成本为甲、乙原料成本为每千克每千克3 3，2 2元。元。厂方希望总成本达到最小厂方希望总成本达到最小，则应如何配制该产品则应如何配制该产品？5第1章 线性规划的基本性质1.1 线性规划的一般模型线性规划的一
5、般模型 成分含量成分含量(%)(%)原原 料料 化学成分化学成分 甲甲 乙乙 产品成分产品成分 最低含量最低含量(%)(%)A B C 12 3 2 3 3 15 4 2 5 成本（元成本（元/千克）千克）3 2 x x1 1x x2 2min z z=3x1+2x2 12 x1 +3x2 4 2 x1 +3x2 2s.t.3 x1+15x2 5 x1 +x2=1 x1,x2 0配料平衡条件配料平衡条件z z6第1章 线性规划的基本性质1.1 线性规划的一般模型线性规划的一般模型 1.1.2 线性规划的一般模型线性规划的一般模型 一般一般LP模型的模型的三类参数三类参数三类参数三类参数：价值系
6、数价值系数价值系数价值系数c c j j，消耗系数消耗系数消耗系数消耗系数a a ij ij，右端常数右端常数右端常数右端常数b b i i.LP模型的模型的三要素三要素三要素三要素：决策变量决策变量决策变量决策变量，目标函数目标函数目标函数目标函数，约束条件约束条件约束条件约束条件.s.t.opt z=c1 x1+c2 x2+c3 x3+cn xn a11x1+a12 x2+a1n xn b1 a21x1+a22 x2+a2n xn b2 am1x1+am2x2+amn xn bm xj(或或)0,或自由或自由,j=1,2,n 7第1章 线性规划的基本性质1.2 线性规划的图解法线性规划的图
7、解法1.2.1 图解法的基本步骤图解法的基本步骤 X*=(4,6)Tz*=42 1画出可行域图形画出可行域图形 2画出目标函数的画出目标函数的 等值线及其法线等值线及其法线 3确定最优点确定最优点max z=3x1+5x2 x1 8 2 x2 12 3x1+4 x2 36 x1,x2 0s.t.x1x2O(0,0)x1=8A(8,0)2x2=12D(0,6)3x1+4x2=36O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)z=15z=30z 法向法向z*=42边界方程边界方程边界方程边界方程8第1章 线性规划的基本性质1.2 线性规划的图解法线性规划的图解法1.2.2
8、几点说明几点说明实际运用时还须注意以下几点实际运用时还须注意以下几点:(1)(1)若函数约束原型就是等式若函数约束原型就是等式,则其代表的区域仅为一直线则其代表的区域仅为一直线,而且问而且问 题的整个可行域题的整个可行域R R(若存在的话若存在的话)也必然在此直线上。也必然在此直线上。(2)(2)在画目标函数等值线时只须画两条就能确定其法线方向在画目标函数等值线时只须画两条就能确定其法线方向,为此为此,只须赋给只须赋给z z 两个适当的值。两个适当的值。(3)(3)在找出最优点后在找出最优点后,关于其坐标值有两种确定方法关于其坐标值有两种确定方法:在图上观测最优点坐标值在图上观测最优点坐标值
9、通过解方程组得出最优点坐标值通过解方程组得出最优点坐标值9第1章 线性规划的基本性质1.2 线性规划的图解法线性规划的图解法1.2.3 几种可能结果几种可能结果一、唯一解一、唯一解 如例如例1 1、例、例2 2都只有一个都只有一个最优点，属于唯一解的情形最优点，属于唯一解的情形。s.t.max z=3x1+4x2 x1 8 2x2 12 3x1+4x2 36 x1 ，x2 0 二二、多重解多重解z=12z*=36线段线段BCBC上无穷多个上无穷多个点均为最优解。点均为最优解。O(0,0)x1x2R D(0,6)C(4,6)B(8,3)A(8,0)10第1章 线性规划的基本性质1.2 线性规划的
10、图解法线性规划的图解法x1x2z*三、无界解三、无界解3694812x1x2R R2 2R R1 1 R R2 2=四、无可行解四、无可行解+R R1 111第1章 线性规划的基本性质1.3 线性规划的标准形式线性规划的标准形式1.3.1 线性规划问题的标准形式线性规划问题的标准形式max z=c1x1+c2x2+c3x3+cnxns.t.a11x1+a12x2+a1nxn=b1(0)a21x1+a22x2+a2nxn=b2(0)am1x1+am2x2+amnxn=bm(0)x1,x2,xn 0简记为：简记为：max z=cjxj j=1ns.t.aijxj=bi,i=1,2,mj=1nxj
11、0,j=1,2,nmax z=CTX s.t.AX=b X 0(M1):(M2):(M3):(M)12第1章 线性规划的基本性质1.3 线性规划的标准形式线性规划的标准形式 1.3.2 非标准形非标准形LP问题的标准化问题的标准化 一、目标函数一、目标函数 min z=CTX 令令 z=z max z=CTX 例例：min z=3x1 2x2 max z=3x1 2x2 二、函数约束二、函数约束 bi0 两边同时乘以两边同时乘以 -1 约束为约束为形式形式 加上加上松弛变量松弛变量 约束为约束为形式形式 减去减去剩余变量剩余变量 三、决策变量三、决策变量 若若xk 0,令令 xk=xk,则则
12、xk 0 若若xk为为自由变量自由变量,令令 xk=xk xk且且 xk,xk 0 xx*f (x)-f (x)13第1章 线性规划的基本性质1.3 线性规划的标准形式线性规划的标准形式z z=3x1+5x2maxx1 8 2x2 12 3x1+4x2 36 x1 ，x2 0 s.t.x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5=36 x1，x2，x3，x4，x5 0 s.t.z z=3x1+5x2max范例范例范例范例+0 0 x3+0 0 x4+0 0 x514第1章 线性规划的基本性质1.3 线性规划的标准形式线性规划的标准形式min z=x1 2 x2 3 x3
13、x1 2 x2 x3 5 2x1 3 x2 x3 6 x1 x2 x3 2 x1 0,x3 0s.t.解:max z=x1 2x2 3x3s.t.x1 2x2 x3 +x4 =5 2x1 3x2 x3 -x5 =6 x1 x2 x3 +x6=2 x1,x4,x5,x6 0,x3 0例例4 4 将下述将下述LP问题化成标准形问题化成标准形15第1章 线性规划的基本性质1.3 线性规划的标准形式线性规划的标准形式令令x2=x2 x x2 2，且，且 x2，x x2 2 0 x3=-x x3 3 代入上式中，得代入上式中，得 max z=x1 2 x2+2 x x2 2 3x x3 3 x1+2x2
14、 2x x2 2+x x3 3+x4 =5 2x1+3x2 3x x2 2+x x3 3 x5 =6 x1+x2 x x2 2+x x3 3 +x6=2 x1,x2,x x2 2,x x3 3,x4,x5,x6 0s.t.16第1章 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质1.4.1 线性规划的解的概念线性规划的解的概念 一、一、可行解可行解:满足满足LP问题所有约束条件的问题所有约束条件的X。二、二、最优解最优解:满足目标要求的可行解满足目标要求的可行解X。三、三、基本解基本解:只适用于标准形只适用于标准形LP问题问题（M）。）。(1)基基(矩阵矩阵)AX=b 设设
15、B B为为A的一个的一个m阶子矩阵，若阶子矩阵，若|B B|0,|0,则称则称B B为约束方程组为约束方程组AX=b或标准形或标准形LP问题问题(M)的一个的一个基（矩阵）基（矩阵）。17第1章 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质范范范范 例例例例A=1 0 1 0 0 0 2 0 1 03 4 0 0 1 x1 x2 x3 x4 x5a1 a2 a3 a4 a5 可取可取 B0=（a3,a4,a5）为基（）为基（|B0|0）,这时这时称称 a3,a4,a5 为为基向量基向量，而，而 a1 ,a2 为为非基向量非基向量；称称x3,x4,x5 为为基变量基变量，而
16、，而 x1,x2 为为非基变量非基变量。18第1章 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质 (2)(2)基本解基本解 范例范例范例范例的标准形的标准形max z=3x1+5x2s.t.x1 +x3 =8 2 x2 +x4 =12 3x1+4x2 +x5=36 x1,x2,x3,x4,x5 0 取取 B0=（a3,a4,a5）为基，令一切非基变量为基，令一切非基变量 x1=x2=0,可解得基变量可解得基变量 x3=8，x4=12，x5=36则得一特解则得一特解 X0=(0，0，8，12，36)T 称为一个称为一个(关于关于 B0 为基的为基的)基本解基本解。19第1章
17、 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质也可取也可取 B1=(a2,a3,a4)为基为基,得得 X1=(0，9，8，-6，0)T还可取还可取 B2=(a1,a2,a3)为基为基,得得 X2=(4，6，4，0，0)T等等等等。四、四、基本可行解基本可行解 满足非负性约束的基本解满足非负性约束的基本解。如如 X0，X2；而而 X1 不不可行可行。对对基本基本(可行可行)解解而言而言：在其分量中，若有一个或更多个：在其分量中，若有一个或更多个基变量基变量取值为取值为0 0，则，则称其为一个称其为一个退化的退化的退化的退化的基本基本(可行可行)解解，否则为，否则为非退化的非
18、退化的非退化的非退化的。如设：如设：X X=(0，6 6，5 5，0，0 0)T 是一个是一个基本可行解基本可行解，其中其中 x x5 =0 0 为为基变量基变量基变量基变量，则该，则该X X为为退化的退化的退化的退化的基本可行解基本可行解。20第1章 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质非退化的非退化的非退化的非退化的基本基本(可行可行)解解，并恰有并恰有 n n m m 个个 0 0 分量。分量。基本可行解基本可行解对应的对应的基基，称为称为可行基可行基；最优基本解最优基本解最优基本解最优基本解对应的对应的基基，称为称为最优基最优基。如：如：基基 B0=(a2
19、,a3,a4)对应对应 X0=(0，0，8，12，36)T 可行可行 基基 B1=(a2,a3,a4)对应对应 X1=(0，9，8，-6-6，0)T 不可行不可行不可行不可行 基基 B2=(a1,a2,a3)对应对应 X2 =(4 4，6 6，4，0，0)T 恰有恰有 m m 个个非非非非 0 0 分量，分量，为为可行基可行基为为非可行非可行非可行非可行基基为为最优基最优基x*x*B*21第1章 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质1.4.2 凸性的几个基本概念凸性的几个基本概念一一、凸集凸集 设设S S En，对任意两点，对任意两点XS S，Y YS S，若对满
20、足，若对满足0 1的一切的一切实数实数，都有，都有 X+(1-)Y Y S S则称则称S S为为凸集凸集。XY YXY Y 凸集凸集凸集凸集非非凸集凸集非非表示表示S S 中两点中两点 X，Y Y 连线上的任一点连线上的任一点凸集凸集的的几何意义几何意义：凸集：凸集S S中任意两点中任意两点 X，Y Y 连线上的点，都在凸集连线上的点，都在凸集S S中。中。22第1章 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质二、二、极点极点 设凸集设凸集S S E En n,X XS S，如果如果X X不能用不能用S S中不同的两点中不同的两点Y Y和和Z Z表示为表示为 X X=Y
21、 Y+(1-)Z Z (01)则称则称X X为为S S的一个的一个极点极点。三、三、凸组合凸组合 设设X Xi iE En n,实数实数 i i 00,i=1,2,s,且且i i=1 1，则称则称 X X=1 1X X1 1+2 2X X2 2+s sX Xs s为点为点 X X1 1，X X2 2，X Xs s 的一个的一个凸组合凸组合。23第1章 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质1.4.1.4.3 3 线性规划的解的性质线性规划的解的性质 性质性质性质性质1：LP问题问题(M)的可行域的可行域 R=XAX=b,X 0 是凸集。是凸集。性质性质性质性质2：L
22、P问题问题(M)的一个基本可行解与可行域的一个基本可行解与可行域 R 的一个极点的一个极点 互相对应。互相对应。性质性质性质性质3：线性规划的基本定理线性规划的基本定理线性规划的基本定理线性规划的基本定理 对于一个给定的标准型对于一个给定的标准型LP问题问题(M)来说：来说：若若(M)有可行解，则必有基本可行解；有可行解，则必有基本可行解；若若(M)有最优解，则必有最优基本解。有最优解，则必有最优基本解。性质性质性质性质4 4：若：若LP问题的可行域问题的可行域 R,则则 R 至少有一极点。至少有一极点。性质性质性质性质5 5：LP问题可行域问题可行域 R 的极点数目必为有限个。的极点数目必为
23、有限个。24第1章 线性规划的基本性质1.4 线性规划的解及其性质线性规划的解及其性质仅就标准形仅就标准形LP问题问题(M)说明其合理性。说明其合理性。因因(M)是一个是一个m阶阶n维的维的LP问题，则从其系数阵的问题，则从其系数阵的n列中列中取出取出m列，所构成其列，所构成其基基的个数不超过的个数不超过C C mn=n！m！(n-m)！C C mn基本可行解基本可行解的个数的个数 基本解基本解的个数的个数而问题而问题(M)的的 枚举法枚举法枚举法枚举法:当当m=50，n=100时时，此，此时需要求解的时需要求解的50元元50阶的线性方程组的个数为阶的线性方程组的个数为C C 50100=10
24、0！50！50！1029 这是一个天文数字！故需另寻其他有效方法。这是一个天文数字！故需另寻其他有效方法。25第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型 1.5.1 生产计划问题生产计划问题 某企业拟用某企业拟用m种资源生产种资源生产n种产品种产品，已知第已知第i种种资源的数量为资源的数量为bi,其单价为其单价为pi,每生产一个单位第每生产一个单位第j种种产品所提供的产值为产品所提供的产值为vj,所消耗的第所消耗的第i种资源的数量种资源的数量为为aij。第第j种产品的合同与指令性计划的产量指标为种产品的合同与指令性计划的产量指标为ej,最高需求量为最高需求量为dj。
25、该企业应如何拟定生产计划该企业应如何拟定生产计划？26第1章 线性规划的基本性质 一、决策变量决策变量 设设xj为第为第j种产品的计划产量种产品的计划产量 二、约束条件约束条件 指标约束指标约束 xj ej,j=1,2,n 需求约束需求约束 xj dj,j=1,2,n 资源约束资源约束 三、目标函数目标函数 总产值总产值1.5 线性规划的应用模型线性规划的应用模型 j=1naijxj bi,i=1,2,m j=1nm i=1z2=pi(aij xj)总成本总成本z1=vj xj nj=127第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型 i=1=vj xj-pi(aij
26、 xj)j=1nmj=1n=(vj-pi aij)xjj=1n i=1m令令 cj=vj-pi aij i=1mxj ej,j=1,2,nxj djaijxj bi,i=1,2,m j=1nmax z=cj xjj=1n s.t.则则 总利润总利润 z=z1-z228第1章 线性规划的基本性质1.5.2 食谱问题食谱问题 有有n种食品种食品,每种食品中含有每种食品中含有m种营养成分种营养成分。食品用食品用 j=1,2,n表示表示，养分用养分用 i=1,2,m表示表示。已知第已知第 j 种种食品单价为食品单价为 cj,每天最大供量为每天最大供量为 dj;而每单位第而每单位第 j种食品所含种食品所
27、含第第 i 种养分的数量为种养分的数量为 aij。假定某种生物每天对第假定某种生物每天对第 i 种养分的种养分的需求量至少为需求量至少为 bi,而每天进食数量限定在而每天进食数量限定在 h1,h2 范围内范围内。试求该生物的食谱试求该生物的食谱，使总成本为最小使总成本为最小。1.5 线性规划的应用模型线性规划的应用模型29第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型 设设 xj 为每天提供给该生物食用的第为每天提供给该生物食用的第 j 种食品的数量，种食品的数量，则该问题的数学模型为则该问题的数学模型为:s.t.0 xj dj,j=1,2,nmin z=cj xjj=
28、1nj=1 h1 xj h2nj=1 aij xj bi,i=1,2,m n 某厂制造某种部件，由某厂制造某种部件，由2个个B1零件零件,3个个B2零件配套组装零件配套组装而成而成。该厂有该厂有A1,A2,A3三种机床可加工这两种零件三种机床可加工这两种零件，每种每种机床的台数机床的台数，以及每台机床的生产率如下表所示以及每台机床的生产率如下表所示。求产量最大的生产方案求产量最大的生产方案。1.5.3 产品配套问题产品配套问题30第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型 一、决策变量一、决策变量 设以设以xij表示每台表示每台Ai(i=1,2,3)机床每个工作日加
29、工机床每个工作日加工Bj(j=1,2)零件的时间零件的时间(单位单位:工作日工作日)；z为为B1,B2零件按零件按 2:3 的比例配套的数量的比例配套的数量(套套/日日)。机床机床种类种类机床机床台数台数每台每台每台每台机床生产率机床生产率(件件/日日)零件零件B1零件零件B2A1320203030A2235354545A3410101818x11x12x21x22x31x3231第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型 二、约束条件二、约束条件 工时约束工时约束 配套约束配套约束机床机床种类种类总总总总生产率生产率(件件/日日)零件零件B1零件零件B2A1606
30、09090A270709090A340407272x11x12x21x22x31x32z=min (60 x11+70 x21+40 x31),(90 x12+90 x22+72x32)1213z (60 x11+70 x21+40 x31)12z (90 x12+90 x22+72x32)13非线性，等价改写成：非线性，等价改写成：或或x11+x12=1x21+x22=1x31+x32=1z-35x11-35x21-20 x31 0z-30 x12-30 x22-24x32 032第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型则该问题的数学模型为则该问题的数学模型为:
31、max z s.t.x11 +x12 =1 x21 +x22 =1 x31 +x32 =1z 35x11 35x21 20 x31 0z 30 x12 30 x22 24x32 0z,x11,x12,x21,x22,x31,x32 0 制造某种机床制造某种机床，需要需要 A,B,C三种轴件三种轴件，其规格与数量如表其规格与数量如表所示所示，各类轴件都用各类轴件都用5.5米长的同一种圆钢下料米长的同一种圆钢下料。若计划生产若计划生产100台机床台机床，最少需要用多少根圆钢最少需要用多少根圆钢？1.5.4 下料问题下料问题33第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型轴
32、类轴类 规格：长度（米）规格：长度（米）每台机床所需轴件数每台机床所需轴件数 A 3.1 1 B 2.1 2 C 1.21.2 4 余料余料 j j 1.21.2找出全部找出全部省料截法省料截法一根圆钢所截各类轴件数一根圆钢所截各类轴件数 截法截法轴类轴类 轴轴 件件 需要量需要量 A(3.1)100 B(2.1)200 C(1.2)400 余料余料(米米)234511100.310200210.1 0 0 1 0 2 4 1 0.734第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型min z=x1+x2+x3+x4+x5s.t.x1+x2 100 x1 +2x3 +x
33、4 200 2x2 +x3+2x4+4x5 400 x1，x2，x3，x4，x5 0则该问题的数学模型为则该问题的数学模型为:设第设第 j 种截法下料种截法下料 xj 根。根。35第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型 某化工厂要用三种原料某化工厂要用三种原料 D，P，H 混合配制三种不同规格混合配制三种不同规格的产品的产品 A，B，C。有关数据如下有关数据如下：1.5.5 配料问题配料问题产品产品规规 格格单价单价(元元/kg)A原料原料D不少于不少于50%原料原料P不超过不超过25%50B原料原料D不少于不少于25%原料原料P不超过不超过50%35C不不 限
34、限25原料原料最大供量最大供量(kg/天天)单价单价(元元/kg)D1006565P1002525H603535应如合配制应如合配制，才能使利润达到最大才能使利润达到最大？表表1-10表表1-1136第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型一、决策变量决策变量 设以设以 xij 表示每天生产的表示每天生产的第第 j 种产品中所含第种产品中所含第 i 种原料种原料的数量的数量(kg，右表右表)。ji D P HABCx11 x12 x13x21 x22 x23x31 x32 x33二、约束条件二、约束条件 规格约束规格约束(据据表表1-10)x11+x12+x13x
35、11 0.50 x11+x12+x13x12 0.25x11+x12+x13x21 0.25x11+x12+x13x22 0.5037第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型改写成改写成 -x11 +x12 +x13 0-x11+3 x12 -x13 0-3 x21 +x22 +x23 0 x21 +x22 -x23 0 资源约束资源约束(据据表表1-11)x11+x21 +x31 100 x12+x22+x32 100 x13+x23 +x33 6038第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型三、目标函数三、目标函数 总产值总产值(
36、据据表表1-10)产品产品A的产值的产值:50(x11+x12 +x13)产品产品B的产值的产值:35(x21+x22+x23)产品产品C的产值的产值:25(x31+x32 +x33)以上三项之和即以上三项之和即总产值总产值。总成本总成本(据据表表1-11)原料原料D的成本的成本:6565(x11+x21 +x31)原料原料P的成本的成本:2525(x12+x22+x32)原料原料H的成本的成本:3535(x13+x23 +x33)以上三项之和即以上三项之和即总成本总成本。39第1章 线性规划的基本性质1.5 线性规划的应用模型线性规划的应用模型 目标函数目标函数为：为：总利润总利润总利润总利润=总产值总产值-总成本总成本max z z=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 该问题的数学模型为该问题的数学模型为:s.t.-x11 +x12+x13 0 -x11+3x12 -x13 0 -3x21+x22 +x23 0 x21+x22 -x23 0 x11 +x21 +x31 100 x12 +x22 +x32 100 x13 +x23 +x33 60 xij 0，i=1,2,3；j=1,2,340第1章 线性规划的基本性质