管理运筹学线性规划.ppt

《管理运筹学线性规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学线性规划.ppt（71页珍藏版）》请在三一办公上搜索。

1、管理运筹学,线性规划,松彝钧茧坐搽款杖蹬锅浚倡纵琅变半念冶默铱望运阮挑措润衡罗捐绵坯喂管理运筹学线性规划管理运筹学线性规划,2,第一讲 线性规划,第一章 线性规划的数学模型第一节 线性规划一般模型第二节 线性规划的图解法第三节 线性规划的标准型第四节 线性规划解的概念第二章 线性规划的单纯形法第一节 单纯形法原理第二节 表格单纯形法第三节 人工变量问题第四节 单纯形法补遗第三章 线性规划的对偶理论第四章 线性规划灵敏性分析,只褐昼樱镊啡窜谋忠桓喘蓬镜虚沙项皋每暖章又纠膜配航挞尚殿嗡告窄烤管理运筹学线性规划管理运筹学线性规划,3,第一章 线性规划的数学模型,线性规划 Linear Program

2、ming LP规划论中的静态规划解决有限资源的最佳分配问题求解方法：图解法单纯形解法,悍摩芦酣按友砌歹二击咸劳丛业汐扰广款特涡筹竖极蛔迪麻爱轨绚嘱工货管理运筹学线性规划管理运筹学线性规划,4,第一章 线性规划的数学模型,第一节 线性规划一般模型第二节 线性规划的图解法第三节 线性规划的标准型第四节 线性规划解的概念,得杆当褥区驹尾伎湿睦描枫倪篇粘黎伐翻歇屁琐楞地仓刁差去雅沸瘴纫仪管理运筹学线性规划管理运筹学线性规划,5,第一节 线性规划一般模型,一、线性规划问题的三个要素,决策变量决策问题待定的量值称为决策变量。决策变量的取值要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件

3、表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。,俏火幕分龟漾兴叠杭臣曙鲸仑纵神氦盆撅惺柴剪欧技茁愈竖帧硅创亏恍彰管理运筹学线性规划管理运筹学线性规划,6,第一节 线性规划一般模型,例1.生产计划问题 某厂生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制，相关数据如表所示：问如何安排、两产品的产量，使利润为最大。,二、线性规划模型的构建,碾昆尘鹅苟族画伪融厢妇秤咆腾伯

4、祈直脱愈蛔橡替疤慢链坚谭冻舔南钦桐管理运筹学线性规划管理运筹学线性规划,7,第一节 线性规划一般模型,(1)决策变量。要决策的问题是、两种产品的产量，因此有两个决策变量：设x1为产品产量，x2为产品产量。(2)约束条件。生产这两种产品受到现有生产能力的制约，原料用量也受限制。设备的生产能力总量为300台时，则约束条件表述为 x1+x2 300A、B两种原材料约束条件为2x1+x2 400 x2 250,建立模型,封沙姐胰苞超怖勇缮渝蛋虎蓉乎嵌锥了蜜巳饼谜叁币隆溶恳缎尝儡氰龙央管理运筹学线性规划管理运筹学线性规划,8,第一节 线性规划一般模型,(3)目标函数。目标是利润最大化，用Z表示利润，则

5、maxZ=50 x1+100 x2(4)非负约束。、产品的产量不应是负数，否则没有实际意义，这个要求表述为 x1 0，x2 0,诛粟押实吏怪苹支锤机烟橱咎阀押叛天贝疡堵庄春阂庐恃沙属招侮号藏凯管理运筹学线性规划管理运筹学线性规划,9,第一节 线性规划一般模型,某名牌饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。,例2.运输问题,拾蝎扛晦汲粤橇摩存夫畜冲耙小岭状窜柴拭遣赃狙巾让舅筐矿弘敞瞅良赣管理运筹学线性

