第1章线性规划线性规划问题提出可行区域与基本可行解单纯形算法单纯形法进一步讨论1.1线性规划问题
提出线性规划例题生产计划问题线性规划模型一般形式规范形式标准形式形式转换
概念图解法某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划问题分
析模型注释向量形式矩阵形式变一般形式为标准形式约束转换实例不
等式变等式几个概念图解法例解线性规划注释解可能
出现的情况：可行域是空集可行域无界无最优解最优解存在且唯一，则一定在顶点上达到最优解存在且不唯一，一定存在顶点是最
优解1.2可行区域与基本可行解?可行域的几何结构?基本可行解与基本定理可行域的几何结构基本假设凸集可行
域的凸性基本假设凸集与顶点基本可行解与基本定理定义基本定理问题
1.3单纯形算法算法的三个阶段算法步骤单纯形表算例算法步骤单纯形法进一步讨论两
阶段法大M法退化说明两阶段法大M法基本定理阶段1：确定初始基可行解假设
问题引入松弛变量得则，可设则，约束变为则，初始基可行解为则阶段2：由一个基可行解到另一个设初始基可行解又
设前m个坐标非0，即因为是基可行解，所以若我们总假定有方法使基矩阵是单位矩阵，则上式展开为因为是基，所以，其余向量可由它
线性表示对上式乘以正数上式与相加得从中可找到另一个满足约束的点要使它成为基可行解，需要满足，且至少有一个取等号。又因
为，若aij<0，则条件自然满足，所以，只需取即可。阶段3：最优性检验和解的判别把基可行解分别代入目标令（1）当所
有的说明：现有顶点的目标函数值比相邻各顶点的目标函数值都大，现有顶点对应的基可行解即为唯一最优解。（2）当所有的又对某个非
基变量有则，无穷多最优解。（3）若存在某个又无界解。的所有分量单纯形表例子例：解：-2010zjc
j－1/502/518/5x110-3/51[14/5]021/5x30-25/14-5/14
00zjcj－2/7-1/7011x110-3/145/14103/2x2500510
zjcj－102[5]8x4001439x30x4x3x2x1bxBcB00
510cj单纯形法的矩阵描述考虑问题引入松弛变量得设B是一个可行基，若则对应于B的变量向量则同时将C也分成两块
所以,有所以，LP问题写成将（2）移项后得将（3）左乘将（4）代入目标（1）得为什么要做进一步讨论第一阶段：不考虑原
问题是否存在基可行解，给原问题加入人工变量，并构造只含人工变量的目标函数w，并要求实现最小化。若求解得w=0，说明原问题存在基可行
解，可进入第二阶段，否，原问题无可行解，停。第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换成原问题的目
标函数系数，作为第二阶段的初始表。第页第页运筹帷幄之中决胜千里之外线性规
划LinearProgramming运筹学课件1.1.1线性规划例题453单位产品的利润（
千元）2000523原料P3800420原料P21500032原料P1原料可用量（公斤/日）产
品Q3产品Q2产品Q1单位产品所需原料数量（公斤）生产计划问题1.1.2线性规划模型一般形式标准形式目标转换变量转换松弛变量剩余变量例:基本解不一定是可行解 |
|
