线性规划常见疑问.docx

第一章 线性规划 常见疑问解答1. 线性规划——这一运筹学重要分支的开创者是谁？这里，必须谈到两个著名的人物，康托洛维奇和丹捷格1939 年著名数理经济学者康托洛维奇发表了《生产组织和计划中的数学法》这一运筹 学的先驱性名著，其中已提到类似线性规划的模型和“解乘数求解法”但是他的工作直到19 60年的《最佳资源利用的经济计算》一书出版后，才得到重视1975年，康托洛维奇与T.C . Koopmans 一起获得了诺贝尔经济学奖1947年G . B. Dantzig在研究美国空军军事规划时提出了线性规划的模型和单纯形解 法，并很快引起美国著名经济学家Koopmans的注意Koopmans为此呼吁当时年轻的经济 学家要关注线性规划今天，单纯形法及其理论已成为了线性规划的一个重要的部分2. 线性规划模型的形式是什么？目标函数和约束条件都是线性的3. 线性规划模型的三要素是什么？就是资源向量b,价值向量c,系数矩阵A （—般都假设A是满秩的）其中，资源向量 b表示了稀缺资源的种类和限度；价值向量c反映了单位产品（广义）所创造的收益或形成 的成本；而系数矩阵 A 是现有生产技术、生产工艺、管理水平的具体体现。

只要这三个要 素确定了,相应的线性规划模型就确定了4. 线性规划模型的经济意义在？简言之,线性规划模型对于解决经济学研究的核心问题——资源有效配置有比较重要的 意义它不仅为宏观或微观的经济研究提供了—个有效的解决问题的平台,而且,（曾经） 为经济学家提供了—个解决资源优化配置的新的思路不仅如此,线性规划在企业的运作管 理、物流管理、财务管理、人力资源管理、战略管理等诸多面也能为管理者提供科学的决策 支持5. 线性规划的标准形式是怎样的？线性规划的标准形式有三个特点：a） 约束条件都是等式；b） 等式约束的右端项为非负的常数；c） 每个变量都要求取非负数值下面是线性规划标准形式的一般表达，6. 线性规划标准形的向量矩阵形式是怎样的？线性规划的标准形式如用向量矩阵形式可简洁表述为：7. 在将线性规划的一般形式转化为标准形式时，要注意哪几点？要注意两点：一是某一约束条件为“W”或“三”形式的不等式时，应“+”一个非负松弛变量 或“－” 非负松弛变量；二是某个变量不满足非负约束时，这个变量要用一到两个非负的新 变量替换，以使标准型中所有的变量均满足非负要求8. 如将下述一般形式的线性规划问题转化为标准形？Min Z=x1＋2x2＋3x3s.t. -2x ＋x＋xw9123-3x ＋x＋2x三41233x -12x -23x =3-6X1 wo, x2 三0, x3任意。

令X1' =-xi，则X1=-X1'（新变量替换），且X；三0；令、二x3' -x3”（两个新变量替换），且x3' ,x3”三0;在第一和第二个不等式约束中分别引入松弛变量：X4,X5，且x4, x5三0;同时将第三 个约束条件的两边同时乘以（－1），以将右边常数项“－6”转化为“6”由此，上述线性规划的 一般形式转化为标准形MaX Z ' =X1' －2X2－3 （X3' －X3"）2X1'＋ X2＋ （X3' －X3"）＋X4 = 93X1'＋ X2＋2（ X3' －X3"） －X5= 43X'＋ 2X＋3 （ X' －X"） = 61 2 3 3X1‘，X2, X3', X3" , X4, X5三0 .9. 线性规划求解所需的基本概念，包含哪些？ 包含可行解、可行域、最优解、基、基向量、基变量、非基变量、基解、基本可行解 退化的基本可行解、可行基、最优基等，且概念间存在紧密的关系10. 什么是可行解？满足所有约束条件的解被称为可行解11. 什么是可行域？所有可行解的集合被称为可行域12. 什么是最优解？使目标函数值取得最优的可行解被称为最优解13. 基的定义是什么？基是由系数矩阵A中的线性无关的列向量构成的可逆阵。