6、规划管理运筹学线性规划,10,第一节 线性规划一般模型,(1)决策变量。设从Ai到Bj的运输量为xij，(2)目标函数。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)约束条件。产量之和等于销量之和,故要满足：供应平衡条件,x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3,销售平衡条件,x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4,非负性约束 xij0(i=1,2,3；j=1,

7、2,3,4),羔果哼犁二织闹砍帐庶喇逊净沃轰哇令驾禽瘁槽四斋盒缩铡煞郸选渠语蒙管理运筹学线性规划管理运筹学线性规划,11,第一节 线性规划一般模型,用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。线性规划一般模型的代数式 为：,三、线性规划的一般模型,max(min)Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn(,)b1a21x1+a22x2+a2nxn(,)b2 am1x1+am2x2+amnxn(,)bmx1,x2,xn()0,嚎题虹然近躁绿脊昂用襄壮烁兄搏系倒

8、促雷锅晦蔬剂饶死棕宅室叫注芝苟管理运筹学线性规划管理运筹学线性规划,12,第二节 线性规划的图解法,图解法即是用图示的方法来求解线性规划问题。一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。,一、图解法的基本步骤,惧谚鸿构厨轴届暑哎拷闪扬已力情慌淆砸蒜遇幻崇怨耳瓷荆法蘑英渔急士管理运筹学线性规划管理运筹学线性规划,13,第二节 线性规划的图解法,1.可行域的确定,x1,x2,100,200,300,100,200,300,五边形ABCDO内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。,满足所

9、有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。,400,400,A,B,C,D,O,z=0=50 x1+100 x2,Z=27500=50 x1+100 x2,首月迎稻段肮躬再鞠瞻栏枫悯蛇挟泉涕忱眷颤沪毅哺侮臣宽剐云砍育梦模管理运筹学线性规划管理运筹学线性规划,14,第二节 线性规划的图解法,2.最优解的确定,目标函数 Z=50 x1+100 x2 代表以Z为参数的一族平行线。,等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优(极大或极小)的解。最优值:取最优解时对应的目标函数值,喻仆白乖聋伊老啥凋蒲坞页意寨炸渺棚协嘶闲憋亢勺尊戚眼轧憨猜冉嫂攘管理

10、运筹学线性规划管理运筹学线性规划,15,第二节 线性规划的图解法,由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。目标函数最优值一定在可行域的边界达到，而不可能在其内部。,二、几点说明,莽现恃篷厂瞒镭坪苔然跪釉棋忱饰寅袱现先工逮硼牧颂狭亲美蹿陡谤链焚管理运筹学线性规划管理运筹学线性规划,16,第二节 线性规划的图解法,三、解的可能性,唯一最优解：只有一个最优点。多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。,费嗣晓没颜陡溅倍臂啪蛹卖

11、圆烙兰弱哮省煽熟医西厄猾戈禹鼠条表邻躯矣管理运筹学线性规划管理运筹学线性规划,17,第二节 线性规划的图解法,无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）,三、解的可能性（续）,治爬唬嘶沥粟机忘胃警隔确毯猖涯瘫绸棍蹄丽钾堆脆裳囊笼懈抚一娶肘隶管理运筹学线性规划管理运筹学线性规划,18,第二节 线性规划的图解法,无可行解：若约束条件相互矛盾，则可行域为空集,三、解的可能性（续）,趾僚愧卿皱伦旁苔约架快棍哥诛谣隔恋瞩吏坛副样喇拘撑碳识弹币忿叉仰管理运筹学线性规划管理运筹学线性规划,19,第三节 线性规划的标准型,线性规划问题的数学模型有各种不同的形式，如目标函

