运筹学线性规划与单纯形法

1、运筹学基础及应用线性规划及单纯形法,1,运 筹 帷 幄 之 中,决 胜 千 里 之 外,linear programming,运 筹 学 课 件,运筹学基础及应用线性规划及单纯形法,2,1 一般线性规划问题的数学模型 1-1 问题的提出 生产计划问题 如何合理使用有限的人力、物力和资金，使得收到最好的经济效益。 如何根据给定的计划，统筹安排用最少的人力、物力完成任务。,运筹学基础及应用线性规划及单纯形法,3,引例 某企业计划生产、两种产品。这两种产品都要分别在a、b、c、d四种不同设备上加工。生产每件产品需占用各设备分别为2、1、4、0h，生产每件产品，需占用各设备分别为2、2、0、4h。已知

2、各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品企业能获得2元利润，每生产一件产品企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。,运筹学基础及应用线性规划及单纯形法,4,运筹学基础及应用线性规划及单纯形法,5,设分别用 表示两种产品在计划期内的产量,因为设备a在计划期内的可用时间为12h，不允许超,于是有,同样的对设备b,c,d有,企业的目标是在各种设备能力允许的条件下，利润最大,运筹学基础及应用线性规划及单纯形法,6,需满足条件：,实现目的：,求解这一类带附加限制条件的极值问题，是 运筹学中规划论部分的内容,运筹学基础及应用

3、线性规划及单纯形法,7,1-2 线性规划问题的数学模型,规划问题三个组成要素：,1.决策变量:,2.目标函数:,3.约束条件:,是决策者为实现规划目标采取的方案、,指问题要达到的目的要求，表示为决,策变量的函数。,措施，是问题中要确定的未知量。,指决策变量取值时受到的各种可用资,源的限制，表示为含决策变量的等式,或不等式。,运筹学基础及应用线性规划及单纯形法,8,解：将实际问题转化为线性规划模型有以下步骤：,1确定决策变量：,2确定目标函数：,3确定约束条件：,4变量取值限制:,x1=产品的计划内产量 x2=产品的计划内产量,企业的目标是总利润收入最大,（一般情况，决策变量只取正值即非负值）,

4、运筹学基础及应用线性规划及单纯形法,9,数学模型,线性规划数学模型三要素：,决策变量、约束条件、目标函数,运筹学基础及应用线性规划及单纯形法,10,一般形式：,目标函数：,约束条件：,运筹学基础及应用线性规划及单纯形法,11,简写形式：,目标函数：,约束条件：,运筹学基础及应用线性规划及单纯形法,12,向量形式：,目标函数：,约束条件：,若,运筹学基础及应用线性规划及单纯形法,13,矩阵形式表示为：,其中：,目标函数：,约束条件：,运筹学基础及应用线性规划及单纯形法,14,1-3 线性规划问题的标准型,规定线性规划标准形式为,运筹学基础及应用线性规划及单纯形法,15,线性规划标准型的特点：,求

5、目标函数的 max,约束条件中为“=”,右端常数 bi 0,决策变量 xj 0,注意：有些课本上规定标准形式的目标函数取最小值,运筹学基础及应用线性规划及单纯形法,16,线性规划问题的标准型 (2)：,运筹学基础及应用线性规划及单纯形法,17,线性规划问题的标准型(3)：,运筹学基础及应用线性规划及单纯形法,18,b. 约束条件标准化,(1) 约束条件是 类型,如何将一般问题化为标准型：,a. 目标函数标准化,左边 加 非负松弛变量,(2) 约束条件是 类型,左边 减 非负剩余变量,运筹学基础及应用线性规划及单纯形法,19,(3) 变量符号无约束,(4) 变量 xi 0,引入新变量,(5) 右

6、端常数 bi 0,等式两边乘以（-1）,运筹学基础及应用线性规划及单纯形法,20,例1.3 将下述规划模型化为标准型:,运筹学基础及应用线性规划及单纯形法,21,解：,运筹学基础及应用线性规划及单纯形法,22,运筹学基础及应用线性规划及单纯形法,23,课堂练习1 将下列问题化成标准型:,运筹学基础及应用线性规划及单纯形法,24,运筹学基础及应用线性规划及单纯形法,25,课堂练习2,运筹学基础及应用线性规划及单纯形法,26,课堂练习3,运筹学基础及应用线性规划及单纯形法,27,1-4 线性规划问题的解,可行解 最优解,满足目标函数（1.6a）的可行解x，称为线性规划的问题最优解,满足约束条件（1

7、.6b）与（1.6c）的x，称为线性规划的问题可行解,运筹学基础及应用线性规划及单纯形法,28,线性规划问题的标准型 (2)：,运筹学基础及应用线性规划及单纯形法,29,基、基向量、基变量 设 r(a) = m,并且b是a的m 阶非奇异 的子矩阵（det(b) 0),则称矩阵 b为 线性规划问题的一个基。,矩阵 b =（p1，p2.pm) ，其列向量 pj 称为对应基b的基向量。,与基向量 pj 相对应的变量xj 就称为 基变量，其余的就称为非基变量。,运筹学基础及应用线性规划及单纯形法,30,基解.基可行解.可行基 对于某一特定的基b，非基变量取 0 值的解，称为基解。,运筹学基础及应用线性

