运筹学(线性规划)_第1页
运筹学(线性规划)_第2页
运筹学(线性规划)_第3页
运筹学(线性规划)_第4页
运筹学(线性规划)_第5页
已阅读5页,还剩133页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

page1德州学院数学科学学院运筹学教案运筹帷幄之中决胜千里之外线性规划LinearProgramming线性规划介绍历史悠久,理论成熟,应用广泛运筹学的最基本的方法之一,网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法,使付出的费用最小或获得的收益最大。page2线性规划理论的发展:1939年前苏联康托洛维奇(KOHTOPOBUZ)《生产组织与计划中的数学方法》提出“解乘数法”。线性规划介绍列奥尼德·康托罗维奇,前苏联人,由于在1939年创立了享誉全球的线形规划要点,对资源最优分配理论做出了贡献,而获得诺贝尔经济学奖。page3美国科学院院士DANTZIG(丹齐克),1948年在研究美国空军资源的优化配置时提出线性规划及其通用解法“单纯形法”。被称为线性规划之父。线性规划介绍

线性规划之父的Dantzig(丹齐克)。据说,一次上课,Dantzig迟到了,仰头看去,黑板上留了几个几个题目,他就抄了一下,回家后埋头苦做。几个星期之后,疲惫的去找老师说,这件事情真的对不起,作业好像太难了,我所以现在才交,言下很是惭愧。几天之后,他的老师就把他召了过去,兴奋的告诉他说他太兴奋了。Dantzig很不解,后来才知道原来黑板上的题目根本就不是什么家庭作业,而是老师说的本领域的未解决的问题,他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。

page4线性规划介绍

1960年,“最佳资源利用的经济计算”康托洛维奇和库伯曼斯(Koopmans)。两人因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖

佳林·库普曼斯,美国人,他将数理统计学成功运用于经济计量学,对资源最优分配理论做出了贡献。page51961年,查恩斯与库伯提出了目标规划,艾吉利提出了用优先因子来处理多目标问题。20世纪70年代,斯.姆.李与杰斯开莱尼应用计算机处理目标规划问题。计算机50约束100变量

30000约束3000000变量线性规划介绍page6从1964年诺贝尔奖设经济学奖后,到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作,其中著名的有Simon,Samullson,Leontief,Arrow,Miller等。线性规划介绍保罗-萨缪尔逊(PAULASAMUELSON),他发展了数理和动态经济理论,将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里·列昂惕夫(WASSILYLEONTIEF),美国人,他发展了投入产出方法,该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗(KENNETHJ.ARROW),美国人,因与约翰-希克斯(JOHNR.HICKS)共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒(MERTONM.MILLER),1923-2000,美国人,由于他在金融经济学方面做出了开创性工作,于1990年获得诺贝尔经济奖。page7线性规划介绍线性规划研究的主要问题:有一定的人力、财力、资源条件下,如何合理安排使用,效益最高?某项任务确定后,如何安排人、财、物,使之最省?

page8线性规划(LinearProgramming)

LP的数学模型图解法单纯形法单纯形法的进一步讨论-人工变量法

LP模型的应用本章主要内容:page9生产和经营管理中经常提出如何合理安排,使人力、物力等各种资源得到充分利用,获得最大的效益,这就是规划问题。线性规划通常解决下列两类问题:(1)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标(2)在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大.)线性规划问题的数学模型1.规划问题page10

例1美佳公司计划制造I,II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表I—l所示。问该公司应制造A、B两种家电各多少件,使获取的利润为最大?项目III每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润(元)21线性规划数学模型page11目标函数约束条件解:用变量x1和x2分别表示美佳公司制造家电I和II的数量。项目III每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润(元)21例1用数学语言描述线性规划数学模型page12例2捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随合同期定,期限越长折扣越大,具体数字见下表。租借仓库的合同每月初都可办理,每份台同具体现定租用面积数和期限。因此该厂可根据需要,在任何一个月初办理租借台同。每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小。月份1234所需仓库面积15102012合同租借期限1个月2个月3个月4个月合同期内的租费2800450060007300线性规划数学模型page13解:设变量xij表示捷运公司在第i(i=1.…,4)个月初签订的租借期为j〔j=1,…,4)个月的仓库面积的合同(单位为100m2)。约束条件目标函数例2月份1234所需仓库面积15102012合同租借期限1个月2个月3个月4个月合同期内的租费2800450060007300线性规划数学模型page14线性规划问题的数学模型page15xa例3如图所示,如何截取x使铁皮所围成的容积最大?线性规划问题的数学模型page16例4

