第1章 线性规划与单纯形法 第1节PPT讲稿.ppt

《第1章 线性规划与单纯形法 第1节PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第1章 线性规划与单纯形法 第1节PPT讲稿.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章线性规划与单纯形法第1节第1页，共33页，编辑于2022年，星期日定义：定义：运筹学运筹学是应用分析、试验、量化的方法，是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。最优方案，以实现最有效的管理。第2页，共33页，编辑于2022年，星期日内容内容Linear Programming 线性规划线性规划Nonlinear Programming 非线性规划非线性规划Integer Programming 整数规划整数规划Dynamic

2、Programming 动态规划动态规划 Inventory Theory 存储论存储论 Queuing 排队论排队论第3页，共33页，编辑于2022年，星期日Game Theory 对策论对策论/博弈论博弈论Network Analysis 网络分析网络分析Decision Analysis 决策分析决策分析Forecasting 预测预测Simulation 仿真仿真,etc第4页，共33页，编辑于2022年，星期日第一章第一章 线性规划与单纯形法线性规划与单纯形法第5页，共33页，编辑于2022年，星期日第1节 线性规划问题及其数学模型1.1 问题的提出 例例1 1 某工厂在计划期内要安

3、排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表资源 产品拥有量设 备1 2 8台时原材料 A 40 16 kg原材料 B04 12 kg第6页，共33页，编辑于2022年，星期日 该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多?解：设x1和x2分别表示计划生产产品I和II的数量，则有第7页，共33页，编辑于2022年，星期日线性规划的一般模型形式第8页，共33页，编辑于2022年，星期日1.2 图解法步骤：(1)建立平面直角坐标系(2)图示约束条件，确定可行域(3)图示目标函数，即一条直线(4)目标函数直线沿法线方向向

4、可行域边界平移，直至与可行域相切为止，从切点中确定最优点第9页，共33页，编辑于2022年，星期日第10页，共33页，编辑于2022年，星期日 目标值在(4,2)点，达到最大值14目标函数第11页，共33页，编辑于2022年，星期日可能出现的几种情况(1)无穷多最优解(多重最优解)目标函数 max z=2x1+4x2 第12页，共33页，编辑于2022年，星期日(2)无界解(3)无可行解第13页，共33页，编辑于2022年，星期日由图解法可以看出，对于LP问题(1)非空可行域是有界或无界凸多边形(2)若存在最优解，则一定在有界可行域的顶点取到(3)若两个顶点同时得到最优解，则连线上任一点都是最

5、优解第14页，共33页，编辑于2022年，星期日1.3 线性规划问题的标准形式第15页，共33页，编辑于2022年，星期日利用求和号写成第16页，共33页，编辑于2022年，星期日用向量表示为：第17页，共33页，编辑于2022年，星期日用矩阵表示为：第18页，共33页，编辑于2022年，星期日非标准型化标准型步骤：(1)决策变量x0,令x/=-x，则x/0(2)取值无约束的变量x=x/-x/,x/0,x/0(3)约束条件右端项(限额系数)bi0时，两 端同时乘以(-1)，不等号方向改变(4)约束条件为”不等式时，左端加上非 负松弛变量，不等式改为等式 约束条件为”不等式时，左端减去非 负剩余

6、变量，不等式改为等式(5)目标函数最小化min z，取z/=-z，则 max z/=min(-z)第19页，共33页，编辑于2022年，星期日例1的数学模型，加松驰变量后化为标准型：第20页，共33页，编辑于2022年，星期日例：将下列LP问题化为标准形式第21页，共33页，编辑于2022年，星期日1.4线性规划问题的解概念1.可行解2.基，基变量3.基本解，基可行解第22页，共33页，编辑于2022年，星期日1.可行解可行解定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解可行解称为最最优优解解。第23页，共33

7、页，编辑于2022年，星期日1.4线性规划问题的解概念2.基，基向量，基变量基，基向量，基变量,非基变量非基变量第24页，共33页，编辑于2022年，星期日1.4线性规划问题的解概念矩阵矩阵A中剩余的中剩余的n-m个列向量为个列向量为N，与之对，与之对应的变量应的变量XN称为非基变量。称为非基变量。第25页，共33页，编辑于2022年，星期日3 基可行解基可行解基本解：令非基变量都为基本解：令非基变量都为0，求解约束方程，求解约束方程的解对应于基的解对应于基B的一个基本解；的一个基本解；基可行解：若基可行解：若X为线性规划问题对应于基为线性规划问题对应于基B的基本解，若满足的基本解，若满足X0

8、，则称，则称X为该线性规为该线性规划问题的一个基可行解；划问题的一个基可行解；线性规划问题的基可行解对应于可行域的线性规划问题的基可行解对应于可行域的顶点。顶点。第26页，共33页，编辑于2022年，星期日1.4线性规划问题的解概念第27页，共33页，编辑于2022年，星期日1.4线性规划问题的解概念【例【例1】求线性规划】求线性规划所有基矩阵，基解，基本所有基矩阵，基解，基本 可行解及最优解可行解及最优解第28页，共33页，编辑于2022年，星期日1.4线性规划问题的解概念【解】约束方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵其中第其中第1列与第列与第3列构成的列构成的2阶矩阵不是

9、一个基，阶矩阵不是一个基，基矩阵只有基矩阵只有9个，即个，即第29页，共33页，编辑于2022年，星期日1.4线性规划问题的解概念 对对来来说说，x1,x2是是基基变变量量，x3,x4，x5是是非非基基变量，令变量，令x3=x4=x5=0，则约束条件式为：，则约束条件式为：x1、x2有唯一解有唯一解x12/5,x2=1则则 基本解为基本解为第30页，共33页，编辑于2022年，星期日对对B2来说，来说，x1,x4,为基变量，令非变量为基变量，令非变量x2,x3,x5为零，则约束条件变为：为零，则约束条件变为：得到得到 x1=-1/5，x4=4，基本解为基本解为第31页，共33页，编辑于2022年，星期日作业：求出剩下的基本解，基本可行解，最优解第32页，共33页，编辑于2022年，星期日1.4线性规划问题的解概念不同解之间的关系不同解之间的关系第33页，共33页，编辑于2022年，星期日