线性规划常见疑问

线性规划常见疑问第一章 线性规划 常见疑问解答1、线性规划这一运筹学重要分支的开创者就是谁？这里,必须谈到两个著名的人物,康托洛维奇与丹捷格。1939 年著名数理经济学者康托洛维奇发表了生产组织与计划中的数学方法这一运 筹学的先驱性名著,其中已提到类似线性规划的模型与“解乘数求解法”。但就是她的工作直到 1960 年的最佳资源利用的经济计算一书出版后,才得到重视。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=x12x23x3s、t、一2X+ x2 +X3W 93X + x?+ 2X3 三43X 2x2一 3Xg=6X WO, x2 三0, x3 任意。答:令X' =X,则X=X'（新变量替换），且X'三0;令x3 = X3' x3”（两个新变量替换），且x3' ,x3”三0；在第一与第二个不等式约束中分别引入松弛变量：x4,x5 ,且x4,x5三0;同时将第三个约束 条件的两边同时乘以（）,以将右边常数项“6”转化为“6”。由此,上述线性规划的一般 形式转化为标准形。Max Z' =X' 2X23 (X3' X3")2X'X2 (X3' X3")X4=93X'X22( X3' X3") X5 = 43X'2X23 ( X3' X3")=6X2 , X3',x3" , x4, x5±0、9、线性规划求解所需的基本概念,包含哪些？包含可行解、可行域、最优解、基、基向量、基变量、非基变量、基解、基本可行解 退化的基本可行解、可行基、最优基等,且概念间存在紧密的关系。10、什么就是可行解？满足所有约束条件的解被称为可行解。11、什么就是可行域？所有可行解的集合被称为可行域。12、什么就是最优解？使目标函数值取得最优的可行解被称为最优解。13、基的定义就是什么？基就是由系数矩阵A中的线性无关的列向量构成的可逆方阵。14、什么就是基向量？用来构成基的列向量称为该基的基向量。15、一个线性规划模型的基就是唯一的不？一般不就是。只要构成基的列向量不完全相同,基就不同。因此,基一般可能有多个,但数目最多不超过用、16、仅有列向量排列顺序不同的那些基就是否被视为相同的基？就是的。仅有列向量排列顺序不同的那些基被视为相同的基。17、什么就是基变量？一个线性规划模型的系数矩阵 A 中的每个列向量实际上就是每个变量在所有约束条件 中的系数排成列构成的。当某个基被选定之后,这个基所含的系数矩阵的列向量所对应的那 些变量就被称为这个基的基变量。18、什么就是非基变量？当某个基被选定之后,这个基所含的系数矩阵的列向量所对应的那些变量就被称为这个 基的基变量,而其余的变量就被称为这个基的非基变量。19、什么就是基解？在一个线性规划模型的标准型下 ,当某个基被选定之后,这个基对应的非基变量值都被 令为 0,此时这个线性规划模型标准型的约束条件部分就成为了一个仅包含基变量的线性方 程组,求解这个线性方程组就可以把此时该基对应的基变量的值求出来。这种做法求出的所 有变量的值,被称为该基对应的基解。一般地,也常将这种做法得到的该基所有基变量的值称 为基解。20、什么就是基本可行解？当某个基被选定之后，如果计算出该基的基解三0,即其中每个基变量的值都就是三0, 则此基解被称为基本可行解。21、什么就是可行基？如果某个基对应的基解就是基本可行解,则该基被称为可行基。22、什么就是退化的基本可行解？当某个基被选定之后，如果计算出该基的基解三0,即其中每个基变量的值都就是三0, 则此基解被称为基本可行解。如果这个基本可行解中某个基变量的值=0,则此基本可行解 被称为退化的基本可行解。23、什么就是退化的可行基？如果某个基对应的基解就是退化的基本可行解,则该基被称为退化的可行基。24、什么就是最优基？如果某个基对应的基解就是基本可行解 ,且就是使目标函数值取得最优的最优解 ,则该 基被称为最优基。25、基、基变量、基解间的关系如何？基、基变量、基解间具有一一对应的关系。当某个基被确定下来后,该基对应的那些基 变量与非基变量就被确定下来,它们在这个基下的取值,即基解,也被确定下来。所以,当谈到某 个基变量或非基变量时,一定要指出就是哪个基下的基变量或非基变量,同样地,当谈到某个 基解时,一定要指出就是哪个基下的基解。26、求基解可以利用公式就是什么？求基解可以利用公式就是XB =B-ib,其中B就是选定的基（矩阵）,Bt就是选定基的逆 矩阵, b 就是线性规划模型的资源向量,即模型约束条件的右端常数项形成的列向量。这个公 式可以求出所选定的基对应的基变量向量XB的值。27、求基解的公式XB =Brb中，基变量向量XB中各分量的排列顺序必须与所 对应的基B中各基向量的排列顺序一致不？必须保持一致。如基B= (P P5 P2),则基变量向量XB= ( x1 x5 x2 )t、28、基解仅指基变量(向量)XB的值不？严格地说,基解指的就是某个基对应的所有基变量与非基变量及其取值。由于,非基变量 的值都被设定就是0,故为简便，基解也常指基变量(向量)xB的值。29、退化的基本可行解与基本可行解有何区别？基本可行解只要求基解XB = B-ib±0、若某个基解XB = B-ib±0,但XB = B-ib>0, 即存某基变量的值为 0,则此时的基解被称为退化的基本可行解。同时,此基解对应的基被称 为退化的可行基。30、线性规划的几何意义何在？线性规划的几何意义体现在如下几点,a) 线性规划的可行域就是凸多面体,就是凸集。b) 线性规划的任意一个可行解对应于可行域中的某个点。c) 线性规划的基本可行解一一对应于可行域的顶点。d) 如果线性规划的可行域有界,则线性规划的可行域中的任意一个 (点),都可用顶点的凸组合线 性表示。e) 若线性规划有最优解,则最优解一定可在某个基本可行解上取得 ,也即在可行域的某个顶点 (极点)上取得。31、图解法适应于哪种线性规划问题？图解法适应于那种仅包含两个变量的线性规划问题。32、用图解法求解线性规划问题的步骤就是怎样的？a) 首先,按约束条件在已建立的坐标轴上绘出该线性规划问题的可行域 ;如果可行域不存在,则 该线性规划问题无可行解,图解法停止,否则转到步骤 b;b) 画出目标函数值 z=cx=0 时的目标函数等值线;c) 判断使目标函数值得到改进的目标函数等值线的移动方向 ;d) 沿所判断的改进方向,将目标函数等值线平行推移至可行域的边界 ,且任何继续推移将使可 行域内无点在等值线上时停住。此时,目标函数等值线上与可行域相切的哪些点,就对应着该线性 规划问题的最优解，转到步骤e；如果沿所判断的改进方向，平移目标函数等值线的过程永无止境， 则意味着该线性规划问题目标函数值无界,它没有最优解,图解法停止;e) 观察或计算出最优解。33、如何用图解法求解如下线性规划模型？Max Z=2x1x2X W33X+x2 W12X+x2 W5X, x2±0答:a) 首先,按约束条件在已建立的坐标轴上绘出该线性规划问题的可行域,如下图阴影区域 ABC D 所示;b) 画出目标函数值 z= 2x1x2 =0 时的目标函数等值线;c) 由目标函数z=2x1+x2做等价变形得到x2= -2x1+Z,知，目标函数值Z即就是目标函数等 值线的纵截距。在可行域内寻求目标值Z取最大，即寻求目标函数等值线的纵截距取最大。当目 标函数等值线从过原点的位置(Z=0, 2x1+x2=0)向右移动时，其对应的纵截距从0开始增大；d) 这个过程直到目标函数等值线到达可行域的顶点 B 为止。e) B 点对应的坐标(3, 2), 即就是该线性规划问题的最优解。34、如何实现求最大值的线性规划问题与求最小值的线性规划问题的相互转 化？一般而言，只须将求最小值的线性规划问题的目标函数系数反号，并将符号“MIN”转换为 “MAX”就可将其转化为求最大值的线性规划问题。反之，只须将求最大值的线性规划问题的 目标函数系数反号，并将符号“MAX”转换为“MIN”就可将其转化为求最小值的线性规划问 题。35、如何求一个线性规划问题某个基B下的检验向量？利用公式cBB-iA-c来求。其中,A就是系数矩阵,c就是价值向量,cB就是该基基变量的 目标函数系数所形成的行向量。36、当求一个线性规划问题某个基 B 下的检验向量时，如何写出公式 cBB-1A- c 中的 cB 向量？cB 就是该基基变量的目标函数系数所形成的行向量，其分量排列顺序必须与所对应的基 B中各基向量的排列顺序一致，也即与此时基变量向量XB中各分量的排列顺序一致。如基B = (P1 P5 P2)， 则基变量向量 XB= ( x1 x5 x2 )T， cB= ( c1 c5 c2 )、37、求最大值与求最小值的线性规划问题,其最优判别定理有何区别？其区别主要体现在检验向量上。当线性规划模型的目标函数为MAX Z时,对于某可行基B ( B-ib0 ),若检验向量 cbBtAc±0,贝9与基B对应的基本可行解xB= B-ib, xN=0为最优解(基本最优解),此时的 基 B 称为最优基。当线性规划模型的目标函数为MIN Z时,对于某可行基B ( B-ib20 ),若检验向量 cBB