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

《第1章线性规划及对偶问题.ppt》由会员分享，可在线阅读，更多相关《第1章线性规划及对偶问题.ppt（29页珍藏版）》请在课桌文档上搜索。

1、第1章 线性规划及对偶问题,教学要求与主要内容：,教学要求：通过本章的学习，了解线性规划及其对偶问题的基本理论；掌握线性规划求解的基本方法单纯形法,了解对偶单纯形方法，熟悉灵敏度分析的方法；会建构线性规划模型，并会用“规划求解”模板进行求解。主要内容：1.1 线性规划模型1.2 线性规划求解基本方法1.2.1 图解法1.2.2 单纯形法简介1.3 线性规划对偶问题1.4 线性规划应用举例本章小结,1.1 线性规划(Linear Programming)模型,1.1.1 问题的提出,设：产品甲生产x1，产品乙生产x2,目标：Max z=70 x1+65x2,约束条件：,设备A生产能力限制：7x1

2、+3x2210,设备B生产能力限制：4x1+5x2200,设备C生产能力限制：2x1+4x2180,产量非负限制：x1，x20,决策变量,决策变量,目标函数,约束条件,三要素：1.决策变量2.目标函数3.约束条件,1.1.2 线性规划模型,1.适用条件：（1）优化条件:问题目标最大化、最小化的要求；（2）约束条件:问题目标受一系列条件的限制；（3）选择条件:实现目标存在多种备选方案；（4）非负条件的选择:根据问题的实际意义决定是否非负。2.构建线性规划模型的步骤（1）科学选择决策变量（2）根据实际问题的背景材料，找出所有的约束条件（3）明确目标要求（4）确定是否增加决策变量的非负条件,例2,M

3、in z=2x1+6x2+5x3+4x4+3x5 0.50 x1+2.00 x2+3.00 x3+1.50 x4+0.80 x585 0.10 x1+0.06x2+0.04x3+0.15x4+0.20 x55 0.08x1+0.70 x2+0.35x3+0.25x4+0.02x518 x1x50,设X1X2X3X4x5,由决策变量、目标函数和约束条件构成的问题称为规划问题，如果决策变量为可控连续变量，目标函数和约束条件则是决策变量的线性函数，则称为线性规划问题。（P12例1.3）,3.线性规划模型表示形式,决策变量；,目标函数系数、价值系数或费用系数；,右端项或资源常数；,称为约束系数或技术系

4、数。,（1）一般形式：,（2）集合形式：,（3）向量形式：,（4）矩阵形式：,【例3】将线性规划模型一般表达式化为矩阵形式。,解:,设:,1.1.3 线性规划标准形式,线性规划标准模型的一般表达式：,非标准形式标准化方法：,1.目标函数,2.约束条件为不等式:,引进松驰变量xs:,引进剩余变量xs:,4.决策变量为自由变量:,5.约束右端项为负:,两端乘-1:,0,3.约束条件为不等式:,【例4】将线性规划模型转化为标准式,解:,无约束,(4)在第一、第三约束左端加上松弛变量x4,x60，在第二约束左端减去剩余变量x50,作业：P7576习题1、2，P78:8(1)9(2)建模,1.2 线性规

5、划基本解法,几个基本概念:可行解：凡满足约束条件的决策变量的取值称为线性规划的可行解。可行域：所有可行解的集合称为线性规划的可行域。最优解：使目标函数达到最优值的可行解称为线性规划的最优解 1.2.1 图解法(graphical method)步骤:(1)平面上画出直角坐标;(2)图示约束条件,标出满足所有约束条件的公共区域(可行域);(3)图示目标函数的一根基线(母线)按目标值要求,让基线平行移动,直到与可行域相切为止,切点即为最优解;(4)求出切点坐标值,代入目标函数求得目标函数最优值.,【例1.6】运用图解法求解线性规划问题,(5,0),(2,6),x1,(0,8),四种结局:,1.2.

6、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),10830,2 5 8,x2,(0,8),x1,1.解的概念,标准化,标准化,定义:A为mn阶矩阵,若A的秩为m,B为A中的任意mm阶子矩阵,且行列式|B|0,则称B为线性规划的一个基；对应的XB为基变量；XN为非基变量；,称

