运筹学复习题及答案

１《运筹学》复习题及解答一．简答题1．线性规划的特点是什么?(P10,－9行)：决策变量的取值是连续的,目标函数是决策变量的线性函数,约束条件是决策变量的线性等式或不等式.2．什么叫线性规划的可行解、最优解?(P15,定义2－1)：满足线性规划约束条件的解，称为可行解，使目标函数达到最优的可行解称为最优解.3．写出线性规划的标准型（LP ）的矩阵形式.(P18, －10行)：min ..0T f s t ==⎧⎨≥⎩c x Ax b x 4．什么叫（LP ）的“基”?(P18,定义2－2)：由A 中m 个线性无关的列构成的子阵，称为（LP ）的一个基，记为B.5．什么叫（LP ）的“基解”，它依赖于什么?(P19,定义2－3)：当基B 取定后，令全部非基变量为0，则这时=Ax b 的解,0B D b ==x x 称为（LP ）关于基B 的基解.它依赖于基B 的选取.２6．什么叫（LP ）的“基可行解”，几何上对应什么? (P19,定义2－4，P20,定理2－3)：当（LP ）的一个基解，同时又是可行解，则称为基可行解. x 是可行集G 的顶点的充要条件是x 是(LP )的基可行解.7．单纯形法是怎样判断（LP ）无界的?(P30,定理2－5)：若T(B)中存在某0()t D r t I <∈但整列0(1,2,)it y i m ≤= ,则(LP)的目标值f 在其可行域G 上无下界.8．互为对偶的两个线性规划的可行解的目标值有何关系?(P47,定理3－2)：设x 与y 分别为(P)与(D)的可行解,则T Tb yc x ≤9．互为对偶的两个线性规划的最优值有何关系? (P47,定理3－3)：(P)与(D)的最优值相等10．对偶单纯形法是怎样判断（LP ）无可行解的?(P49,定理3－5)：设x 为(LP)的关于B 的基解,且T(B)中某0,0,(1,2,)k kj b y j n <≥= ，则(LP)无可行解.11．平衡运输问题的“平衡”是指什么?(P77, 10行)：总存货量恰好等于总需求量,即11mni j i j a b ===∑∑.12．平衡运输问题的单位运价矩阵每行加上一个不同的常数其最优解有何变化.(P95-5)：最优解相同13．用分枝定界法求解一个极小化的整数规划，当得到多个可行解时，该取哪个的目标值作为上界？(P113)：应取目标值最小的那个作为上界14．试述求解0-1规划的隐枚举法.(P116, －11行)：（1）列出2n个可能解及其相应的目标值f k (k=1,2,…,2n);（2）按f k的大小顺序检查各可能解的可行性，第一个可行解就是最优解.15．动态规划中状态变量的设置要满足什么条件？(P128, 8行)：状态的设定应具有无后效性16．动态规划的最优化原理是什么?(P130, 6行)：最优策略的子策略必定是最优子策略.17．什么是矩阵对策的“优超原理”?(P167,－4行)：利用优超性质反复删除收益矩阵的行或列，从而可把矩阵对策简化. 这称为矩阵对策的优超原理.18．矩阵对策中的“混合策略”是指什么?３４(P168, 定义7－3)：概率向量12(,,...,)T m X x x x =与12(,,...,)T n Y y y y =分别称为甲方和乙方的混合策略.19．在EOQ 存贮模型中，平均费用与批量有何关系？(P181,(8-2)式)： , (0)2bQ auC eu Q Q =++>20．在有价格优惠的EOQ 存贮模型中，最佳批量会发生在哪些点上？(P188)：驻点与间断点21．计算机模拟的进程控制主要有哪些方法？ (P214, 10行)：时间步长法与事件步长法.22．如何利用[0, 1]均匀分布的随机数产生指数分布的随机数？ (P218, 10.2.4)：设~[0,1]r U ，则 ~()l n re ηλλ=-二．证明：从原成本矩阵C 的任一行(列)中各元素加(减)一个常数,得到新的成本矩阵C’, 则此两成本矩阵的指派问题的最优解是相同的.５三．请对下面的约束加以改进1212123935..8418,0,x x s t x x x x +≤⎧⎪-≥⎨⎪≥⎩整数1212123935..8418,0,x x s t x x x x +≤⎧⎪-≥⎨⎪≥⎩整数 等价于121212311.67..2 4.5,0,x x s t x x x x +≤⎧⎪-≥⎨⎪≥⎩整数 等价于121212311..25,0,x x s t x x x x +≤⎧⎪-≥⎨⎪≥⎩整数 证明：设矩阵C 的第i 行对应的常数为d i ， ijij i c c d '=± 1111111()nnnnnnnijij ij i ij i ij i j i j i i j i f c x c d x z d x z d ======='==±=±=±∑∑∑∑∑∑∑即f 与z 仅差一个常数, 所以两目标在相同的约束条件下，最优解是相同的.６四. 在极小化问题的下列表格中，4个常数a 1、a 2、a 3、a 4之值为未知（假定各0≥j x 且都不是人工变量）：x B x 1 x 2 x 3 x 4 x 5 x 6 bx 2x 5 x 3 0 2 1/2 1 0 0 0 0 1 0 -1/2 a 3 0 1 0 a 1 3/2 -1/2 a 2 8 1/2 r3a 41/2说出对4个未知常数的要求，使以下的说法对上表为真. (1) 现行解是最优解，但存在多个最优解； (2) 现行解不可行；(3) 有一个约束条件有矛盾； (4) 现行解是退化的基可行解； (5) 现行解可行，但问题无最优解.五． 如图,虚线表示一海岸线,H 1至H 5 是五个码头, A 表示一个工厂的位置.用动态规划方法求A 到海岸线最近的一个码头的路线并指出其距离.3 3 AB 1 B 2C 1 C 2 C 3D 1D 2 D 3 D 4H 1H 2 H 3H 4H 51 2 63 1 312 5 32 4 54 53 6 5解：2432122243(1) 0,0,0(2) 0(3) 0,0(4) 0(5) 0,0,0a a a a a a a a a a ≥=><≥<=≥<≤７六. 某公司计划在三个地区共设置四个销售点, 根据市场预测, 在不同地区设置不同数量的销售点每月可得利润如下表所示(单位:万元). 请考虑在各地区设置销售点的数目,使该公司每月获得最大利润.销售点数 地区1 地区2 地区31 16 12 10 2 25 17 143 30 20 164 32 22 17解：最短路径1122A B C D H →→→→，最近距离为7.3 3 (7)(6)(10)(4)(5)(7)(1)(2) (3) (5)H 1H 2H 3 H 4H 51 2 6 31312 5 324 5 4 5 36 5８阶段k : 确定地区k 的销售点数， 状态变量k s : 剩余销售点数, 决策变量k x : 地区k 的销售点数, 决策集:{|0}k k k k D x x s =≤≤,阶段k 的利润：()k k w x ，状态转移规律：12113224,,,s s s x s s x ==-=-40f =,333333330()max{()}()x s f s w x w s ≤≤==3333333333(0)0(0),(1)10(1),(2)14(2),(3)16(3),(4)17(4)f x f x f x f x f x ==========2222223220()max {()()}x s f s w x f s x ≤≤=+-223(0)(0)(0)0f w f =+=223232(1)max{(0)(1),(1)(0)}max{010,120}12(1)f w f w f x =++=++==23223223(0)(2)014(2)max (1)(1)max 121022(1)(2)(0)170w f f w f x w f ++⎧⎫⎧⎫⎪⎪⎪⎪=+=+==⎨⎬⎨⎬⎪⎪⎪⎪++⎩⎭⎩⎭９七. 如下线性规划问题12312312max 26..240,1,2,3.jf x x x x x x s t x x x j =-+⎧++≤⎪-+≤⎨⎪≥=⎩ 已知其标准化模型的最优单纯形表为x B x 1 x 2 x 3 x 4 x 5 bx 1 x 5 1 0 1 3 1 1 1 1 0 1 6 10 r312(1) 写出它的最优解X *, 最优基B ; (2) 写出它的对偶问题及其最优解.2323222323(0)(3)016(1)(2)1214(3)max max 27(2)(2)(1)1710(3)(0)210w f w f f x w f w f ++⎧⎫⎧⎫⎪⎪⎪⎪++⎪⎪⎪⎪====⎨⎬⎨⎬++⎪⎪⎪⎪⎪⎪⎪⎪++⎩⎭⎩⎭232323222323(0)(4)017(1)(3)1216(2)(2)(4)max max 31(2)1714(3)(1)2010(4)(0)220w f w f w f f x w f w f ++⎧⎫⎧⎫⎪⎪⎪⎪++⎪⎪⎪⎪⎪⎪⎪⎪+====+⎨⎬⎨⎬⎪⎪⎪⎪++⎪⎪⎪⎪++⎪⎪⎪⎪⎩⎭⎩⎭112121*********1212(0)(4)031(1)(3)1627(2)(2)(4)max{()(4)}max max 47(2)2522(3)(1)3012(4)(0)320x w f w f w f f w x f x x w f w f ≤≤++⎧⎫⎧⎫⎪⎪⎪⎪++⎪⎪⎪⎪⎪⎪⎪⎪+=+-====+⎨⎬⎨⎬⎪⎪⎪⎪++⎪⎪⎪⎪++⎪⎪⎪⎪⎩⎭⎩⎭最优解：1232, 1, 1.x x x ===最优值47.１０八. 某企业生产A 、B 、C 三种产品，产品的主要原料有甲乙两种，产品A 、B 、C 每件分别需要原料甲2、5、4单位；分别需要原料乙5、3、7单位；耗用工时分别为12、15、18小时，每件利润分别为4500元、5000元、4800元。

