可行解, 基本解, 基本可行解和最优解的关系
W.L.X.
posted @ Fri, 19 Dec 2008 07:08:00 +0800
in 数学
, 16396 readers
一个考研的同学问的问题. 记得在初学线性规划时, 在这个问题上我也糊涂过. 下面是我的回答:
1. 可行解(feasible solution): 满足所有约束条件的决策变量x即是可行的解.
2. 基本解(corn-point solution): 请先读清华版运筹学的14, 15页. 约束条件总是可以写作一个线性方程组的样子Ax = b, 一般的A是n x m的矩阵(即n个约束条件, m个决策变量), 并且A的秩k < n(如果k=n会怎样呢?), 所以我们可以从A的m列中找出k个列向量组成一个n x k的满秩矩阵A'来. 方程组A'x = b的解被认为是一个基解(即书中所说的X_B). 书上10页的图1-2中的点(4, 3), Q1, Q2, Q3等都是, 从图上你可以看出它为什么叫做corn-point solution了吧.
3. 基可行解(corn-point feasible solution): 满足所有约束条件的基本解, 注意这时10页处图1-2中的点(4, 3)就被排除在外了.
4. 最优解(optimal solution): 使目标函数最大的可行解, 并且它必定是一个基可行解(线性规划的本质特点).
5. 如果就考试而言, 我想只要把15页的图1-6所示关系答明白就行了.
Thu, 29 Dec 2022 02:45:21 +0800
There are two types of solutions to a linear programming problem: the basic feasible solution and the optimal solution. The basic feasible solution is a solution that meets all the constraints of the problem, but may not be the best possible solution. The optimal solution is the best possible solution that meets all the constraints of the problem. There may be more than one optimal solution, but there can only be one basic feasible solution. The relationship between the basic feasible solution and the optimal solution is that the optimal solution is the best possible solution that meets all the constraints of the problem, while the basic feasible solution is a solution that meets all the constraints of engagement rings the problem, but may not be the best possible solution.