第1章 线性规划及对偶问题

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,1,章 线性规划及对偶问题,课时：,8,学时,主讲：关文忠,教学要求与主要内容,：,教学要求：,通过本章的学习，了解线性规划及其对偶问题的基本理论；掌握线性规划求解的基本方法,单纯形法,了解对偶单纯形方法，熟悉灵敏度分析的方法；会建构线性规划模型，并会用“规划求解”模板进行求解。,主要内容：,1.1,线性规划模型,1.2,线性规划求解基本方法,1.2.1,图解法,1.2.2,单纯形法简介,1.3,线性规划对偶问题,1.4,线性规划应用举例,本章小结,1.1,线性规划,(Linear Programming),模型,1.1.1,问题的提出,产品甲,产品乙,生产能力,(,小时,),设备,A,7,3,210,设备,B,4,5,200,设备,C,2,4,180,计划利润,(,元,/,件,),70,65,设：产品甲生产,x,1,，产品乙生产,x,2,目标：,Max z=70 x,1,+65x,2,约束条件：,设备,A,生产能力限制：,7x,1,+3x,2,210,设备,B,生产能力限制：,4x,1,+5x,2,200,设备,C,生产能力限制：,2x,1,+4x,2,180,产量非负限制：,x,1,，,x,2,0,决策变量,决策变量,目标函数,约束条件,三要素：,1.,决策变量,2.,目标函数,3.,约束条件,1.1.2,线性规划模型,1.,适用条件：,（,1,）优化条件,:,问题目标最大化、最小化的要求；,（,2,）约束条件,:,问题目标受一系列条件的限制；,（,3,）选择条件,:,实现目标存在多种备选方案；,（,4,）非负条件的选择,:,根据问题的实际意义决定是否非负。,2.,构建线性规划模型的步骤,（,1,）科学选择决策变量,（,2,）根据实际问题的背景材料，找出所有的约束条件,（,3,）明确目标要求,（,4,）确定是否增加决策变量的非负条件,例,2,Min z=2x,1,+6x,2,+5x,3,+4x,4,+3x,5,0.50 x,1,+2.00 x,2,+3.00 x,3,+1.50 x,4,+0.80 x,5,85,0.10 x,1,+0.06x,2,+0.04x,3,+0.15x,4,+0.20 x,5,5,0.08x,1,+0.70 x,2,+0.35x,3,+0.25x,4,+0.02x,5,18,x,1,x,5,0,饲料,营养甲,(,克,/,公斤,),营养乙,(,克,/,公斤,),营养丙,(,克,/,公斤,),成本,(,元,/,公斤,),1,0,50,0,10,0,08,2,2,2,00,0,06,0,70,6,3,3,00,0,04,0,35,5,4,1,50,0,15,0,25,4,5,0,80,0,20,0,02,3,需要,85,克,5,克,18,克,设,X,1,X,2,X,3,X,4,x,5,由决策变量、目标函数和约束条件构成的问题称为规划问题，如果决策变量为可控连续变量，目标函数和约束条件则是决策变量的线性函数，则称为线性规划问题。（,P12,例,1.3,）,3.,线性规划模型表示形式,决策变量；,目标函数系数、价值系数或费用系数；,右端项或资源常数；,称为约束系数或技术系数。,（,1,）一般形式：,（,2,）集合形式：,（,3,）向量形式：,（,4,）矩阵形式：,【,例,3,】,将线性规划模型一般表达式化为,矩阵形式。,解,:,设,:,1.1.3,线性规划标准形式,线性规划标准模型的一般表达式,：,非标准形式标准化方法,：,1.,目标函数,2.,约束条件为不等式,:,引进松驰变量,x,s,:,引进剩余变量,x,s,:,4.,决策变量为自由变量,:,5.,约束右端项为负,:,两端乘,-1:,0,3.,约束条件为不等式,:,【,例,4,】,将线性规划模型转化为标准式,解,:,无约束,(4),在第一、第三约束左端加上松弛变量,x,4,x,6,0,，在第二约束左端减去剩余变量,x,5,0,作业：,P7576,习题,1,、,2,，,P78:8(1)9(2),建模,1.2,线性规划基本解法,几个基本概念,:,可行解：凡满足约束条件的决策变量的取值称为线性规划的可行解。,可行域,：所有可行解的集合称为线性规划的可行域。,最优解,：使目标函数达到最优值的可行解称为线性规划的最优解,1.2.1,图解法,(graphical method),步骤,:,(1),平面上画出直角坐标,;,(2),图示约束条件,标出满足所有约束条件的公共区域,(,可行域,);,(3),图示目标函数的一根基线,(,母线,),按目标值要求,让基线平行移动,直到与可行域相切为止,切点即为最优解,;,(4),求出切点坐标值,代入目标函数求得目标函数最优值,.,可行域,【,例,1.6,】,运用图解法求解线性规划问题,(5,0),2x,1,+x,2,=10,x,1,+x,2,=8,(2,6),x,1,10,8,3,0,2 5 8,x,2,(0,8),3x,1,+2x,2,=6,四种结局,:,x,1,x,2,唯一最优解,x,2,x,1,无穷多最优解,x,1,x,2,无界解,x,2,x,1,无可行解,1.2.2,单纯形法简介,最优解一定在可行域的顶点上,将顶点坐标代入目标函数有,:,(0,0):z=30+20=0,(5,0):z=35+20=15,(0,8):z=30+28=16,(2,6):z=32+26=18,单纯形法的基本思路就是基本可行解的转移，先找到一个初始基本可行解，如果不是最优解，设法转移到另一个基本可行解，并使目标函数值不断增加，直到找到最优解,。,(5,0),(2,6),10,8,3,0,2 5 8,x,2,(0,8),x,1,1.,解的概念,标准化,N,B,标准化,定义,:,A,为,mn,阶矩阵,若,A,的秩为,m,B,为,A,中的任意,mm,阶子矩阵,且行列式,|B|0,则称,B,为线性规划的一个,基,；,对应的,X,B,为,基变量,；,X,N,为,非基变量,；,称为,基本解,满足非负约束的基本解为,基本可行解；,与基本可行解对应的,B,称为,可行基。,2.,基变量、目标函数的非基变量表达,基变量的非基变量表达：,当,j,0,时，,Z,可进一步增大，称为,检验数,。,目标函数的非基变量表达：,3.,单纯形法计算步骤,c,j,3,2,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,0,x,3,10,2,1,1,0,0,x,4,8,1,1,0,1,j,=,c,j,-z,j,3,2,0,0,解,：,1,标准化,2,找出初始基本可行解，列出初始单纯形表,3,判断：求出检验数,j,=,cj-zj,，当所有,j0,找到最优解，否则转第,4,步,（,1,）找出最大检验数,j,，,对应的变量为引进变量（入基变量）。（,x1,）,（,2,）根据最小比值原则确定离去变量（出基变量）。（,x3,）,4,找出新的基本可行解,（,3,）用引进变量替换离去变量，列出新的单纯形表,c,j,3,2,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,0,x,3,10,2,1,1,0,5,0,x,4,8,1,1,0,1,8,j,=,c,j,-z,j,3,2,0,0,a.,主元素行,=,原主元素行,/,主,b.,主元素列：新表中为单位向量，除主元素位为“,1”,，其余为“,0”,c.,其它行列数学按矩形规则得到,0,-3/2,1/2,0,j,=,c,j,-z,j,6,1,-1/2,1/2,0,3,x,4,0,10,0,1/2,1/2,1,5,x,1,3,x,4,x,3,x,2,x,1,b,x,B,c,B,0,0,2,3,c,j,-1,-1,0,0,j,=,c,j,-z,j,2,-1,1,0,6,x,2,2,-1,1,0,1,2,x,1,3,x,4,x,3,x,2,x,1,b,x,B,c,B,0,0,2,3,c,j,A=0,，则该行数字不变,B=0,，则该列数学不变,最优解：,x1=4,x2=2,x6=4,其它,=0,最优值：,max z=24+32=14,作业：,P26,：,2,（,1,），,3,（,3,）,演示实验,线性规划,Excel,求解,1.,ExcelORM,线性规划,目标函数,max,变量个数,2,约束个数,2,确定生成电子表模型并输入数据,.,2.,调用规划求解模板,设置规划求解参数对话框,(,工具,规划求解,),3.,求解,1.3,线性规划的对偶问题,假若该企业打算放弃生产产品的项目，而将所有设备出租，收取租金，如何确定三种设备单位台时的租金，才能使企业不至于蚀本？,1.3.1,线性规划的对偶模型,生产产品,I,的台时出租收入不小于产品,I,的利润,生产产品,II,的台时出租收入不小于产品,II,的利润,(1),(2),(2),式称为,(1),式的对偶问题,原问题,对偶问题,目标函数,max,约束右端项,目标函数系数,约,m,个,束 ,条 ,件 ,n,个,变 ,0,量 无约束,0,Min,目标函数中的系数,约束右端项,m,0,变,无约束 量,0,n,个 约,束,条,件,规范形式,非规范形式可按下面方法转换,对偶单纯形法迭代步骤：,1,列出单纯形表，表中原问题检验数为对偶问题基本可行解,2,表中基变量列为对偶问题检验数,当所有检验数,0,时，找到最优解，否则转第三步,3,（,1,）找出最小检验数，对应变量为离去变量,（,2,）对偶问题基本可行解与离去变量所在行之最小比值,=,min,j,/a,kj,|,a,kj,=0,则无可行解,),确定主元素，主元素对应变量为引进变量,（,3,）将引进变量替换离去变量列出新的单纯形表，转,2,c,j,-10,-8,0,0,c,B,Y,B,b,y,1,y,2,y,3,y,4,0,0,y,3,y,4,-3,-2,-2,-1,-1,-1,1,0,0,1,c,j,-z,j,-10,-8,0,0,5,8,1.3.2,对偶单纯形法,0,-1/2,1/2,1,3/2,y,1,-10,0,-5,-3,0,c,j,-z,j,5/2,1,1,-1/2,-1/2,0,-1/2,y,4,0,y,4,y,3,y,2,y,1,b,Y,B,c,B,0,0,-8,-10,c,j,原问题最终单纯形表,原问题 对偶问题,解 检验数,检验数 解,对偶问题的解称为原问题的影子价格,;,影子价格可由检验数直接得到,.,1,-1,0,1,1,y,1,-10,-6,-2,0,0,c,j,-z,j,-2,1,1,0,1,y,2,-8,y,4,y,3,y,2,y,1,b,Y,B,c,B,0,0,-8,-10,c,j,c,j,3,2,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,3,x,1,2,1,0,1,-1,2,x,2,6,0,1,-1,2,j,=,c,j,-z,j,0,0,-1,-1,0,-1/2,1/2,1,3/2,y,1,-10,0,-5,-3,0,c,j,-z,j,5/2,1,1,-1/2,-1/2,0,-1/2,y,4,0,y,4,y,3,y,2,y,1,b,Y,B,c,B,0,0,-8,-10,c,j,1.4,应用举例,(P54,运作实例,1-1),媒体,可达消费者数,(,人,),单位广告成本,(,元,),媒体可提供广告数,(,个,),单位广告影响力数据,电视,I(,非黄金档,)x1,15000,1500,15,65,电视,2(,黄金档,)x2,20000,4000,10,90,网络,x3,40000,2000,40,30,报纸,x4,12000,450,20,40,杂志,x5,10000,600,15,20,解,:,1.,决策变量,:,xj,2.,目标,:,广告影响力最大,max Z=65x,1,+90 x,2,+30 x,3,+40 x,4,+20 x,5,3.,约束条件,:,可达消费者人数限制,:15000 x,1,+20000 x,2,+40000 x,3,+12000 x,4,+10000 x,5,2000000,