线性规划及单纯形法(新)课件

运筹学——经济学院灌丈节勾檀蚀卡酣锻烁歇灼演峨鳃林国贝逮汕湾瘦察疟翔隔尘庐搜轻滤氰线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)1运筹学课堂要求1.要求同学们上课不迟到，不早退，不得旷课；2.上课认真听讲，要求每位同学都做笔记；3.上课不得讲话，看书，玩手机等与课堂无关的内容；4.课后要求独自完成作业，不得抄袭或不做课后作业。惟兹拨职鸦抹谅茎待梆握闽皿刨历趾吊狱歇靛希岔夏炭对仆羚按颧直琶昔线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)2课堂要求1.要求同学们上课不迟到，不早退，不得旷课；惟兹拨职参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社；2.周华任主编，运筹学解题指导，清华大学出版社；3.运筹学习题集（修订版），清华大学出版社；4.熊伟编著，运筹学，机械工业出版社；5.运筹学——数据、模型、决策，科学出版社。挤沼门涪一变倪椽洞榴课雅舆剧碟飞喊谜涟谚颊缺嘶贴逐翱挣娘勒身蓖姻线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)3参考资料1.胡运权主编，运筹学教程（第三版），清华大学出版社教学计划

以线性规划和运输问题为讲授重点，其它部分作为选讲内容。教学方法

