线性规划常见疑问

1、第一章线性规划常见疑问解答 1. 线性规划一一这一运筹学重要分支的开创者是谁？ 这里，必须谈到两个著名的人物，康托洛维奇和丹捷格。 1939年著名数理经济学者康托洛维奇发表了生产组织和计划中的数学方法这一运 筹学的先驱性名著，其中已提到类似线性规划的模型和解乘数求解法”但是他的工作直到 1960年的最佳资源利用的经济计算一书出版后，才得到重视。1975年，康托洛维奇与 T . C . Koopmans 起获得了诺贝尔经济学奖。 1947年G . B. Dantzig在研究美国空军军事规划时提出了线性规划的模型和单纯形解 法，并很快引起美国著名经济学家Koopmans的注意。Koopmans为此

2、呼吁当时年轻的经济 学家要关注线性规划。今天，单纯形法及其理论已成为了线性规划的一个重要的部分。 2. 线性规划模型的形式是什么？ 目标函数和约束条件都是线性的。 3. 线性规划模型的三要素是什么？ 就是资源向量b,价值向量c,系数矩阵A （般都假设 A是满秩的）。其中，资源向量 b表示了稀缺资源的种类和限度；价值向量c反映了单位产品（广义）所创造的收益或形成 的成本；而系数矩阵 A是现有生产技术、生产工艺、管理水平的具体体现。只要这三个要 素确定了，相应的线性规划模型就确定了。 4. 线性规划模型的经济意义何在？ 简言之，线性规划模型对于解决经济学研究的核心问题一一资源有效配置有比较重要的

3、意义。它不仅为宏观或微观的经济研究提供了一个有效的解决问题的平台，而且，（曾经） 为经济学家提供了一个解决资源优化配置的新的思路。不仅如此，线性规划在企业的运作管 理、物流管理、财务管理、人力资源管理、战略管理等诸多方面也能为管理者提供科学的决 策支持。 5. 线性规划的标准形式是怎样的? 线性规划的标准形式有三个特点： a) 约束条件都是等式； b) 等式约束的右端项为非负的常数； c) 每个变量都要求取非负数值。 下面是线性规划标准形式的一般表达， 6. 线性规划标准形的向量矩阵形式是怎样的？ 线性规划的标准形式如用向量矩阵形式可简洁表述为： 7. 在将线性规划的一般形式转化为标准形式时，

4、要注意哪几点？ 要注意两点：一是某一约束条件为“w”或形式的不等式时，应“+ ”一个非负 松弛变量或“-”非负松弛变量；二是某个变量不满足非负约束时，这个变量要用一到两 个非负的新变量替换，以使标准型中所有的变量均满足非负要求。 8. 如何将下述一般形式的线性规划问题转化为标准形？ Min Z=xi + 2x2 + 3x3 S.t. 2X1 + X2 + X3W 9 3xi +X2 + 2x3 4 3xi 2x2 3x3 = 6 xi w 0, X2 0, X3 任意。 答： 令 Xi = X1,贝y X1 = xi(新变量替换)，且 xi 0； 令X3 = X3 X3”（两个新变量替换），且

5、X3 , X3” 0； 在第一和第二个不等式约束中分别引入松弛变量：X4, X5 ,且X4 , X5 0 ；同时将第三 个约束条件的两边同时乘以 （1），以将右边常数项“6”转化为“ 6”。由此，上述线性规 划的一般形式转化为标准形。 Max Z =Xi 2X2 3(X3 X3”) 2x1 + X2 + (X3 X3) + X4 =9 3X1 + X2 + 2( X3 X3) X5 = 4 3x1 + 2X2 + 3 ( X3 X3) =6 Xi, X2 , X3，X3, X4,X5 0 . 9. 线性规划求解所需的基本概念，包含哪些? 包含可行解、可行域、最优解、基、基向量、基变量、非基变量

6、、基解、基本可行解、 退化的基本可行解、可行基、最优基等，且概念间存在紧密的关系。 10. 什么是可行解？ 满足所有约束条件的解被称为可行解。 11. 什么是可行域？ 所有可行解的集合被称为可行域。 12. 什么是最优解？ 使目标函数值取得最优的可行解被称为最优解。 13. 基的定义是什么？ Z. 基是由系数矩阵A中的线性无关的列向量构成的可逆方阵。 14. 什么是基向量？ 用来构成基的列向量称为该基的基向量。 15. 一个线性规划模型的基是唯一的吗？ 一般不是。只要构成基的列向量不完全相同，基就不同。因此，基一般可能有多个，但 数目最多不超过. 16. 仅有列向量排列顺序不同的那些基是否被视