某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定,单件产品在不同设备上加工所需要的台时如下表所示,企业决策者应如何安排生产计划,使企业总的利润最大?设备产品ABCD利润(元)

2

1

4

0

2

2

2

0

4

3有效台时12

81612线性规划问题的数学模型page17解:设x1、x2分别为甲、乙两种产品的产量,则数学模型为:maxZ=2x1+3x2

x1≥0,x2≥0s.t.

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12运输问题page18问题分析page19模型page20

AB备用资源煤1230

劳动日3260

仓库0224

利润4050求:最大利润的生产计划。练习1生产计划问题线性规划数学模型page21maxZ=40x1+50x2解:设产品A,B产量分别为变量x1

,x2x1

+2x2

303x1+2x2

602x2

24x1,x2

0s.t.线性规划数学模型page22求:最低成本的原料混合方案?

原料ABC每单位成本

14102261253171642538

每单位添加剂中维生12148

素最低含量练习2混合配料问题线性规划数学模型page23

原料ABC每单位成本

14102261253171642538

每单位添加剂中维生12148

素最低含量

原料ABC每单位成本

14102261253171642538

每单位添加剂中维生12148

素最低含量解:设每单位添加剂中原料i的用量为xi(i=1,2,3,4)minZ=2x1

+5x2+6x3+8x44x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)线性规划数学模型page24s.t.2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是:(1)问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;(2)问题的约束条件是一组多个决策变量的线性不等式或等式。

怎样辨别一个模型是线性规划模型?

线性规划问题的数学模型page25线性规划问题的数学模型page26目标函数:约束条件:3.线性规划数学模型的一般形式简写为:注释page27概念page28线性规划问题的数学模型page29向量形式:其中:线性规划问题的数学模型page30矩阵形式:其中:比例性:决策变量变化引起目标的改变量与决策变量改变量成正比;可加性:每个决策变量对目标和约束的影响独立于其它变量;连续性:每个决策变量取连续值;确定性:线性规划中的参数aij,bi,ci为确定值。隐含的假设线性规划数学模型page31线性规划的适用情况要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件线性规划数学模型page32线性规划问题的数学模型page333.线性规划问题的标准形式特点:(1)目标函数求最大值(有时求最小值)(2)约束条件都为等式方程,且右端常数项bi都大于或等于零(3)决策变量xj为非负。规范形式page34线性规划问题的数学模型模型转换约束转换目标转换变量转换实例page35约束转换不等式变等式等式变不等式不等式变不等式page36不等式变等式松弛变量剩余变量page37不等式变不等式page38例5:将minZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1,x20,x3无限制化为标准型线性规划标准形式page39解:①令x3=x4-

x5②加松弛变量x6③加剩余变量x7

④令Z'=-ZmaxZ'=x1-2x2+3x4-3x5x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,

x2,

x4,…,x70minZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1,x20,x3无限制线性规划标准形式page40

例6

把问题转化为标准形式page41(1)minZ=2x1-x2+2x3练习3将下列线性规划问题化成标准型:-x1

+x2+x3

=

4-x1

+x2-x3

6x1

0

,x2

0,x3

无约束

s.t.(2)maxZ=2x1+x2+3x3+x4x1

+x2+x3+x3

72x1

-3x2+x3

=-8x1

-2x3+2x4

1x1,

x3

0,x2

0

,x4

无约束

s.t.线性规划标准形式(3)minZ=2x1+3x2+5x3x1

+x2-x3

-5

-6x1

+7x2-9x3

=15|19x1

-7x2+5x3|13x1,

x2

0,x3

无约束

s.t.(4)maxZ=x1-3x2-x1

