运筹学复习资料（工程硕士—2011.11）

1、运筹学复习资料（工程硕士2011.11）一、判断题1. 对一个有n个变量，m个约束的标准型的线性规划问题，其可行域的顶点恰好为个。2. 任何线性规划问题存在并且具有唯一的对偶问题。3. 建立目标规划模型时，对于其中的正偏差变量应取正值，负偏差变量应取负值。4. 一旦一个人工变量在迭代中转变为非基变量，该变量及相应列的系数可以从单纯形表中删除，而不影响计算结果。5. 已知为线性规划的对偶问题的最优解，若，说明在最优生产计划中第i中资源一定有剩余。6. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。二、填空题1. 对于Max L.P问题，若X(0)=(b1,b2,bm,0

2、,0)T为一基可行解，有一个 ，并且对i=1,2,m有 ，那么该L.P问题具有无界解（或称无最优解）。2. 设原问题是MaxZ=CX；AX+Xs=b；X,Xs0其对偶问题是Min=Yb；YA-Ys=C；Y,Ys0则原问题单纯形表的 对应其对偶问题的一个基解，且其符号方向 。3. 有m个产地n个销地的产销平衡的运输问题，对应变量xij的系数列向量Pij= ；其约束方程系数矩阵的秩 。4. 在目标规划中，正、负偏差变量d+和d-恒有 的关系；含有正、负偏差变量的约束条件称为 ，它们是软约束。5. 设有最大化的整数规划问题A，与它相应的线性规划为问题B，分枝定界法就是从解问题B开始，若其最优解不符合

3、A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的 ；而A的任意可行整数解的目标函数值将是Z*的一个 。三、根据资料回答问题1. 写出下列L.P问题的对偶问题Max Z=2x1+x2+4x3Min=5x1-4x2+3x32. 下面是一张求Max问题、约束条件用“”连接的L.P问题最优单纯形表格,其中x3、x4、x5为松弛变量。XBx1x2x3x4x5x141000x5400-21x2201-0j-1400-0要求：(1)写出该问题及其对偶问题的最优解；(2)如能以代价1增添第一种资源一个单位是否值得，为什么？(3)如有人愿意向你购买第二种资源，应要价多少才合算，为什么？(4)是否有其

4、它最优解，为什么？3. 已知下表是某一约束条件用“”连接的L.P问题最优单纯形表格，其中x4、x5为松弛变量。XBx1x2x3x4x5x35/201/211/20x15/21-1/20-1/61/3j0-40-4-2要求：写出原线性规划问题的数学模型。四、求解下列各题1. 某工厂生产甲、乙、丙三种产品，单位产品所需工时分别为2、3、1个工时；单位产品所需原材料分别为3、1、5公斤；单位产品利润分别为2元、3元、5元。工厂每天可利用的工时为12个，可供应的原材料为15公斤。要求：(1) 试确定使总利润为最大的日生产计划和最大利润。(2) 若由于原材料涨价，使得产品丙的单位利润比原来减少了2元，问

5、原来的最优生产计划变否？若不变，说明为什么；若变，请求出新的最优生产计划和最优利润。(3) 在保持现行最优基不变的情况下，若要增加一种资源量，应首先考虑增加哪种资源？为什么？单位资源增量所支付的费用是多少才合算？为什么？2. 求下面运输问题的最小运输费方案。销地产地B1B2B3B4产量A1291079A213425A384257销量38463. 针对目标规划模型，用图解法求出问题的满意解。4. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问应如何分配这五项工作，并求得最大产值。工作工人ABCDE甲 946 85乙 859106丙 973 58丁 486 95戊10

6、53 63附：三、四题答案三、根据资料回答问题2.(1)该问题的最优解X*=(4,2,0,0,4)T，Z*=14；对偶问题最优解Y*=(3/2,1/8,0)，*=14。(2)值得。因13/2(该资源影子价格)，所以可以盈利。(3)要价至少要在1/8以上才合算。因为这样能盈利，否则不如自己组织生产。(4)没有其它最优解。因为所有非基变量的检验数均严格小于0，所以当前解为唯一最优解。3. 由题意已知原线性规划问题目标函数为Max（因j0为最优），且c4、c5为0（松弛变量目标函数系数为0）。根据知：，得：根据，得：。则原线性规划问题的数学模型为：四、求解下列各题1.(1) 设甲、乙、丙三种产品日生

7、产量分别为x1、x2、x3，建立L.P模型： 化标准型 用单纯形法求解：cj23500CBXBbx1x2x3x4x50x41223110120x515315013j0235000x497/514/501-1/545/145x333/51/5101/515j-15-1200-13x245/141/2105/14-1/145x333/141/201-1/143/14j-150/7-200-5/7-6/7j0 (j=1,2,5)，得最优解：；。(2) 产品丙的单位利润比原来减少了2元，即，。按灵敏度分析的方法直接反映到最终表：cj235-200CBXBbx1x2x3x4x53x245/141/210

8、5/14-1/145-2x333/141/201-1/143/14j-150/7-200-6/7-3/7原来的最优生产计划不变，因此时仍有j0 (j=1,2,5)。(3) 保持现行最优基不变，若要增加一种资源量，应首先考虑增加第二种资源(原材料)。因为；单位资源增量所支付的费用：工时单价不超过，原材料单价不超过才是合算的，这样才有利可图，否则不如将资源卖掉。2.(1) 用Vogel法求初始解：销地产地B1B2B3B4产量差额A129107952222A21342511A3842572221销量384621差额11231235825297(2) 用位势法求检验数： 销地产地B1B2B3B4产量UiA129310790A241-132425-5A311842357-5销量384621Vj2977(3) 用闭回路法调整并进一步求检验数：销地产地B1B2B3B4产量UiA129310799A2513341253A3118423574销量384621Vj-70-2-2所有检验数均为大于零，已得最优解（退化解），基变量：，；其余非基变量：均等于零。最小总运费：Z*=833. 满意解为图中A(4,0)、B