14. 什么是基向量？用来构成基的列向量称为该基的基向量15. 一个线性规划模型的基是唯一的吗？一般不是只要构成基的列向量不完全相同，基就不同因此，基一般可能有多个，但数目最多不超过5 .16. 仅有列向量排列顺序不同的那些基是否被视为相同的基？是的仅有列向量排列顺序不同的那些基被视为相同的基17. 什么是基变量？一个线性规划模型的系数矩阵 A 中的每个列向量实际上是每个变量在所有约束条件中 的系数排成列构成的当某个基被选定之后，这个基所含的系数矩阵的列向量所对应的那些 变量就被称为这个基的基变量18. 什么是非基变量？当某个基被选定之后，这个基所含的系数矩阵的列向量所对应的那些变量就被称为这 个基的基变量，而其余的变量就被称为这个基的非基变量19. 什么是基解？在一个线性规划模型的标准型下，当某个基被选定之后，这个基对应的非基变量值都 被令为 0，此时这个线性规划模型标准型的约束条件部分就成为了一个仅包含基变量的线性 程组，求解这个线性程组就可以把此时该基对应的基变量的值求出来这种做法求出的所有 变量的值，被称为该基对应的基解一般地，也常将这种做法得到的该基所有基变量的值称 为基解20. 什么是基本可行解？当某个基被选定之后，如果计算出该基的基解三0,即其中每个基变量的值都是三0,则 此基解被称为基本可行解。

21. 什么是可行基？如果某个基对应的基解是基本可行解，则该基被称为可行基22. 什么是退化的基本可行解？当某个基被选定之后，如果计算出该基的基解三0,即其中每个基变量的值都是三0,则 此基解被称为基本可行解如果这个基本可行解中某个基变量的值=0,则此基本可行解被 称为退化的基本可行解23. 什么是退化的可行基？如果某个基对应的基解是退化的基本可行解，则该基被称为退化的可行基24. 什么是最优基？如果某个基对应的基解是基本可行解，且是使目标函数值取得最优的最优解，则该基 被称为最优基25. 基、基变量、基解间的关系如？基、基变量、基解间具有一一对应的关系当某个基被确定下来后，该基对应的那些 基变量和非基变量就被确定下来，它们在这个基下的取值，即基解，也被确定下来所以， 当谈到某个基变量或非基变量时，一定要指出是哪个基下的基变量或非基变量，同样地，当 谈到某个基解时，一定要指出是哪个基下的基解26. 求基解可以利用公式是什么？求基解可以利用公式是XB =B-lb，其中B是选定的基(矩阵)，B-1是选定基的逆矩阵，Bb 是线性规划模型的资源向量，即模型约束条件的右端常数项形成的列向量这个公式可 以求出所选定的基对应的基变量向量XB的值。

B27. 求基解的公式X =B-ib中，基变量向量X中各分量的排列顺序必须与所对BB应的基B中各基向量的排列顺序一致吗？必须保持一致如基B二(P. P5 P2),则基变量向量XB二(X1 x5 x2 )T .1 5 2 B 1 5 228. 基解仅指基变量(向量)XB的值吗？格地说，基解指的是某个基对应的所有基变量和非基变量及其取值由于，非基变量 的值都被设定是0,故为简便，基解也常指基变量(向量)XB的值B29. 退化的基本可行解和基本可行解有区别？基本可行解只要求基解XB二B-ib三0.若某个基解XB二B-ib三0,但XB二B-ib>0,B B B即存某基变量的值为 0,则此时的基解被称为退化的基本可行解同时,此基解对应的基被 称为退化的可行基30. 线性规划的几意义在？线性规划的几意义体现在如下几点,a) 线性规划的可行域是凸多面体，是凸集b) 线性规划的任意一个可行解对应于可行域中的某个点c) 线性规划的基本可行解一一对应于可行域的顶点d) 如果线性规划的可行域有界，则线性规划的可行域中的任意一个(点)，都可用顶点的凸组 合线性表示e) 若线性规划有最优解，则最优解一定可在某个基本可行解上取得，也即在可行域的某个顶点 (极点)上取得。

