北邮运筹学ch32基变量与闭回路.33

上海海洋大学试卷诚信考试承诺书本人郑重承诺：我已阅读且透彻理解了“上海海洋大学学生考场规则”和“上海海洋大学学生违反校纪校规处理规定”，承诺在考试中自觉遵守，如有违反，按有关条款接受处理。

承诺人签名： 日 期：考生姓名： 学号： 专业班名： 一、(10分)写出下列线性规划问题的对偶问题：123123123123123567531556102050,0,Min Z x x x x x x x x x x x x x x x =----+-≥⎧⎪--+≤⎪⎨--=-⎪⎪≤≥⎩s.t.不受限制解：123123123123123152055556631070,0,Max w y y y y y y y y y y y y y y y =+---+≤-⎧⎪--≤-⎪⎨-+-=-⎪⎪≥≤⎩s.t.不受限制二、（15分）、已知线性规划问题：12341234123423422320232200, 1.2.3.4iMax Z x x x x x x x x x x x x x i =++++++≤⎧⎪+++≤⎨⎪≥=⎩s.t. 其对偶问题的最优解为Y 1*=1.2,Y 2*=0.2,试用对偶的互补松弛性求解原问题的最优解。

解：121212121212202021222333240,0Max w y y y y y y y y y y y y =++≥⎧⎪+≥⎪⎪+≥⎨⎪+≥⎪⎪≥≥⎩s.t.变为标准型为1234123412121212122122233324,,,,,0s s s s s s s s y y y y y y y y y y y y y y y y y y ⎧+-=⎪+-=⎪⎪+-=⎨⎪+-=⎪⎪≥⎩因为最优解为Y 1*=1.2,Y 2*=0.2，所以12340.4,0.6,0,0s s s s y y y y ====根据对偶的互补松弛性，123412340s s s s x y x y x y x y +++=，所以120x x ==所以343423203220x x x x +=⎧⎨+=⎩，解得344x x ==三、（15分）给定线性规划问题12312312min 26..240j 1,2,3j z x x x x x x s t x x x =-++⎧++≤⎪-≤⎨⎪≥=⎩（）（1）把11c =-改为4，求原问题的最优解（2）讨论2c 在什么范围内变化时原来的最优解也是原问题的最优解。

No .1 线性规划1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而工厂有供纺纱的总工时7200h ，织带的总工时1200h 。