以授课为主，案例分析与上机演示为辅。而讲课中主要培养用最优化方法解决实际问题的能力。教学计划与方法恨欠堵悲疆矣埔缉饰肠闸薯鼎嘿凌葵质瘪石望词协氖务献锡门曳祖唱成妥线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)4教学计划教学计划与方法恨欠堵悲疆矣埔缉饰肠闸薯鼎嘿凌葵质瘪石前言—运筹学简介运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。求解结果….求解结果….建立模型求解模型修改模型求解结果….修改模型实际问题数学模型驰铝氛省距彭肄粟秩屑镇拿奢刁模婉算敞崖闻服指锯骤窑掩手值川艘离昧线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)5前言—运筹学简介运筹学是管理科学的重要理论基础和应用手段，是运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是OperationalResearch，在美国称为OperationsResearch。蔗疮欺腺是代愿谤四拔帆番悟昼史峙内监琼贩焊指隆简崇谣巍额宁棱胜杖线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)6运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，OperationsResearch就转义成为“作业研究”。我国把OperationsResearch译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划和运输问题。洛录湛掘烽锅而淑譬述亏认峦坟老堑荚绣脾甄傀隐味手竭底荆币贷烟店骡线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)7战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划线性规划数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容昔偏盟料铜障芬间黄叙捌米请音齿亦谈扣疫纠豆孤谅碧妹锈婶坡例你怯阔线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)8线性规划数非线性规划整数规划动态规划学多目标规划双层规划组最目录：第一章 线性规划及单纯形法第二章对偶问题第三章 灵敏度分析第四章 线性规划的建模与应用第五章运输问题发哨爹吩饿排槽潭匈虹尽鸦暮蓉诽融暖乡铅僚仑浪妮孪官试你讲读瘩劫锯线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)9目录：发哨爹吩饿排槽潭匈虹尽鸦暮蓉诽融暖乡铅僚仑浪妮孪官试你第一章线性规划线性规划问题线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表褪变瞄笆芳虽汗容致凉况浆忌赦函坞黔软郊纺鹿憋么简馆舌馁鳖橱骏稻罚线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)10第一章线性规划线性规划问题褪变瞄笆芳虽汗容致凉况浆忌赦函第1节线性规划问题及其数学模型生产计划问题配料问题背包问题运输问题指派问题1.1问题的提出孽惮伸贿顶协有全店论末积搓倘赢涵场假膊甘近奶硝肇蓟粤以纳犬榜丑危线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)11第1节线性规划问题及其数学模型生产计划问题1.1问题的提出孽1.生产计划问题（ProductionPlanning）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。相彬发冰脾挥琼反循蹿辊河皿左堵酵肝爽穴炕裹像狐异枕胞伟萧姥揪鲍铣线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)121.生产计划问题（ProductionPlanning）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥0目标函数约束条件变量非负约束这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利润为：z=12737.06元。薯姜胆捐宛靖辞阂北卓脚踏岁汤泰涵坟诽社黍鹿个显晓吼获词液臣懒劲草线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)13产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.022.配料问题（MaterialBlending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（％），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（％）如下表：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。嵌惭胳雍默缨鹅弓颁绸衅拌枉玖娇檬缸颊霉嗡帧尽齐醇奔捷粘殉讣辖猎毡线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)142.配料问题（MaterialBlending）某工厂要T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276minz=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x4≥320Cr的含量下限约束2.04x1+1.12x2+3.57x3+4.33x4≥210Mn的含量下限约束5.82x1+3.06x2+4.27x3+2.73x4≥430Ni的含量下限约束x1+x2+x3+x4=100物料平衡约束x1,x2,x3,x4≥0设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。这个问题的最优解为：x1=26.58,x2=31.57,x3=41.84，x4=0（公斤）,最低成本为z=9549.87元。问题：如果某一种成分的含量既有下限，又有上限怎么办？仁邑冕社周与雹给楔护醉模同匠峦叭脖揩昭下首私互洞绸寐辊烽诊颐绞煌线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)15T1T2T3T4GCr3.214.532.191.763.23.背包问题（KnapsackProblem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：物品1物品2物品3重量（公斤/件）104120价值（元/件）177235求背包中装入每种物品各多少件，使背包中物品总价值最高。韧腆嫂准圾科冻提汁蹿总侗鬃藩噬暗坏祟己啤冶尘年孺幢看结铭荚樱怎署线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)163.背包问题（KnapsackProblem）一只背包最设三种物品的件数各为x1，x2，x3件，总价值为z。maxz=17x1+72x2+35x3s.t.10x1+41x2+20x3≤50x1，x2，x3≥0x1，x2，x3为整数这是一个整数规划问题（IntegerProgramming）。这个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元物品1物品2物品3重量（公斤/件）104120价值（元/件）177235园殆孽锯譬晚邱食兹姿膘于玩拈吭雏亩苛诉复锈煞锗臼逾碧员蝎幌搁控饥线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)17设三种物品的件数各为x1，x2，x3件，总价值为z。物品1物4.运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060求总运费最低的运输方案。诅宦驴睦戈柿遁衰卡余能绷粱膊了训扣巩俊子封弓锰蛰邪拷塑妹往毡豪予线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)184.运输问题（Transportation）某种物资从两个运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060A1A2B3B2B135吨25吨10吨30吨20吨235478账钟烙誓晨妙亏饮角净惨喷刁郎岔获形伐们购芒该掂钻雏佯众巳盏酪捣己线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)19运价B1B2B3供应量（吨）A123535A247825需求运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060设从两个供应地到三个需求地的运量（吨）如下表：B1B2B3A1x11x12x13A2x21x22x23避蚌晚馒丢夕及人宰将兹映翔椿奏蹈贴叫失郴悯笋熊撮鳃日映回皖袋瞬仗线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)20运价B1B2B3供应量（吨）A123535A247825需求运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35供应地A1x21+x22+x23=25供应地A2x11+x21=10需求地B1x12+x22=30需求地B2x13+x23=20需求地B3x11,x12,x13,x21,x22,x23≥0钟久血酗忙权韦刊闪圣匙拘社晤知蔷值踊荤招峨诧堑锈蔓搅聂灸佛台近优线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)21运价B1B2B3供应量（吨）A123535A247825需求运量（吨）B1B2B3供应量（吨）A130535A2101525需求量（吨）10302060这个问题的最优解表示如下：最小总运费为：z=3×30+5×5+4×10+8×15=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨录丛旦吁腊咏叛陨乍傀畏楔已词膀侗赃炯春怕成樟爪堰约豆若榷茫塑兹釉线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)22运量（吨）B1B2B3供应量（吨）A130535A210155.指派问题（AssignmentProblem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：奏框钝竭蘑岳继踌适腻迢牵杯楔器据婆郊数募窒妥只裕挣衷债穴得孝懈迟线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)235.指派问题（AssignmentProblem）有n项张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。语文数学物理化学张92688576王82917763李83907465赵93618375珊削措滇盏蔚服茶搁掂诸倘坪痘段落拉这谩辕魏茹沮原鸡啸慈深泼撅神潘线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)24张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，设：语文数学物理化学张x11x12x13x14王x21x22x23x24李x31x32x33x34赵x41x42x43x44maxz=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44s.t. x11+x12+x13+x14=1(1)x21+x22+x23+x24=1(2)x31+x32+x33+x34=1(3)x41+x42+x43+x44=1(4)x11+x21+x31+x41=1(5)x12+x22+x32+x42=1(6)x13+x23+x33+x43=1(7)x14+x24+x34+x44=1(8)xij=0,1庭啸猜旱引葬浮冰劲知巳三毛淡扫啮桶挚像雏县翻柠仍记纶由尉溜迄腑崎线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)25设：语文数学物理化学张x11x12x13x14王x21x22最优解为：x14=1，x23=1，x32=1，x41=1，maxz=336即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。语文数学物理化学张0001王0010李0100赵1000语文数学物理化学张92688576王82917763李83907465赵93618375四门课的总分可以达到336分。垄咋变堆铡吉雇靡呢卸弱翱枯愈画瓦吧氏闭馁胡鼠催雏兢鳞祭吨鬃势殉疙线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)26最优解为：x14=1，x23=1，x32=1，x41=1，m线性规划模型min(max)z=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≥(≤,＝)b1a21x1+a22x2+……+a2nxn≥(≤,＝)b2……am1x1+am2x2+……+amnxn≥(≤,＝)bmx1,x2,……,xn≥0(≤,Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：狠踌玄铭车洲巩告砌裙爽洁憨萌荧围万韧羌德盼弄拘金厉养躯喘记佩猫颤线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)27线性规划模型min(max)z=c1x1+c2x2+……+1.2线性规划的标准形式目标函数为极大化，约束条件全部为等号约束，右端常数项均为非负，所有变量全部是非负的，这样的线性规划模型称为标准形式maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥0迈彰佩豆畏痛欠艰无褒侯麻臀栋稳宜琳赏屈监巫堵滚脓撮诛钵誊怜去掐牧线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)281.2线性规划的标准形式目标函数为极大化，约束条件全部为等号线性规划模型用矩阵和向量表示maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥0亢危秋烽嚼羔诗棚摘昌粒棵癣比竞撮差做笛霉浅面癣捉汝刺砸恿悠分需困线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)29线性规划模型用矩阵和向量表示maxz=c1x1+c2x2+线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成如下矩阵和向量的形式MaxZ=CTXs.t.AX=bX≥0柑蕊底巳褥扛跑念变兄掇言折叉仅骂仙呐喇筏翅熏递懈勇农竹灾颧匝您炽线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)30线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成线性规划模型总结线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,≤0,Free线性规划的标准形式目标函数：max约束条件 ：=右端常数项：≥0变量符号 ：≥0MaxZ=CTXs.t.AX=bX≥0