+2x2-5

x1

+3x2=10x1,

x2

无约束

s.t.线性规划标准形式page43定义1:满足约束(2)、(3)的x=(x1…xn)T称为LP问题的可行解,全部可行解的集合称为可行域。定义2:满足(1)的可行解称为LP问题的最优解线性规划的标准型4.线性规划的图解法page44maxZ=Cx(1)Ax=b(2)x

0(3)图解法求解的目的:一是判别线性规划问题的求解结局;二是在存在最优解的条件下,把问题的最优解找出来。

4.线性规划的图解法page45图解法的步骤:1、在平面上建立直角坐标系;2、图示约束条件,找出可行域;3、图示目标函数和寻找最优解。4.线性规划的图解法page46例7maxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x204.线性规划的图解法page47解:(1)、确定可行域

x10x1=0(纵)x20x2=0(横)x1+2x230x1+2x2=30(0,15)(30,0)x23x1+2x2=60(0,30)(20,0)

2x2=244.线性规划的图解法0102030DABC203010x1page48(2)、求最优解最优解:x*=(15,7.5)

Zmax

=975Z=40x1+50x20=40x1+50x2(0,0),(10,-8)C点:x1+2x2=30

3x1+2x2=604.线性规划的图解法page490102030DABC203010x1x2Z=40x1+80x2=0

x1+2x2=30DABCx20x1解:最优解:BC线段B点C点x(1)=(6,12)x(2)=(15,7.5)x=x(1)+(1-)x(2)(01)例8、maxZ=40x1+80x2

x1+2x2303x1+2x2602x224

x1,x204.线性规划的图解法page504.线性规划的图解法X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)X==+(1-)maxZ=1200

X1615

X2127.5page51无界解无有限最优解例9、maxZ=2x1+4x2

2x1+x28-2x1+x22x1,x20Z=02x1+x2=8-2x1+x2=28246x240x14.线性规划的图解法page52例10、maxZ=3x1+2x2-x1-x21x1,x20无解无可行解-1x1-1x204.线性规划的图解法page53唯一解无穷多解无有限最优解无可行解有解无解当目标函数的直线族与某约束条件平行,且该问题有解时。约束条件无公共区域。有解但可行域可伸展到无穷时总结4.线性规划的图解法page54由图解法得到的启示(1)、线性规划问题的解的情况有四种:唯一最优解;无穷多最优解;无界解;无可行解。(2)、若线性规划可行域存在,则可行域是一个凸集。(3)、若有最优解,定可在可行域的顶点得到。(4)、解题思路是找出凸集的各顶点的最大目标函数值。4.线性规划的图解法page55练习:用图解法解以下问题:

maxZ=5x1+6x2x1

-2x2

2

-2x1

+3x22x1,

x2

无约束

s.t.4.线性规划的图解法page56maxZ=CxAx

=bx0Am×n

满秩

x

=(x1…xn)T

一、线性规划问题的解的概念5.线性规划基本概念page57定义1:基(基阵)——设A为约束方程组的m×n阶系数矩阵设(n>m),其秩为m,B是矩阵A中的一个m×m阶的满秩子矩阵,称B是线性规划问题的一个基。

P1P2…Pm……Pna11a12…

a1m……a1nA=a21a22…

a2m……

a2n

……am1am2…

amm

……amnB5.线性规划基本概念page58A=(P1…

PmPm+1…

Pn

)=(BN)

基向量非基向量…x=(x1…

xm

xm+1…

xn

)T=(xB

xN)T

基变量非基变量

xB

xN…B中的每一个列向量Pj称为基向量,与基向量对应的变量称为基变量,其他变量称为非基变量。5.线性规划基本概念page59Ax=b的求解xB

xN(BN)=bBxB

+NxN=bBxB

=b-NxNxB

=B-1b-B-1NxNA=(BN)x=(xB

xN

)T若B为单位矩阵xB

=b-NxN若xN=0xB

