对于一般的线性规划问题,求解结果有哪几种情况?

发布网友发布时间：2022-04-23 09:20

共4个回答

热心网友时间：2023-06-27 10:59

可行解按字面意义就可以理解，可行的解。什么是可行？符合所有约束条件就可行，否则不可行。

基本解和基本可行解，这两个玩意可以认为是为了求解线性规划问题而发明的概念。线性规划不画图应该怎么求解呢？答案是按多元一次方程组来求。

我们知道线性规划都可以转化为标准型（具体转化方法就不赘述了），而标准型写成矩阵形式是下面这样的：

X是一个列向量，其元素的个数就是题目中未知变量的个数，假如有n个。

目标方程Z其实是各个未知变量按权（就是乘以价值系数）求和的结果。

AX=b是资源约束条件，假如有m个约束条件，那AX=b就有m个方程。为了求X中各未知量的值，我们只要能求解这个方程组就可以了。初中应该学过，多元一次方程组用高斯消去法，有唯一解的条件是未知量的个数刚好等于方程组的个数（n=m），可在线性规划问题中往往是n>m的。

这种情况怎么做呢？很简单，想办法让n=m，这就用到了基B的概念。一般运筹学教材的描述是“B是A的m×n阶非奇异子矩阵”。线性代数学得好的肯定已经明白了，没学好的呢？那就要看如果绕开“非奇异子矩阵”的概念，应该怎么理解。其实就是把A分成n个列向量，从中任意取出了m个，当然这m个列向量必须是线性无关的，就是说不能有哪一个可以用剩下的m-1个表示出来，要不相对于少取了一个。这m个列向量就是一个基B，也叫作基矩阵。从A中刨去B，剩下的n-m个列向量组成的矩阵就是非基N，或者叫非基矩阵。基B对应的变量 [公式] 叫作基变量，非基N对应的变量[公式]叫作非基变量。第一个约束条件也就写成了：

这时我们只要把 [公式] 中变量都设为0，上式就变成了： [公式] ，这是m个线性无关的m元一次方程组成的方程组，消元法就可以求出[公式]来。连带上[公式]，得出的 [公式] 就是上述约束条件的解，当然也是原约束条件AX=b的一个解，这个解就是一个基本解。

热心网友时间：2023-06-27 10:59

线性规划问题的最优解主要存在四种情况：

1）唯一最优解。判断条件：单纯形最终表中所有非基变量的检验数均小于零
2）多重最优解：判断条件：单纯形最终表中存在至少一个非基变量的检验数等
于零。
3）无界解。判断条件：单纯形法迭代中某一变量的检验数大于零，同时它所在
系数矩阵列中的所有元素均小于等于零
4）无可行解。判断条件：在辅助问题的最优解中，至少有一个人工变量大于零

请采纳，谢谢

热心网友时间：2023-06-27 11:00

热心网友时间：2023-06-27 11:01

线性规划

来源：《信息系统项目管理师教程（第3版）》第27章管理科学基础知识P875

线性规划是研究在有限的资源条件下，如何有效地使用这些资源达到预定目标的数学方法。用数学的语言来说，也就是在一组约束条件下寻找目标函数的极值问题。

求极大值（或极小值）的模型表达如下。

1.图解法

解线性规划问题的方法有很多，最常用的有图解法和单纯形法。图解法简单直观，有助于了解线性规划问题求解的基本原理，下面，通过一个例子来说明图解法的应用。

【例】某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原料的消耗，如表27-5所示。

该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应该如何安排计划使该工厂获利最多？

的点，必然落在由这三个半平面相交组成的区域内，如图27-13中的阴影部分所示。阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），因而此区域是本题的线性规划问题的解的集合，称它为可行域。图27-13图解法。

这说明该厂的最优生产计划方案是：生产4件产品Ⅰ，2件产品Ⅱ，可得最大利润为14元。

2.解的讨论

在上述例题中，得到的最优解是唯一的，但对一般线性规划问题而言，求解结果还可能出现以下几种情况：无穷多最优解（多重解），无界解（无最优解），无可行解。当求解结果出现后两种情况时，一般说明线性规划问题的数学模型有错误。无界解源于缺乏必要的约束条件，无可行解源于矛盾的约束条件。

从图解法中直观地看到，当线性规划问题的可行域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。

3.单纯形法

图解法虽然直观，但当变量数多于3个以上时，它就*为力了，这时需要使用单纯形法。

单纯形法的基本思路是：根据问题的标准，从可行域中某个可行解（一个顶点）开始，转换到另一个可行解（顶点）。并且使目标函数达到最大值时，问题就得到了最优解。限于篇幅，本书不再介绍单纯形法的详细求解过程。

4.线性规划的适用性

线性规划模型用在原材料单一、生产过程稳定不变、分解型生产类型的组织是十分有效的，例如，石油化工厂等。对于产品结构简单、工艺路线短，或者零件加工组织，有较大的应用价值。需要注意的是，对于机电类组织用线性规划模型只适用于作年度的总生产计划，而不用来做月度计划。这主要与工件在设备上的排序有关，计划期太短，很难安排过来。

一般来说，一个经济管理问题满足以下条件时，才能建立线性规划的模型。

(1)要求解问题的目标函数能用数值指标来反映，且为线性函数。

(2)存在着多种方案。

(3)要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式描述。