搜索
P15～P18作业4图论（组合优化）实验1，设备更新问题（题略）设备更新可归结为加权最短路径问题，节点为每年可做的决策，各边权比为决策当年费用，最短路径即为最佳决策策略。决策图为：（假设同一年内使用一台且只使用一台机器）每个节点决策计为Vij（i为第i年购买新设备，j为购买后使用年数）相应路径上的成本（权值）计为Wij，则据题意有：Vij∈{i=1，2，3，4，5；j=1,2,3,4}W11=100-17.2+1.5-50=34.3W12=100-15.5+1.7+1.5-30=57.7W13=100-14+1.5+1.7+1.8-10=81W14=100-12.2+1.5+1.7+1.8+2.2-5=90W21=100-15.5+1.7-30=56.2W22=100-14+1.7+1.8-10=79.5W23=100-12.2+1.7+1.8+2.2-5=88.5W31=100-14+1.8-10=77.8W32=100-12.2+1.8+2.2-5=86.8W41=100-12.2+2.2-5=8用Lingo软件求解为：根据计算结果有W15=90为最佳策略，即在使用2年后购买新设备并在第6年末卖掉。2，汽车租赁（题略）根据条件，每辆车的单位移动成本相同，因此可以简化为∑（各代理点调整车辆数∗移动距离）的最小值的问题。设决策变量为Xij，i为调整出代理点，j为调整入代理点。Xij〉0整数约束条件为：i∈{2，5，8，9}j∈{1，3，4，6，7，10}以及各代理点调整出车辆数及调整入车辆数即∑𝑋2𝑗=13−6=7∑𝑋𝑖1=10−8=2……Lingo求解为：根据求解为最低费用234.6*5*1.3=1524.9元最佳车辆调配方案为：1-3:11-6:51-7:15-4:38-10:49-1:29-3:39-10:13，饮料厂的生产与检修计划（题略）总费用最小则第四周结束后库存为零。且每周末的库存量为下周开始的库存量。设每周生产量为Xi（i=1，，4），每周末的库存量为Yi（i=1，，，4）则总费用（目标函数）为min=∑（Xi∗Ci+0.2∗Yi）Ci为每月制造成本。约束条件为每月销售量：X1-Y1=15X2+Y1–Y2=25X3+Y2–Y3=35X4+Y3=25及最大生产量的线性规划问题Lingo建模求解为：则根据求解结果有生产计划为：第一个月15第二个月40第三个月25第四个月20，总费用为528。4，指派问题（题略）（一）确定每名工人的最佳工作方案设决策变量为Xij，i为第i个人，j为第j项工作，Xij∈{0，1}0为不承担，1为承担。同时，对无法完成的工作，假设费用为10000，这样在最小成本中被舍弃。用Lingo求解为：即最低成本为140元，工作分配为：甲完成D，乙完成C，丙完成B，丁完成A（二）假设戊替换甲，则Lingo求解为：即最低费用为16元，同理代替其他三位后最低成本分别为150120130，所以可以让戊代替丙，最低费用为120元（三）同样的方法，假设用工作E替代工作A,则Lingo求解为：最低费用为80元。相同算法，分别代替工作BCD后最低费用为130，120，110。因此可优先于A，最低费用为80元5，工件加工问题(题略)设决策变量为Xij（i=1…6,j=1…6,i≠j）i为当前使用刀，j为换用的下一把刀，且Xij∈{0,1}0为不使用，1为使用同时用TIMEii=999约束iLingo建模：数据：用TIMEii=999约束i≠j目标函数：min=@sum(arrange:time*x);约束条件：@for(cur(i):@sum(next(j):x(i,j))=1);没把刀有一次换到@for(next(j):@sum(cur(i):x(i,j))=1);每把刀都能换到一次求解为：即最佳换刀顺序为1-6-5-2-3-4-1最短换刀时间为8分钟6，最优通信连线（题略）假设Wij为i代理点到j代理点的距离，则Wij=|Xi-Xj|+|Yi-Yj|决策变量为Xij={0，1}0为不连通，1为连通。则Wij最小即为最佳方案Lingo求解为：根据求解结果，最佳方案为9---1---8----3------4-----510--7267，旅行线路问题