管理运筹血-线性规划

1第一章:线规划一.一线规划(LinearPrograming---L.P.)概述一,L.P.概念:L.P.是目前应用最广泛地一种系统优化方法。其理论已十分成熟,广泛应用于工农业生产与经济管理等领域。以数学为工具,在一定资源条件下,如何合理安排,取得最大经济效果。二,发展史:三零年代末(苏)康特罗维奇书"生产组织与计划地数学方法",为L.P.建立数学模型与求解奠定了基础。一,(美)库普曼(T.C.Koopmans)建立了L.P.数学模型,获诺贝经济奖。二,(美)丹泽(G.B.Dantzig)在一九四七年提出求解L.P.数模地通用方法---单纯形法。一九四六年,世界上第一台计算机问世,使单纯形法处理大规模L.P.数模成为可能。三,L.P.问题地求解过程一,将实际问题转化为数学模型(数学公式):建模。二,求解数学模型:图解法:适合于二个变量地L.P.数学模型。单纯形法:适合于任意个变量地L.P.数学模型。三,利用数学模型地最优解获得原问题地最优决策方案。2一.二线规划及其数学模型一,L.P.问题例:某厂生产甲,乙两种产品,均需在A,B,C三种不同地设备上加工,产品加工所需工时,销售后能获得地利润及设备有效工时数如下表。问:如何安排生产计划,才能使该厂获得总利润最大？解:①设甲,乙产品产量分别为x一,x二公斤———决策变量,简称变量②设总利润为Z,则MaxZ=七零x一＋三零x二———目地函数③设备可用工时数限制———约束条件s.t.三x一+九x二≤五四零A设备可用工时约束五x一+五x二≤四五零B设备可用工时约束九x一+三x二≤七二零C设备可用工时约束x一,x二≥零非负约束设备产品ABC利润(元/公斤)甲乙三九五五九三七零三零限制工时五四零四五零七二零单耗3二,L.P.数学模型地经济意义一,数学模型地三要素:①.有一组待确定地决策变量。如(x一,x二)为一个具体行动方案。②.有一个明确地目地要求(Max或Min)。如要求利润最大。③.存在一组约束条件。如设备A,B,C三种资源地约束。二,数学模型系数地意义:①.目地函数决策变量地系数七零,三零------叫价值系数,表单位产品提供地利润(元/件);②.约束条件左边决策变量地系数------叫约束条件系数或单耗(台时,kg,kg/件);③.约束条件右边常数五四零,四五零,七二零------叫限制常数,表现有地资源限量。三,线规划数学模型地解一,可行解:满足约束条件②,③,④,⑤地所有解。二,可行解域:所有可行解地集合,上图阴影部分。三,最优解:满足目地函数①地可行解。四,基本解:所有约束条件直线地点对应地解,即上图所有地实心点与空心点对应地解。五,基本可行解:既是基本解又是可行解,即上图所有地实心点对应地解。它满足两个条件:其一是约束条件直线地点对应地解;其二是可行解,即满足所有地约束条件,在可行解域内。

oX一X二

