MBA运筹学实用培训讲义

MBA运筹学讲义运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。例如，在线性规划中体现为两方面：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。第一部分线性规划内容框架庭LP黄问题节基本纤概念无 细 蔬数学新模型申 间 农可行删解、暗最优挣解巾实际孔问题蹈 议 啊 谜LP本问题饭 炎 瓜 绪 垄 抱解的约概念熊 陶 听基本僻解、命基可垦行解院提织袖纷出泊 惩 抬 逝 务 匀 艘 向 朝 似 忠 析 诱基本箱最优恒解拒 榜 零 棋 教 危 购 年基本戴方法胜 腰 颂 温 根 洒 阵 躺 拾 窝 快图解拦法危 鼓 灭 驼 能 漂 拾 容 南 轧 度 宵 初 咐原始长单纯仰形法上 加 艇 父 宪 手 贵 艇 沈 厌 乘单纯流形法违 陪 割 盏 吵 矩姨大楚M裂法石 薯 喊 固 卖 像 久 向 虎 锡 昼 歪 掌 身人工云变量跪法境 舟 粒 针 服 存 滥 毅 窜 行 翠对偶障单纯万形法另 掏 如 顿 但两阶育段法云 膊 裂 盘 羞 爪 拆 蝴 卫 惑 桶 完对偶愧理论明 刃 雅 拐 摘 却 棕 尘进一艘步讨叙论罗 旱 耻 哄 堂 森 有 稠 农 晕 浆 健灵敏屯度分茶析聚──唱参数初规划缘*就 犬 哭 鞭 旗 威 傅 丽在经朱济管羊理领鸣域内仇应用商 兴 禾 元 广 输 反 劲 矩 疏运输腐问题惩（转托运问粥题）桶 负 涌 惜 踪特殊屑的兼LP驴问题项 妄 例整数划规划激 搞 缓 驴 维 欧 搅 钱 习 长多目哀标荒LP解问题巴*华第一例部分躲迁线性所规划快（除Li窑ne丘ar桑P侮ro膝gr甩am枪mi尤ng香）及阵其应肠用骂第一丈章融贤LP破问题怪的数驶学模屿型与颈求解面星依§苦1桂L范P办问题迫及其狐数学怜模型芽象钟（一绸）引岭例贡1绒（生馆产计帅划的拐问题偷）砌螺请某垃工厂督在计疤划期落内要跨安排助生产静Ⅰ螺、腐Ⅱ晶的两我种产系品，罚已知辱生产苍单位防产品睬所需衬的设掩备台窗时，浩A弦、捧B下两种靠原材懂料的详消耗历以及层每件必产品费可获称的利直润如户下表划所示罢。问搞应如昼何安啄排计付划使回该工周厂获相利最倾多？摘Ⅰ熄Ⅱ蔬资源施限量附设备幸1隆2映8踢(粥台时贿)辰原材贯料炼A暖4沫0波16限(k半g)芽原材焰料爬B咏0凤4际12速(k苏g)渔单位赵产品胶利润锹（元陈）盏2逆3起该问退题可的用一涌句话绣来描沉述，油即在纱有限章资源瓦的条漂件下壳，求超使利迹润最雨大的杯生产模计划草方案产。鹊解：互设胆x毅1困,x解2闲分别建表示医在计抓划期塌内生糟产产鸟品毯Ⅰ咬、衣Ⅱ乎的产庆量。刑由于纺资源名的限谎制，固所以认有：汉机器疑设备瓜的限期制条秋件：想x闪1样+2渡x鸭2吧≤滥8局原材哪料侧A秀的限勾制条字件：南深4x瘦1朽≤着16速 弦 血（称贡为资唤源约冻束条孤件）俯原材帅料食B枣的限庭制条予件：卵煎4x招2退≤恩12磁同时突，产史品预Ⅰ球、早Ⅱ程的产加量不蝇能是数负数拘，所现以有释x桶1突≥土0炸，葛x命2拜≥冒0勺 钥 屡 派 拳（称虫为变待量的摩非负猎约束灾）辉显然毫，在良满足捕上述称约束海条件国下的榨变量各取值泻，均舱能构伯成可辨行方达案，贞且有冶许许枝多多室。而河工厂缓的目妨标是厌在不杏超过颠所有梳资源版限量盈的条劲件下舟，如少何确脂定产以量扮x锅1梅，奶x坚2占以得洒到最缘大的特利润筐，即式使目狭标函歌数霞Z=状2x撕1共+3拘x藏2梢 帖 淹 寄的值驾达到秀最大观。幕综上抛所述奏，该踩生产蛮计划绑安排燕问题嘱可用剪以下糠数学拴模型绪表示逃：丧ma俗xz继=2芒x隐1慎+3槽x员2拼引例酸2.夏雁（营篮养配逐餐问汁题）甘假定堂一个锁成年晚人每利天需避要从灾食物脸中获它取旋30码00层卡路匠里热械量，昆55愧克蛋剧白质四和谜80释0创毫克油钙。差如果升市场回上只妈有四轻种食杀品可炊供选益择，惹它们返每千霸克所泰含热电量和淹营养加成份稠以及洞市场警价格层如下佩表所李示。绳问如枝何选蛮择才徒能满违足营顿养的泥前提忙下使在购买捧食品而的费浪用最岂小？葛序号弊食品赚名称舞热量文(劲卡路拐里融)在蛋白索质征(套克护)孩钙目(m犹g)机价格坛(捧元食)稠1接猪肉省10捡00偷50元40第0故10捷2坝鸡蛋猜80蚀0稼60柿20障0鞋6哪3过大米头90写0招20大30辟0提3陵4部白菜巨20标0块10圾50使0绳2聋解艰:股设肥x岛j扰(j挣=1否,2胃,3级,4然)励为第社j预种食隶品每清天的姑购买山量，宣则配味餐问性题数匠学模仪型为枕mi艇nz杏=1拴0x撒1咳6x歇2通3x宣3升2x蜻4樱鼻道（二协）馆LP枣问题据的模目型殖上述扫两例钞所提定出的玉问题村，可胃归结何为在院变量英满足露线性表约束怎条件奏下，宴求使描线性环目标洒函数科值最鹅大或混最小傅的问阀题。应它们俗具有公共同躬的特铜征。复（次1旋）每惹个问笋题都固可用凳一组园决策鼓变量禾(x怖1印,x登2不,净…辉x史n擦)鱼表示束某一菊方案凭，其侮具体西的值宝就代瑞表一别个具衫体方悟案。食通常辅可根鞋据决夺策变望量所丑代表肉的事佣物特恰点，歇可对北变量敏的取帮值加树以约括束，叮如非梨负约数束。缩（蔬2君）存父在一浓组线啦性等善式或碧不等岸式的闲约束事条件疤。僵（各3躬）都礼有一新个用杂决策罪变量坦的线饱性函疾数作更为决酱策目映标（性即目消标函积数）洲，按仁问题愈的不牙同，密要求点目标药函数遥实现培最大咱化或淹最小叫化。脏满足砌以上陕三个邻条件者的数彩学模弱型称歪为信LP提的数光学模厘型，喊其一赌般形拜式为萄：胖ma坟x(广或誓mi辞n)点z=布c时1叨x室1劝+c叙2辛x希2耽+索…捎+c驰n舱x盈n宽 鹅 旅 杠 宗 秀 惜(1淡.1局)(1.3)盟 鸣 烈 宫 宗 酱(1圾.2规)(1.3)要或紧诱缩形榨式丛 盟 膊 绞ma庭x(殿或死mi翻n)强z=盾 例 应 陵 巴 冠 嗽 凯 绿(1什.4柱)迟或矩届阵形孝式蝴 岭 饱 扮ma攀x(匹或裂mi馆n)终z=矿cx嚼 种 炼 呼 言 风 耳 轨 懒 拖 横 会 宁 斥(1梅.5晃)顾或向据量形派式：滤 搂 逼 哄ma晴x(萄或居mi呈n)斤z=语cx呜 诉 目 姿 凤 其 须 震 草 花 绿 链 难(1巧.跳6罪)伙其中梦C=纷(c闸1角,c典2蔽,奥…跌,c烂n栏)互，称社为价观值系厉数向正量；余称为款技术姻系数晓矩阵缴（并吩称消体耗系由数矩诱阵）闸脸=(政p场1华,p阀2秒,近…问,p晋n神)该称资碗源限界制向株量毒 度 残X=希(x分1循,x型2律,似…稍,x竞n丹)霉T沫称为腥决策摊变量坐向量垄。幸（三测）顷LP蛾问题贱的标尤准型伶1.各为了归讨论事LP叼问题繁解的鸟概念供和解漫的性段质以驴及对鸣LP请问题添解法符方便慎，必愧须把抄LP古问题莲的一启般形档式化墨为统吊一的孙标准忽型：maxz=cx进 俭 洁 痕ma蠢xz宫=命；挪 同 锦maxz=cx孔仪锄或糠 笛 北 塌 船 费 光 懒 护ma经xz核=c奖x棉 甘 搬 妨 构 绍 赠 漏或倍标准织型的泼特点顶：伪①坏目标激函数谨是最识大化渣类型急②搬约束置条件炉均由剑等式肉组成息③端决策昂变量楚均为娃非负访④讽b尿i元(i蚊=1狗,2减,节…历,n津)朱2.汉化一商般形妨式为旋标准虏型扶①赚mi勒nz狡ma捞x(还-z培)=胁-c筑x械②“政”躲左边岩+受松驰棍变量价；百“顺”括左边棍－需“扛松驰以变量格”锄③施变量曲x述j支0订-x梳j剧0哄变量粘x咐j惕无限师制处令超x蛙j劈=x叉j排－锣xj雅④偏b醋i吐<0唉等式携两边悼同乘沿以爬(-滩1)宫。签3.明模型鞭隐含撞的假锹设哲①预比例迅性假气定：全决策匹变量葱变化凯的改储变量洗与引息起目抽标函叶数的井改变俱量成活比例众；决枕策变捧量变叛化的筝改变栽量与友引起宅约束震方程伙左端缩值的抗改变造量成际比例膨。此网假定桨意味制着每攻种经反营活蛋动对讨目标毒函数猴的贡慰献是爪一个骄常数刮，对遭资源钞的消赴耗也扫是一偿个常适数。块②歉可加处性假吓定：挑每个芳决策鞭变量或对目够标函测数和床约束衣方程保的影锡响是桂独立往于其慨它变奉量的怠。挠③足连续哪性假挑定：炸决策武变量汽应取尽连续承值。爬④吼确定劈性假闪定：甘所有稠的参林数夸(a蛮ij寻,b新i惑,c喘j窜)扣均为消确定根，所靠以窜LP坏问题兵是确攀定型虏问题蹲，不慕含随耀机因蔽素。娘以上竖4惑个假木定均撤由于刻线性寄函数鲜所致荷。在闪现实血生活羡中，寿完全件满足合这疫4捡个假末定的飞例子钥并不木多见洪，因批此在霞使用秘LP饥时必云须注等意问鼻题在匹什么写程度民上满涨足这呜些假浆定。总若不炭满足旺的程阿度较盐大时到，应夹考虑陈使用村其它燕模型嚼和方蹈法。痕如非倾线性弃规划彻，整心数规桨划或处不确辣定型纲分析魔方法龟。叉对戴LP采标准毁型，患我们链还假旺定束r(横A)阁=m赴<n推。艘（四葡）来LP险问题献的解奴的概搁念爪设冒LP咐问题似 或 召 重ma今xz枣=摇 淋 如 配 网 舰 以 嚼 革(1大.趟7蛮)腥 堡 锅 由 衣 拼(1抽.荐8帖)棕 趣 热 秘 疲 好 司 舒(1吨.略9疏)饮棍赏1.痕从代叫数的渔角度昌看：迈可行乳解和去最优佣解竞河巷满足忧约束劲条件换(1冲.劣8扎)剩和求(1暮.冲9加)天的解锋X=桂(x硬1东,x凶2腰,锅…夜,x海n校)败T值称为短可行姥解。会所有遭可行组解构雀成可流行解皱集，欣即可卖行域拴。而葛使目企标函衣数达竞到最裳大值搭的可径行解盒称为云最优躁解，遗对应封的目场标函丑数值筋称为揪最优榜值。昆求解洽LP蒸问题糠就是瓜求其百最优寇解和边最优委值，脚但从夹代数害的角彼度去燥求是稠困难蝴的。礼2.阵从厨LP蚁角度疫看：筝基：切设江A辛为植mx执n丹矩阵蔑，始r(拢A)响=m仅，狐B墙是垮A胆中的散mx哀m痒阶非比奇异蝇子矩徐阵（烤即菜|B衡|脆0自），赢则称买B社是心LP化问题逢的一泥个基尖。瓣若却B吩是山LP孤问题五的一眼个基技，则避B娱由绸m界个线辆性独惨立的狂列向铅量组睁成，东即仓B=兔(P烟r1份,P姐r2领,数…柳,P状rm叠)挺，其豆中赠P槐rj敬=(堤a故1r桂j贩,a修2r肠j惩,析…脚,a陈mr论j默)叮T催，谷(j稻=1巴,2戴,辣…聚,m夜)陷称为革基向短理。笔与其须向量梯P粥rj化相对漫应的沟变量碎x着rj绑称为栗基变马量，村其它祥变量基称为久非基箭变量惑。显拘然，乘对应丽于每枣个基郑总有迁m巩个基蕉变量金，阁n裕－哭m构个非昂基变显量。社基本庙解与着基可缓行解贪俩设悟B横是武LP慌问题穷的一慕个基秋，令扯其苏n钉－婶m而个非窝基变墙量均饶为零究，所犹得方绪程的抛解称翻为该影LP纠问题嚷的一握个基渐本解行。显羽然，畏基躲B瓦与基吧本解欢是一杠一对别应的迟，基务本解改的个扒数堂≤纷C敢m赏n尽。在煮基本撕解中占，称尘满足琴非负听条件灯的基始本解臂为基勾可行笑解，情对应嘱的基丹称为笋可行福基。激退化娱解喉嚼挺如果匆基解泥中非鱼零分核量的亿个数最小于蜜m仪，则绵称此慌基本帅解为握退化肌的，英否则默是非骆退化搂的。河最优泛基叨坐败如果妖对应仍于基齿B腊的基馅可行依解是网LP蚂问题逗的最喉优解感，则斩称粗B耀为跪LP开问题季的最缺优基柱，相柱应的分解又栏称基嫌本最愚优解沃。崭3.孟LP兰问题迎解之雅间的倍关系烈如图兽所示先 征 倘 脸 基本解可行解仇 屡 么 遭 愿 停 基本解可行解基可行解基可行解厚（五吧）两君个变烟量L亮P问鼓题的评图解扁法鞋侨闲1.疗LP躺问题者解的例几何军表示捷。以先引例概为例施说明①②③④恐ma籍xz测=2寇x跟1迫+3绸①②③④灾按以扫下顺组序进兰行：拥解：凳（声1除）画镰出直室角坐却标系疯；台款篮榨棒（潮2粮）依脊次做衰每条唐约束随线，焰标出上可行姑域的父方向怠，并骄找出莫它们程共同恨的膛仰蒙粘们咏陷可行尾域；AQ1Q2x2③②党啄贴桃社（校3垄）任俊取一名目标研函数键值作桶一条御目标卸函数巷线（感称等天值线就），柿根据捡目标轧函数婶（最私大或息最小浪）类缸型，暂平移奇该直混线即覆将离它开可晚行域押上，傅则与闯目标低函数泻线接勾触的枕最终斗点即沸表示抬AQ1Q2x2③②3B3BQ4Q4Q3220101x1①x1①0123401234图1牌闹酷其中嘴，将任目标既函数死Z=术2x设1级+3魔x呈2堡改写旁为脾，因射此，壤它可营以表程示为客：以匹z狱为参顿数，渡以针为斜丙率的蛇一族恰平行级线。呜位于尾同一已条直貌线上驱的点久具有丑相同烫的值主。宇解的绍几种熄情况梨：怎（知1求）此日例有宁唯一福解粮Q谱2娇，即棍x燥1独=4听,x半2窑=2厕,z适=1载4荐行辞（雾2利）有涂无穷尽多最将优解泡（多址重解钢），蹦若将梨目标遥函数虽改为再z=陕2x很1迫+4钱x责2梦则线迅段榨Q疗2撇，优Q券3存上的尺点均印为最女优解控。典狠瓜（宜3吩）无志界解x2x20x10x1慰求论ma顾x嫩无界杯但求来mi代n喷有唯烈一解散胃谋（誉4继）无育可行迹解x2x2xx100巡可行倚域与烦最优锡解间炮的关械系：聚 泼 稻可行昌域他 呆 区 止 泻 流最优很解醒 泼 辨 讲空搬夺集蓬 言 坦 视 廉 夫无最施优解初（无浓可行援解）屡 趁 绕 绕有界洲集仗 盗 粗 榆 坏 舅唯一架最优挤解衰 剧 告 决 赤 压 斑 穗 怠 雕多重吊解屯 风 妇 石无界蜓集拳 龟 债 方 均 蛙无有刮限最垄优解刺（无取界解砖）辞结论论：（紫1迅）嫂LP陕问题碰的可挨行域锡是凸权集（显凸多涝边形茅，凸研多面藏体，巡…喂）；运含蹄宝包犁（硬2哪）庆LP皇问题都最优岂解若逃存在事，则竟必可售在可昏行域放的顶活点上惜得到吼；狼奖带舒榜荣（蚁3肃）约LP赏问题豪的可雅行域耐的顶坏点个摇数是程有限迟的；踏纵显丘乡卸（下4皆）若阶LP松问题容有两伶个最公优解甩，则猜其连改线上说的点铸都是膊最优锹解。池因此绣，求漂解横LP陷问题蝇可转堡化为葱如何梁在可崇行域旦的顶乎点上常求出颂使目源标函信数值就达到吉最优吵的点贱的问波题。宾剖相2.叮基可摸行解救的几绳何意株义期应急对例兽1组L赵P荷问题赔标准搜化为送 捆 拴 贺ma钞xZ指=2惰x贸1鉴+3吴x剃2爱可求贵得所桃有的滩基本择解：碎x庄(1捞)尼=(役0,抽0,下8,网16恰,1播2)弯T挽(0膏点亭),无x呼(2鲁)辈=(飞4,亮0,驼4,四0,谣12残)橡T材(Q仰1恩点偏)眠x捕(3丘)炮=(古4,幸2,夜0,估0,私4)年T歌(Q离2屈点玉),季x授(4掩)让=(选2,抱3,势0,窗8,台0)愁T京(Q涌3爹点直)尾x熔(5铃)需=(学0,讽3,航2,粮16寨,0棋)摆T彻(Q沿4兄点铃),讽x决(6里)漏=(底4,呼3,遥-2饥,0坟,0被)煤T窝(C熟点裤)烦x或(7撑)悔=(厨8,李0,身0,宵-1呈6,厨12击)东T静(A膨点助),刊x旬(8肝)砌=(尸0,违4,递0,昂16骂,-时4)误T晶(B概点速)锋但浓A尚、达B拒、滑C崖三点宏是非桐可行写域上摄的点妥，即脚非可士行解刃。因活此，桐x颈(1绝)晃，管x巴(2岁)窃，属x剑(3走)采，焰x趁(4狠)兔，呜x防(5绍)吩才是崇基可滴行解梯，它劣们与浊可行援域的配顶点仿相对敌应。淡于是响还有盼结论驶：（杠5庄）对味于标歉准型获的裹LP属问题洁，亡X去是基溜可行赞解的绍充要踏条件孕是腹X迎为可裤行域广的顶研点。乎棵制惧（匪6劝）话萄峡偶哥耐吹租宅跃良彼屑觉并≤浅C恢m懒n为灶都3.啄图解雾法只阻适用车于两糠个变佩量（妨最多冲含三棒个变系量）针的敬LP拼问题六。草献码4.彼求解冷LP闸问题蜂方法设的思堆考：怪①怠完全星枚举歇法，努对亡m箩、也n耳较大解时，丛C再m纹n谎是一笑个很假大的概数，众几乎蛋不可宰能；衫②丝从可鲁行域备的一奏个顶扑点（搁基可萍行解福）迭旨代到扒另一饶个顶惹点（属基可擦行解笑）。魄忽品§热2勇屋单纯怜形法谷与计狡算机灰求解摘绣渡1.拼解惠LP谨问题浅单纯丛形法感的基余本思袜路：轮求出白一个旅初始挂基可活行解农 痒 相 不 易 倘 缓 挡 浴 肯 饰y停紧判别闷此基唤可行财解是荐否停扔最再等却航优烧归巾助解赖 劣 麦 罗 爷 轿 锋N衡求出喉使目让标函捐数值的得到北改善喊的基锄可行排解华垂党2.升单纯障形法券的计格算步肤骤（凯表格泊形式丑）那瘦荡（孝1漫）建盛立初薪始单秧纯形任表，淹假定须B=城I，赢b撕≥烧0确锐赖糠丰设剩ma济xZ帐=c款1巾x退1岔+c葬2恶x部2救+仇…蜘+c龟n柳x显n帜将目小标函面数改拦写为娱：趋-Z挥+c魄1狐x草1撇+c宅2扛x自2肌+殊…观+c降n付x垂n买=0病把上叶述方涌程组房和目是标函汇数方割程构顺成妄n+仪1肝个变泄量，场m+速1芳个方歌程的遥方程春组，鸣并写夜成增竟广矩踢阵的创形式坏：悟-Z擦 拦x拥1黎 羽x岛2庸 杏…锄 勒x有m孙 鞭x承m+喘1育 诸…态 币 失x垃n侧 怒 势0忙 耗1埋 隙0转 贝…井 决0拔 们1m姥+1趟 派…咏 贱1n庄 校 昌1刘0合 柄0馆 被1周 克…责 动0标 尖2m章+1督 切…锋 氏2n韵 床 燃2歪0爬 寸0士 页0府 胸…妹 朋1阳 棕mm胞+1答 它…毒 虹mn坐 升m陵-1邮 即c李1殖 窝c俊2户 吗…肺 炎c兔m债 乖c狼m+槽1土 薯…处 赌 景c矩n茫 秆 浑0诵以非欲基变跌量表酸示基岔变量泛形式肺代入芳Z决中的盘基变然量笨,软有而 述 娱临童 朱 勇税令却水插于是节因此陆，上屑述的津增广俘矩阵撕就可藏写成凡：尽Z铜 鸭x球1耻 谦x乎2剪 肃…浮 追x阔m根 晃x宽m+峰1尝 妻…叮 呀 衔x舒n困 角 禾 某 堡 驰 冈0展 典1贫 叔0候 泰…屈 深0嫁 滑1m燥+1毁 打…核 丰1n馅 疫 够 笋 桌 惭 签 闲1嫌0组 超0毒 时1素 雹…毕 跪0携 惭2m苗+1呼 项…途 染2n屑 泡 督 颠 辽 拨 锤 女2宝0误 店0岭 肯0饱 庄…岁 隆1泊 闸mm廊+1莲 犁…扯 锹mn剩 岩 辩 边 丢 犯 污m饼1筝 旨0萄 启0笛 暗…舞 建0巷 听…监－驾c紫n饼 运淋 唱 陪再令蚂则上捷述增疼广矩狱阵可扒写成房下面爪表格未形式宗：即民初始减单纯趴形表吉T爷（借B曲）镰C佣j尽C惯1白……纲C克m跪c日m+鸭1牧……位c阀n追i够C惩B嚼x案B抓x劳1也……云x黄m席x妹m+宇1深……陈x瓜n注C袜1消x宫1冲1牧1宋……雨0篇a半1m故+1幸……暮a遮1n烂C指2俘x少2术2武0石……沃0期a屯2m队+1搂……矛a教2n达：万：奇：桌：舅趋统：袭：金……巴…嘱：炸C任m猎x鸣m电m蔽0赶……帜1母a足mm肚+1绞……援a希mn毕Z齿Z绝0置0孟……盒0杠m+弯1纵……纠n绸j起检验鼻数行矮上述响初始磨单纯闷形表苦可确矛定初棉始可厌行基补和初肉始基丽可行沫解：疤B=王(P标1愈,P两2讽,沙…碧,P受m港)=娃I,凯依x=炎(b界1希,b逗2律,践…闹,b罩m说,庆0雪……键0)绍T矿从初闭始单澡纯形芬表建听立的贷过程愤可以寒看到俗以下呢事实爸：守棵浑（方1姑）凡熔LP雨模型熄中约赛束条拿件为脂“≤妻”贴型，石在化伶为标纱准型仓后必况有楼B=逐I抚，如闭果享b冲≥芬0喜，则惊模型诸中约君束方长程的修各数太据不传改变旷符号镰照抄收在表萌中相异应的古位置滥。目顺标函统数非该基变逮量的腹系数陪则以懂相反傅数填赠入检矮验数否行各脑相应疮位置歼。鹅婚磁（熄2命）在因单纯辈形表水中，谨凡基肾变量否所在呢的列移向量挤必是奸单位击列向纷量，格其相防应的有检验选数均田为零外。顶呢处（鉴3净）吐更好使表现狮一般奶规律翻的在牺矩阵疲形式名的单雨纯形筛表中席设溪Ma型xX株=C雀X彻 蔽 滥Ma汽xZ千=C蕉X+斜0X缓L犹述岔其标隙准型迁为群仪将系羞数矩弃阵仍(A舌,I五)休分划屋为绸(B贫,N伟,I殃)音，其螺中础B才为可回行基杰，对汉应于挤基变睁量向浪量缺X帖B碑,N易对应蓄于顺X贿N糠，丽I斤对应厕于相X饺L愉,(颂X参N屠,X稿L俗)惜为非锯基变库量向励量。搅于是斜(X绸,L哪)邻T啦=(摘X稠B葬,X庙N贼,X哪L璃)盼T摧,(瞧C,悟0)灵=(粉C朗B京,C步N旷,0惕)轧。因狂此，摊矩阵吧形式辫的扭LP包模型低改写乎为：难窜驻滴谅用非照基变嫌量向图量表滩示基瞧变量容向量符，有德甲脾欢渴丧X认B芽=B魂-1鼠b跟－旗B前-男1舰NX库N衫－搞B方-1介X花L绍窄身代入广目标款函数艳中有最 史 仰Z甘=C兼B圆(B拜-1鲁b震－架B才－耗1郊NX涨N绿－章B众-1头X很L洋)+笼C这N绒X乔N央+0唉X卧L慌 驳 柄维=C于B蚕B刷-1办b殃－读C更B眉B萌-1夺NX钱N拔－落C挡B部B判-1谦X逮L套)+片C疗N容X眼N炕 泽 为遗=C职B妻B励-1壳b扣－谎(C例B酿B辩-1热N－刊C却N暖)X凡N贱－昨C翻B己B踩-1康X缩L将元检裕写成逼对应妹于基掠B既的矩滥阵形酷式的冶单纯株形表亭T宾（夹B侍）：培C购C贡B尝C贴N蛛C涉L随X璃B桃X铲N窑X哭L吓X欢B斑1庸B捐-1才N垫B外-1爱Z鬼C皱B求B呀-1势b桂0票C辞B晓B狡-1喉N权－门C编N倾C白B沙B溜-1孝例如恼将例嗓1税丹化成此标准贴型后失如下朵表拌T傅（地B吉）：形C挤j爸2编3搭0扣0展0难i神C薄B涌X贸B眨x农1巴x拔2动x腾3惰x吼4折x岁5以0桐x渠3森8白1朱2坦1拼0想0第0矛x咱4涝16励4园0冒0蚂1加0箱0造x然5陆12信0尝4氧0气0冶1猾-Z锁0日-棒2皆-财3芦0吊0疾0避σ役j夜初始帮可行械基甘B=腊(P刃3双,P评4思,P略5坏)=睬I,皮X茶=(诊0,敌0,扁8,描16吐,1吗2)躺T运现坚（脱2懒）判耕别最却优解芹老弦1赏萄在值T(罢B)岗中，口若所鱼有的拜检验筋数至σ雷j谜≥博0拣(j购=1邀,2森,拌…拖,n锦)驾 祝 赏则载B四为最社优基陈，相醋应的份基可格行解旋为最禽优解半，停灯止计淋算。耻毁色2悬批在御T(单B)疮中，滋若有模σ烈k并<0荷(突1歇k虑n)框，且瓜x颈k棚的系闻数列垦向量尼P欣k纸0孝，则万该问趟题无蜂界，魄停止题计算位。否究则转镜入（召3馅）疮集传（妨3筋）换角基迭墓代（压基变牌换）客忠白1毛谈先确必定入夜基变盐量塘X焰k僻:袭k毯=m改in搂{j谜|遍j棵<0卵}鸽做宋2趁御按最溪小比海值原悬则确慰定出声基变观量圆x万L米：急留积3撑斜以杨为主宅元，元进行建初等巾行变匹换（厕又称剪旋转急变换凡）即饥将列淘向量申变换龙为单智位列璃向量劝：棚返回值（恶2调）。崭换基胳迭代判的关篇键在那于将鹊换入榆变量适对应负的列挺向量秩用初久等行德变换蓄方法阴变换茅成单疏位列轨向量觉。其孙中主置元缠变成烘1功。即汉第奔L斤个分核量鲁如果四在最任终表腥中有帽非基扁变量饿的检闪验数荒为验0初，则柄该问芬题有旱多重说最优仔解。年良阳3.飞单纯椅形法番的进届一步盘讨论铸──井用人柱工变众量法直求初银始基岔可行其解逢踩惠（一谋）人少工变孙量法止若对律LP帮模型迷标准留化后端，不及具有苦B=表I斧时，链如何阵办？喘此时阿可采订用人拣工变鹊量法丙得到臂初始端基可犁行解胜。艺所谓匠人工乱变量损法是谷在原台问题础不含塌有初民始可基行基太B=昌I竹的情占况下杯，人馆为的硬对约绘束条宋件增起加虚粮拟的跨非负雨变量埋（即怎人工隶变量臣），迎构造萌出含徐有弱B=均I绕的另羞一个抗LP健问题易后求随解。汽当增捕加的垄人工仇变量灶全部蛋取值建为振0罗时，仗才与坑原问纯题等荡价。聚这样溉，新蔬问题帜将有围一个屠初始秧基可苗行解姻（以掏人工漂变量粮为基夜变量拼），某可用算单纯迹形法舟进行盈迭代仁。经旱迭代映后，芝若人亲工变但量全考部被冬换成州非基释变量篮，则筋原问拒题的核约束乡条件刑被恢课复，贴同时仿也得朋到一刘个基废可行魔解。骑在最梯终表碰中若局不能泄全部塘被换钱出，备则说画明原福问题绍无可韵行解显。归因此寨，该墨法的趟关键倾在于阔将人盯工变倚量全昏部换悠出。沙人工途变量懂法常彩见的亩有大期M曲法和泡两阶宗段法缎。冰瑞麦（规1榜）大舌M义法（堆通过溉下例急简略避介绍许其方买法与拜步骤光）母服召例，镇用大押M陶法求决解愧Mi筝nZ距=x虚1删+1亦.5况x走2啊解：轿Mi懂nZ怠=x进1浊+1份.5棕x撕2伴+0葵.x青3兵+0陕.x江4严+M锣x登5脂+M罢x宫6攀其中撤x额3典,x探4纺为松积驰变争量，碰x权5程,x唯6门为人舞工变迎量，五M慈为任怨意大勺的正河数。佣注意霉到：搬①槽分别台在约轿束条夸件增杨加人坑工变旋量早x未5拳,x对6始是为危了构扬成英“畜人工劝基男”溜爪茶必土②齐对于旗Mi芦n暂的目遣标函俯数采第用架(+抄M)蜓，而返对于秃Ma单x猪的目堵标函至数则饺采用渡(-毫M)攀作为皮人工油变量盐的系敏数界,赛是强粉加于狐人工被变量拳的一牧种惩智罚强,填其目援的是产为了购强制奇人工昌变量晃由变井量转速为非编基变属量，编使之旬恢复揭原问庙题，酒或与盾原问误题等泽价。线盏突翅带③币对于俘mi把nZ粪判别亲最优碗性准太则应冒是赴C卵j厌－梢Z善j惭≤伯0溉。辩诞陈积辈④这大简M民法适严合于衰手算钥，不控适用玉于计五算机陪求解民。搁（迷2而）两绘阶段捐法他第一妇阶段咳：不脚考虑野原问删题是擦否存友在基涌可行什解；沿给原历LP跟问题书的约申束条弊件加折入人猎工变索量，此构造罗仅含找人工疾变量畜的目乞标函搭数并船要求核实现彩最小削化（胃即使碧原迹LP眉问题灰目标贯函数大是求稻最大畅化）寄的辅勒助问电题：险Mi锈nW秀=x渣n+耻1师+环…委+x垂n+结m粒然后课用单技纯形聪法求握解（暮1持）。革若抬W免0梁，则锁原问杜题无锤可行择解，遣停止雹计算跟。若筹W=刃0强，且育所有避的人且工变训量均珍为非纵基变犯量，网则去酷掉人昨工变节量后链可得男到原卖问题轧的基宝可行攻解；搅如果赌人工吉变量封中含任有为辛0办的基巷变量晕时（梯即退策化解珍），皇则可拜再进陪行初龙等行旺变换史将其添换出爹，从向而获诵得原悠问题结的基傻可行拜解。着第二悦阶段现：在碗第一优阶段窄所得夜的基悄可行常解的配基础纤上，拆将最霸终表已中的咸人工深变量津列删妻去，煎同时遭将人闪工目套标函绪数行词换入糖原问雨题的向目标肺函数笼作为闷第二框阶段之计算唉的初妥始表写。段仍以租上例殊为例沃用两想阶段序法求惧解。们Mi冷nZ弊=x陶1哨+1遣.5躁x松2塘+0捞x餐3越+0砌x正4尺原问获题：镰 剩 冶 含 市Mi澡nW加=x羊5追+x燥6而辅助骡问题队：止 脊 虎 搏 破书中盗第1康9页薪表2莫.9脚和表麻2此.1青0惑的说猜明：穿（谣1咐）第擦一阶寸段的殃初始鞭表中海非基这变量耕的检叙验数姻=广人工启变量勾所在魔行的骂非基烦变量爬相应店系数寻之和贺，目棍标函净值值者=粥人工井变量克所在娇行相染应常鞋数之艘和。属（摔2储）第况二阶拆段单盼纯形狂表中渗目标盆函数示系数铃应将面非基门变量慢表示毛基变板量后裕所得姨结果还填入溜，或我先直肺接填柿入原莲系数馒，再替通过糕初等疾行变督换使级基变得量的根检验酿数为拿0悠。诚刺猴（虹3谜）若搬ma弄xZ践，则葛可转想化为偏mi边nZ跌1渐(Z沫1康=-海Z)秧董娃（二放）退腿化果单纯覆形法市计算另中用降规则这决定仁换出正变量呼时，诞有时肺出现福两个再以上拼相同肝的最惨小比进值，券这样袍在下束一次占迭代规中就护有一斤个或鹅几个湿基变舟量等晕于觉0祖，出绪现退浩化解赵，如胖某个钓最大老化问救题的悄单纯膨形表故为：迹C匹j畅4姜0堆3喷0色0东0艇i筛C目B效X房B跳x轨1贿x势2助x屠3旨x奶4龄x文5离x秋6叮0严x掉5烦6隶2仙0贿1戒0便1史0拴3点0候x叫4眼3洗[1社]抓-1羽0及1胁0师0粮3的0射x当6鱼5店1先1鹅1篮0益0槐1筹5蚊Z加0限-趟4盲0麦-糟3戒0劣0忆0织j携0达x亲5恒0傅0湾[2疲]冤1响-2呜1演0厨0肆4遗x很1袭3技1忆-1接0讨1喇0圆0好/飞0软x原6让3傍0拒2赔1产-1魔0富1骡1沈Z立12针0枪-塘4师-创3膨4所0恋0容j冰在出嫂现退钻化解胜后的悄继续跪迭代抄中，纲有可挤能出吓现基杯循环旺：趣B荐1热B厦2质……辅B丽1哑这样州迭代事下去希便永浓远得征不到磁最优摄解。词解决射基循硬环的饲方法洲很多煌，如瞎“音摄动滥法盘”箱、苏“嫩字典斜序法沾”简等等给。奏在计划算机竹上常席采用编“香Bl容an购d巩规则时”浓：界（衡1迎）取趟表中殿下标矮最小主的非援基变青量粒x扫k宁为换遣入变践量，赠即来k=逮mi压n{柳j注|眉j倍>0役}灯朋登（初2狸）按怕规则音计算己，若帅存在喷两个搅相同骗以上旁最小闪比值婆时，迷选取们下标厨最小失的基盈变量饱为换漠出变议量双x冬L猪，即垒值得抛庆幸陆的是域出现淘基循央环是严罕见芹的。摇丝喷§客3爬定对偶逢理论书与灵上敏度吸分析秩葬插一、臭LP侨的对苏偶问梁题主垮急1倾.衡引例准窄前已仿述引崇例谣1重是一客个在逆有限志资源注的条化件下寸，求拨使利后润最甜大的偏生产找计划帽安排犯问题然，其杨数学对模型径为：（设备）（原材料A）（原材料B）汤ma迟xZ压=2努x柏1（设备）（原材料A）（原材料B）翻现从珍另一然角度维考虑届此问镇题。岗假设想有客凉户提拴出要程求，宪租赁内工厂议的设璃备台梯时和输购买给工厂塞的原艳材料奶A帜、桥B麦，为秃其加蚂工生袋产别巷的产巧品，箩由客芝户支曾付台雀时费美和材挤料费北，此辉时工坝厂应批考虑雀如何撇为每缎种资欢源的匀定价毫问题藏？阶解：欢设灿y推1丰,y件2钩,y构3舟分别印表示奋出租酒单位践设备垄台时章的租割金和殃出售姜单位猪原材距料桂A域、坚B洪的价贵格（衡含附胡加值换）命工厂秋决策认者考隆虑：生润肝（猎1房）出揪租设价备和殿出售共原材喘料应篮不少汪于自筐己生拨产产送品的芳获利标，否述则不只如自箩己生永产为洋好。和因此吃有睛工厂丽的总妇收入临为担 光 束W=浙8y腔1咬+1手6y吨2赏+1踩2y证3梨（遣2涝）价占格应汪尽量柴低，究否则北没有咬竞争啦力（康此价顷格可件成为稀与客漂户谈效判的小底价捞）尘租赁恐者考桑虑：辆希望渔价格衬越低他越好完，否懂则另傲找他某人。泥于是欢，能忧够使谅双方算共同英接受悄的是芬Mi讲nW稿=8绵y叹1护+1趣6y管2谣+1苗2y代3胳上述色两个拴LP痕问题邪的数碌学模俩型是舞在同股一企串业的多资源恐状况折和生递产条衫件下纹产生哑的，姨且是栋同一取个问红题从淡不同雹角度帝考虑输所产祖生的给，因袖此两由者密努切相射关。回称这岂两个仓LP套问题插是互哈为对永偶的农两个抖LP聚问题状。其滨中一该个是惊另一祸个问挠题的适对偶伏问题购。韵2.疑从矩适阵形冶式讨弊论互匪为对稍偶敌LP气问题损由例尊1嫩虏 肌 席 病 款 桥 布有迁ma费xZ芦=c愁x河由矩萍阵形众式的休单纯酿形表侦中可赠知：半检验截数的魂表达材式为票：撒 萄 拆C偶B稳B友-1院N霞－拳C做N血和矛C械B帅B灰-1①②角犯皇当①②寻表示湾LP手问题形已得据到最腊优解刑令碑Y=缠C气B塘B刚-1情,钩且励②拥有扫Y士0剩由于捧基变踩量驾X龄B链的检毛验数福为辱0每，可妨改写控成能C友B锤B胞-1壳B降－贞C由B涝=0设因此窝，包暑括基熊变量湿在内哗的所恩有检福验数陡可写辉成漫(C娱B断B腊-1丽B洒－蓝C纯B江,橡C氧B霜B欧-1患N档－烤C击N傍)=青(C迹B销B乔-1聋A面－底C)协=尸YA编－缴C从≥翠0种即渴YA更C叨又对两②岛 丈 差Y=每C德B哑B陪-1专，两订边右贼乘坏b帜，有桐Yb搬=C某B极B吹-1温b=恒Z折由于扎Y盘无上捆界，新所以咬只有翼最小通值，蓝因此臂有药Mi艇nW推=Y盐b眼它是弦原问嫁题弟 岁 初{m桥ax阿Z=宰CX械|羞AX狱b,展X接0}逆的对化偶问填题努于是杏，对盯称形溪式下葱两个举互为示对偶疑LP贤问题使的数璃学模雕型为惠：诉Ma滴xZ厕=C惹X祝 衔 紫 教 脑Mi怪nW唇=Y驼b渠 汤 沾与侍 导 曲任何砌一个民LP俭问题田均有摧一个眼对偶棉LP狱问题鸭与之筝匹配沟。绑对偶乓理论东就是燕研究浆LP亿问题伏及其辆对偶孕问题鸭的理疮论，错它是警LP输理论国中的威重要炕内容造之一腾。贝二、肾对偶烫理论体域州1.诵原问俊题与签对偶烧问题暑的关逢系如孤下表积所示忍原怖泉始割湾对染麻偶筹闸表先原问壤题怀Ma眠x颗（对令偶问拌题）趣对偶丝问题拖Mi员n高（原聪问题栋）枯约束子条件浇数轻=m趟赛变量本个数继=m做第具i挤个约副束条贡件为嫁“”返第味i素个约报束条傍件为僻“≥弯”腹第室i不个约锈束条蜡件为均“灯=告”疾输第撇i匠个变辜量长≥纯0池爬第假i耕个变虚量帝≤场0察春第凉i裙个变溜量无野限制云变量堡个数鞠=m轰拒约束捧条件绵个数谋=n订第放i仅个变龄量洞≥遇0隙第拴i纷个变榜量冲≤晒0土第阁i识个变惰量无路限制行目第拔i思个约功束条舅件为饿“”杆使第厅i弓个约怎束条辟件为晓“≥夏”哥拘第拆i疤个约尊束条辫件为择“宏=涌”同第末i逗个约收束条浊件的戴右端炸项吐目标敞函第机i惯个变信量的亲系数必屿目标跑函数荒第眯i荡个变思量的碗系数劲勉第校i字个约找束条滴件的腰右端价顶欺2.贤对偶满问题盛的基据本性报质给Ma阔xZ衡=C嚷X搞 赏 锁 孩 枣Mi口nW寨=Y节b绍设怪劈 迫 必 抗 悉锻鹅（从1呆）（心对称拔性）坚对偶春问题溜的对圾偶是蛋原问挺题；这（况2小）（怠弱对庸偶性历）若钳是原荒问题机的可裙行解室，绝是对筋偶问愚题的政可行痕解；角告膊则附；捎（始3筒）（穷无界顷性）扛若原用问题岗（对右偶问今题）梁为无骆界解重，则云其对搭偶问很题（兆原问酒题）顿无可标行解返；容（激4幕）（遥最优恋性准储则）斯，若引、料分别坑是互强为对况偶问柳题的酒可行怒解，对且演C散=长b杨，则蛾、行分别用是它回们的臂最优附解；岛（傅5掌）（详对偶矩定理狸）若射互为袋对偶戴问题浇之一拿有最工优解勇，则挑另一耐问题稼必有辆最优然解，发且它么们的遮目标伍函数嘉值相附等。干管裙锣拥捆待奶宋饥剥寇海屠拳共芬①希原问模题与渴对偶助问题组都有阅最优朗解，闹且筑CX贷=Y横b猎；凯②宋一个聪问题杂具有昂无界钓解，锁则它辞的对令偶问独题无盯可行选解；半③违两个方问题修均无挑可行先解。蹈（列6嫂）（牲互补愈松驰牵性）你，若银X污*依、撞Y携*助分别航是原姨问题们的对点偶问欢题的螺可行匠解，慌则穴X糕*翼、束Y腔*仙是最洁优解洲的充屯要条续件是切：败Y厕*久X仪S扯=0揪,Y猛S虑X盐*仆=0馆(少其中质X团S均,Y邮S某分别驰是原亏问题怠和对部偶问骄题的见松驰嚷变量苍向量书)住。或俯，玉X湿*谎、歌Y泥*拦分别亏是原砖问题愚和对寸偶问诉题最竖优解绪的充脏要条检件是歇：买①航若文y肢*撇i店>0传，则遭a谅ij慰X晶*牺j异=b萍i禽②属若贫a兄ij勉X主*念j洲<b巩，则改y首*氧i帮=0准③肃若侮X沾*迫j演>0吐，则丝a谣ij劣y淹*辣i舰=c妥j哭④鸭若鸽a宅ij岩y摇*馋i狭>c绕j拘，则络X骡*嫂j点=0疏地波三、送对偶培单纯原形法丑胆戒1.助单纯舟形法咸的重浇新解烛释①（称为原始可行条件）②（称为对偶可行条件）纽X*灶是最予大化阀原珠LP帐问题暮最优滥解的虚充要幅条件吉①（称为原始可行条件）②（称为对偶可行条件）茧因此文，单孕纯形拣法是葬在保胀持原熔始可瞧行下哲，经侦过迭瓣代，魂逐步帐实现险对偶弯可行里，达衫到求姥出最捏优解提的过赵程。级根据硬对偶感问题衡的对摘称性芒，也姓可以场在保金持对里偶可叙行下覆，经艘过迭鲁代，租逐步躲实现绿原始弄可行测，以富求得叔最优土解。吉对偶丧单纯据形法袭就是无这种胀思想盯所设躬计的其。全2.若对偶虫单纯加形法蒸的计材算步撒骤：客举例店说明种血修3.负对偶葱单纯化形法洗与单阅纯形登法的厌不同批之点痛：蝴①对不要盯求模叫型中趣b以≥回0垫②垒先确倚定换丛出变剧量铁x沫L践，再范确定显换入唱变量逼x数K③韵咽洞4.出对偶牢单纯伪形法建适用驾对象丝①屠ma侮xZ戒=C走X(誉C犬≤暮0)杂 量 崖 息②垂ma黑xZ存=C叫X稳（连b风无限遗制）盖，缺③生当变累量个讨数（福约束浩个数稍时，刊可先浆转化略为其餐对偶涂问题数，再猜用单示纯形偿法或漏对偶怒单纯掠形法秆解之父④朗进行鲜灵敏丽度分码析时梨，有正时会屠用到帮此法塞姑串四、挥对偶笛解的潮经济坚含义哈和影纹子价除格代饿批1.汇对偶职解吓Y*莲=C尽B火B佣-1饮的经巧济含料义致窝俱设互积为对拜偶的脏LP篇问题验 浪 约ma用xZ令=C变X却 宾 立 缘mi击nW存=Y响b绕呈白(绿原庭)么 复 件 窃(城对铺)丹州懂有备延Z*孟=C于B怨B肃-1曾b=油W*阔汁思(特其中疫B坊为最酿优基曾)怠漠殊因此货鞭透或者椒说悬Z*垮=y问*习1很b腿1兔+y港*拆2钳b母2其+y四*帝m灿b暴m受隔吵则纹其含杨义是买：若娇对原雕问题炎右端冈常数摇项向艘量轨b今中的圆某一壮常数弟项祥b昂i抬增加分一个忍单位虏，目絮标函伙数的舌最优上值耍Z*伯的变距化将追是孝Y混i谢*县。换到句话钉说，搁Y蹈i植*顾表示冠当殊b溜i训增加纳一个闻单位哨时，奏目标卷函数身最优醋值的篮相应泄增量竿。实俯质上牙Y霸i叼*坊就是藏第帆i阀种资籍源边熄际价躺值的卵一种宴表现烘，也仆是对挨第退i倡种资杯源的庸一种突估价鼻。旧事实钢上，押如引屈例中近互为贷对偶汽LP退问题伸分别曲描述牧生产致计划慰问题此和资贺源的革定价蛋问题宵，其酒数学的模型掩分别混是：插ma革xZ高=2中x猜1扮+3鸭x谁2店 膀 恳 半 魂 愿mi喉nW璃=8弃y陆1鸦+1罗6y朝2眼+1收2y淹3被(腔原问慕题葱)忧 骂 纠(贴对偶毙问题储)办对原幕问题帐用单澡纯形店法求错解所撑得最交终表漆为菊C咱2纸3统0虽0蔬0误C茄B土X潜B济b慰x婚1迎x饺2型x助3刷x贸4济x缓5耳2阀x功1名4思1牧0丛0擦1/殊4净0虾0批x脊5锋4岔0集0劳-2歌1/读2曲1殿3荐x盗2伴2昏0夹1笑1/料2斯-1梅/8绢0华Z家14煮0素0确1.怜5真0.于12服5来0蛛由此汗，它燃们的趁最优稿解分竭别是渗X*训=(仍4,隆2)立T腊和桌Y=闪(1畅.5蛾,0乒.1启25挥,0晴)养拆润Z*捡=W争*=趴14豆=8纪Y厨1挪*+惕16麻Y春2太*1万2Y无3倡*铁封次健虹其中趁Y铁1况*=贫1.内5澡表示贿单独忆对设亦备台围时增猪加爪1检个单肠位，璃可使乘Z交值增凑加戒1.剂5惨个单鄙位的脏利润片；嫩Y抓2沙*=旱0.璃12妙5听表示睁单独急对原病材料站A爹增加即1响个单育位，杰可使诊Z敢值增椒加撑0.枪12键5欲个单舌位的厚利润第；而每Y罪3稠*=匠0对表示注单独束对原壶材料碗B帮增加抽一个誉单位稀，却稼不使讽Z扑值增管加。建这是孟因为版从最择终表玻中可秤看出斥，在浊最优碗方案冶中，感松驰倾变量鹅x涂5贼=4吐，即偏表示希在最赵优生揪产方挎案中孔，原扒材料于B爱尚有酸4丸个单练位剩羡余被徒闲置打，不等产生影任何萍经济爬效益绩。寨胆雷2.护影子锅价格飘的定脏义维把某勇一经妄济结陈构中桨的某摆种资芒源，大在最器优决点策下嫩的边佳际价敏值称据为该际资源谁在此权经济滥结构与中的墙影子表价格识。采影子拌价格耗是在哥最优醋决策猾下对航资源约的一网种估染价，府没有腥最优唇决策电就没牧有影摄子价啦格，风所以坐影子膜价格终又称汇“忙最优卷计划据价格赔”芹，立“历预测斯价格条”穴等等夫。禁资源惰的影务子价魂格定卷量的昨反映腊了单射位资旋源在累最优西生产杂方案星中为策总收茶益应鼻提供黑的收幕益，灭因此宪，资购源的谋影子潮价格匹也可矮称为东在最素优方主案中地投入馅生产铺的机启会成活本。担3.砖影子浆价格满的求售法狠奶害(1吸)膛在非陡退化宰情况厨下：葵设妹B蒸为晚LP小问题喂的最惊优基恶，则协膀互陶资源们的影亩价鬼=Y翻*=印C仰B岸B叠-1雪垄罚(2剂)垮在退旁化情羞况下触：栽出马当对尘偶问像题有识K馒个最娱优解范，则崖第显i旦种资拦源的制影价是=浑即影筐价的到第欲i垮个分常量等珍于这赚K件个对渡偶解踩中第弃i肚个分耍量的点最小丸值。煎例如持，设俘某资波源利奉用问宰题为(资源1限制)(资源2限制)其丽ma行xZ纠(资源1限制)(资源2限制)讨最港突终浅拜表震3缴1啊0尺0屠X托B与x啦1进x孟2叙x隙3胸x常4倚x鱼1伸2棉1事1停1虾0运x煌4售0表0篮-1呈[-政3]携1友Z窜6诸0杯2辟3醋0强x惯1驰2坐1寨2/命3牺0蚕1/肝3浸x普3踩0尘0喇1/壮3总1悦-1啊/3蒸Z续6订0握1锯0断1局∴芹余资源延1车的影糊价唐侄缓环共=m仁in碌{y等1至*(菠1)去,y藏1枕*(暂2)灰}腥政态印冠=m国in治{3沉,0险}=莲0牵柳菠仪帜资源沉2物的影尚价赞=m醒in遵{y痛2院*(它1)际,y防2并*(分2)俊}=恒mi光n{摘0,纲1}欧=0影价>0，说明该资源已耗尽，成为短线资源。影价=0，说明该资源有剩余，成为长线资源。指什弹4.龄影价>0，说明该资源已耗尽，成为短线资源。影价=0，说明该资源有剩余，成为长线资源。臣目洲（苦1冤）指芹出企受业挖得潜革用新的煤途径蛙旧户（脸2安）对彼市场项资源拍的最悉优配厅置起派着推术进作涛用辱围麻（流3宵）可你为企赴业决纽策者讽提供留调整予最优谜生产按方案魂的信消息古补街胁纽C蚕B牲B怪-1既P寇j呢－馒C股j币<0黎说明闷第寄j毛种产授品应惭投产特愉晴阿基C剑B脏B缎-1轧P鞭j佳－暖C锐j远>0堡说明舅第誉j含种产摔品不葱应投洒产渡尤其免对新鞋产品暗是否艇应投董产，由可按纱以上变两式哀考虑砌。登（博4揪）可额以预丑测产壮品的挂价格木叼徒（允5蒸）可珠作为哑同类绩企业燥经济心效益恭评估湿指标劣之一底。靠疯位五、扔灵敏柿度分枯析酸面对康市场家变化暂，灵源敏度娃分析济的任蚊务是墓须解茎决以壤下两议类问御题：寿（南1药）当您系数俭A吊、没b犬、毯c吼中的晚某个燥发生符变化澡时，鹅目前污的最拉优基筒是否稻仍最拒优（缺即目诵前的炕最优柿生产稠方案散是否检要变郊化）南？蛛闯捏（欲2宝）为洗保持疯目前贝最优粮基仍坛是最泼优基圣，参赔数羊A掉、颈b颂、脏c眯允许拦变化好范围斯是什都么？吨蹄狐灵敏浆度分猜析的长方法污是在辩目前出最优饰基傅B郊下进夺行的粱。即锄当参止数坊A妄、架b俯、钩c颈中的型某一冈个或刺几个增发生下变化自时，冻考察垦是否讯影响限以下永两式咬的成霉立？轿裕饮查壮1.节对资舟源数蛙量习b泄r技变化疮的分买析束当蓬b颈中某光个岂b拔r哗发生单改变肃时，少将影棵响基眯变量轰的取晌值棒X额B念=B欣-1增b纪。若施b或r锡的变逃化仍舅满足念B维-1蹲b浇≥岭0播，则渡目前片的基记B揉仍为幅最优逐基，锦仅在复B尽-1燃b盯和灿C州B衣B删-1鞋b游的数竭量上唐有些披改变潮。若兰b厦r爹的变勺化使宰B肾-1支b粉中某急些分厘量小旅于啦0抛，则德目前膨的基诉成为玻非可符行基牺，为圈此，轰可用乌对偶翻单纯帆形法非迭代客求得墓新的境最优巨解。旨B王-1躬b修≥矛0足给出欺了使偿最优慧基阻B陷保持肿不变艳时石△慢b必r僻的允开许的希变化深范围度：乌由解析不等绳式组详昌域B柳-1丈(b汉+王△液b)淋=B李-1挑b+怨B过-1谱可得摘：窗蒸开必贡其中泥为最谜终表双中慨列的列第瓶i少个分术量，悬为堆B趴-1猪中第司r拣列的植元素首。脆妹雕例骑占绩2.珠对价拢值系犁数富C间j僚变化部的分茂析怜键盲（吵1耍）当公C串N币中某妄个缺C犯j如发生侄变化锅时，挤只影耍到非并基变赛量飞x凝j拳的检交验数席挣问娘茧漠由于饰欺定若害，则侨△捞C条j叙≤σ肥j潮。视贵善这就族是保隆持最卖优基逆不变淡下，替△蜂C绣j狱的允包许变岔化范耍围。景否则立，用拣单纯扁形法西继续乱迭代倡，求浇得新架的最锹优解迎。旅暑叔（裤2势）当讲C浮B哄中某途个帝C李r炸发生稳变化碌时，忆则会脚影响江到所哀有非风基变男量的谅检验新数便σ腰N绳=C法B丝B俊-1愧N奔－楼C过N抽。秀解不烈等式初组对 列 陷=罢(C报B踏+爹△商C疼B伪)B砖-1尾N餐－臂C饲N廉=(拒C进B半B劈-1总N湾－忙C碧N透)+蹦△朵C莲B兄B己-1驰N朋≥她0越走即飘 轰(C的B化B锻-1滔N申－盗C敞N射)+愤(0长,蚕…赚,遵△忆C损r便,盾…独,0被)B斑-1葱N边≥边0脂得到边使最处优解丛不变疏△迫C村r偶的允丹许变束化范勺围；厘势翅摩喇例彼厕乌（趋3汗）对鱼增加常新产博品的株分析逗设革柴企业糊在计衣划期窃内，尤拟议步生产谈新产伟品少X吵n+正1悬，并际已知偿新产睛品的堡单位捷利润咏为井C饼n+授1飞，消丧耗系啦数向并量为时P晋n+鲁1员=(挨a辉1,茶n+嘱1头,a倚2,泽n+伪1胜,率…撒a您m,误n+庸1杯)阁T伯，此秋时应淹如何茶分析税才能织确定族该新厉产品苗理澡菊投产走？冠增加肤新产帐品应喝在不漠影响举企业妻目前然计划质期内赚最优约生产楚的前敏提下壤进行牌。因北此可吼从现仰行的爹最估绝基摆B慧出发俯考虑版：脆若匀σ贺n+呆1告=C就B定B闹-1师P印n+建1供－类C唐n+找1事<0舌，则瓜应投客产毛若舒σ眨n+临1纵=C闸B更B扛-1厨P副n+妹1湿－敏C浙n+现1耐>0良，则规不应岗投入员。芹牢夺即新徐产品悼的机雨会成初本小仔于目魔前的稼市场阁价格玉时，越应投社产否徐则不完应投帮产。开纯船（缩4萍）对蝇增加骆新约艺束条勒件的蛙分析劲在企哗业生趣产过易程中仆，经柏常有捉新情理况发监生，怨造成畏原本喇不紧森缺的谈某种史资源议变成冬为紧段缺资午源，味对生西产计断划造悠成影著响，辉如水券、电迷和资丰源的翁供应嘱不足农等，广对生廊产过煮程提棉出了哀新约己束等似。没对增角加新寿约束请条件庄的分细析方商法步铁骤是差：论第一月步：升将目完前的弯最优池解代级入新碎增加粉的约纯束，唤若能耗满足重约束底条件路，则指说明颗新增示约束尿对目婆前的钻最优绍解（医即最淋优生贯产方呼案）去不构挥成影增响（咏称此理约束洲为不漂起作辫用约孕束）驻，可障暂时扑不考送虑新龟增约牧束条等件。樱否则级转下睬一步村；属第二锣步：县把新叮增约移束添佳加到遮原问侄题最科终表悠中，贺并作歪初等吐行变歪换，薯构成俯对偶约可行亮的单糊纯形机表，景并用鼻对偶级单纯隆形法移迭代傲，求惯出新好的最谈优解洽。例：猎（穴5纹）技鸟术系业数厉a呈ij兴变化睁的分当析什第一显种情选况（恐当虫j方J坝N桐）：宾方法朴与增卧加一冒个新塔产品蚕的分农析相丝同。欠第二奴种情咬况（零当唤j句J下B馒）：焰由于葵B互中元超素的梯改变芒影响籍到辈B袜-1害的变询化，核因此车也影柳响到钳T(鼻B)类。目挂前的馆基长B岁对应睛的解窃有可在能既饮不是敬原始承可行海，也由不是抵对偶饼可行饿。于市是不舍如重坐新求识解。强第二讨章慎厕特殊什LP炸问题摸及其络解法腰所谓麻特殊战LP泡问题科是指挑LP烫模型渴的系衰数矩贝阵具均有特长殊的绳结构饥，有盆可能田找到词比单润纯形宏法更烫为简携便的批求解弯方法叔，从短而节基省人奶力和播物力火。循§竞1辛腾运输傻问题者及其倘解法仔引例磁：卫某公撒司经翠销甲如产品拔，它韵下设蒸三个京加工腿厂，淋每日休的产怪量分属别为百：柏A养1父-7泛吨，铁A困2悦-4气吨，鹿A营3硬-9跳吨。贸该公结司把晚这些票产品躬分别慈运往吼四个洁销售届点，术各销循售每纤日销女量为卧：歪B股1糟-3涨吨，午B财2指-6另吨，寇B祝3疾-5卫吨，谊B产4培-6垮吨。子已知绿从各炕工厂杯到各豆销售抵点的棋单位锤产品育的运迅价为课下表快所示抛。问抚该公术司应掀如何陈调运况产品始，在态满足蚁各销惯售点相需求许量的坏前提渗下，键使总钩运费荷为最无少。伏平衡猎表（毫单位扯：吨象）横 弊 码 耍运价栽表捐 农 寒 寨（单饲位：搁元膜/迁吨）吓销地青产地帆B面1知B庙2爷B闯3桑B遇4疾产量火B煮1镇B亭2碗B辜3部B颂4害A腥1马7即3巧11巴3信10与A医2冒4吓1塑9衡2箭8老A面3正9畏7咸4盟10如5件销贴益量耐3浓6扎5映6垒解：值这是戚一个驴产销锁平衡罪的运着输问愤题，掠其数忧学模租型是诉：袜察番设筛X聪ij系表示结从役A授i宁调运痰产品滑到坦B盾j夫的数雄量（惕吨）逗，则协mi套nZ跪=3久X踢11秋+1首1X而12饶+3止X白13览+1脖0X直14粉+X片21哥+9华X兼22诱劈+2药X匀23料+8赖X尺24锻+7傻X注31猎+4妻X租32方+1游0X煌33新+5声X貌34寄x挠11广+x菌12坊+x厉13役+x唤14煮 传 燕 径 喝 芬 少 补 栋 汉=7皇x挡21错+x邻22柄+x必23买+x以24躁 霞 止 螺 惯 身=4田x枯31匆+x被32安+x饿33陷+x钢34其 长=9s.t菊x云11餐 译 省 术 绕+x孝21军 君 纪 肆 钓+x匙31筝 劣 共 哲 标=3s.t泼x挨12福 初 全 叫+x呜22爬 也 痒 添 芽+x闪32抬 系 辆 蝇=6部x赤13杯 买 宜 博+x御23纲 早 通 诚 代+x沫33朋 榜 督=5蝇x云14拒 题 眨 轮+x额24右 榜 云 围 交+x舍34浊 炎=6爪x筛ij规≥餐0泄辉米(i鸭=1判,2湿,3沟,座认j=姑1,巴2,秒3,流4)环三粥一、行产量净平衡差的运绵输问绵题及挡其解少法延叠早1.赚产销边平衡塑的运汪输问敲题的售数学慧模型断及其奏特点姓特点洽：（消1鸟）其狮系数杜矩阵予的结耽构疏匆松，爽且每台一列上向量幕 胖 逃P岗ij罪=(枕0,他…摸1,拆…认1,晋…触0)令T协=e件i佣+e揭m+需j竟扎份可以蛛证明奖，巡r(植A)抄=m缸+n秘－宁1奥。即限有示m+粉n珍－盟1夺个独谅立方饰程。士于是悉，该锐LP爽问题随有且钱仅有身m+推n半－幸1别个基羡变量壁。透（直2凶）究（产感销平伸衡条连件）仙旦禽（简3节）因让为顽故必摩有可厨行解迎和最晨优解句。库由于唐上述注特点阔，若窑按单扭纯形卧法求闻解必赠须增钢加人微工变识量，扛致使谅计算相量大斧大增宿加，揪故用毯特殊房解法统──跳表上煮作业咱法。洋2.咐表上面作业姻法佣表上拦作业眠法实袄质上诱还是西单纯旦形法业，但矩具体舌计算中和术疼语上杏有所莫不同饭。其哈计算挪步骤梯方法帜，并劳通过助对引袋例的俱求解竭过程售说明寻之一挽。耻（信1康）用竟最小兴元素冲法确更定初革始方飘案（乞即初虑始基西可行右解）挑柄忘切记嘴在产闸销平里衡表亏上必壮须且串只能虾填写粗m+腿n然－秤1兵个数粉字格滨反炊（什2止）用段位势掘法求堪出空外格的爷检验柄数并良进行杯最优多解的粉判别挤设趴u音1锻,u舞2浆,肆…劝u液m骡;鸟v压1屡,v型2啄,庙…死,v粥n伐是对趴应运考输问弄题刻m+络n宫个约馆束条董件的舟对偶膨变量铁，贤B过为含煎有人广工变隙量的蓝初始海可行偏基，疯由舒LP练问题誓的对涂偶理尿论知替C全B泻B刚-1兵=(桐u陵1窄,u题2暂,挖…滥u卧m追;剧v低1碑,v度2叶,治…潜,v条n拴)垃伴事而每岗个决融策变慈量龟X即ij爪相应隐的系脂数向负量色P富ij蛾=e尺i驼+e军m+欢j绣，所绩以蜡C什B借B锁-1光P青ij榜=u献i泡+v巨j贩狂夺于是翻，检李验数纷σ爬ij类=C来B省B惯-1奶P接ij邀－尿C简ij感丝=(眉u晌i孝+v寸j漆)胞－冻C水ij状又各愧基变艰量的针检验械数为郑0盒，故监对每散个基饮变量娃所在创的数衬格的瓶检验骆数有袜(例u间i喉+v义j辞)答－广C鬼ij吓=伏0积正柳添i,驱j尺J沉B播百瞎即有浸方程疾组君筑饰掏冲共开m+闪n据个未智知数折尺s崭=m箱+n爬－阁1特个方纹程烈显然仁上述量方程胶有解屿，且揪由于库含有蒙一个战自由啄变量画，因摄此，辩可令监任一航未知蹦数为棋0芒，就红可求灿出上生述方挖程组涛的解探(u端i1有,u耀i2永,乔…者u闭im悲,v速j1拍,v幼j2颗,桐…触v咸jn宣)调──犹称为钞位势鞋解。蛾如用伸位势基法求正引例碍初始辜基可叙行解女的检脂验数章：叹销地袭产地酱B叶1西B妹2电B蹦3己B扬4仪u净i臣A意1亦-1检3涝-2落11家③毯⑩配0解A享2附1沾-1密9括②县+1旨⑧幕-1总A温3支-1少0岁7附④别-1变2临⑩疏⑤额-5躁v爸j匀2业9秆3雕10共干倍第一汗步：润将运齿价表塌中的牺数字腾分别阻写在避各格报听右道上角评，并填对基映变量草相应鹿的运事价加疫圈，社同时础在表尼中增茅加松v乳j米和长u君i乘列。石渠纤第二疫步：筋利用驼圈数韵格分难别算驾出沿u够i嘴和售v缠j绒，即闪令冶u舟1裤=0县，然售后按个u闸i拾+v垫j势=C娇ij布辱俱(i绳,j踢J朝B碑)据，相棍继确合定悲u歉i倾，屈v正j得的值骑。于俯是有造v竟3耐=3记,v铲4刚=1象0,湿u州2掘=-偶1,捐v系1厚=2束,u捎3僚=-巨5,素v酱2店=9期第三产步：欧按铲σ咏ij壮=似(u怖i璃+v内j执)洒－熟C路ij浅艇(比i,殖j礼J展N即)醉算出盾表中德各空谢格（压即非揉基变研量）巾的检着验数泥：梅σ四11箱=(史0+宝2)仆－份3=炮-庄1拥，倾σ协12揪=(紧0+识9)顾－羡11侧=凝-惕2她，膛σ惰22漠=衡-造1松，搅σ艺24蚊=1载，航σ欺31脏=充-拔10幕，撤σ侦33正=勉-博12敌由于竿运输承问题邮的目山标函阅数是墓求最档小化井，故近判别式最优霸解的四准则婚是所栽有的鹅σ雨ij拼=C庸B悼B慨-1狗P肥ij鸡－牵C俩ij逮≤柜0王因为婚24谨=巡+音1>缠0响，所蹲以目赖前尚肝未得惕到最熔优解新，尚导须改初进落（解3锯）在孝调运缸平衡民表上趴用闭奶回路打法进梯行调德整，定得到瞒新的炒基可黎行解垂（新糖的调肌运方庙案）膀敬刺i)远派确定心换入返变量滋：自串上而愧上，脾自左矛向右孔第一桌个正仙检验罢数相斑应的晨非基恨变量础（空勉格）富为入姨基变窃量。斯戏盐ii昂)然作闭飘回路消：以楚换入症变量沈空格聪为出症发点知，用拌水平到或垂病直线私向前就划，胁当碰宴到某娇一恰残当数贡格转扫90奉后，疾继续黄前进镰，直锯至回服到起乓始空教格止步。亩劳跟ii多i)营使确定铁调整覆量淘=m嘱in闸{敌第奇锣数次青拐角斧格的辟调运岔量撇}暂曲容iv免)蓄在闭耗回路急上进伞行调袍整：转对闭顶回路运上每三个奇叶数次致拐角灭格的虹调运兆量－彻对闭堵回路踩上每腾个第沿偶数舞次（旋含起屠始格蜜）拐指角格响的调狗运量畜+萝。调义整后娃，将瞎闭回筐路中族为或0王的一惊个数零格作盗为空哭格（绞即出荡基变覆量）起。兴闭回葡路外崖的各丢调运首量不钉变。策这样析便得棍到新享的调森运方勿案（域新基顾可行封解）世销地点产地胖B暂1跪B教2筹B抄3锅B萄4期产量陶A骨1缝(+惜1)据4输3充(-彻1)心7辨A雾2鄙3驳(-放1)改1割(+筛1)寿4遍A郊3芹6午3斯9侦销量揉3爸6肯5屿6殃对调数整后质所得敲的新纺方案欲，再识进行刮检验赔，已院得到暗最优攻解（宰最优禁调运摄方案罚）；访从晴A影1江调运淹到税5捧吨到梅B刑3桥，调叨运庭2市吨到你B位4田从尺A寄2纹调运雄到筹3暮吨到膊B霸1注，调乞运归1垃吨到忽B影4协从炉A壁3行调运毫到溪6闪吨到作B缺2腾，调皂运厨3歌吨到嘱B摄4博总运半费最逝小是絮85制元识（皱4污）在范进行身表上心作业傻法须灵注意钱的问需题：旷华沟i)烛竟在最谱终调庭运表棵中，姜若有已某个吴空格饮（非庆基变壳量）协的检垄验为改0炮时，合则表含明该棚运输镇问题桌有多病重调制运方犹案；蒸例概ii嫂)菌在确住定初建始方挂案时甲，若胳在犁(i碧,j退)宜格填待上某蝇数字清后炸,挂出现歼A扬i梨处的贯余量非=B第j济处的旺需量发，此卷时必锈须在男平衡筛表上秤被划吉去行贪和列殖相应届位置喂的任父一空理格处犯填上欧一个挑“肺0总”钓，以翁满足销数格爹=m届+n绒－于1猫个的匹需要宽；作柄膝ii鞭i)粱臂在用散闭回音路法舒调整核时，填当闭书回路罚上第雷奇数谣次拐白角数营有几僻个相脚同的值最小务值时堂，调捎整后糊只能灿有一俭个空巴格，奖其余盯均要鹊保留坟数猛“横0亦”烧，以斥保证茧数格贸=m王+n惯－寄1榴个的诚需要恰。生以上贩ii殖)争，井ii绝i)抓均出到现退理化解洋。萍iv朝)吵用最呼小元储素法认所得艺到的匠初始牌方案移可以毅不唯痰一。赵孕工二、良产销桌不平扔衡的着运输偷的问见题及桨其求遣解方像法镇蹄寺1.且数学冤模型节：产协大于淡销迫漂产小耕于销站眯让 倘 强熟雅裙蚂2.形解法罢思路旬：纲将不缩平衡秋转化陷为平子衡。倘即当构时，沙考虑致在平匪衡表娃中增路加一肠虚拟葡列，颂表示武增加罚一个济销货拣点挑(j茧=n滑+1越)扔如仓衣库，肾其销易货量杏为提，且峰各运伙价福Ci吊n+售1=箭0嫁；当剂时，寺考虑惨在平闪衡表犯中增弓加一膊虚拟弓行，酷表示聚增加埋一个辅新产莲地，忧且各据运价驳C烤m+阵1j帐=0犹。然肆后再腹用产晴销平趋衡的偏运输春问题局的解送法进档行解是之。例亲三、田转运同问题清及其勿解法浊：坝棵浩1.统所谓用转运吵问题骗是在痒以下均背景码产生妻的：夜酿美(1释)都每个逃工厂板生产率的产韵品不响直接川运到顿销地些，可肚以几革个产并地集疗中一田起运衰。场读波(2气)蜓运往滑各销教地的衔物资皇可先坦运给匙其中劣的几凤个销贯地，辛再转赏运给单其它胁销地捡。芒郊情(3籍)沉除产村、销装地之进外，每还可阅以有赶几个陕中间饮转运芹站，键在产唉地之茧间，气销地布之间陡或产狐销之敬间转由运。抬凡类惰似上米述情债况下渡的调盲运物乓资并仿使总皆运费济最小誉的问扶题统婶称为胆转运言问题烤。遭2.合求解派“慎转运辫问题专”资的思短路是肌把问含题中奴所有婚的产妻地、雪中转旱站和疗销地班都既岛看作添产地酒，又掏都看的作销袍地，老把销“餐转运拿问题妹”帅变成馒扩大解后的姑产销模平衡兆的运尊输问普题处谎理。什宾络3.状求解森“域转运热问题受”坟的方坛法步芳骤：婶徐武(1传)番建立过扩大逗的产星销平绵衡运统输问赴题单德位运回价表开。其矩中刷柳紧1)赢对两腹地不闻能直挠接运柄输的柱单位保运价速定为粱M鞠（很哭大的惠正数岔）；群为河2)硬对所莫有中孔转站毕T孤j真的产预量和悄销量帆定为葛相等左，设犯定为棉；阁营绞3)蹦对产荒量列婚的各热数据陪可按躁下式波计算牌并填隐入：剥酷炼A绳i结的产王量记=a乘i特+疏,T吴j孔产量午=啦，臣B路j搅的产屑量酿=棕俱述4)进对销惜量行威的各江数据杂可按厌下式借计算胀并填风入：躁也海A鼠j蛛的产弄量截=容,T颤j秆销量电=荐，闭B制j窑的销宰量年=艘+b样j黄晕恨(2张)达用表旁上作腿业法布进行蜘求解踢料元§予2躬售指派善问题踩及其调解法引例涝任务储人员至E柏J修G倒R堪甲晶2伏15抗13冒4馅乙雾10麦4驴14记15仗丙毙9卸14记16凭13幻丁侨7验8启11艘9当指派第i人去完成第j项工作否则军印都解：肿设膝X坟ij瞒表示狗第描i栗人从战事第妻j店当指派第i人去完成第j项工作否则子因此拍，该梦问题崇的数检学模刺型为令Mi阿nZ席=2押X顷11混+1篇5X际12峰+1热3X蚊13抚+4初X馒14朱+1羊0X瑞21长+4岛X觉22扫+1葵4X选23款+1批5X咏24忽讨式盖+9辩X蛛31部+1杏4X棒32刮+1慕6X纠33迈+1面3X探34摆+7胸X套41躁+8漏X拦42抬+1到1X管43往+9症X献44住表示控第忙j权项工廉作只门指派免人完昂成君表示翼第痛i摆人被泉指派奶完成粮一项粱工作术X鼓ij蔬=0织或爱1(禽i,愧j=遭1,假2,薄3,倾4)跑诸如袜此类鼻，有号n脏项任泄务，格恰好准有歌n忆个人尝可承磁担这武些任拥务，蓄但由歌于每估人的陈专长私技术园不同戏，完豆成任纠务的迎效率骡(获所费畜时间染_院不同兴，为底使完趋成岩n鬼项任酒务的沫总效箩率最碗高（喉即所坑需总辰时最戏少）三，应被如何俘指派票（分避派）谁人员毅的问熔题统助称为锋指派疼（分涌派）予问题草。云一、驶指派贪问题斗的数波学模龄型及初其特绒点三斑既1.却数学谋模型炒：缺修德2.蹦特点哄厌政（套1准）给年定一叙个指围派问向题时截，必灵须给姓出效洗率矩买阵（解系数肺矩阵鞋）剖C=玻(C草ij轰)献nx横n励,蕉且榴C肠ij枣0识，因赵此必池有最抬优解冠(亿)。腊稍乐（肚2颜）指取派问姓题是服一种焦特殊晶的平明衡的冷运输母问题游，由丹于模冻型结饭构的车特殊对性（昨看作泄每产罢地的耽产量仅均为易1披，每处销地蜂的销解量均茶为惠1咱），鸦故可棵用更古为简哲便的填匈牙供利法览进行考求解酷。犹栏贸（趣3巧）解诞矩阵万是指挡派问扑题的前可行想解，既但不床一定猴是最沾优解知。恋糠地二、池指派袖问题极的解养法挽──匆匈牙项利法就雅塔1.豆匈牙赢利法颤的基轮本思剃想是极：对军同一骂项工妹作（聚任务湿）挑j砍来说问，同卖时提户高或抹降低汗每人侦相同黑的效富率（捏常数弃t颗i渡），瓦不影叶响其淘最优用指派哨；同军样，面对同病一个榜人提i然来说闻，完循成各嗓项工宿作的辱效率汽都提疫高或旨降低前相同势的效霜率（者常数宋d腐i锋），亏也不究影响驾其最推优指大派，筋因此度可得爷到新注的效霞率矩棒阵趋(b撑ij生)鸣nx提n荐，其待中哈b残ij待=C萍ij往+t惠i挣+d撤j腾峰钩醋（对旱所有扁的愉i,纪j剩）脑则新访的目茫标函校数为秧 争 冻 究 箩 钞 侵 隔 姨辽 佩 祝 门 布 柜苍 踢 狱 察 喊 抓冈其中思为常天数晒这说验明士Z荐与京Z臂同时报达到车最小测值。异因而桌最优玩解相烟同。剑故指炼派问属题有愤以下摆性质浅：留若从宰效率碎矩阵届(C既ij题)劝nx误n锄的一蹦行（叮列）遍各元叔素中定分别颈减去培该行惠（列废）的站最小扇元素蹦，得屿到的耻新效梳率矩告阵炊(b辰ij赛)阅nx掏n吵不改备变原拢指派港问题裁的最供优解秤。茫2.疫匈牙夫利法态梁统三、勇对求认最大胀化的堵指派膝问题母，（守即求吓）慰,哀可采蔑用构善造新道的效搏率矩闲阵嗓(M犯－蜂C秃ij纵)n昨xn哗，其国中秤M=算ma筑x{这C咐ij棉}卷，（窗显然料M茎－库C敞ij咐0例），万将其循转化冷为爪求所觉得到言的最丹优解赛就是特原问邻题的轿最优冻解。吓事实膝上叠谱专师撇由于绞nM截为常锹数，层因此报，使围Z絮取得仰最小伞的最疲优解驶就是垃使馅Z很取得按最大演的最占优解秋。果4.服以上腹讨论瞎的指尤派问加题是恭效率厌矩阵笑的行篮数等猴于列梢数，维即讨m+弦n症的