(1) 列出线性规划模型，以便确定产品的数量使总利润最大；(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？解：(1)设A 的产量为x 1，B 的产量为x 2，C 的产量为x 3，D 的产量为x 4，则有线性规划模型如下：max f (x )=(168-42)x 1 +(140-28)x 2 +(1050-350)x 3 +(406-140)x 4=126 x 1 +112 x 2 +700 x 3 +266 x 4s.t. ⎪⎩⎪⎨⎧=≥≤+≤+++4,3,2,1 ,012005.02 720041023434321i x x x x x x x i(2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。

2、将下列线性规划化为极大化的标准形式解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x 4，在第二行添加人工变量x 5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量x 6, x 7，并令x x x 333='-''，则有max[-f (x )]= {-2 x 1 -3 x 2 -5('-''x x 33)+0 x 4 -M x 5+0 x 6 +0 x 7} s.t. 0,,,,,,,1355719 13 5571916 9976 5 7654332173321633215332143321≥'''=+''+'-+-=+''-'+-=+''+'-+-=+''-'+--⎪⎪⎪⎩⎪⎪⎪⎨⎧x x x x x x x x x x x x x x x x x x x x x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧±≥≤+-=-+--≥-+++=不限321321321321321 ,0,13|5719|169765..532)(min x x x x x x x x x x x x t s x x x x f3、用单纯形法解下面的线性规划⎪⎪⎩⎪⎪⎨⎧≥≤++-≤++-≤-+++= ,0,,4205.021********* ..352)(max 321321321321321x x x x x x x x x x x x t s x x x x f 解：在约束行1,2,3分别添加x 4, x 5, x 6松弛变量，有初始基础可行解和单纯形答：最优解为x 1 =244.375, x 2 =0, x 3 =123.125, 剩余变量x 6 =847.1875；最优解的目标函数值为858.125。

判断题判断正误，如果错误请更正第五章运输与指派问题1.运输问题中用位势法求得的检验数不唯一。

2.产地数为3,销地数围的平衡运输中，变量组{Xll, X13, X22, X33, X34}可作为一组基变量。

3.不平衡运输问题不一定有最优解。

4.m+n-1个变量构成基变量组的充要条件是它们不包含闭合回路。

5.运输问题中的位势就是其对偶变量。

6.含有孤立点的变量组不包含有闭回路。

7.不包含任何闭回路的变量组必有孤立点。

& 产地个数为m销地个数为n的平衡运输问题的对偶问题有m+n个约束。

9.运输问题的检验数就是对偶问题的松弛变量的值。

10.产地个数为m销地个数为n的平衡运输问题的系数矩阵为A,则有r(A)〈=m+nT。

11.用一个常数k加到运价C的某列的所有元素上，则最优解不变。

12.令虚设的产地或销地对应的运价为一任意大于0的常数C (00),则最优解不变。

13.若运输问题中的产量或销量为整数则其最优解也一定为整数。

14.运输问题中的单位运价表的每一行都分别乘以一个非0常数，则最优解不变。

15.按最小元素法求得运输问题的初始方案，从任一非基格出发都存在唯一一个闭回路。

16.在指派问题的效率表的某行乘以一个大于零的数最优解不变。

选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。

第五章运输与指派问题1.下列变量组是一个闭回路的有A{x21,xll,xl2,x32,x33,x23} B{xll,xl2,x23,x34,x41,xl3} C {x21,xl3,x34,x41,xl2} D{xl2,x32,x33,x23,x21,xll} D{xl2,x22,x32,x33,x23,x21}2.具有M个产地N个销地的平衡运输问题模型具有特征A有MN个变量M+N个约束B 有M+N个变量MN个约束C有MN个变量M+N-1个约束D有M+N-1个基变量MN-M-N+1个非基变量E系数矩阵的秩等于M+N-13.下列说法正确的有A运输问题的运价表第r行的每个cij同时加上一个非0常数k, 其最优调运方案不变。

北京交通大学2010-2011学年第一学期《运筹学基础》期末考试试卷（A）考试方式：闭卷任课教师：李岷珊学院_____________ 专业___________________ 班级____________ 学号_______________ 姓名_____________请注意：本卷共六大题，如有不对，请与监考老师调换试卷！一、1、找出下列变量组中的闭回路并排成标准次序：A. X12X23X34X41B.X12X53X46X52X16X43C.X12X24X22X14D. X12X14X24X32X34X222、已知线性规划问题MAX Z = X1+2X2+3X3+4X4X1+2X2+2X3+3X4≤20 2X1+X2+3X3+2X4≤20 X i≥0 求其对偶问题3、已知线性规划问题MAX Z =CX, 约束条件AX=b, X i≥0。

证明其可行域是凸集；并证明该问题若有不同的最优解，则有无穷多最优解。

4、（1，1，1，0，0，0），（1，0，0，0，1，0），（0，0，1，1，1，0）（0，1，0，1，0，0），（0，0，0，0，0，1），（0，0，0，0，0，1）是无向简单图的关联矩阵。

画出该图，并回答该图是否连通。

5、分别利用优超关系和求鞍点方法求解如下矩阵对策。

其赢得矩阵的三行分别为（2，6，8），（5，4，10），（7，7，9）二、解下列线性规划问题，并写出最优基矩阵B及其逆矩阵；若第二种资源发生变化，在什么范围内变化原最优基不变？MAX Z = 2X1+3X23X1 + 6X2≤36 2X1 ≤12 4X2≤20 X1≥0，X2≥02三、在下图中，除已经标明方向的弧其方向均为从左至右，仅四条上下方向的弧为从下至上。

以上各弧对应数对左边数字即是该弧的容量，求该网络（A是源，F是汇）的最大流。

G 7-3 H第 3 页共5 页四、在上图中，各弧对应数对左边数字是该弧的长度，求（A到F的）最短路。

运筹学_华侨大学中国大学mooc课后章节答案期末考试题库2023年1.运筹学的发展趋势是追求数学模型的精巧。

参考答案:错误2.对于总运输费用最小的运输问题，若已经得到最优方案，则其所有空格的检验数都（）参考答案:非负3.下列变量组是一个闭回路（）参考答案:{x12,x32,x33,x23,x21,x11}4.若线性规划的原问题和其对偶问题都具有可行解，则该线性规划问题一定具有最优解。

参考答案:正确5.若线性规划问题的原问题存在可行解，则对偶问题也一定存在可行解.参考答案:错误6.某个常数bi波动时，最优表中引起变化的有（）参考答案:基变量的取值7.当基变量xj的系数cj波动时，最优表中引起变化的有（）参考答案:非基变量的检验数8.单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。

参考答案:正确9.X是线性规划的可行解，则错误的结论是（）。

参考答案:X是基本可行解10.不是运筹学的主要来源（）参考答案:政治11.运筹学是一门数学课程。

参考答案:错误12.运筹学作为科学名字出现在（）参考答案:20世纪30年代末13.下列哪些不是运筹学的研究范围（）参考答案:系统设计14.已知y*i为线性规划的对偶问题的最优解,如果y*i=0,说明在最优生产计划中第i种资源一定有剩余。

参考答案:错误15.运筹学模型（）参考答案:可以是图象的，也可以是符号的，能够预测某些决定性因素与效果16.关于目标规划下面说法不正确的是：（）参考答案:目标函数可以是最大化或最小化问题17.在目标规划中，求解的基本原则是首先满足高级别的目标，但当高级别目标不能满足时（）。

参考答案:其后的某些低级别目标有可能被满足18.目标规划没有系统约束时，不一定存在满意解。

参考答案:错误19.连通图一定有支撑树。

参考答案:正确20.Dijkstra算法要求边的长度非负。

参考答案:正确21.目标规划只能解得满意解，不存在最优解。

1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。

⎪⎩⎪⎨⎧≤≤≤≤≤++=83105120106max 212121x x x x x x z2.将下述线性规划问题化成标准形式。

（1）⎪⎪⎩⎪⎪⎨⎧≥≥-++-≤+-+-=-+-+-+-=无约束4,03,2,12321422245243min 4321432143214321x x x x x x x x x x x x x x x x x x x x z解：令z z -='，''4'44x x x -=⎪⎪⎩⎪⎪⎨⎧≥=-+-++-=+-+-+=-+-+-+-+-=0,,,,,,232142222455243'max 65''4'43216''4'43215''4'4321''4'4321''4'4321x x x x x x x x x x x x x x x x x x x x x x x x x x x x x z3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。

⎪⎩⎪⎨⎧≥≤+≤++=0,825943510max 21212121x x x x x x x x z解：①图解法：②单纯形法：将原问题标准化：⎪⎩⎪⎨⎧≥=++=+++=0,,,825943510max 432142132121x x x x x x x x x x x x z C j10 5 0 0 θ 对应图解法中的点C B B b x 1 x 2 x 3 x 4 0 x 3 9 3 4 1 0 3 O 点 0x 48 [5] 2 0 1 8/5 σj 0 10 5 0 0 0 x 3 21/5 0 [14/5] 1 -3/5 3/2 C 点 10x 1 8/5 1 2/5 0 1/5 4 σj -16 0 1 0 -2 5x 2 3/215/14-3/14B 点10x 1 1 1 0 -1/7 2/7 σj35/2-5/14-25/14最优解为（1,3/2,0,0），最优值Z=35/2。