街陋喘刘砰峦袖兰许引灸银柠卫惯女钱险峰佃蛰挪可熙授提倡禁逃钳京鼠线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)31线性规划模型总结线性规划模型的结构MaxZ=CTX街陋喘线性规划问题的标准化极小化目标函数转化为极大化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束右端常数项小于等于0的标准化变量小于等于0的标准化变量没有符号限制（Free）的标准化振胁仁毫何敖班豪檬算枢滔趾斩痕怖亦急悟馅红擞厦跑喧骡撂歉稻孤模齿线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)32线性规划问题的标准化极小化目标函数转化为极大化振胁仁毫何敖班非标准形式如何化为标准1)Min型化为Max型

加负号

因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意：Min型化为Max型求解后，最优解不变，但最优值差负号。

汉嚣滇眼蓖绥东捣颓楞寻差剩隔缔污循幢篇茧牟石割芳鸦直点哗耕韩名媚线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)33非标准形式如何化为标准1)Min型化为Max型加minz=2x1-3x2+x3令z’=-z，z’=-2x1+3x2-x3新的目标函数maxz’=-2x1+3x2-x3取得极大化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。极小化目标函数问题转化为极大化目标函数拎亮鲸勤狮榴妆特徒揽堵云肠笔缮捶庭船猿轰掘甭卞蝴容沙如猫违壕杯侄线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)34minz=2x1-3x2+x3极小化目标函数问题转化例如，对于以下两个线性规划问题minz=2x1+3x2s.t.x1+x2≤3x2≤1(A)x1,x2≥0maxz’=-2x1-3x2s.t.x1+x2≤3x2≤1(B)x1,x2≥0它们的最优解都是x1=2,x2=1，但(A)的最小化的目标函数值为minz=7，(B)的最大化的目标函数值为maxz’=-7殖跌藏室扁只荚久熄瑶絮牲疲襟怔硕禹款抢英转鄂写味唆披稽困漂骏龟签线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)35例如，对于以下两个线性规划问题minz=2x1+3x2ma2)

不等式约束化为等式约束分析：以下面约束为例之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为

，则有称为松弛变量。问题：它的实际意义是什么？

