资源描述：
《线性规划及对偶问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第1章 线性规划及对偶问题课时：8学时主讲：关文忠教学要求与主要内容：教学要求：通过本章的学习，了解线性规划及其对偶问题的基本理论；掌握线性规划求解的基本方法——单纯形法,了解对偶单纯形方法，熟悉灵敏度分析的方法；会建构线性规划模型，并会用“规划求解”模板进行求解。主要内容：1.1线性规划模型1.2线性规划求解基本方法1.2.1图解法1.2.2单纯形法简介1.3线性规划对偶问题1.4线性规划应用举例本章小结1.1线性规划(LinearProgramming)模型1.1.1问题的提出产品甲产品乙生产能力(小时)设备A73210设备B45200设备C24180计划利润(元/件)7065设
2、：产品甲生产x1，产品乙生产x2目标：Maxz=70x1+65x2约束条件：设备A生产能力限制：7x1+3x2≤210设备B生产能力限制：4x1+5x2≤200设备C生产能力限制：2x1+4x2≤180产量非负限制：x1，x2≥0决策变量决策变量目标函数约束条件三要素：1.决策变量2.目标函数3.约束条件1.1.2线性规划模型1.适用条件：（1）优化条件:问题目标最大化、最小化的要求；（2）约束条件:问题目标受一系列条件的限制；（3）选择条件:实现目标存在多种备选方案；（4）非负条件的选择:根据问题的实际意义决定是否非负。2.构建线性规划模型的步骤（1）科学选择决策变量（2）根据实际
3、问题的背景材料，找出所有的约束条件（3）明确目标要求（4）确定是否增加决策变量的非负条件例2Minz=2x1+6x2+5x3+4x4+3x50.50x1+2.00x2+3.00x3+1.50x4+0.80x5≥850.10x1+0.06x2+0.04x3+0.15x4+0.20x5≥50.08x1+0.70x2+0.35x3+0.25x4+0.02x5≥18x1~x5≥0饲料营养甲(克/公斤)营养乙(克/公斤)营养丙(克/公斤)成本(元/公斤)10．500．100．08222．000．060．70633．000．040．35541．500．150．25450．800．200．023需
4、要85克5克18克设X1X2X3X4x5由决策变量、目标函数和约束条件构成的问题称为规划问题，如果决策变量为可控连续变量，目标函数和约束条件则是决策变量的线性函数，则称为线性规划问题。（P12例1.3）3.线性规划模型表示形式——决策变量；——目标函数系数、价值系数或费用系数；——右端项或资源常数；——称为约束系数或技术系数。（1）一般形式：（2）集合形式：（3）向量形式：（4）矩阵形式：【例3】将线性规划模型一般表达式化为矩阵形式。解:设:1.1.3线性规划标准形式线性规划标准模型的一般表达式：非标准形式标准化方法：1.目标函数2.约束条件为不等式:引进松驰变量xs:引进剩余变量x
5、s:4.决策变量为自由变量:5.约束右端项为负:两端乘-1:≥03.约束条件为不等式:【例4】将线性规划模型转化为标准式解:无约束(4)在第一、第三约束左端加上松弛变量x4,x6≥0，在第二约束左端减去剩余变量x5≥0作业：P75~76习题1、2，P78:8(1)9(2)建模1.2线性规划基本解法几个基本概念:可行解：凡满足约束条件的决策变量的取值称为线性规划的可行解。可行域：所有可行解的集合称为线性规划的可行域。最优解：使目标函数达到最优值的可行解称为线性规划的最优解1.2.1图解法(graphicalmethod)步骤:(1)平面上画出直角坐标;(2)图示约束条件,标出满足所有约
6、束条件的公共区域(可行域);(3)图示目标函数的一根基线(母线)按目标值要求,让基线平行移动,直到与可行域相切为止,切点即为最优解;(4)求出切点坐标值,代入目标函数求得目标函数最优值.可行域【例1.6】运用图解法求解线性规划问题(5,0)2x1+x2=10x1+x2=8(2,6)x110830258x2(0,8)3x1+2x2=6四种结局:x1x2唯一最优解x2x1无穷多最优解x1x2无界解x2x1无可行解1.2.2单纯形法简介最优解一定在可行域的顶点上,将顶点坐标代入目标函数有:(0,0):z=3×0+2×0=0(5,0):z=3×5+2×0=15(0,8):z=3×0+2×8=
7、16(2,6):z=3×2+2×6=18单纯形法的基本思路就是基本可行解的转移，先找到一个初始基本可行解，如果不是最优解，设法转移到另一个基本可行解，并使目标函数值不断增加，直到找到最优解。(5,0)(2,6)10830258x2(0,8)x11.解的概念标准化NB标准化定义:A为m×n阶矩阵,若A的秩为m,B为A中的任意m×m阶子矩阵,且行列式
8、B
9、≠0,则称B为线性规划的一个基；对应的XB为基变量；XN为非基变量；称为基本解满足非负约束的基本解为基本可
