《运筹学》作业参考答案作业一一、是非题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

（√）2.线性规划问题的每一个基解对应可行解域的一个顶点。

（╳）3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。

（√）4.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。

（√）5.单纯形法计算中，如果不按最小比值规划选出基变量，则在下一个解中至少有一个基变量的值为负。

（√）6.线性规划问题的可行解如为最优解，则该可行解一定是基可行解。

（╳）7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。

（╳）8.对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为mnC个。

（╳）9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。

（√）10.求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。

（√）二、线性规划建模题：1.某公司一营业部每天需从A、B两仓库提货用于销售，需提取的商品有：甲商品不少于240件，乙商品不少于80台，丙商品不少于120吨。

已知：从A仓库每部汽车每天能运回营业部甲商品4件，乙商品2台，丙商品6吨，运费200元/每部；从B仓库每部汽车每天能运回营业部甲商品7件，乙商品2台，丙商品2吨，运费160元/每部。

问：为满足销售量需要，营业部每天应发往A、B两仓库各多少部汽车，并使总运费最少？解：设营业部每天应发往A、B两仓库各x1，x2部汽车,则有：12 121212min200160 47240 2280 621200(1,2)jW x xx xx xx xx j=++≥⎧⎪+≥⎪⎨+≥⎪⎪≥=⎩2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。

现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：该企业计划用于此项广告宣传的经费预算是80万元，此外要求：①至少有200万人次妇女接触广告宣传；②电视广告费用不得超过50万元,③电视广告至少占用三个单元一般时间和两个单元黄金时间,④广播和报纸广告单元均不少于5个单元而不超过10个单元。

解：设电视一般时间、黄金时间、广播和报纸各投放广告单元数为x1，x2，x3，x4，有：123412341234121234max 409050200.40.70.30.1580304020102000.40.750325105100(1,...4)Z x x x x x x x x x x x x x x x x x x xj j =++++++≤⎧⎪+++≥⎪⎪+≤⎪≥⎪⎨≥⎪⎪≤≤⎪≤≤⎪⎪≥=⎩三、计算题：对于线性规划模型1212122j max 34 628x 3x 0(j=1,2)z x x x x x x =++≤⎧⎪+≤⎪⎨≤⎪⎪≥⎩1.用图解法求出其所有基本解，并指出其中的基本可行解和最优解。

2.三个方程中分别添加松驰变量x3,x4,x5后把模型化成标准型，用单纯形法寻求最优解。

并与1题中图解法中对照，单纯形表中的基可行解分别对应哪些顶点。

3.若直接取最优基125[,,]B P P P =，请用单纯形表的理论公式进行计算对应基B 的单纯形表，并与第2题最优单纯形表的计算结果比较是否一致。

（附单纯形表的理论公式：非基变量xj 的系数列向量由Pj 变成-1j j p B p = ，基变量的值为1B X B b -=，目标函数的值为10 B B B Z C X C B b -==，检验数公式jj j B R C C P =-）。

解：（1）图解如下：所有基本可行解：O （0,0），Q 1（6,0），Q 2（4,2），Q 3（2,3），Q 4（0,3）共五个基可行解。

从上图知：最优解为点Q 2（4,2），目标函数值为Z ＝20。

（2）模型标准化为：1212312425j max 346 28 (2) x +x =3 (3)x 0(j)z x x x x x x x x =+++=⎧⎪++=⎪⎨⎪⎪≥⎩　(1)一切从上表知：表一中的基可行解（0,0,6,8,3）对应坐标原点O ，表二中的基可行解为（6,0,0,2,3）对应图中的Q 1点，表三中的基可行解为（4,2,0,0,1）对应图中的Q 2点，得到最优解。

（3）若取基[]⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦125110B =P ,P ,P 120011，基变量为x 1,x 2,x 5，刚好是最优表中的对应基变量，可算出⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦-12-10B -1101-11（从第三个单纯形表也可找到B －1），由单纯形表计算公式计算非基变量的系数列向量、检验数及基解等。

32-1012-110011-1101P ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==-⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦，42-1001-110111-1101P -⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦，1252-1064-110821-1131B x X x x ⎡⎤⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦。

33320(3,4,0)121B R c C P ⎡⎤⎢⎥=-=--=-⎢⎥⎢⎥⎣⎦，44410(3,4,0)111B R c C P -⎡⎤⎢⎥=-=-=-⎢⎥⎢⎥-⎣⎦与迭代的第三个单纯形表计算结果一致。

四、写出下列线性规划问题的对偶问题。

