数学规划模型的建立PPT课件

1、例2施工点 j 的坐标为njbajj, 2 , 1),( 对某材料的需求量为njqj, 2 , 1, 第 i个料场的容量为., 2 , 1,miMi 吨吨求料场的位置及各料场向各施工点的供应量，使材料运输的总吨公里最小。解 设各料场到各施工点的距离为直线距离，且各施工点可在不同料场取料。个料场坐标个料场坐标为第为第设设iyxii),(提供的材料数量提供的材料数量向施工点向施工点为料场为料场jiwij则 minjjijiijbyaxwz1122)()( mijijnjqw1, 2 , 1, njiijmiMw1, 2 , 1,njmiwij, 2 , 1;, 2 , 1, 0 总吨公里数需求限制

2、容量限制非负限制mins.t.第1页/共79页学习这一部分需注意的地方：1. 对给定的实际问题，如何作合理的假设，并建立 模型。如何处理分段函数、矛盾约束等问题。2. 怎样将一类模型化为另一类模型，易于求解。3. 同一问题可建立不同模型第二个问题不便用微分法求解，可用数学规划方法求解。第2页/共79页II II 数学规划模型的建立数学规划模型的建立数学规划模型的一般形式：)(minXfz )(nRSX TnxxxX),(21 ）或或)(max(Xfz 例如：)0(2 kkxyzmax0, 0,222 yxdyxs.t.0,| ),(222 yxdyxyxSTyxX),( 若能写出描述S的数学式

3、子，则可直接写出。这里第3页/共79页)(nRSX TnxxxX),(21 )(minXfz ）或或)(max(Xfz 目标函数可行域可行解决策变量描述S 的数学式子约束条件S 问题可行问题不可行 X最优解 z最优目标值几个概念：第4页/共79页特别：nnxcxcxcz 2211min(或 max)或 njjjxcz1minmibxatsinjjij, 2 , 1,),(.1 11212111.bxaxaxatsnn 22222121bxaxaxann mnmnmmbxaxaxa 2211），（或（或1b ），（或（或2b ），（或（或mb njxj, 2 , 1, 0 njxj, 2 , 1

4、, 0 线性规划模型或CXz minbAXts .OX 等约束第5页/共79页注：M CXz minbAXts .OX M是常数与CXz minbAXts .OX 有相同的最优解1.2.CXz minbAXts .OX CXz 0maxbAXts .OX 与有相同的最优解第6页/共79页另外：1. 取整数，称模型为整数规划模型jxjx2. 中部分取整数，称模型为混合整数规划模型jx3. 只取0或1两个值，称为 0 1 规划模型4. 目标函数或约束条件是非线性的， 称为非线性规划模型5. 若目标函数只有一个，称为单目标规划模型； 若目标函数不只一个，称为多目标规划模型。第7页/共79页nBBB2

5、1mAAA21maaa21nbbb21mnmmnnccccccccc212222111211产地销地运价例1求使总运费最少的调运方案。试建模。产量需求量42一、运输问题第8页/共79页 mjjmiiba11假设假设解的运量。的运量。到销地到销地为产地为产地设设jiijBAx则 minjijijxcz11min njiijmiaxts1, 2 , 1,. mijijnjbx1, 2 , 1,njmixij, 2 , 1;, 2 , 1, 0 产销平衡注：若产大于销，则 njiijmiax1, 2 , 1, 若产小于销，则 mijijnjbx1, 2 , 1, 线性规划模型第9页/共79页 重要结

6、论：当供应量 与需求量 均为整数时，模型的最优解 是整数解。iajb X第10页/共79页例2 自来水输送问题某市有甲、乙、丙、丁四个居民区，自来水由A、B、C由三个水库供应。四个区每天必须的基本生活用水分别为30、70、10、10千吨，但三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库向各区送水所付出的引水管理费不同（如表，其中C水库与丁区间无输水管道），其它管理费均为450元/千吨。各区用户每千吨收费900元。此外，各区用户都向公司申请了额外用水量，分别为每天50、70、20、40千吨。问公司应如何分配供水量，才能获利最多？第11页/共79页丁

7、丁丙丙乙乙甲甲CBA/230200190150190130140170220130160引水管理费(元/千吨)第12页/共79页将有关数据整理列表：丁丁丙丙乙乙甲甲CBA50605010107030/230200190150190130140170220130160水库居民区供应量生活用水额外用水40207050成水输本ijciajb160 iia300 jjb问题分析：可看成是“产小于销”的运输问题。解第13页/共79页设 xij 分别表示水库A,B,C(i=1,2,3)向居民区甲,乙,丙,丁(j=1,2,3,4)的供水量。其中X34=0.模型建立由题意目标函数为： 314111604501

8、60900maxijijijxcz可转化为： 3141minijijijxcz506050.3332312423222114131211 xxxxxxxxxxxts5030140802414332313322212312111 xxxxxxxxxxx 10107030供给限制需求限制一般问题中：供给限制用“ ”需求限制用“ ”“ ”引水管理费因160千吨水须全部输出. 4 , 3 , 2 , 1; 3 , 2 , 1, 0 jixij第14页/共79页注：为了增加供水，公司考虑改造水库，使三个水库的供水能力提高一倍，问模型将作何改动？分析：由于总供水能力为320千吨，总需求量为300千吨，水不

9、能全部卖出，所以不能将获利最多转化为引水管理费最少。须算出每千吨净利润。每千吨净利润用户交的900元其它管理费450元引水管理费/220250260300260320310280230320290CBA净利润(元/千吨)丁丁丙丙乙乙甲甲ijc第15页/共79页模型改为： jiijijxcZMax,506050.3332312423222114131211 xxxxxxxxxxxts100120100 其它同前第16页/共79页例3 最大流问题 2014151210138891012图中弧上的数字表示每小时两结点沿箭头方向的最大车流量，求到每小时的最大车流量。二、网络（规划）问题第17页/共79

10、页设 v 为从 出发的车流量，1 为 到 的车流量，ijijx则vmaxvxxts 1312.252412xxx vxxx 675747流量守恒条件1202006712 xx弧容量限制0 v)(max1312xx 去掉6757471312xxxxx 去掉若不设v,则模型有四处需修改第18页/共79页如果源、汇不止一个时，建模方法类似。可增加一个虚拟源、虚拟汇化成单源单汇的问题。 图中的结点 称为源（发点），结点 称为汇（收点）。图是单源单汇的情形。17第19页/共79页例4201345672012632658974s1220T01567求从 流出，到 的最大流量。解 设 为 到 的流量，ijx

11、ij0sx1sx01 、 为流入 、 的量，Tx5Tx6Tx7567 、 、 为流入 、 、 的量。10maxssxx 020.xxtss 131xxs 2524234202xxxxx Txxx77637 401207602 xx第20页/共79页例5 设有工作 件，人员 个，且一人做一件工作， 第 人作第 件工作的时间（或费用）为 ， 问：如何分派可使总时间（或总费用）最少。mmijcij解 本题需确定：第 人做或不做第 件工作，ij这是定性变量，首先将其定量化。设 否则否则件工作件工作人做第人做第第第, 0, 1jixijmji, 2 , 1, mixtsmjij, 2 , 1, 1.1

12、mjxmiij, 2 , 1, 11 mjixij, 2 , 1,10 ，或或01规划模型则 mimjijijxcz11min注：若 表示效益，则目标函数应极大化ijc问：各人员类不止1人， 各工作类不止1件工作， 决策变量为何？若人数“”工作件数 三、分派问题第21页/共79页四、生产活动问题(分段函数、矛盾约束等的处理方法)nAAA21mBBB21mbbb21nccc21mnmmnnaaaaaaaaa212222111211资源产品单耗资源量单位利润例6问如何安排生产使总利润最大。解 设 表示第 种产品的产量，jxj则 njjjxcz1max njijijmibxats1, 2 , 1,.

13、njxj, 2 , 1, 0 资源分配问题第22页/共79页分段函数问题例中 单位收益单位成本（可变成本）jc若还要考虑固定成本jM则第j 种产品的利润为： 000,jjjjjjxxMxcc于是引入 01变量： 否则否则，种产品种产品生产第生产第0, 1jyj0 jx即即0 jxnj, 2 , 1 设 Lj 是xj的上界，则模型改写为：第23页/共79页 njjjxcz1max njijijmibxats1, 2 , 1,.njyj, 2 , 1, 10 或或,jjyL nj, 2 , 1 混合整数规划模型等价性：（1）10 jjyx由由0 jx由Z的极大化0 jy（2）1 jy由0 jx00

14、 jjxy由由注：将目标函数变成jjnjjjyMxcz)(1 则为非线性的。 njjjyM1jx 0若不考虑固定成本，则不引入0-1变量。第24页/共79页 更复杂的分段函数的处理方法* *设B1是某种原料（单位：吨），还可以从市场上购买到不超过1500吨的原料。若购买量不超过500吨，其价格为10千元/吨；购买量多于500吨但不超过1000吨时，超过500吨的部分8千元/吨；购买量超过1000吨时，超过1000吨的部分6千元/吨。问怎样安排生产和采购？增设x为采购量，则可得采购支出（千元）： 15001000,630001000500,810005000,10)(xxxxxxxc第25页/共

15、79页)(max1xcxcznjjj 这时，目标函数为:处理法1：设三种价格的采购量分别为：321,xxx则目标函数为：)6810(max3211xxxxcznjjj 约束条件增加：500,00)500(0)500(3213221 xxxxxxx只有当 x1 =500时，才能以每吨8千元的价格购买x2(0)非线性规划模型！第26页/共79页处理法1：x321aaa1b2b3b)(xc0;1500,1000,500321 aaa.12000,9000,5000321 bbb可用端点的凸组合来表示线段上的值，如：上时有上时有在在上，上，在在,)(,2121bbxcaax1)(2122112211

16、bbxcaax为了统一表示，引入01变量 否则否则，个区间取值个区间取值在第在第0, 1kxk 第27页/共79页则0, 10)(02102211022110 innnnnbbbxcaaax 且112121210100 nnnnn 1, 1 , 0101110 niin，或或 至多两个相邻的 i取非零值可得混合整数规划模型第28页/共79页产品种类限制问题（不考虑固定成本）n种产品中只生产其中k种njjyj, 2 , 1,0, 1 否则否则，种产品种产品生产第生产第设 njjjxcz1max njijijmibxats1, 2 , 1,.njyj, 2 , 1, 10 或或,jjyL nj,

17、2 , 1 jx 0则jy01. 0kyyyn 21要求产量不小于80单位80第29页/共79页矛盾约束问题设 、 为机器1、2的可用工时（资源），1b2bn 种产品只在一台机器上加工，则以下两个约束条件是矛盾的，不能同时出现在一个模型中。 njjjbxa111, njjjbxa122若引入 01变量： 否则否则，上加工上加工在机器在机器1, 0iyi2 , 1 i设 M 是充分大的常数，则两个矛盾约束可统一在一个模型中：第30页/共79页 njjjxcz1max njijijmibxats1, 4 , 3,.;, 2 , 1, 0njxj njiijijiMybxa12 , 1,121 yy

18、2 , 110 iyi，或或一般，若m 种资源中只用其中k 种资源，则令 否则否则，种资源种资源用第用第1, 0iyimi, 2 , 1 约束条件改为： njiijijmiyMbxats1, 2 , 1,.kmymii 1第31页/共79页例7 生产存储问题（多阶段问题）某公司生产一种产品，最大生产能力为100单位，第 月的单位存储费为 元，预定的销售量和单位成本如表。求使生产成本与存储费之和最低的生产计划。 iie解先作合理假设 1月初无库存； 4月底卖完； 当月生产的不入库； 库存量无限制。假设：432176807270601207060月份单位成本ic(元)销售量id(件)第32页/共7

19、9页模型一 41jjjxcz11311)( jjiijjiiedxmin,.11 jiijiidxts3 , 2 , 1 j 4141iiiidx1000 ix. 4 , 3 , 2 , 1 i且为整数，第 j+1月初的库存量整数规划模型设 为第 月的产量， 为单位存储费，ixiie则第33页/共79页模型二若设 为第 月初的库存量， 则isi 41jjjxczminiiise 414 , 3 , 2 , 1,.1 idxsstsiiii0, 051 ss1000 ix. 4 , 3 , 2 , 1 i且为整数，增加了决策变量 ，但模型简洁了。is本问题还可建立动态规划模型第34页/共79页几

20、点说明：1. 增加投资扩大生产能力若每投资k 元可增加一个单位的生产能力。设 表示第 月的投资，iki则第 月的产量限制条件变为：i1000 ix ittkk11第 月前的投资在第 月仍起作用，ii生产投资问题。第35页/共79页2. 均衡生产问题前例中的最优月产量为：TX)60,50,100,100( 月初库存量为：TS)0 ,70,40, 0( 为使生产尽量均衡，可增加相继两个月产量差的限制：iiiizyxx 1),(0 上升的量上升的量 iy同时希望非负变量 、 越小越好。iyiz则目标函数可提为： iiiiiisczbyazmin其中a 为第 月比第 月增加一个产品要支付的费用，b 为

21、减少一个产品支付的费用，c 为库存费。i1 i)(0 下降的量下降的量 iz第36页/共79页根据要求还可提为： iiiisczbzmin iiiiscyazmin或不希望减少不希望增加第37页/共79页例8 （ P.7例1.8 ）求生产、存储、维修计划将有关数据整理列表(同例1.6)：51t113243363361008672134471ttjtaaa71j71cccj机床单耗产品台数tl月台时tb单位利润月台时台数 小时 天数。 13444 16 21如一台机床维修一次需160(台时)10(天) 16(小时) 19第38页/共79页假定： 没有轮到维修的和维修后的机床在使用期间能正常工作；

22、 维修一台机床是在某月内完成，不会跨入下一月。设 第 月初、第 种产品的库存量，ijsij 第 月、第 种产品的产量，ijxij 第 月、第 种机床的维修量。itkit 61716171maxijijijijjasxcz,., 1 jiijijijsdxsts 7 , 1; 6 , 1 ji,16071ittjijtjkbxa 5 , 1; 6 , 1 ti5 , 1,61 tlktiit需求限制资源限制维修限制且为整数且为整数titlk 0i 第 月维修哪几台机床可由人安排，只安排未维修的；第39页/共79页例9 （下料问题）某厂要做100套钢架，每套由长为2.9米，2.1米和1.5米的圆钢

23、各一根组成。已知原料长7.4米。问如何下料使原料最省。试建模。问题分析：“最节省”可以是“所用原料根数最少”，也可以是“余料最少”。 基于前者建模。一根原料钢管有不同的切割组合.。找出每一种组合用去多少根原料钢管。所以首先列出所有可能组合即“模式”。第40页/共79页解 将8种下料方案列表:101302340210321021110000876543215 . 11 . 29 . 2方案根数长度合计 6.0 6.6 7.2 6.3 7.4 6.5 7.1 7.3余料 1.4 0.8 0.2 1.1 0 0.9 0.3 0.1100100100需求量则则种方案所用原料根数，种方案所用原料根数，为

24、第为第设设ixi 81miniixz1002.8765 xxxxts10023276432 xxxxx1003234865321 xxxxxx8 , 2 , 10 jxj且为整数且为整数第41页/共79页若希望余料最少，则87643211 . 03 . 09 . 01 . 12 . 08 . 04 . 1xxxxxxxz 余料超过1.5米 约束条件取“100” 设需 根原料，第 根下第 种圆钢 根，nijijx3 , 2 , 1;, 2 , 1 jni3 , 2 , 1, 2 , 13 , 2 , 1,100, 2 , 1, 4 . 75 . 11 . 29 . 2.min1321 jnijx

25、nixxxtsnniijiiin是决策变量，而线性规划模型中是定数！该模型不易计算！以下几种作法欠妥：第42页/共79页 客户拟定的设施地址（1）离散型选址问题（2）连续型选址问题设施的地址未拟定，可选在所论区域（很大）的任何地方。问题：第 个设施是否需修建？若要修建，应为周围哪些客户服务？ 选址 分配问题i五、选址问题第43页/共79页例10（离散型）施工点 j 对某材料的需求量为njqj, 2 , 1, 第 i个料场的容量为., 2 , 1mi 的单位运费 (元/ 吨). 求使总费用最少的场址。可基于两种考虑建模：2 施工点 只能在某一料场获取全部所需材料。j1 施工点 可在任何料场获取部

26、分材料，以满足需求；j建场费为di 元,解 1 假定： 任何施工点到任何料场的道路是通的； 施工点 可在任何料场获取部分材料，以满足需求；j拟定m 个地方建料场，,吨吨iMijc为地址 到施工点 ij一个大型工程有n个施工点，第44页/共79页提供的材料数量提供的材料数量向施工点向施工点为料场为料场设设jixij则 miiiminjijijydxcz111 mijijnjqx1, 2 , 1, njiiijmiyMx1, 2 , 1,njmixij, 2 , 1;, 2 , 1, 0 总费用需求限制容量限制非负限制mins.t. 否则否则，建料场建料场在地址在地址0, 1iyimiyi, 2

27、, 110 ，或或混合整数规划模型第45页/共79页2假定： 任何施工点到任何料场的道路是通的； 施工点 只能在某一料场获取全部所需材料。j设 否则否则，供料供料向施工点向施工点地址地址0, 1jixij 否则否则，建料场建料场在地址在地址0, 1iyi则 miiiminjijijydxcz111, 11 miijx njiiijmiyMx1, 2 , 1,总费用需求限制容量限制mins.t.njmixij, 2 , 1;, 2 , 1, 10 或或非负限制miyi, 2 , 110 ，或或jqjqnj, 2 , 1 01规划模型第46页/共79页由于区域很大，所以施工点到料场间的距离视为直线

28、距离njbajj, 2 , 1),( 例11（连续型）设工程所涉及的区域很大，第 j 个施工点的坐标为：单位运费为c (元/吨/公里),欲建的m个料场地址未拟定，其余条件与例11相同。求使总费用最少的场址。解 基于第二种考虑建模设料场 的坐标为i与前例相同与前例相同iijiiyxsr,),( miiiminjjijijijydbsarcqxz11122)()(mins.t. 同前例 对 可不作非负限制，称为自由变量iisr ,非线性规划模型第47页/共79页注：(1) 若m个料场都要修建，则不设01变量iy（3）若区域小，且道路呈网状，则使用矩形距离|jijibsar （2）指标不一定是“费用

29、”，可以是“客户”到“设施” 的最大距离最小等。相当于将 取成1。iy目标函数中的常数项 应去掉。 miid1第48页/共79页), 2 , 1)(,(nibaiii 个个用用户户的的坐坐标标为为设设第第解解若希望用户到中心的最大距离越小越好，则 |maxmin1,iiniyxbyax且为整数且为整数,0 ,0.byaxts 11220),(yx),(iiba也可以是用户到中心的距离之和最小建模。均在第一象限内，例12 设某城市的街道成纵横交叉的网状，今欲建一物资供应中心，供n个用户。问该中心建在什么位置合适。试建模。),(yx处，坐标为处，坐标为供应中心建在街道拐角供应中心建在街道拐角问题！

30、第49页/共79页以下几种作法不妥： 用直线距离 没设“中心”建在街道拐角处 将“中心”取在坐标原点，) |(|min1 niiiyxz决策变量？ 设第 个用户的需求量为 ，单位运费为 ，得iiqic iiiiibyaxqcz|)|(|min（总运费）第50页/共79页例13某公司有工厂A1,A2生产某种产品，生产能力分别为Q1,Q2,有四个容量为Mk的仓库Bk(k=1,2,3,4)存放该产品，工厂和仓库均可向n个客户Cj(j=6,7,n+5)供货，客户需求量为qj(j=6,7,n+5).现公司打算：扩建仓库B1,其月费用为e1，库容量增加M；新建仓库B5,月费用为e5，库容量为M5;关闭仓库

31、B2或B3,关闭后可节约费用e2或e3;并要求总的仓库数不得超过4个。已知工厂Ai向仓库或客户供货的运费每单位为cij(i=1,2;j=1,2,3,4,5为向仓库供货的运费，j=6,7,n+5为向客户供货的运费)。第k个仓库向第j个客户供货的单位运费dkj(k=1,2,3,4,5; j= 6,7,n+5)。以上费用均由公司负担。问公司该作何选择可使总费用最少。第51页/共79页解为便于理解，先作网络图。1A2A1B5B6C5 nC11c16c15c5, 1 nc21c26c25c5,2 nc16d5, 1 nd56d5,5 nd工厂仓库客户第52页/共79页可仿运输问题，将有关数据列表。565

32、1 nCCBB5,22625215, 1161511 nncccccccc5,5565, 116 nndddd5121BBAA21QQ51MM 56 nqq产地销地运价总量)5, 6(),5 , 1( njCjBAjjxiij设)5, 6( njCBjykkj 211iix 215iix2 , 1 i5 , 1 k9第53页/共79页, 0, 111 否则否则扩扩B )3 , 2(, 0, 1 iBii，否则否则留留 。否则否则建建 , 0, 155B 5533221151562151min eeeeydxczknjijkjinjijij 2 , 1,.51 iQxtsinjij5 , 1,2

33、156 kxyiiknjkj5, 6,5121 njqyxjkkjiij,11211 MMxii ),5 , 3 , 2(21 jMxjjiij ,4214Mxii 2532 产量限制客户需求限制仓库数量限制第54页/共79页六、曲线拟合问题（去绝对值符号、化极大极小化模型为线性规划模型）已知变量 y （随机变量）随 x（非随机变量）变化。并已知一组样本观测值：niyxii, 2 , 1, ),( 求近似表示 y 与 x 之关系的经验方程回归方程。 ),(iiyx),(iiyx1对观测值作散点图，若点子沿一直线变化，则可用直线方程bxay 作为经验方程。（回归方程）2所给的准则不同，求出的a,

34、b 也不同。第55页/共79页常用方法 最小二乘法： niiibxay12)( niiyz12)(iy求使最小的a,b.由 00bzaz可解得 a,b。求回归直线这一过程，称为拟合 一条回归直线。于是得到回归方程bxay iibxay 称函数值： 为回归值。 所求回归方程能否用于预测和控制，还需作假设检验。类似可拟合回归曲线和回归平面。第56页/共79页例14（1）拟合一条回归直线，使回归值与观测值的绝对偏差之和最小；（2）拟合一条回归直线，使回归值与观测值的最大偏差最小。解 设回归方程为：bxay （1）依题意，求解 niiibxayz1| )(|min这是一个无约束的非线性规划模型，不便用

35、微分法处理。已知变量y随变量x变化，并已知一组观察值., 2 , 1),(niyxii 去掉绝对值符号，化为线性规划模型第57页/共79页令 )(| )(|21iiiiibxaybxayu )(| )(|21iiiiibxaybxayv 0 0 iiiivubxay | )(|iiiivubxay )(则模型化为： niiivuz1)(minniyvubxatsiiii, 2 , 1,. nivuii, 2 , 1, 0, 为自由变量。为自由变量。ba,是2n+2个决策变量，n个约束方程的线性规划模型。第58页/共79页（2）依题意，得一极大极小化模型：| )(|maxiiibxay min

36、a,b| )(|maxiiibxayu 令因对任何i都有：| )(|iibxayu 于是得非线性规划模型：uminnibxayutsii, 2 , 1, 0| )(|. 0 u又因对任何i都有：ubxayuii )(化线性规划模型第59页/共79页niubxaytsii, 2 , 1, 0)(. 0 uumin则得线性规划模型：niubxayii, 2 , 1, 0)( 该模型中只有三个决策变量。第60页/共79页例15某公司上午8点到21点各时段需要的服务人员数量如表1，四个班次的作息时间及月工资如表2。求既满足需求又使公司所付工资总额最少的人员安排。65432100:2100:1800:1

37、800:1600:1600:1400:1400:1200:1200:1000:1000:8 102030102520序号时间区间需求人数表1七、人员时间安排问题第61页/共79页432100:2100:1200:2100:1200:1700:800:1700:8 00:1800:1700:1700:1600:1400:1300:1300:12 900900800800班次工作时间休息时间月工资表2解利用表1、表2的各时间区间端点，将营业时间区间细分，并用“1”表示工作，“0”表示休息，得一关联表（表3）。第62页/共79页00:2100:1800:1800:1700:1700:1600:160

38、0:1400:1400:1300:1300:1200:1200:1000:1000:8 1020203010102520110001001011111111011110001100114321班 次时 段需求人数表3列给出了各班在哪几个时段工作，行给出了各时段有哪几个班在工作。第63页/共79页设 为第 班安排的人数ixi)4 , 3 , 2 , 1( i则得整数规划模型：4321900900800800minxxxxz 25.21 xxts10432 xxx10431 xxx304321 xxxx20421 xxx203 x1043 xx 且为整数，0 ix4 , 3 , 2 , 1 i建该

39、模型的关键是：找出各班次工作的关联表，根据关联表写出约束条件。有多余的约束条件！第64页/共79页例16 （选课策略）某校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、学分、所属 类别和先修课要求如表。问：毕业时，学生最少可以学习哪些课程？第65页/共79页编号 名称 学分 所属类别 先修课要求1 微积分 5 数学2 线性代数 4 数学3 最优化 4 数学；运筹学 微积分；线代4 数据结构 3 数学；计算机 计算机编程5 应用统计 4 数学；运筹学 微积分；线代6 计算机模拟 3 计算机；运筹学 计算机编程7 计算机编程 2 计算机8

40、预测理论 2 运筹学 应用统计9 数学实验 3 运筹学；计算机 微积分；线代课程情况表第66页/共79页建立课程与课程类别的关联表：110110100101101000000011111类别数学计算机运筹学课程微积分 线代 优化 结构 统计 模拟 编程 预测 实验 需求量2329 , 2 , 10, 1 iixi，否则否则，门课门课选修第选修第则得01规划模型：是前例中需求量为2，3，2的特别情形。解第67页/共79页编号 名称 先修课要求1 微积分 2 线性代数 3 最优化 微积分；线代4 数据结构 计算机编程5 应用统计 微积分；线代6 计算机模拟 计算机编程7 计算机编程 8 预测理论

41、应用统计9 数学实验 微积分；线代课程情况表第68页/共79页 91miniixz课程总数类别（需求）限制23297649865354321 xxxxxxxxxxxxxx.ts先修要求)()()(jixxji 先修先修后修后修9 , 2 , 1, 10 jxj或或13xx 23xx 74xx 020002002219587621574213 xxxxxxxxxxxxxxx注意表述方法！第69页/共79页例17 一个生产问题，有关数据如表。问如何安排生产可使总利润最大，产量之和最小。要求第二种原料用完。CBA0124546488010080单位利润产品原料单耗甲 乙总量解 设 为甲，乙的产量21,xx则211minxxz 21210080maxxxz 8054.21 xxts482421 xx61 x0,21 xx双目标规划模型一般形式：)(minXQ)(maxXROXMXFts )(.矛盾的八、线性多目标规划模型第70页/共79页化成单目标规划模型化法一)(minXQaXRts )(.OXMXF )(或bXQts )(.)(maxXROXMXF )(化法二 )()1()(minXRXQ OXMXFts )(. 为目标权重或偏好系数。 均可看成参数，对不同的参数值求出最优解，然后加以讨论，选出满意解。 ,ba第71页/共79