3.3机理模型.ppt

《3.3机理模型.ppt》由会员分享，可在线阅读，更多相关《3.3机理模型.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 3.3 机理模型 优化问题与规划模型优化问题与规划模型优化问题与规划模型 优化问题优化问题：与最大、最小、最长、最短等等有关的问题。与最大、最小、最长、最短等等有关的问题。解决最优化问题的数学方法：解决最优化问题的数学方法：运筹学运筹学 运筹学主要分支运筹学主要分支：线性规划、非线性规划、整数规划；线性规划、非线性规划、整数规划；动态规划、多目标规划、分层规划；动态规划、多目标规划、分层规划；存贮论、存贮论、排队伦、排队伦、对策论、对策论、决策论；决策论；图与网络分析图与网络分析 。线性规划线性规划1.问题问题例例1 家具生产的安排家具生产的安排 一一.家具公司生产桌子和椅子，家具公司生产桌

2、子和椅子，每张桌子要用每张桌子要用15个工时，个工时，0.2立方木材，立方木材，售价售价80元元 每张椅子要用每张椅子要用10个工时，个工时，0.05立方木材，售价立方木材，售价45元元 用于生产的劳力共计用于生产的劳力共计450个工时，木材共有个工时，木材共有4立方米立方米 问为达到最大的收益，应如何安排生产？问为达到最大的收益，应如何安排生产？分析：分析：1.1.求什么？求什么？生产多少桌子？生产多少桌子？生产多少椅子？生产多少椅子？2.2.优化什么？优化什么？收益最大收益最大 3.3.限制条件？限制条件？原料总量原料总量 劳力总数劳力总数x1x2Max f=80 x1+45 x20.2

3、x1+0.05 x2 415 x1+10 x2 450模型模型I：以产值为目标取得最大收益以产值为目标取得最大收益.设：生产桌子设：生产桌子 x1张张,椅子椅子 x2张张,(决策变量决策变量)将将目标目标优化为：优化为：max f=80 x1+45x2 对决策变量的对决策变量的约束约束：0.2x1+0.05x24 20 x1+5x2400 15x1+10 x2450,x1 0,x2 0,0.2x1+0.05x24规划问题：在约束条件下求目标函数的最优值点。规划问题：在约束条件下求目标函数的最优值点。规划问题包含规划问题包含3个组成要素个组成要素:决策变量、目标函数、约束条件决策变量、目标函数、

4、约束条件。1.1.规划问题分类：规划问题分类：当目标函数和约束条件当目标函数和约束条件 都是决策变量的线性函数时，都是决策变量的线性函数时，称为称为线性规划问题线性规划问题,否则称为否则称为非线性规划问题非线性规划问题。2.2.线性规划问题求解方法线性规划问题求解方法称满足约束条件的向量为称满足约束条件的向量为可行解可行解,称可行解的集合为称可行解的集合为可行域可行域 ,称使目标函数达最优值的可行解为称使目标函数达最优值的可行解为最优解最优解.图解法：图解法：(解两个变量的线性规划问题解两个变量的线性规划问题)在平面上画出可行域（凸多边形），在平面上画出可行域（凸多边形），计算目标函数在各极点

5、计算目标函数在各极点(多边形顶点多边形顶点)处的值处的值比较后，取最值点为最优解。比较后，取最值点为最优解。命题命题 1 1 线性规划问题的可行解集是凸集线性规划问题的可行解集是凸集 可行解集：线性不等式组的解可行解集：线性不等式组的解 0.2x1+0.05x2=415x1+10 x2=450命题命题2 线性规划问题的目标函数线性规划问题的目标函数(关于不同的目标关于不同的目标值值)是一族平行直线是一族平行直线,目标值的大小描述了直线离原点的远近目标值的大小描述了直线离原点的远近命题命题3 3 线性规划问题的最优解一定在可行解集线性规划问题的最优解一定在可行解集的某个的某个极点极点上达到上达到

