论文研究- 线性规划最优解后的决策.pdf

所需积分/C币:10 2019-09-20 14:56:18 489KB .PDF
收藏 收藏
举报

论文研究- 线性规划最优解后的决策.pdf,  本文介绍资源的最佳分配;资源上、下限的决定;创利额变化对最优解的影响;增加新产品的决策;对排斥在最优解以外产品的分析以及几个参数同时变化的决策方法。为管理分析人员在取得最优解后,进一步决策时,提供简单可行的方法。
42 系统工程理论与实践 1986年3月 公司共有甲原料460斤、乙原料740斤。A工厂分到甲原料200斤,乙原料400斤; B工厂分到甲原料260斤,乙原料340斤。A工厂的数学模型和最优表如表4所示。 表4 数学模型maxS1=4X1+5X2 10X1+3X2≤2008X1+12X2≤400;X1,X2≥0 最优表 基变量列X X 常数项b; X1 100 32 8 X 5 19 判别行 S1-175 12 48 由表4可知,A工厂最佳生产方案为:X1=12.5,X2=25。其利润S1=175元。甲 原料的影子价格W1=1乙原料的影子价格2÷19 48 同理,列出B工厂的数学模型和最优表(表5)。 表5 数学模型axS2=5Xs+4X4 4X3+10X4≤260312X3+6X4≤340;X3,X4≥0 最优表 基变量列X; X 3 X4 常数项b 2 X 15 16 48 判别行 1015 48 6 由表5可知,B工厂最佳生产方案为:X。=150,X=3°其利润S2=105 用 原料的影子价格Ⅳ2=3,乙原料的影子价格W,=1。公司总利润为:S=S1+S2 344.17元。由上述结果可以看出W1<W;W2>形4说明这两种原料的使用尚有不合 理的地方。若将A工厂的甲原料减少,而增加给B工厂;将B工厂的乙原料减少,而增 加给A工厂。将使甲、乙原料得到较合理的应用,从而使公司总利润增加。比如将A工 厂的甲原料减少40斤,增加给B工厂;将B工厂的乙原料减少40斤,增加给A工厂, 此时,无需重新用单纯形法求解。直接根据影子价格的含义求出。对A工厂, 0 12+40×19 1 12.5元;对B工厂,40 17 6+(-40) 48 6.67元。此时,公 48 司总利润比原来增加5.83元(=12.5-6.67)。 第1期 线性规划最优解后的决策 43 既然公司可以依据资源在各厂的影子价格对各厂资源数量进行调整y当然局可以依 据资源在各公司的影子价格对各个公司的资源进行调整;……直至中央可以依据资源在 各个省(或部)的影子价格对各个省(或部)的资源进行调整。经过这样上下的反复调 整,从而获得资源的最佳分配。 资源上、下限的决定 资源数量的增(或减)不超过某一界限,影子价格将保持不变,如超过这一界限, 影子价格就发生突变。据此计算出资源数量变化的上限和下限具有较大的实用意义。此 问题仍可在最优表上获得解决。现在用例1说明之。从例1最优表(见表2)可知,变 量x表示乙机床工作时数的松弛时间量。当X8的值为1,相当于把可用的乙机床工作时 间减少一个单位,这将使目标函数值减少20元。这样资源b2的一个单位必须有20元的 价值。根据同样的推理,资源b的一个单位的价值为14元,资源b4的一个单位的价值 为-。元,资源b1的一个单位的价值为零元。我们研究在20元发生变化之前,能加上 (或减去)多少附加单位。我们用最优表的“常数项”列内的元素除以调入过程列 (即X8列)内的对应元素的比值。比值如下(见表2) 150÷(-0.5)=一300335000÷50=700;5000÷0=不确定;3000*0=不确 定。最小正比值(即当有几个正比值取最小的)为700。而乙机床的最大工作时间为 700,所以资源有效性一直降到零小时,资源的价值都是有效的。最大负比值(即 当有几个负比值取最接近于零的数)为-300。这样影子价格20的可用性区域是0至 1000,即(700-700至(700+300。将四种资源数量变化的上、下限列于表6。 表6 变化极限 区域极限 资 源 最大工作时间影子价格 低 高 低 高 甲机床 850 无 乙机床 700 20 700 1000 丙机床 100 14 100 300 0 400 丁机床 32 450 1350 对于W1=0的情况,有上限为无穷大。即当W1=0时,甲机床工作时间已有剩余。 因此,对资源b的数量无论再增加多少都不会改变资源b的影子价格。我们所计算的资源 数量变化的上限和下限,是指调整第讠种资源数量时,其它资源数量均保持不变的情况。 、创利额变化对最优解的影响 当外界条件变化,使创利额发生改变。对最优解有什么影响呢?如例2,3的目标 系数为5,如能知道这个数值增加多少或减少多少才使最优解发生变化,将对企业经营 分析有帮助。从理论上可将上述问题归结为:已求得线性规划问题 系统工程理论与实践 1986年8月 maxs=CX s,t.AX=byX≥0 的最优解。求保持最优解不变,C的变化范围。当C没有变化时,基变量X;的判别数 b;=C;=CnB1P;=0。当C变化了△C;时,引起了C发生△C的变化。 (Cn△C)B=CB1+△CB=CB+(0,…,0,ΔC,0,0,…,0)B1 =CaB2+△C(b1+b2+…+bm) 发生变化后的判别数为:by′=C;-CBp;-△C·b;=by-△C;b,(j=1, 2,…,n)。若要求原最优解不变,必须b′=bo-△Cb≤0。得 △C≥ 当b;>0;△C;≤ 当b<0 b;是基变量x:在最优表中所在行的各系数值(j=1,2,…,n)。C的变化范围为: max b>0≤ΔC;≤min{-jb<0 可在最优表上用判别行上的每一个元素除以行内的对应元素获得。 见例2的最优表(表5)。对X3系数有 17 16 3 48 48 3.4。即△C3的变化范围是:-3.4≤ΔC≤3。即X的系数C3=5在(1.6,8〕之间 变化,不影响原最优解。 四、增加新产品的决策 对偶规划对于管理分析人员评价新生产过程是非常有用的。例1(表2)的对偶规 划数学模型为: minZ=850y1+700y2+100y+900y4 s.t.0.01y1+0.02y2≥0.4; 0.01y1+0.02V≥0.28 0.01y1+0.03y4≥0.32 0.03y+0.05y2≥0.72 0.03y:+0.05y3≥0,6 0.03y1+0.08y:≥0.6 y;≥0(讠=1,2,3,4) 例如工厂要生产一种新产品G,G在乙、丙机床上加工,工时分别为0.01和0.02。 生产一个单位的G产品能提供利润0.4元。是否生产G产品?我们把这个新过程加到原 问题内,把0.01y2+002y≥0.40加到对偶问题内(其中y2、y为乙、丙机床…个单 位工作时间的价值,分别为20元、14元)。把y2、y代入得:0.01×20+0.02×14≥ 0.4030.48>0.40。不违反约束条件,投入生产新产品G无利可图。 五、对排斥在最优解以外产品的分析 在例2的最优表(表2)中,X4=X=X=0说明不生产D、E、F产品。提高价 格或降低工时可以改变这种状态。生产F产品价格应该提高多少?X的有关对偶约束条 件为:0.03y1+0.08y4≥0.60+h,h代表价格的变化。把y1、y值代入求得 第1期 线性规划最优解后的决策 45 32 0.03×0+0.08× -≥0.60+h;0.853≥0.60+h。为了违反约束条件,h>0.253 元。这样ⅹ即F产品)进入最优解。 使F产品进入最优解的第二个可能性是减少J机床加工工时。有关对偶约束条件为: 0.03y1+(0.08-K)y4≥0.60,其中K代表机床加工工时的变化。代入y1、y值求得:0.03 0+(0.08-K)x、32 ≥0.60。K>0.02375工时,则违反约束条件,进入最优解 六、几个系数问时变化的决策 以上讨论了取得最优解后,单个系数变化时的决策。如果几个系数(甚至是不同类 型的几个系数)同时变化时,如何决策?通过综合例题(兼作为单参数问题的举例)加以 说明。 已知某工厂计划生产I、I、I三种产品,各产品需要在A、B、C设备上加工, 有关数据如表7所示。 表7 I 设备每月的有效台时 10 300 B 10 400 C 13 10 420 单位产品利润(千元) 3 2.9 试回答:(1)使生产总的盈利最大;(2)为了增加产量借用B设备60台时,租金18 万元,经济上是否合算?(3)若有新产品Ⅳ、V,Ⅳ需用设备A-12台时,B一5台 时,C-10台时,单位产品盈利为2.1千元;V需用设备A-4台时,B-4台时,C 12台时,单位产品盈利1.87千元。这两种新产品投产在经济上是否合算?(4)改进产 品工艺与结构后,生产每件I产品,需用设备A-9台时,B-12台时,C一4台 时,单位产品盈利4.5千元,问对原计划有何影响? 解:(1)数学模型及最优表(见表8) 表8 数学模型m&xS=3X1+2X2+2.9X s. t 8X1+2X2+10X3≤300;10X1+5Y2+8X3≤400 2X1+13X2+10X3≤120;X1,X2,X3≥0 最优表 基变量列 常数项列b X 338 300 X2 7 116 50 10 50 5 X3 5 30 判别行 3 2029 15 46 系统工程理论与实践 1986年3月 (2)由最优表得知:B设备工作时间的影子价格2=1千元。故借用B设备60 合时,可增加利润16万(=0×X15千元)现租金18万元,故不合第。 (3)列出对偶规划的数学模型 mind=300y1+400y2+生20 s.t.8y+10y2+2y≥3;2y1+5y2+13y3≥23 10y1+81y2+10y≥29;y1,y2,y≥0 其中y1、y2ys为A、B、C设备一个单位工作时间的价值,分别为 100 干元、4 15 千 兀、150 千元 Ⅳ产品:12y1+5y2+10y≥2.1,12×3+5X4+10×、7=2.16>2.1不 100 150 违反约束条件,投入产品Ⅳ,经济上不合算。 V产品:4y+4y2+12y≥187,A*100+4、4+12X1501.75<1.87违 3 反约束条件,投入产品V,经济上合算。 (4)设改进的I产品为I′。首先计算X的列向量: Q 1 17 349 10060300 9 300 50 30 相应地计算x的判别数 1-CBBp1=4.5 3 12 253 100’15’150 300 力是I′的系数列向量。 因产品I′是产品I的改进。因此,可以利用原最优表,即将上面算出的x的列向 量数字和判别数填入原最优表的X1的列向量位置处。得表9 表 基变量列X Xi X X Z2 常数项列b; 360 1 3035 X2 501b 1 15 5 6 30 判别行 253 2029 300 100 150 15 第1期 线性规划最优解后的决策 47 因为换入的X是基变量,所以应当将X1的系数向量重新变换为单位列向量。得 表10 表10 基变量列XX1 X2 2 Z 2 Z 常数项列b Xi 27 55 17 6760 349 349 349 349 220 34400 1745 1745 1745 1745 340 45150 1745 2094 10470 5235 41835 S-158727 3490 10470 104700 1047 判别数还有正数,需再换基迭代。得表11。 表11 基变量列XXi X Z1 常数项列b; X11 13611 5235 270475 68 142392 142392 11866 X2 -5235 15727 150070 177990 177990 5933 1745 -1635 1575 1505 340 2040 10200 123 2643675392625 680 7119600355980000 355980 判别数均为非正数,得最优表。最佳生产方案为 1161=150010,I=0。获利润为:S=4,5、270475 270475 5933 11866+2 150070 十2.9×0 54522525 5933 355980=153.16千元。 这种计算方法的理论依据是:当我们取得最优解以后,如某些系数发生变化时,只 需要利用CB1、CBBP及B1计算出最优表上的相应的修正数字。把这些修正数字填 到最优表相应的位置,继续换基迭代,直到再取得最优解为止。 参考文獸 1〕胡幼青:影子价格问题介绍,《价格理论与实践》,1981年,第5期。 〔2〕刘涌康:线性规划,《上海企业》,1983年,第1期。 〔3〕《运筹学》试用教材编写组编:《运筹学》,清华大学出版社,1982年。 〔4〕〔美〕F.S.麦克劳林、R.C.皮克哈德著:《管理决策的定量技术》,中国铁道出版社,1982年。 5〕叶若春:《线型规划理论与应用》(增订版),中兴管理顾问公司发行,1980年。 f6〕许宏佩:影子价格的应用,《华东工学院学报》,总第29期,1984年。

...展开详情
试读 8P 论文研究- 线性规划最优解后的决策.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744207 你的留言是对我莫大的支持
    2019-09-20
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究- 线性规划最优解后的决策.pdf 10积分/C币 立即下载
    1/8
    论文研究- 线性规划最优解后的决策.pdf第1页
    论文研究- 线性规划最优解后的决策.pdf第2页
    论文研究- 线性规划最优解后的决策.pdf第3页

    试读已结束,剩余5页未读...

    10积分/C币 立即下载 >