8、规划及单纯形法,31,基解.基可行解.可行基 对于某一特定的基b，非基变量取 0值的解，称为基解。 满足非负约束条件的基解，称为 基可行解。,运筹学基础及应用线性规划及单纯形法,32,基解.基可行解.可行基 对于某一特定的基b，非基变量取 0值的解，称为基解。 满足非负约束条件的基解，称为 基可行解。 与基可行解对应的基，称为可行基,运筹学基础及应用线性规划及单纯形法,33,max z=2x1+3x2 st. x1+x23 x1+2x24 x1, x20,max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2 , x3 , x40

9、,a=,x1 x2 x3 x4,1 1 1 0 1 2 0 1,可行解：x=(0，0)t，x=(0，1)t，x=(1/2，1/3)t 等。,设,b=,1 0 0 1,，令,，则,| b |=10,令 x1=x2 =0，则 x3 =3, x4=4，x=(0,0,3,4)t,例：,x3 x4,基变量,令,b=,1 1 1 0,x1 x3,，则,令 x2=x4 =0，则 x3 =-1, x1=4，x=(4,0,-1,0)t,| b |=-10,非基本可行解,基本可行解,标准化,运筹学基础及应用线性规划及单纯形法,34,注意问题：,基解的个数不超过 ，并且,基解中非零分量的个数不大于m,为什么？,因为

10、基的个数不超过,运筹学基础及应用线性规划及单纯形法,35,解的集合：,非可行解,可行解,运筹学基础及应用线性规划及单纯形法,36,解的集合：,基解,运筹学基础及应用线性规划及单纯形法,37,解的集合：,可行解,基解,基可行解,运筹学基础及应用线性规划及单纯形法,38,解的集合：,可行解,基解,基最优解,基可行解,运筹学基础及应用线性规划及单纯形法,39,最优解,基本最优解,运筹学基础及应用线性规划及单纯形法,40,例1.4：举例说明什么是基、基变量、基 解、基可行解和可行基。,运筹学基础及应用线性规划及单纯形法,41,解：写出约束方程组的系数矩阵a 2 2 1 0 0 0 a= 1 2 0 1

11、 0 0 4 0 0 0 1 0 0 4 0 0 0 1,运筹学基础及应用线性规划及单纯形法,42,解：写出约束方程组的系数矩阵a 2 2 1 0 0 0 b = ( p3, p4, p5, p6 ) a= 1 2 0 1 0 0 1 0 0 0 4 0 0 0 1 0 = 0 1 0 0 0 4 0 0 0 1 0 0 1 0 0 0 0 1,运筹学基础及应用线性规划及单纯形法,43,解：写出约束方程组的系数矩阵a 2 2 1 0 0 0 b = ( p3, p4, p5, p6 ) a= 1 2 0 1 0 0 1 0 0 0 4 0 0 0 1 0 = 0 1 0 0 0 4 0 0 0

12、 1 0 0 1 0 0 0 0 1,可见矩阵a的秩不大于4，而 矩阵b为4 4满矩阵，故 ( p3, p4, p5, p6 ) 为上述问题的一个基。,而与 其对应的 变量 x3, x4, x5, x6 是基变量，x1, x2 是非基变量,运筹学基础及应用线性规划及单纯形法,44,又因为该基解中所有变量取值为非负, 故它又是基可行解。,在约束方程中令 x1 = x2 = 0，可解得 x3 = 12, x4 = 8, x5 = 16, x6 = 12, 由此x=( 0, 0, 12, 8, 16 )t 是这个线性 规划问题的一个基解。,因而与这个基可行解对应的基 ( p3, p4, p5, p6

13、 )是一个可行基。,作业：习题1.2（b）,运筹学基础及应用线性规划及单纯形法,45,. 图解法,（1）满足约束条件的变量的值，称 为可行解。,（2）使目标函数取得最优值的可行解，称为最优解。,运筹学基础及应用线性规划及单纯形法,46,图解法的特点 优点：直观性强，计算方便。 缺点：只适用于问题中有两个变量的情况。,注意：不要求模型为标准型。,运筹学基础及应用线性规划及单纯形法,47,求解下述线性规划问题：,运筹学基础及应用线性规划及单纯形法,48,x1,x2,2,2,4,6,8,4,6,0,z=6,z=0,(4,2),zmax,运筹学基础及应用线性规划及单纯形法,49,目标函数的几何意义：,

14、表示一族平行的等值线族，位于同一条直线上的点具有相同的目标函数值, 可以把z看成是二元函数,运筹学基础及应用线性规划及单纯形法,50,最优解的确定：,运筹学基础及应用线性规划及单纯形法,51,图解法的步骤：,建立坐标系，将约束条件在图上表示； 确立满足约束条件的解的范围； 绘制出目标函数的图形； 确定最优解。,运筹学基础及应用线性规划及单纯形法,52,无穷多最优解的情况：,目标函数与某个约束条件恰好平行,运筹学基础及应用线性规划及单纯形法,53,无界解（或无最优解）的情况：,可行域上方无界,运筹学基础及应用线性规划及单纯形法,54,无可行解的情况：,约束条件不存在公共范围,运筹学基础及应用线性

