6.1问题的提出 第六章线性规划 1问题的提出 例1.某工厂有3种机器M1,M2,M3, 各为m1,m2,m3台.该厂生产P,P2, P这4种产品.T=(t31甲的 P,产品一个单位需要机器M的小时数 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=Cx1+,+C3x3+CAX4 满足如下的约束条件
６．１ 问题的提出 安排各产品的产量，才能使得所获的利润最 大？ 解．设４种产品的产量分别为x1，x2，x3， x4．利润 Z＝c1x1＋c2x2＋c3x3＋c4x4．机器 Mi一周内的机时为60mi，i＝1，2，3，4． 于是整个问题就是 max(Z)= c1x1＋c2x2＋c3x3＋c4x4， 满足如下的约束条件：
6.1问题的提出 t1x1+t2x2+t3x3+t14X460m t21X1+t2x2+t3x3+t24x46m2 t31x1+t2x2+t3Xx3+t34X4-60m X1,X2,X3,X>0 即在满足约束条件的前提下使目标函数 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, m.b=(b1b2…bn).有n种饲料,每单 位饲料j营养素含量为a,A=(a1)mxn 饲料的单位价格为c,C=(Cc1c2…cn)在 满足营养要求下,如何使饲料成本最低? 解设每头牲口每天需要饲料j量为x单位 X=(x1x2…xn.则有 minZ=CⅩ, 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个销地,需求量分别为b,b2 ,bn.设从产地运往销地j单位运费为 C;且产销平衡,即 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 mZ→2Xj 满足约束条件 m ∑x≤a,i=1,2,…,m b,j=1,2,…,n Ⅹ>0,i=1,2,…,m,j=1,2,…,n
６．１ 问题的提出 解 设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-t)x2∈S 则称S为凸集 规定空集为凸集,显然凸集的交集为凸 集.设S={X|AX0)},即S是线性 规划问题中的满足约束条件的X的集合(即 允许解域),则S是凸集.理由如下: 设X1,Ⅹ2∈S,t∈[0,1] =tx1+(1-t)×2,AX=A[tX1+(1-t×2] =tAX1+(1-t)AX2b,显然,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凸集 因而X∈S.可见允许解域S是凸集.允许解 域也称为超凸多面体 定义设S是超凸多面体,Ⅹ∈S,如果不存 在X1,Ⅹ2∈S,Ⅹ1X2,t∈(0,1),使得 X=tx1+(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=(a1 )m xn, b=(b1b2…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=-mi(Z),而AXb与 (一A)X≥-b等价.所有满足约束条件的X 的集合称为允许解域.允许解不存在,则 允许解域为空集,则线性规划问题无解; 而允许解域存在,目标函数无上界,上述 线性规划问题也无解.允许解存在,而目 标函数又有上界,则上述线性规划问题有 解
６．3 一般提法和几何意义 显然，maxZ＝－min(－Z)，而AX≤b与 (－A)X≥－b等价．所有满足约束条件的X 的集合称为允许解域．允许解不存在，则 允许解域为空集，则线性规划问题无解； 而允许解域存在，目标函数无上界，上述 线性规划问题也无解．允许解存在，而目 标函数又有上界，则上述线性规划问题有 解．