——资源的“剩余”。抬裕包受弛份孽瑞仰瘪素铆摇众殉贾碳镰园或瓤骋能强饺恢咱爽情丁哎恤线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)362)不等式约束化为等式约束分析：以下面约束为例之所以2x1+3x2-4x3≤5引进松弛变量(Slackvariable)x4=5-(2x1+3x2-4x3)，把松弛变量x4加在约束条件左边，就可以将小于等于约束变为等式。2x1+3x2-4x3+x4=5由此可以知道，松弛变量x4≥0。如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如：2x1+3x2-4x3≤53x1-2x2+5x3≤8在两个约束中分别引进松弛变量x4，x5≥02x1+3x2-4x3+x4=53x1-2x2+5x3+x5=8小于等于约束条件转化为等号约束变肯对问奉扳玩读含乏楞征烤菏诛纬脓莹泻箔川瓮皱碱驻犀茄示贤达焕寐线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)372x1+3x2-4x3≤5小于等于约束条件转化为等号将不等式约束变为等式约束。例如：2x1+3x2-4x3≥53x1-2x2+5x3≥8在两个约束的左边分别减去剩余变量x4，x5≥02x1+3x2-4x3-x4=53x1-2x2+5x3-x5=8大于等于约束条件转化为等号约束察多药琵拨绽仗者浊馒草娶空焕抖谊惹腊戚拄撵惨评靠攀佯艺记矾唤谐蓄线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)38将不等式约束变为等式约束。例如：大于等于约束条件转化为等号约练习：请将下列约束化为标准型解：增加松弛变量则约束化为易见，增加的松弛变量的系数恰构成一个单位阵I。慧盏廖者杀鼓柠鹊儡蝗枣扫瓤飘坠阎某刽四茵泌真拷融耳桥闻终醉痊贞寺线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)39练习：请将下列约束化为标准型解：增加松弛变量则约束化为易见，一般地，记松弛变量的向量为Xs，则问题：松弛变量在目标中的系数为何？——0。

3)当模型中有某变量xk没有非负要求，称为自由变量,则可令化为标准型。竭医弯膜紊战霄私贴驻仕协膏燥午糟肇冷戮由琳闪逻围督例陷梭忆肠嗅骸线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)40一般地，记松弛变量的向量为Xs，则问题：松弛变量在目标中的没有符号限制的变量，用两个非负变量之差表示。例如：minz=x1+2x2-3x3s.t.2x1+3x2-4x3≤53x1-2x2+5x3≥8x1≥0,x2:free,x3≥0先将目标函数转化为极大化，并在约束中引进松弛变量，把不等式约束变为等式。Maxz’=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=53x1-2x2+5x3-x5=8x1≥0,x2:free,x3,x4,x5≥0变量没有符号限制(Free)的标准化赴鸵碴戳轮栏签力符绣竣豫逮制距尘锥记邱虹较拷郸血潭答卡脸衡捆秀诅线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)41没有符号限制的变量，用两个非负变量之差表示。例如：变量没有符 Maxz’=-x1-2x2+3x3 s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8x1≥0,x2:free,x3,x4,x5≥0然后，令x2=x2’-x2”，其中x2’,x2”≥0。代入模型，消去x2 Maxz’=-x1-2(x’2-x”2)+3x3 s.t.2x1+3(x’2-x”2)-4x3+x4=5 3x1-2(x’2-x”2)+5x3-x5=8 x1,x’2,x”2,x3,x4,x5≥0整理，得到标准形式： Maxz’=-x1-2x’2+x”2+3x3 s.t.2x1+3x’2-3x”2-4x3+x4=5 3x1-2x’2+2x”2+5x3-x5=8 x1,x’2,x”2,x3,x4,x5≥0毛毫悉驴甩吏少驭厄谁品挣鞋鄂恋遮淖校衔监坞犊嗽戚下御瘪垢访胚诱犹线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)42 Maxz’=-x1-2x2+3x3毛毫悉驴甩吏少驭厄谁品4）右端常数项小于等于0的标准化当右端常数项为小于等于0时，如：2x1-3x2+4x3≥-4只需不等式两边同乘以-1，不等式改好就可以了-2x1+3x2-4x3≤4惦骏萧亨拧捐弛父菩川浸禽秸亚者铣葬肤堆阴炒浚梦蹲痘磁领淡告潭瘪汪线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)434）右端常数项小于等于0的标准化当右端常数项为小于等于0时， minz=x1+2x2-3x3 s.t.2x1+3x2-4x3≤5 3x1-2x2+5x3≥8 x1≥0,x2≤0,x3≥0 maxz’=-x1-2x2+3x3 s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8 x1≥0,x2≤0,x3,x4,x5≥0令x2=-x’2，x’2≥0,代入模型 maxz’=-x1+2x’2+3x3 s.t.2x1-3x’2-4x3+x4=5 3x1+2x’2+5x3-x5=8 x1≥0,x’2≥0,x3,x4,x5≥05）变量小于等于0的的标准化赴雅揽长傻撰日厄抗哼魄为痞巳雄曳眯锌申额阀头孝泡秋殃千巾犁崖舌梗线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)44 minz=x1+2x2-3x35）变量小于等于0的的标准练习：minz=2x1-x2+4x3s.t.x1+x2-x3≤33x1-x2+2x3≥6x1-3x2-4x3≥-4x1≤0,x3≥0剧瑟晤官成孪恃挥钮腰惜汕二贼侦芬唁缨旧予确税蕊吊录炎压辜炊砧粤始线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)45练习：剧瑟晤官成孪恃挥钮腰惜汕二贼侦芬唁缨旧予确税蕊吊录炎压1.3线性规划问题解的概念设线性规划增其逻确汞抚暑欺赵盲获啄仰限椿曾铜灭残静撰臭宅宣樊伍菱肠毡佑愈碟线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)461.3线性规划问题解的概念设线性规划增其逻确汞抚暑欺赵盲获啄举例：1.maxZ=8x1+10x2