15、规划及单纯形法,55,步骤：（1）作平面直角坐标系，标上刻度；（2）做出约束方程所在直线，确定可行域；（3）做出一条目标函数等值线，判定优化方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优解，并 计算最优值。,讨论一：模型求解时，可得到如下几种解的状况：（1）唯一最优解：只有一点为最优解点，简称唯一解；（2）无穷多最优解：有许多点为最优解点，简称无穷多解；（3）无界最优解：最优解取值无界，简称无界解; （4）无可行解：无可行域，模型约束条件矛盾。,讨论二：lp模型求解思路：（1）若lp模型可行域存在，则为一凸形集合；（2）若lp模型最优解存在，则其应在其可行域顶点上找到；（3）顶点与

16、基本解、基本可行解的关系：,运筹学基础及应用线性规划及单纯形法,56,利用图解法求解如下的数学模型,运筹学基础及应用线性规划及单纯形法,57,50,40,30,20,10,10,20,30,40,围成的区域,运筹学基础及应用线性规划及单纯形法,58,10,20,30,40,50,40,30,20,10,由 围成的区域,运筹学基础及应用线性规划及单纯形法,59,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,4x1+3x2 120,可行域,同时满足： 2x1+x2 50 4x1+3x2 120 x1 0 x2 0 的区域可行域,运筹学基础及应用线性规划及单纯

17、形法,60,x2,50,40,30,20,10,10,20,30,40,x1,可行域,o（0，0）,q1（25，0）,q2（15，20）,q3（0，40）,可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。 该问题的可行域是由o，q1，q2，q3作为顶点的凸多边形,运筹学基础及应用线性规划及单纯形法,61,x1,x2,50,40,30,20,10,10,20,30,40,可行域,目标函数是以z作为参数的一组平行线 x2 = z/30-（5/3）x1,运筹学基础及应用线性规划及单纯形法,62,x2,50,40,30,20,10,10,20,30,40,x1,可行

18、域,当z值不断增加时，该直线 x2 = z/30-（5/3）x1 沿着其法线方向向右上方移动。,运筹学基础及应用线性规划及单纯形法,63,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当该直线移到q2点时，z（目标函数）值达到最大： max z=50*15+30*20=1350 此时最优解=（15，20）,q2（15，20）,运筹学基础及应用线性规划及单纯形法,64,二个重要结论： 满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。,最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。,运筹学基础及应用线性规划及单纯

19、形法,65,解的讨论：,无可行解.,无穷多组最优解;,无界解;,最优解是唯一解；,可行解,运筹学基础及应用线性规划及单纯形法,66,无穷多组最优解：,若上题中的目标函数由,变为,约束条件保持不变，即,运筹学基础及应用线性规划及单纯形法,67,x2,运筹学基础及应用线性规划及单纯形法,68,运筹学基础及应用线性规划及单纯形法,69,无界解,运筹学基础及应用线性规划及单纯形法,70,运筹学基础及应用线性规划及单纯形法,71,无可行解：,该问题可行域为空集，即无可行解，也不存在最优解。,运筹学基础及应用线性规划及单纯形法,72,10,8,6,4,2,2,4,6,8,x1,x2 3,x1+ 2x2 8

20、,x1 4,x2,-2x1+x24,运筹学基础及应用线性规划及单纯形法,73,解的情况： 有可行解 有唯一最优解 有无穷最优解 无最优解( 无界解 ) 无可行解,运筹学基础及应用线性规划及单纯形法,74,. 单纯形法原理 -1 预备知识：凸集和顶点 凸集概念： 设c是n维线性空间rn的一个点集，若c中的任意两点x、x的连线上的所有点仍在c中，称c为凸集。,即：对任何 则称c为凸集,运筹学基础及应用线性规划及单纯形法,75,例：凸集,运筹学基础及应用线性规划及单纯形法,76,例：非凸集,运筹学基础及应用线性规划及单纯形法,77,例：凸集性质 二个凸集的交还是凸集,二个凸集的并不一定是凸集,运筹学

21、基础及应用线性规划及单纯形法,78,顶点： 设c是凸集, 若c中的点x不能成为d中任何线段上的内点，则称x为凸集c的顶点。 即：对任何x、xc，不存在x = x+(1- ) x（01 ）, 则称x为凸集c的一个顶点。,运筹学基础及应用线性规划及单纯形法,79,例 多边形上的点a、b、c、d、e是顶点,圆周上的点都是顶点,a,b,e,c,d,运筹学基础及应用线性规划及单纯形法,80,定理1：若线性lp模型存在可行解，则可行域为凸集。,证明：设 max z=cx st.ax=b x0,并设其可行域为c，若x1、x2为其可行解，且x1x2 ， 则 x1c，x2 c， 即ax1=b，ax2=b，x10

