线性规划常见疑问解答

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

2、时年轻的经济学家要关注线性规划。今天，单纯形法及其理论已成为了线性规划的一个重要的部分。2. 线性规划模型的形式是什么？目标函数和约束条件都是线性的。竝或irun）£ =门猊+人+徐"證si.+呵2+<(=,>)+<(=>)UUU+<(=,>)%$般形式）3. 线性规划模型的三要素是什么?就是资源向量b,价值向量C,系数矩阵A （般都假设 A是满秩的）。其中，资源向量 b表示了稀缺资源的种类和限度；价值向量c反映了单位产品（广义）所创造的收益或形成的成本；而系数矩阵 A是现有生产技术、 生产工艺、管理水平的具体体现。只要这三个要素确定了，

3、相应的线性规划模型就确定了。4. 线性规划模型的经济意义何在？（曾经）简言之，线性规划模型对于解决经济学研究的核心问题一一资源有效配置有比较重要的 意义。它不仅为宏观或微观的经济研究提供了一个有效的解决问题的平台，而且，为经济学家提供了一个解决资源优化配置的新的思路。不仅如此，线性规划在企业的运作管理、物流管理、财务管理、人力资源管理、战略管理等诸多方面也能为管理者提供科学的决策支持。5. 线性规划的标准形式是怎样的?线性规划的标准形式有三个特点：a）约束条件都是等式；b）等式约束的右端项为非负的常数；c）每个变量都要求取非负数值。下面是线性规划标准形式的一般表达,JWfejt （或 min）

4、 z z Ci jt；+A + cnxn+ a12 x2 心+ a2Xx2 M M M 口讥乃 +乃（标堆形式）st6. 线性规划标准形的向量矩阵形式是怎样的?线性规划的标准形式如用向量矩阵形式可简洁表述为:Ax = b沦 Q t>0.7. 在将线性规划的一般形式转化为标准形式时，要注意哪几点?要注意两点：一是某一约束条件为“w”或形式的不等式时，应“+” 一个非负松弛变量或“-”非负松弛变量；二是某个变量不满足非负约束时，这个变量要用一到两个非负的新变量替换，以使标准型中所有的变量均满足非负要求。10. 什么是可行解?满足所有约束条件的解被称为可行解。11. 什么是可行域？所有可行解的

5、集合被称为可行域。12. 什么是最优解？使目标函数值取得最优的可行解被称为最优解。13. 基的定义是什么？基是由系数矩阵A中的线性无关的列向量构成的可逆方阵。14. 什么是基向量？用来构成基的列向量称为该基的基向量。15. 一个线性规划模型的基是唯一的吗？一般不是。只要构成基的列向量不完全相同，基就不同。因此，基一般可能有多个，但 数目最多不超过.17. 什么是基变量？一个线性规划模型的系数矩阵 A中的每个列向量实际上是每个变量在所有约束条件中 的系数排成列构成的。 当某个基被选定之后， 这个基所含的系数矩阵的列向量所对应的那些 变量就被称为这个基的基变量。18. 什么是非基变量？当某个基被选

6、定之后，这个基所含的系数矩阵的列向量所对应的那些变量就被称为这 个基的基变量，而其余的变量就被称为这个基的非基变量。19. 什么是基解？在一个线性规划模型的标准型下，当某个基被选定之后，这个基对应的非基变量值都被令为 0，此时这个线性规划模型标准型的约束条件部分就成为了一个仅包含基变量的线性 方程组， 求解这个线性方程组就可以把此时该基对应的基变量的值求出来。这种做法求出的所有变量的值， 被称为该基对应的基解。 一般地， 也常将这种做法得到的该基所有基变量的 值称为基解。20. 什么是基本可行解？当某个基被选定之后，如果计算出该基的基解0,即其中每个基变量的值都是 0,则此基解被称为基本可行解