6、(穿过可行域的目标直线组中最远离穿过可行域的目标直线组中最远离(或接近或接近)原原点的直线所穿过的凸多边形的点的直线所穿过的凸多边形的顶点顶点).求解可得求解可得 生产计划生产计划 x1=14,x2=24 净收益净收益 f=80 x1+45x2=2200（元）（元）共用木材共用木材 0.2x1+0.05x2=4（立方）（立方）共需劳力共需劳力 15x1+10 x2=450（工时）（工时）,单纯形法单纯形法:使用线性代数的方法求解线性规划问题使用线性代数的方法求解线性规划问题 通过确定约束方程组的基本解通过确定约束方程组的基本解,并计算相应目标函数值并计算相应目标函数值,在可行解集的极点中搜寻最

7、优在可行解集的极点中搜寻最优 模型的标准化模型的标准化 正则模型正则模型:决策变量决策变量:x1,x2,xn.目标函数目标函数:Z=c1x1+c2x2+cnxn.约束条件约束条件:a11x1+a1nxnb1,am1x1+amnxnbm,模型的标准化过程模型的标准化过程 10.引入松弛变量将不等式约束变为等式约束引入松弛变量将不等式约束变为等式约束 若有若有 ai1x1+ainxnbi,则则引入引入xn+i 0,使得使得 ai1x1+ainxn+xn+i=bi 若有若有 aj1x1+ajnxnbj,则引入则引入xn+j 0,使得使得 aj1x1+ajnxn-xn+j=bj.且有且有 Z=c1x1

8、+c2x2+cnxn+0 xn+1+0 xn+m.20.将目标函数的优化变为目标函数的极大化将目标函数的优化变为目标函数的极大化.若求若求 min Z,令令 Z=Z,则问题变为则问题变为 max Z.30.引入人工变量引入人工变量,使得所有变量均为非负使得所有变量均为非负.若若 xi 没有非负的条件没有非负的条件,则引入则引入 xi 0 和和 xi0,令令 xi=xi xi,则可使得问题的全部变量均非则可使得问题的全部变量均非负负.标准化模型标准化模型 求变量求变量 x1,x2,xn,max Z=c1x1+cnxn,s.t.a11x1+a1nxn=b1,am1x1+amnxn=bm,x1 0,

9、xn 0,讨论模型讨论模型I 模型可以标准化为模型可以标准化为 求变量：求变量：x1,x2,x3,x4 max f=80 x1+45x2 s.t.20 x1+5x2+x3=400 15x1+10 x2+x4=450 x10，x20,x30,x40令令x3=x4=0关于关于x1,x2 求解方程求解方程(4),(5)可得可得 x1=14，x2=24 代入目标函数（代入目标函数（3）得到）得到 f=8014+4524=2200令令x2=x3=0关于关于x1,x4 求解方程求解方程(4),(5)可得可得 x1=20，x4=150 f=8020+450=1600令令x1=x4=0关于关于x2,x3 求解

10、方程求解方程(4),(5)可得可得 x2=45，x3=170 f=800+4545=2025令令x1=x2=0关于关于x3,x4 求解方程求解方程(4),(5)可得可得 x3=400，x4=4500 f=800+450=0令令x1=x3=0关于关于x2,x4 求解方程求解方程(4),(5)可得可得 x2=80，x4=350 非可行解非可行解令令x2=x4=0关于关于x1,x3 求解方程求解方程(4),(5)可得可得 x1=30，x3=400 非可行解非可行解最优解为最优解为 x1=14，x2=24，目标函数值目标函数值f=8014+4524=2200 定义定义:若代数方程若代数方程AX=B的解

11、向量有的解向量有n-m个分量为零个分量为零,其余其余m个分量对应个分量对应A的的m个线性无关列个线性无关列,则称该解向量为方程组的一个则称该解向量为方程组的一个基本解基本解.在一个线性规划问题中在一个线性规划问题中,如果一个可行解也是约束方程组的基本解如果一个可行解也是约束方程组的基本解,则称之为则称之为基本可行解基本可行解命题命题 4 一个向量一个向量 x 是线性规划问题可行解集的一个是线性规划问题可行解集的一个极点极点,当且仅当它是约束方程的一个当且仅当它是约束方程的一个基本可行解基本可行解.一般线性规划的数学模型及解法：一般线性规划的数学模型及解法：min f=cTxs.t.Ax b A

