求解一般线性规划问题策略 >寻找初始基本可行解 >给出基本可行解为最优解的判别准则 给出从目前基本可行解转移到新基本 可行解的方法
Page:11 QSC 华东理工大学 工商经济学院 生产与运作管理 求解一般线性规划问题策略 ➢寻找初始基本可行解 ➢给出基本可行解为最优解的判别准则 ➢给出从目前基本可行解转移到新基本 可行解的方法
求解流程 确定初始 基本可行解 最优解?是 给出最优解 否 转移到新 的基本可行解
Page:12 QSC 华东理工大学 工商经济学院 生产与运作管理 求解流程 确定初始 基本可行解 最优解？ 否 转移到新 的基本可行解 给出最优解 是
基的定义 定义线性规划的基( Basis 对于线性规划的约束条件 AX=b X>0 设B是A矩阵中的一个非奇异的m×m子矩 阵,则称B为线性规划的一个基
Page:13 QSC 华东理工大学 工商经济学院 生产与运作管理 基的定义 定义 线性规划的基(Basis) 对于线性规划的约束条件 AX=b X≥0 设B是A矩阵中的一个非奇异的m×m子矩 阵，则称B为线性规划的一个基
约束方程AX=b的分块矩阵表示 设B是线性规划的一个基,则A可以表示为 A=B,NI X X也可相应地分成 其中Xp为m×1向量,称为基变量 X为(n-m)×1向量,称为非基变量 AX=b可表示为[B 或 BXa+NX、=b
Page:14 QSC 华东理工大学 工商经济学院 生产与运作管理 设B是线性规划的一个基，则A可以表示为 A=[ B, N ] X X X = B N X也可相应地分成 其中 XB为m×1向量，称为基变量 XN为(n-m)×1向量，称为非基变量 约束方程 AX=b 的分块矩阵表示 B N X X , . b B N AX=b可表示为 = 或 BXB+NXN =b
若X取确定的值,则X有唯一的值与之对 应 XB=B-b-B-INXN 特别,取X=0,这时有XB=B1b
Page:15 QSC 华东理工大学 工商经济学院 生产与运作管理 若XN取确定的值，则XB有唯一的值与之对 应 XB=B-1b-B-1NXN 特别，取XN=0，这时有XB=B-1b