7、。21. 什么是可行基？如果某个基对应的基解是基本可行解，则该基被称为可行基。22. 什么是退化的基本可行解？当某个基被选定之后，如果计算出该基的基解 0,即其中每个基变量的值都是 0, 则此基解被称为基本可行解。如果这个基本可行解中某个基变量的值= 0,则此基本可行解 被称为退化的基本可行解。24. 什么是最优基？如果某个基对应的基解是基本可行解，且是使目标函数值取得最优的最优解，则该基 被称为最优基。25. 基、基变量、基解间的关系如何？基、基变量、基解间具有一一对应的关系。当某个基被确定下来后，该基对应的那些 基变量和非基变量就被确定下来，它们在这个基下的取值，即基解，也被确定下来。所以

8、， 当谈到某个基变量或非基变量时， 一定要指出是哪个基下的基变量或非基变量， 同样地， 当 谈到某个基解时，一定要指出是哪个基下的基解。26. 求基解可以利用公式是什么？求基解可以利用公式是 Xb =bTb,其中B是选定的基（矩阵），B_是选定基的逆矩阵， b 是线性规划模型的资源向量，即模型约束条件的右端常数项形成的列向量。这个公式可以求出所选定的基对应的基变量向量 XB 的值。27. 求基解的公式Xb =1b中，基变量向量Xb中各分量的排列顺序必须与所对 应的基B中各基向量的排列顺序一致吗？必须保持一致。如基 B= (P1 P5 P2), 则基变量向量 XB= ( x1 x5 x2 ) T

9、 .28. 基解仅指基变量(向量) XB 的值吗？严格地说，基解指的是某个基对应的所有基变量和非基变量及其取值。由于，非基变 量的值都被设定是 0，故为简便，基解也常指基变量(向量) XB 的值。29. 退化的基本可行解和基本可行解有何区别？基本可行解只要求基解 Xb = B -1b> 0.若某个基解 Xb = B Tb0,但Xb = B 一 1b>0,即 存某基变量的值为 0，则此时的基解被称为退化的基本可行解。同时，此基解对应的基被称 为退化的可行基。30. 线性规划的几何意义何在？线性规划的几何意义体现在如下几点,a) 线性规划的可行域是凸多面体,是凸集。b) 线性规划的任意

10、一个可行解对应于可行域中的某个点。c) 线性规划的基本可行解一一对应于可行域的顶点。d) 如果线性规划的可行域有界,则线性规划的可行域中的任意一个(点),都可用顶点的凸组 合线性表示。e) 若线性规划有最优解,则最优解一定可在某个基本可行解上取得,也即在可行域的某个顶 点(极点)上取得。31. 图解法适应于哪种线性规划问题？图解法适应于那种仅包含两个变量的线性规划问题。32. 用图解法求解线性规划问题的步骤是怎样的？a) 首先，按约束条件在已建立的坐标轴上绘出该线性规划问题的可行域；如果可行域不存在， 则该线性规划问题无可行解，图解法停止，否则转到步骤b；b) 画出目标函数值 z=cx=0 时

11、的目标函数等值线；c) 判断使目标函数值得到改进的目标函数等值线的移动方向；d) 沿所判断的改进方向，将目标函数等值线平行推移至可行域的边界，且任何继续推移将使 可行域内无点在等值线上时停住。 此时， 目标函数等值线上与可行域相切的哪些点， 就对应着该线性规划问题的最优解，转到步骤 e；如果沿所判断的改进方向，平移目标函数等值线的过程永 无止境，则意味着该线性规划问题目标函数值无界，它没有最优解，图解法停止；e) 观察或计算出最优解。33. 如何用图解法求解如下线性规划模型？Max Z=2x1 x2xi < 33xi + X2 w 12xi + X2 w 5Xi, X2>0答：a)

12、 首先，按约束条件在已建立的坐标轴上绘出该线性规划问题的可行域，如下图阴影区域 ABCD所示；b) 画出目标函数值 z= 2X1X2 =0 时的目标函数等值线；c) 由目标函数 Z=2Xi + X2做等价变形得到 X2 = 2Xi+乙 知，目标函数值 Z即是目标函数等值 线的纵截距。在可行域内寻求目标值 Z 取最大，即寻求目标函数等值线的纵截距取最大。当目 标函数等值线从过原点的位置 (Z=0, 2 XiX2=0) 向右移动时，其对应的纵截距从 0 开始增大；e）B点对应的坐标（3, 2）,即是该线性规划问题的最优解。、函值 标等 r目数鹽丿薯值銭右移纵 截距即目标 函数值増大-34. 如何实

