《第1-2讲序，线性规划 优化理论 教学课件》由会员分享，可在线阅读，更多相关《第1-2讲序，线性规划 优化理论 教学课件（169页珍藏版）》请在金锄头文库上搜索。
1、1,优化理论,四川大学经济学院 邹瑾 电子邮箱：,绪论,优化理论概述 优化理论的历史 优化理论的工作步骤 本课程的内容,学习要求,1.了解优化理论的含义和历史。2.掌握优化理论的工作步骤。3.了解优化理论的主要分支。,一、什么是优化理论？,由于优化理论研究与应用的广泛性和复杂性，人们至今没有形成一个统一的定义。下为几种的代表性界定： 优化理论是依据给定目标和约束条件，从众多方案中选择最优方案的最优化技术。(Gerard Corunrjols etc: “Optimization methods in finance”,Cambridge University Press) 最优化方法是近几十年
2、形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。(何坚勇：最优化方法， 清华大学出版社) 在经济管理工作中，经常需要从多种方案中确定一种最佳方案，确定最佳方案的方法就是最优化方法，其理论基础就是最优化理论 。 ( 傅英定等：最优化理论与方法，国防工业出版社),我们的看法,优化理论是数学理论与管理科学的融合：它的目的是研究一个系统的组织管理中可以定量的优化问题，为决策者提供有依据的最优方案，以实现最有效的管理；它采用的主要方法是建立数学模型并求解。优化理论可以称为“管理数学”。,二、优化理论的来源,优化理论的三个来源：军事、经济、管理,优化理论的起源-军事,第
3、二次世界大战期间，英、美等国的军事部门为战争需要而成立的一些研究小组的研究活动。 这些研究的最主要的特点是集中一批跨多种学科领域的科学研究人员，有组织地对一特定问题进行全面、系统的分析，提出提高某武器系统效率的操作方法和执行策略。,应用概率及随机过程,优化理论,运筹学,应用统计,数值计算和仿真,其他,优化理论,优化理论,优化理论,优化理论,优化理论,优化理论,优化理论,优化理论,成功的研究案例,如何布置防空雷达 反潜作战中的深水炸弹投放 轰炸机对德国地面目标轰炸的命中率,核武器发展方向决策,数学模型：其中，k ：毁伤力值y ：爆炸力c ：命中精度,优化理论的起源经济,数理经济对理论理论的影响
4、魁奈的经济表 瓦尔特提出的经济平衡问题 冯.诺依曼提出的广义经济平衡模型 康托洛维奇发表的生产组织和计划中的数学方法,优化理论的起源-管理,管理科学优化理论的关系 管理理论中最有影响的三个学派中的两个（古典学派与系统学派）广泛应用了优化理论的方法。 古典学派的代表性人物Taylor、Cantt到等提出的动作分析、甘特图至今还在使用。,优化理论的发展,线性规划,非线性规划,动态规划,网络优化,组合优化,数学规划,优化理论,代表人物： Dr. Hanif Sherali virginia tech Integer Programming Dr. Yinyu Ye Stanford Linear C
5、onic Optimization,杜栋、庞庆华：现代综合评价方法与案例精选，清华大学出版社，2005,经济金融中常见优化问题：,经济均衡问题及其应用投资组合问题市场营销问题,三、优化理论研究的工作步骤,优化理论研究的主要目的是-发现问题和解决问题 发现影响系统运行效率的主要问题 提出改进现有系统的运行效率的建议 合理配置和使用系统内的稀缺资源,长期筹资问题,比如说对企业来说，筹资结构的选择是多样化的，怎么构建企业最优资本结构呢？,问题分析 比如说对企业来说，怎么构建最佳资本结构？,何谓企业“最佳资本结构”？影响因素有哪些？约束条件是怎么样的？ 采用哪种数学模型？ 如何求解？ 解是什么？,优化
6、模型的工作步骤,（1）分析与表述问题提出问题，明确目标，找出系统变量，弄清其变化范围、相互关系，以及对目标的影响，分析解决问题的可行性。 技术可行性：有无现成方法可使用；（2）建立数学模型 模型是对现实世界的抽象和映射，构造模型时要根据一些假设对模型进行必要地抽象和简化。 （3）模型求解,四、本课程的主要内容,掌握优化理论的基本分析方法 线性优化 整数优化 决策分析中的优化技术 动态优化,第二讲 线性规划,线性规划是优化理论中出现最早、运用最广泛、最基本的优化方法。,第二章 线性规划,最早和最广泛使用的最优化方法-线性规划的发明 丹捷格1947年提出单纯形法。 康托诺维奇于1939年提出用于前
7、苏联经济计划的类似模型及“解乘数法”的求解方法。（与库伯曼斯因对资源最优分配理论的贡献而获得1975年诺贝尔经济学奖） 冯.诺依曼和摩根斯坦1944年发表的对策论与经济行为涉及与线性规划等价的对策问题及线性规划对偶理论 从1964年诺贝尔经济学奖后，到1992年24年间的32名获奖者中有13人（40%）从事过与线性规划有关的研究工作，其中比较著名的还有Simon、Samullson、Leontief、Arrow、Miller等 在世界500家最大的企业中，有85的企业使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用已为使用者节约了数以亿万计的资金。,最基本的最优化方法,网络规划、整数
8、规划、目标规划和多目标规划都是以线性规划为基础的。 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。,第一章 线性规划与单纯形方法,1.1 线性规划的基本概念 1.2 线性规划的基本理论 1.3 单纯形方法 1.4求解线性规划的软件工具 1.5 线性规划应用举例,1.1 线性规划的基本概念,1.线性规划模型 2.线性规划模型的一般形式 3.线性规划隐含的假定 4.线性规划的标准形式 5.线性规划的图解法,1.线性规划模型,例1.1 生产计划问题 胜利家具厂生产桌子和椅子两种家具。桌子售价50元。椅子售价30元，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时
9、，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大。,生产方案,生产价格高的产品：能生产25个桌子，木工剩余20小时，销售收入1250元。 替代生产方案1：生产20个桌子，10个椅子，木工仍剩余10小时，销售收入1300元。 替代生产方案2：生产15个桌子，20个椅子，用完全部工时，销售收入1350元,资源使用计算表,可能的生产方案,用手工计算也可找出很多可行方案 对于简单问题有时也可找出最优方案 当问题更复杂时，如有20种产品，消耗10种资源，用人工计算是否有效？ 一个很简单的问题都可能
10、存在无数可行解，从中找出最优解不是容易的事。 线性规划模型是求解这类问题的有效工具。,生产计划数学模型,决策变量：模型要决定的未知量 x1 = 生产桌子的数量， x2 = 生产椅子的数量 目标函数：决定线性规划优化方向 max: z = 50x1 + 30x2,约束方程：反映客观条件的限制,木工工时不能超过可用工时 4x1 + 3x2 120 油漆工工时不能超过可用工时 2x1 + 3x2 50 非负约束 x10， x20，,max: z = 50x1 + 30x2 S.T. 4x1 + 3x2 120 2x1 + 3x2 50x10， x20,线性规划是求一个线性函数在满足一组线性等式或不等
11、式方程条件下极值的数学问题的统称。 线性规划模型由三部分组成： 1 由决策变量构成的反映决策者目标的线性目标函数； 2 一组由决策变量的线性等式或不等式构成的约束方程； 3 限制决策变量取值范围的非负约束。,2、线性规划模型的一般形式,线性规划问题的一般形式可以写为：,max: z = c1x1 + c2 x2 + + cnxn s.t. a11x1 + a12 x2 + + a1nxn b1 a21x1 + a22 x2 + + a2nxn b2 am1x1 + am2 x2 + + amnxn bm x1, x2, xn 0,x1, x2, xn为决策变量，表示第n种生产经营活动的规模。
12、z = c1x1 + c2 x2 + + cnxn 称为目标函数，反映生产活动的目标，cj为（j=1，2,n）为目标函数系数（又称价值系数）。表示与活动相关的费用或收益。 a11x1 + a12 x2 + + a1nxn bi，为使用第i种资源的资源限制约束。 xj0，为非负约束,3、线性规划隐含的假定,线性规划要求目标函数和约束方程必须是线性函数隐含了如下假定： 比例性假定 可加性假定 连续性假定 确定性假定,比例性假定: 目标函数的改变量和决策变量的改变量成比例。 由决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。 比例性假定意味着每种经营活动对目标函数的贡献是一个常数，对
13、资源的消耗也是一个常数。,可加性假定: 每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。,连续性假定: 线性规划问题中的决策变量应取连续值。 确定性假定:线性规划中的所有参数都是确定的参数。线性规划问题是确定性问题，不包含随机因素。,4、线性规划的标准型,所有的约束必须为等式约束，所有的变量为非负变量，目标函数求最大化max: z = c1x1 + c2 x2 + + cnxn s.t. a11x1 + a12 x2 + + a1nxn = b1 a21x1 + a22 x2 + + a2nxn = b2 am1x1 + am2 x2 +
14、 + amnxn = bm x1, x2, xn 0,如何将线性规划问题转化为标准型,将极小化的目标函数转化：min f(x) = max-f(x)变量取值限制约束的转化： xi 0 做变量代换yi = -xi xi 是自由变量，做变量代换： xi = ui vi，ui 0,vi 0,把不等式约束转化为等式约束： 加入松弛变量 将“”约束转化为标准形式 x1+ x2 10 x1 + x2 + xs = 10，xs 0， 引入一剩余变量，将“ ”约束转化标准形式x1+ x2 10 x1 + x2 - xs = 10，xs 0,例1.3 将下列线性规划模型转变为标准形式：min: 3x1- x2
15、+ 4x3s.t. x1 - 2x2 + 5x3 02x1 + x2 - 3x3 03x1 - 5x2 = 0x1 0, x2 0 变量代换：x2= -y，x3 = u - v， 并引入松弛变量s1和s2,令x2= -y，x3 = u - v，并引入松弛变量s1和s2 max: -3x1 - y - 4u + 4vs.t. x1 + 2y + 5u - 5v - s1 = 02x1 - y - 3u + 3v + s2 = 03x1 + 5y = 0x10, y0, u0, v0, s10, s20,矩阵表达形式,max: cxs.t. Ax = b x 0,5、线性规划的图解法,图解法简单、直观、便于初学者了解线性规划基本原理和几何意义： 例1.4 用图解法求解生产计划问题 max: z = 50x1 + 30x2s.t. 4x1 + 3x2 120 2x1 + x2 50x1, x20,50 45 40 35 30 25 20 15 10 5 0,| | | | | | 5 10 15 20 25 30,x1,x2,目标函数 Max Z = 50x1 + 30x2约束条件 4x1 +3x2 1202 x1 + x2 50 x1、 x2 0,