22、，x20，,又 x为x1、x2连线上一点，即 x=x1+(1-)x2c， (01)， ax=ax1+ (1-)ax2 = b+ (1-)b =b , (01)，且 x 0， x c， c为凸集。,-2 线性规划问题基本定理,运筹学基础及应用线性规划及单纯形法,81,引理：线性规划问题的可行解x=(x1, x2,xn)t 为基本可行解的充要条件是x的正分量所对应的系数列向量线性独立。,证： （1）必要性：x基本可行解x的正分量所对应的系数列向量线性独立 可设x=(x1,x2,xk,0,0,0)t，若x为基本可行解，显然，由基本可行解定义可知x1, x2,xk所对应的系数列向量p1,p2,pk应该

23、线性独立。,（2）充分性： x的正分量所对应的系数列向量线性独立 x为基本可行解 若a的秩为m，则x的正分量的个数km； 当k=m时，则x1,x2,xk的系数列向量p1,p2,pk恰好构成基， x为基本可行解。 当km时，则必定可再找出m-k个列向量与p1,p2,pk一起构成基， x为基本可行解。,运筹学基础及应用线性规划及单纯形法,82,证：用反证法 x非基本可行解x非凸集顶点 （1）必要性：x非基本可行解 x非凸集顶点 不失一般性，设x=(x1,x2,xm,0,0,0)t，为非基本可行解， x为可行解，, pjxj=b，,j=1,n,即 pjxj=b (1),j=1,m,又 x是非基本可行

24、解， p1,p2,pm线性相关，即有 1p1+2p2+mpm=0， 其中1，2，m不全为0，两端同乘0，得 1p1+2p2+mpm=0，（2）,定理2：线性规划模型的基本可行解对应其可行域的顶点。,运筹学基础及应用线性规划及单纯形法,83,由 (1)+(2)得 (x1+ 1)p1+ (x2+ 2)p2+ (xm+ m)pm=b 由 (1)-(2)得 (x1 -1)p1+ (x2 - 2)p2+ (xm -m)pm=b,令x1=(x1+ 1，x2+ 2，xm+ m，0， ，0)t x2=(x1- 1，x2- 2，xm- m ，0，0)t 取充分小,使得 xj j0， 则 x1、x2均为可行解，

25、但 x=0.5x1+(1-0.5)x2， x是x1、x2连线上的点， x非凸集顶点。,运筹学基础及应用线性规划及单纯形法,84,（2）充分性： x非凸集顶点 x非基本可行解,设x=(x1,x2,xr,0,0,0)t为非凸集顶点，则必存在y、z两点，使得,x=y+(1-)z，(01)，且y、z为可行解 或者 xj=yj+(1-)zj (01)，（j=1,2,n)， yj0，zj0, 0, 1-0 ，当xj=0， 必有yj=zj=0, pjyj =,j=1,n, pjyj=b (1),j=1,r, pjzj =,j=1,n, pjzj=b (2),j=1,r, (yj-zj)pj=0,j=1,r,

26、(1)-(2),得,即,(y1 - z1)p1+ (y2 - z2)p2+ (yr -zr)pr=0,运筹学基础及应用线性规划及单纯形法,85, y、z为 p1,p2,pr线性相关， x非基本可行解。 不同两点， yj-zj不全为0，,运筹学基础及应用线性规划及单纯形法,86,从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。,运筹学基础及应用线性规划及单纯形法,87,z1=cx1=cx0-c=zmax-c ，z2=cx2=cx0+c =zmax+c z0 = zmax z1 ， z0 = zmax z2 ， z

27、1 = z2 = z0 ，即 x1 、 x2也为最优解， 若x1、x2仍不是顶点，可如此递推，直至找出一个顶点为最优解。 从而，必然会找到一个基本可行解为最优解。,定理3：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。,证：设 x0=(x10, x20,xn0)t 是线性规划模型的一个最优解， z0=zmax=cx0 若x0非基本可行解，即非顶点，只要取充分小， 则必能找出x1= x0-0 ，x2 = x0 +0 ，即x1 、 x2为可行解，,运筹学基础及应用线性规划及单纯形法,88,单纯形法的计算步骤：,初始基本可行解,新的基本可行解,最优否？,stop,y,n,运筹学基础及应用

28、线性规划及单纯形法,89,1947年丹捷格提出的单纯形法为求解线性规划问题提供了方便、有效的通用算法。,单纯形法原理,运筹学基础及应用线性规划及单纯形法,90,一、单纯形法的基本思想,顶点的逐步转移： 即从可行域的一个顶点（基可行解）开始，转移到另一个顶点（另一个基可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优） ，当目标函数达到最优值时，问题也就得到了最优解。,需要解决的问题：,为了使目标函数逐步变优，怎么转移？ 目标函数何时达到最优，判断标准是什么？,运筹学基础及应用线性规划及单纯形法,91,二、单纯形法原理,-3 确定初始基可行解,当线性规划的约束条件全部为“”时，可按照

29、如下 方法寻找初始基可行解,运筹学基础及应用线性规划及单纯形法,92,第一步：引入非负的松弛变量， 将该lp化为标准型,运筹学基础及应用线性规划及单纯形法,93,第二步：寻求初始可行基，确定基变量,运筹学基础及应用线性规划及单纯形法,94,第二步：寻求初始可行基，确定基变量,运筹学基础及应用线性规划及单纯形法,95,第二步：寻求初始可行基，确定基变量,运筹学基础及应用线性规划及单纯形法,96,第二步：寻求初始可行基，确定基变量,对应的基变量是,运筹学基础及应用线性规划及单纯形法,97,第三步：写出初始基本可行解和相应的目标函数值,以这个单位矩阵作为基解得,于是 就是基本可行解,注意：当线性规划

