线性规划课件

**线性规划**线性规划问题及其数学模型

资源合理利用问题：第5页例2-1质量检验问题：第6页例2-2线性规划数学模型的一般形式**资源合理利用问题：第5页例2-1

1.决策变量：x1和x22.目标函数：max(2x1+3x2)3.约束条件：10

x1+20x2804x1

166x218

x1，x20**

质量检验问题：第6页例2-2

1.决策变量：x1和x22.目标函数：min(40

x1+36x2)

3.约束条件：5

x1+3x2

45

x1

8x2

10

x1，x20**线性规划数学模型的一般形式

1.决策变量是非负变量；

2.目标函数是线性函数；

3.约束条件是线性等式或不等式组。一般形式为：

max(min)(c1

x1+c2

x2+…+

cn

xn

)

a11

x1+a12

x2+…+a1nxn

(=,)b1

a21

x1+a22

x2+…+a2n

xn

(=,)b2

……

am1

x1+am2

x2+…+amn

xn

(=,)bm

x1，

x2，

…，xn

0

**

线性规划的图解法1.局限性：只能求解具有两个变量的线性规划问题。2.学习目的：图解法只能求解具有两个决策变量的线性规划问题，其应用具有很大的局限性，因此学习图解法的目的并非是要掌握一种线性规划问题的求解方法，而是要通过图解法揭示线性规划问题的内在规律，为学习线性规划问题的一般算法（单纯形法）奠定基础。3.线性规划有关解的几个概念4.图解法的基本步骤5.图解法所反映出的一般结论**线性规划有关解的几个概念

1.可行解：满足约束条件的一组决策变量的取值；

2.可行域：可行解所构成的集合；

3.最优解：使目标函数达到极值的可行解；

4.最优值：与最优解相对应的目标函数的取值。**图解法的基本步骤

1.画出平面直角坐标系；

2.将约束条件逐一反映进平面直角坐标系，用标号和箭线表明约束条件的顺序和不等号的方向；

3.找出可行域并反映出目标函数直线的斜率；

4.平移目标函数直线找出最优解。

5.例题：第7页例2-3：用图解法求解例2-16.习题：第8页例2-4：用图解法求解例2-2

**用图解法求解例2-1x1x2

4

3

2

1

012345678**用图解法求解例2-1x1x2

4

3

2

1

012345678**用图解法求解例2-1x1x2

4

3

2

1

012345678**用图解法求解例2-1x1x2

4

3

2

1

012345678**用图解法求解例2-1x1x2

4

3

2

1

012345678**用图解法求解例2-1x1x2

4

3

2

1

012345678**用图解法求解例2-1x1x2

4

3

2

1

012345678**用图解法求解例2-2x1x251015

15

10

5

0**图解法所反应出的一般结论1.线性规划问题的可行域是凸多边形；2.如果线性规划问题有最优解，其最优解一定可以在其可行域的顶点上得到，而不会在可行域的内部；3.如果线性规划问题在其可行域的两个顶点上得到最优解，那么两顶点连线上的所有点均为最优解点；4.线性规划问题的解可能有四种情况：唯一最优解；无穷多最优解；无界解和无可行解。**线形规划问题的标准形式1.标准形式的基本条件：（1）决策变量非负；（2）目标函数极大化（或极小化）；（3）约束条件为严格等式，且右端项非负。2.标准形式的表示：

代数式；和式；向量式；矩阵式

3.

标准形式的转化**线性规划的标准型：代数式minz=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2………

am1x1+am2x2+…+amnxn=bm

xj

≥0j=1,2,…,n**线性规划的标准型：和式minz=∑cjxj∑aijxj=bi

i=1,2,…,m

xj

≥0

j=1,2,…,nj=1nnj=1**线性规划的标准型：向量式minz=CX∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,n

C=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=1**线性规划的标准型：矩阵式

minz=CX

AX=b，X≥0，

b≥0

其中：b=(b1,b2,…,bm)T

a11

a12

….a1n

A=a21

a22…

a2n

…

…

…

am1

am2

…amn**标准形式的转化1.无约束变量x的处理：

x=y-z,其中y,z02.负数变量x的处理：

x=-y,其中y03.目标函数极小化的处理：

MinCX=-Max(-CX)4.非等式约束条件的处理：加松弛变量或减剩余变量5.右端项为负：两端同乘“-1”**线形规划的解集特征1.线性规划基与解的概念

(1)基、基列、基变量和非基变量

(2)基解、基可行解和可行基2.凸集的概念与解集的基本定理

(1)凸集的概念

(2)解集的基本定理**线性规划基与解的概念1.基、基列、基变量和非基变量

(1)基：MaxCX,AX=b,X0,b0

Amn其秩为m，B是Amn中的一个mm阶满秩矩阵，则称B是线性规划问题的一个基

(2)基列：基B中所包含的m个列向量

(3)基变量：基列所对应的决策变量

(4)非基变量：基变量以外的决策变量2.基解、基可行解、可行基

(1)基解：令所有的非基变量为零，所求得的一组解

(2)基可行解：所有分量均为非负的基解

(3)可行基：与基可行解所对应的基**凸集的概念与解集的基本定理1.凸集的概念：设K是n维欧氏空间的一点集，若任意两点X(1)

