浙江科技学院考试试卷
浙江科技学院
学年 第 学期考试试卷卷
考试科目 考试方式 完成时限 拟题人 批准人 年 月 日 系 年级 专业
班级 学号 姓名
题序 一 二 三 四 五 六 七 八 九 十 总分 得分 命题：
一、 填空题（2×10=20分）
1、用表上作业法求解某运输问题，若已计算出某空格的检验数为-5，则
其经济意义是 在该空格增加一个运量总运费将减少5 若从该空格调整，设调整量为2，则调后可使总运费下降 10 。 2、假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么D和B的关系为 D 包含 B 。
3、已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X3,X4,X5为松驰变量。
XB b X1 X2 X3 X4 X5 X4 3 0 0 -2 1 3 X1 4/3 1 0 -1/3 0 2/3 X2 1 0 1 0 0 -1 Cj-Zj 0 0 -5 0 -23 3???21??-1
问：（1）写出B=??1/3.02/3?
?00?1???
(2)对偶问题的最优解： Y＝（5，0，23，0，0）T
(3)аZ*/аb1= 5 ,这个数值的经济含义是 影子价格
第 1 页 共 7 页
浙江科技学院考试试卷
4、
V2 V4
V1 V6
V3 V5
v1?011000???v2?001000?v3?000010?? 1）请写出该图的邻接矩阵 ?v4?010001??v5?010101???v6?000010??2）V1 的入次为 0 ；V5的出次为 2 。
二、 计算题（62分）
1. 考虑如下线性规划问题（24分） Max z=-5x1+5x2+13x3 s.t. -x1+x2+3x3≤20
12x1+4x2+10x3≤90 x1，x2， x3≥0 回答以下问题： 1）求最优解
2）求对偶问题的最优解
3）当b1由20变为45，最优解是否发生变化。
4）求新解增加一个变量x6，c6=10，a16=3，a26=5，对最优解是否有影响 5）c2有5变为6，是否影响最优解。
答：最优解为 1) Cj -5 5 13 0 0 θ CB XB b X1 X2 X3 X4 X5 0 X4 20 -1 1 3 1 0 20/3 0 X5 90 12 4 10 0 1 9 第 2 页 共 7 页
浙江科技学院考试试卷
Cj-Zj -5 5 13 0 0 13 X3 20/3 -1/3 1/3 1 1/3 0 20 0 X5 70/3 46/3 22/3 0 -10/3 1 70/22 Cj-Zj -2/3 2/3 0 -13/3 0 13 X3 185/33 -34/33 0 1 2/11 -1/22 5 X2 35/11 23/11 1 0 -5/11 3/22 -68/33 0 0 -1/11 -1/11 最优解为X1=185/33, X3=35/11
2)对偶问题最优解为
Y＝（1/22,1/11,68/33,0,0）T 3)
当b1=45时 X= 45/11 -11/90 由于X2的值小于0，所以最优解将发生变化 4）P6’=(3/11,-3/4)T σ6=217/20>0
所以对最优解有影响。 5）当C2=6 σ1=-137/33 σ4=4/11 σ5=-17/22
由于σ4大于0所以对最优解有影响
2.某公司在三个地方的分厂A1、A2、A3生产同一种产品，需要把产品运送到四个销售点B1、B2、B3、B4去销售。各分厂的产量、各销售地的销量和各分厂运往各销地的每箱产品的运费如表。(13分)
产 销 B1 A1 A2 A3 销量/t 21 10 23 400 B2 17 15 21 250 B3 24 30 20 350 B4 25 19 22 200 产量/t 300 450 450 问应如何调运,可使得总运输费最小? 解：
初始解为
第 3 页 共 7 页
浙江科技学院考试试卷
A1 A2 A3 销量/t B1 400 400 B2 200 50 250 B3 350 350 B4 100 100 200 产量/t 300 450 450
计算非基变量检验数
A1 A2 A3 销量/t B1 9 0 6 400 B2 0 0 -1 250 B3 9 17 0 350 B4 0 -4 0 200 产量/t 300 450 450
由于X24,X32的检验数小于0所以不是最优解 把X24作为新的基变量得
A1 A2 A3 销量/t B1 400 400 B2 250 250 B3 350 350 B4 50 50 100 200 产量/t 300 450 450
重新计算检验数
A1 A2 A3 销量/t B1 5 0 10 400 B2 0 4 7 250 B3 1 3 0 350 B4 0 0 0 200 产量/t 300 450 450
由于所有的检验数都大于等于0，所以已经得到最优解
3. 有5个工人，要指派他们分别完成5项工作，每人做各项工作所消耗的时间如下表：(10分)
第 4 页 共 7 页
浙江科技学院考试试卷
工作 A B C D E 工人 甲 7 9 17 14 10 乙 6 7 14 6 10 丙 4 8 7 15 12 丁 6 9 12 8 7 戊 6 9 12 10 6 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？（8分）
答：最优解为
X= 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 4.求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（15分）
V1
(5,0) (3,3)
(3,3)
VS （4,1） V2
(4,0) (9,3) (8,4) V3 Vt
(6,0) 最大流为：14
V1 (5,3) (3,3) (3,0) V2 Vs (4,4) (4,1) (9,7) (8,8) Vt V3 (6,6)
第 5 页 共 7 页