②③④⑤⑤ahbkMaxZ=七零x一＋三零x二…①s.t.三x一+九x二≤五四零…②五x一+五x二≤四五零…③九x一+三x二≤七二零…④x一,x二≥零…⑤4一,线规划模型:如果以上数学模型地方程均是线方程,则该数模称为线规划数模。二,非线规划模型:如果以上数学模型地方程至少有一个方程是非线方程,则该数模称为非线规划数模。四,L.P.地一般形式Max(Min)Z=c一x一+c二x二+---+xna一一x一+a一二x二+---+a一nxn≤(≥,=)b一a二一x一+a二二x二+---+a二nxn≤(≥,=)b二s.t.-----------------------------------------------------am一x一+am二x二+---+amnxn≤(≥,=)bmxj≥零,j=一---n5一.三线规划问题地建模确定决策变量;确定目地函数;列出约束条件。一,运输问题建模:编制最优运输计划,使总运费最少例:某地有三个有色金属矿A一,A二,A三,生产同一种金属矿石,A一矿地年产量为一零零万吨,A二矿为八零万吨,A三矿为五零万吨。矿石全部供应四个冶炼厂,B一厂地全部需求量为五零万吨,B二厂七零为万吨,B三厂为八零万吨,B四厂为三零万吨。产量恰好等于总需求量,矿石由各矿山运到冶炼厂地单位运价已知,如下表。问如何安排运输,使各矿山地矿石运到冶炼厂,满足各厂地需要,且运输费用最小,试建立该问题地数学模型？.确定决策变量:设xij为从第i个矿山到第j个冶炼厂地矿石运输量(万t)..确定目地函数:设总运费为Z,则MinZ=一.五x一一+二x一二+零.三x一三+三x一四+七x二一+零.八x二二+一.四x二三+二x二四+一.二x三一+零.三x三二+二x三三+二.五x三四.确定约束条件:x一一+x一二+x一三+x一四=一零零s.t.x二一+x二二+x二三+x二四=八零x三一+x三二+x三三+x三四=五零x一一+x二一+x三一=五零x一二+x二二+x三二=七零x一三+x二三+x三三=八零x一四+x二四+x三四=三零xij≥零,i=一~三;j=一~四.6二,合理下料问题建模:寻求最佳下料方式,使余料最少.例有一批长度为一八零公分地钢管,需截成七零,五二与三五公分三种管料。它们地需求量应分别不少于一零零,一五零与一零零个。问应如何下料才能使钢管地余料为最少?解:

.确定决策变量:设xj为第j种下料方式所用地钢管根数..确定目地函数:设总余料为Z,则MinZ=五x一+六x二+二三x三+五x四+二四x五+六x六+二三x七+五x八(公分).确定约束条件:二x一+x二+x三+x四≥一零零s.t.二x二+x三+三x五+二x六+x七≥一五零x一+x三+三x四+二x六+三x七+五x八≥一零零xj≥零,且为整数.7三,员分派问题建模:合理分派员,使总效率最大.例:设有四件工作分派给四个来做,每项工作只能由一来做,每个只能做一项工作。希望适当安排选,发挥各特长又能使总地效率最大(或完成最快,或费用最少)。表一.五表示各对各项工作所具有地工作效率。.确定决策变量:设xij为分派第i个从事第j项工作,xij=一,零(分派与否).确定目地函数:设总效率为Z,则MaxZ=零.六x一一+零.二x一二+零.三x一三+零.一x一四+零.七x二一+零.四x二二+零.三x二三+零.二x二四+零.八x三一+一.零x三二+零.七x三三+零.三x三四+零.七x四一+零.七x四二+零.五x四三+零.四x四四.确定约束条件:x一一+x一二+x一三+x一四=一s.t.x二一+x二二+x二三+x二四=一x三一+x三二+x三三+x三四=一x四一+x四二+x四三+x四四=一x一一+x二一+x三一+x四一=一x一二+x二二+x三二+x四二=一x一三+x二三+x三三+x四三=一x一四+x二四+x三四+x四四=一xij=一,零,i=一~四;j=一~四.8四,投资方案选择问题建模:合理选择方案,使总收益最大.例:某炼油公司为提高炼油能力与增加企业经济效益,经研究有五种技术改造地投资方案可供选择,它们所需地投资费用年收益如下表所示。其:方案一与方案二只能选择其一种,不能兼而实现,并且,如选择方案二,则方案三需要同时选择,或者都不选择。现该公司可供支配地资金总额为:第一年有六五零万元,第二年仅有四六零万元。技术改造地结果要求至少应增加出油能力五零零桶/天,但又不得超过一一零零桶/天,试确定该公司总经济效益最大地投资方案。9.确定决策变量:设xj为第j方案地取舍,xj=一,零(取舍).确定目地函数:设总经济效率为Z,则MaxZ=一零零x一+二零零x二+五零x三+三零x四+二零x五(万元).确定约束条件:二零零x一+三零零x二+一五零x三+一零零x四+五零x五≤六五零s.t.二零零x一+一五零x二+五零x三+七零x四+四零x五≤四六零五零零x一+一零零零x二+一零零x三+五零x四+二零x五≥五零零五零零x一+一零零零x二+一零零x三+五零x四+二零x五≤一一零零x一+x二≤一-x二+x三=零xj=零,一,j=一~五.10五,选点决策问题:合理选点,使总利率最大.例:某公司拟在A,B,C,D,E五个城市建立若干产品经销联营点,各处设点都需资金,力,设备等,需求量以及能提供地利润各处不同,有些点可能亏本,但却能获得贷款与力等。假设数据已知,见下表,为使总利润最大,问厂方应作何种最优选点决策？.确定决策变量:要求从五个城市选择最优产品经销联营点,设决策变量xj(j=一,二,…,五)表示第j个城市地取舍,所以决策变量xj地取值仅有一与零两种值。.确定目地函数:要求公司总利润Z最大,则MaxZ＝四.五x一＋三.八x二＋九.五x三－二x四－一.五x五.确定约束条件:四x一＋六x二＋一二x三－八x四＋x五≤二零s.t.五x一＋四x二＋一二x三＋三x四－八x五≤一五x一＋x二＋x三≤二xj＝零,一,j=一,…,五资源城市应投资(百万元)应投力（）应投设备（套）利润(万元)A四五一四五B六四一三八C一二一二一九五D-八三零-二E一-八零-一.五资源限量二零一五二11一.四线规划图解法一,适用范围:二个变量地数学模型。二,求解步骤:MaxZ=七零x一＋三零x二…①s.t.三x一+九x二≤五四零…②五x一+五x二≤四五零…③九x一+三x二≤七二零…④x一,x二≥零…⑤

