《第1章 线性规划与单纯形法 第1节精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章 线性规划与单纯形法 第1节精选文档.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章线性规划与单纯形法第1节本讲稿第一页，共三十三页定义：定义：运筹学运筹学是应用分析、试验、量化的方法，是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。方案，以实现最有效的管理。本讲稿第二页，共三十三页内容内容Linear Programming 线性规划线性规划Nonlinear Programming 非线性规划非线性规划Integer Programming 整数规划整数规划Dynamic Programming 动态规划动态
2、规划 Inventory Theory 存储论存储论 Queuing 排队论排队论本讲稿第三页，共三十三页Game Theory 对策论对策论/博弈论博弈论Network Analysis 网络分析网络分析Decision Analysis 决策分析决策分析Forecasting 预测预测Simulation 仿真仿真,etc本讲稿第四页，共三十三页第一章第一章 线性规划与单纯形法线性规划与单纯形法本讲稿第五页，共三十三页第1节 线性规划问题及其数学模型1.1 问题的提出 例例1 1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表资源 产品拥
3、有量设 备1 2 8台时原材料 A 40 16 kg原材料 B04 12 kg本讲稿第六页，共三十三页 该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多?解：设x1和x2分别表示计划生产产品I和II的数量，则有本讲稿第七页，共三十三页线性规划的一般模型形式本讲稿第八页，共三十三页1.2 图解法步骤：(1)建立平面直角坐标系(2)图示约束条件，确定可行域(3)图示目标函数，即一条直线(4)目标函数直线沿法线方向向可行域边界平移，直至与可行域相切为止，从切点中确定最优点本讲稿第九页，共三十三页本讲稿第十页，共三十三页 目标值在(4,2)点，达到最大值14目
4、标函数本讲稿第十一页，共三十三页可能出现的几种情况(1)无穷多最优解(多重最优解)目标函数 max z=2x1+4x2 本讲稿第十二页，共三十三页(2)无界解(3)无可行解本讲稿第十三页，共三十三页由图解法可以看出，对于LP问题(1)非空可行域是有界或无界凸多边形(2)若存在最优解，则一定在有界可行域的顶点取到(3)若两个顶点同时得到最优解，则连线上任一点都是最优解本讲稿第十四页，共三十三页1.3 线性规划问题的标准形式本讲稿第十五页，共三十三页利用求和号写成本讲稿第十六页，共三十三页用向量表示为：本讲稿第十七页，共三十三页用矩阵表示为：本讲稿第十八页，共三十三页非标准型化标准型步骤：(1)决
5、策变量x0,令x/=-x，则x/0(2)取值无约束的变量x=x/-x/,x/0,x/0(3)约束条件右端项(限额系数)bi0时，两 端同时乘以(-1)，不等号方向改变(4)约束条件为”不等式时，左端加上非 负松弛变量，不等式改为等式 约束条件为”不等式时，左端减去非 负剩余变量，不等式改为等式(5)目标函数最小化min z，取z/=-z，则 max z/=min(-z)本讲稿第十九页，共三十三页例1的数学模型，加松驰变量后化为标准型：本讲稿第二十页，共三十三页例：将下列LP问题化为标准形式本讲稿第二十一页，共三十三页1.4线性规划问题的解概念1.可行解2.基，基变量3.基本解，基可行解本讲稿第
6、二十二页，共三十三页1.可行解可行解定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解可行解称为最最优优解解。本讲稿第二十三页，共三十三页1.4线性规划问题的解概念2.基，基向量，基变量基，基向量，基变量,非基变量非基变量本讲稿第二十四页，共三十三页1.4线性规划问题的解概念矩阵矩阵A中剩余的中剩余的n-m个列向量为个列向量为N，与之对，与之对应的变量应的变量XN称为非基变量。称为非基变量。本讲稿第二十五页，共三十三页3 基可行解基可行解基本解：令非基变量都为基本解：令非基变量都为0，求解约束方程，求解约束方程的解
7、对应于基的解对应于基B的一个基本解；的一个基本解；基可行解：若基可行解：若X为线性规划问题对应于基为线性规划问题对应于基B的基本解，若满足的基本解，若满足X0，则称，则称X为该线性规为该线性规划问题的一个基可行解；划问题的一个基可行解；线性规划问题的基可行解对应于可行域的顶线性规划问题的基可行解对应于可行域的顶点。点。本讲稿第二十六页，共三十三页1.4线性规划问题的解概念本讲稿第二十七页，共三十三页1.4线性规划问题的解概念【例【例1】求线性规划】求线性规划所有基矩阵，基解，基本所有基矩阵，基解，基本 可行解及最优解可行解及最优解本讲稿第二十八页，共三十三页1.4线性规划问题的解概念【解】约束
8、方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵其中第其中第1列与第列与第3列构成的列构成的2阶矩阵不是一个基，基阶矩阵不是一个基，基矩阵只有矩阵只有9个，即个，即本讲稿第二十九页，共三十三页1.4线性规划问题的解概念 对对来来说说，x1,x2是是基基变变量量，x3,x4，x5是是非非基基变量，令变量，令x3=x4=x5=0，则约束条件式为：，则约束条件式为：x1、x2有唯一解有唯一解x12/5,x2=1则则 基本解为基本解为本讲稿第三十页，共三十三页对对B2来说，来说，x1,x4,为基变量，令非变量为基变量，令非变量x2,x3,x5为零，则约束条件变为：为零，则约束条件变为：得到得到 x1=-1/5，x4=4，基本解为基本解为本讲稿第三十一页，共三十三页作业：求出剩下的基本解，基本可行解，最优解本讲稿第三十二页，共三十三页1.4线性规划问题的解概念不同解之间的关系不同解之间的关系本讲稿第三十三页，共三十三页