文档介绍：四、单纯形法的一般描述:
  1、初始可行解的确定
(1)初始可行基的确定
观察法——观察系数矩阵中是否含有现成的单位阵?
 LP限制条件中全部是“≤”类型的约束——将新增的松弛变量作为初始基变量,对应的系数列向量构成单位阵;
先将约束条件标准化,再引入非负的人工变量, 以人工变量作为初始基变量,其对应的系数列向量构成单位阵,称为“人造基”;
然后用大M法或两阶段法求解;
线性规划限制条件都是“≥”或“=”类型的约束——
等式约束左端引入人工变量的目的
使约束方程的系数矩阵中出现一个单位阵,用单位阵的每一个列向量对应的决策变量作为“基变量”,这样,出现在单纯形表格中的B(i)列(即约束方程的右边常数)值正好就是基变量的取值。
(注意:用非基变量表示基变量的表达式)
①如果限制条件中既有“≤”类型的约束,又有“≥”或“=”类型的约束,怎麽办?
构造“不完全的人造基”!
讨论
②为什麽初始可行基一定要选单位阵?
b列正好就是基变量的取值,检验数行
和b列交叉处元素也正好对应目标函数值,
因此称b列为解答列
(2)写出初始基本可行解——
根据“用非基变量表示基变量的表达式”,非基变量取0,算出基变量,搭配在一起构成初始基本可行解。
2、建立判别准则:
(1)两个基本表达式的一般形式
就LP限制条件中全部是“≤”类型约束,新增的松弛变量作为初始基变量的情况来描述:
此时LP的标准型为
初始可行基:
初始基本可行解:
一般(经过若干次迭代),对于基B,
用非基变量表出基变量的表达式为:
用非基变量表示目标函数的表达式:
若是对应于基B的基本可行解, 是非基变量的检验数,若对于一切非基变量的角指标j,均有≤0,则X(0)为最优解。
(2)最优性判别定理
(3)无“有限最优解”的判别定理
若为一基本可行解,有一非基变量xk,其检验数, 而对于i=1,2,…,m,均有,则该线性规划问题没有“有限最优解”。