13、现求最大值的线性规划问题与求最小值的线性规划问题的相互转化？一般而言，只须将求最小值的线性规划问题的目标函数系数反号，并将符号 Min”转换为max就可将其转化为求最大值的线性规划问题。反之，只须将求最大值的线性规划问题的目标函数系数反号，并将符号max转换为min”就可将其转化为求最小值的线性规划问题。35. 如何求一个线性规划问题某个基 B下的检验向量？利用公式CbB1A- c来求。其中，A是系数矩阵，c是价值向量，CB是该基基变量的目标 函数系数所形成的行向量。38. 当一个线性规划问题的基确定后，此时变量Xj的检验数G如何求？利用公式q =CbB1P - Cj来求，其中，P是系数矩阵A

14、中变量X对应的列向量。Cj是 变量Xj在目标函数中的系数。39. *最优判别定理是如何推导出的？仅就求MAX勺线性规划问题且已化为标准形后的情形予以讨论。设x是任一可行解，B是某个可行基(B 1b>0),此基下的基解对应的目标函数值为'工,且检验向量CbB_ 1A c> 0,则在约束条件的左右两边同时乘以，得到将此式加到F=cx,则得到因为CbB1A c > 0, x> 0,所以，二'.即任一可行解x对应的目标函数值 F都不超过基b的基解对应的目标函数值 V' 11,故，与基b对应的基本可行解 xb= b 1b, xn=0为最优解(基本最优解)，

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

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

17、, X5> 0b）单纯形法求解过程ro -2 -1 0丁B =（号片）30 11231 011 0左00 1310 100 -2201 -1X4=1, X5=0.c) 最优解为 Xi=3, X2=2, X3=0,45. 每张单纯形表的基是否相同?每张单纯形表的基是不相同的，一个基一一对应于一张单纯形表。46. 单纯形法出现死循环的情形如何避免?当存在退化的基本可行解时，可能会出现死循环的情形。为避免此情形的发生， 可运用BLAND法则，即确定谁入基时，若不唯一，则选位置最靠前的检验数处入基；确定主元素时，若最小比值不唯一，则将取得最小比值的入基列中位置最靠前的元素，作为主元素。其它的方法

18、还有几种，可自己去寻找相应的参考书。47. 如下线性规划问题中，单纯形法求解过程的每张表所显示的基本可行解对 应于图中可行域上的哪个点？Max Z=2X1 + X2s.t.X1< 3 3 X1 + X2 < 12 xi,X2 > 0答：a)单纯形法求解过程o目标函数等值一种直观的思想可供借鉴一b)图解法等值线右移-纵 琶距Z即目标 函数值增犬卩C) 对应关系每张单纯形表所对应的可行基(P3, P 4, P 5)(Pi, P 4, P 5)(Pi, P 4, P 2)每张单纯形表所显示的基本可行解(0 0 3 12 5)(3 0 0 3 2)(3 2 0 1 0)基本可行解所对

19、应的图示可行域顶点DAB48. 当在系数矩阵A中，找不到单位阵形式的基作为初始基时，怎么办?当在系数矩阵A中，找不到单位阵形式的基作为初始基时,构造一个与现在的线性规划有密切关系的新的线性规划问题，通过求解这个新的线性规划问题，从而找出原线性规划的最优解。这种思想产生了两种典型做法：大M法、两阶段法，统称人工变量法。49. 大M法的参数M表示的是无穷大的数吗？M在计算时，可看作一个非常大的参数（非严格的说法，仅为便于检验数含 M时值的正 负判断），但M并不是无穷大，理论上可以证明，M只要取到某个数值以上就可以了。50. 大M法的解与原线性规划问题解的关系是什么？大M法的解与原线性规划问题解的关系是i. 若原线性规划问题有最优解 X*，则I是线性规划问题（大 M法）的最优解。ii. 若线性规划问题（大M法）有最优解V /，则X是原线性规划问题（L）的最优解。iii. 若线性规划问题（大 M法）没有最优解，则原线性规划问题也无最优解。£iv. 若线性规划问题（大 M法）有最优解，但其最优解 V / ，则原线性规划问 题也无最优解。51. 如何用大M法求解如下的线性规划