数学建模案例分析--最优化方法建模4运输投资与聘用

§4运输、投资与聘用钢铁、煤炭、粮食等物资有若干生产基地和消费点，如何根据已有的交通网安排运输方案，使总运费最少，是典型的运输问题。例7某种物资有m个生产地点（称产地）mAAA,,,21和n个消费地点（称销地）nBBB,,,21。已知iA的供应量为),,2,1(miai，jB的需求量为),,2,1(njbj，从iA到jB的运价（单位物资）为ijc，问如何制定运输方案，即从iA到jB的运量为多少，使总运费最少。设从iA到jB的运量为ijx，则二者之间的运费为ijcijx，记总供应量为maaaa21，总需求量为nbbbb21，如果ba，即该物资产销平衡，则问题很容易归纳成ijminjijxcZMin11（1）miaxtsinjij,,2,1,..1（2）njbxjmiij,,2,1,1（3）njmixij,2,1,,,2,1,0（4）其中（2）式表示从iA运往各销地的物资之和恰为iA的供应量),,2,1(miai，（3）式有相对应的含义。这显然是线性规划模型，其约束条件（3）、（4）的系数矩阵比较简单，这类问题求解比较简单。如果ba，即产大于销时，（2）式应改为miaxinjij,,2,1,1或可设一个虚拟销地1nB，其需求量（实际上是贮存量）为ba，令从iA到1nB的运价1,nic为零，从而化为产销平衡问题。运输问题还可以有更复杂的情况，譬如可以将各产地的物资集中在若干点再运出，可以先集中运往若干销地再分散；除产、销地外，还可以设若干中间站进行转运。这时应知道各产地、中间站及各销地之间的运价（不存在运输线路时可设运价为一充分大的正数，同一地点的运价设为零）。若有k个中间站，记nkml，则可扩大为有l个产地和l个销地的运输问题。因为原有的产地、销地及增加的中间站，在扩大的问题中都既是产地，又是销地，记运价为pqc，运量为),,2,1,(lqpxpq，则目标函数与（1）类似：lplqpqpqxcZ11（1’）而在产销平衡ba条件下，约束条件（2）、（3）应改为lqppqlmpampaax1,,1,,,2,1,(2’)lkmqabkmqaxqlppq,1,,,2,1,1（3’）即原有产地),,2,1(mp的供应量增加总产量a，同时设其需求量),,2,1(mq也为a；中间站的供应及需求),,1,(kmmqp均为a；原有销地的需求量),,1(lkmq增加a，同时设其供应量),,1(lkmp也为a。（1´）~（3´），（4）仍可用运输问题的方法求解。如何投放资金使一段时间后获得最高的回报，是金融活动中的问题之一，这里只讨论最简单的情况。例8现有一笔资金S，今后5年内有以下项目的投资可供选择：项目A：若每年初投资1元，则两年后收回本利共)1(a元；项目B：只能在第2年初投资，第5年末收回本利的)1(b倍，但投资额不能小于R；项目C：只能在第3年初投资，第5年末收回本利的)1(c倍，但投资额不能超过Q；项目D：每年初可购1年期债券，利率d。问如何确定每年初这些项目的投资，使５年末的本利总额最大。用)5,4,3,2,1(,,,iDCBAiiii分别表示第i年初这4个项目的投资额，我们逐年讨论：1i，手中资金S只能投资A，D，并且D可每年回收，故不应留有闲滞资金，于是SDA11（1）2i，第1年末只有D可收回1)1(Dd，而A，B，D均可投资，有1222)1(DdDBA（2）3i，第2年末A可收回1)1(Aa，D可收回2)1(Dd，可投资A，C，D，有21333)1()1(DdAaDCA（3）4i，类似地有3244)1()1(DdAaDA（4）5i，只能投资Ｄ435)1()1(DdAaD（5）再加上对B、C投资额的限制QCRB32,（6）及)5,4,3,2,1(0,,,iDCBAiiii（7）第5年末的本利总额应为5324)1()1()1()1(DdCcBbAaZ（8）问题归结为在条件（1）~（7）下求)5,4,3,2,1(,,,iDCBAiiii，使（8）最大的线性规划模型。部门如何聘用雇员使效率最高或费用最少，其思路与投资问题相近，用下例说明。例9邮局一周中每天需要不同数目的雇员，设周i)7,,2,1(i至少ia人，又规定应聘者连续工作5天，问邮局每天聘多少雇员才能满足需求，又使聘用总人数最少。考虑进一步的问题：上述指全时雇员（每天工作8小时）。如果邮局也可以聘用半时雇员（每天工作4小时，也需连续工作5天），设全时和半时雇员的工资分别为每小时3元和2元，并且限制半时雇员的工作量不应超过总工作量的四分之一，问邮局如何安排聘用方案，使所付工资总额最少。由于每个雇员需连续工作5天，邮局聘用总人数不是每天聘用人数之和。定义周一开始工作的雇员为ia)7,,2,1(i。目标函数——聘用总人数为721xxxZ（1）由于除了周二和周三开始工作的之外，其余都会在周一工作，所以周一至少应有1a人的约束应表示为176541axxxxx（2）类似地有276521axxxxx（3）376321axxxxx（4）474321axxxxx（5）554321axxxxx（6）665432axxxxx（7）776543axxxxx（8）721,,,xxx为正整数（9）形成在条件（2）~（9）下求（1）式的Z最小的整数线性规划模型。对于进一步的问题，设上述的721,,,xxx为全时雇员人数，类似地记721,,,yyy为半时雇员人数，则目标函数——总工资为)(542)(583721721yyyxxxS（10）其中3和2分别是全时和半时雇员的小时工资，8和4为小时数，而5是（连续）工作的天数。约束条件（2）式应改为17417418)(4)(8ayyyxxx(11)（3）~（7）式应作类似的改动（略）。最后，再加上半时雇员工作量不超过总量四分之一的限制)(825.0)(54721721aaayyy（12）721,,,xxx,721,,,yyy为正整数（13）形成新的整数线性规划模型。