线性规划常见疑问

第一章线性规划中常见问题的解答1.谁是运筹学的一个重要分支线性规划的发起人？在这里，我们必须谈谈两个著名的人物，康塔洛维奇和邓蒂斯。1939年，著名的数学经济学家康塔洛维奇发表了运筹学的开创性杰作生产组织和计划中的数学方法，其中已经提到了类似线性规划的模型和“解乘数法”。然而，直到1960年的书最佳资源利用的经济计算出版，他的工作才被重视。1975年，康塔洛维奇和t c .库普曼获得了诺贝尔经济学奖。1947年，丹齐格在研究美国空军军事规划时提出了线性规划模型和单纯形法，很快引起了美国著名经济学家库普曼斯的注意。因此，库伯曼呼吁当时的年轻经济学家关注线性规划。今天，单纯形法及其理论已经成为线性规划的重要组成部分。2.线性规划模型的形式是什么？目标函数和约束是线性的。3.线性规划模型的三个要素是什么？是资源向量b、值向量c、系数矩阵a(通常假设a是满秩的)。其中，资源向量B表示稀缺资源的类型和限度；价值向量反映了单位产品产生的收入或成本(广义上)；系数矩阵A是现有生产技术、生产工艺和管理水平的具体体现。只要确定了这三个要素，就可以确定相应的线性规划模型。4.线性规划模型的经济意义是什么？总之，线性规划模型对于有效配置资源解决经济研究的核心问题具有重要意义。它不仅为宏观或微观经济研究提供了解决问题的有效平台，而且(曾经)为经济学家提供了解决资源优化配置的新思路。不仅如此，线性规划还可以在企业运营管理、物流管理、财务管理、人力资源管理、战略管理等诸多方面为管理者提供科学的决策支持。线性规划的标准形式是什么？线性规划的标准形式有三个特点：a)约束是等式；b)等式约束的正确项是非负常数；c)每个变量都需要一个非负值。以下是线性规划标准形式的一般表达式。6.线性规划标准形式的向量矩阵形式是什么？线性规划的标准形式，如向量矩阵，可以简洁地表示为：7.当把线性规划的一般形式转换成标准形式时，我们应该注意什么？需要注意两点：第一，当约束条件为“”或“”形式的不等式时，应使用非负松弛变量或“-”非负松弛变量；第二，当一个变量不满足非负约束时，该变量应该被一个或两个新的非负变量代替，以便标准形式的所有变量都满足非负要求。8.以下线性规划的一般形式如何转化为标准形式？最小Z=x1+2x2+3x3s.t. -2x1+ x2+ x3 9-3x1 + x2+ 2x3 43x1 - 2x2- 3x3=-6X1 0，x2 0，x3为任意值。回答：如果x1=-x1=-x1=-x1(新变量替换)，并且x10；设x3=x3 -x3”(用两个新变量代替)，x3，x3 0；松弛变量分别引入第一和第二不等式约束：x4，x5，和x4，X50；同时，第三个约束条件的两边都乘以(-1)，将右边的常量项“-6”转换为“6”。因此，上述线性规划的一般形式被转换成标准形式。最大Z=x1-2x 2-3(x3-x3)2x 1+x2+(x3-x3)+x4=93 x1+x2+2(x3-x3)-X5=43x 1+2x 2+3(x3-x3)=6x1，x2，x3，x3，x4，x50。9.线性规划需要什么基本概念？包括可行解、可行域、最优解、基、基向量、基变量、非基变量、基解、基本可行解、退化基本可行解、可行基、最优基等。概念之间有着密切的关系。10.什么是可行的解决方案？满足所有约束的解称为可行解。11.可行区域是什么？所有可行解的集合称为可行域。12.最佳解决方案是什么？获得最优目标函数值的可行解称为最优解。基础的定义是什么？该基是由系数矩阵a中线性独立的列向量组成的可逆方阵14.什么是基向量？用于形成基底的列向量称为基底向量。15.线性规划模型的基础是唯一的吗？通常不会。只要构成基的列向量不相同，基就不同。因此，通常可能有多个基数，但数量不应超过最大值。16.只有那些列向量顺序不同的基才被认为是同一个基吗？是的，只有那些列向量按不同顺序排列的基才被视为同一个基。17.基本变量是什么？线性规划模型的系数矩阵A中的每个列向量实际上是通过在所有约束中的列中排列每个变量的系数而形成的。当选择一个基时，与包含在该基中的系数矩阵的列向量相对应的变量被称为该基的基变量。18.什么是非基本变量？当选择一个基时，与包含在基中的系数矩阵的列向量相对应的变量被称为基的基变量，而剩余的变量被称为基的非基变量。19.基本解决方案是什么？在线性规划模型的标准形式下，当选择某个基时，对应于该基的非基变量值都被设置为0。此时，线性规划模型的标准形式的约束条件部分变成仅包含基本变量的线性方程组。求解线性方程组可以找出此时对应于基的基变量的值。通过这种方法获得的所有变量的值被称为对应于基的基解。一般来说，通过这种方法获得的所有基变量的值也通常称为基解。20.基本可行的解决方案是什么？选择某个基后，如果计算出该基的基解0，即每个基变量的值0，则该基解称为基本可行解。21.可行的基础是什么？如果对应于某个基的基本解是基本可行解，则该基称为可行基。22.降解的基本可行解决方案是什么？选择某个基后，如果计算出该基的基解0，即每个基变量的值0，则该基解称为基本可行解。如果这个基本可行解中的一个基本变量的值等于0，那么这个基本可行解就叫做退化基本可行解。23.退化的可行基础是什么？如果对应于某个基的基本解是退化的基本可行解，则该基称为退化可行基。24.什么是最佳基础？如果与某个基相对应的基解是基本可行解，并且是获得最优目标函数值的最优解，则该基被称为最优基。25.基础、基础变量和基础解之间的关系是什么？基础、基础变量和基础解之间存在一一对应关系。当确定基数时，确定对应于基数的基数变量和非基数变量，并且还确定它们在基数下的值，即基数解。因此，当谈论某个基变量或非基变量时，有必要指出哪个基变量或非基变量在下面。同样，当谈论某个基本解时，有必要指出哪个基本解在哪个基本下。26.什么公式可以用来找到基本解？可用于找到基解的公式是XB=B-1b-1B，其中B是所选基(矩阵)，B-1是所选基的逆矩阵，B是线性规划模型的资源向量，即，由模型约束条件的右常数项形成的列向量。该公式可以找到对应于所选基数的基数变量向量XB的值。27.在用于寻找基本解的公式XB=B-1b-1B中，基本变量向量XB中的分量的排列顺序必须与相应的基本B中的基本向量的排列顺序一致吗？必须一致。如果基B=(P1 P5 P2)，则基变量向量XB=(x1 x5 x2 )T28.基础解是否仅指基础变量(向量)XB的值？严格地说，基本解决方案是指所有的基本基本可行解只需要基本解XB=B-1B 0。如果某个基本解XB=B-1B 0，但XB=B-1B 0，即某个基本变量的值为0，则此时的基本解称为退化基本可行解。同时，对应于该基解的基被称为退化可行基。30.线性规划的几何意义是什么？线性规划的几何意义体现在以下几点。a)线性规划的可行域是凸多面体和凸集。b)线性规划的任何可行解对应于可行区域中的某一点。c)线性规划的基本可行解与可行域的顶点一一对应。d)如果线性规划的可行域是有界的，那么线性规划的可行域中的任何一个(点)都可以用顶点的凸组合来线性表示。e)如果线性规划有最优解，那么最优解必须在基本可行解上获得，即在可行区域的顶点(极点)上。31.图解法适用于哪种线性规划问题？图解法适用于只有两个变量的线性规划问题。32.用图解法解决线性规划问题的程序是什么？a)首先根据约束条件在已建立的坐标轴上画出线性规划问题的可行域；如果可行域不存在，则线性规划问题没有可行解，并且停止图解法，否则，过程进行到步骤B；b)当目标函数值z=cx=0时，绘制目标函数的等值线；c)判断目标函数等值线的移动方向，提高目标函数值；d)将目标函数的轮廓线沿着判断的改进方向平行移动到可行区域的边界，当可行区域中没有点在轮廓线上时，任何进一步的移动将停止。此时，与可行域相切的目标函数的轮廓线上的哪些点对应于线性规划问题的最优解，并转到步骤e；如果目标函数的等值线沿着判断的改进方向平移的过程是无止境的，这意味着线性规划问题的目标函数值是无界的，它没有最优解，并且图解法停止。e)观察或计算最优解。33.如何用图解法求解下列线性规划模型？最大Z=2x1+x2x1 3 3x1+x2 12 x1+x2 5 x1，x20回答：a)首先，根据约束条件在建立的坐标轴上画出线性规划问题的可行域，如下图阴影区域ABCD所示；b)当目标函数值z=2x1 x2=0时，绘制目标函数的等值线；c)已知目标函数值z是目标函数轮廓线的纵向截距，通过目标函数z=2x1 x2的等效变形得到x2=-2x1 z。在可行区域中，目标值Z最大，即目标函数的轮廓线的纵向截距最大。当目标函数的轮廓线从穿过原点的位置向右移动时(z=0，2x1 x2=0)，其相应的纵向截距从0开始增加。d)继续该过程，直到目标函数的轮廓线到达可行区域的顶点b。e)对应于点b的坐标(3，2)是线性规划问题的最优解。34.如何实现求最大值的线性规划问题和求最小值的线性规划问题之间的相互转化？一般来说，求最小值的线性规划问题的目标函数系数只需要取反，符号“min”转换为“MAX”就可以转换为求最大值的线性规划问题。相反，只需要将线性规划问题的目标函数的系数反过来，就可以找到最大值，并将符号“max”转换为“min”，就可以找到最小值。35.如何在线性规划问题的某个基B下找到测试向量？使用公式cbb-1a-c查找。其中a是系数矩阵，c是值向量，而cB是由基变量的目标函数系数形成的行向量。36.在线性规划的基b下寻找测试向量时，如何在公式cbb-1a-c中写入cB向量当线性规划模型的目标函数为最大值Z时，对于可行基b (b-1b 0)，如果测试向量cbb-1a-c 0，则对应于基b的基本可行解XB=b-1b，xn=0为最优解(基本最优解)，此时的基b称为最优基。当线性规划模型的目标函数为MIN Z时，对于可行基b (b-1b 0)，如果测试向量cbb-1a-c 0，则对应于基b的基本可行解XB=b-1b，xn=0为最优解(基本最优解)，此时的基b称为最优基。38.当线性规划问题的基础被确定时，如何找到变量xj的测试数sj？使用公式SJ=Cbb-1Pj-CJ来计算，其中Pj是对应于系数矩阵A中的变量xj的列向量。CJ是目标函数中的变量xj的系数。39.*最佳鉴别定理是如何推导出来的？本文只讨论已转化为标准形式的最大似然线性规划问题。设x为任何可行解，b为可行基(b-1b 0)，在此基下对应于基本解的目标函数值为，测试向量cbb-1a-c 0，然后将约束条件的左右两边同时相乘得到把这个公式加到F=cx上，你得到因为cbb-1a-c 0且x 0，也就是说，对应于任何可行解x的目标函数值f不超过对应于基B的基本解的目标函数值，因此，对应于基b=xB=B-1b、xN=0 xn=0的基本可行解XB是最优解(基本最优解)，此时基B被称为最优基。40.单纯形法的初始基础一定是单位矩阵吗？这还不确定。计算中初始基通常是单位矩阵有两个原因：一是单位矩阵的基确实存在；另一个是单位矩阵的逆矩阵是最简单最容易找到的。事实上，从任何基础开始计算单纯形法都是可能的。41.单纯形法的概念是什么？因为只要最优解存在，它就可以在基本可行的基础上获得。然而，有许多可行的基础，不可能用穷举法逐一验证它们以获得最佳的基础。因此，采用基替换迭代的方法，从易于计算其逆的初始基对应的单纯形表开始，逐步获得不同可行基对应的单纯形表，直到找到最优基对应的单纯形表。42.基础变更迭代过程的本质是什么？本质上，改变基的迭代过程是通过将对应于一个基的单纯形表转移到对应于另一个基的单