线性规划及单纯形法.pptx

会计学1.2线性规划问题解的基本理论一、LP问题的各种解1、可行解：满足约束条件和非负条件的决策变量的一组取值。

2、最优解:使目标函数达到最优值的可行解。

3、最优值：最优解对应目标函数的取值。
对于线性规划标准型
MaxZ=c1x1+c2x2+…..+cnxn
s.t.a11x1+a12x2+….+a1nxn=b1
a21x1+a22x2+….+a2nxn=b2
………………….
am1x1+am2x2+….+amnxn=bm
x1,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问题的一个基。

基向量、基变量、非基变量、基本解？12100
A=（P1,P2,P3,P4,P5）=40010
04001
A矩阵包含以下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+2500x2
s.t.3x1+2x2≤65
2x1+x2≤40
3x2≤75
x1,x2≥0

注意，线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。32100
A=（P1,P2,P3,P4,P5）=21010
03001
A矩阵包含以下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=65
2x1+x2=40
3x2+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的最优解可以转化为只在可行域的顶点中找，从而把一个无限