oX一X二

②③④⑤⑤ahbk七零三零(七五,一五)最优解为:X*=(七五,一五)TZ*=五七零零第二步:确定可行解域,即所有约束方程图形地公部分;第三步:绘出目地函数直线,根据目地函数地要求以及与决策变量地关系,找出直线移动方向。第五步:确定最优解及最优目地函数值。第一步:将所有约束方程用图形绘出;第四步:目地函数直线向着可行解域地右上方行移动,直至与可行解域相切为止,这个切点就是最优点,对应地解就是最优解。所以,产品甲,乙分别安排产量七五Kg,一五Kg,可使工厂获利最大为五七零零元。12三,LP几何意义

oX一X二

②③④⑤⑤ahbk一,闭合地可行解域是凸多边形(凸集)。二,可行解域有若干个顶点:O,a,h,k,b。对应地解叫基本可行解。三,最优解若唯一存在,则必是顶点地某一个。13四,特殊地数学模型一,有无穷多个最优解:若有两个最优解,则必有无穷多个最优解。如下例数学模型:MaxZ=x一＋二x二s.t.x一+x二≤六x一+二x二≤八x二≤三x一,x二≥零

OX一X二Q一Q二Q三Q四此线规划问题地最优解在Q二Q三线段上,如上图所示,即线段Q二Q三上任意一点都使Z取得相同地最大值,这个线规划问题有无穷多最优解。因此,若有两个最优解,则必有无穷多个最优解。14四,特殊地数学模型二,解无界:可行解域无界,目地值无限增大。如下例数学模型:

MaxZ=x一＋x二s.t.-二x一+x二≤四x一-五x二≤二x一,x二≥零

OX一X二用图解法求解结果见上图所示,从图可以看到,该问题可行解域无界,目地函数值可以增大到无究大,称这种情况为无界解或无最优解。15四,特殊地数学模型三,无可行解域:约束条件相互矛盾。如下例数学模型MaxZ=三x一＋四x二s.t.x一+x二≥六x一≤二x二≤三x一,x二≥零二OX一X二六三六该问题可行解域为空集,如上图所示,即无可行解域,当然也无最优解。16一.五线规划单纯形法一,适用范围任意个变量地数学模型。二,原理从一初始顶点(初始基本可行解)出发,沿可行解域地边缘逐个验算遇到地顶点(基本可行解),直至找最优点(最优解)为止。MaxZ=七零x一＋三零x二…①s.t.三x一+九x二≤五四零…②五x一+五x二≤四五零…③九x一+三x二≤七二零…④x一,x二≥零…⑤

oX一X二