31. 图解法适应于哪种线性规划问题？图解法适应于那种仅包含两个变量的线性规划问题32. 用图解法求解线性规划问题的步骤是怎样的？a) 首先，按约束条件在已建立的坐标轴上绘出该线性规划问题的可行域；如果可行域不存在， 则该线性规划问题无可行解，图解法停止，否则转到步骤 b；b) 画出目标函数值 z=cx=0 时的目标函数等值线；c) 判断使目标函数值得到改进的目标函数等值线的移动向；d) 沿所判断的改进向，将目标函数等值线平行推移至可行域的边界，且任继续推移将使可行域 无点在等值线上时停住此时，目标函数等值线上与可行域相切的哪些点，就对应着该线性规划 问题的最优解，转到步骤e；如果沿所判断的改进向，平移目标函数等值线的过程永无止境，则 意味着该线性规划问题目标函数值无界，它没有最优解，图解法停止；e) 观察或计算出最优解33. 如用图解法求解如下线性规划模型？Max Z=2x ＋x12x W3 ①13x +x W12 ②12x +x W5 ③12x, x 三012a) 首先，按约束条件在已建立的坐标轴上绘出该线性规划问题的可行域，如下图阴影区域 AB CD 所示；b) 画出目标函数值 z= 2x1＋x2 =0 时的目标函数等值线；12c) 由目标函数Z=2x’ + x2做等价变形得到x2= -2X1 + Z, 知,目标函数值Z即是目标函数等值1 2 2 1线的纵截距。

在可行域寻求目标值Z取最大，即寻求目标函数等值线的纵截距取最大当目标 函数等值线从过原点的位置(Z=0, 2xi + x2=0)向右移动时，其对应的纵截距从0开始增大；d) 这个过程直到目标函数等值线到达可行域的顶点 B 为止e) B 点对应的坐标(3, 2), 即是该线性规划问题的最优解34. 如实现求最大值的线性规划问题与求最小值的线性规划问题的相互转化？—般而言，只须将求最小值的线性规划问题的目标函数系数反号，并将符号“MIN”转换 为“MAX”就可将其转化为求最大值的线性规划问题反之，只须将求最大值的线性规划问题 的目标函数系数反号，并将符号“MAX”转换为“MIN”僦可将其转化为求最小值的线性规划问题35. 如求一个线性规划问题某个基B下的检验向量？利用公式cBB-iA-c来求其中，A是系数矩阵，c是价值向量，CB是该基基变量的目BB 标函数系数所形成的行向量36. 当求一个线性规划问题某个基 B 下的检验向量时，如写出公式 cBB－1A－c 中的 cB 向量？CB是该基基变量的目标函数系数所形成的行向量，其分量排列顺序必须与所对应的基B B中各基向量的排列顺序一致，也即与此时基变量向量XB中各分量的排列顺序一致。

如基B二B（P1 P5 P2）-则基变量向量 XB= （ X1 X5 X2 ）T，CB= （ C1 C5 S ）"37. 求最大值和求最小值的线性规划问题，其最优判别定理有区别？其区别主要体现在检验向量上当线性规划模型的目标函数为MAX Z时，对于某可行基B （ B-ib三0 ）,若检验向量 cBB-iA-c三0,则与基B对应的基本可行解XB二B-ib, xn=0为最优解（基本最优解），此时 B B N的基 B 称为最优基当线性规划模型的目标函数为MIN Z时，对于某可行基B （ B-ib三0 ）,若检验向量CBB-1A-CWO,则与基B对应的基本可。