Question

运筹学中的线性规划的问题

运筹学线性规划中的凸集和基本可行解角顶可行解初始基变量和非基变量到底是什么啊，本人自学运筹学，基础不好，想请教大家，希望能够讲详细点。谢谢。。。

Answer 1

在线性规划中，因约束条件都是线性函数，所以其可行域为凸集。参考二维问题的图解法，其可行域是由几个线条围起来的区域，所以肯定是凸集。那么，求解最优解就在这个凸集里搜索。由目标函数等值线的移动来搜索解，则最优解肯定在其凸集的边缘达到最优值，而该凸集的边缘要么是线段要么是顶点，因此线性规划问题的最优解肯定是在可行域的顶点上。
其实这些顶点就是线性规划问题的基可行解。
那么怎么从模型中求出这些顶点（基可行解）呢？
求解模型的关键在于求解AX=b。
因A矩阵为m×n矩阵，无法得出上述约束条件方程的唯一解。必须在A矩阵中找出m×m的非奇异子矩阵B，即满足｜B｜不等于零（行列式不为零），从而可求得BX＝b的唯一解。此时对应于矩阵B的决策变量称为基变量，其余为非基变量。X中基变量取值为BX＝b的解，非基变量取值为零，则该X即为问题的基（可行）解，即对应于可行域的顶点的解。
这是按我的理解写的，希望能有所帮助。

Answer 2

先还是看一下高等代数相关的解线性方程组的知识

Answer 3

(1)线性规划中的凸集，是指它的可行域（所有可行解的集合）是一个凸集（在2元线性规划中为凸平面多边形），即设X1和X2为可行域中任意2个可行解，则X=1/2(X1+X2)仍为可行解，仍落在可行域内X1和X2；
（2）线性的基本可行解，是一组特殊的可行解：它将变量分为2类，1类为基本变量（变量个数为约束条件中独立方程个数），另1类为非基本变量（变量个数为决策变量个数与基本变量个数之差），令全体非基本变量取值为0，若基本变量对应唯一一组解且满足变量约束，则全体决策变量对应的这组解，称为该问题关于这个基本变量组的基本可行解；
（3)基本可行解，在几何上对应可行域的顶点，又称角顶可行解。
（4）求解线性规划问题时，求得的第一个基本可行解对应的基本变量组，称为初始基本变量组。