∑Px≤(=2)b (1.6) X≥0G=12,…,n) 其中C=(cl,c2,…cn),称为价值系数向量: A=(anax“an|称为技术系数矩阵(并称消耗系数矩阵) b b 称资源限制向量 X=(x1,x2,…,xn)称为决策变量向量。 (三)LP问题的标准型 1为了讨论LP问题解的概念和解的性质以及对LP问题解法方便,必须 把LP问题的一般形式化为统一的标准型: maxz> C maXz-c =b(i=1,2,…,m)「AX=b 或 x,≥0(=1,2, X≥0 ∑P,x=b x,≥0(=12,…,n)
-6- = = = 0 ( 1,2, , ) ( , ) 1 X j n p x b j n j j j (1.6) 其中C=(c1,c2,…,cn)，称为价值系数向量； = m m mn n n a a a a a a a a a A , , , , , , 1 2 21 22 2 11 12 1 称为技术系数矩阵（并称消耗系数矩阵） =(p1,p2,…,pn) = m b b b b 2 1 称资源限制向量 X=(x1,x2,…,xn) T称为决策变量向量。 （三）LP问题的标准型 1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须 把LP问题的一般形式化为统一的标准型： maxz= = n j j j c x 1 ； = = = = 0( 1,2, , ) ( 1,2, , ) 1 x j n a x b i m j n j j j i 或 = X 0 AX b maxz=cx 或 = = = 0( 1,2, , ) 1 x j n p x b j n j j j maxz=cx
标准型的特点: ①目标函数是最大化类型 ②约束条件均由等式组成 ③决策变量均为非负 ④b(i=1,2…,n) 2化一般形式为标准型 ①minz→>max(-z)=cx ②“≤”→左边+松驰变量;“≥”→左边一“松驰变量” ③变量x≤0>x≥0变量x无限制→令x=x-xj” ④b<0→等式两边同乘以(-1) 3模型隐含的假设 ①比例性假定:决策变量变化的改变量与引起目标函数的改变量成比 例;决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假 定意味着每种经营活动对目标函数的贡献是一个常数,对资源的消耗也是 一个常数。 ②可加性假定:每个决策变量对目标函数和约束方程的影响是独立于 其它变量的。 ③连续性假定:决策变量应取连续值。 ④确定性假定:所有的参数(ai,b,c)均为确定,所以LP问题是确定型问 题,不含随机因素。 以上4个假定均由于线性函数所致。在现实生活中,完全满足这4个假 定的例子并不多见,因此在使用LP时必须注意问题在什么程度上满足这些 假定。若不满足的程度较大时,应考虑使用其它模型和方法。如非线性规 划,整数规划或不确定型分析方法
-7- 标准型的特点： ①目标函数是最大化类型 ②约束条件均由等式组成 ③决策变量均为非负 ④bi(i=1,2,…,n) 2.化一般形式为标准型 ①minz→max(-z)=-cx ②“”→左边+松驰变量；“”→左边－“松驰变量” ③变量xj0→-xj0变量xj无限制→令xj=xj－xj ④bi<0→等式两边同乘以(-1)。 3.模型隐含的假设 ①比例性假定：决策变量变化的改变量与引起目标函数的改变量成比 例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假 定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是 一个常数。 ②可加性假定：每个决策变量对目标函数和约束方程的影响是独立于 其它变量的。 ③连续性假定：决策变量应取连续值。 ④确定性假定：所有的参数(aij,bi,cj)均为确定，所以LP问题是确定型问 题，不含随机因素。 以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假 定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些 假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规 划，整数规划或不确定型分析方法
对LP标准型,我们还假定(A=m<n。 (四)LP问题的解的概念 设LP问题 maⅹz= ∑ (1.7) ax=b(i=12,…,m) (1.8) x≥0(=12,…,m) (1.9) 1从代数的角度看: 可行解和最优解满足约束条件(.8)和(19)的解X=(x1,x2,…,xn)称为 可行解。所有可行解构成可行解集,即可行域S={XA,=b,x≥0} 而使目标函数达到最大值的可行解称为最优解,对应的目标函数值称为最 优值。 求解LP问题就是求其最优解和最优值,但从代数的角度去求是困难 的 2从LP角度看 基:设A为mxn矩阵,r(A)=m,B是A中的mxm阶非奇异子矩阵(即B|=0), 则称B是LP问题的一个基。 若B是LP问题的一个基,则B由m个线性独立的列向量组成,即 B=(PP2,…,Pm),其中P(an,arn…,am),(=12;…,m)称为基向理。与其 向量P相对应的变量x称为基变量,其它变量称为非基变量。显然,对应 于每个基总有m个基变量,n-m个非基变量。 基本解与基可行解设B是LP问题的一个基,令其n-m个非基变量均 为零,所得方程的解称为该LP问题的一个基本解。显然,基B与基本解是
-8- 对LP标准型，我们还假定r(A)=m<n。 （四）LP问题的解的概念 设LP问题 maxz= = n j j j c x 1 (1.7) = = = n j a j x j bi i n 1 ( 1,2,, ) (1.8) x 0( j 1,2, , n) j = (1.9) 1.从代数的角度看： 可行解和最优解 满足约束条件(1.8)和(1.9)的解X=(x1,x2,…,xn) T称为 可行解。所有可行解构成可行解集，即可行域 S = {X A = b, x 0} x 。 而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最 优值。 求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难 的。 2.从LP角度看： 基：设A为mxn矩阵，r(A)=m，B是A中的mxm阶非奇异子矩阵（即|B|0）， 则称B是LP问题的一个基。 若B是LP问题的一个基，则B由m个线性独立的列向量组成，即 B=(Pr1,Pr2,…,Prm)，其中Prj=(a1rj,a2rj,…,amrj) T，(j=1,2,…,m)称为基向理。与其 向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应 于每个基总有m个基变量，n－m个非基变量。 基本解与基可行解 设B是LP问题的一个基，令其n－m个非基变量均 为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是
对应的,基本解的个数≤Cn。在基本解中,称满足非负条件的基本解 为基可行解,对应的基称为可行基。 退化解如果基解中非零分量的个数小于m,则称此基本解为退化 的,否则是非退化的 最优基如果对应于基B的基可行解是LP问题的最优解,则称B为LP 问题的最优基,相应的解又称基本最优解。 3.LP问题解之间的关系如图所示 基本解 可 基可行解 (五)两个变量LP问题的图解法 1LP问题解的几何表示。以引例为例说明 maxz=2x1+3x2 x1+2x2≤8① 4x.<16 4x2≤12 x≥0,x2≥0④ 按以下顺序进行 解:(1)画出直角坐标系; (2)依次做每条约束线,标出可行域的方向,并找出它们共同的 可行域
-9- 一一对应的，基本解的个数≤Cmn。在基本解中，称满足非负条件的基本解 为基可行解，对应的基称为可行基。 退化解 如果基解中非零分量的个数小于m，则称此基本解为退化 的，否则是非退化的。 最优基 如果对应于基B的基可行解是LP问题的最优解，则称B为LP 问题的最优基，相应的解又称基本最优解。 3.LP问题解之间的关系如图所示 （五）两个变量LP问题的图解法 1.LP问题解的几何表示。以引例为例说明 maxz=2x1+3x2 + 0, 0 4 12 4 16 2 8 1 2 2 1 1 2 x x x x x x 按以下顺序进行： 解：（1）画出直角坐标系； （2）依次做每条约束线，标出可行域的方向，并找出它们共同的 可行域； ① ② ③ ④ 可 行 解 基本解 基可行解
(3)任取一目标函数值作一条目标函数线(称等值线),根据目标 函数(最大或最小)类型,平移该直线即将离开可行域上,则与目标函数 线接触的最终点即表示最优解 图1 其中,将目标函数乙2(+3x改写为x=-2x+12,因此,它可 以表示为:以z为参数,以一二为斜率的一族平行线。位于同一条直线上的 点具有相同的值。 解的几种情况 (1)此例有唯一解Q2,即x1=4x2=2,z=14 (2)有无穷多最优解(多重解),若将目标函数改为z2x1+4x2则线段 Q2,Q3上的点均为最优解。 (3)无界解
-10- （3）任取一目标函数值作一条目标函数线（称等值线），根据目标 函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数 线接触的最终点即表示最优解。 图1 其中，将目标函数Z=2x1+3x2改写为 x x z 3 1 3 2 2 = − 1 + ，因此，它可 以表示为：以z为参数，以 3 2 − 为斜率的一族平行线。位于同一条直线上的 点具有相同的值。 解的几种情况： （1）此例有唯一解Q2，即x1=4,x2=2,z=14 （2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段 Q2，Q3上的点均为最优解。 （3）无界解 x2 ② ③ ① Q2 Q4 Q3 B Q1 A x1 3 2 1 0 0 1 2 3 4