清华大学：《组合数学》课程教学资源（PPT课件讲稿）第六章 线性规划

6.1问题的提出 第六章线性规划 1问题的提出 例1.某工厂有3种机器M1,M2,M 各为m1,m2,m台.该厂生产P1,P2,P3, P4这4种产品.T=(t1)3×4中的为生产 P产品一个单位需要机器M的小时数 1,2,3;j=1,2,3,4.设4种 产品的单位利润率为c1,c2,c3,c4。假定生 产这4种产品所用的机器无先后之分,每周 机器开动不超过60小时,在一周内应如何

６．１ 问题的提出 第六章 线性规划 １ 问题的提出 例１．某工厂有３种机器M1，M2，M3， 各为m1，m2，m3台．该厂生产P1，P2，P3， P4这４种产品．T＝（t ij）3×4中的t ij为生产 Pj产品一个单位需要机器Mi的小时数． i＝1，２，３；j＝１，２，３，４．设４种 产品的单位利润率为c1，c2，c3，c4。假定生 产这４种产品所用的机器无先后之分，每周 机器开动不超过６０小时，在一周内应如何

6.1问题的提出 安排各产品的产量,才能使得所获的利润最 大 解.设4种产品的产量分别为x1,x2,x3, x4,利润Z=c1x1+c2x2+c3x3+c4x4.机器 M;一周内的机时为60m;,i=1,2,3,4 于是整个问题就是 max(z=C,x1+C2x2+C3 x3+C4X4 满足如下的约束条件

６．１ 问题的提出 安排各产品的产量，才能使得所获的利润最 大？ 解．设４种产品的产量分别为x1，x2，x3， x4．利润 Z＝c1x1＋c2x2＋c3x3＋c4x4．机器 Mi一周内的机时为60mi，i＝1，2，3，4． 于是整个问题就是 max(Z)= c1x1＋c2x2＋c3x3＋c4x4， 满足如下的约束条件：

6.1问题的提出 tuXItt12x2+t3x3+t14X40 即在满足约束条件的前提下使目标函数 Z达到最大

６．１ 问题的提出 t11x1＋t12x2＋t13x3＋t14x4≤60m1 t21x1＋t22x2＋t23x3＋t24x4≤60m2 t31x1＋t32x2＋t33x3＋t34x4≤60m3 x1，x2，x3，x4≥0 即在满足约束条件的前提下使目标函数 Z达到最大．

6.1问题的提出 例2某饲料厂为牲口安排饲料.每头牲 口每天需要营养素i量不少于b;,i=1,2 b=(b1 b2 bn).有n种饲料,每单 位饲料j营养素的含量为a,A=(amxm 饲料j的单位价格为c,C=(c1c2…cn).在 满足营养要求下,如何使饲料成本最低? 解设每头牲口每天需要饲料j的量为x1单位 X=(X X2Xn).则有 min z-cX AX>b,X≥0

６．１ 问题的提出 例２ 某饲料厂为牲口安排饲料．每头牲 口每天需要营养素i的量不少于bi，i=1,2,…, m．b ＝(b1 b2 ··· bm)．有n种饲料，每单 位饲料j中营养素i的含量为aij，A＝( aij )m×n． 饲料j的单位价格为cj，C＝( c1 c2 ··· cn )．在 满足营养要求下，如何使饲料成本最低？ T T 解 设每头牲口每天需要饲料j的量为xj单位 X ＝(x1 x2 ··· xn )．则有 min Z=CX， AX≥b , X≥０

6.1问题的提出 例3某产品有m个产地,产量为a1,a2, ,an;有n个销地,需求量分别为b1,b2, ,bn.设从产地运往销地j的单位运费为 Cn.且产销平衡,即 ∑a;=∑b 应如何调配使总运费最低?

６．１ 问题的提出 例３ 某产品有m个产地，产量为a1，a2， ···，am；有n个销地，需求量分别为b1，b2， ···，bn．设从产地i运往销地j的单位运费为 cij．且产销平衡，即 ∑ai ＝∑bj 应如何调配使总运费最低？ m n i=1 j=1

6.1问题的提出 解设x表示从产地运往销地j的产品量 问题变成求 m n mn2一2>9x 满足约束条件 ∑x;≤a,i=1,2 ∑x1≥b,j=1,2,…,n X1=0,i=1,2,…,m,j=1,2

６．１ 问题的提出 解 设xij表示从产地i运往销地j的产品量． 问题变成求 min Z =∑∑cijxij 满足约束条件 ∑xij≤ai，i＝1，2，…，m ． ∑xij≥bj，j＝1，2，…，n． Xij≥0， i＝1，2，…，m , j＝1，2，…，n． m n i=1 j=1 m n i=1 j=1

6.2凸集 定义设S是n维欧氏空间的点集,若∨x1 x2∈S,t∈[0,1,都有Ⅹ=tx1+(1-tx2∈S 则称S为凸集 规定空集为凸集,显然凸集的交集为凸 集.设S={X|AX<b,X≌0},即S是线性 规划问题中的满足约束条件的X的集合(即 允许解域),则S是凸集.理由如下 设X1,Ⅹ2∈S,t∈[0,1] X=tx1+(1一tx2,AX=A[x1+(1一tX2 =tAX1+(1-t)AX2≤b,显然,X≥0

６．2 凸集 定义 设S是n维欧氏空间的点集，若x1， x2∈S，t∈[0 , 1]，都有X＝tx1+(1－t)x2∈S 则称S为凸集． 规定空集为凸集，显然凸集的交集为凸 集．设S = {X｜AX≤b，X≥0}，即S是线性 规划问题中的满足约束条件的X的集合（即 允许解域），则S是凸集．理由如下： 设X1，X2∈S，t∈[0 , 1]， X= tX1+ (1－t)X2，AX＝A[tX1+ (1－t)X2 ] ＝tAX1+ (1－t) AX2≤b，显然，X≥0

6.2凸集 因而Ⅹ∈S.可见允许解域S是凸集.允许解 域也称为超凸多面体 定义设S是超凸多面体,ⅹ∈S,如果不存 在X1,X2∈S,Ⅹ1X2,t∈(0,1),使得 X=X1+(1-t)X2,则称X为S的顶点

６．2 凸集 因而X∈S．可见允许解域S是凸集．允许解 域也称为超凸多面体 定义 设S是超凸多面体，X ∈S，如果不存 在X1，X2∈S，X1≠X2，t ∈( 0 , 1 )，使得 X＝tX1+ (1－t )X2，则称X为S的顶点

6.3一般提法和几何意义 3 般提法和几何意义 以上问题可归纳为一类问题:目标函数是 线性函数,约束条件是线性不等式,在满 足约束条件的前提下求目标函数的最大值 或最小值.为简便起见,用矩阵表示.设 C=(c1c2…cn),X=(x1x2…x A=(a1mxn,b=(bb2…b 线性规划可表示为:maxZ=CX aX0

６．3 一般提法和几何意义 以上问题可归纳为一类问题：目标函数是 线性函数，约束条件是线性不等式，在满 足约束条件的前提下求目标函数的最大值 或最小值．为简便起见，用矩阵表示．设 C＝( c1 c2 ···cn )，X＝( x1 x2 ···xn ) ， A＝( aij )m×n，b＝( b１b2 ···bn ) ． 线性规划可表示为：max Z＝CX AX≤b X≥0 T T • 3 一般提法和几何意义

6.3一般提法和几何意义 显然,maxZ=-min(-Z),而AX<b与 A)X≥-b等价.所有满足约束条件的X 的集合称为允许解域.允许解不存在,则 允许解域为空集,则线性规划问题无解; 而允许解域存在,目标函数无上界,上述 线性规划问题也无解.允许解存在,而目 标函数又有上界,则上述线性规划问题有

６．3 一般提法和几何意义 显然，maxZ＝－min(－Z)，而AX≤b与 (－A)X≥－b等价．所有满足约束条件的X 的集合称为允许解域．允许解不存在，则 允许解域为空集，则线性规划问题无解； 而允许解域存在，目标函数无上界，上述 线性规划问题也无解．允许解存在，而目 标函数又有上界，则上述线性规划问题有 解．