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

下载本文档

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

文档简介

运筹学OperationsResearchChapter1线性规划LinearProgramming1.1LP的数学模型

MathematicalModelofLP1.2图解法

GraphicalMethod1.3标准型

StandardformofLP1.4基本概念

BasicConcepts1.5单纯形法

SimplexMethod1.1数学模型

MathematicalModel1.1线性规划的数学模型MathematicalModelofLP线性规划(LinearProgramming,缩写为LP)通常研究资源的最优利用、设备最佳运行等问题。例如,当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大)。19十一月2024【例1-1】生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定,每件产品甲需要消耗材料A2公斤,消耗材料B1公斤,每件产品乙需要消耗材料A1公斤,消耗材料B1.5公斤。已知在计划期内可供材料分别为40、30公斤;每生产一件甲、乙两产品,企业可获得利润分别为300、400元,如表1-1所示。假定市场需求无限制。企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大。1.1线性规划的数学模型MathematicalModelofLP1.1.1应用模型举例19十一月2024【解】设x1、x2分别为甲、乙产品的产量,数学模型为:1.1线性规划的数学模型MathematicalModelofLP

产品

资源

乙现有资源材料A2140材料B11.530利润(元/件)300400表1-119十一月2024线性规划的数学模型由决策变量

Decisionvariables

目标函数Objectivefunction及约束条件Constraints构成。称为三个要素。其特征是:1.解决问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;2.解决问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型?1.1线性规划的数学模型MathematicalModelofLP19十一月2024【例1-2】某超市决定:营业员每周连续工作5天后连续休息2天,轮流休息。根据统计,超市每天需要的营业员如表1-2所示。表1-2营业员需要量统计表超市人力资源部应如何安排每天的上班人数,使超市总的营业员最少。星期需要人数星期需要人数一300五480二300六600三350日550四4001.1线性规划的数学模型MathematicalModelofLP19十一月2024【解】设xj

(j=1,2,…,7)为休息2天后星期一到星期日开始上班的营业员,则这个问题的线性规划模型为1.1线性规划的数学模型MathematicalModelofLP星期需要人数星期需要人数一300五480二300六600三350日550四40019十一月20241X10C1404>=3001042X267C2301>=30013X3146C3350>=35004X4170C4400>=40005X597C5480>=48006X6120C6600>=60007X717C7550>=5500最优解:Z=617(人)1.1线性规划的数学模型MathematicalModelofLP注:表中是取整数后的结果!整数规划将在第3章讲解。19十一月2024【例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根,这些轴的规格分别是1.5,1,0.7(m),这些轴需要用同一种圆钢来做,圆钢长度为4m。现在要制造1000辆汽车,最少要用多少圆钢来生产这些轴?【解】这是一个条材下料问题,设切口宽度为零。设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式1.5y1+y2+0.7y3≤4表示,求这个不等式关于y1,y2,y3的非负整数解。象这样的非负整数解共有10组,也就是有10种下料方式,如表1-3所示。表1-3下料方案

方案规格12345678910需求量y1(根)

22111000001000y210210

432101000y3