1231312323231Min Z = 5x +4x + 3x 2x +7x 8 8x +5x -4x 154x + 6x = 30x ,x 0,x ≥⎧⎪≤⎪⎨⎪⎪≥⎩自由变量 解：设三个方程的对偶变量分别为y 1,y 2,y 3，有：1231223123123max 8153028554474630,0,W y y y y y y y y y y y y y =+++=⎧⎪+≤⎪⎨-+≤⎪⎪≥≤⎩为自由变量五、有一个Max 型的线性规划问题具有四个非负变量，三个“≤”型的条件，其最优表格如下表，请写出其对偶问题的最优解及目标函数值。

解：该问题的松驰变量为x 5,x 6,x 7，由对偶规划的性质知三个对偶变量的值分别为x 5,x 6,x 7检验数的负值，目标函数值与原问题相等。

故12341Y=(y ,y ,y )=(,0,)33， W ＝34/3。

用表上作业法求解此问题的最优解。

（要求用行列差值法给初始解，用位势法求检验数。

） 解：（1（2）用位势法求检验数：对基变量有：()0ij ij i j R c u v =-+=,并令u1=0，求出行列位势，如下表。

各非基变量的检验数分别为：R 12=4－(3+0)=1， R 23=7－(3+2)=2，即基变量的检验数都大于0，当前方案为最优调运方案。

作业二一、用隐枚举法求解下面0－1型整数规划问题：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≤-+≤-+≤+≤++-+=10,,44225423..232132132132321321或x x x x x x x x x x x x x x t s x x x Z Max解：问题为求极大型，需所有的变量前的价值系数变为负号，故令11221',1'x x x x =-=-，模型变为：231123231231231233('2')'3' 2 (1)4' 1 (2)..'2' 1 (3)'4' 1 (4)',',01Max Z x x x x x x x x s t x x x x x x x x x =-++--+≤-⎧⎪-+≤⎪⎪---≤-⎨⎪---≤-⎪=⎪⎩或，用目标函数值探索法求最大值：从表中可以看出，当123'0,'1,0x x x ===时具最大目标函数值，即1231,0,0x x x ===，Z max ＝2。

二、某服装厂有五项工作需要分给五个技工去完成，组成分派问题，各技工完成各项工作的能力评分如下表所示。

请问应如何分派，才能使总得分最大？解：（1）效率矩阵为：1.30.800 1.00 1.2 1.3 1.30[] 1.000 1.200 1.0500.2 1.41.00.90.61.1ij c ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦，问题是求极大，转化为求极小问题，设 1.4ij ij b c =-，构造以b ij 为系数的矩阵，0.10.6 1.4 1.40.41.40.20.10.1 1.4[]0.41.4 1.40.2 1.41.40.35 1.4 1.200.40.50.81.40.3ij b ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦（2）对b ij 矩阵进行系数变换，使每行每列出现0元素，00.4 1.3 1.30.31.3000 1.3[']0.21.1 1.201.21.40.25 1.4 1.200.10.10.51.10ij b ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦（3）进行试分配：(0)0.4 1.3 1.30.31.3(0) 1.3[']0.21.1 1.2(0) 1.21.40.25 1.4 1.2(0)0.10.10.51.1ij b ⎡⎤⎢⎥∅∅⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥∅⎣⎦，（4）作最少的直线覆盖所有的0元素：(0)0.4 1.3 1.30.31.3(0) 1.3[']0.21.1 1.2(0) 1.21.40.25 1.4 1.2(0)0.10.10.51.1ij b ⎡⎤⎢⎥∅∅⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥∅⎣⎦ √√（5）在没有被覆盖的部分中找出最小数0.1，则第四、五行减去这个最小数0.1，同时第五列加上这个最小数，其他元素不变，目的是增加0元素的个数。

00.4 1.3 1.30.41.3000 1.4[']0.21.1 1.20 1.31.30.15 1.3 1.1000.41.00ij b ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦（6）试分配：(0)0.4 1.3 1.30.41.3(0) 1.4['']0.21.1 1.2(0) 1.31.30.15 1.3 1.1(0)(0)0.41.0ij b ⎡⎤⎢⎥∅∅⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥∅∅⎣⎦，此时，所有的0都已打括号或划掉，且打括号的0元素（独立的0元素）个数刚好为5个，得到了问题的最优解，问题的解矩阵为：1000000100000100000101000ij x ⎡⎤⎢⎥⎢⎥⎡⎤⎢⎥=⎣⎦⎢⎥⎢⎥⎢⎥⎣⎦，即A 1做平车，A 2做卷边，A 3做绷缝，A 4做打眼，A 5做考克，总得分为6.1。