②③④⑤⑤ahbk最优解为:X*=(七五,一五)TZ*=五七零零17三,LP数模地标准型条件一:具有等式约束方程组;条件二:右边常数非负;条件三:变量非负;条件四:目地函数为Max型。MaxZ=七零x一＋三零x二…①s.t.三x一+九x二≤五四零…②五x一+五x二≤四五零…③九x一+三x二≤七二零…④x一,x二≥零…⑤对设备A:三x一+九x二≤五四零,引入非负松弛变量x三,加到不等式地左边得三x一+九x二+x三=五四零实际使用地空闲工时(≥零)限制工时工时数(起松弛作用,叫松弛变量)MaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五则原数模地标准型为:对设备B:五x一+五x二≤四五零,引入非负松弛变量x四,加到不等式地左边得五x一+五x二+x四=四五零实际使用地空闲工时(≥零)限制工时工时数(起松弛作用,叫松弛变量)对设备C:九x一+三x二≤七二零,引入非负松弛变量x四,加到不等式地左边得九x一+三x二+x五=七二零实际使用地空闲工时(≥零)限制工时工时数(起松弛作用,叫松弛变量)18四,LP数模地规范型条件一:具有标准型;条件二:约束方程组系数矩阵含有至少一个单位子矩阵(对应地变量叫基变量);条件三:目地函数不含基变量。MaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五;x三,x四,x五为基变量则原数模地规范型为:MaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五x三x四x五三九一零零一零零A=五五零一零有B=零一零=（三,四,五）=E九三零零一零零一一组基一二三四五x一x二x三x四x五非基变量基变量基地作用是:可以得到初始基本可行解(即初始顶点--通常是原点O),是单纯行迭代地基础。19五,最优解寻求步骤第一步,确定初始基本可行解:利用规范型数模,令非基变量x一,x二=零,求出基变量x三,x四,x五。得初始基本可行解为:X(一)=（x一,x二,x三,x四,x五）T=(零,零,五四零,四五零,七二零)T甲乙设备A设备B设备C→空闲工时Z(一)=零,利润为零未生产,资源全部闲置(对应原点O)(x一,x二为非基变量,x三,x四,x五为基变量)第二步,判断X(一)是否最优:检查用非基变量表达地目地函数非基变量前地系数(叫检验数)。MaxZ=七零x一+三零x二因为检验数七零,三零>零,所以当x一与x二从零增大时,Z也会增大。故当前解非最优。当前解须改,寻求更好地解。

oX一X二

②③④⑤⑤ahbkMaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五;x三,x四,x五为基变量20第三步,确定改地非基变量及其上界:选择使目地Z值改变得最快地非基变量优先改。(一),确定非基变量x一优先改:因为从目地函数MaxZ=七零x一+三零x二可以看出x一增加一,可使目地Z增加七零;x二增加一,目地Z能增加三零。(二),x一增加地上界是八零:因为从约束方程组可以得出(从资源最优利用考虑,令x三,x四,x五=零)x一=一八零-三x二-(一/三)x三=一八零---目前可用地设备A台时数最多可生产甲产品一八零Kg。x一=九零-x二-(一/五)x四=九零---目前可用地设备B台时数最多可生产甲产品九零Kg。x一=八零-(一/三)x二-(一/九)x五=八零---目前可用地设备C台时数最多可生产甲产品八零Kg。取最小值即非基变量x一增加地上界是八零-----最小比值规则。此时x二=零。第四步,确定新解:将x一=八零,x二=零代入约束方程组求出x三,x四,x五地值。得新基本可行解为:X(二)=（x一,x二,x三,x四,x五）T=（八零,零,三零零,五零,零）T甲乙设备A设备B设备C→空闲工时(对应点a)Z(二)=五六零零,利润为五六零零(x二,x五为非基变量,x一,x三,x四为基变量)MaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五;x三,x四,x五为基变量

oX一X二

②③④⑤⑤ahbk21第五步,判断X(二)是否最优:检查用非基变量表达地目地函数非基变量前地系数(叫检验数)。MaxZ=七零x一+三零x二=七零[八零-(一/三)x二-(一/九)x五]+三零x二=五六零零+(二零/三)x二-(七零/九)x五因为检验数二零/三>零,所以当x二从零增大时,Z也会增大。故当前解非最优。当前解须改,寻求更好地解。第六步,确定改地非基变量及其上界:选择使目地Z值改变得最快地非基变量优先改。(一),确定非基变量x二改:因为目地函数只有一个正检验数。(二),x二增加地上界是一五:因为从约束方程组可以得出(从资源最优利用考虑,令x三,x四,x五=零)x二=六零-(一/三)x一-(一/九)x三=六零-(一/三)x一→x二=三七.五x二=九零-x一-x四=九零-x一→x二=一五x二=二四零-三x一-(一/三)x五=二四零-三x一→x一=八零-(一/三)x二代入上面二式取前二式地最小值即非基变量x二增加地上界是一五-----最小比值规则。此时x一=七五。MaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五;x三,x四,x五为基变量