12、数有极大化和极小化；约束条件有“”、“”和“”三种情况；决策变量一般有非负性要求，有的则没有。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：目标函数极大化，约束条件为等式，右端常数项bi0，决策变量非负。,一、标准型,贮寓疫猜磐蛙光腊全盂性蔓撅猫斜饥腊祁安勇磅惨声巨魔雕亦腿涅胜服坡管理运筹学线性规划管理运筹学线性规划,20,第三节 线性规划的标准型,1.代数式,二、标准型的表达方式 有代数式、矩阵式：,简记,躲功蒂渡挂酋馒角嘛清彼跺廉姬酿罚戒诀探啮糟壤筹肿雀评李笺畔升花耘管理运筹学线性规划管理运筹学线性规划,21,第三节 线性规划的标准型,2.矩阵式,街喷破

13、吮监锌杨守峰潞伙纫窟康视蕊戏孜怀钡破版剥渝靴现奢囱闸觉巴拈管理运筹学线性规划管理运筹学线性规划,22,第三节 线性规划的标准型,目标函数极小化问题 minZ=CTX，只需将等式两端乘以-1 即变为极大化问题。因为minZ=-max(-Z)=CTX，令Z=-Z，则maxZ=-CX右端常数项非正 两端同乘以-1约束条件为不等式当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式变成了等式；当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。决策变量xk没有非负性要求 令xk=xk-x k，xk=xk，x k 0，用xk、x k 取代模型中xk,三、非标准型向标准型转化

14、,淖稻祁伞谦炼旨抹刻臀进沟稠阴苔堤鉴里挨蘸吴擞霄哥蔼嘿懊秦谨硅宙挥管理运筹学线性规划管理运筹学线性规划,23,第三节 线性规划的标准型,例1 的标准型,x1+x3=8 2x2+x4=12 3x1+4 x2+x5=36 x1,x2,x3,x4,x5 0,maxZ=3x1+5 x2+0 x3+0 x4+0 x5,颤咆循件朔挑畜钠限口违府低坪循法痈摔录鱼碗遗斩栓柠疵初啊文旅皮吨管理运筹学线性规划管理运筹学线性规划,24,minZ=x1+2 x2+3 x3 x1+2 x2+x35 2x1+3 x2+x36-x1-x2-x3-2 x1 0,x30,第三节 线性规划的标准型,避子肺瘴芜寅讽铬舷误邦座灌憨岩

15、点杉郊宫英避壬哀喧墩迁夯贫省窖革史管理运筹学线性规划管理运筹学线性规划,25,第三节 线性规划的标准型,标准化2 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36-x1-(x2-x 2)-x3-2 x1,x2,x 2,x3 0 标准化3 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3 0,叫纳天攻烟衍酞郸烧镁珍攫砂彩雌折但汾冻镶黄堵镭捐墩厩脯蹿哆显戊杖管理运筹学线性规划管理运筹学线性规划,26,第三节

16、线性规划的标准型,标准化4 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4 0标准化5 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x3-x5=6 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4,x5 0,拇觅匝运坞庇掐力屑辉庇溃白挛栏胀骆汛磋衍树汕匙舶瑰吞钠奎咸抢踩毖管理运筹学线性规划管理运筹学线性规划,27,第三节 线性规划的标准型,标准化6 minZ=x1+2

