《线性规划及对偶问题.ppt》由会员分享，可在线阅读，更多相关《线性规划及对偶问题.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章 线性规划及对偶问题课时：8学时主讲：关文忠教学要求与主要内容教学要求与主要内容：n教学要求：教学要求：n通过本章的学习，了解线性规划及其对偶问题的基本理论；通过本章的学习，了解线性规划及其对偶问题的基本理论；掌握线性规划求解的基本方法掌握线性规划求解的基本方法单纯形法单纯形法,了解对偶单了解对偶单纯形方法，熟悉灵敏度分析的方法；会建构线性规划模型，纯形方法，熟悉灵敏度分析的方法；会建构线性规划模型，并会用并会用“规划求解规划求解”模板进行求解。模板进行求解。n主要内容：主要内容：n1.1线性规划模型线性规划模型n1.2线性规划求解基本方法线性规划求解基本方法n1.2.1图解法图解法n1
2、.2.2单纯形法简介单纯形法简介n1.3线性规划对偶问题线性规划对偶问题n1.4线性规划应用举例线性规划应用举例n本章小结本章小结1.1线性规划线性规划(LinearProgramming)模型模型n1.1.1问题的提出问题的提出产产品甲品甲 产产品乙品乙生生产产能力能力(小小时时)设备设备A A7 73 3210210设备设备B B4 45 5200200设备设备C C2 24 4180180计计划利划利润润(元元/件件)70706565设：产品甲生产设：产品甲生产x1，产品乙生产，产品乙生产x2目标：目标：Max z=70 x1+65x2约束条件：约束条件：设备设备A生产能力限制：生产能力
3、限制：7x1+3x2210设备设备B生产能力限制：生产能力限制：4x1+5x2200设备设备C生产能力限制：生产能力限制：2x1+4x2180产量非负限制：产量非负限制：x1，x20决策变量决策变量决策变量决策变量目标函数目标函数约束条件约束条件三要素：三要素：1.决策变量决策变量2.目标函数目标函数3.约束条件约束条件1.1.2线性规划模型线性规划模型n1.适用条件：适用条件：n（1）优化条件）优化条件:问题目标最大化、最小化的要求；问题目标最大化、最小化的要求；n（2）约束条件）约束条件:问题目标受一系列条件的限制；问题目标受一系列条件的限制；n（3）选择条件）选择条件:实现目标存在多种备
4、选方案；实现目标存在多种备选方案；n（4）非负条件的选择）非负条件的选择:根据问题的实际意义决定是否非负。根据问题的实际意义决定是否非负。n2.构建线性规划模型的步骤构建线性规划模型的步骤n（1）科学选择决策变量）科学选择决策变量n（2）根据实际问题的背景材料，找出所有的约束条件）根据实际问题的背景材料，找出所有的约束条件n（3）明确目标要求）明确目标要求n（4）确定是否增加决策变量的非负条件）确定是否增加决策变量的非负条件 例2nMin z=2x1+6x2+5x3+4x4+3x5n 0.50 x1+2.00 x2+3.00 x3+1.50 x4+0.80 x585n 0.10 x1+0.06
5、x2+0.04x3+0.15x4+0.20 x55n 0.08x1+0.70 x2+0.35x3+0.25x4+0.02x518n x1x50饲饲料料 营营养甲养甲(克克/公斤公斤)营营养乙养乙(克克/公斤公斤)营营养丙养丙(克克/公斤公斤)成本成本(元元/公斤公斤)1 10 050500 010100 008082 22 22 200000 006060 070706 63 33 300000 004040 035355 54 41 150500 015150 025254 45 50 080800 020200 002023 3需要需要85克克5克克18克克设设X1X2X3X4x5由决策变
6、量、目标函数和约束条件构成的问题称为规划问题，如果决策变量为可控由决策变量、目标函数和约束条件构成的问题称为规划问题，如果决策变量为可控连续变量，目标函数和约束条件则是决策变量的线性函数，则称为线性规划问题。连续变量，目标函数和约束条件则是决策变量的线性函数，则称为线性规划问题。（P12例例1.3）3.线性规划模型表示形式线性规划模型表示形式决策决策变变量；量；目目标标函数系数、价函数系数、价值值系数或系数或费费用系数；用系数；右端右端项项或或资资源常数；源常数；称称为约为约束系数或技束系数或技术术系数。系数。（1）一般形式：）一般形式：（2）集合形式：）集合形式：（3）向量形式：）向量形式：
7、（4）矩阵形式：）矩阵形式：【例例3】将将线性性规划模型一般表达式化划模型一般表达式化为矩矩阵阵形式。形式。解解:设设:1.1.3线性规划标准形式线性规划标准形式线线性性规规划划标标准模型的一般表达式准模型的一般表达式：非非标标准形式准形式标标准化方法准化方法：1.目目标标函数函数 2.约约束条件束条件为为不等式不等式:引引进进松松驰变驰变量量xs:引引进进剩余剩余变变量量xs:4.决策决策变变量量为为自由自由变变量量:5.约约束右端束右端项为负项为负:两端乘两端乘-1:03.约约束条件束条件为为不等式不等式:【例例4】将将线线性性规规划模型划模型转转化化为标为标准式准式解解:无无约约束束(4
8、)在第一、第三在第一、第三约约束左端加上松弛束左端加上松弛变变量量x4,x60，在第二约束左端减去剩余变量，在第二约束左端减去剩余变量x50 作业：P7576习题1、2，P78:8(1)9(2)建模1.2线性规划基本解法线性规划基本解法n几个基本概念几个基本概念:n可行解：凡满足约束条件的决策变量的取值称为线性规划可行解：凡满足约束条件的决策变量的取值称为线性规划的可行解。的可行解。n可行域可行域：所有可行解的集合称为线性规划的可行域。：所有可行解的集合称为线性规划的可行域。n最优解最优解：使目标函数达到最优值的可行解称为线性规划的：使目标函数达到最优值的可行解称为线性规划的最优解最优解n1.
9、2.1图解法图解法(graphicalmethod)n步骤步骤:n(1)平面上画出直角坐标平面上画出直角坐标;n(2)图示约束条件图示约束条件,标出满足所有约束条件的公共区域标出满足所有约束条件的公共区域(可可行域行域);n(3)图示目标函数的一根基线图示目标函数的一根基线(母线母线)按目标值要求按目标值要求,让基线让基线平行移动平行移动,直到与可行域相切为止直到与可行域相切为止,切点即为最优解切点即为最优解;n(4)求出切点坐标值求出切点坐标值,代入目标函数求得目标函数最优值代入目标函数求得目标函数最优值.可行域【例例1.6】运用运用图图解法求解解法求解线线性性规规划划问题问题(5,0)2x
10、1+x2=10 x1+x2=8(2,6)x1108302 5 8x2(0,8)3x1+2x2=6四种四种结结局局:x1x2唯一最优解x2x1无穷多最优解x1x2无界解x2x1无可行解1.2.2 单纯形法简介n最优解一定在可行域的顶点上最优解一定在可行域的顶点上,将顶点坐标代入目标函数有将顶点坐标代入目标函数有:n(0,0):z=30+20=0n(5,0):z=35+20=15n(0,8):z=30+28=16n(2,6):z=32+26=18n单纯形法的基本思路就是基本单纯形法的基本思路就是基本可行解的转移，先找到一个初可行解的转移，先找到一个初始基本可行解，如果不是最优始基本可行解，如果不是
11、最优解，设法转移到另一个基本可解，设法转移到另一个基本可行解，并使目标函数值不断增行解，并使目标函数值不断增加，直到找到最优解加，直到找到最优解。(5,0)(2,6)108302 5 8x2(0,8)x11.解的概念解的概念标准化NB标准化n定义定义:nA为为mn阶矩阵阶矩阵,若若A的秩的秩为为m,B为为A中的任意中的任意mm阶子矩阵阶子矩阵,且行列式且行列式|B|0,则称则称B为线性规划的一个为线性规划的一个基基；n对应的对应的XB为为基变量基变量；nXN为为非基变量非基变量；称为称为基本解基本解n满足非负约束的基本解满足非负约束的基本解为为基本可行解；基本可行解；n与基本可行解对应的与基本
12、可行解对应的B称称为为可行基。可行基。2.基变量、目标函数的非基变量表达基变量、目标函数的非基变量表达基变量的非基变量表达：基变量的非基变量表达：当j0时，Z可进一步增大，称为检验数。目标函数的非基变量表达：目标函数的非基变量表达：3.单纯形法计算步骤单纯形法计算步骤cj3200cBxBbx1x2x3x40 x31021100 x481101j=cj-zj3200解解：1标准化标准化2找出初始基本可行解，列出初始单纯形表找出初始基本可行解，列出初始单纯形表3判断：求出检验数判断：求出检验数j=cj-zj，当所有，当所有j0,找到最优解，否则转第找到最优解，否则转第4步步（1）找出最大检验数）找
13、出最大检验数j，对应的变量为引对应的变量为引进变量（入基变量）。（进变量（入基变量）。（x1）（2）根据最小比值原则确定离去变量）根据最小比值原则确定离去变量（出基变量）。（出基变量）。（x3）4找出新的基本可行解找出新的基本可行解（3）用引进变量替换离去变量，列出新）用引进变量替换离去变量，列出新的单纯形表的单纯形表cj3200cBxBbx1x2x3x4 0 x310211050 x4811018j=cj-zj3200a.主元素行主元素行=原主元素行原主元素行/主主b.主元素列：新表中为单位向量，除主元主元素列：新表中为单位向量，除主元素位为素位为“1”，其余为，其余为“0”c.其它行列数学
14、按矩形规则得到其它行列数学按矩形规则得到0-3/21/20j=cj-zj61-1/21/203x401001/21/215x13 x4x3x2x1bxBcB0023cj-1-100j=cj-zj2-1106x22-11012x13 x4x3x2x1bxBcB0023cjA=0，则该行数字不变，则该行数字不变B=0，则该列数学不变，则该列数学不变最优解：最优解：x1=4,x2=2,x6=4,其它其它=0最优值：最优值：maxz=24+32=14作业：作业：P26：2（1），），3（3）演示实验演示实验线性规划线性规划Excel求解求解1.ExcelORM线性规划线性规划目标函数目标函数max,变
15、量个数变量个数2,约束个数约束个数2,确定生成电子表模型确定生成电子表模型并输入数据并输入数据.2.调用规划求解模板调用规划求解模板,设置规划求解参数对设置规划求解参数对话框话框(工具工具规划求解规划求解)3.求解求解1.3 线性规划的对偶问题n假若该企业打算放弃生假若该企业打算放弃生产产品的项目，而将所产产品的项目，而将所有设备出租，收取租金，有设备出租，收取租金，如何确定三种设备单位如何确定三种设备单位台时的租金，才能使企台时的租金，才能使企业不至于蚀本？业不至于蚀本？1.3.1线性规划的对偶模型线性规划的对偶模型生产产品生产产品I的台时出租收入不小于产品的台时出租收入不小于产品I的利润的
16、利润生产产品生产产品II的台时出租收入不小于产品的台时出租收入不小于产品II的利润(1)(2)(2)式称为式称为(1)式的对偶问题式的对偶问题原问题原问题对偶问题对偶问题目标函数目标函数max约束右端项约束右端项目标函数系数目标函数系数约约m个个束束条条件件n个个变变0量量无约束无约束0Min目标函数中的系数目标函数中的系数约束右端项约束右端项m0变变无约束无约束量量0n个个约约束束条条件件 规范形式规范形式非规范形式可按下面方法转换非规范形式可按下面方法转换n对偶单纯形法迭代步骤：对偶单纯形法迭代步骤：n1列出单纯形表，表中原问列出单纯形表，表中原问题检验数为对偶问题基本可题检验数为对偶问题
17、基本可行解行解n2表中基变量列为对偶问题表中基变量列为对偶问题检验数检验数n当所有检验数当所有检验数0时，找到最时，找到最优解，否则转第三步优解，否则转第三步n3（1）找出最小检验数，对）找出最小检验数，对应变量为离去变量应变量为离去变量n（2）对偶问题基本可行）对偶问题基本可行解与离去变量所在行之最小解与离去变量所在行之最小比值比值n=minj/akj|akj=0则无可行解则无可行解)确定主元素，主元素对应变确定主元素，主元素对应变量为引进变量量为引进变量n（3）将引进变量替换离）将引进变量替换离去变量列出新的单纯形表，去变量列出新的单纯形表，转转2cj-10-800cBYBby1y2y3y
18、400y3y4-3-2-2-1-1-11001cj-zj-10-800581.3.2对偶单纯形法对偶单纯形法0-1/21/213/2y1-100-5-30cj-zj5/211-1/2-1/20-1/2y40y4y3y2y1bYBcB00-8-10cj原问题最终单纯形表原问题最终单纯形表原问题原问题对偶问题对偶问题解解检验数检验数检验数检验数解解对偶问题的解称为原问题的影子价格对偶问题的解称为原问题的影子价格;影子价格可由检验数直接得到影子价格可由检验数直接得到.1-1011y1-10-6-200cj-zj-21101y2-8y4y3y2y1bYBcB00-8-10cjcj3200cBxBbx1
19、x2x3x43x12101-12x2601-12j=cj-zj00-1-10-1/21/213/2y1-100-5-30cj-zj5/211-1/2-1/20-1/2y40y4y3y2y1bYBcB00-8-10cj1.4应用举例(P54运作实例1-1)媒体媒体可达消费者可达消费者数数(人人)单位广告成单位广告成本本(元元)媒体可提供广媒体可提供广告数告数(个个)单位广告影响单位广告影响力数据力数据电视电视I(非黄金档非黄金档)x11500015001565电视电视2(黄金档黄金档)x22000040001090网络网络x34000020004030报纸报纸x4120004502040杂志杂志
20、x5100006001520解解:1.决策变量决策变量:xj2.目标目标:广告影响力最大广告影响力最大maxZ=65x1+90 x2+30 x3+40 x4+20 x53.约束条件约束条件:可达消费者人数限制可达消费者人数限制:15000 x1+20000 x2+40000 x3+12000 x4+10000 x52000000电视广告数量限制电视广告数量限制:x1+x210广告总预算限制广告总预算限制:1500 x1+4000 x2+2000 x3+450 x4+600 x5300000电视广告限制电视广告限制:1500 x1+4000 x2180000媒体可提供广告数限制媒体可提供广告数限
21、制:x115,x210,x340,x420,x515要求要求:(1)可达消费者人数可达消费者人数2,000,000人人;(2)电视广告数量电视广告数量10个个;广告总预算广告总预算300,000元元;其中电视广告预算其中电视广告预算180,000元元.1.4应用举例(P54运作实例1-1)ExcelORM生成的工作生成的工作表模型表模型设置规划求设置规划求解参数解参数得到最优解得到最优解本章小结本章小结n本章着重介绍了线性规划模型的特性和单纯形法的基本原本章着重介绍了线性规划模型的特性和单纯形法的基本原理理.n1.线性规划模型线性规划模型n基本条件：优化条件、约束条件、选择条件、变量非负的基本
22、条件：优化条件、约束条件、选择条件、变量非负的选择。选择。n建模步骤：科学选择决策变量、找出所有约束条件、明确建模步骤：科学选择决策变量、找出所有约束条件、明确目标要求、非负变量的选择。目标要求、非负变量的选择。n2.线性规划对偶问题线性规划对偶问题n对偶问题与原问题的相对的，即对偶的对偶是原问题。对偶问题与原问题的相对的，即对偶的对偶是原问题。n对偶问题的解为原问题的影子价格，原问题的解为对偶问对偶问题的解为原问题的影子价格，原问题的解为对偶问题的影子价格。题的影子价格。n3.单纯形法求解步骤：单纯形法求解步骤：找出：找出：k=maxj|j0 以以alk为为中心元素中心元素进进行迭代行迭代列初始列初始单纯单纯形表形表 所有所有aik0?所有所有j0？得到最得到最优优解解YESYESNONO无界无界结结束束作业：P77:5(1)(4)P79:9(3)