浙江科技运筹学试卷试卷8答案

本文格式为Word版，下载可任意编辑——浙江科技运筹学试卷试卷8答案浙江科技学院考试试卷

……………………名线姓订装………号…学………………级…班…业…专……浙江科技学院

200-200学年第学期考试试卷卷

考试科目考试方式完成时限拟题人审核人批准人年月日院年级专业题序一二三四五六七八九十总分得分一、填空（15×2分）1、在线性规划问题的约束方程AX=b,X≥0中，对于选定的基B，令非基变量XN=0，得到的解X=B-1b；若X=B-1b≥0，则称此基本解为基本可行解；若X=B-1b=0，则称此基本可行解为退化的解；若所有检验数均小于等于0，则此基可行解为最优解。

2、用对偶单纯形法求解线性规划问题时，根据br＜0确定xr为出基变量；根据最小比值法则θ=min{br/arj}，确定xk为进基变量。3、线性规划问题的可行解X=（，，．．．）为基本可行解的充要条件是X的正分量对应的系数列向量是线性无关。

4、已知y*为某线性规划问题的对偶问题的最优解，若y*>0，说明在最优化生产计划中对应的资源已消耗完毕。

5、平衡运输问题（m个产地，n个销地）的基可行解中基变量共有m+n-1个

；

其

中

决

策

变

量

xij

所

对

应

的

列

向

量

pij=

(0,0,…,0,1,0…,0)T.。

6、对于Max型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：

XBbx1x2x3x4x23/4017/4-11/4

则对应的割平面方程为-3/4x3-1/4x4≤-3/4。

7、用匈牙利法解分派问题时，当独立零元素的个数等于任务数或人数时则找到了分派问题的最优解；称此时独立零元素对应的效益矩阵为最优指派问题。

第页共页浙江科技学院考试试卷

8、假使某一整数规划：MaxZ=X1+X2X1+9/14X2≤51/14-2X1+X2≤1/3X1,X2≥0且均为整数

所对应的线性规划（松弛问题）的最优解为X1=3/2，X2=10/3，MaxZ=6/29，我们现在要对X2进行分枝，应当分为X2≤3和X2≥4。二、计算题（50分）

1．已知某极大化线性规划问题，其初始及最优单纯形表如下：（20分）

CjCB000XBx3x4x5σjb129812000x1x2x3x4x522100300110200112000最优解表CjCB102XBx1x4x2σjB23412000x1x2x3x4x5101/20-1/200-3/213/201001/200-1/20-1/2(1)求出对偶问题与对偶问题的最优解;解：对偶问题为Miw=12y1+9y2+8y32y1+3y2≥12y1+2y3≥2y1,y2,y3≥0

最优解为y1=1/2,y2=0,y3=1/2,w=10

第页共页

浙江科技学院考试试卷

(2)求C1的变化范围,使最优基不变;σ3=0-1/2C1≤0

σ5=0-(-1/2C1)-1≤0

所以0≤C1≤2最优解不变(3)假使b1由12变为16,求最优解.

?1/20?1/2??16??4???????则X’＝B-1b=??3/213/2??9????3?

?0????01/2????8??4?CjCB102XBx1x4x2σj102x1x3x2324B4-3412000x1x2x3x4x5101/20-1/200-3/213/201001/200-1/20-1/21001/30001-2/3-101001/2000-1/3-1此时最优解为X=（3,4,2,0,0）T2.各点之间的直接距离见表，求从1-7的最短路。（15分）1234567

第页共页

104-1250434024-2705541006-3072780浙江科技学院考试试卷

解：1234567104-1250434024-2705541006-3072780P1j(1)P1j(2)P1j(3)P1j(4)05405934105934190593419所以1－7的最短路为7，v1-v5-v6-v73.求如下图的网络的最大流和最小截集(割集)，每弧旁的数字是（cij）。（15分）解：V1

最大流＝5

第页共页

V3（2,2）V5（6,1）（4,4）（5）（4,1）（5）V2（3,3）V4（7,3）（6）V3

（2）V5（6）

V1（4）

（4）（5）

（5）

V2（3）

V4（7）

V6V6（6,2）浙江科技学院考试试卷

三、建模（20分）

1.某工厂生产三种产品，各种产品重量与利润关系如表所示，现将此三种产品运往市场出售，运输能力总重量不超过15吨，问如何安排运输使总利润最大？试建立动态规划模型，不要求求解。(10分)种类123解，设阶段K＝1，2，3

状态变量Sk为从第k个阶段到第n个阶段可以装入的体积决策变量Uk表示在第k个产品装入的件数Sk+1=Sk-vkUk阶段指标Vk＝akUk递推公式fk=opt{vk+fk+1(sk+1)}

2.已知A1，A2，A3三个矿区可分别供应煤炭200，300，400（万吨/年）。下述地区需调入煤炭：B1：100——200万吨/年，B2：200——300万吨/年，B3：为不低于200万吨/年，最高不限，B4：180——300万吨/年，已知单位运价表如表——6所示。如要求把所有煤炭分派出去，满足上述需求，又使总运费为最少的调运方案，试列出用运输问题模型求解时的产销平衡表及单位运价表（不必求解）。（15分）表—6销地产地A1A2A3销地产地A1A2A3A4产量B14780‘体积（立方厘米/件）vk423利润（元/件）ak150130200B1478B23109B36512B45617解各地的产量与销量以及单位