30、的约束条件是“=”或者“”时，可人为的添加人工变量构造一个单位矩阵作为基，这种方法我们在第5节中介绍,运筹学基础及应用线性规划及单纯形法,98,-4 从一个基本可行解向另一个基本可行解转换,不失一般性，设基本可行解x0=(x10, x20,xm0,0,0)t ， 前m个分量为正值，秩为m，其系数矩阵为,p1 p2 pm pm+1 pj pn b 1 0 0a 1,m+1 a1j a 1n b1 0 1 0 a 2,m+1 a2j a 2nb2 0 0 1a m,m+1 amj a mn bm, pjxj0 =,j=1,n, pixi0=b (1),i=1,m,运筹学基础及应用线性规划及单纯形法

31、,99,又p1 p2 pm为一个基，任意一个非基向量pj可以以该组向量线性组合表示，即 pj = a1j p1 + a2j p2 + amj pm ，即 pj = aij pi ， 移项，两端同乘0 ，有 (pj- aij pi )=0 (2),i=1,m,i=1,m,(1)+(2)： (xi 0- aij)pi + pj =b， 取充分小，使所有xi 0 - aij 0，从而,i=1,m,x1 = (x1 0- a1j ,x2 0- a2j ,xm 0- amj ,0,0)t,也是可行解。,当取 = min aij 0 = ，则x1的前m个分量至少有一个xl1为0。,xi 0,aij,alj

32、,xl 0,i, p1 , p2,pl-1, pl+1, pm, pj 线性无关。,运筹学基础及应用线性规划及单纯形法,100, x1 也为基本可行解。,3.最优解的判别,依题义,z0 = cjxj0 =ci xi0,i=1,m,j=1,n,z1 = cjxj1 =ci(xi 0- aij) + cj ,i=1,m,j=1,n,=cixi 0+ (cj - ciaij)= z0 + j,i=1,m,i=1,m,运筹学基础及应用线性规划及单纯形法,101,因0，所以有如下结论：,(1) 对所有j，当 j0 ，有z1 z0 ，即z0为最优值，x0为最优解； (2) 对所有j，当j0 ，但存在某个非

33、基变量k=0，则对此pk作 为新基向量得出的解x1 ，应有z1 = z0 ，故z1 也为最优值， 从而 x1为最优解，且为基本可行解， x0、x1 连线上所有的点均为最优解，因此该线性规划模型 具有无穷多解； (3) 若存在某个j 0，但对应aij0，则因当 时，有z1 ， 该线性规划模型具有无界解。,运筹学基础及应用线性规划及单纯形法,102,最优性检验与解的判别:,有最优解 ( 所有 ), 有唯一最优解 (所有 ), 有无穷最优解 (存在 ),无界解(存在某个 , 而 ),考虑问题：若目标函数 是求最小值，应该怎样 判别得到最优解？,有最优解 ( 所有 ), 有唯一最优解 (所有 ), 有

34、无穷最优解 (存在 ),无界解(存在某个 , 而 ),运筹学基础及应用线性规划及单纯形法,103,4. 单纯形法的计算步骤,表格单纯形法：,1、初始单纯形表的建立,(1)表格结构：,运筹学基础及应用线性规划及单纯形法,104,（2）表格设计依据：,设 , 把目标函数表达式改写成方程的 形式, 和原有的m个约束方程组成一个具有n+1个变量、 m+1个方程的方程组：,运筹学基础及应用线性规划及单纯形法,105,（2）表格设计依据：,设 , 把目标函数表达式改写成方程的 形式, 和原有的m个约束方程组成一个具有n+1个变量、 m+1个方程的方程组：,运筹学基础及应用线性规划及单纯形法,106,取出系

35、数写成增广矩阵的形式：,-z x1 x2 xm xm+1 xm+2 xn b,-z，x1，xm所对应的系数列向量构成一个基,运筹学基础及应用线性规划及单纯形法,107,用矩阵的初等行变换将该基变成单位阵,这时 变成0 ，相应的增广矩阵变成如下形式：,其 中,运筹学基础及应用线性规划及单纯形法,108,用矩阵的初等行变换将该基变成单位阵,这时 变成0 ，相应的增广矩阵变成如下形式：,其 中,运筹学基础及应用线性规划及单纯形法,109,？,运筹学基础及应用线性规划及单纯形法,110,增广矩阵的最后一行就是用 非基变量表示目标函数的表达式, (j=1,2,n)就是非基变量的 检验数。,运筹学基础及应

36、用线性规划及单纯形法,111,（3）检验数的两种计算方法：, 利用矩阵的行变换，把目标函数表达式中基变 量前面的系数变为0；, 使用计算公式,运筹学基础及应用线性规划及单纯形法,112,最优性检验与解的判别:,有最优解 ( 所有 ), 有唯一最优解 (所有 ), 有无穷最优解 (存在 ),无界解(存在某个 ,而 ),运筹学基础及应用线性规划及单纯形法,113,表格单纯形法： 1、 初始单纯形表的建立,2、表格单纯形法计算过程：,运筹学基础及应用线性规划及单纯形法,114,2、表格单纯形法计算过程：,运筹学基础及应用线性规划及单纯形法,115,2、表格单纯形法计算过程：,第一步：求出初始基可行解