12、1x=b1 LB x UBMatlab求解程序求解程序x,f=linprog(c,A,b,A1,b1,LB,UB)练习练习1：农作物种植安排：农作物种植安排一个农场计划种蔬菜一个农场计划种蔬菜,棉花和水稻棉花和水稻.预计预计每亩产值（利润）分别为每亩产值（利润）分别为110元元,75元元,60元元.农场有农场有50亩土地亩土地,20个劳动力个劳动力,种种植这三种农作物每亩地分别需要劳动力植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4,如何规划经营使经济效益如何规划经营使经济效益最大最大.设决策变量：设决策变量：种植蔬菜种植蔬菜x1亩亩,棉花棉花x2亩亩,水稻水稻x3亩，亩，求目标函数

13、求目标函数 f=110 x1+75x2+60 x3在约束条件在约束条件 x1+x2+x350 1/2x1+1/3x2+1/4x3 20 x1，x2，x30下的最大值下的最大值练习练习2 资源分配资源分配生产甲肥生产甲肥1吨吨,需要磷酸盐需要磷酸盐0.4吨吨,硝酸盐硝酸盐1.8吨吨,利润利润1万元万元;生产乙肥生产乙肥1吨吨,需要磷需要磷酸盐酸盐0.1吨吨,硝酸盐硝酸盐1.5吨吨,利润利润0.5万元万元.现有磷酸盐现有磷酸盐10吨吨,硝酸盐硝酸盐66吨吨,问甲、乙问甲、乙肥各生产多少吨获利最大？肥各生产多少吨获利最大？设决策变量：设决策变量：生产甲肥生产甲肥x1吨吨,乙肥乙肥x2吨，吨，求目标函

14、数求目标函数 f=1x1+0.5x2在约束条件在约束条件 0.4x1+0.1x210 1.8x1+1.5x2 66 x1，x20下的最大值。下的最大值。模型模型 II.在不降低当前生产水平的前提下评估资源的在不降低当前生产水平的前提下评估资源的贡献，使贡献，使“成本成本”投入最低。投入最低。设每立方木材和每个工时投入设每立方木材和每个工时投入“成本成本”分别为分别为 y1 y2(决策变量决策变量)则则目标函数目标函数为：为：g=4y1+450y2 对决策变量的对决策变量的约束约束 0.2y1+15y2 80 0.05y1+10y2 45 y1 0,y2 0 求解可得求解可得 y1=100（元（

15、元/m3），），y2=4（元（元/工时）工时）总成本总成本 g=4y1+450y2=2200（元）（元）产品成本（资源的贡献）产品成本（资源的贡献）0.2y1+15y2=80 0.05y1+10y2=453.对偶问题对偶问题(Dual Problem)：A 是是m n 矩阵，矩阵，c 是是 n 1向量（价格），向量（价格），b 是是 m 1向量（原料）向量（原料）x 是是 n 1向量（产出）向量（产出）,y 是是 m 1向量（成本）向量（成本）问题问题max f=cTxs.t.Ax b xi 0,i=1,2,n.对偶问题对偶问题min f=bTys.t.ATy cyi 0,i=1,2,m.对偶

16、定理对偶定理:互为对偶的两个线性规划问题互为对偶的两个线性规划问题,若其中一个有有穷的最优解若其中一个有有穷的最优解,则另一个也有有穷的最优解则另一个也有有穷的最优解,且最优值相等且最优值相等.若两者之一有无界的最优解若两者之一有无界的最优解,则另一个没有可行解则另一个没有可行解模型模型 I 给出了生产中产品的最优给出了生产中产品的最优 方案方案模型模型 II 给出了生产中资源的最低估价给出了生产中资源的最低估价.这种估价涉及到资源的有效利用这种估价涉及到资源的有效利用,它不是市场价格它不是市场价格,而是根据资源在生产中的贡献确定的估价而是根据资源在生产中的贡献确定的估价.我们称之为我们称之为

17、影子价格影子价格(shadow price)例例2.生产生产5种产品种产品P1,P2,P3,P4,P5 单价为单价为 550,600,350,400,200.三道工序三道工序:研磨研磨、钻孔钻孔、装配装配。每种产品所需工时每种产品所需工时 P1 P2 P3 P4 P5 I 12 20 0 25 15 II 10 8 16 0 0 III 20 20 20 20 20各工序的生产能力（工时数）各工序的生产能力（工时数）288 192 384如何安排生产，收入最大。如何安排生产，收入最大。模型：设模型：设 xi 生产生产 Pi 的件数。的件数。则则max Z=550 x1+600 x2+350 x

