基本解与基本可行解的定义 定义线性规划的解 Bb X 称为线性规划与基B对应的基本解 若其中B1b≥0,则称以上的基本解为一基本可行 解,相应的基B称为可行基
Page:16 QSC 华东理工大学 工商经济学院 生产与运作管理 定义 线性规划的解 称为线性规划与基B对应的基本解。 若其中B-1b0，则称以上的基本解为一基本可行 解，相应的基B称为可行基。 X X X B b 0 = = − B N 1 基本解与基本可行解的定义
定理线性规划的基本可行解就是可行 域的极点
Page:17 QSC 华东理工大学 工商经济学院 生产与运作管理 定理 线性规划的基本可行解就是可行 域的极点
单纯形原理的矩阵描述 设标准的线性规划问题为 min F CX s t AX=b X≥0 矩阵A可以分块记为A=B,N 相应地,向量X和C可以记为X BN C
Page:18 QSC 华东理工大学 工商经济学院 生产与运作管理 单纯形原理的矩阵描述 设标准的线性规划问题为 min z= CTX s.t. AX=b X0 矩阵A可以分块记为A=[B，N] 相应地，向量X和C可以记为 X X X C C C = = B N B N
AX=b可以写成 BX +NX=b XB=B-b-B- NXN 对于一个确定的基B,目标函数z可以写成 Z=C X=CT CT1/X B=CRXB+ CNAn T 目标函数z用非基变量表出的形式 z=CB(B b-B NXN)+CNXN CBB b-CBBN-CNXN
Page:19 QSC 华东理工大学 工商经济学院 生产与运作管理 AX=b可以写成 BXB+NXN =b 即 XB =B-1b-B-1NXN 对于一个确定的基B，目标函数z可以写成 z T B T N T B N B T B N T = = N C X C C = + X X , . C X C X 目标函数z用非基变量表出的形式 z B T N N T N B T B T N T N = − + = − − − − − − C B b B NX C X C B b C B N C X ( ) ( ) 1 1 1 1
单纯形表的结构 B B B AB B-IN B-b 检验数0c、CBN
Page:20 QSC 华东理工大学 工商经济学院 生产与运作管理 单纯形表的结构 CB CN XB XN CB XB I B - 1N B - 1b 检验数 0 CN-CBB - 1N