37、, 列出初始单纯形表.,运筹学基础及应用线性规划及单纯形法,116,运筹学基础及应用线性规划及单纯形法,117,2、表格单纯形法计算过程：,第一步：求出初始基可行解, 列出初始单纯形表.,第二步：进行最优性检验.,若所有 , 则停止, 否则转下一步.,第三步：求从一个基可行解转换到另一个基可行解, 列出新的单纯形表.,运筹学基础及应用线性规划及单纯形法,118,(1) 确定换入变量: , 与其对应的 作为 换入变量.,第三步：,运筹学基础及应用线性规划及单纯形法,119,(1) 确定换入变量: , 与其对应的 作为换入变量.,(2) 确定换出变量: , 与其对应的 作为换出变量.,称主元素,

38、决定了转移去向.,第三步：,运筹学基础及应用线性规划及单纯形法,120,(1) 确定换入变量: , 与其对应的 作为换入变量.,(2) 确定换出变量: , 与其对应的 作为换出变量.,(3)：列出新的单纯形表.,称主元素, 决定了转移去向.,第三步：,运筹学基础及应用线性规划及单纯形法,121,运筹学基础及应用线性规划及单纯形法,122,是换入基, 是换出基, 是主元素.,运筹学基础及应用线性规划及单纯形法,123,是换入基, 是换出基, 是主元素.,运筹学基础及应用线性规划及单纯形法,124,是换入基, 是换出基, 是主元素.,运筹学基础及应用线性规划及单纯形法,125,a: 改变 所在行的

39、向量.,运筹学基础及应用线性规划及单纯形法,126,alj/alk,aln/alk,a: 改变 所在行的向量.,运筹学基础及应用线性规划及单纯形法,127,b: 改变其他行的向量.,公式:,用新表中第 l 行的数字乘上, 加到原表第 i 行上, 即为新表的第 i 行.,运筹学基础及应用线性规划及单纯形法,128,b: 改变其他行的向量.,alj/alk,aln/alk,运筹学基础及应用线性规划及单纯形法,129,alj/alk,aln/alk,运筹学基础及应用线性规划及单纯形法,130,alj/alk,aln/alk,c: 在新表中计算出 , 进行最优解检验.,运筹学基础及应用线性规划及单纯形

40、法,131,alj/alk,aln/alk,c: 在新表中计算出 , 进行最优解检验.,运筹学基础及应用线性规划及单纯形法,132,单纯形法的计算及示例,化为标准形式,运筹学基础及应用线性规划及单纯形法,133,cj ,x1,x2,x3,x4,xb,b,cb,1 1 1 0 1 2 0 1,2 3 0 0,34,x3 x4,00,cj - zj,2,3,0,0,3/1=3,4/2= 2,x3 x2,cj - zj,03,x1 x2,cj - zj,0 0 -1 -1,23,i,1,1/2,0,1/2,2,0,1/2,1,-1/2,1,1/2,0,0,-3/2,2,4,1,0,2,-1,2,0,

41、1,-1,1,1,单纯形法计算：,运筹学基础及应用线性规划及单纯形法,134,单纯形法计算过程总结：,（1）化标准形，列初始单纯形表；,（2）计算检验数： j =z=cj-zj = cj- ciaij,（3）最优性判断：当所有检验数均有j 0时，则为最优解。否则迭代求新的基本可行解。,（4）迭代：入基变量：取maxj 0 = kxk出基变量：取min i=bi/aik aik0= l x(l)主元素： alk 新单纯表：pk=单位向量,注：当所有检验数j 0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。,i=1,m,运筹学基础及应用线性规划及单纯形法,135,5单纯形法的进

42、一步讨论,5-1 大m法,化标准形为：,运筹学基础及应用线性规划及单纯形法,136,它的系数矩阵是：,由于系数矩阵中存在单位阵，很容易找到初始可行基。,运筹学基础及应用线性规划及单纯形法,137,化为标准型：,该问题的系数矩阵为：,在系数矩阵中人为添 加两列单位列向量,运筹学基础及应用线性规划及单纯形法,138,目标函数变为：,引进人工变量，及m非常大正系数,运筹学基础及应用线性规划及单纯形法,139,(1),(2),这种处理方法称为大m法，以下则可完全按单纯形法求解。,运筹学基础及应用线性规划及单纯形法,140,cj ,-3 0 1 0 0 -m -m,cb,xb,b,x1,x2,x3,x4

43、,x5,x6,x7,x4 x6x7,0 -m -m,4 1 9,1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0 1,cj - zj,-2m-3,4m,1,0,0,0,-m,i,4/1=4,1/1=1,9/3=3,x4 x2x7,0 0 -m,-2 1 -1 0 -1 1 0,3,0,1,3,2,1,1,-1,0,6,6,0,4,0,3,1,-3,cj - zj,6m-3,0,4m+1,0,3m,-4m,0,3/3=1,-,6/6=1,这里为什么不选择x4 作为换出变量而选择x7？,x4 x2x1,0 0 1,1,2/3,0,1,-1/2,1,0,3,1,0