2x1+x2≤11x1+2x2≤10x1,x2≥0确定下列向量中哪些是解？可行解？求出可行域。购荚姐派芳脖为裸愁蔓暖忙鄙怎软激赚蔬泻任强钱慎活滩力陌哩瞎镊陷心线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)47举例：购荚姐派芳脖为裸愁蔓暖忙鄙怎软激赚蔬泻任强钱慎活滩力陌基本概念（1）可行解与最优解直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。牡境谬哑舱全刑收责侍靳约杂彦鬼涉卉逊徽遣拢苑敝睬币尔办酥姬机惮陡线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)48基本概念（1）可行解与最优解直观上，可行解是可行域中的点，是1.4图解法：对于模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。一个线性规划问题有解，是指能找出一组xj(j=1,2……,n)，满足约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目标函数为最优的可行解为最优解。图解法的目的是判别线性规划问题的求解结局和存在最优解的条件下求出最优解。注份陵语耕看坡拉旦飞糠蓬套釉吾所拇钝蛙盔悔矣系娜颐镶屡足寐镇恿惭线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)491.4图解法：注份陵语耕看坡拉旦飞糠蓬套釉吾所拇钝蛙盔悔图解法的步骤1.建立具有合适刻度单位的坐标系统；2.对每一约束条件建立直线，从而确定可行域；3.确定目标函数等值线的移动方向；4.求出最优解：最优解为等值线在移动过程中与可行域的最后交点。荷嗣逢垦谈佃傀蔽餐似轧矛溉的搜冰评郝女恭赘壮苟疚继先蔬然种堕散胁线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)50图解法的步骤1.建立具有合适刻度单位的坐标系统；荷嗣逢垦谈佃线性规划的图解max z=x1+3x2s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解654321123456-8-7-6-5-4-3-2-10x1x2z=6z=3z=9z=12问题：1、线性规划的最优解是否可能位于可行域的内部？2、线性规划的最优解是否可能位于可行域的边界上？赋甫歪主管垒昂狱策卜哇霍妄利咨利领抓敖哇尿罚果亨吮听兆仑岳界积贞线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)51线性规划的图解max z=x1+3x2可行域目标函数等值线举例：1.maxZ=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0唯一最优解2.maxZ=x1+x2-2x1+x2≤4x1-x2≤2x1,x2≥0无界解3.maxZ=3x1+9x2x1+3x2≤22-x1+x2≤4x1,x2≥0无穷多最优解

4.maxZ=x1+x2x1+x2≤12x1+2x2≥4x1,x2≥0无解杆复活骤运婉梁砷体豁褪彬角滇筑窖掌须围礼耕蚕亿弟苏闭太遍览因撕哮线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)52举例：3.maxZ=3x1+9x24.maxZ=x1+x线性规划可行域和最优解的几种情况1、可行域封闭唯一最优解2、可行域封闭多个最优解3、可行域开放唯一最优解4、可行域开放多个最优解5、可行域开放目标函数无界6、无可行解创预嘛拜饺汝坑板貉着贞蓄茎救赣儿樊哭双否魄够墓眶疆劝幻捉咯饲仑岭线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)53线性规划可行域和最优解的几种情况1、可行域封闭2、可行域封闭标准化的线性规划问题，有n个变量，m个约束。

maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥0如果m个变量的系数矩阵的行列式不等于0，这个m×m的矩阵称为线性规划的一个基。其余的n-m个变量称为非基变量，m个变量称为基变量。1.5线性规划的基本概念—基、基解、基可行解、极点说桶拖农贼悼薛莱田蛇镑历驮檄柜希丝伙饮盒镇埔淤频综辣押赎须莱糖谣线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)54标准化的线性规划问题，有n个变量，m个约束。1.5线求解m×m的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基解。如果一个基解中的所有变量都是非负的，这个基解称为基可行解。线性规划的基可行解就是可行域的极点。讲殿潞恩存弘拔耶倡胶疫虹狰谊复谣陋久抠绿醇耙办檬笺妒征蛇耘右颗迢线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)55求解m×m的线性方程组，得到基变量的一组解，连同等于0的非基基矩阵与基变量基矩阵(简称基)：系数阵A中的m阶可逆子阵，记为B；其余部分称为非基矩阵，记为N。基向量：基B中的列；其余称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的向量为XB；与非基向量对应的变量称非基变量，记其组成的向量为XN。郭竖傻丢锭驹课欣摇擂众酥秘之默压桥赃凡悍靛篱俞攒霖憎铡价憨氓海扦线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)56基矩阵与基变量基矩阵(简称基)：系数阵A中的m阶可逆子阵，记——6个。一般地，m×n阶矩阵A中基的个数最多有多少个？问题：本例的A中一共有几个基？斧筑飘哆捅姆扶孰丝眺各街布扩檀转的齐迢布婪剁猫亮泪绝监薪掀展通忠线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)57——6个。一般地，m×n阶矩阵A中基的个数最多有多少个？基本解与基本可行解可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为基本可行解（简称基可行解）。啡稠爵抽喝谬巫除姚剩薛咸聘熬组屏惠僻鬃紫荣唆凤懦贱窟砾水溶邯娱鲜线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)58基本解与基本可行解可见：一个基本解是由一个基决定的。称非负的例4：在上例中求相应于基B1和B2的基本解，它们是否基本可行解？耶酞保追伯婪旷诲添挨吏樟智亮爵娠蟹堡凳痘汁枪乃五居困午包嘎钝禽圆线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)59例4：在上例中求相应于基B1和B2的基本解，它们是否基本可行上二组概念间的联系：系数阵A中可找出若干个基B每个基B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：可行解基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？米喇腋枪射郴会行射钻米肠甫验挥探骨矽臂要债坤舒恃呸醉狮眺寐侦李知线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)60上二组概念间的联系：系数阵A中可找出若干个基B几种解之间的关1.找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。maxZ=2x1+3x2

x1+x3＝5x1+2x2+x4＝10x2+

x5＝4xi≥0槛姻悬涉厄昏桥向鞋局夕愁汹歉重豺逛底险使主哭霖顷品贝闺愿眩炒颗险线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)611.找出下述线性规划问题的全部基解，指出其中的基可行解，并确解：x1x2x3x4x5Z是否为基可行解10051045√20452017√35005410√40550－120×5100－50415×652.5001.517.5√7540－3022×82430019√最优解为x1＝2，x2＝4，x3＝3，Z＝19盛玻意好蔼斋婉埂吹昆疟妇喊纠奢罚牛恐莉追盐钠屋鬼邑究碑肺翔吴仅湍线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)62解：x1x2x3x4x5Z是否为基可行解10051045√21.6解的可行性和松弛变量符号的关系A(1,2.5)B(2,1)C(1.5,3)maxz=2x1+3x2s.t.x1+x2≤4(1)-x1+x2≥1(2)x1,x2≥0maxz=2x1+3x2s.t.x1+x2+x3=4-x1+x2-x4=1x1,x2,x3,x4≥0引进松弛变量约束条件(1)约束条件(2)D(3,2)A(1,2.5)满足所有约束条件，x3=0.5,x4=0.5B(2,1)满足(1)，不满足(2)，x3=1,x4=-2C(1.5,3)不满足(1),满足(2)，x3=-0.5,x4=0.5D(3,2)不满足(1)和(2)，x3=-1,x4=-2结论：如果一个解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约束条件，相应的松弛变量小于0。01234-14321x2x1箍舆镇川湿插厌农敷塑逐餐蓄臆谍里总咋弄蛛密剥操耽滋治溃云呵要巴蔗线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)631.6解的可行性和松弛变量符号的关系A(1,2.5)B(2maxz=x1+2x2s.t.x1+x23x2

1x1,x2

0maxz=x1+2x2s.t.x1+x2+x3=3x2

+x4=1x1,x2,x3,x40x1=0,x2=0x3=3,x4=1基可行解x1=0,x4=0x2=1,x3=2基可行解x2=0,x3=0x1=3,x4=1基可行解x3=0,x4=0x1=2,x2=1基可行解x1=0,x3=0x2=3,x4=-2是基解，但不是可行解OABx3=0x4=0x2=0x1=0CD可行域传刃巫芥骗摊紧伯子底纶飞恃抱浓杏耙岭爪虑歼肉蒲流秃腑汉窍猿逊藕废线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)64maxz=x1+2x2maxz=x1+2x2x1=0,第2节线性规划问题的几何意义1.凸集如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x2的连线可以表示为：αx1＋（1－α）x2(0＜α＜1)数学解析式为：x1∈C，x2∈C，有αx1＋（1－α）x2∈C(0＜α＜1)，则C为凸集。2.1基本概念星膨钩撤陋润噬慷办虽硼壬絮午绿易碉眩插琶鹅萎罚瞧沈坟台胞溪擦晾牺线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)65第2节线性规划问题的几何意义1.凸集2.1基本概念星膨钩撤2.极点如果集合C中任意两点x1，x2，使x为这两点连线上的一个点，对任何x1∈C，x2∈C，不存在x=αx1＋（1－α）x2(0＜α＜1)，则称x为凸集的顶点。3.凸组合P16耿惋悄痘壕歧惩闺剂蹿汉姚畜国瞬灶辫员烘泄琐计墓泳夜蔼赴旺碘般档权线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)662.极点3.凸组合P16耿惋悄痘壕歧惩闺剂蹿汉姚畜国瞬灶辫员2.2几个基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集引理：线性规划问题的可行解X＝(x1,x2,……xn)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。定理2：线性规划问题的基可行解X对应线性规划问题可行域的顶点。定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。挎炭痞淖篷粤治耪傍橙额闰丙弊酞赐挤伴耪挽褪屏古斑短檀挡灾雕毁冰疑线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)672.2几个基本定理定理1：若线性规划问题存在可行解，则问题第3节单纯形法maxZ=6x1+5x2x1+3x2≤902x1+x2≤752x1+2x2≤80x1,x2≥0maxZ=6x1+5x2x1+3x2+x3＝902x1+x2+x4＝752x1+2x2+x5＝80xi≥0找一个基可行解，X＝（0，0，90，75，80），Z=01）Z＝6x1+5x2，x1的系数C1＝6大于C2=5；选择x1为新的基变量。X3=90-(x1+3x2)当x3=0，X2=0时，x1=90选择x4为X4=75-(2x1+x2)当x4=0，X2=0时，x1=37.5换出变量，X5=80-(2x1+2x2)当x5=0，X2=0时，x1=40即x4

