2015年运筹学补考复习知识点归纳及样题

《2015年运筹学补考复习知识点归纳及样题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《运筹学》补考复习知识点归纳及样题总体要求：1、2小时，闭卷考试；2、只需带黑色签字笔、铅笔、橡皮，不要带书包、纸来。绘图部分可以用铅笔，其余部分不得用铅笔、圆珠笔答题。3、五道题目，每题20分，每题小问可能包含计算、简答、填空、作图。比照样题答题，解题步骤不规范、说明不清楚要扣分。4、以下给出的全部是样题，而不是原题。需要你比照样题复习、掌握课件中讲过的所有知识点。样题中不可能将所有考点都告诉你。填空填写计算表达式而非公式。5、考试时间和地点：开学的第一周，地点等候通知；6、考试无须带计算器，但你自己还是需要有一定的笔算能力。7、遵守考试纪律，作弊

2、严惩不贷。一、线性规划之“运输问题”的建模与求解1、样题：已知某运输问题其供销关系及单位运价、各产地产量、各销地销量如表1所示，问如何调运物品，使得总运输费用（单位：百元/万件）最小？表1产销平衡表和单位运价表销地Bj产地AiB1B2B3产量（万件）A14258A23537A31334销量（万件）485要求：（1）请建立该问题的线性规划模型；（2）如果有必要再化为标准问题。（3）用表上作业法求解：用最小元素法确定初始方案（如果每一步划线之初同时有多个最小运价元素，请从行、列标号最小的元素开始进行分配；如果未进行到最后一步但需要补充0元素作为基变量，请

3、加在与该剩余最小元素所画十字线上运价最小且未分配运量的位置）；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整（如果调整后得到多个0元素，将对应运价最小的0元素保留为基变量），直至求出最优方案。解：（1）设从产地Ai调运到销地Bj的物品为xij万件，可建立如下线性规划模型：（2）∵总产量=8+7+4=19>总销量=4+8+5=17，所以这是产大于销的非标准运输问题。可增加虚拟销地即库存积压仓库B4，各个产地到它的单位运价都是0，它的虚拟销量即生产过剩量为2万件（=19-17）。（3）第一步：用最小元素法确定初始方案，如下所示：第

4、二步：求非基变量检验数，验证初始方案是否最优。法一：用位势法求检验数。求解见表2所示：表2销地产地B1B2B3B4UiA1432055000A2-1053030-33A3013331000Vj1200因为min(σ11,σ13,σ21,σ24,σ33,σ34

5、σij<0)=σ24=-3<0，所以初始方案并非最优方案，需进一步调整，x24为进基变量。σ24表示如果产地A2增运1万件物品给虚拟销地B4，将导致初始方案总运费减少3百元。法二：用闭回路法求非基变量检验数σ11=4-0+0-1=3；σ13=5-3+5-2=5；σ21=3-5+2-0+0-1=-

6、1；σ24=0-5+2-0=-3σ32=3-2+0-0=1；σ33=3-3+5-2+0-0=3（注：图中画出了非基变量x21的闭回路）；下面“验证初始方案是否最优”的分析同“法一”。第三步：求θ值，调整初始方案，得到改进方案二X1。过程如下：以X24作为进基变量，由其所在闭回路的偶数序号格调运量确定调整量θ＝min(2,2)=2，按照“奇加偶减”的原则所示进行调整，选择x22作为出基变量但保留调整后为0运量的x14。用伏格尔法求出的初始方案就是调整方案X1。用位势法可求出方案二X1的非基变量检验数，如表3所示：表3销地产地B1B2B3B4UiA143

7、2052000A2235303000A3010331000Vj1230因为所有非基变量检验数都不小于0但σ33=0，所以本题有无穷多最优解。再以x33为进基变量比照上述方法进行方案调整，可得到另一个最优方案，如下：，这个方案实际上与调整方案X1是相同的。决策结论：产地A1向销地B2调运物品8万件；产地A2向销地B3调运物品5万件；产地A3向销地B1调运物品4万件；产地A2存在过剩生产物品2万件，存放在积压仓库B4。最小总运费=8×2+5×3+2×0+4×1=35（百元）。2、复习知识点：（1）产大于销、或者销大于产的运输问题建模（第三版89页（第4版

8、104页）“模型可写成”一直到“由于总的产量”之前的模型这是“产大于销”的情形；如果是第二种情况，则模型约束条件中的符号变为:“=ai”、“

9、作业法求标准运输问题最优解的方法：用最小元素法确定初始方案；用位势法或者闭回路法求变量检验数并能据此判别当前