=B-1b5.线性规划基本概念page60定义2:可行解——满足方程约束条件的解x=(x1,x2,…xn)T,称为线性规划问题的可行解。全部可行解的集合称为可行域。定义3:最优解——使目标函数达到最大值的可行解,称为最优解。5.线性规划基本概念page61定义4:基本解——对应于基B,x=为Ax=b的一个解,则x为线性规划问题的基本解,也称基解。B-1b0定义5:基本可行解——基B,基本解x=若B-1b0,称基解为基本可行解,也称基可行解。

B-1b0※基本解中最多有m个非零分量。※基本解的数目不超过Cnm=个。n!m!(n-m)!定义6:可行基——对应于基可行解的基称为可行基。5.线性规划基本概念page62例11x1+2x2+x3=303x1+2x2+x4=602x2+x5=24x1…x50121003201002001P1P2P3P4P5A=5.线性规划基本概念page63x1x2x3x4x5x=b=306024B=(P3P4P5)=I

是满秩子矩阵

非基N=(P1P2)x3=30-(x1+2x2)x4=60-(3x1+2x2)x5=24-2x25.线性规划基本概念page64令x1=

x2=0,x3=30,x4=60,x5=2400306024x===xN

0xB

B-1b5.线性规划基本概念page65例12:给定约束条件

-x3+x4=0x2+x3+x4=3-x1+x2+x3+x4=2

xj

0(j=1,2,3,4)求出基变量是x1,x3,x4的基本解,是不是可行解?5.线性规划基本概念page66

0-11解:B=(P1P3P4)=011-111

01-10B-1=-1/21/2031/21/202b=5.线性规划基本概念page67

x1

x3=B-1b

x4

xB

=

01-101

=-1/21/203=3/2

1/21/2023/2∴x=(1,0,3/2,3/2)T是5.线性规划基本概念page68线性规划解之间的关系线性规划解之间的关系:可行解基本解非可行解基本可行解最优解page69退化基本可行解与退化基1、退化基本可行解:基本可行解中存在取零值的基变量,则称该基本可行解为退化的基本可行解。2、退化基:退化的基本可行解对应的基,称为退化基。page70凸集——D是n维空间的一个集合,x(1),

x(2)∈D,若对任何x(1),

x(2),有x=x(1)+(1-)x(2)∈D(01),则D为凸集。定义1:凸集——如果集合D中任意两个点,其连线上的所有点也都是集合D中的点,则称D为凸集。二、凸集及其顶点5.线性规划基本概念page71x(1)x(2)凸多边形凹多边形x(1)x(2)5.线性规划基本概念page72

x(1),x(2),…,x(k)

是n维欧氏空间中的k个点,若有一组数

µ1,µ2,…,µk

满足

0µi1(i=1,…,k)定义2µ

i=1ki=1有点x=µ1x(1)

+…+µkx(k)则称点x为x(1),x(2),…,x(k)

的凸组合。凸组合5.线性规划基本概念page73

凸集D,点xD,若找不到两个不同的点x(1),x(2)D使得

x=x(1)

+(1-)x(2)

(0<<1)

则称x为D的顶点。定义3顶点5.线性规划基本概念page74证明:设LP问题的可行解域为集合CC={x|Ax=bx0}任取x(1),x(2)C,则

x=x(1)

+(1-)x(2)

0

(0

1)又因为Ax(1)

=b,Ax(2)

=b所以Ax=A[x(1)

+(1-)x(2)

]=b

+(1-)b=b

xC,C为凸集定理1:LP问题的可行解域一定是凸集。三、几个基本定理的证明5.线性规划基本概念page75只须证明:

D的k个顶点x(1),…,x(k)

,有

预理1D为有界凸多面集,xD,x必可表为D的顶点的凸组合。0µi1,使x=µ1x(1)

+…+µkx(k)µ

i=1ki=15.线性规划基本概念page76证明可用归纳法(略)x(1)x(2)x(3)x’xx’在边界上x在内部x(1)(1-)x(2)(1-)x(3)x=++x=x’

+(1-)x(2)

(0

1)x’=x(1)

+(1-)x(3)

(0

1)5.线性规划基本概念page77证明:设x(1),…,x(k)

为可行域顶点,若x*不是顶点,但

maxZ=Cx*