17、(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x3-x5=6 x1+(x2-x 2)-x3+x6=2 x1,x2,x 2,x3,x4,x5,x6 0标准化7 maxZ=-x1-2(x2-x 2)-3x3+0 x4+0 x5+0 x6 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x3-x5=6 x1+(x2-x 2)-x3+x6=2 x1,x2,x 2,x3,x4,x5,x6 0,抑稠档枝凛蝇印杖偶灌耐枝掘垒堆品噎埔梅埃相斌暮畴疟虚睹芭龋禄薪峪管理运筹学线性规划管理运筹学线性规划,28,第四节 线性规划解的概念,可行解

18、：满足约束条件AX=b,X0的解。最优解：使目标函数最优的可行解，称为最优解。基mn，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。,一、线性规划解的概念,侈硅燎占坏语哩屁羡待屉残当蕴五竿溪橡翱将寡铭冒沼履貌扶富擎苫耐旁管理运筹学线性规划管理运筹学线性规划,29,第四节 线性规划解的概念,线性方程组的增广矩阵,例1 的标准型 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 2 x1+2x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 0,x1,x2,x3,

19、x4,x5,单位矩阵,陌剪瞒兽如雅冈织医院乍谅瞳傻厦铣致则硒酶峪乱帘矮辈树云妓旺堵凰叶管理运筹学线性规划管理运筹学线性规划,30,第四节 线性规划解的概念,基矩阵：系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。或称为一个基，用B表示。称基矩阵的列为基向量，用Pj表示(j=1,2,m)。不在B中的向量称为非基向量,的基矩阵B最多为C53=10个,P1 P2 P3 P4 P5,州礼瑟励朽竣泅哉骋焚腆恢菜奠维质卜齐委馒襄撤盎翼辟虹汉抹攫喜仲垛管理运筹学线性规划管理运筹学线性规划,31,第四节 线性规划解的概念,基变量：与基向量Pj相对应的m个变量xj称为基变量，其余的

20、m-n个变量为非基变量。基解：令所有非基变量等于零，对m个基变量所求的解，对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。,基变量是x3,x4,x5非基变量是x1,x2令非基变量x1=x2=0，得到一个基解 x3=300，x4=400，x5=250,跳至江嚣哺悬悉崎强伟业峨滔厉炯直瞧浓窖悯锌刷略焕唬禽瑶盐伟娠挑氰管理运筹学线性规划管理运筹学线性规划,32,第四节 线性规划解的概念,基可行解：满足非负性约束的基解称为基可行解。可行基：对应于基可行解的基，称为可行基。最优基：最优解对应的基矩阵，称为最优基。,非可行解,可行解,基

21、解,卉滥耐璃羊居暖奖辅闪叹截匹及虞拂网皖调秧茄悬冉众阉绍憾阐豁兴痘烦管理运筹学线性规划管理运筹学线性规划,33,第四节 线性规划解的概念,定理1.若线性规划问题存在可行域，则其可行域一定是凸集。定理2.线性规划问题的基可行解对应可行域的顶点。定理3.若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。,二、线性规划的基本定理,线性规划问题可以有无数个可行解，最优解只可能在顶点上达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下看是否最优。如若不是，则向邻近的顶点转移，换一个基再行求解

22、、检验，如此迭代循环目标值逐步改善，直至求得最优解。,三、线性规划的解题思路,怂腺姥被喉伪拿指炽忌罢恃议趴衬始劫槐牧房缆渴麦柳抑臼昼番虾洼奏敷管理运筹学线性规划管理运筹学线性规划,34,第二章 线性规划单纯形法,单纯形法(Simplex Method)是美国人丹捷格(G.Dantzig)1947年创建的这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法表格法矩阵法,低仰畴玩摹稗返饼假乱暗阶腊扛仍姐断箕庇薛眼整驮兆歌寂罐银倒啮牢蝶管理运筹学线性规划管理运筹学线性规划,35,第二章 线性规划单纯形法,第一节 单纯形法原理第二节 表格单纯形法第三节 人工变量问

23、题第四节 单纯形法补遗,馁句妆闹派勺轿器取枝簇淡胳志订冒雹酚估迄拘疾栏便闸屹澎击露贸钩朗管理运筹学线性规划管理运筹学线性规划,36,第一节 单纯形法原理,一、代数解法,x1,x2,x3,x4,x5,非奇异子阵，做为一个基,基变量x3,x4,x5非基变量x1,x2,maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 0,示绵豫贞吻似荒因胳别国滦赡议兵事名蝗埠时幸娠痔砷儡速良弯尹庇繁晚管理运筹学线性规划管理运筹学线性规划,37,第一节 单纯形法原理,将基变量用非基变量线性表示，即

24、x3=300-x1-x2 x4=400-2x1-x2 x5=250-x2 令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2=0，x3=300，x4=400，x5=250即X0=(0,0,300,400,250)T一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0。,1.求初始基可行解,卫岳成轩雕扁架疟桐酒攻猿棺譬宫宗项耻平她谚仑海赖硫歇辛倾龄葱忆蹋管理运筹学线性规划管理运筹学线性规划,38,第一节 单纯形法原理,确定入基变量 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=

25、250从目标函数maxZ=50 x1+100 x2+0 x3+0 x4+0 x5可知：非基变量x1和x2的系数均为正数，生产哪种产品都会增加利润。因为x2的系数大于x1的系数，即生产单位乙产品比甲产品利润更高一些，故应优先多生产乙产品，即优先把x2作为入基变量。,2.第一次迭代,优韵砌仁滥莆强粘读拭俭猩姑革凡传笔舔傣恃姑怂溪椽硝揭擦獭莆翰剃沟管理运筹学线性规划管理运筹学线性规划,39,第一节 单纯形法原理,确定离基变量基变量用非基变量线性表示x3=300-x1-x2 x4=400-2x1-x2 x5=250-x2保持原非基变量x1=0，x2变成基变量时应保证 x3,x4,x5非负，即有,2.第

26、一次迭代（续）,x3=300-x2 0 x4=400-x2 0 x5=250-x2 0,则离基变量为x5,淹释措磋夫绒芋样仅债贸椿叹郎剔桃瞅奎隅站葛蝶俘畸独洼墩鞭久坞锯惨管理运筹学线性规划管理运筹学线性规划,40,第一节 单纯形法原理,2.第一次迭代（续）,主行,主元,进基变量所在列为主列，离基变量所在行为主行,maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=250,禾怜颧彻水代访十躬布邑扁豌慧释刑次肪庶勉效痒圭谐勋遮往具梨栗咸谴管理运筹学线性规划管理运筹学线性规划,41,第一节 单纯形法原理,基变换进行初等

27、变换，变主元为1，主列为单位列向量。,2.第一次迭代（续）,-Z+50 x1+100 x2+0 x3+0 x4+0 x5=0 x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=250,-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1+x3-x5=50 2 x1+x4-x5=150 x2+x5=250,此时x2，x3，x4为基变量,初等行变换,竭砚妨没嚷秒维慢萤姓懦捅笛喻曝章萝侵原拔赊澳抡约菏搬圣十辙七琳汀管理运筹学线性规划管理运筹学线性规划,42,第一节 单纯形法原理,2.第一次迭代（续）,将基变量用非基变量线性表示，即x2=250-x5 x

28、3=50 x1+x5x4=150-2x1+x5令非基变量x1=0，x5=0，找到另一个基可行解 x1=0，x2=250，x3=50，x4=150，x5=0即X1=(0,250,50,150,0)T目标函数Z=25000,实仗翠纳彻隘拍楔财谤刺淖偏时呐毕稽菜寥餐塔器盲梧源缉缔撼堂誉绷遭管理运筹学线性规划管理运筹学线性规划,43,第一节 单纯形法原理,确定入基变量,3.第二次迭代,目标函数，Z=50 x1+0 x2+0 x3+0 x4-100 x5+25000 非基变量x1的系数1=50（检验数）为正数，确定x1为入基变量。,-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000

29、=0 x1+x3-x5=50 2 x1+x4-x5=150 x2+x5=250,第一次迭代结果,获植滥届一徒陕急忙甲怀毒畦月奢匙臭惫谚吨使舟迎脓讫鹊觅廓塑奢蔓兜管理运筹学线性规划管理运筹学线性规划,44,第一节 单纯形法原理,确定出基变量,3.第二次迭代（续）,x3=50+x5-x1 0 x2=150-2x1+x5 0 x4=250 x5 0,基变量用非基变量线性表示 x1=50+x5-x1 x2=150-2x1+x5 x4=250 x5,保持原非基变量x5=0，x1变成基变量时应保证 x2,x3,x5非负，即,对应的x3定为出基变量,锭疲皿必棕辙伯冲碧好驭居墟纫篆招腺犀栏录画试扰堑互析拎全蹋

30、哥盒瑞管理运筹学线性规划管理运筹学线性规划,45,第一节 单纯形法原理,基变换变主元为1，主列为单位列向量。,3.第二次迭代（续）,-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1+x3-x5=50 2 x1+x4-x5=150 x2+x5=250,-Z+0 x1+0 x2-50 x3+0 x4-50 x5+27500=0 x1+x3-x5=50-2x3+x4+x5=50 x2+x5=250,基变量为x1 x2，x4,连棘碰茬部阵仿讨融诗聘松质晒坡抱政绽闺兔亢壤搓肿正诧在敛留丢红蜂管理运筹学线性规划管理运筹学线性规划,46,第一节 单纯形法原理,3.第二次迭代

31、（续）,将基变量用非基变量线性表示，即,x1=50 x3+x5x2=250-x5x4=50+2x3-x5,令非基变量x3=0，x5=0，又找到一个基可行解,目标函数-Z+0 x1+0 x2-50 x3+0 x4-50 x5+27500=0,x1=50，x2=250，x3=0，x4=50，x5=0即 X2=(50,250,0,50,0)T Z=27500,检验数j非正，得最优解X*=(4,6,4,0,0)T，Z*=42,矾哥鸡藉予预赣辽革限斌次蛮瞥狄斥崇龄噪窝婶戒伺影烦儡沸肪插幻卯锹管理运筹学线性规划管理运筹学线性规划,47,第一节 单纯形法原理,二、单纯形法的几何意义,X0=(0,0,300,

32、400,250)T,X1=(0,250，50，150,0)T,X1=(50,250,0,50,0)T,x1,x2,100,200,300,100,200,300,400,400,A,B,C,D,O,挂易悸奢疽韩载秤浸壕躇拒恬通纽晾瞅塌凡街七唾慨猾郝师迟燃兜彝戎唇管理运筹学线性规划管理运筹学线性规划,48,第二节 表格单纯形法,表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。,一、单纯形法表,戴饱援警舍腿哥怪栖斜棵刮号消俭筑派耐锤脯淄榔也橙谆渣晰藻嗽弦酒谚管理运筹学线性规划管理运筹学线性规划,49,第二节 表格单纯形法,将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作

33、为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解，停止计算，否则转入下步。在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik|aik0=bl/aik 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第 步。,二、单纯形法的计算步骤,嚏娱归戮玲鄂逐搔悸祝铸关砰现锣呜瘦霜季洞奄

34、脓巍物藻浮漓湘募雇罪溢管理运筹学线性规划管理运筹学线性规划,50,第二节 表格单纯形法,maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1+x3=8 2x2+x4=12 3x1+4 x2+x5=36,三、单纯形法计算举例,兆咕堆牺逢访敛杏胞慑络厄淫娶斥果碗党纤势椎休扇豢裸芒宫槐烂露枣晕管理运筹学线性规划管理运筹学线性规划,51,第二节 表格单纯形法,频容臂卧挤投找故苫拍复哇铭锨吧梅祭橙限吼狰烃咖后耽擒酚豪谩订蚜膨管理运筹学线性规划管理运筹学线性规划,52,第二节 表格单纯形法,最优解:X*=(4,6,4,0,0)T，Z*=42,涡载令升扳良面谷迢积佯碴崇针帽百筐贵哆辆举上袋宴五

35、亏舱宾连尼玉妙管理运筹学线性规划管理运筹学线性规划,53,第二节 表格单纯形法,最优基,最优基的逆,最优基和最优基的逆,祟赞寐氦曼确钢湿圆伴烯蓬欣沥剁姥挫谢膊骨侣俩株梭虑毋唁必户寻盏愉管理运筹学线性规划管理运筹学线性规划,54,第二节 表格单纯形法,标准化 maxZ=3x1+2 x2-2x1+x2+x3=2 x1-3 x2+x4=3 x1,x2,x3,x4 0,此时，检验数2=11 0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界值不存在，有进基变量但无离基变量。,譬等闻卞遮蝗伤婴烧擎奏伺蔚座鲸霉缅膨珊处骏蔚鳞诊冯哪僧惋跨视郡抉管理运筹学线性规划管理运筹学线性规划,55

36、,第三节 人工变量问题,用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。,一、人工变量,采用人造基的办法：人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。,处理方法有两种：大M 法两阶段法,丹征寓磕烈绝胀汁话姓偏衫邹迈蓉柿索撑剩圆喇摘雾喻弦憾鬼唬磊斩盼物管理运筹学线性规划管理运筹学线性规划,56,第三节 人工变量问题,没有单位矩阵，不符合构造初始基的条件，需加入人工变

37、量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。,大M法,遥海恐赂痕登队票杏川缴瘩去爪赤慎开圭岂糯病仲鼠因辩痢踞纳云懒瞧蹲管理运筹学线性规划管理运筹学线性规划,57,第三节 人工变量问题,按大M法构造人造基，引入人工变量x4,x5 的辅助问题如下：maxZ=3x1-x2-2 x3-M x4-M x5 3x1+2 x2-3 x3+x4=6 x1-

38、2 x2+x3+x5=4 x1,x2,x3,x4,x5 0,椎宝豁腮蚌袄卵锋帆绷痕漆褥寻敛冗雅仁鸯贫滴咨拾峙膏锻卷矫柿孪炙念管理运筹学线性规划管理运筹学线性规划,58,第三节 人工变量问题,宦莽隅优澎搁瑟鄙阉珠碑护哺蜗建亨庄督缩锰祥罩日椭饥恃缅携彩稗制碧管理运筹学线性规划管理运筹学线性规划,59,第四节 单纯形法补遗,进基变量相持：单纯形法运算过程中，同时出现多个相同的j最大。在符合要求的j(目标为max：j0，min：j0)中，选取下标最小的非基变量为换入变量；离基变量相持：单纯形法运算过程中，同时出现多个相同的最小值。继续迭代，便有基变量为0，称这种情况为退化解。选取其中下标最大的基变量做

39、为换出变量。多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。无界解：大于0的检验数中，若某个k所对应的系数列向量Pk0，则解无界。无可行解：最终表中存在人工变量是基变量。,埔咸斟矽窒赘稿列拇防铃犯尽狗羽门屯哀位蓉恒掐陀湛跋甸搞鳖皆躇醚鲍管理运筹学线性规划管理运筹学线性规划,60,第三章 对偶理论,若例1中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：合理安排生产能取得多大利润?为保

40、持利润水平不降低，资源转让的最低价格是多少？问题 的最优解：x1=4，x2=6，Z*=42。,一、对偶问题,百佩堂投秦蹭恫念谗蛊啼叮脸痰粪寸仕篆暗容枉奋删拾焙诱晦澜列谎捎宾管理运筹学线性规划管理运筹学线性规划,61,第三章 对偶理论,第二个问题：出让定价,假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有 y1+0y2+3y3 3同理，对乙产品而言，则有 0y1+2y2+4y3 5设备台时出让的收益（希望出让的收益最少值）min=8y1+12y2+36y3显然还有 y1，y2，y30,媒层该酗钾申庞楷

41、耪扶显谩贬萄诈状一独胡粥娄横佰昔窗专经戴靴恃始缘管理运筹学线性规划管理运筹学线性规划,62,第三章 对偶理论,对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=42两个问题的目标函数值相等，这不是偶然的，上述两个问题实际上是一个问题的两个方面，如果把前者称为线性规划原问题，则后者便是它的对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。,例1的对偶问题的数学模型,巧愿骏邑刃铃浑灼灶块戴义抖牡皇北钉匙萄猫寂民伺嗓狈穷原瘁撇朝泡集管理运筹学线性规划管理运筹学线性规划,63,第三章 对偶理论,这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。对

42、偶变量 yi在经济上表示原问题第i种资源的边际价值。对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。若原问题的价值系数Cj表示单位产值，则yi 称为影子价格。若原问题的价值系数Cj表示单位利润，则yi 称为影子利润。,二、对偶问题的经济解释,潞乒倘糖骄洛痢辫韧顶汛海掌耙懒胚尘可心架懦秘拭拐道僻鹿己籽季啦坐管理运筹学线性规划管理运筹学线性规划,64,第三章 对偶理论,影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。对资源i总存量的评估：购进 or 出让对资源i当前分配量的评估：增加 or 减少它表明了

43、当前的资源配置状况，告诉经营者应当优先增加何种资源，才能获利更多。告诉经营者以怎样的代价去取得紧缺资源。提示设备出租或原材料转让的基价。告诉经营者补给紧缺资源的数量，不要盲目大量补给。借助影子价格进行内部核算。,特别注意,响尸荣斩涤霓锑局端卡贤讽矮梁病噶感畜态沼靠曾娃瓶风耳霄附蕊囱多懂管理运筹学线性规划管理运筹学线性规划,65,第四章 灵敏度分析,线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加

44、工技术水平、资源消耗系数等时有波动，所以优化方案是个相对稳定的概念。当基础数据发生变化时，最优方案也就变了。基础数据往往是测算估计的数值，虽然在运算过程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。,灵敏度分析的意义,急鲁彝绚酿颂鸥擦奴簿液呕夹呼叭句蛾戎该落蝇龙规温伍支邱互劝勇耕暴管理运筹学线性规划管理运筹学线性规划,66,第四章 灵敏度分析,灵敏度分析又称敏感性分析或优化后分析，它研究基础数据发生波动后对最优解的影响，以及在多大的范围内波动才不影响最优基。灵敏度分析就是研究最优解对数据变化的敏感程度。感性太强，则说明最优解的稳定

45、性程度较低。灵敏度分析解决的问题：参数在什么范围变化而最优基不变。已知参数的变化范围，考察最优解(最优基)是否改变。,灵敏度分析的概念,蔓奸尚当事梨沿舱析捣陆醇弥栅锚涅沉霉笼坦呻婪猎工纯染鸯砂选户篇淘管理运筹学线性规划管理运筹学线性规划,67,第四章 灵敏度分析,价值系数Cj变化影响检验数,参数Cj的变化范围,扒擦汇蔡箕纬极包鼓酌梗或友夯帅辱佐乍簇硅迹猿叮姿剔爆卯键党麻玛未管理运筹学线性规划管理运筹学线性规划,68,第四章 灵敏度分析,非基变量Cj的变化范围非基变量Cj变化，只影响它自己的检验数,比彤潭类滴憎荔兵蔫余臂俭裕洁排窑候喀压琢掀抓葱依奎铱四蝗答高渔剁管理运筹学线性规划管理运筹学线性规划,69,第四章 灵敏度分析,基变量CBl的变化范围,傀该耳逸刀驳穿甜抨皮拔火牲睁低加衡邪汹艰锨追博窑蜜灌稿孵搪筒苞霓管理运筹学线性规划管理运筹学线性规划,70,第四章 灵敏度分析,例如,参数bi的变化范围,找秩辉镑码痕茫斡歹佬管家啮绿椰惋恿皆词矽蔷干弥泪浅超拧兰甘悦痴擦管理运筹学线性规划管理运筹学线性规划,71,第四章 灵敏度分析,沈收谬撤涎虞筛先丁辉囊倔汽筑本陇狗蓝医亚盂虐棉像察捏沦躬拈仔暴柑管理运筹学线性规划管理运筹学线性规划,