k，X(2)

k的连线上的一切点

X(1)+(1-)X(2)

k，(0<<1)

则称k为凸集。2.解集的基本定理：

(1)若线性规划问题存在可行域，则其可行域是凸集；

(2)线性规划问题的基可行解对应其可行域的顶点；

(3)若线性规划问题存在最优解，则其最优解一定能在基可行解中找到。**线性规划的单纯形法1.单纯形法的基本原理

(1)单纯形法的基本思路

(2)第12页例2-62.最优性检验与解的判别3.单纯形表4.单纯形法的基本步骤5.用单纯形法求解例2-66.课上习题**单纯形法的基本思路1.找出一个初始的基可行解；2.判断其最优性；3.转移至另一个较优的基可行解；4.重复2、3两步直至最优。**第12页例2-6Maxz=2x1+3x210x1+20x2+x3=804x1+x4=16

6x2+x5=18x1，

x2，

x3，

x4，

x50B=(p3，p4，p5)X(0)=(0，0，80，16，18)TZ(0)=0，z=2x1+3x2寻找相邻的基可行解**例2-6Max(2，3)=3

x2入基Min(80/20，18/6)=3

x5出基B=(p3，p4，p2)10x1+x3-10/3x5=204x1+x4=16x2+1/6x5=3X(1)=(0，3，20，16，0)TZ(1)=9，z=9+2x1-1/2x5**例2-6Max(2)=2

x1入基Min(20/10，16/4)=2

x3出基B=(p1，p4，p2)x1+1/10x3-1/3x5=2-2/5x3+x4+4/3x5=8x2+1/6x5=3X(2)=(2，3，0，8，0)TZ(2)=13，z=13-1/5x3+1/6x5**例2-6Max(1/6)=1/6

x5入基Min(8/(4/3)，3/(1/6))=6

x4出基B=(p1，p5，p2)x1+1/4x4=4-3/10x3+3/4x4+x5=6x2+1/20x3-1/8x4=2X(3)=(4，2，0，0，6)TZ(3)=14，z=14-9/10

x3

-1/8x4**最优性检验与解的判别**单纯形表**单纯形法的基本步骤1.数学模型标准化、正规化；2.建立初始单纯形表；3.计算检验数并判断最优性，结束或继续；4.确定入基变量和出基变量，5.迭代运算；6.重复3、4、5步，直至结束。**用单纯形法求解例2-6**用单纯形法求解例2-6**用单纯形法求解例2-6**用单纯形法求解例2-6**课上习题1.Maxz=2x1+4x2+x3+x4x1+3x2

+x48

2x1+x2

6x2

+x3

+x4

6x1

+x2

+x3

9x1~4

02.第17页例2-103.第19页例2-11**单纯形法的进一步讨论1.计算问题

(1)入基变量的选择

(2)解的退化2.人工变量与初始正规基

(1)大M法

(2)两阶段法**入基变量的选择

入基变量是根据最大正检验数来选择的，这样做的目的是为了使目标函数得到最大的增量，因此当最大正检验数有多个时，可主观地选择它们中的任意一个作为入基变量。其实具有正检验数的所有非基变量都可作为入基变量。**出基变量的选择与解的退化1.退化解：部分基变量的值为零的基可行解称为退化解。2.在选择出基变量时，如果最小比值不唯一，可主观确定出基变量，此时产生退化解。3.例**例Maxz=2x4+(3/2)x6

x1+x4-x5=8

x2+2x4+x6=4

x3+x4+x5+x6=3

x1~60**例**例**例**例**例**人工变量与初始正规基第21页例2-13:

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x30(1)标准化**例2-13的标准化

Minz=-3x1+x2+x3x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1~50(2)正规化**例2-13的正规化人工变量：为构造基变量（正规基）人为加入的变量

x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~70初始正规基B=(p4,p6,p7)=E**大M法1.大M法：令人工变量的价值系数为“-M”(极大值)或“M”(极小值)的单纯形法即称为大M法；例如：

Minz=-3x1+x2+x3+Mx人1+Mx人2

Maxz=2x1+x2+4x3-Mx人1+Mx人22.例2-13的大M法3.习题（大M法）**用大M法求解例2-13

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x30**用大M法求解例1.13

Minz=-3x1+x2+x3+Mx6+Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~70**用大M法求解例1.13**用大M法求解例1.13**用大M法求解例1.13**用大M法求解例1.13**习题（用大M法求解）

Maxz=2x1+4x2+x3x1+x2+x36x1+x2-2x34x1-2x2+x38x1，

x2，x30**习题（用大M法求解）

Maxz=2x1+4x2+x3-Mx7x1+x2+x3+x4=6x1+x2-2x3+x5=4x1-2x2+x3-x6+x7

=8x1~70**习题（用大M法求解）**习题（用大M法求解）**习题（用大M法求解）**两阶段法1.两阶段法：第一阶段，在原约束条件下，求所有人工变量和的最小值；第一阶段的目的是获得问题的一个初始基可行解（人工变量和的最小值为零）或得出问题无可行解（人工变量和的最小值大于零）的结论；第二阶段，去掉人工变量，在原目标下从已得到的基可行解开始优化。2.例2-13的两阶段法3.习题（两