01023012451000余料(m)00.30.50.1o.400.30.60.20.51.1线性规划的数学模型MathematicalModelofLP19十一月2024设xj(j=1,2…,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为:求下料方案时应注意,余料不能超过最短毛坯的长度;最好将毛坯长度按降的次序排列,即先切割长度最长的毛坯,再切割次长的,最后切割最短的,不能遗漏了方案。如果方案较多,用计算机编程排方案,去掉余料较长的方案,进行初选。1.1线性规划的数学模型MathematicalModelofLP

方案规格12345678910需求量y1(根)22111000001000y210210

432101000y3

01023012451000余料(m)00.30.50.1o.400.30.60.20.519十一月20241X15002X203X304X405X506X662.57X708X809X925010X100Z=812.51.1线性规划的数学模型MathematicalModelofLP19十一月2024【例1-4】配料问题。某钢铁公司生产一种合金,要求的成分规格是:锡不少于28%,锌不多于15%,铅恰好10%,镍要界于35%~55%之间,不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼,每种矿物的成分含量和价格如表1-4所示。矿石杂质在治炼过程中废弃,现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中,合金含量没有发生变化。表1-4矿石的金属含量

合金矿石锡%锌%铅%镍%杂质费用(元/t)1251010253034024000303026030155206018042020040202305851517551901.1线性规划的数学模型MathematicalModelofLP19十一月2024解:设xj(j=1,2,…,5)是第j种矿石数量,得到下列线性规划模型注意,矿石在实际冶炼时金属含量会发生变化,建模时应将这种变化考虑进去,有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题,在许多行业生产中都能遇到。1.1线性规划的数学模型MathematicalModelofLP矿石锡%锌%铅%镍%杂质费用(元/t)12510102530340240003030260301552060180420200402023058515175519019十一月20241X102X20.33333X304X40.58335X50.6667最优解:Z=347.51.1线性规划的数学模型MathematicalModelofLP19十一月20241.1线性规划的数学模型MathematicalModelofLP【例1-5】投资问题。某投资公司拟将5000万元的资金用于国债、地方国债及基金三种类型证券投资,每类各有两种。每种证券的评级、到期年限及每年税后收益率见表1-5所示。表1-5证券投资方案

决策者希望:国债投资额不少于1000万,平均到期年限不超过5年,平均评级不超过2。问每种证券各投资多少使总收益最大。序号证券类型评级到期年限每年税后收益率(%)1国债1183.22国债21103.83地方债券1244.34地方债券2364.75基金1434.26基金2544.619十一月20241.1线性规划的数学模型MathematicalModelofLP解设xj(j=1,2,…,6)为第j种证券的投资额,目标函数是税后总收益为资金约束:国债投资额约束:平均评级约束:平均到期年限约束:19十一月2024整理后得到线性规划模型1.1线性规划的数学模型MathematicalModelofLP决策结果:X=(250,750,3500,0,500,0)Z=101419十一月2024【例1-6】均衡配套生产问题。某产品由2件甲、3件乙零件组装而成。两种零件必须经过设备A、B上加工,每件甲零件在A、B上的加工时间分别为5分钟和9分钟,每件乙零件在A、B上的加工时间分别为4分钟和10分钟。现有2台设备A和3台设备B,每天可供加工时间为8小时。为了保持两种设备均衡负荷生产,要求一种设备每天的加工总时间不超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的产量最大。【解】设x1、x2为每天加工甲、乙两种零件的件数,则产品的产量是设备A、B每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备1小时的约束为1.1线性规划的数学模型MathematicalModelofLP19十一月2024目标函数线性化。产品的产量y等价于整理得到线性规划模型约束线性化。将绝对值约束写成两个不等式1.1线性规划的数学模型MathematicalModelofLP19十一月20241.1.2线性规划的一般模型一般地,假设线性规划数学模型中,有m个约束,有n个决策变量xj,j=1,2…,n,目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示,aij称为工艺系数。约束条件右端的常数用bi表示,bi称为资源限量。则线性规划数学模型的一般表达式可写成为了书写方便,上式也可写成:1.1线性规划的数学模型MathematicalModelofLP19十一月2024在实际中一般xj≥0,但有时xj≤0或xj无符号限制。1.1线性规划的数学模型MathematicalModelofLP19十一月20241.什么是线性规划,掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。作业:教材习题

1.1~1.51.1线性规划的数学模型MathematicalModelofLP下一节:图解法19十一月20241.2图解法

GraphicalMethod图解法的步骤:1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域,其交集就是可行解集合,或称为可行域;2.绘制目标函数图形。先过原点作一条矢量指向点(c1,c2),矢量的方向就是目标函数增加的方向,称为梯度方向,再作一条与矢量垂直的直线,这条直线就是目标函数图形;3.求最优解。依据目标函数求最大或最小移动目标函数直线,直线与可行域相交的点对应的坐标就是最优解。一般地,将目标函数直线放在可行域中求最大值时直线沿着矢量方向移动求最小值时沿着矢量的反方向移动1.2图解法TheGraphicalMethod19十一月2024x1x2O1020304010203040(300,400)(15,10)最优解X=(15,10)最优值Z=8500例1-71.2图解法TheGraphicalMethod19十一月2024246x1x2246最优解X=(3,1)最优值Z=5(3,1)minZ=x1+2x2例1-8(1,2)1.2图解法TheGraphicalMethod19十一月2024246x1x2246X(2)=(3,1)X(1)=(1,3)(5,5)minZ=5x1+5x2例1-9有无穷多个最优解即具有多重解,通解为0≤α≤1

当α=0.5时X=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)1.2图解法TheGraphicalMethod19十一月2024246x1x2246(1,2)无界解(无最优解)max