定理2:可行域有界,最优值必可在顶点得到Cx*=µ

iC

x(i)ki=1µ

iCx(m)ki=1=Cx(m)[设Cx(m)=Max(C

x(i))]1ikµ

ix(i)ki=1µ

i=1ki=10µi1x*=5.线性规划基本概念page78引理2:LP问题的可行解x是基本可行解x的非0分量对应的系数列向量线性无关证明:(1)必要性。由基可行解的定义显然。(2)充分性。若向量P1,P2,…

Pk线性独立,则必有k

m。

当k=m时,它们恰好构成一个基,从而x=(x1,x2,…,xm,0,…,0)为相应的基可行解。当k<m时,则一定可从其余列向量中找出(m-k)个与P1,P2,…,Pk构成一个基,其对应的解恰为x,所以据定义它是基可行解。5.线性规划基本概念page79证明(反证法):()假设x不是基本可行解x=(x1,…,xn

)Txj

>0j=1,…,kxj

=0j=k+1,…,n由引理2知,p1,…,pk

线性相关必有不全为0的1,…,

k使1p1+…+

k

pk

=0做=(1,…,

k,0…,0)T则有A

=1p1+…+

k

pk

=0可行域C中点x是顶点x是基本可行解定理3:5.线性规划基本概念page80选任一不为零的数令

x(1)

=x+

0

x(2)

=x-

0又Ax(1)

=Ax+A=b

Ax(2)

=Ax-A=b

所以x(1)Cx(2)C因为x=1/2x(1)+1/2x(2)所以x不是可行域的顶点5.线性规划基本概念page81证明:()不是顶点,不是基可行解设x为可行解xj

>0j=1,…,kxj

=0j=k+1,…,n若x不是顶点,则有x(1)=x(2)C,使得:

x=x(1)

+(1-)x(2)

(0<

<

1)

xj

=xj

(1)

+(1-)xj

(2)

(j=1,…,k)0=xj

(1)

+(1-)xj

(2)

(j=k+1,…,n)5.线性规划基本概念page82因为>0,1->0,xj

(1)

0,xj

(2)

0所以xj

(1)=

xj

(2)=

0(j=k+1,…,n)因为Ax(1)

=bAx(2)

=bp

jxj(1)=bnj=1p

jxj(2)=bnj=1即p1x1(1)+…+pk

xk(1)=b(a)p1x1(2)+…+pk

xk(2)=b(b)5.线性规划基本概念page83由(a)-(b)得(x1(1)-x1(2))p1+…+(xk(1)-xk(2))pk=0即x不是基可行解所以p1,…,pk

线性相关定理4若线性规划问题有最优解,一定存在一个基可行解是最优解。5.线性规划基本概念page84

(LP)问题的基本可行解可行域的顶点。若(LP)问题有最优解,必可以在基本可行解(顶点)达到。若(LP)问题有可行解,则可行解集(可行域)是凸集(可能有界,也可能无界),有有限个顶点。5.线性规划基本概念LP问题解的性质page856.单纯形法

6.1、单纯形法迭代原理

6.2、单纯形法计算步骤

6.3、人工变量法

6.4、两阶段法

6.5、计算中的几个问题page866.1单纯形法迭代原理一、确定初始基可行解二、从一个基可行解转换为相邻基可行解三、最优性检验和解的判别page87A中总存在一个单位矩阵(P1,P2,…,Pm)。一、确定初始基可行解当约束条件为时,加上松驰变量的系数矩阵即为单位矩阵。当约束条件为或=时,可以构造人工基,人为产生一个单位矩阵。基向量、基变量、非基向量、非基变量可得初始基可行解:x=(x1,…,xm,xm+1,…xn)T=(b1,…,bm,0,…,0)T6.1单纯形法迭代原理page88两个基可行解相邻指的是它们之间变换且仅变换一个基变量。设x(0)=(x10,x20,…xm0,0,…0)T,有Pixi0=bmi=1系数矩阵的增广矩阵二、基可行解的转换6.1单纯形法迭代原理page89Pj=aijPimi=1Pj-

aijPi=0

