运筹学复习题总结.doc

运筹学复习题
一、用单纯性表求解线性规划模型
例用单纯形法求下列线性规划的最优解

解:1)将问题化为标准型,加入松驰变量x3、x4则标准型为:
2)列单纯形表。
3)解为:XT=(18,4,0,0),目标函数值:maxZ=70
解答完毕!
二、写出一般线性规划的对偶形式
非常重要的法则:
由max min时
对偶问题的约束与原问题变量一致,变量与约束相反;
由min max时
对偶问题的约束与原问题变量相反,变量与约束一致;
三、用表上作业法求解运输问题
完整步骤:
0-1整数规划建模问题
0-1变量作为逻辑变量(logical variable),常被用来表示系统是否处于某个特定状态,或者决策时是否取某个特定方案。例如
当决策取方案P时
当决策不取方案P时
1、投资场所的选定——相互排斥的计划
例 某公司拟在市东、西、南三区建立门市部。拟议中有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、背包问题
一只背包最大装载重量为50公斤。现有三种物品,每种物品数量无限。每种物品每件的重量、价格如下表:
求背包中装入每种物品各多少件,使背包中物品总价值最高。
设三种物品的件数各为x1,x2,x3件,总价值为z。
max z=17x1+72x2+35x3
. 10x1+41x2+20x3≤50
x1,x2,x3≥0 x1,x2,x3为整数
厂址选择模型
在5个备选地点中选择3处建设生产同一产品的工厂,每个地点建厂所需投资,占用农田,建成以后的生产能力如下。总投资不超过800万元,占有农田不超过60亩。如何选择厂址,使总生产能力最大。
设5个0-1变量x1,x2,x3,x4,x5,
max z=70x1+55x2+42x3+28x4+11x5
. 320x1+280x2+240x3+210x4+180x5≤800
20x1+ 18x2+ 15x3+ 11x4+ 8x5≤ 60
x1+ x2+ x3+ x4+ x5= 3
x1,x2,x3,x4,x5 为 0-1变量
用标号求解动态规划中的最短路问题
用标号法求解网络最大流问题
注:总结标号过程
1)如果在前向弧上,有fij(流量)<cij (容量),那么给 vj 标号(vi ,l(vj) ).其中 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 成为标号已检查的点。