运筹学经典案例

农场管理一、背景介绍•普拉夫家族拥有并经营着一家世代相传的640亩的农场，他们必须在农场上辛苦地工作才能维持生活和度过难关。这个家族的相当一部分历史是先辈们如何与洪水、旱灾和其他灾害作斗争的历史。但是，这个家族的成员很满意这种自力更生的生活方式。•普拉夫家族的农场，主要从事种植农作物和饲养牲畜的工作。但是农场的设备及相关科学技术没有及时更新。•现在，这个家族正经历了一次大丰收，场主面临着在现有条件下，如何分配有限的现金和劳动力使明年年底能够拥有最多的现金的问题。摘要•利用整数规划方法解决了场主在现有条件下，如何分配有限的现金和劳动力使明年年底能够拥有最多的现金的问题。得出结论：•1.在明年种植414亩大豆，42亩玉米，100亩小麦；饲养42头牛，2000只鸡可获得最大货币资产102811.0美元。•2.通过分情况讨论，发现不管天气情况如何，购买尽可能多的牛能赚更多的钱。所以普拉夫家族应该购买牛至42头(最大容量)；至于作物的种植量，普拉夫家族可以先去咨询当地的气象站再根据实际情况作出决定，当得知未来可能发生某种灾害天气时，就可以参考分析结果，进行资金和劳动力的分配；如果未来的天气情况无法预测，为了尽可能减少未来可能存在的损失，普拉发家族应该走一个稳健的种植路线：种植更多小麦，同时也可以购进一些鸡。•3.使用lingo做敏感性分析之后可以看出资金的影子价格为0，因此不需要贷款。理论综述•关键字：线性规划影子价格资源配置Lingo软件•名词解释：•线性规划：指研究线性约束条件下线性目标函数的极值问题的数学理论与方法。即对于统筹规划问题，为如何合理地、有效地利用现有有限的人力、物力、财力资源来完成更多的任务。或者如何才能以最少的代价去实现目标。作出的最优决策，提供科学的依据。采用数学语言来描述：问题的目标用变量函数的形式来表达（称为目标函数），问题的限制条件用有关变量的等式或不等式来表达。（称为约束条件）当变量连续取值，且目标函数与约束条件均线性时，称这类模型为线性规划模型。•影子价格：影子价格的含义就是资源单位增加量对最优值的贡献大小，实际问题中资源的增加最坏也就是对最优解没有贡献（相当于不用增加部分的资源），不会出现负影响。•前人研究：线性规划的发展•法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。•1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。•1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。•1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获得1975年诺贝尔经济学奖。•50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。•线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。•1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。•1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。•参考文献：杨桂元宋马林运筹与管理2010年第05期，张建中，徐绍吉.线性规划.北京：科学出版社，1990，ISBN：7-03-001833-8有关普拉夫家族的相关数据•劳动力提供：冬春两季可提供4000个人工秋；夏两季可提供4500个人工。可以利用富余劳动力赚取外快；冬、春季每小时5美元，夏、秋季节每小时5.5美元；•土地提供：640亩•种植三种农作物的每亩地的相关数据：大豆玉米小麦冬春季节（人工数）1.00.90.6夏秋季节（人工数）1.41.20.7净值（美元）706040•现有资产：鸡2000只，总价值$5000；牛30头，总价值$35000•牛每头1500元，鸡每只3美元。一年之后，每头牛会增值10%，而鸡由于老化会贬值25%。每头牛需要有两亩地的草，以及每月10个人工，每年可净收入现金850美元。一只鸡每月0.05个人工，每年净收入4.25美元。最多可饲养5000只鸡和42头牛。•另外为了给牲畜提供足够的饲料，约翰决定下一年为每头牛种植至少一亩的玉米，而为每只鸡种植至少0.05亩的小麦。问题：现在，这个家族正经历了一次大丰收，拥有了20000美元可用于购买更多的牲畜（其他的一些现金将会用于将来的开支，包括农作物的种植；约翰、尤妮斯和父亲现在正在讨论每年应该种植多少农作物以及饲养多少头牛和多少只鸡。他们讨论的目的是为了明年年底能够拥有最多的现金（牲畜的收入加上农作物的收入加上原有的货币资产加上年底所拥有的牲畜的价值减去明年40000美元的生活费）。1.要如何分配有限的现金和劳动力使明年年底能够拥有最多的现金•上面每年农作物的净值是在假设气候良好的条件下得出的。如果气候不好的话，会严重影响农作物的收成。他们最担心的自然灾害是旱、涝、早霜及干旱和早霜、涝灾和早霜一起来。在这些情况下，估计净值如下表所示。气候条件每亩净值大豆玉米小麦旱涝早霜干旱和早霜涝灾和早霜-101550-1510-152040-201001030-1052.针对上面每种情况估计明年年底该家族拥有的货币资产。如果同时有两种情况发生，该家族的货币资产会有何种变化？该家族应如何决定才能最有效的平衡气候良好条件下的好收成和气候不好条件下的坏收成。父亲对往年的气候做了一番研究，并得到了下面的一些数据。气候条件概率（%）好天气旱涝早霜干旱和早霜涝灾和早霜402010151053.基于这些数据，该家族决定作出如下的牲畜和种植决策。不再假设良好的气候条件会持续下去，而是按照上表的概率计算净收入在所有情况下的平均值。针对上述情况，对前面的分析作出调整。并考虑如果该家族能够获得应行贷款进而扩大牲畜饲养规模的话，贷款利率应该控制在多少？并需要对各项参数的敏感程度进行分析，指出有哪些数据需要进一步的估计。问题分析•普拉夫家族每年可提供的劳动力是有限的。简单来说，在这个案例中，普拉夫家族可提供劳动力做三种工作：•1.种植农作物；•2.饲养牲畜；•3.充分利用富余劳动力到别的需要劳动力的农场赚取外快案例中需要解决的问题实质上是把有限的劳动力进行最合理的分配以谋求最大的经济效益。•为了解决问题，首先得明确变量之间的对应关系，然后通过各个变量之间的关系列出目标函数方程并求解解决方案•问题1.根据案例分析，我们组对于所述情况进行了讨论，确定了建模思路大致为：•剩余现金=作物卖出（减去饲养消耗）+牲畜生产产生价值+牲畜价值（增值贬值）+富余劳动力产生的外快+20000(已有现金)-购买消费-40000(明年生活开支)•模型如下：•设明年种植大豆x1亩，玉米x2亩，小麦x3亩；饲养牛x4只，饲养鸡x5只•得到原方程：•MaxZ=70x1+60(x2-x4)+40(x3-0.05x5)+850x4+4.25x5+[35000+1500(x4-30)]110%+[5000+3(x5-2000)]75%+5(4000-x1-0.9x2-0.6x3-6x10x4-6x0.05x5)+5.5(4500-1.4x1-1.2x2-0.7x3-6x10x4-6x0.05x5)[phone](x4-30)-3(x5-2000)-40000•x1+x2+x3+2x4≤640;•x4≤42;•x5≤5000;•x4≤x2;•0.05x5≤x3;•X4=30;•x5=2000•1500(x4-30)+3(x5-2000)≤20000;•x1,x2,x3,x4,x5≥0•用lingo进行求解•在lingo输入界面输入•Max=70*x1+60*(x2-x4)+40*(x3-0.05*x5)+850*x4+4.25*x5+(35000+1500*(x4-30))*1.1+(5000+3*(x5-2000))*0.75+5*(4000-x1-0.9*x2-0.6*x3-6*10*x4-6*0.05*x5)+5.5*(4500-1.4*x1-1.2*x2-0.7*x3-6*10*x4-6*0.05*x5)[phone]*(x4-30)-3*(x5-2000)-40000;•x1+x2+x3+2*x4=640;•x4=42;•x5=5000;•x4=30;•x5=2000;•x4=x2;•0.05*x5=x3;•1500*(x4-30)+3*(x5-2000)=20000;•@gin(x1);•@gin(x2);•@gin(x3);•@gin(x4);•@gin(x5);•经过计算得出最优解为X*=(414,42,100,42,2000)；目标函数最大值Z*=102811.0•即在明年种植414亩大豆，42亩玉米，100亩小麦；饲养42头牛，2000只鸡可获得最大货币资产102811.0美元•问题2.五种气候条件分析，以旱为例：•在旱灾情况下，各种农作物的净值发生了变化，大豆变为-10，玉米-15，小麦0。•设x1,x2,x3,x4,x5分别为大豆种植量、玉米种植量、小麦种植量、饲养牛数、饲养鸡数，则根据牲畜的收入加上农作物的收入加上原有的货币资产加上年底所拥有的牲畜的价值减去明年40000美元的生活费得到的目标函数为：•MaxZ=-10x1-15(x2-x4)+0(x3-0.05x5)+850x4+4.25x5+[35000+1500(x4-30)]110%+[5000+3(x5-2000)]75%+5(4000-x1-0.9x2-0.6x3-6x10x4-6x0.05x5)+5.5(4500-1.4x1-1.2x2-0.7x3-6x10x4-6x0.05x5)[phone](x4-30)-3(x5-2000)-40000••x1+x2+x3+2x4≤640;•x4≤42;•x5≤5000;•x4≤x2;•0.05x5≤x3;•1500(x4-30)+3(x5-2000)≤20000;•x4=30;•X5=2000;•x1,x2,x3,x4,x5≥0•用lingo进行求解•在lingo输入界面输入•Max=-10*x1-15*(x2-x4)+850*x4+4.25*x5+(35000+1500*(x4-30))*1.1+(5000+3*(x5-2000))*0.75+5*(4000-x1-0.9*x2-0.6*x3-6*10*x4-6*0.05*x5)+5.5*(4500-1.4*x1-1.2*x2-0.7*x3-6*10*x4-6*0.05*x5)[phone]*(x4-30)-3*(x5-2000)-40000;•x1+x2+x3+2*x4=640;•x4=42;•x5=5000;•x4=30;•x5=2000;•x4=x2;•0.05*x5=x3;•1500*(x4-30)+3*(x5-2000)=20000;•@gin(x1);•@gin(x2);•@gin(x3);•@gin(x4);•@gin(x5);•经过计算得出最优解为X*=(0,42,133,42,2660)；目标函数最大值Z*=79093.75•即在干旱的情况下，明年不种植大豆，种植42亩玉米，133亩小麦；饲养42头牛，2660只鸡可获得最大货币资产79093.75美元，其他天气情况计算过程雷同•经过计算，得出：•晴天：种植414亩大豆，4