mi=1两边乘上一个正数θ>0,得θ

(Pj-aij

Pi)=0

mi=1同相加整理得:Pixi0=bmi=1所以得到另一个点x(1),使Pixi(1)=bni=1可行解?基解?6.1单纯形法迭代原理page90所以x(1)是可行解令存在:6.1单纯形法迭代原理page91重新排列后不含非基向量的增广矩阵:因alj>0,故上述矩阵元素组成的行列式不为零,P1,P2,…Pl-1,Pj,Pl+1,…,Pm

是一个基。所以,x(1)

,是基可行解。00…010…06.1单纯形法迭代原理page92进行初等变换:b=(b1-θa1j,…,bl-1-θal-1,j,θ,bl+1-

θal+1,j,…bm-amj)T由此x(1)是x(0)相邻的基可行解,且由基向量组成的矩阵仍为单位矩阵。x(1)=(b1-θa1j,…,bl-1-θal-1,j,θ,bl+1-

θal+1,j,…bm-amj)T

?6.1单纯形法迭代原理page93将基本可行解x(0)和x(1)分别代入目标函数得:三、最优性检验和解的判别6.1单纯形法迭代原理page94是对线性规划问题的解进行最优性检验的标志。当所有的σi<=0时,现有顶点为最优解。当所有的σi<=0时,又对某个非基变量xj,有Cj-Zj=0,且可找到θ

>0,则有无穷多最优解。当存在某个σj>0,又Pj<=0,则有无界解。通常简写为6.1单纯形法迭代原理page951)找出初始基可行解,建立单纯形表。6.2单纯形法计算步骤Cjc1…cm…cj…cnCBxBbx1…xm…xj…xnc1x1b110…a1j…a1nc2x2b200…a2j…a2n…………….……………cmxmbm01…amj…amn

σj=cj-zj0…0……page966.2单纯形法计算步骤

5)以a’l,k为主元素进行旋转运算,转2)。3)若,使得但则此问题无界解,停止.否则,转下一步.page97例13用单纯形法求解线性规划问题maxZ=2x1+x25x2

156x1

+2x2

24x1

+x2

5x1,

x2

0s.t.6.2单纯形法计算步骤page98解:1、先将上述问题化成标准形式有maxZ=2x1+x2+0·x3+0·x4+0·x56.2单纯形法计算步骤找到一个初始基可行解x=(0,0,15,24,5)

5x2+x3=15s.t.6x1+2x2+x4=24x1+x2

+x5=5

x1,

…,x50page992、列初始单纯形表:因为σ1>σ2,确定x1为换入变量。因为θ=min{-,24/6,5/}=4所以6为主元素,x4为换出变量。Cj21000θCBxBbx1x2x3x4x50x315051000x424620100x5511001

σj=cj-zj6.2单纯形法计算步骤page1003、列新单纯形表:因为σ2>0

,确定x2为换入变量。因为θ=min{15/5,4/2/6,1/4/6}=3/2。所以4/6为主元素,x5为换出元素。Cj21000θCBxBbx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61

σj=cj-zj6.2单纯形法计算步骤page1014、列新单纯形表:因为Cj-Zj<0,所以达到最优解。最优解为:x=(7/2,3/2,15/2,0,0)。目标函数值为Z=2×7/2+1×3/2+0×15/2+0+0=8.5Cj21000θCBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2000-1/42/3

σj=cj-zj6.2单纯形法计算步骤page102练习题解:原问题化为标准型6.2单纯形法计算步骤page103Cj3501000θCBxBbx1x2x3x4x5x6x70x5351110100350x612510-1010120x7500-11001-

σj=cj-zj3501000列初始单纯形表156.2单纯形法计算步骤page104Cj3501000θCBxBbx1x2x3x4x5x6x70x523-40111-10235x212510-1010-0x7500-110015

σj=cj-zj-220060-5016列新单纯形表6.2单纯形法计算步骤page105Cj3501000θCBxBbx1x2x3x4x5x6x70x518-40201-1-195x21751-10011-1x4500-11001-

