运筹学复习题总结

《运筹学复习题总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、运筹学复习题一、用单纯性表求解线性规划模型例用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:2）列单纯形表。3）解为：XT=（18，4，0，0），目标函数值：maxZ=70解答完毕！二、写出一般线性规划的对偶形式非常重要的法则：由maxmin时对偶问题的约束与原问题变量一致，变量与约束相反；由minmax时对偶问题的约束与原问题变量相反，变量与约束一致；三、用表上作业法求解运输问题完整步骤：四、0-1整数规划建模问题0-1变量作为逻辑变量(logicalvariable),常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定

2、方案。例如当决策取方案P时当决策不取方案P时1、投资场所的选定——相互排斥的计划例5.5某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai(i=1，2，…，7)可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?解题时先引入0-1变量xi(=1,2，…，7)2、指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成

3、绩（百分制）如表所示，如何安排他们的工作使总成绩最好。设数学模型如下：目标函数为要求每人做一项工作，约束条件为：每项工作只能安排一人，约束条件为：变量约束：3、背包问题一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。设三种物品的件数各为x1，x2，x3件，总价值为z。maxz=17x1+72x2+35x3s.t.10x1+41x2+20x3≤50x1，x2，x3≥0x1，x2，x3为整数4、厂址选择模型在5个备选地点中选择3处建设生产同一产品的工厂，每个地点建厂所需投资，占用农

4、田，建成以后的生产能力如下。总投资不超过800万元，占有农田不超过60亩。如何选择厂址，使总生产能力最大。设5个0－1变量x1，x2，x3，x4，x5，maxz=70x1+55x2+42x3+28x4+11x5s.t.320x1+280x2+240x3+210x4+180x5≤80020x1+18x2+15x3+11x4+8x5≤60x1+x2+x3+x4+x5=3x1，x2，x3，x4，x5为0－1变量五、用标号求解动态规划中的最短路问题六、用标号法求解网络最大流问题注：总结标号过程1）如果在前向弧上，有fij（流量）

5、l(vj)=min[l(vi),cij–fij].这时，vj成为标号未检查的点。（2）如果在后向弧（vj,vi）上，有fji>0,那么给vj标号（-vi,l(vj)）.其中l(vj)=min[l(vi),fji].这时，vj成为标号未检查点。于是vi成为标号已检查的点。注意：考试时不需要写出以上全过程，只要在图上标号，然后画出调整后的图，最后写出最大流量v（f*）就可以了！