Z=x1+2x2例1-101.2图解法TheGraphicalMethod19十一月2024x1x2O10203040102030405050无可行解即无最优解maxZ=10x1+4x2例1-111.2图解法TheGraphicalMethod19十一月2024由以上例题可知,线性规划的解有4种形式:1.有唯一最优解(例1-7例1-8)2.有多重解(例1-9)3.有无界解(例1-10)4.无可行解(例1-11)1、2情形为有最优解3、4情形为无最优解1.2图解法TheGraphicalMethod19十一月20241.通过图解法了解线性规划有几种解的形式2.作图的关键有三点

(1)可行解区域要画正确

(2)目标函数增加的方向不能画错

(3)目标函数的直线怎样平行移动作业:教材习题

1.61.2图解法TheGraphicalMethod下一节:线性规划的标准型19十一月20241.3线性规划的标准型StandardformofLP

在用单纯法求解线性规划问题时,为了讨论问题方便,需将线性规划模型化为统一的标准形式。1.3线性规划的标准型StandardformofLP线性规划问题的标准型为:1.目标函数求最大值(或求最小值)2.约束条件都为等式方程3.变量xj非负4.常数bi非负19十一月2024max(或min)Z=c1x1+c2x2+…+cnxn1.3线性规划的标准型StandardformofLP注:本教材默认目标函数是max19十一月2024或写成下列形式:

或用矩阵形式1.3线性规划的标准型StandardformofLP19十一月2024通常X记为:

称A为约束方程的系数矩阵,m是约束方程的个数,n是决策变量的个数,一般情况m≤n,且r(A)=m。其中:1.3线性规划的标准型StandardformofLP19十一月2024【例1-12】将下列线性规划化为标准型【解】(1)因为x3无符号要求,即x3取正值也可取负值,标准型中要求变量非负,所以令1.3线性规划的标准型StandardformofLP19十一月2024(3)第二个约束条件是≥号,在≥号左端减去剩余变量(Surplusvariable)x5,x5≥0。也称松驰变量1.3线性规划的标准型StandardformofLP(2)第一个约束条件是≤号,在≤左端加入松驰变量(slackvariable)x4,x4≥0,化为等式;(4)第三个约束条件是≤号且常数项为负数,因此在≤左边加入松驰变量x6,x6≥0,同时两边乘以-1。(5)目标函数是最小值,为了化为求最大值,令Z′=-Z,得到maxZ′=-Z,即当Z达到最小值时Z′达到最大值,反之亦然。19十一月2024综合起来得到下列标准型1.3线性规划的标准型StandardformofLP19十一月2024

当某个变量xj≤0时,令x/j=-xj

。当某个约束是绝对值不等式时,将绝对值不等式化为两个不等式,再化为等式,例如约束将其化为两个不等式再加入松驰变量化为等式。1.3线性规划的标准型StandardformofLP19十一月2024【例1-13】将下例线性规划化为标准型【解】此题关键是将目标函数中的绝对值去掉。令

则有1.3线性规划的标准型StandardformofLP19十一月2024得到线性规划的标准形式

1.3线性规划的标准型StandardformofLP对于a≤x≤b(a、b均大于零)的有界变量化为标准形式有两种方法。一种方法是增加两个约束x≥a及x≤b

另一种方法是令x'=x-a,则a≤x≤b等价于0≤x'≤b-a,增加一个约束x'≤b-a并且将原问题所有x用x=x'+a替换。19十一月20241.如何化标准形式?