44、,1/2,-1/2,1/6,0,0,0,1/3,1/3,0,0,0,0,-1/2,-1/2,cj - zj,0,0,0,3,-m-3/2,2/3,-m+1/2,-,9,6,运筹学基础及应用线性规划及单纯形法,141,cj ,-3 0 1 0 0 -m -m,cb,xb,b,x1,x2,x3,x4,x5,x6,x7,x4 x2x3,0 0 1,cj - zj,-3/2,0,0,-m+3/4,1,3/2,0,1,5/2,0,1,0,1/4,-1/2,1/2,0,0,0,-3/4,0,0,0,-1/2,-1/2,3/4,3/2,-1/4,1/4,1/4,-3/4,-m-1/4,运筹学基础及应用线性规

45、划及单纯形法,142,(1) 当所有的检验数 ,并且单纯形表基变量没有取值非零的人工变量时，表明已经得到原问题的最优解,大m法判别准则,(2) 当所有的检验数 ,并且单纯形表基变量有取值非零的人工变量时，表明已经得到原问题无可行解,(3) 若所解的大m问题有无界解(即有可行解但无最优解),则当人工变量全为零时，原问题无界解；当人工变量不全为零，表明原问题无可行解；,运筹学基础及应用线性规划及单纯形法,143,min z=2x1+3x2 max z=-2x1-3x2+0 x3 x1+x2 3 标准化 s.t x1+x2 -x3=3 x1+2x2 = 4 x1+2x2=4 x10, x20 xj0

46、, (j=1,2,3,4),max z=-2x1-3x2+0 x3 -m x4-m x5 s.t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj0, (j=1,2,3,4,5),引进人工变量，及m非常大正系数，模型转变为,运筹学基础及应用线性规划及单纯形法,144,cj ,x1,x2,x3,x4,xb,b,cb,1 1 -1 1 0 1 2 0 0 1,-2 -3 0 -m -m,34,x4 x5,-m -m,cj - zj,-2+2m,-3+3m,-m,0,3/1=3,4/2= 2,1/2 0 -1 1 -1/2 1/2 1 0 0 1/2,x4 x2,12,cj - z

47、j,-1/2+m/2 0 -m 0 3/2-m/2,-m -3,24,1 0 -2 2 -1 0 1 1 -1 1,x1 x2,21,cj - zj,0 0 -1 -1-m -1-m,-2 -3,i,x5,0,运筹学基础及应用线性规划及单纯形法,145,原问题化为标准形式后的约束条件,添加了人工变量以后的约束条件,5-2 两阶段法,运筹学基础及应用线性规划及单纯形法,146,(1) 第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解，若zmin=0 ，表明原问题有可行解，则可进入第二阶段，求原模型最优解。,运筹学基础及应用线性规划及单纯形法,147,0,2/3,cj ,0 0 0 0 0

48、 -1 -1,cb,xb,b,x1,x2,x3,x4,x5,x6,x7,x4 x6x7,0 -1 -1,4 1 9,1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0 1,cj - zj,-2,4,0,0,0,0,-1,i,4/1=4,1/1=1,9/3=3,x4 x2x7,0 0 -1,-2 1 -1 0 -1 1 0,3,0,1,3,2,1,1,-1,0,6,6,0,4,0,3,1,-3,cj - zj,6,0,4,0,3,-4,0,3/3=1,-,6/6=1,x4 x2x1,0 0 0,1,0,1,-1/2,1,0,3,1,0,1/2,-1/2,1/6,

49、0,0,0,1/3,1/3,0,0,0,0,-1/2,-1/2,cj - zj,0,0,0,-1,0,-1,运筹学基础及应用线性规划及单纯形法,148,说明 (1) 如果第一阶段求解结果的目标函数最优解为0，表明原线性规划问题存在可行解 (2) 若第一阶段求解结果目标函数最优解不为0，也就是最优解的基变量中含有人工变量，表明原来的线性规划问题无可行解。,于是根据单纯形表可以看出原问题有可行解，原问题的一个可行解为,运筹学基础及应用线性规划及单纯形法,149,3,第二阶段: 将第一阶段最终单纯形表中的人工变量去掉，原问题的目标函数引入最终单纯形表，继续迭代,cj ,-3 0 1 0 0,cb,x

50、b,b,x1,x2,x3,x4,x5,x4 x2x1,0 3 1,0 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2,cj - zj,0,0,3/2,i,-,9,2/3,x4 x2x3,0 0 1,0,0,5/2,0,0,1,-1/2,0,1,0,3/4,cj - zj,0,0,3/2,0,0,0,-1/4,-3/2,00 -3,0,3/2,-1/2,1,-3/4,运筹学基础及应用线性规划及单纯形法,150,min z=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s.t x1+x2 -x3=3 x1+2x2 = 4 x1+2