7、为相同的基？ 是的。仅有列向量排列顺序不同的那些基被视为相同的基。 17. 什么是基变量？ 一个线性规划模型的系数矩阵A中的每个列向量实际上是每个变量在所有约束条件中 的系数排成列构成的。 当某个基被选定之后， 这个基所含的系数矩阵的列向量所对应的那些 变量就被称为这个基的基变量。 18. 什么是非基变量？ 当某个基被选定之后，这个基所含的系数矩阵的列向量所对应的那些变量就被称为这 个基的基变量，而其余的变量就被称为这个基的非基变量。 19. 什么是基解？ 在一个线性规划模型的标准型下，当某个基被选定之后，这个基对应的非基变量值都 被令为0，此时这个线性规划模型标准型的约束条件部分就成为了一个

8、仅包含基变量的线性 方程组，求解这个线性方程组就可以把此时该基对应的基变量的值求出来。这种做法求出的 所有变量的值，被称为该基对应的基解。一般地，也常将这种做法得到的该基所有基变量的 值称为基解。 20. 什么是基本可行解? 当某个基被选定之后，如果计算出该基的基解0,即其中每个基变量的值都是 0,则 此基解被称为基本可行解。 21. 什么是可行基？ 如果某个基对应的基解是基本可行解，则该基被称为可行基。 22. 什么是退化的基本可行解？ 当某个基被选定之后，如果计算出该基的基解0,即其中每个基变量的值都是 0,则 此基解被称为基本可行解。如果这个基本可行解中某个基变量的值=0,则此基本可行解

9、被 称为退化的基本可行解。 23. 什么是退化的可行基？ 如果某个基对应的基解是退化的基本可行解，则该基被称为退化的可行基。 24. 什么是最优基？ 如果某个基对应的基解是基本可行解，且是使目标函数值取得最优的最优解，则该基 被称为最优基。 25. 基、基变量、基解间的关系如何？ 基、基变量、基解间具有一一对应的关系。当某个基被确定下来后，该基对应的那些 基变量和非基变量就被确定下来，它们在这个基下的取值，即基解，也被确定下来。所以， 当谈到某个基变量或非基变量时，一定要指出是哪个基下的基变量或非基变量，同样地，当 谈到某个基解时，一定要指出是哪个基下的基解。 26. 求基解可以利用公式是什么

10、？ 求基解可以利用公式是 XB =B 1b,其中B是选定的基（矩阵），B 1是选定基的逆矩阵， b是线性规划模型的资源向量，即模型约束条件的右端常数项形成的列向量。这个公式可 以求出所选定的基对应的基变量向量Xb的值。 27. 求基解的公式Xb =1b中，基变量向量Xb中各分量的排列顺序必须与所 对应的基B中各基向量的排列顺序一致吗？ 必须保持一致。如基B=（PlP5P2）,则基变量向量Xb=（xiX5X2）T. 28. 基解仅指基变量（向量）Xb的值吗？ 严格地说，基解指的是某个基对应的所有基变量和非基变量及其取值。由于，非基变 量的值都被设定是 0,故为简便，基解也常指基变量（向量）Xb的

11、值。 29. 退化的基本可行解和基本可行解有何区别？ 基本可行解只要求基解 Xb = B%0.若某个基解Xb = B %0，但Xb = B%0, 即存某基变量的值为 0,则此时的基解被称为退化的基本可行解。同时，此基解对应的基被 称为退化的可行基。 30. 线性规划的几何意义何在？ 线性规划的几何意义体现在如下几点， a）线性规划的可行域是凸多面体，是凸集。 b）线性规划的任意一个可行解对应于可行域中的某个点 c）线性规划的基本可行解对应于可行域的顶点。 d）如果线性规划的可行域有界，则线性规划的可行域中的任意一个（点），都可用顶点的凸组 合线性表示。 e）若线性规划有最优解， 则最优解一定可

12、在某个基本可行解上取得，也即在可行域的某个顶点 （极点）上取得。 31. 图解法适应于哪种线性规划问题? 图解法适应于那种仅包含两个变量的线性规划问题。 32. 用图解法求解线性规划问题的步骤是怎样的？ a）首先，按约束条件在已建立的坐标轴上绘出该线性规划问题的可行域；如果可行域不存在， 则该线性规划问题无可行解，图解法停止，否则转到步骤b ； b）画岀目标函数值 z=cx=O时的目标函数等值线； C）判断使目标函数值得到改进的目标函数等值线的移动方向； d）沿所判断的改进方向，将目标函数等值线平行推移至可行域的边界，且任何继续推移将使 可行域内无点在等值线上时停住。此时，目标函数等值线上与可