18、3+400 x4+200 x5。s.t.12 x1+20 x2+0 x3+25 x4+15 x5 288 10 x1+8 x2+16 x3+0 x4+0 x5 192 20 x1+20 x2+20 x3+20 x4+20 x5 384 xi 0有解有解 x1=12，x2=7.2，x3=x4=x5=0 Z=10920分析：分析：1.约束条件（生产能力）限制的情况约束条件（生产能力）限制的情况 12x1+20 x2=288 288 10 x1+8x2=177.6192 20 x1+20 x2=384 384三个工序的生产能力不平衡三个工序的生产能力不平衡如果改变三个工序的生产能力，每个工序的单如果

19、改变三个工序的生产能力，每个工序的单位增长会带来多少贡献？位增长会带来多少贡献？2.产品价格的影响产品价格的影响 x1 x2 x3 x4 x5 550 600 350 400 200结果表明与结果表明与 P1,P2相比相比 P3,P4,P5，定价低了，定价低了.在当前的生产能力下，产品的定价不平衡在当前的生产能力下，产品的定价不平衡价格如何改变价格如何改变,生产才能达到平衡生产才能达到平衡?对偶问题有解对偶问题有解:工序的成本（贡献）：工序的成本（贡献）：w1=6.25,w2=0,w3=23.75 Zopt=6.25288+0192+23.75384 =10920 约束条件约束条件(影子价格）

20、的情况影子价格）的情况X1：126.25+100+2023.75=550550X2：206.25+80+2023.75=600600X3：0 6.25+160+2023.75=475.00350X4：256.25+00+2023.75=631.25400X5：156.25+00+2023.75=568.752004.灵敏度分析当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时,最优解是否会随之变化?通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题,被称为参数线性规划(参见线性规划书籍).例如,当农作物的价格发生变化时,生产计划是否应马上随之改变?可以稍微改

21、变价格，观察最优解的变化，讨论参数的灵敏性。练习练习3 营养配餐营养配餐甲种食品每甲种食品每10克含克含5个单位的蛋白个单位的蛋白,10个单位的铁个单位的铁,单价单价3元元;乙种食品每乙种食品每10克克含含7个单位的蛋白个单位的蛋白,4个单位的铁个单位的铁,单价单价2元元.现需要一份食品现需要一份食品,含有含有35个单位的个单位的蛋白蛋白,40个单位的铁个单位的铁,问如何配餐最省钱问如何配餐最省钱?思考1一家大建筑公司正在三个地点开掘。同时又在一家大建筑公司正在三个地点开掘。同时又在其他四个地点建筑，这里需要土方的填充。在其他四个地点建筑，这里需要土方的填充。在1、2、3处挖掘产生的土方分别为

22、每天处挖掘产生的土方分别为每天150，400，325立方码。建筑地点立方码。建筑地点A、B、C、D处处需要的填充土方分别为需要的填充土方分别为175，125，225，450立方码。也可以从地点立方码。也可以从地点4用每立方码用每立方码5美元美元的价格获得额外的填充土方。填充土方运输的的价格获得额外的填充土方。填充土方运输的费用约为一货车容量每英里费用约为一货车容量每英里20美元。一辆货车美元。一辆货车可以搬运可以搬运10立方码的土方，每立方码土方每英立方码的土方，每立方码土方每英里运输费里运输费2美元。下表给出了各地点间距离的美元。下表给出了各地点间距离的英里数。求使公司花费最少的运输计划。英

23、里数。求使公司花费最少的运输计划。挖掘与建筑地点间的距离（英里）挖掘与建筑地点间的距离（英里）接收填充土方的地点接收填充土方的地点挖掘地点挖掘地点 A B C D1 5 2 6 102 4 5 7 53 7 6 4 44 9 10 6 2农作物问题农作物问题某农户有某农户有100英亩土地合英亩土地合5000美元可供投资。美元可供投资。每年冬季家庭成员可以贡献每年冬季家庭成员可以贡献3500小时的劳动小时的劳动时间，而夏季为时间，而夏季为4000小时。如果这些劳动时小时。如果这些劳动时间有富裕，家庭成员可以去附近农场打工，冬间有富裕，家庭成员可以去附近农场打工，冬季每小时季每小时4.8美元，夏季

24、每小时美元，夏季每小时5.1美元。美元。现金收入来源于现金收入来源于3种农作物（大豆、玉米、燕种农作物（大豆、玉米、燕麦）以及麦）以及2种家禽（奶牛、母鸡）。农作物不种家禽（奶牛、母鸡）。农作物不需要投资，但每头奶牛需要需要投资，但每头奶牛需要400美元初始投资，美元初始投资，每只母鸡需要每只母鸡需要3美元初始投资。美元初始投资。思考思考2每头奶牛需要每头奶牛需要1.5英亩土地，冬季需要付出英亩土地，冬季需要付出100小时劳动时间，夏季小时劳动时间，夏季50小时，每年净收益小时，每年净收益为为450美元；相应地，每只母鸡不占用土地，美元；相应地，每只母鸡不占用土地，冬季冬季0.6小时，夏季小时

25、，夏季0.3小时，年净收益为小时，年净收益为3.5美元。养鸡房最多容纳美元。养鸡房最多容纳3000只母鸡，栅拦最只母鸡，栅拦最多能容纳多能容纳32头奶牛。头奶牛。种植一英亩的大豆、玉米、燕麦分别需要冬季种植一英亩的大豆、玉米、燕麦分别需要冬季劳动时间劳动时间20、35、10小时，夏季劳动时间小时，夏季劳动时间30、75、40小时，年景收益分别为小时，年景收益分别为175、300、120美元。建立数学模型，帮助该农户确定养美元。建立数学模型，帮助该农户确定养殖计划，使得年净收入最多。殖计划，使得年净收入最多。思考题思考题*：有：有4名同学到一家公司参加三名同学到一家公司参加三个阶段的面试，公司要

26、求每个同学都必个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并管处复试，最后到经理处参加面试，并且不许插队（即在任何阶段且不许插队（即在任何阶段4位同学的顺位同学的顺序是一样的）。由于序是一样的）。由于4位置同学的专业背位置同学的专业背景不同，所以每人在三个阶段的面试时景不同，所以每人在三个阶段的面试时间也不同，如下所示：间也不同，如下所示：秘书初试秘书初试 主管复试主管复试 经理面试经理面试同学甲同学甲 13 15 20同学乙同学乙 10 20 18 同学丙同学丙 20 16 10同学丁同学丁 8 10

27、15这这4位同学约定他们面试完后一起离开公位同学约定他们面试完后一起离开公司，假定现在是早上司，假定现在是早上8：00，问他们最，问他们最早何时能离开公司。早何时能离开公司。3.3 机理模型优化问题与规划模型优化问题与规划模型课堂讨论总结参加组数：19组，人数57人参加评分：411包饺子模型：10组，洗衣服9组优胜组包饺子 五组1.刘达通 胡勤 王威2.马锡豫 3.张郑4.李直5.杨雅婷洗衣服1.刘轶群2.文豪3.封达道4.孙鹏举5.帅清 4.非线性规划非线性规划 当目标函数和约束条件中包含有决策变量的非当目标函数和约束条件中包含有决策变量的非线性函数时，线性函数时，称为称为非线性规划问题非线

28、性规划问题。例例3.某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水泥日用量水泥日用量di(单位：吨）单位：吨）建两个日储量为建两个日储量为 e=20 吨的料场，吨的料场，需要确定料场位置需要确定料场位置(xj,yj)和运量和运量cij，使总吨公里数最小。使总吨公里数最小。假设：假设：1.只考虑两点间的直线距离只考虑两点间的直线距离 2.各工地的需求稳定各工地的需求稳定令令 cij 为料场为料场 j 向工地向工地 i 运送的水泥量运送的水泥量 min z=f(z)s.t.A1xb1,A2x=b2,c1(x)0,c2(x)=0 LB x U

29、BMATLAB 程序程序 x,z=fmincon(fun,x0,A1,b1,A2,b2,LB,UB,nonlcon）用随机搜索算法确定初始点：用随机搜索算法确定初始点：在可行域在可行域0.5,8.75 0.75,7.75内简单地选取内简单地选取n个个随机的的点，随机的的点，计算目标函数在这些点的值，选择其中最小的计算目标函数在这些点的值，选择其中最小的点即可。点即可。然后，可采用然后，可采用Matlab求最值点程序求出精确的求最值点程序求出精确的最小值点最小值点:求函数求函数fun在在x0点附近的最小值点点附近的最小值点 5.0-1规划规划 如果要求决策变量只取如果要求决策变量只取0 或或 1

30、的线性规划问题的线性规划问题,称为整数规划称为整数规划.0-1 约束不一定是由变量的性质决定的约束不一定是由变量的性质决定的,更多更多地是由于逻辑关系引进问题地是由于逻辑关系引进问题的的 例例4 背包问题背包问题 一个旅行者的背包最多只能装一个旅行者的背包最多只能装 6 kg 物品物品.现有现有4 件物品件物品 重量为重量为 2 kg,3 kg,3 kg,4 kg,价值为价值为 100 元元,120元元,90元元,115元元.应携带那些物品使得携带物品的价值最大应携带那些物品使得携带物品的价值最大?建模建模:记记xj：旅行者携带第：旅行者携带第 j 件物品的件数件物品的件数,xj=0,1.约束

31、条件约束条件 2x 1+3x 2+3x 3+4x 4 6 求求xj使目标函数使目标函数 f=x1+1.2x2+0.9x3+1.15x4最大最大.用用Lingo 软件求解软件求解0-1规划规划Linear Interactive and General OptimizerModel:Max=x1+1.2*x2+0.9*x3+1.15*x4;2*x1+3*x2+3*x3+4*x40表示每件第表示每件第 j 类仪器的科学价值类仪器的科学价值;aj0表示每件第表示每件第 j 类仪器的重量类仪器的重量.每类仪器件数不限每类仪器件数不限,但装载件数只能是整数但装载件数只能是整数.飞船总载荷不得超过数飞船总

32、载荷不得超过数 b.设计一种方案设计一种方案,使得被装载仪器的科学价值之和最大使得被装载仪器的科学价值之和最大.建模建模 记记 xj 为第为第 j 类仪器的装载数类仪器的装载数.求求 各种仪器的装载数量各种仪器的装载数量 xj（整数）整数）在约束条件在约束条件 jaj xj b 下下,使得目标函数使得目标函数 f=j cj xj达到最大值达到最大值.7.用用Lindo软件求解整数规划软件求解整数规划Linear Interactive and Discrete optimizermax 3x1+2x2st2x1+3x2=142x1+x2=9endgin x1gin x2(或者用或者用 gin

33、2)求求 整数整数 x1,x2Max Z=3x1+2x2s.t.2x1+3x2142x1+x2 98.规划问题的建模艺术规划问题的建模艺术将实际问题归结为线性规划模型是一个探将实际问题归结为线性规划模型是一个探索创造的过程。索创造的过程。例例7 钢材截短钢材截短 有一批钢材有一批钢材,每根长每根长7.3米米.现需做现需做100套短钢材套短钢材.每套包括长每套包括长2.9米米,2.1米米,1.5米的各一根米的各一根.至少用掉多少根钢材才能满足需要至少用掉多少根钢材才能满足需要,并使得用料最省并使得用料最省.解解:可能的截法和余料可能的截法和余料第第1种种 7.3-(2.92+1.51)=0第第2

34、种种 7.3-(2.91+2.12)=0.2第第3种种 7.3-(2.91+1.52)=1.4第第4种种 7.3-(2.91+2.11+1.51)=0.8第第5种种 7.3-(2.12+1.52)=0.1第第6种种 7.3-(2.13)=1第第7种种 7.3-(2.11+1.53)=0.7第第8种种 7.3-(1.54)=1.3设按第设按第i种方法截种方法截 xi 根钢材根钢材(决策变量决策变量).目标函数目标函数 min f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8约束条件约束条件2x1+x2+x3+x4 1002x2+x4+2x5+3x6+x7 100

35、x1+2x3+x4+2x5+3x7+4x8 100 xi 0,i=1,8 用用Matlab程序解得程序解得 x1=40 x2=20 x5=30,f=7 （实际上应要求实际上应要求xi 为正整数。这是一个整数规划为正整数。这是一个整数规划问题）。问题）。例例 8 存储问题存储问题有有5种药品种药品 S=1,2,3,4,5 要存放要存放,有些药品不能存放在一起有些药品不能存放在一起,能存放在一起存放的药品为能存放在一起存放的药品为 =1,2,1,3,5,2,4,5,3,1,4,5不同的组合所需的存放费用不同不同的组合所需的存放费用不同其中第其中第 i 种组合的存储费用为种组合的存储费用为 ci,求

36、这五种药品费用最低的储存方案。求这五种药品费用最低的储存方案。令令xi 为存储组合为存储组合 i 的决策变量的决策变量:xi=1 时存储第时存储第 i 个组合个组合,否则否则 xi=0求求存储方案存储方案x=(x1,x2,x3,x4,x5,x6)在约束条件在约束条件 x1+x2 +x5 1 x1+x3 1 x2 +x4 1 x3+x6 1 x2 +x3+x6 1 xi 0，1，i=1,2,6,下使得目标函数下使得目标函数 f=cixi 最小最小.习题习题 一一 资源的最优配置策略资源的最优配置策略某工厂有某工厂有1000台机器台机器,生产两种产品生产两种产品 A,B,若投入若投入 y 台机器生

37、产台机器生产A 产品产品,则纯收入为则纯收入为 5y.若投入若投入 y 台机器生产台机器生产B 产品产品,则纯收入为则纯收入为 4y.又知又知,生产生产A 种产品机器的年折损率为种产品机器的年折损率为20%,生产生产B 种产品机器的年折损率为种产品机器的年折损率为10%,问在问在5年内如何安排各年度的生产计划年内如何安排各年度的生产计划,才能使总收入最高才能使总收入最高.习题二习题二 混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。如何根据如何根据 4位运动员的位运动员的4种游泳竞赛成绩安排混合泳接种游泳竞赛成绩安排混合泳接力队，以取得最佳成绩。力队，以

38、取得最佳成绩。蛙泳蛙泳 蝶泳蝶泳 自由泳自由泳 仰泳仰泳 甲甲 99 60 59 73 乙乙 79 65 93 87 丙丙 67 93 63 81 丁丁 56 79 86 76 习题三习题三在大约在大约1000m高空的某边长为高空的某边长为160km的正方形的正方形区域内有若干架飞机作水平飞行。区域内有若干架飞机作水平飞行。区域内每架飞机的位置和速度向量均有计算机区域内每架飞机的位置和速度向量均有计算机记录其数据，以便进行飞行管理。记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域的边缘当一架欲进入该区域的飞机到达区域的边缘时时记录其数据后要立即计算并判断是否会与区域记录其数据后要

39、立即计算并判断是否会与区域内的飞机发生碰撞。内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新如果会碰撞，则应计算如何调整各架（包括新进入的）飞机的飞行的方向角，以避免碰撞。进入的）飞机的飞行的方向角，以避免碰撞。先假定条件如下：先假定条件如下：1）不碰撞的标准为任意两架飞机的距离大于）不碰撞的标准为任意两架飞机的距离大于8km2）飞机飞行方向角调整的幅度不超过）飞机飞行方向角调整的幅度不超过3003）所有飞机飞行速度均为每小时）所有飞机飞行速度均为每小时800km4）进入该区域的飞机到达区域的边界时，）进入该区域的飞机到达区域的边界时，与区域内的飞机的距离应在与区域内的飞机的距离应在

40、60km以上以上5）最多考虑）最多考虑6架飞机架飞机6）不必考虑飞机离开次区域后的状况）不必考虑飞机离开次区域后的状况请你对这个避免碰撞的飞行管理问题建立数学请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，模型，列出计算步骤，对以下数据进行计算（方向角误差不超过对以下数据进行计算（方向角误差不超过0.010）。）。要求飞机飞行方向角调整的幅度尽量小要求飞机飞行方向角调整的幅度尽量小设该区域四个顶点的坐标为设该区域四个顶点的坐标为 (0,0),(160,0),(160,160),(0,160)记录数据为记录数据为飞机编号飞机编号 横坐标横坐标x纵坐标纵坐标y方向角方向角(0)1 150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 150 230 新进入新进入 0 0 52注：方向角指飞行方向与注：方向角指飞行方向与x轴正向的夹角轴正向的夹角