北邮《运筹学》课件 第2章 线性规划.pptx

1;;SaulI.Gass,(2002)TheFirstLinear-ProgrammingShoppe.OperationsResearch50(1):61-68./10.1287/

opre.7781;我每天要求一定量的两种维生素，Vc和Vb。

假设这些维生素可以分别从牛奶和鸡蛋中得到。;令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写

成如下的数学形式：;2.1线性规划模型;;线性规划模型;线性规划模型;;;线性规划模型-标准型;标准型;;;16;17;18;19;;21;22;2.3线性规划的基本概念和基本性质;线性规划的基本概念;;线性规划的基本概念;max z=x1+3x2

s.t. x1+x2+x3 =6

-x1+2x2+x4 =8

x1,x2,x3,x4≥0;几何概念;;;;;线性规划的基本概念;线性规划的基本性质;;;;;线性规划的基本定理;2.4求解线性规划问题的单纯形方法;四个假设;单纯形方法;单纯形方法;;单纯形法;;;;49;50;51;52;53;54;55;56;57;;59;60;61;62;63;64;65;66;67;68;69;;;练习;为找到初始可行基，对有等式约束的(LP)问题，

通过引入人工变量，化为辅助问题：

其中M为足够大的正数。

如果得到（*）的最优解对应的人工变量，则两个规划最优值（有限值）相等，且（*）的最优解去掉人工变量就是对应原问题的最优解。

否则，原问题没有可行解。;标准化，引入松弛变量和剩余变量;再引入“人工变量”，构造初始表：;

单纯型算法的进一步讨论

——人工变量法（大M法）例

;

单纯型算法的进一步讨论

——人工变量法（大M法）例

;单纯型算法的进一步讨论

——关于解的判别;单纯型算法的进一步讨论

——关于解的判别;

无穷多最优解;有无界解;解的判别;完整的单纯形算法（大M法）步骤框图;两阶段法;;;写成标准化形式;第1

阶段;;;1/400-21/8-21/8;;;练习;单纯形法总结;2.6退化情形;其单纯形法迭代过程如下：;;;;;2.7用软件求解线性规划;;作业题P253-255