每月计划，可提供原料甲乙分别为420、520单位；正常可用工时为1000小时，可用加班工时至多为1300小时，每小时加班费需支付100元。

希望每月总利润最大，试建立该问题的数学模型，不需求解。

（加班工时要取整数）解：先把数据整理列表产品A 产品B 产品C 上限 原料甲 2 5 4 420 原料乙 5 3 7 520 工时 12 15 18 1000 利润450050004800设产品A 、B 、C 的月产量分别为123,,x x x 件，加班工时为4x 小时，月总利润为f , 则123412312312344max 450050004800100254420537520..121518100013000,jf x x x x x x x x x x s t x x x x x x j =++-⎧++≤⎪++≤⎪⎪++≤+⎨⎪≤⎪⎪≥⎩整数，＝1,2,3,4解：（1）最优解*(6,0,0,0,10)T X =最优基1510(,)11B A A ∙∙⎛⎫==⎪-⎝⎭. (2) 对偶问题为 121212112min 64221..10,0g y y y y y y s t y y y =+-≥⎧⎪+≥-⎪⎨≥⎪⎪≥≥⎩ 最优单纯形表中松弛变量的检验数就是对偶问题的最优解： 14252,0y r y r ====九. 用图解法求解线性规划：1212212max 3210..20,0f x x x x s t x x x =++≤⎧⎪≤⎨⎪≥≥⎩十. 用伏格尔法求出以下运输问题的初始基可行解. 并求此解的总运输费.c i j B 1 B 2 B 3 B 4 a i A 1 10 6 7 12 4 A 2 16 10 8 9 10 A 3 5 4 10 10 6 b j5276点A(2,2)是最优解。