可以对照四条标准逐一判断!

标准形式是人为定义的,目标函数可以是求最小值。2.用WinQSB软件求解时,不必化成标准型。图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。作业:教材习题

1.71.3线性规划的标准型StandardformofLP下一节:基本概念19十一月20241.4线性规划的有关概念BasicConceptsofLP

设线性规划的标准型

maxZ=CX

(1.1)

AX=b

(1.2)

X≥0(1.3)式中A是m×n矩阵,m≤n并且r(A)=m,显然A中至少有一个m×m子矩阵B,使得r(B)=m。1.4基本概念BasicConcepts

(basis)A中m×m子矩阵B并且有r(B)=m,则称B是线性规划的一个基(或基矩阵basismatrix)。当m=n时,基矩阵唯一,当m<n时,基矩阵就可能有多个,但数目不超过19十一月2024【例1-14】线性规划

求所有基矩阵。【解】约束方程的系数矩阵为2×5矩阵容易看出r(A)=2,2阶子矩阵有C52=10个,其中第1列与第3列构成的2阶矩阵不是一个基,基矩阵只有9个,即1.4基本概念BasicConcepts

19十一月2024由线性代数知,基矩阵B必为非奇异矩阵并且|B|≠0。当矩阵B的行列式等式零即|B|=0时就不是基当确定某一矩阵为基矩阵时,则基矩阵对应的列向量称为基向量(basisvector),其余列向量称为非基向量

基向量对应的变量称为基变量(basisvariable),非基向量对应的变量称为非基变量

在上例中B2的基向量是A中的第一列和第四列,其余列向量是非基向量,x1、x4是基变量,x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的,不同的基对应的基变量和非基变量也不同。1.4基本概念BasicConcepts

19十一月2024可行解(feasiblesolution)

满足式(1.2)及(1.3)的解X=(x1,x2…,xn)T

称为可行解。基本可行解(basis

feasiblesolution)

若基本解是可行解则称为是基本可行解(也称基可行解)。

例如,与X=(0,0,0,3,2,)都是例1的可行解。

基本解(basissolution)对某一确定的基B,令非基变量等于零,利用式(1.2)解出基变量,则这组解称为基B的基本解。最优解(optimalsolution)满足式(1.1)的可行解称为最优解,即是使得目标函数达到最大值的可行解就是最优解,例如可行解是例2的最优解。非可行解(Infeasiblesolution)

无界解

(unboundsolution)1.4基本概念BasicConcepts

19十一月2024显然,只要基本解中的基变量的解满足式(1.3)的非负要求,那么这个基本解就是基本可行解。在例1-13中,对B1来说,x1,x2是基变量,x3,x4,x5是非基变量,令x3=x4=x5=0,则式(1.2)为对B2来说,x1,x4,为基变量,令非基变量x2,x3,x5为零,由式(1.2)得到

,x4=4,因|B1|≠0,由克莱姆法则知,x1、x2有唯一解x1=2/5,x2=1则基本解为1.4基本概念BasicConcepts

19十一月2024由于是基本解,从而它是基本可行解,在中x1<0,因此不是可行解,也就不是基本可行解。反之,可行解不一定是基本可行解例如满足式(1.2)~(1.3),但不是任何基矩阵的基本解。基本解为1.4基本概念BasicConcepts

19十一月2024可行基基可行解对应的基称为可行基;最优基基本最优解对应的基称为最优基;如上述B3就是最优基,最优基也是可行基。当最优解唯一时,最优解亦是基本最优解,当最优解不唯一时,则最优解不一定是基本最优解。例如右图中线段的点为最优解时,Q1点及Q2点是基本最优解,线段的内点是最优解而不是基本最优解。基本最优解

最优解是基本解称为基本最优解。例如,满足式(1.1)~(1.3)是最优解,又是B3的基本解,因此它是基本最优解。1.4基本概念BasicConcepts

19十一月2024基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示:基本最优解基本可行解可行解最优解基本解例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。1.4基本概念BasicConcepts