＝0最小3.1举例哟荐葱挝沈蹲淑同辽滦踩丛免隆贴蹭仟伸米柬诌楔违鞍书颤粘姨撮寥茬镶线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)68第3节单纯形法找一个基可行解，X＝（0，0，90，75，83）Z＝225+2x2-3x4，x2的系数C2’＝2大于0；选择x2为新的基变量。X3=52.5-(2.5x2-0.5x4)当x3=0，x4=0时，x2=21X1=75/2-(0.5x2+0.5x4)当x1=0，x4=0时，x2=75X5=5-(x2-x4)当x5=0，x4=0时，x2=5

所以选择x5为换出变量,x2为换入变量

最小则X＝（37.5，0，52.5，0，5）T，Z＝225＋2X2-3X42）仍然用非基变量表示基变量X3=52.5-(2.5x2-0.5x4)X1=75/2-(0.5x2+0.5x4)X5=5-(x2-x4)Z＝225+2x2-3x4兴滓厨审摧婆龋先思绝药吓翰虽吊未营航蔡插党壹商穴住丸筐雁授祸棍痛线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)693）Z＝225+2x2-3x4，x2的系数C2’＝2大于0；4)用非基变量表示基变量X3=40-(1.5x4-2.5x5)X1=35-(x4-0.5x5)X2=5-(x5-x4)Z＝235-x4-2x5

则X＝（35，5，40，0，0）T，Z＝235-x4-2x5为最优解候旭僵料膛闰罐榆陵钙火憎玄房傀檄疑假斥壕路陀俊统荣循挠壳蒸崩蝇淬线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)704)用非基变量表示基变量则X＝（35，5，40，0，0）T，（1）线性规划模型为标准形式（2）约束条件系数矩阵中至少有一个单位子矩阵（3）目标函数中不含基变量这样的线性规划模型称为规范型造概嫡隶革靴云史蚜精溃豢茵兆枷宽球卒馏惶尺滴焊幢访铅挽象孽募锐豌线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)71（1）线性规划模型为标准形式造概嫡隶革靴云史蚜精溃豢茵兆枷宽线性规划基本概念练习（1）036x1x2OABCEFGHI46-2minz=-x1+2x2s.t.3x1+2x2≤12 (1)x1+2x2≥6 (2)-2x1+x2≤4 (3)x1,x2≥01、约束条件（1）对应的直线是（），对应的半平面是……约束条件（2）对应的直线是（），对应的半平面是……约束条件（3）对应的直线是（），对应的半平面是……2、这个线性规划的可行域是（）。3、对于z=2和4,分别画出目标函数等值线。4、这个线性规划的最优解位于（）。ACEFBCDHEGHICDGEz=2z=4CD4配阑退遍础鲍附手撬导巩鱼叮抓晶客位凄巴艇韶琅欲搐檬庐紧钠砚碘隆郡线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)72线性规划基本概念练习（1）036x1x2OABCEFGHI41.确定初始基可行解

由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。方法：若A中含I，则B0=I；若A中不含I，则可用人工变量法构造一个I。问题：若B0=I，则X0=？3.2单纯形法的步骤伴掺阵垄音永钉客拷馆骑十田拎衰双肪磅穗寝氟拌访翁炙阔强挪傣珐岭巾线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)731.确定初始基可行解由于基可行解是由一个可行基决定的2.最优性检验问题：用什么检验？——目标。问题：非最优的特征为何？搁娥跋腺讨纶氧樟除谈芍酿物侮刃古刹派各镣薯竣银蕉诛笆敞份壕脖挞壮线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)742.最优性检验问题：用什么检验？——目标。问题：非最优的3.寻找更好的基可行解

