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 aX<b X>0
６．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 的集合称为允许解域．允许解不存在，则 允许解域为空集，则线性规划问题无解； 而允许解域存在，目标函数无上界，上述 线性规划问题也无解．允许解存在，而目 标函数又有上界，则上述线性规划问题有 解．