13、行域相切的哪些点，就对应着 该线性规划问题的最优解，转到步骤e ；如果沿所判断的改进方向，平移目标函数等值线的过程 永无止境，则意味着该线性规划问题目标函数值无界，它没有最优解，图解法停止； e）观察或计算岀最优解。 33. 如何用图解法求解如下线性规划模型？ Max Z=2 xi + x2 xiw 3 3xi + X2 w 12 xi + x2 w 5 xi, x2 0 答： z. a) 首先，按约束条件在已建立的坐标轴上绘出该线性规划问题的可行域,如下图阴影区域 AB CD所示； b) 画岀目标函数值 z= 2xi + X2 =0时的目标函数等值线； c) 由目标函数 Z=2 xi + X

14、2做等价变形得到 X2 = 2xi +乙 知，目标函数值 Z即是目标函数等 值线的纵截距。在可行域内寻求目标值Z取最大，即寻求目标函数等值线的纵截距取最大。当 目标函数等值线从过原点的位置 (Z=0, 2xi + X2=0)向右移动时，其对应的纵截距从0开始增大; d) 这个过程直到目标函数等值线到达可行域的顶点B为止。 e) B点对应的坐标(3, 2),即是该线性规划问题的最优解。 34. 如何实现求最大值的线性规划问题与求最小值的线性规划问题的相互转 化？ 一般而言，只须将求最小值的线性规划问题的目标函数系数反号，并将符号“ MIN转换 为“MAX就可将其转化为求最大值的线性规划问题。反之

15、，只须将求最大值的线性规划问 题的目标函数系数反号，并将符号“ MAX转换为“ MIN就可将其转化为求最小值的线性规 划问题。 35. 如何求一个线性规划问题某个基 B下的检验向量？ 利用公式CbB 1A c来求。其中，A是系数矩阵，c是价值向量，cb是该基基变量的目 标函数系数所形成的行向量。 36. 当求一个线性规划问题某个基 B下的检验向量时，如何写出公式 cbB 1A C中的CB向量？ CB是该基基变量的目标函数系数所形成的行向量，其分量排列顺序必须与所对应的基 B 中各基向量的排列顺序一致，也即与此时基变量向量Xb中各分量的排列顺序一致。如基 B =(P1P5P2),则基变量向量Xb

16、=(X1X5X2)T,CB=(C1C5C2 ). z. 37. 求最大值和求最小值的线性规划问题，其最优判别定理有何区别? 其区别主要体现在检验向量上。 当线性规划模型的目标函数为 MAX Z时，对于某可行基B (0 ),若检验向量 cbB c 0,则与基B对应的基本可行解 xb= Bxn=O为最优解(基本最优解)，此时 的基B称为最优基。 当线性规划模型的目标函数为 MIN Z时，对于某可行基 B ( B 1b0 ),若检验向量 cbB 1A cw0,则与基B对应的基本可行解 xb= B 1b, xn=0为最优解(基本最优解)，此 时的基B称为最优基。 38. 当一个线性规划问题的基确定后，

17、此时变量xj的检验数j如何求？ 利用公式j =cbB 1Pj cj来求，其中，Pj是系数矩阵 A中变量xj对应的列向量。cj 是变量Xj在目标函数中的系数。 39. *最优判别定理是如何推导出的？ 仅就求MAX的线性规划问题且已化为标准形后的情形予以讨论。 设X是任一可行解，B是某个可行基(B 1b 0),此基下的基解对应的目标函数值为 ,且检验向量cbB 1A O 0, 则在约束条件的左右两边同时乘以，得到 将此式加到F=cx，则得到 因为cbB 1A O 0, x 0,所以，-门人_ .即任一可行解x对应的目标函数值 F 都不超过基B的基解对应的目标函数值,故，与基B对应的基本可行解 xb

18、= B 1b, x N=0为最优解(基本最优解)，此时的基B称为最优基。 40. 是否单纯形法的初始基一定要是单位阵？ 这是不一定的。之所以计算时，初始基一般都用单位阵，原因有两个：一个是单位阵 样的基确实存在；另一个是单位阵的逆矩阵最简单易求。实际上，从任何一个基开始单纯形 法的计算都是可以的。 41. 单纯形法的思想是怎样的？ 因为只要最优解存在，就一定可在某个基本可行基上取得。而可行基有多个，不可能 用穷举法逐一验证，得到最优基，故采取换基迭代的方法，从容易计算其逆的初始基对应的 单纯形表开始，逐步得到不同的可行基对应的单纯形表， 直至找到最优基对应的单纯形表为 止。 42. 换基迭代的

