上海海洋大学 运筹学试卷

上海海洋大学试卷（答案） 学年学期 2010~ 2011学年第 一 学期 考核方式 考试 课程名称 运筹学 A/B卷 （ A ）卷 课程号 1107401 学分 2 学时 32 题号 一 二 三 四 五 六 七 八 九 十 总分 分数 阅卷人 姓名： 学号： 专业班名： 一、[
]某工厂利用原材料甲、乙、丙生产产品A、B、C，有关资料如下表所示 三种原材料生产三种产品的有关数据 A B C 每月可供原材料（公斤） 甲 3 2 1 200 乙 1 2 3 400 丙 2 1 1 300 每件产品利润（元） 5 1 4 问： 求使该厂获利最大的生产计划数学模型；
将此数学模型化为标准型；
写出一基矩阵，并求出对应的基解，判别是否为基可行解；
用单纯形法求最优解；
写出线性规划的对偶问题；
求对偶问题的最优解．
若增加二公斤原材料甲，总利润增加多少？
设原材料乙的市场价格为1.5元/公斤，若要转卖原材料乙，工厂应至少叫价多少？为什么？
【解】（1）设 x1、x2、x3分别为产品A、B、C的月生产量，数学模型为

（2）


（3）基矩阵
，对应的基变量
，基解 EMBED Equation.3 
 为基可行解。  EMBED Equation.3 
 （4）最优单纯形表：
最优解X=（25，0，125），Z=560。工厂应生产产品A25件，产品C125种，总利润为625元。  EMBED Equation.3 
 （5）对偶问题  EMBED Equation.3 
  EMBED Equation.3 
  EMBED Equation.3 
 (6) 最优解Y=（1.375，0.875，0），Z=625  EMBED Equation.3 
 （7）影子价格为 EMBED Equation.3 
,故增加利润2.75元。  EMBED Equation.3 
 （8）因为y2=0.875，所以叫价应不少于2.375元。  EMBED Equation.3 
 二、[ EMBED Equation.3 
]求解下列BIP问题：  EMBED Equation.3 
 【解】 最优解X=(1,0,0,0,0),Z=3  EMBED Equation.3 
 三、[ EMBED Equation.3 
] 下表给出了运输问题的产销平衡表和单位运价表 B1 B2 B3 B4 Ai A1 9 6 10 11 10 A2 4 3 5 6 40 A3 5 8 12 9 20 Bj 10 25 35 10 用元素差额法求初始调运方案； EMBED Equation.3 
 求解运输问题的最优调运方案。 EMBED Equation.3 
 【解】1）
 EMBED Equation.3 
 2）
验算非基变量的检验数均大于0，故此为最优解。  EMBED Equation.3 
 四、 [ EMBED Equation.3 
]现有在确定四个人来分别完成四项工作中的一项，由于每个工人的技术特长不同，他们完成各项工作所需的工时也不同。每个工人完成每项工作所需工时如下表所示。试找出一个工作分配方案，使总工时最少。 A B C D Ⅰ 12 6 9 15 Ⅱ 20 12 18 26 Ⅲ 35 18 10 25 Ⅳ 6 10 15 7 【解】
 EMBED Equation.3 

 EMBED Equation.3 

 EMBED Equation.3 
 最优工作分配方案Ⅰ做A, Ⅱ做B，Ⅲ做C，Ⅳ做D。总工时=41  EMBED Equation.3 
 五、[ EMBED Equation.3 
]求下图的最小部分树，并求最小树长。            解：
最小树长为20.  EMBED Equation.3 
 六、[ EMBED Equation.3 
]在下图中，求A到H、I的最短路及最短路长。  EMBED MSPhotoEd.3 
 解：  EMBED MSPhotoEd.3 
 A到H的最短路PAH={A,C,G,F,H},最短路长21；  EMBED Equation.3 
 A到I的最短路PAI={A,C,G,F,I},最短路长20；  EMBED Equation.3 
 七、[ EMBED Equation.3 
]