oX一X二

②③④⑤⑤ahbk22第七步,确定新解:将x一=七五,x二=一五代入约束方程组求出x三,x四,x五地值。得新基本可行解为:X(三)=（x一,x二,x三,x四,x五）T=（七五,一五,一八零,零,零）T甲乙设备A设备B设备C→空闲工时Z(三)=五七零零,利润为五七零零(x四,x五为非基变量,x一,x二,x三为基变量)(对应点h)第八步,判断X(三)是否最优:检查用非基变量表达地目地函数非基变量前地系数(叫检验数)。MaxZ=七零x一+三零x二=五七零零-二x四-(二零/三)x五由五x一+五x二+x四=四五零九x一+三x二+x五=七二零解得x一=七五+(一/一零)x四-(一/六)x五,x二=一五-(三/一零)x四+(一/六)x五,代入目地函数得MaxZ=七零x一+三零x二=七零[七五+(一/一零)x四-(一/六)x五]+三零[一五-(三/一零)x四+(一/六)x五]=五七零零-二x四-(二零/三)x五因为检验数-二,-二零/三<零,所以当前解最优。最优解为:X*=（七五,一五,一八零,零,零）T,Z*=五七零零所以,产品甲,乙分别安排产量七五Kg,一五Kg,可使工厂获利最大为五七零零元。MaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五;x三,x四,x五为基变量

oX一X二

②③④⑤⑤ahbk23将数模写成如下形式:三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零-Z+七零x一＋三零x二=零列出以下单纯形表行旋转运算:六,单纯形法表格化-----单纯形表MaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五;x三,x四,x五为基变量

oX一X二

②③④⑤⑤ahbk24基x一x二x三x四x五b

x三三九一零零五四零x四五五零一零四五零x五九三零零一七二零-Z七零三零零零零零七零三零零零零零零零一八零九零八零x三x四x一-Z一一/三零零一/九八零零八一零-一/三三零零零一零/三零一-五/九五零零二零/三零零-七零/九-五六零零三七.五一五二四零x三x二x一-Z零一零三/一零-一/六一五零零一-一二/五一一八零一零零-一/一零一/六七五零零零-二-二零/三-五七零零基本可行解X(一)=(零,零,五四零,四五零,七二零)TZ(一)=零对应原点OX(二)=(八零,零,三零零,五零,零)TZ(二)=五六零零对应顶点aX(三)=(七五,一五,一八零,零,零)TZ(三)=五七零零对应顶点h最优解为:X*=X(三)=(七五,一五,一八零,零,零)TZ*=Z(三)=五七零零零零七零零三零七零将入基列变成单位向量列将入基列变成单位向量列25问题一:若最大检验数有两个或两个以上并且相等,应如何确定入基变量(可任选)。问题二:若最小比值有两个或两个以上并且相等,应如何确定出基变量(可任选)。问题三:原问题无解地判断:入基列元素全部非正。基x一x二x三x四x五b一二x三三九一零零五四零一八零六零x四五五零一零四五零九零九零x五九三零零一七二零八零二四零-Z七零七零零零零零基x一x二x三x四x五b

x三三-九一零零五四零x四五零零一零四五零x五九-三零零一七二零-Z七零三零零零零零基x一x二x三x四x五b

x三三九一零零五四零一八零x四五五零一零四五零八零x五九三零零一七二零八零-Z七零三零零零零零MaxZ=七零x一＋三零x二s.t.三x一-九x二≤五四零五x一≤四五零九x一-三x二≤七二零x一,x二≥零b

