会计学1.2线性规划问题解的基本理论一、LP问题的各种解1、可行解：满足约束条件和非负条件的决策变量的一组取值。2、最优解:使目标函数达到最优值的可行解。3、最优值：最优解对应目标函数的取值。对于线性规划标准型MaxZ=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn=b1a21x1+a22x2+….+a2nxn=b2………………….am1x1+am2x2+….+amnxn=bmx1,x2….xn0其中：bi0(i=1,2,….m)即：二、与线性规划问题解有关的基本概念1.基：设A是约束方程组m×n的系数矩阵，A的秩R(A)＝m，B是A中m×m阶非奇异子式,即|B|≠0,则称B是LP问题的一个基。基向量、基变量、非基变量、基本解？12100A=（P1,P2,P3,P4,P5）=4001004001A矩阵包含以下10个3×3的子矩阵：B1=（p1，p2，p3）B2=（p1，p2，p4）B3=（p1，p2，p5）B4=（p1，p3，p4）B5=（p1，p3，p5）B6=（p1，p4，p5）B7=（p2，p3，p4）B8=（p2，p3，p5）B9=（p2，p4，p5）B10=（p3，p4，p5）经计算可知：对应A系数矩阵可找出8个基（除B4、B8以外都是基）。对应于每一个基，可以得到8个基本解：x(1)=(4,3,-2,0,0)T（对应B1）x(2)=(2,3,0,8,0)T（对应B2）x(3)=(4,2,0,0,4)T（对应B3）x(5)=(4,0,4,0,12)T（对应B5）x(6)=(8,0,0,-16,12)T（对应B6）x(7)=(0,3,2,16,0)T（对应B7）x(9)=(0,4,0,16,-4)T（对应B9）x(10)=(0,0,8,16,12)T（对应B10）结合图形法分析解的集合：解的集合：解的集合：作业：找出下列线性规划问题的基本解、基本可行解和可行基Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0注意，线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。32100A=（P1,P2,P3,P4,P5）=2101003001A矩阵包含以下10个3×3的子矩阵：B1=（p1，p2，p3）B2=（p1，p2，p4）B3=（p1，p2，p5）B4=（p1，p3，p4）B5=（p1，p3，p5）B6=（p1，p4，p5）B7=（p2，p3，p4）B8=（p2，p3，p5）B9=（p2，p4，p5）B10=（p3，p4，p5）其中B4=0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。对于基B3=（p1，p2，p5），令非基变量x3=0，x4=0，即在等式约束中令x3=0，x4=0，解线性方程组：3x1+2x2=652x1+x2=403x2+x5=75得到x1=15，x2=10，x5=45，对应的基本解：x（3）=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T。由于每一个分量都是大于或等于0的，因此它是一个基本可行解。于是对应的基B3是一个可行基。类似可得到x(2)=(5,25,0,5,0)T（对应B2）x(7)=(20,0,5,0,75)T（对应B5）x(8)=(0,25,15,15,0)T（对应B7）x(9)=(0,0,65,40,75)T（对应B10）是基本可行解;因此，可行基有五个，分别是B2B3B5B7B10。x(3)=(0,32.5,0,7.5,-22.5)T（对应B9）x(4)=(65/3,0,0,-10/3,75)T（对应B6）x(5)=(7.5,25,-7.5,0,0)T（对应B1）x(6)=(0,40,-15,0,-45)T（对应B8）是基本解。三、与线性规划解的性质有关的基本概念（凸集、顶点）凸集2、凸组合设X（1）,X（2）,…,X（k）是n维欧氏空间中的K个点,若存在k个数μ1,μ2,…,μk,满足0≤μi≤1,i=1,2,…,k；且，则称X=μ1X（1）+μ2X（2）+…+μkX(k)为X（1）,，X（2），…，X（k）的凸组合。3、顶点设K是凸集，XK；若X不能用X（1）K，X（2）K的线性组合表示，即X≠αX（1）+（1-α）X（2）（0<α<1）则称X为K的一个顶点（也称极点或角点）多边形上的点是顶点定理1-3若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。在可行域中寻找LP的最优解可以转化为只在可行域的顶点中找，从而把一个无限