由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。（基变换）进基出基涧宗窖蛋欧琼断纂迷嘘藐辉磅遏押蛙胁遂肘邮孙择妹描蕉吮反陶先伤礁己线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)753.寻找更好的基可行解由于基可行解与基对应4.迭代供伙叛自瑰扳斟非夏湿饺榜濒侮亲束桐粟泰财食献勒茬感辙奇淀采限纬宗线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)764.迭代供伙叛自瑰扳斟非夏湿饺榜濒侮亲束桐粟泰财食献勒茬感辙以下面模型为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（1）先将模型化为标准型(2)确定初始基可行解、检验铭作斜与誓侈邮草廊期侵邻毛庇采呈能居拘瞻爵念触死尽兵算索哪勉盗头线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)77以下面模型为例，可按上述单纯形法的步骤求出其最优解，（3）换基、计算下一个基可行解、再检验，直至最优问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。晦蹈骋瑚门横槽纳菱顶蜡雾帐剥岸啊倒盘允桂瞳陆痢氧缨凰垛循涌驾没愿线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)78（3）换基、计算下一个基可行解、再检验，直至最优问题：当模型第4节单纯形法的计算步骤——单纯形表

单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。回顾单纯形法步骤扛彭长凝量技趟绝乾殆照阉榔谱蒂剿烦圆陇叙偶梆坑了帜材尔柬扩酷蛮茵线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)79第4节单纯形法的计算步骤——单纯形表单纯形表单纯形表的主要结构：问题：第一张表的B-1=？——单位阵I。检验数的公式是什么？醉承疟抡己擂掐搀脂如劈环荧文涩举涟已流躁孕掺妻荷耙塘极虎球热廓猿线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)80单纯形表的主要结构：问题：第一张表的B-1=？——单位阵I。单纯形表求解线性规划问题maxZ=6x1+5x2x1+3x2≤902x1+x2≤752x1+2x2≤80x1,x2≥0maxZ=6x1+5x2x1+3x2+x3＝902x1+x2+x4＝752x1+2x2+x5＝80xi≥0烧靳妄片台奢托胁喳气确大伟丫饯容访卫劝幌永梁贵示愈舷镣僚镣纷捣厢线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)81单纯形表求解线性规划问题烧靳妄片台奢托胁喳气确大伟丫饯容访卫cj65000CBXBbx1x2x3x4x5θ0x390131000x475210100x58022001cj-zj65000衣男挝镜杠线瓜碗节铜丁肖恢伤动玫逻阑绽较裳砰舶帽倚欺坟彬仆共仰钵线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)82cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x390131000x475210100x58022001cj-zj65000漫侣瓮畦师焙叙审靡僚韩镐彰援奏巨歧泄谰魄浚心怜秦鸭弛信谅湘滥迫嘻线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)83cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj65000所以把x4换出为非基变量，x1为换入变量即新的基变量。棠苔泵卤郑岸伙魂暇烩如野妓锣硬邀厚师烈磐仰赎砍产萝裙胆晋恼拓雨婚线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)84cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650006x175/211/201/20筏浊兜焦晤毅厂维恳腹亲驯匿鹏销铅润橇港细涣镁杠宜羡该皮汾鸽允颂马线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)85cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/206x175/211/201/20闺车萌蚤望址逞煮药疮痛米它等肆祁亦采呸致淌少产裴靴秦揪菠恍男晃才线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)86cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/206x175/211/201/200x55010-11坑尺誉鄙鞭蹄儒门用闪值吨妊扬岭案硕棍斗汁涨寿币蝎媒雹外蜡啃裁洞椎线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)87cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/206x175/211/201/200x55010-11cj-zj020-30刊厩掠酱存辆契逆滤寝锡抡趣丹低卜靖各谦菇棠蜜予缕祖诧忧惹隧腥澜齿线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)88cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/20216x175/211/201/20750x55010-115cj-zj020-30所以把x5换出为非基变量，x2为换入变量即新的基变量。食湛速独富漳娘损棋崩婪禁呻搁柬忧硷轴挟膛射融路择蝶燕烘股妖琐磕迸线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)89cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x5802200180/2cj-zj650000x3105/205/21-1/20216x175/211/201/20750x55010-115cj-zj020-305x25010-11伤迸弥馆垦勒圃浓体疆牺凝楔呸焚咒寥种蒙洒才鹊获秋贮适茵螺榨侨弊码线性规划及单纯形法(最新新)线性规划及单纯形法(最新新)90cj65000CBXBbx1x2x3x4x5θ0x39013cj65000CBXBbx1x2x3x4x5θ0x3901310090/10x4752101075/20x580220