51、x2=4 x10, x20 xj0, (j=1,2,3,4),max z=-x4-x5 s.t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj0, (j=1,2,3,4,5),第一阶段：构造判断是否存在可行解的模型,用单纯形法求解，若zmin=0 ，表明该模型有可行解，则可进入第二阶段，求原模型最优解。,运筹学基础及应用线性规划及单纯形法,151,cj ,x1,x2,x3,x4,xb,b,cb,1 1 -1 1 0 1 2 0 0 1,0 0 0 -1 -1,34,x4 x5,-1 -1,cj - zj,2,3,-1,0,3/1=3,4/2= 2,1/2 0 -1 1 -1

52、/2 1/2 1 0 0 1/2,x4 x2,12,cj - zj,1/2 0 -1 0 -3/2,-1 0,24,1 0 -2 2 -1 0 1 1 -1 1,x1 x2,21,cj - zj,0 0 0 -1 -1,0 0,i,x5,0,运筹学基础及应用线性规划及单纯形法,152,第二阶段：将原目标函数引入最终单纯形表，继 续迭代 max z=-2x1-3x2+0 x3,cj ,x1,x2,x3,xb,b,cb,1 0 -2 0 1 1,-2 -3 0,21,x1 x2,-2 -3,cj - zj,0,0,-1,运筹学基础及应用线性规划及单纯形法,153,当所有 时，又对某个非基变量 有

53、且可以找到 ，则该线性规划问题有无穷多最优解。,5-3 关于解的判别,例7.,运筹学基础及应用线性规划及单纯形法,154,标准形式为,运筹学基础及应用线性规划及单纯形法,155,用单纯形法计算，得到最终单纯形表为：,从表中可以得到最优解：,它对应的目标函数值为：,运筹学基础及应用线性规划及单纯形法,156,在上表中，非基变量 的检验数为0，如果将 换入基变量，得：,从表中可以得到新的最优解：,因此 和 连线上所有的点都是最优解，该问题有无穷多最优解。,运筹学基础及应用线性规划及单纯形法,157,例8. 求解线性规划问题,解：用图解法求解时知道该问题有无界解，,它的标准形为：,运筹学基础及应用线

54、性规划及单纯形法,158,用单纯形表求解过程如下：,表中 ，但 列数字为零，因此 的取值可无限增大，所以目标函数值也可随之无限增大，说明问题的解无界。,运筹学基础及应用线性规划及单纯形法,159,例9. 求解线性规划问题,将其化为标准形：,运筹学基础及应用线性规划及单纯形法,160,该问题单纯形法求解如下：,当所有 时，人工变量 仍然留在基变量中，而且不为零，故问题无可行解。,运筹学基础及应用线性规划及单纯形法,161,5-4 单纯形法小结,对给定的线性规划问题应首先化为标准形式； 选取或构造一个单位矩阵作为基； 求出初始可行解并列出初始单纯形表； 计算检验数，判断是否最优解； 寻找换入及换出

55、变量，构造新的单纯形表； 求出最优解。,运筹学基础及应用线性规划及单纯形法,162,1.8 已知某线性规划问题的初始单纯形表和用单纯形表 迭代后得到的表(表1.18)，试求括弧中未知数al的值。,运筹学基础及应用线性规划及单纯形法,163,例 用单纯形法解线性规划问题时，有如下二个单纯形表，试把表中数字补全。,cj ,x1,x2,x3,x4,xb,b,cb,1 0 0 1,0 0,3,x3 x4,00,cj - zj,cb xb b,x1 x2 x3 x4,2 -1 -1 1,x1 x2,1,cj - zj,-1 -1,23,运筹学基础及应用线性规划及单纯形法,164,s=(-1，-1)=(3

56、，4)= cs-cb b-1 = -(c1，c2),2 -1 -1 1,1 0 0 1,=-(2c1-c2，-c1+c2),c1=2 c2=3,又 b = b-1 b，,b1 1,2 -1 -1 1,3 b2,6-b2 -3+b2,=,=,b1=2 b2 =4,2 -1 -1 1,1 0 0 1,=,a11 a12 a21 a22,1 0 0 1,=,2a11 - a21 -2a12 - a22 -a11 + a21 -a12 + a22, a11 =1， a12 =1， a21 =1， a22 =2,解：,运筹学基础及应用线性规划及单纯形法,165,简单线性规划模型的建立,步骤：,（2）具体

57、构造模型：选择合适的决策变量、确定目标函数的表达式、约束条件的表达式，分析各变量取值的符号限制。,（1）分析问题：确定决策内容、要实现的目标以及所受到的限制条件。,7. 应用举例,运筹学基础及应用线性规划及单纯形法,166,例11. 工业原料的合理利用,要制作100套钢筋架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原料长7.4m，应如何切割，使用原料最节省（仍掉的料头最小）。,考察如下方案的综合使用：,运筹学基础及应用线性规划及单纯形法,167,解：该问题的线性规划数学模型如下,运筹学基础及应用线性规划及单纯形法,168,该问题要用单纯形法求解，需要添加人工变量：,利用大 m 法求解，得到：,运筹学基础及应用线性规划及单纯形法,169,例12. 混合配料问题,某糖果厂用原料a、b、c 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中a、b、c 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表，问该厂每月生产这三种牌号糖果各多少千克，使该