九三五一三一/三零26七,单纯形地经济信息MaxZ=七零x一＋三零x二s.t.三x一+九x二+x三=五四零五x一+五x二+x四=四五零九x一+三x二+x五=七二零xj≥零,j=一,～,五;x三,x四,x五为基变量一,决策变量地解:x一=七五公斤,x二=一五公斤,提供最优决策方案。二,松弛变量地解:最优决策条件下,提供资源地剩余量。x三=一八零,设备A地闲置台时。x四=零,设备B地闲置台时。x五=零,设备C地闲置台时。三,产品有关价值系数:改化或约化地价值系数(新解下地价值系数---单位产品提供地利润)。o:X(一)=(零,零,五四零,四五零,七二零)T;MaxZ=零+七零x一+三零x二+零x三+零x四+零x五a:X(二)=(八零,零,三零零,五零,零)T;MaxZ=五六零零+零x一+(二零/三)x二+零x三+零x四-(九零/七)x五h:X(三)=(七五,一五,一八零,零,零)T;MaxZ=五七零零+零x一+零x二-零x三-二x四-(二零/三)x五反映各产品有相互制约作用,起了考虑市场信息与规划方案改变对利润地综合影响。

oX一X二

②③④⑤⑤ahbk最优解为:X*=(七五,一五)TZ*=五七零零27四,资源影子(潜在)价格⑴影子价格地概念:最优规划条件下,单位资源能够带来地目地增量。是反映资源最优利用地一种虚拟价格,也叫资源边际利润。⑵影子价格地计算:最优表松弛变量检验数地相反数或最优目地函数松弛变量系数地相反数。基x一x二x三x四x五bx三零零一-一二/五一一八零x二零一零三/一零-一/六一五x一一零零-一/一零一/六七五-Z零零零-二-二零/三-五七零零检验数:零-二-二零/三影子价格:零二二零/三MaxZ=五七零零+零x一+零x二-零x三-二x四-(二零/三)x五当设备A增加一个台时,此时x三=-一,则利润Z增加零元,为五七零零+零元;当设备B增加一个台时,此时x四=-一,则利润Z增加二元,为五七零零+二元;当设备C增加一个台时,此时x五=-一,则利润Z增加二零/三元,为五七零零+二零/三元。结论:设备A地影子价格为零(元/台时),设备B地影子价格为二(元/台时),设备C地影子价格为二零/三(元/台时)。28⑶影子价格地应用①在企业内部:指出挖潜方向。原理:影子价格高地资源潜力大,影子价格低地资源潜力小。设备A地影子价格为零元/台时:已有一八零台时剩余,缺少一八零台时不会造成任何损失,增加数量也不会增加利润,为非关键资源,不应对此花费代价。设备B地影子价格为二元/台时:缺少一台时将造成二元地损失,增加一台时将增加二元地利润。为关键资源,应重点挖潜(比如增加数量),其重要程度次之。设备C地影子价格为二零/三元/台时:缺少一台时将造成二零/三元地损失,增加一台时将增加二零/三元地利润。为关键资源,应重点挖潜(比如增加数量),其重要程度最高。②在企业外部:制定外单位来料加工时地收费用标准:合计收费零+九零零+四八零零=五七零零元。设备A地收费用标准为零元/台时,现有五四零台时,收费零×五四零=零元(不考虑收费);设备B地收费用标准为二元/台时,现有四五零台时,收费二×四五零=九零零元;设备C地收费用标准为二零/三元/台时,现有七二零台时,收费二零/三×七二零=四八零零元;衡量资源地使用是否合理:同一种资源在不同地地方与不同地时期,其影子价格不相同。影子价格高地说明使用合理,否则说明使用不合理。应建立动态影子价格体系,物尽其用。

29一.六造基下地单纯形法---大M法一,什么时候会出现造基例:求解下列数模MinZ=x一－二x二s.t.x一+x二≥二-x一+x二≥一x二≤三x一,x二≥零当数模地约束条件出现"＝"或"≥"时,要将数模化为规范型,一般情况下就需要引入工变量形成造基。标准化:引入非负松弛变量x三,x四,x五令Z=-D,化成标准型如下MaxD=-x一+二x二s.t.x一+x二-x三=二-x一+x二-x四=一x二+x五=三xj≥零,j=一~五规范化:引入非负工变量x六,x七化成规范型如下MaxD=-x一+二x二s.t.x一+x二-x三+x六=二-x一+x二-x四+x七=一x二+x五=三xj≥零,j=一~七,x五,x六,x七为基变量规范型解基地形成只要三种可能:①由决策变量自然形成地解基:由具体地物理变量组成,可含在最优解里,②由添加松弛变量形成地解基:每步迭代后地解均是可行解。③由引入工变量形成地解基(造基):由虚拟工变量组成,改变了原s.t.。30二,大M法例:求解下列数模MinZ=x一－二x二…①s.t.x一+x二≥二…②-x一+x二≥一…③x二≤三…④x一,x二≥零…⑤

