南京-应用运筹学-线性规划.ppt

南京大学周晶教授jzhou,运筹学,问题？,什么是运筹学？为什么要学习运筹学？要学习哪些内容？,什么是运筹学？,运筹帷幄，决策千里作为一门学科诞生于20世纪30年代末期。运筹学一词在英国称为operationalresearch，在美国称为operationsresearch，缩写为O.R.。在大英百科全书中，“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌握这类系统的人提供决策目标和数量分析的工具”。,朴素的运筹思想都江堰水利工程战国时期（大约公元前250年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。追求的效益还有防洪与航运。其总体构思是系统思想的杰出运用。,丁谓的皇宫修复工程北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物的处理用“一沟三用”巧妙地解决了。,田忌赛马齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：齐王上中下田忌下上中最终净胜一局，赢得1000金。,运筹学的三大来源,军事运筹帷幄、决策千里第二次世界大战经济莱昂惕夫的投入产出模型管理著名经济学家西蒙有一句名言：“管理就是决策”,鲍德西（Bawdsey）雷达站的研究（1935年）1935年，英国科学家R.Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。当时，德国已拥有一支强大的空军，起飞17分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。,1939年由曼彻斯特大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖金的P.M.S.Blackett为首，组织了一个小组，代号“Blackett马戏团”。这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官、一名测量员。,研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“OperationalResearch”，即“运筹学”。,大西洋反潜战（1942年）1942年，美国大西洋舰队反潜战官员W.D.Baker舰长请求成立反潜战运筹组，麻省理工学院的物理学家P.W.Morse被请来担任计划与监督。Morse出色的工作之一，是协助英国打破了德国对英吉利海峡的封锁。,1941-1942年，德国潜艇严密封锁了英吉利海峡，企图切断英国的“生命线”。海军几次反封锁，均不成功。应英国要求，美国派Morse率领一个小组去协助。Morse经过多方实地考察，最后提出了两条重要建议：,将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍)运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（25%下降到10%）,管理与运筹学,泰勒的科学管理方法对工人提出科学的操作方法（时间动作研究）对工人进行科学的选择、培训和提高（能力与工作相适应）制定科学的工艺流程，并以文件的形式加以固定和推广（工作定额与标准化）使管理和劳动相分离（计划与执行分离）在工资制度上实行差别计件制（差别计件付酬制）,各种管理科学学派,科学管理原理社会技术系统学派行为科学学派人际关系行为学派管理过程学派社会合作系统学派决策理论学派沟通信息学派管理科学学派经验案例学派数理学派系统管理学派经理角色学派群体行为学派战略管理创新管理知识管理,决策制定主体（管理者）,管理者的多重角色,-认可并奖励业绩-不断完善个人管理技能-给予指导建议-不断提出反馈-员工发展,-构建有效团队-倾听-调解冲突,-设定富于挑战但可以达到的业绩标准-提供及时精确的信息-控制质量,-倡导变化,-影响高层领导的决策-争取资源实现团队目标,-实现经营目标-满足客户的需要,-明确阐述目标-全盘考虑,-计划资源的合理利用,灵活性,控制,公司外部的重点,公司内部的重点,$,教练员创新者,促导者经纪人,监理者生产者,协调员指挥者,激励适应,政策目标,决策制定决策环境,不确定性程度：确定、风险、不确定可重复性程度：程序、非程序人员参与程度：个体、群体主体价值判断：最优、满意、合理,决策制定决策过程,识别问题,方案执行,观察,方案选择,方案评价,备择方案,理解问题,设定目标,解决问题周期,反馈,典型的定量决策问题,装箱问题,已知：两种货物装葙每种货物装葙利润体积限制重量限制问题:两种货物各多少箱?可使获得利润最大？(箱数不能为分数),OR航空公司的问题,该公司要在郊区商业中心内设一个订票服务处。旅客订票时可以用电话与服务处联系。OR公司想知道，为了满足订票业务的需要，应该安装多少条电话线路为宜。显然，电话机和雇员的费用随电话线路的增设而变化。该公司希望对若干条不同线路方案的服务水平加以对比。尤其是公司要设法确定所有线路被占用的时间百分比，以及占先的平均时间长度。,经济的定货量问题,萨拇.塔龙是某闹市区的一家工装裤零售店的主人，他对于尺码短缺的裤子应该进多少货常常感到为难。他决定采用科学的方法来补充库存，以避免因存货短缺而脱销。先假定他出售某种特殊尺码裤子的销售量每周为M件，为简便起见，还假定这个销售是固定的。那么如果库存量为kM件，则库存恰好在k周内售完。又假设M在整个时期内是不变的，因而是补充定货可以定期进行。要决策的问题是确定最经济的定货量。,A2,B7,C20,D12,1,2,3,4,0,2,2,9,2,22,9,21,0,2,3,10,10,22,2,22,网络计划,白色表示作业长度tij，红色表示最早TES和TEF，绿色表示最迟TLS和TLF,秘书问题,瓦特.威洛比是一家从事经济分析和预测的咨询公司.这家公司的总经理凯.塞拉女士想雇佣一位新的事务秘书,正大算请职业介绍所推荐适当的人选同他会面。根据过去的经验，她自信能凭面谈即可断定求职者在受雇后的表现是极好的、好的、还是一般的。她给三种人以相应的分数：极好的为3分，好的为2分，一般为1分。一往的经验还使她相信，会见极好的候选人的概率为0.2，会见好的候选人的概率为0.5，而会见一般的候选人的概率为0.3。,定量分析的过程,定性分析定量分析的前奏应当是一个彻底的定性分析表达问题列出表达问题的基本要素：决策变量、不可控量、限制条件等；建立模型列出表达这些要素之间关系的数学方程式求解模型与分析运用算法求解所构建的模型得到最佳方案或满意方案对输入数据和模型结构作灵敏度分析执行决定或修改模型在实际应用过程中不断完善模型,定量分析的工具模型,模型：把需要解决的决策问题，通过分析其外部影响因素和内部的条件变量，用一个逻辑的或数学的表达式，从整体上说明它们之间的结构关系。代表一种现实情况经过简化只保留相关的部分用模型的特性代表现实情况中的特性P=N(S-C)利润销售量（价格单位成本）,建立模型的重要性,建立模型是运筹学方法的精髓建立模型有助于我们把决策问题所遇到的复杂性和可能的不确定性，转变为适于综合分析的逻辑结构；模型是一种媒介，借以对现实世界作出正确的认识。模型是现实的近似表达，要能抓住决策问题的关键，在真实性和可用性之间取得适当的平衡。,典型的定量分析模型,定量分析的特点,定量分析：管理问题的理性描述和最优解分析方法：数学的、概率的和统计的方法定量优势：可靠数据为依据保证结果客观定量局限：实际问题无法完全地理性描述方法改进：数据分析与经验判断有机结合,运筹学的定义,定义1：为决策机构在对其控制下业务活动进行决策时，提供以定量化为基础的科学方法。定义2：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。定义3:运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。,运筹学的研究对象,机器、设备、网络、乃至系统的运用问题，即如何提高运作效率；拥挤现象：交通路口的车辆排队、服务热线、飞机着陆、船舶进港、网络；竞争现象：人与自然的对抗、人与人的对抗；,运筹学的重要分支,运用分析理论数学规划（又包含线性规划、非线性规划、整数规划、目标规划、动态规划等）图与网络流随机服务系统理论排队论库存论竞争决策理论决策论：人与自然的较量对策论（博弈论）：人与人的较量,运筹学的主要研究分支,线性规划：模型简单，是运筹学中应用最为广泛的一个分支。非线性规划：在各类工程的优化设计中应用广泛。动态规划：研究多阶段决策过程最优化的运筹学分支。图与网络流：利用图来表示研究对象及其联系，并用图论方法来研究网络结构和流量的优化分析。决策论：研究决策过程中关于方案目标选取和度量、效用值计算、选取最优方案和策略等的有关科学理论。对策论（博弈论）：用于研究具有对抗局势的模型。存贮论：研究最优存贮策略的理论和方法。排队论：对排队系统的研究理论和方法。,运筹学主要分支简介,数学规划MathematicalProgramming,一般数学描述目标函数或约束函数都是线性的,则是线性规划(LinearProgramming);若其中至少有一个是非线性的,为非线性规划(NonlinearProgramming);若其中至少有一个变量要求为整数,则为整数规划(IntegerProgramming).,数学规划,动态规划(DynamicProgramming)解决多阶段决策过程最优化问题的一种方法可用于解决最优路径问题、生产计划与库存、投资决策等实际问题。,图与网络流Graphtheory,决策论（decision),著名经济学家西蒙有一句名言：“管理就是决策”。“决策”一词本身是一个广义的概念，后续课程将介绍在不确定或随机环境下的决策分析方法。应用背景：产品开发决策问题、风险投资决策问题、开设连锁店问题等等,博弈论（GameTheory),排队论（QueuingTheory,银行、医院、机场跑道、港口码头、理发店、通信设备、交通路口等等的排队现象；排队论又叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构、或组织被服务的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等。,库存论(InventoryTheory),存储物品的现象是为了解决供应（生产）与需求（消费）之间的不协调的一种措施；由此带来一些需要决策的问题：库存量、进货量（如报童问题）、补货的时间等等决策量。现在也是供应链管理研究中的热点问题。,真实系统,系统分析问题描述,模型建立与修改,模型求解与检验,结果分析与实施,数据准备,运筹学分析的步骤,本课程的主要内容,线性规划整数规划(线性)图论决策论博弈论,第一章线性规划LinearProgramming,运筹学中应用最广泛的方法之一运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大,发展历程,原始的数学规划模型早在1759年和1874年就分别由经济学家Quesnay和Walras提出。康托洛维奇于1939年出版了“生产组织与计划中的数学方法”一书，对一个工厂的生产计划任务建立了线性规划模型，并提出“解乘数法”。冯诺伊曼(VonNeuman)和摩根斯坦(Morgenstern)1944年发表的对策论与经济行为涉及与线性规划等价的对策问题及线性规划对偶理论GBDantzig1947年研究美国空军资源的优化配置时提出了线性规划的通用解法单纯型法。50年代初成功地用电子计算机求解线性规划问题。,从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的还有Simon，Samullson，Leontief，Arrow，Miller等,发展历程,1.1线性规划的数学模型,例1、生产计划问题,问产品A,B各生产多少,可获最大利润?,maxZ=40 x1+50 x2,解:设产品A,B产量分别为变量x1，x2,例2,求：最低成本的原料混合方案,解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4),minZ=2x1+5x2+6x3+8x4,要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件,线性规划问题的特征,线性规划模型的要素,决策变量：向量(x1xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=(x1xn)线性式，求Z极大或极小,56,一般式,Max(min)Z=c1x1+c2x2+cnxn,线性规划问题解的定义,定义1：满足所有约束条件(1)、(2)的解X=(X1Xn)T称为LP问题的可行解，全部可行解的集合称为可行域。,定义2：使目标函数达到最优值的可行解称为LP问题的最优解.,(LP),1.3线性规划的图解法,maxz=x1+3x2s.t.x1+x26-x1+2x28x10,x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,例1、maxZ=40 x1+50 x2,解：(1)、确定可行域x10 x1=0(纵)x20 x2=0(横),x1+2x230 x1+2x2=30(0,15)(30,0),3x1+2x2=60(0,30)(20,0),2x2=24,(2)、求最优解,解：x*=(15,7.5)Zmax=975,0,最优解：BC线段B点C点x(1)=(6,12)x(2)=(15,7.5)x=x(1)+(1-)x(2)(01),求解,X=+(1-),无界无有限最优解,无解无可行解,0,(a)可行域封闭，唯一最优解,(a)可行域封闭，多个最优解,(d)可行域开放，多个最优解,(e)可行域开放，目标函数无界,(f)可行域为空集,(c)可行域开放，唯一最优解,总结,(1)、可行域为凸多边形。,(2)、若有最优解，一定可在可行域的顶点达到。,1.4线性规划解的几何特性,凸集及其性质,定义1：凸集D是n维欧氏空间的一个集合X(1),X(2)D,若任一个满足X=X(1)+(1-)X(2)(01)有XD凸集中任意两点的连线仍然属于该集合。,凸集图例,(a)凸集(b)凸集(c)凸集,(a)非凸集(b)非凸集(c)非凸集,X(1),X(2),X(k)是n维欧氏空间中的k个点，若有一组数1,2,k满足0i1(i=1,k),定义2,有点X=1X(1)+kX(k)则称点X为X(1),X(2),X(k)的凸组合。,凸组合,凸集D,点XD，若找不到两个不同的点X(1),X(2)D使得X=X(1)+(1-)X(2)(00X(2)不是。,(3)选x1从0，x5=0,x1=min(6/1,36/3,1)=6x1进基，x3出基。,B3=(P1P4P2),令x3=x5=0X(3)=(6,12,0,18,0)TZ(3)=840,(2)150X(3)不是,(3)选x5从0，x3=0,x5=min(18/2,12/1/2)=9x5进基，x4出基。,B4=(P1P5P2),令x3=x4=0X(4)=(15,15/2,0,0,9)TZ(4)=975,0,(0,0),x2,x1,三、单纯形表,c1c2cmcm+1cm+kcnCBXBB-1bx1x2xmxm+1xm+kxnc1x1b1100a1m+1a1m+ka1nc2x2b2010a2m+1a2m+ka2ncrxrbr000arm+1arm+karncmxmbm001amm+1amm+kann,Z0000m+1m+kn,例1,4050000CBXBbx1x2x3x4x50 x33012100150 x46032010300 x5240(2)00112040500000 x36(1)010-160 x4363001-11250 x21201001/260040000-2540 x161010-10 x41800-31(2)950 x21201001/224,84000-40015,40 x11510-1/21/200 x5900-3/21/2150 x215/2013/4-1/40,本问题的最优解X=(15,15/2,0,0,9)TZ=975,4050000CBXBbx1x2x3x4x5,97500-35/2-15/20,例2maxZ=x1+2x2,12000CBXBbx1x2x3x4x50 x34101000 x430(1)0100 x58120010120000 x34101002x23010100 x52(1)00-21,(接下表),6100-20,12000CBXBbx1x2x3x4x50 x32001(2)-12x23010101x12100-2180000-10 x41001/21-1/22x2201-1/201/21x1410100,80000-1,X(1)=(2,3)Z(1)=8,X(2)=(4,2)Z(2)=8,无穷多解,1-110-30CBXBbx1x2x3x4x5x61x36011-1201x15120-2000 x68020131110-403-501x3140310511x1211600620 x48020131350-1000-14-3,1012000XBbx1x2x3x4x5i0 x363(4)1003/20 x42410102/10 x53320013/20101200012x23/23/411/40020 x41/213/40-1/4102/130 x50(3/2)0-1/20101810-30012x23/2011/20-1/20 x41/2005/61-13/610 x1010-1/302/3,1800-8/30-2/3,退化解,X*=(0,3/2,0,1/2,0)T,Zmax=18,例5：,41000CBXBbx1x2x3x4x50 x32-111000 x44(1)-40100 x581-2001,041000,0 x360-31104x141-40100 x540(2)0-11160170-400 x312001-1/23/24x112100-121x22010-1/21/2,500009/2-17/2,本问题无界。,四、初始基本可行解的求法,(一)、大M法：判定无解条件：当进行到最优表时，仍有人工变量在基中，且0，则说明原问题无可行解。,例1：,64000-M-MCBXBbX1X2X3X4X5X6X70X310023100000X41204201000-MX614(1)000010-MX7220100-101-36MM+6M+400-M000X37203100-200X46402010-406X1141000010-MX7220(1)00-101,84-22M0M+400-M6-M0,0 x360010(3)-2-30 x42000012-4-26x11410000104x2220100-101172000046-M4-M0 x52001/301-2/3-10 x41600-2/310-8/306x11410000104x224011/300-2/3-2,18000-4/300-M-10/3-M,CBXBbx1x2x3x4x5x6x7,64000-M-M,1.7线性规划的对偶问题,Duality,一、对偶问题,例：某厂生产甲、乙两种产品，消耗A、B两种原材料。生产一件甲产品可获利2元，生产乙产品获利3元。问在以下条件下如何安排生产？,建立线性规划模型：目标函数：MAXZ=2X1+3X2约束条件：X1+2X284X1+164X212X1,X20,从另一角度考虑：如果该厂决定不生产甲、乙两种产品，而将其资源出租或出售，这时工厂的决策者就要考虑给每种资源如何定价的问题。设用Y1,Y2,Y3分别表示出租单位设备台时的租金和出让原材料A、B的附加值。作如下比较，用一个单位设备台时和四个单位的原材料可以生产甲产品一件，获利2元，那么出租和出让的收益不应低于自己生产时的收益。因此有Y1+4Y22;同样地乙产品也有：2Y1+4Y33,一、对偶问题,全部出让或出租的总收入为W=8Y1+16Y2+12Y3从决策者来看，当然希望W值越大越好。但从接受者来讲，支付越少越好。为提高竞争力，因此工厂只能在满足所有产品的利润条件，使其总收入具有竞争力的，因此，W需要求解最小值。因此有线性规划模型：目标函数：minW=8Y1+16Y2+12Y3s.tY1+4Y222Y1+4Y33Y1,Y2,Y30,一、对偶问题,二、对偶关系,（P）（D）,二、对偶关系,原问题(primalproblem)（P1）：maxz=CTXAXbX0对偶问题(dualproblem)（D1）：minw=bTYATYCY0,二、对偶关系,例子:minz=3x1+2x2x3s.t.2x1+x2+3x323x1-5x25x1+x2+x3=1x10,x2自由,x30,二、对偶关系,其对偶问题:maxw=2y1+5y2+y3s.t.2y1+3y2+y33y15y2+y3=23y1+y3-1y10,y20,y3自由,例、写对偶规划,MinZ=4x1+2x23x3,-x1+2x262x1+3x39x1+5x22x3=4x2,x30,MaxW=6y1+9y2+4y3,-y1+2y2+y3=42y1+5y323y2-2y3-3y10,y20,y3自由,MinZ=4x1+2x23x3,x12x2-62x1+3x39x1+5x22x3=4x2,x30,例,MaxW=-6y1+9y2+4y3,y1+2y2+y3=4-2y1+5y323y2-2y3-3y1,y20,y3自由,三、对偶性质,对称性:(P)和(D)相互对偶弱对偶性:CTXbTY最优性:当CTX=bTY时,(P)(D)皆最优对偶原理:如果一个问题有最优解,其对偶问题也有最优且等最优值;如一个问题无界,其对偶问题无可行解兼容性(标准形）:原问题的检验数给出对偶问题的一个基本解互补松弛性（标准形）,例1、写出下面问题的对偶规划,产品A，B产量x1，x2，Z为利润,例1、,X=(8,24)TZ=184,5600XBbx1x2x3x40 x34831100 x41203(4)01056000 x318(9/4)01-1/46x2303/4101/41801/200-3/25x18104/9-1/96x22401-1/31/3,18400-2/9-13/9,4812000MMyBy1y2y3y4y5y6My5533-1010My66140-10111M48-4M120-7MMM00My51/29/40-13/41-3/4120y23/21/410-1/401/4180+1/2M18-9/4M0M30-3/4M0-30+7/4M48y12/910-4/91/34/9-1/3120y213/9011/9-1/3-1/91/3,y=(2/9,13/9),Z=184,18400824M-8M-24,观察结论:,一对互为对偶的线性规划问题都有最优解，且目标函数值相等。,最优表中有两个问题的最优解。,四、对偶解的经济意义,经济解释：,bi：第i种资源的数量yi：对偶解bi增加bi,其它资源数量不变时,目标函数的增量,Z=,biyi,yi：反映bi的边际效益(边际成本),例1中y1=2/9,当机器台时数增加1个单位时，工厂可增加利润2/9个单位。,(2)、影子价格在模型中，yi表示资源bi增加1单位时，企业目标增加的净利润。由(1)的经济解释可知，yi的大小与系统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。,(3)、应用,情况某资源对偶解0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。,情况直接用影子价格与市场价格相比较，进行决策，是否买入该资源。,生产计划问题项目投资问题配料配套问题合理下料问题人力资源问题运输调运问题任务指派问题,1.8线性规划模型的应用,例1:生产计划问题某企业拟生产A、B两种产品，需利用一种原材料并经过车、铣两台机床加工，加工的工时定额、每天可用工时和原材料以及两种产品可能获得的利润如下表所示：要求：1）拟定一个获得利润最大的生产计划；2）若单价0.8元再购入少量原材料投入生产是否合算？为什么？,例2:生产计划问题某车间在每个生产期5天所需要的每种刀具的统计资料如下：每一把刀具成本为0.6元，用过的刀具送到机修车间研磨，每把需花费0.2元。刀具用过后送去磨(只一次），两天后可以磨好送回，供当天（第三天）使用。第五天后应全部换新，每期开始时没有任何刀具，问这个车间需要多少刀具才能应付需要，而成本又最低？试建立线性规划模型。,确定变量：问题是要确定每期需要新刀具的总数，它等价于要确定每天所需的新刀具，同时考虑到送去研磨的刀具第三天可使用，为此，设决策变量Xi(i=1,2,3,4,5)为第i天使用的新刀具；Yj(j=1,2,3)为第j天送去研磨的刀具数。确定目标函数：（新刀具成本研磨成本）为最小，即：minZ0.6(X1+X2+X3+X4+X5)+0.2(Y1+Y2+Y3),确定约束条件：由于研磨的刀具第三天才能使用，因此，X1=120；X2=85第三天开始，每天使用新的和研磨送回的刀具：X3+Y1=160,X4+Y2=145,X5+Y3=300在头三天送去研磨的刀具应满足：Y1X1,Y2X2+(120-Y1);Y3X3+(120-Y1)+(85-Y2)每天使用的新刀具和送研磨的刀具数为非负整数：X1,X2,X3,X4,X5,Y1,Y2,Y30,且均为整数,完整的模型为：minZ0.6(X1+X2+X3+X4+X5)+0.2(Y1+Y2+Y3)s.t.X1=120X2=85X3+Y1=160X4+Y2=145X5+Y3=300Y1X1Y2X2+(120-Y1)Y3X3+(120-Y1)+(85-Y2)X1,X2,X3,X4,X5,Y1,Y2,Y30,且均为整数,求解结果X1=120X2=85X3=160X4=0X5=80Y1=0Y2=145Y3=220,例3：营销策略一贸易公司专门经营某商品的批发业务，公司有库容5000单位的仓库，某年一月一日，公司有库存1000单位，并有资金20000元，估计第一季度该商品的价格如下表所示。如买进的商品当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望本季末库存为2000单位，问应采取什么样的买卖策略可使3个月总的获利最大？一月二月三月进货价（元）2.853.052.90出货价（元）3.103.252.95,考虑到资金周转，应该是先卖出再买进，而且最好是月初卖出月底买进。决策变量：每月买进Xi(i=1,2,3),每月卖出Yi(i=1,2,3)。分析库存情况：库存卖出买入月末库存一月1000Y1X11000-Y1+X1二月1000-Y1+X1Y2X21000-Y1+X1-Y2+X2三月1000-Y1+X1-Y2+X2Y3X31000-Y1+X1-Y2+X2-Y3+X3存货限制：Y11000Y21000-Y1+X1Y31000-Y1+X1-Y2+X2库容限制：1000-Y1+X150001000-Y1+X1-Y2+X250001000-Y1+X1-Y2+X2-Y3+X32000,分析资金流动情况：月初资金卖出买入一月200003.10Y12.85X1二月20000+3.10Y1-2.85X13.25Y23.05X2三月20000+3.10Y1-2.85X1+3.25Y2-3.05X22.95Y32.90X3资金限制：2.85X120000+3.10Y13.05X220000+3.10Y1-2.85X1+3.25Y22.90X320000+3.10Y1-2.85X1+3.25Y2-3.05X2+2.95Y3目标函数：MAXZ=3.10Y1+3.25Y2+2.95Y3-2.85X1-3.05X2-2.90X3,目标函数：MAXZ=3.10Y1+3.25Y2+2.95Y3-2.85X1-3.05X2-2.90X3资金限制：2.85X120000+3.10Y13.05X220000+3.10Y1-2.85X1+3.25Y22.90X320000+3.10Y1-2.85X1+3.25Y2-3.05X2+2.95Y3存货限制：Y11000Y21000-Y1+X1Y31000-Y1+X1-Y2+X2库容限制：1000-Y1+X150001000-Y1+X1-Y2+X250001000-Y1+X1-Y2+X2-Y3+X32000,例4连续投资问题某部门在五年内考虑给下列项目投资：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115。项目B：从第三年初需投资，到第五年末能回收本利125，但规定最大投资额不超过4万元。项目C：第二年初需要投资，到第五年末能回收本利140，但规定最大投资额不超过3万元。项目D：五年内每年初可购买公债于当年末归还并加利息6。该部门现有资金10万元，问应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大。,确定变量：以XiA,XiB,XiC,XiD(i=1,2,3,4,5)分别表示第i年年初给项目A,B,C,D的投资额。具体列于下表：,确定约束条件：投资额应等于手中拥有的资金，不应有剩余。第一年：X1A+X1D=100000第二年：年初资金仅为D项目第一年的本息。X2A+X2C+X2D=X1D(1+6%)第三年：年初资金为A第一次回收本利D第二次本息X3A+X3B+X3D=X1A(1+15%)+X2D(1+6%)第四年：X4A+X4D=X2A(1+15%)+X3D(1+6%)第五年：X5D=X3A(1+15%)+X4D(1+6%)B、C投资额限制：X3B40000;X2C30000确定目标函数：第五年末资金最大MAXZ=1.15X4A+1.40X2C+1.25X3B+1.06X5D,完整的模型为：MAXZ=1.15X4A+1.40X2C+1.25X3B+1.06X5Ds.t.X1A+X1D=100000-1.06X1D+X2A+X2C+X2D=0-1.15X1A-1.06X2D+X3A+X3B+X3D=0-1.15X2A-1.06X3D+X4A+X4D=0-1.15X3A-1.06X4D+X4D=0X2C30000X3B40000XiA,XiB,XiC,XiD(i=1,2,3,4,5)0,求解结果（单位:元）：第一年：X1A=34783,X1D=65217第二年：X2A=39130,X2C=30000,X2D=0第三年：X3A=0,X3B=40000,X3D=0第四年：X4A=45000,X4D=0第五年：X5D=0第五年末总资金：Z=143750,例5投资问题某部门现有资金200万元，今后五年内考虑给以下的项目投资。项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；据测定每万元每次投资的风险指数如下表：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？,解：1）确定决策变量：连续投资问题设xij(i=1-5，j=1、2、3、4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24,2）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B次年末才可收回投资，故第二年年初的资金为1.1x11，于是x21+x22+x24=1.1x11；第三年：年初的资金为1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初的资金为1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初的资金为1.1x41+1.25x32，于是x51=1.1x41+1.25x32；B、C、D的投资限制：xi230(I=1、2、3、4)，x3380，x24100,a)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？目标函数及模型：Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200 x21+x22+x24=1.1x11x31+x32+x33=1.1x21+1.25x12x41+x42=1.1x31+1.25x22x51=1.1x41+1.25x32xi230(I=1、2、3、4)，x3380，x24100 xij0(i=1、2、3、4、5；j=1、2、3、4）,b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12200 x21+x22+x241.1x11；x31+x32+x331.1x21+1.25x12；x41+x421.1x31+1.25x22；x511.1x41+1.25x32；xi230(I=1、2、3、4)，x3380，x241001.1x51+1.25x42+1.4x33+1.55x24330 xij0(i=1、2、3、4、5；j=1、2、3、4）,例6配料问题某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？,解：设xij表示第i种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出约束条件：规格要求有4个约束；(如,x1150%(x11+x12+x13)供应量限制有3个约束。(x11+x21+x31100),