19、过程实质是什么？ 换基迭代的过程实质上是将一个基对应的单纯形表转到另一个基对应的单纯形表的不 断在目标函数值上进行改进的过程。其核心内容是利用初等行变换求另一个基的逆矩阵。所 以，对于线性代数比较熟练的人而言，换基迭代还可直接通过初等行变换进行。换基迭代的 公式实际上就是这一过程的具体体现。 43. 完整的单纯形法的计算步骤是怎样的？ 计算步骤可见下图。 44. 如何用单纯形法求解如下线性规划问题？ Max Z=2 xi + X2 xiw 3 3xi + X2 w 12 Xi + X2 w 5 xi, x2 0 答： a) 引入松弛变量 X3, X4, X5化为标准形 Max Z=2xi +

20、x2 S.t.X1 + X3 =3 3 X1 + X2 + X4 =12 X1 + X2 + X5 =5 X1, X2 , X3, X4, X5 0 b）单纯形法求解过程 c）最优解为 xi =3, X2=2, x3=0, X4=1, x5=0. 45. 每张单纯形表的基是否相同？ 每张单纯形表的基是不相同的，一个基一一对应于一张单纯形表。 46. 单纯形法出现死循环的情形如何避免？ 当存在退化的基本可行解时，可能会出现死循环的情形。 为避免此情形的发生， 可运用 BLAND法则，即确定谁入基时，若最小负检验数不唯一，则选位置最靠前的检验数处入基； 确定主元素时，若最小比值不唯一，则将取得最小

21、比值的入基列中位置最靠前的元素，作为 主元素。其它的方法还有几种，可自己去寻找相应的参考书。 47. 如下线性规划问题中，单纯形法求解过程的每张表所显示的基本可行解对 应于图中可行域上的哪个点？ Max Z=2x1 + X2 s.t. X1 w 3 3 X1 + X2 w 12 X1 + X2 w 5 X1, X2 0 z. 答: a）单纯形法求解过程 b）图解法 c）对应关系 每张单纯形表所对应的可行基 (P3, P4, P5) (P1 , P4, P5) (P1, P4, P2) 每张单纯形表所显示的基本可行解 (0 0 3 12 5) (3 0 0 3 2) (3 2 0 1 0) 基本

22、可行解所对应的图示可行域顶点 D A B 48. 当在系数矩阵A中，找不到单位阵形式的基作为初始基时，怎么办？ 当在系数矩阵 A中，找不到单位阵形式的基作为初始基时，一种直观的思想可供借鉴 构造一个与现在的线性规划有密切关系的新的线性规划问题，通过求解这个新的线性规 划问题，从而找出原线性规划的最优解。这种思想产生了两种典型做法：大M法、两阶段 法，统称人工变量法。 49. 大M法的参数M表示的是无穷大的数吗？ M在计算时，可看作一个非常大的参数（非严格的说法，仅为便于检验数含M时值的 正负判断），但M并不是无穷大，理论上可以证明，M只要取到某个数值以上就可以了。 50. 大M法的解与原线性规

23、划问题解的关系是什么？ 大M法的解与原线性规划问题解的关系是 i. 若原线性规划问题有最优解 X*，则-是线性规划问题（大 M法）的最优解。 胡宀 ii. 若线性规划问题（大M法）有最优解，则X*是原线性规划问题（L） 的最优解。 iii. 若线性规划问题（大 M法）没有最优解，则原线性规划问题也无最优解。 则原线性规划问 iv.若线性规划问题（大 M法）有最优解，但其最优解 题也无最优解。 51. 如何用大M法求解如下的线性规划问题？ Min Z=2xi + 3x2 + X3 s.t.xi+ 4x2 + 2x3 8 3xi + 2x2 6 xi, X2 , x3 0 答： a）原问题的标准形式如下， Min Z=2xi + 3x2+ X3 S.t.xi+ 4x2 + 2X3 X4= 8 3xi + 2x2 x5= 6 xi, X2 , X3, X4 , x5 0 显然，该线性规划问题没有单位阵样的初始基。 b）运用大M法，构造一个新的线性规划问题（P） Min Z=2xi + 3x2 + X3 + My6+ My7