什么是线性规划
运筹学是软考中级系统集成项目管理工程师上午综合知识里的高频考点，也是很多人最头疼的知识点。尤其是线性规划，看起来复杂，其实掌握方法就不难。
线性规划是研究在一组约束条件下，怎么使目标函数达到最优的问题。比如你有一定的人力、物力、财力，怎么安排生产，使利润最大或者成本最小。
线性规划的标准形式是：目标函数是求最大值或最小值，约束条件都是不等式或等式，变量都是非负的。
举个最简单的例子：你生产A和B两种产品，A产品每件利润20元，B产品每件利润30元。生产A产品需要2小时人工和1小时机器，生产B产品需要1小时人工和3小时机器。你一共有10小时人工和15小时机器。怎么安排生产，使利润最大？
这就是一个典型的线性规划问题。目标函数是max 20x+30y，约束条件是2x+y≤10，x+3y≤15，x≥0，y≥0。
软考高项运筹学线性规划解法
图解法解线性规划
最简单的线性规划问题，可以用图解法来解。图解法就是把约束条件画在坐标系里，找到可行域，然后看目标函数在哪个顶点达到最优。
继续上面的例子：约束条件2x+y≤10，画出来是一条直线，直线下方是可行域。约束条件x+3y≤15，也是一条直线，直线下方是可行域。两个可行域的交集就是总的可行域，是一个凸多边形。
线性规划的最优解一定在可行域的顶点上。所以你只要把所有顶点找出来，代入目标函数，看哪个顶点的目标函数值最大就行。
上面的例子，可行域的顶点有：(0,0)，(5,0)，(3,4)，(0,5)。代入目标函数：(0,0)的利润是0，(5,0)的利润是100，(3,4)的利润是180，(0,5)的利润是150。所以最优解是x=3，y=4，最大利润是180元。
图解法容易错的点是：很多人把可行域的顶点找错了。记住：可行域是约束条件交集的凸多边形，顶点就是两条约束直线的交点。你把所有交点找出来，代入目标函数，就能找到最优解。
单纯形法解线性规划
变量超过两个的时候，图解法就不好用了，要用单纯形法。单纯形法是线性规划的通用解法，不管多少个变量都能解。
单纯形法的思路是：先找到一个初始可行解，然后看这个解是不是最优的。如果不是，就换到另一个顶点，看是不是更优。一直换到最优解为止。
单纯形法的步骤是：第一步，把线性规划问题化成标准形式，引入松弛变量，把不等式约束变成等式约束。第二步，建立初始单纯形表。第三步，看检验数，如果所有检验数都小于等于0（求最大值的情况），就是最优解。如果有检验数大于0，就换基迭代。第四步，重复第三步，直到找到最优解。
单纯形法看起来复杂，其实就是按步骤算。考试的时候不会考太复杂的单纯形法，一般考两个变量的图解法，或者考三个变量的简单单纯形法。
单纯形法容易错的点是：很多人换基迭代的时候算错了。记住：换基迭代的规则是，找检验数最大的那个变量进基，找比值最小的那一行出基。然后用高斯消元法把矩阵化成单位矩阵。
常见错题总结
线性规划的错题主要集中在几个地方：
第一，目标函数搞反了。求最大值还是求最小值，很多人搞混了。记住：求最大值的检验数要小于等于0才最优，求最小值的检验数要大于等于0才最优。
第二，可行域找错了。约束条件是大于还是小于，很多人搞混了。记住：不等式约束的方向，直接决定了可行域在哪一侧。
第三，顶点找错了。可行域的顶点是两条约束直线的交点，很多人漏了顶点，或者多算了顶点。
第四，单纯形法换基迭代算错了。进基变量找错了，或者出基变量找错了，或者高斯消元算错了。
怎么避免这些错误？我给你一个口诀：图解法找顶点，单纯形法看检验数。
两个变量的问题用图解法，把约束条件画出来，找可行域的顶点，代入目标函数，找最优解。三个变量以上的问题用单纯形法，按步骤算，看检验数，换基迭代，直到最优。
问题解答
问题1：线性规划是什么？
回答1：线性规划是研究在一组约束条件下，怎么使目标函数达到最优的问题。目标函数是求最大值或最小值，约束条件都是不等式或等式。
问题2：图解法的步骤是什么？
回答2：把约束条件画在坐标系里，找到可行域，然后找可行域的顶点，代入目标函数，看哪个顶点的目标函数值最优。
问题3：单纯形法的思路是什么？
回答3：先找到一个初始可行解，然后看这个解是不是最优的。如果不是，就换到另一个顶点，看是不是更优。一直换到最优解为止。
问题4：线性规划的最优解在哪里？
回答4：一定在可行域的顶点上。
问题5：考试的时候怎么快速解题？
回答5：两个变量的问题用图解法，三个变量以上的问题用单纯形法。记住图解法找顶点、单纯形法看检验数的口诀，考试就不会错。
---
线性规划是软考中级系统集成项目管理工程师上午综合知识的高频考点。核心是：两个变量用图解法，三个变量以上用单纯形法。记住图解法找顶点、单纯形法看检验数的口诀，考试就不会错。