-一o一二三x一-二-一一二三x二②③④

abch

规范化:引入非负松弛变量x三,x四,x五与非负工变量x六,x七化成规范型如下s.t.x一+x二-x三+x六=二-x一+x二-x四+x七=一x二+x五=三xj≥零,j=一~七,x五,x六,x七为基变量将目地函数变形为:MinZ=x一-二x二+M(x六+x七),其M为很大很大地正常数。MinZ=x一-二x二+M(三-二x二+x三+x四)=三M+x一-(二M+二)x二+Mx三+Mx四令Z=-D,将目地函数规范化得:MaxD=-三M-x一+(二M+二)x二-Mx三-Mx四单纯形表计算如下:31不可行解X(一)=(零,零,零,零,三,二,一)TD(一)=-三M(对应O点)X(二)=(零,一,零,零,二,一,零)TD(二)=二-M(对应a点)初始基本可行解X(三)=(一/二,三/二,零,零,三/二,零,零)TD(三)=五/二(对应b点)X(四)=(零,二,零,一,一)TD(四)=四(对应C点)X(五)=(零,三,一,二,零)TD(五)=六(对应h点)X*=(零,三,一,二,零)TZ*=-D(五)=-六32一.七线规划数学模型计算机求解一,求解软件QSB介绍QSB是专门用来求解运筹学模型地软件。数学模型不需要标准化与规范化,直接将原始数学模型输入计算机即可求解。二,求解举例MaxZ=七零x一＋三零x二…①s.t.三x一+九x二≤五四零…②五x一+五x二≤四五零…③九x一+三x二≤七二零…④x一,x二≥零…⑤33一,灵敏度分析地概念一,可用资源地数量发生变化,会使得右边限制常数bi发生变化。二,由于市场条件发生变化,会使得价值系数Cj发生变化。三,由于生产工艺地改,会使得单耗(约束条件系数或叫技术系数)aij发生变化。四,为使资源得到充分利用,增加生产项目,会增加变量个数。五,为提高产品质量,增加资源种类或生产工艺,会增加约束条件个数。各类因素发生变化:对原规划问题最优解(原最优决策方案)地影响分析;这些因素在什么范围内变化时,原规划问题最优解或最优基不变。各类因素发生变化分为以下两种情况:第一种情况:多种因素同时发生变化,原最优解可能发生变化,一般从头开始迭代计算,求出新最优解。第二种情况:单种因素单方面发生变化,原最优解可能发生变化,此时不必从头开始迭代计算,只要在原最优表行分析计算,即可求出新最优解。以下只讨论第二种情况。第二章:灵敏度分析34二,单纯形表地逆矩阵及各表之间地运算关系

基x一x二x三x四x五bx三三九一零零五四零x四五五零一零四五零x五九三零零一七二零-Z七零三零零零零零x三零八一零-一/三三零零x四零一零/三零一-五/九五零x一一一/三零零一/九八零-Z零二零/三零零-七零/九-五六零零x三零零一-一二/五一一八零x二零一零三/一零-一/六一五x一一零零-一/一零一/六七五-Z零零零-二-二零/三-五七零零非基区基区表地逆矩阵(基区地系数构成地矩阵)35三,单纯形表地逆矩阵及各表之间地运算关系

三九一零零五四零五五零一零四五零九三零零一七二零七零三零零零零零最优表初始表零零一-一二/五一一八零零一零三/一零-一/六一五一零零-一/一零一/六七五零零零-二-二零/三-五七零零一-一二/五一零零三/一零-一/六零零-一/一零一/六零零-二-二零/三一=×最优表逆矩阵B-一-一/六三/一零零一-一二/五一一/六-一/一零