7、为基本解,满足非负约束的基本解为基本可行解；与基本可行解对应的B称为可行基。,2.基变量、目标函数的非基变量表达,基变量的非基变量表达：,当j0时，Z可进一步增大，称为检验数。,目标函数的非基变量表达：,3.单纯形法计算步骤,解：1标准化,2找出初始基本可行解，列出初始单纯形表,3判断：求出检验数j=cj-zj，当所有j0,找到最优解，否则转第4 步,（1）找出最大检验数j，对应的变量为引进变量（入基变量）。（x1）,（2）根据最小比值原则确定离去变量（出基变量）。（x3）,4找出新的基本可行解,（3）用引进变量替换离去变量，列出新的单纯形表,a.主元素行=原主元素行/主b.主元素列：新表中为

8、单位向量，除主元素位为“1”，其余为“0”c.其它行列数学按矩形规则得到,0,-3/2,1/2,0,j=cj-zj,6,1,-1/2,1/2,0,3,x4,0,10,0,1/2,1/2,1,5,x1,3,x4,x3,x2,x1,b,xB,cB,0,0,2,3,cj,-1,-1,0,0,j=cj-zj,2,-1,1,0,6,x2,2,-1,1,0,1,2,x1,3,x4,x3,x2,x1,b,xB,cB,0,0,2,3,cj,A=0，则该行数字不变B=0，则该列数学不变,最优解：x1=4,x2=2,x6=4,其它=0最优值：max z=24+32=14,作业：P26：2（1），3（3）,演示实验

9、线性规划Excel求解,1.ExcelORM线性规划目标函数max,变量个数2,约束个数2,确定生成电子表模型并输入数据.,2.调用规划求解模板,设置规划求解参数对话框(工具规划求解),3.求解,1.3 线性规划的对偶问题,假若该企业打算放弃生产产品的项目，而将所有设备出租，收取租金，如何确定三种设备单位台时的租金，才能使企业不至于蚀本？,1.3.1 线性规划的对偶模型,生产产品I的台时出租收入不小于产品I的利润,生产产品II的台时出租收入不小于产品II的利润,(1),(2),(2)式称为(1)式的对偶问题,规范形式,非规范形式可按下面方法转换,对偶单纯形法迭代步骤：1列出单纯形表，表中原问题

10、检验数为对偶问题基本可行解2表中基变量列为对偶问题检验数当所有检验数0时，找到最优解，否则转第三步3（1）找出最小检验数，对应变量为离去变量（2）对偶问题基本可行解与离去变量所在行之最小比值=minj/akj|akj=0则无可行解)确定主元素，主元素对应变量为引进变量（3）将引进变量替换离去变量列出新的单纯形表，转2,1.3.2 对偶单纯形法,0,-1/2,1/2,1,3/2,y1,-10,0,-5,-3,0,cj-zj,5/2,1,1,-1/2,-1/2,0,-1/2,y4,0,y4,y3,y2,y1,b,YB,cB,0,0,-8,-10,cj,原问题最终单纯形表,原问题 对偶问题 解 检验

11、数检验数 解,对偶问题的解称为原问题的影子价格;影子价格可由检验数直接得到.,1,-1,0,1,1,y1,-10,-6,-2,0,0,cj-zj,-2,1,1,0,1,y2,-8,y4,y3,y2,y1,b,YB,cB,0,0,-8,-10,cj,1.4应用举例(P54运作实例1-1),解:1.决策变量:xj2.目标:广告影响力最大max Z=65x1+90 x2+30 x3+40 x4+20 x53.约束条件:可达消费者人数限制:15000 x1+20000 x2+40000 x3+12000 x4+10000 x52000000电视广告数量限制:x1+x210广告总预算限制:1500 x1

12、+4000 x2+2000 x3+450 x4+600 x5300000电视广告限制:1500 x1+4000 x2180000媒体可提供广告数限制:x1 15,x2 10,x3 40,x4 20,x5 15,要求:(1)可达消费者人数2,000,000人;(2)电视广告数量10个;广告总预算300,000元;其中电视广告预算180,000元.,1.4应用举例(P54运作实例1-1),ExcelORM生成的工作表模型,设置规划求解参数,得到最优解,本章小结,本章着重介绍了线性规划模型的特性和单纯形法的基本原理.1.线性规划模型基本条件：优化条件、约束条件、选择条件、变量非负的选择。建模步骤：科学选择决策变量、找出所有约束条件、明确目标要求、非负变量的选择。2.线性规划对偶问题对偶问题与原问题的相对的，即对偶的对偶是原问题。对偶问题的解为原问题的影子价格，原问题的解为对偶问题的影子价格。,3.单纯形法求解步骤：,找出：k=maxj|j0,以alk为中心元素进行迭代,列初始单纯形表,所有aik0?,所有j0？,得到最优解,YES,YES,NO,NO,无界,结束,