σj=cj-zj-220600-5-626列新单纯形表6.2单纯形法计算步骤page106Cj3501000θCBxBbx1x2x3x4x5x6x70x39-20100.5-0.5-0.55x22631001x414-20010.5-0.50.5

σj=cj-zj-10000-3-2-36.2单纯形法计算步骤page1076.3人工变量法当化为标准形后的约束条件的系数矩阵中不存在单位矩阵时,可以人为地增加变量,在最优解中人工变量取值必须为零。为此,令目标函数中人工变量的系数为任意大的负值-M。亦称大M法。page108例1:maxZ=6x1+4x22x1+3x2

1004x1+2x2

120x1=14x2

22x1x2

06.3人工变量法page109maxZ=6x1+4x22x1+3x2+x3=1004x1+2x2+x4=120x1=14x2-x5=

22x1…x5

0解:化成标准型6.3人工变量法page110maxZ=6x1+4x2-Mx6-Mx72x1+3x2+x3=1004x1+2x2+x4=120x1+x6=14x2-x5+x7=

22x1…x7

0加人工变量6.3人工变量法page111Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x310023100000x41204201000-Mx6141000010-Mx7220100-101

σj=cj-zj列初始单纯形表6.3人工变量法page112Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x31002310000500x4120420100030-Mx614100001014-Mx7220100-101

σj=cj-zjM+6M+400-M000x37203100-200x46402010-406x1141000010-Mx7220100-101

σj=cj-zj0M+400-M6-M06.3人工变量法page113Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x3600103-2-30x42000012-4-26x11410000104x2220100-101

σj=cj-zj000046-M4-M0x52001/301-2/3-10x41600-2/310-8/306x11410000104x224011/300-2/3-2

σj=cj-zj00-4/300-M-10/3-M6.3人工变量法page114Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x3600103-2-30x42000012-4-26x11410000104x2220100-101

σj=cj-zj000046-M4-M0x52001/301-2/3-10x41600-2/310-8/306x11410000104x224011/300-2/3-2

σj=cj-zj00-4/300-M-10/3-M6.4两阶段法为了克服大M法的困难,对添加人工变量后的线性规划问题分两个阶段来计算,称为两阶段法。解题思路:第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题,即令目标函数中其它变量的系数取零,人工变量的系数取某个正的常数(一般取1),在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。显然在第一阶段中,当人工变量取值为0时,目标函数值也为0。这时候的最优解就是原线性规划问题的一个基可行解。page115作辅助问题minW=yi

i=1mxj

yi0j=1naij

xj

+yi

=bi(i=1,2,…,m)原问题maxZ=Cj

xj

j=1nxj

0j=1naij

xj

=bi(i=1,2,…,m)6.4两阶段法page116解题过程:第1阶段:解辅助问题。当进行到最优表时,①、若W=0,则得到原问题的一个基本可行解,转入第2阶段。②、若W>0,则判定原问题无可行解。第2阶段:去除人工变量,求解原问题。第一阶段的最优解为原问题的初始基可行解。6.4两阶段法page117例2:maxZ=-x1+2x2x1+x2

2-x1+x21x2

3x1x2

0解:第(1)阶段:minW=x6+x7x1+x2-x3+x6=2-x1+x2-x4+x7=1x2+x5=3x1…x7

06.4两阶段法page118列初始单纯形表Cj00000-1-1θCBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010x530100100

σj=cj-zj第二阶段:去除人工变量,列新单纯形表求解。6.4两阶段法page119

0000011

x1x2x3x4x5x6x7CBxB

3

0

-2110

001x6211-100101x71-1

(1)0-10010x530100100CB

xB

1

-201-1002x61(2)0-1101-1x21-1

10-1001x52100110-1

xB

0

0000011x11/210-1/21/201/2-1/2x23/20

1-1/2-1/201/21/2x53/200-1/21/21-1/2-1/2

6.4两阶段法page120

-12000x1x2x3x4x5CBxB

3/2001/23/20-1x11/210-1/2(1/2)02x23/201-1/2-1/200x53/2001/21/21

xB4-30200x4120-110x2211-100x51-10(1)01

xB

6

1000-2x4210011x2301001x31-10

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论