19十一月2024凸集(Convexset)设K是n维空间的一个点集,对任意两点

时,则称K为凸集。

就是以X(1)、X(2)为端点的线段方程,点X的位置由α的值确定,当α=0时,X=X(2),当α=1时X=X(1)凸组合(Convexcombination)

设是Rn

中的点若存在

使得成立,则称X为的凸组合。1.4基本概念BasicConcepts

19十一月2024极点(Extremepoint)

设K是凸集,,若X不能用K中两个不同的点的凸组合表示为<)10()1()2()1(<-+=aaaXXX则称X是K的一个极点或顶点。X是凸集K的极点即X不可能是K中某一线段的内点,只能是K中某一线段的端点。O1.4基本概念BasicConcepts

19十一月2024【定理1.1】若线性规划可行解K非空,则K是凸集。【定理1.2】线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解。【定理1.3】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上到达,最优解就是极点的坐标向量。定理1.2刻划了可行解集的极点与基本可行解的对应关系,极点是基本可行解,反之,基本可行解一定是极点,但它们并非一一对应,有可能两个或几个基本可行解对应于同一极点(退化基本可行解时)。线性规划的基本定理1.4基本概念BasicConcepts

19十一月2024

定理1.3描述了最优解在可行解集中的位置,若最优解唯一,则最优解只能在某一极点上达到,若具有多重最优解,则最优解是某些极点的凸组合,从而最优解是可行解集的极点或界点,不可能是可行解集的内点。

若线性规划的可行解集非空且有界,则一定有最优解;若可行解集无界,则线性规划可能有最优解,也可能没有最优解。

定理1.2及1.3还给了我们一个启示,寻求最优解不是在无限个可行解中去找,而是在有限个基本可行解中去寻求。下一节将介绍一种有效地寻找最优解的方法。1.4基本概念BasicConcepts

19十一月20241.线性规划常用的概念:可行解、基本解、基本可行解、最优解、基本最优解、基、可行基、最优基、凸集、极点(凸点)、凸组合2.线性规划的三个基本定理。作业:教材习题

1.81.4基本概念BasicConcepts

下一节:单纯形法19十一月20241.5单纯形法SimplexMethod

单纯形计算方法(SimplexMethod)是先求出一个初始基可行解并判断它是否最优,若不是最优,再换一个基可行解并判断,直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。

当系数矩阵A中可以观察得到一个可行基时(通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵),可以通过解线性方程组求得基本可行解。【例1-15】用单纯形法求例1-1线性规划的最优解1.5单纯形法

SimplexMethod1.5.1普通单纯形法19十一月2024【解】化为标准型,加入松驰变量x3、x4则标准型为系数矩阵A及可行基B1r(B1)=2,B1是一个初始基,x3、x4为基变量,x1、x2为非基变量,令x1=0、x2=0由约束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

1.5单纯形法

SimplexMethod19十一月2024以上得到的一组基可行解是不是最优解,可以从目标函数中的系数看出。目标函数Z=300x1+400x2中x1的系数大于零,如果x1为一正数,则Z的值就会增大,同样若x2不为零为一正数,也能使Z的值增大;因此只要目标函数中非基变量的系数大于零,那么目标函数就没有达到最大值,即没有找到最优解,判别线性规划问题是否达到最优解的数称为检验数,记作λj,j=1,2,…,n

本例中λ1=300,λ2=400,λ3=0,λ4=0。参看表1-6(a)

最优解判断标准

当所有检验数λj≤0(j=1,…,n)时,基本可行解为最优解。

当目标函数中有基变量xi时,利用约束条件将目标函数中的xi消去即可求出检验数。

1.5单纯形法

SimplexMethod检验数目标函数用非基变量表达时的变量系数19十一月2024进基列出基行bi/ai2,ai2>0θi表1-6(a)XBx1x2x3x4bx3211040x413/20130λj30040000

(b)x3x2λj

(c)x1

x210

λj

基变量120002/302/3204/31-2/340100/30-800/330103/4-1/21501-1/211000-25-250将3/2化为11.5单纯形法

SimplexMethod201519十一月2024最优解X=(15,10,0,0)T,最优值Z=8500X(1)=(0,0)x11.5单纯形法

SimplexMethodx1x2O1020304010203040X(2)=(0,20)X(3)=(15,10)19十一月2024典则形式:(1)约束条件系数矩阵存在m个不相关的单位向量;(2)目标函数中不含有基变量。满足条件(1)时立即可以写出基本可行解,满足条件(2)时马上就可以得到检验数。

如何通过观察得到第一个基本可行解并能判断是否为最优解,关键看模型是不是典则形式(或典式)。

单纯形法的开始和后面的计算都是在做这两件工作。表1-6每一张表对应的模型都是典式,从一个可行基换到另一个可行基后,接下来的任务就是从当前的典式变换到另一个典式。1.5单纯形法

SimplexMethod19十一月2024单纯形法全过程的计算,可以用列表的方法计算更为简洁,这种表格称为单纯形表(表1-6)。计算步骤:1.求初始基可行解,列出初始单纯形表,求出检验数。其中基变量的检验数必为零;2.判断:(a)若λj≤0(j=1,2,…,n)得到最优解;(b)某个λk>0且aik≤0(i=1,2,…,m)则线性规划具有无界解(见例1-18)。(c)若存在λk>0且aik(i=1,…,m)不全非正,则进行换基;1.5单纯形法

SimplexMethod19十一月2024第L个比值最小,选最小比值对应行的基变量为出基变量,若有相同最小比值,则任选一个。aLk为主元素;

(c)求新的基可行解:用初等行变换方法将aLk

化为1,k列其它元素化为零(包括检验数行)得到新的可行基及基本可行解,再判断是否得到最优解。(b)选出基变量,求最小比值:1.5单纯形法

SimplexMethod3.换基:(a)选进基变量设λk=max{λj|λj>0},xk为进基变量19十一月2024【例1-16】用单纯形法求解【解】将数学模型化为标准形式:不难看出x4、x5可作为初始基变量,单纯形法计算结果如表1-7所示。1.5单纯形法

SimplexMethod19十一月2024Cj12100bθCBXBx1x2x3x4x50x42-3210150x51/3150120λj121000

0x42x2λj

1x1

2x2

λj

表1-71/3150120301713751/30-90-2M2025601017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最优解X=(25,35/3,0,0,0)T,最优值Z=145/31.5单纯形法

SimplexMethod-40-145/319十一月2024【例1-17】用单纯形法求解

【解】这是一个极小化的线性规划问题,可以将其化为极大化问题求解,也可以直接求解,这时判断标准是:λj≥0(j=1,…,n)时得到最优解。容易观察到,系数矩阵中有一个3阶单位矩阵,x3、x4、x5为基变量。目标函数中含有基变量x4,由第二个约束得到x4=6+x1-x2,并代入目标函数消去x4得1.5单纯形法

SimplexMethod19十一月2024XBx1x2x3x4x5bθx3x4x51-16[1]121000100015→6215621/2λj1-1↑000

6

x2x4x51-241001-1-20100015111

λj20100

11

表中λj≥0,j=1,2,…,5所以最优解为X=(0,5,0,1,11,)最优值

Z=2x1-2x2-x4=-2×5-1=-11极小值问题,注意判断标准,选进基变量时,应选λj<0的变量xj进基。1.5单纯形法

Simplex

Method表1-819十一月2024【例1-18】求解线性规划【解】化为标准型1.5单纯形法

SimplexMethod19十一月2024初始单纯形表为XBx1x2x3x4bx3x432-2-1100114λj-1100

0λ2=1>0,x2进基,而a12<0,a22<0,没有比值,从而线性规划的最优解无界。由模型可以看出,当固定x1使x2→+∞且满足约束条件,还可以用图解法看出具有无界解。1.5单纯形法

SimplexMethod19十一月2024【例1-19】求解线性规划【解】:化为标准型后用单纯形法计算如下表所示1.5单纯形法

SimplexMethod19十一月2024XBx1x2x3x4x5bθ(1)x3x4x5-111[2]2-11000100014→10225—λj24↑0000(2)x2x4x5-1/2[2]1/21001/2-11/201000126→4—38λj4↑0-200-8(3)x2x1x50101001/4-1/2[3/4]1/41/2-1/40017/235/2→14—10/3λj000↑-20-20(4)x2x1x30101000011/31/3-1/3-1/32/34/38/314/310/3λj000-20-20

(3)中λj全部非正,则最优解为:

表(3)表明,非基变量x3的检验数λ3=0,x3若增加,目标函数值不变,即当x3进基时Z仍等于20。使x3进基

x5出基继续迭代,得到表(4)的另一基本最优解X(1),X(2)是线性规划的两个最优解,它的凸组合

仍是最优解,从而原线性规划有多重最优解。1.5单纯形法

SimplexMethod19十一月2024唯一最优解的判断:最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解

。多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断:

某个λk>0且aik≤0(i=1,2,…,m)则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。1.5单纯形法

SimplexMethod19十一月2024在实际问题中有些模型并不含有单位矩阵,为了得到一组基向量和初基可行解,在约束条件的等式左端加一组虚拟变量,得到一组基变量。这种人为加的变量称为人工变量,构成的可行基称为人工基,用大M法或两阶段法求解,这种用人工变量作桥梁的求解方法称为人工变量法。【例1-20】用大M法解下列线性规划1.大M单纯形法1.5.2大M和两阶段单纯形法1.5单纯形法

SimplexMethod19十一月2024【解】首先将数学模型化为标准形式式中x4,x5为松弛变量,x5可作为一个基变量,第一、三约束中分别加入人工变量x6、x7,目标函数中加入―Mx6―Mx7一项,得到人工变量单纯形法数学模型用前面介绍的单纯形法求解,见下表。1.5单纯形法

SimplexMethod19十一月2024Cj32-100-M-MbCBXBx1x2x3x4x5x6x7-M

0-Mx6x5x7-4123-1-212[1]-1000101000014101→λj3-2M2+M-1+2M↑-M0005M-M0-1x6x5x3-6-32[5]3-2001-1000101003→81λj5-6M5M↑0-M001+3M20-1x2x5x3-6/5[3/5]-2/5100001-1/53/5-2/50103/531/5→11/5λj5↑0000123-1x2x1x301010000111025/32/31331/319/3λj000-5-25/3-152/3(2)初始表中的检验数有两种算法,第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7,得到用非基变量表达的目标函数,其系数就是检验数;第二种算法是利用公式计算,如最优解X=(31/3,13,19/3,0,0)T;最优值Z=152/3注意:1.5单纯形法

SimplexMethod(1)M是一个很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值19十一月2024【例1-21】求解线性规划【解】加入松驰变量x3、x4化为标准型在第二个方程中加入人工变量x5,目标函数中加上Mx5一项,得到1.5单纯形法

SimplexMethod19十一月2024用单纯形法计算如下表所示。

Cj5-800MbCBXBx1x2x3x4x50Mx3x5[3]11-2100-1016→4λj5-M↑-8+2M0M0

-4M5Mx1x5101/3-7/31/3-1/30-10122λj0-29/3+7/3M-5/3+1/3MM0

-10-2M1.5单纯形法

SimplexMethod19十一月2024表中λj≥0,j=1,2,…,5,从而得到最优解X=(2,0,0,0,2),Z=10+2M。但最优解中含有人工变量x5≠0说明这个解是伪最优解,是不可行的,因此原问题无可行解。

两阶段单纯形法与大M单纯形法的目的类似,将人工变量从基变量中换出,以求出原问题的初始基本可行解。将问题分成两个阶段求解,第一阶段的目标函数是约束条件是加入人工变量后的约束方程,当第一阶段的最优解中没有人工变量作基变量时,得到原线性规划的一个基本可行解,第二阶段就以此为基础对原目标函数求最优解。当第一阶段的最优解w≠0时,说明还有不为零的人工变量是基变量,则原问题无可行解。1.5单纯形法

SimplexMethod2.两阶段单纯形法19十一月2024【例1-22】用两阶段单纯形法求解例19的线性规划。【解】标准型为在第一、三约束方程中加入人工变量x6、x7后,第一阶段问题为用单纯形法求解,得到第一阶段问题的计算表如下:1.5单纯形法

SimplexMethod19十一月2024Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x7-4123-1-212[1]-1000101000014101→λj2-1-2↑1000-5

100x6x5x3-6-32[5]3-2001-100010100

3→81λj6-5↑0100

-3000x2x5x3-6/53/5-2/5100001-1/53/5-2/5010

3/531/511/5λj00000

01.5单纯形法

SimplexMethod19十一月2024最优解为最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解,将它作为初始基可行解,求原问题的最优解,即第二阶段问题为1.5单纯形法

SimplexMethod19十一月2024Cj32-100bCBXBx1x2x3x4x5

2

0

-1

x2

x5

x3

1

0

0

0

0

1

0

1

0λj5↑0000

2

3

-1x2

x1

x30

1

01

0

0

0

0

11

1

0213λj000-5

Cj32-100bCBXBx1x2x3x4x520-1x2x5x3-6/5[3/5]-2/5100001-1/53/5-2/50103/531/5→11/5λj5↑0000

123-1x2x1x301010000111025/32/31331/319/3λj000-5-25/3

-152/3用单纯形法计算得到下表最优解X=(31/3,13,19/3,0,0)T;最优值Z=152/31.5单纯形法

SimplexMethod19十一月2024【例1-23】用两阶段法求解例1-21的线性规划。【解】例1-21的第一阶段问题为用单纯形法计算如下表:1.5单纯形法

SimplexMethod19十一月2024Cj00001bCBXBx1x2x3x4x501x3x5[3]11-2100-1016→4λj

-1↑2010

-401x1x5101/3-7/31/3-1/30-10122λj

07/31/310

-2λj≥0,得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值w=2≠0,x5仍在基变量中,从而原问题无可行解。1.5单纯形法

SimplexMethod19十一月2024解的判断唯一最优解的判断:最优表中所有非基变量的检验数非零,则线规划具有唯一最优解多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解无界解的判断:

某个λk>0且aik≤0(i=1,2,…,m)则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。无可行解的判断:(1)当用大M单纯形法计算得到最优解并且存在Ri>0时,则表明原线性规划无可行解(2)当第一阶段的最优值w≠0时,则原问题无可行解1.5单纯形法

SimplexMethod19十一月2024设有线性规划其中Am×n且r(A)=m,X≥0应理解为X大于等于零向量,即xj≥0,j=1,2…,n。1.5.3计算公式1.5单纯形法

SimplexMethod19十一月2024不妨假设A=(P1,P2,…,Pn)中前m个列向量构成一个可行基,记为B=(P1,P2,…,Pm)。矩阵A中后n-m列构成的矩阵记为N=(Pm+1,…Pn),则A可以写成分块矩阵A=(B,N)。对于基B,基变量为XB=(x1,x2,…,xm

)T,非基变量为XN=(xm+1,xm+2,…xn)T。则X可表示成同理将C写成分块矩阵C=(CB,CN),CB=(C1,C2,…,Cm),

CN=(Cm+1Cm+2,…,cn)则AX=b可写成1.5单纯形法

SimplexMethod19十一月2024因为r(B)=m(或|B|≠0)所以B—1存在,因此可有令非基变量XN=0,XB=B—1b,由B是可行基的假设,则得到基本可行解X=(B-1b,0)T将目标函数写成1.5单纯形法

SimplexMethod19十一月2024得到下列五个计算公式:(令XN=0)

1.5单纯形法

SimplexMethod19十一月2024上述公式可用下面较简单的矩阵表格运算得到,设初始矩阵单纯形表1-16

将B化为I(I为m阶单位矩阵),CB化为零,即求基本可行解和检验数。用B-1左乘表中第二行,得到表1-17XBXNbXBIB-1NB-1bCj-ZjCBCN0XBXNbXBBNbCj-ZjCBCN0表1-16表1-171.5单纯形法

SimplexM

温馨提示

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

评论

0/150

提交评论