1、第一部分 绪 论第二部分 线性规划与单纯形法1 判断下列说法是否正确：(a)图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；(b)线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；(c)线性规划问题的每一个基解对应可行域的一个顶点；(d)如线性规划问题存在可行域，则可行域一定包含坐标的原点；(e)对取值无约束的变量 xi，通常令 其中，在用单纯形法求得的最优解中有可能同时出现(f)用单纯形法求解标准型的线性规划问题时，与 对应的变量都可以被选作换入变量；(g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一
2、个基变量的值为负；(h)单纯形法计算中，选取最大正检验数 k对应的变量 xk作为换入变量，将使目标函数值得到最快的增长；(i)一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；(k)若 x1，x 2分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中 1， 2可以为任意正的实数；(1)线性规划用两阶段法求解时，第一阶段的目标函数通常写为Xai为人工变量)，但也可写为 ，只要所有 ki均为大于零的常数；(m)对一个有 n个变量、m 个约束的标准型的线性规划问题，其可
3、行域的顶点恰好为 个；(n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解；(o)线性规划问题的可行解如为最优解，则该可行解一定是基可行解；(p)若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解；(q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优；(r)将线性规划约束条件的“”号及“”号变换成“”号，将使问题的最优目标函数值得到改善；(s)线性规划目标函数中系数最大的变量在最优解中总是取正的值；(t)一个企业利用 3种资源生产 4种产品，建立线性规划模型求解得到的最优解中，最多只
4、含有 3种产品的组合；(u)若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解；(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。【答案】1.1(a)(b)(f)(g)(i)(J)(1)(q)(t)正确，(c)(d)(e）(h)(k)(m)(n)(o)(p)（r)(s)(U)(v)不正确。2用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。【答案】(a)唯一最优解，z *=3，x 1=12，x 2=0；(b)无可行解；(c)有可行解，但 max z无界；(d)无穷多最优解，z *=66。表 1.6x
5、1 x2 x3 x4 X5x3 dx4 2x5 341a 2a1531OOO10OO1cj一z j C1 C2 O O O【答案】1.25(a)d0，C 10，而 c10且d43a 2；(d)C10，3a 20，a 10；(f)x5为人工变量，且 c10，C 2o。3 某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为 48000 1、重型炸弹 48枚、轻型炸弹 32枚。飞机携带重型炸弹时每升汽油可飞行 2 km，带轻型炸弹时每升汽油可飞行 3 km。又知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来回路程汽油消耗(空
6、载时每升汽油可飞行 4 km)外，起飞和降落每次各消耗 100 1。有关数据如表 117所示。表 117摧毁可能性要害部位 离机场距离km每枚重型弹 每枚轻型弹12344504805406000.100.200.150.250.O80.160.120.20为了使摧毁敌方军事门标的可能性最大，应如何确定飞机轰炸的方案。要求建立这个问题的线性规划模型。【答案】用 i=1，2 分别代表重型和轻型炸弹，j=1，2，3，4 分别代表四个要害部位，xij为投到第 J部位的 i种型号炸弹的数量，则问题的数学模型为式中目标函数非线性，但 rain z等价于 max 1g(1z)，因此目标函数可改写为4 用单纯
7、形法求解下列线性规划(1)123123max40,jZxx【解】单纯形表：C(j) 3 4 1 0 0Basis C(i) X1 X2 X3 X4 X5 R. H. S. Ratio X4 0 2 3 1 1 0 1 1/3X5 0 1 2 2 0 1 3 3/2C(j)-Z(j) 3 4 1 0 0 0 X2 4 2/3 1 1/3 1/3 0 1/3 1/2X5 0 -1/3 0 4/3 -2/3 1 7/3 MC(j)-Z(j) 1/3 0 -1/3 -4/3 0 -4/3 X1 3 1 3/2 1/2 1/2 0 1/2 X5 0 0 1/2 3/2 -1/2 1 5/2 C(j)-Z
8、(j) 0 -1/2 -1/2 -3/2 0 -3/2 最优解：X= （1/2，0，0，0， 5/2） ；最优值 Z3/2(2) 12341234max557060,jZxx【解】单纯形表：C(j) 2 1 -3 5 0 0 0Basis C(i) X1 X2 X3 X4 X5 X6 X7 R. H. S. RatioX5 0 1 5 3 -7 1 0 0 30 MX6 0 3 -1 1 1 0 1 0 10 10X7 0 2 -6 -1 4 0 0 1 20 5C(j)-Z(j) 2 1 -3 5 0 0 0 X5 0 9/2 -11/2 5/4 0 1 0 7/4 65 MX6 0 5/2
9、 1/2 5/4 0 0 1 -1/4 5 10X4 5 1/2 -3/2 -1/4 1 0 0 1/4 5 MC(j)-Z(j) -1/2 17/2 -7/4 0 0 0 -5/4 X5 0 32 0 15 0 1 11 -1 120 MX2 1 5 1 5/2 0 0 2 -1/2 10 10X4 5 8 0 7/2 1 0 3 -1/2 20 MC(j)-Z(j) -43 0 -23 0 0 -17 3 因为 730 并且 ai70(i=1,2,3)，故原问题具有无界解，即无最优解。线性规划的对偶理论与灵敏度分析2.1写出下列线性规划问题的对偶问题：【答案】2.2已知线性规划问题：用单纯
10、形法求解得最终单纯形表如表 22 所示。(a)求 和 bl，b 2；(b)求表 22【答案】【解析】 （1）由题意可设初始单纯形表的增广矩阵为最终单纯形表的增广矩阵为对矩阵 作初等行变换，使其第 4，5 列组成单位矩阵2()AB由单纯形运算法则可知， 13()()AB所以， 1123223129/,4,5/,85aaab（2）由检验数的计算式可知 32/00/4cc求解上述方程组得： 1237,8c2.3已知线性规划问题：用单纯形法求得最终表如表 28所示。表 2-3试用灵敏度分析的方法分别判断：(a)目标函数系数 C1或 c2分别在什么范围内变动，上述最优解不变；(b)当约束条件右端项 b1
11、，b 2中一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；(c)问题的目标函数变为时上述最优解的变化；(d)约束条件右端项由 变为【答案】2.4 已知表 24为求解某线性规划问题的最终单纯形表，表中 x4，x 5为松弛变量问题的约束为形式。表 2-4(a)写出原线性规划问题；(b)写出原问题的对偶问题；(c)直接由表 24写出对偶问题的最优解。【答案】(a)原线性规划问题如下：(a)原线性规划问题如下：(b)略；(c)对偶问题最优解为 Y*=(4，2)。2.5已知线性规划问题：用单纯形法求解时，其最优解见表 27。表 2-5要求：(a)直接写出上述问题的对偶问题及其最优解。(b)若
12、问题中 x2列的系数变为(3，2，3) T，试问表 27 中的解是否仍为最优解?(C)若增加一个新的变量 x4，其相应系数为(2，3，2)T。试问增加新变量后表 27中的最优解是否发生变化?【答案】(a)其对偶问题为其最优解为(b)zz系数变化后，对偶问题第(2)个约束将相应变为 2y1+3y23，将 y1*，一￥2*代入不满足，故原问题最优解将发生变化；(C)相应于新变量 x4，因有 ，故原问题最优解将发生变化。2.6已知线性规划问题：要求：(a)写出它的对偶问题；(b)应用对偶理论证明原问题和对偶问题都存在最优解。【答案】(a)略；(b)容易看出原 1“3题和其对偶问题均存在可行解，据对偶理论，两者均存在最优解。第三部分 运输问题
