第二章线性规划模型-课件

第二章第二章 线性规划模型线性规划模型 线性规划是数学规划中研究较早线性规划是数学规划中研究较早,发展较快发展较快,应用广泛的应用广泛的的一个重要分支的一个重要分支,也是数学模型中的一项重要内容也是数学模型中的一项重要内容.它在生产它在生产安排、物质运输、投资决策、交通运输等现代工农业和经济安排、物质运输、投资决策、交通运输等现代工农业和经济安排、物质运输、投资决策、交通运输等现代工农业和经济安排、物质运输、投资决策、交通运输等现代工农业和经济管理等方面都有着广泛的应用管理等方面都有着广泛的应用.我们知道我们知道,在经济活动中提在经济活动中提高经济效益一般可通过两个途径高经济效益一般可通过两个途径:第一是加强技术方面的改第一是加强技术方面的改造以降低生产过程中对资源的消耗从而降低制造成本造以降低生产过程中对资源的消耗从而降低制造成本;第二第二是提高企业的管理是提高企业的管理,即合理安排人力及物力，以降低企业的即合理安排人力及物力，以降低企业的管理成本管理成本.线性规划最早由前苏联数学家康托罗维奇首先提出线性规划最早由前苏联数学家康托罗维奇首先提出,1947年美国数学家丹齐克提出了解决线性规划的普遍算法年美国数学家丹齐克提出了解决线性规划的普遍算法单纯形方法；单纯形方法；1947年美国数学家冯年美国数学家冯.诺依曼提出了对偶理论诺依曼提出了对偶理论并开创了线性规划的许多新领域并开创了线性规划的许多新领域;线性规划的研究成果推动线性规划的研究成果推动了其他数学规划问题包括整数规划、随机规划和非线性规划了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究的算法研究.一一、线性规划模型、线性规划模型 一、模型的建立一、模型的建立 我们从下面几个例子引出线性规划的模型我们从下面几个例子引出线性规划的模型.问题一问题一 某车间为其它部门生产某车间为其它部门生产200套钢管三脚架套钢管三脚架,每套由长度为每套由长度为2.9、2.1、1.5米的钢管各一根组成米的钢管各一根组成.已知原料钢管的长度为已知原料钢管的长度为7.4米米,如何确定钢管的切割方案如何确定钢管的切割方案,能使钢管的利用率最高能使钢管的利用率最高.分析分析 首先对长度为首先对长度为7.4米的钢管要确定合适的切割方案米的钢管要确定合适的切割方案,并使得每次切割后丢弃的原料尽可能少并使得每次切割后丢弃的原料尽可能少.为此建立所有可能为此建立所有可能的切割方案的切割方案:1.440080.831070.222061.10305030140.911130.302120.11021余料余料1.52.12.9编号编号 以以 表示在第表示在第 种方案下所使用的原料数种方案下所使用的原料数,则一个合适的则一个合适的切割方案表现为切割方案表现为而衡量方案好坏的评价指标为在该方案下所丢弃的余料数而衡量方案好坏的评价指标为在该方案下所丢弃的余料数,即反映为余料函数即反映为余料函数由此得到该问题的数学表达式由此得到该问题的数学表达式:问题二问题二 投资决策问题投资决策问题 某基金公司为扩展业务需要招聘部分基金经理某基金公司为扩展业务需要招聘部分基金经理.在业务在业务考试中考试中,考官提出了这样一个问题考官提出了这样一个问题.为公司制定一个五年期的投资计划为公司制定一个五年期的投资计划.项目可供选择：项目可供选择：现已知有四个投资现已知有四个投资项目项目A:于每年的年初可进行投资于每年的年初可进行投资,并于次年末完成并于次年末完成,投资投资收益为收益为6%；项目项目B:于第三年的年初进行投资于第三年的年初进行投资,并于第五年的年末完成并于第五年的年末完成投资投资,投资收益为投资收益为16.5%,投资额不超过投资额不超过35万；万；项目项目C:于第二年的年初进行投资于第二年的年初进行投资,并于第五年的年末完成并于第五年的年末完成成投资成投资,投资收益为投资收益为21.5%,投资额不超过投资额不超过40万；万；项目项目D:于每年的年初可进行投资于每年的年初可进行投资,并于当年末完成并于当年末完成,投资投资收益为收益为2.35%.该公司现有资金该公司现有资金120万万,试为该公司制定投资计划试为该公司制定投资计划.模型建立模型建立 以以 代表年份代表年份,分别表示分别表示4个项个项目目,表示在第表示在第 年对项目年对项目 的投资额的投资额.显然显然,每年的资金必每年的资金必须全部用于某些项目的投资须全部用于某些项目的投资.由条件所设知每年可行的投由条件所设知每年可行的投资计划为资计划为第一年第一年第二年第二年第三年第三年第四年第四年第五年第五年 投资收益函数为投资收益函数为 由此得到该问题的数学模型由此得到该问题的数学模型 问题三问题三 运输问题运输问题产地产地的产量分别为的产量分别为对该类物资对该类物资,有有 个需个需并设并设求点求点,分别记为分别记为 需求量为需求量为又从产地又从产地 到需求点到需求点 的单位运输成本为的单位运输成本为求相应的运求相应的运输方案输方案.设有一种物资设有一种物资,它有它有 个产地个产地,记为记为 模型建立模型建立 设设 表示从产地表示从产地 到需求点到需求点 的运输量的运输量,则合适的运输则合适的运输方案表现为方案表现为对产量的要求对产量的要求对需求量的要求对需求量的要求 而相应的目标函数为而相应的目标函数为 由此得到相应的数学模型为由此得到相应的数学模型为 思考思考 一般情况下一般情况下,产销是不平衡的产销是不平衡的,此时相应的模型将如何此时相应的模型将如何?在上面例中在上面例中,目标函数及约束条件均为线性表达式目标函数及约束条件均为线性表达式,故故把这样的模型称为把这样的模型称为线性规划模型线性规划模型.定义定义 如下的一组数学关系式即称为一个如下的一组数学关系式即称为一个线性规划线性规划或或线线性规划模型性规划模型 求解线性规划的传统解法是单纯形法求解线性规划的传统解法是单纯形法.但单纯形方法针但单纯形方法针 对的是线性规划的标准型对的是线性规划的标准型,为此引入标准型（典式）的概为此引入标准型（典式）的概念念.定义定义 具有如下形式的线性规划为线性规划的具有如下形式的线性规划为线性规划的标准型标准型:对于非标准形式的线性规划都可以经过适当的转换而化对于非标准形式的线性规划都可以经过适当的转换而化化为相应的标准型化为相应的标准型.二、线性规划的解法二、线性规划的解法 1.解的概念解的概念 设线性规划设线性规划定义定义 设设是是 维实向量维实向量,若若 满足满足,则称则称 是线性规划的一个是线性规划的一个解解;若解若解 满足满足,则称其为规则称其为规划的划的可行解可行解;可行解的全体称为可行解的全体称为可行域可行域;使规划达到极值使规划达到极值 的可行解称为线性规划的的可行解称为线性规划的最优解最优解,相应的目标函数值称为相应的目标函数值称为最优解值最优解值.2.图解法图解法 线性规划的图解法针对的是具有两个决策变量的线性规线性规划的图解法针对的是具有两个决策变量的线性规划问题划问题.设线性规划设线性规划 求解过程求解过程建立合适的坐标系统建立合适的坐标系统;对约束条件对约束条件 建立第建立第 条直线条直线 从而确定可行域从而确定可行域;对等值线对等值线:由规划的类型确定等值线由规划的类型确定等值线移动方向移动方向,则最优解为等值线在移动过程中与可行域的则最优解为等值线在移动过程中与可行域的最最后交点后交点.例例 求解规划求解规划最后交点最后交点移动方向移动方向解解 由图中可以看到由图中可以看到,可行域为多边形区域可行域为多边形区域 最最优解为优解为 最优解值为最优解值为 3.单纯形方法单纯形方法 设线性规划设线性规划并进一步假定约束条件系数矩阵中并进一步假定约束条件系数矩阵中中有中有 阶单阶单位子矩阵位子矩阵.单纯形方法解题步骤单纯形方法解题步骤:1.建立单纯形表建立单纯形表,并保证在该表中基变量的价值系数为并保证在该表中基变量的价值系数为0.2.求出当前解求出当前解,并判定当前解是否为最优解并判定当前解是否为最优解.（当前解（当前解3.若当前解不是最优解若当前解不是最优解,则进行换基则进行换基:则检验数行则检验数行 为新价值系数的相反数行为新价值系数的相反数行.的定义是基变量取右端的常数项的定义是基变量取右端的常数项,非基变量取为零）非基变量取为零）.判定当前解是否为最优解的条件是判定当前解是否为最优解的条件是确定进基变量确定进基变量 其中其中 由关系由关系确定确定.确定出基变量确定出基变量 其中其中而而 为第为第 行对应的基变量行对应的基变量.以以 为为主元主元进行迭代进行迭代,目标目标:主元化为主元化为1,该列的其余该列的其余4.重新进行判定重新进行判定.元化为零元化为零.（只能用（只能用行变换行变换）注注 线性规划的单纯性表线性规划的单纯性表 设线性规划为设线性规划为并且假设在约束条件系数矩阵中前并且假设在约束条件系数矩阵中前 个列向量为单位向量个列向量为单位向量,则相应的单纯形表为则相应的单纯形表为表中的表中的 行是检验数行行是检验数行,中的数是将中的数是将 消为消为0后后,取负取负值后所得到的值后所得到的.例例2 用单纯形方法求解线性规划用单纯形方法求解线性规划.解解 由前面讨论知原问题的单纯形表为由前面讨论知原问题的单纯形表为此时此时,当前解为当前解为由于由于 故当故当前解非最优解前解非最优解.所以所以主元主元主元主元故最优解为故最优解为 最优解值为最优解值为检验数非负检验数非负二、整数规划二、整数规划 在前面所涉及到的许多线性规划模型中在前面所涉及到的许多线性规划模型中,很多情况下很多情况下,除除了对变量有非负要求外了对变量有非负要求外,有时甚至要求其取值为整数型的有时甚至要求其取值为整数型的.例如在问题一中例如在问题一中,变量变量 表示在第表示在第 种方案下所使用的原种方案下所使用的原料钢管数料钢管数,则相应取值为非负整数则相应取值为非负整数.这样的线性规划称为这样的线性规划称为整数规划整数规划.若线性规划中对变量的要求为部分整数型的若线性规划中对变量的要求为部分整数型的,这样的规这样的规称为称为混合型混合型的的.在整数规划中在整数规划中,舍弃决策变量的整数限制舍弃决策变量的整数限制,所得到的规所得到的规划称为原规划所对应的划称为原规划所对应的松弛问题松弛问题.求解整数规划并不能通求解整数规划并不能通过求对应的松弛问题的最优解再取其整数部分而求得过求对应的松弛问题的最优解再取其整数部分而求得.求求解整数规划的方法主要有分枝定界法和割平面法解整数规划的方法主要有分枝定界法和割平面法.这里我这里我们仅介绍分枝定界法们仅介绍分枝定界法,有兴趣的读者可以参阅相应的书籍有兴趣的读者可以参阅相应的书籍.1.整数规划及分枝定界法整数规划及分枝定界法 求解整数规划的的分枝定界法求解整数规划的的分枝定界法 设线性规格设线性规格为整数为整数.求出对应松弛问题的最优解求出对应松弛问题的最优解,若该解为整数解若该解为整数解,则该解也则该解也是原规划的最优解是原规划的最优解,若该解不是整数解若该解不是整数解,则进行分枝则进行分枝;设设 不是整数解不是整数解,则最优整数解中的则最优整数解中的 必然满足必然满足因此将原问题分解成两个规划因此将原问题分解成两个规划 为整数为整数.及及为整数为整数.分别求出这两个规划所对应的松弛问题的最优解分别求出这两个规划所对应的松弛问题的最优解;若有一个分枝的解为整数解若有一个分枝的解为整数解,而另一个分枝的最优解的而另一个分枝的最优解的函数值小于该整数解的函数值函数值小于该整数解的函数值,则将该枝剪去（定界）并则将该枝剪去（定界）并由此得到原问题的最优解由此得到原问题的最优解;若两个分枝对应的松弛问题的最优解都不是整数解若两个分枝对应的松弛问题的最优解都不是整数解,则则分别进行分枝分别进行分枝,继续求解继续求解.例例3 求解整数规划求解整数规划且为整数且为整数.解解 由单纯性方法得到松弛问题的最优解由单纯性方法得到松弛问题的最优解:注意到该解不是整数解注意到该解不是整数解,取取 进行分枝进行分枝,形成形成2个规划个规划,规划规划且为整数且为整数.及规划及规划且为整数且为整数.这两个规划所对应的松弛问题的最优解分别为这两个规划所对应的松弛问题的最优解分别为 由于规划由于规划所对应的松弛问题的最优解值低于规划所对应的松弛问题的最优解值低于规划所对所对应的松弛问题的最优解值应的松弛问题的最优解值,且规划且规划所对应的松弛问题的所对应的松弛问题的解为整数解解为整数解,故规划故规划舍去（定界舍去（定界,剪枝）剪枝）,从而得到原从而得到原规划的最优解为规划的最优解为 2.01规划规划 整数规划中的一个特殊模型是整数规划中的一个特殊模型是01规划规划.在引入在引入01规规划之前先看一个例子划之前先看一个例子.问题三问题三课程选修方案确定课程选修方案确定 某学校规定某学校规定:运筹学专业的学生毕业时至少学习过两门运筹学专业的学生毕业时至少学习过两门数学课数学课,三门运筹学课和两门计算机课三门运筹学课和两门计算机课.这些课程的编号、这些课程的编号、名称、学分和所属类别如下表所示名称、学分和所属类别如下表所示,则毕业时学生最少可则毕业时学生最少可以学习这些课程中的哪些课程？又如果某个学生既希望选以学习这些课程中的哪些课程？又如果某个学生既希望选修课程的数量少修课程的数量少,而又能获得较多的学分而又能获得较多的学分,那么他该如何那么他该如何确定他的选修课程计划？确定他的选修课程计划？1,2计算机计算机,运筹学运筹学2数学实验数学实验95运筹学运筹学2自动化控制自动化控制8计算机计算机4程序设计程序设计77计算机计算机,运筹学运筹学3汇编语言汇编语言61,2数学数学,运筹学运筹学3应用统计应用统计57数学数学,计算机计算机3数据结构数据结构41,2数学数学,运筹学运筹学3最优化方法最优化方法3数学数学3线性代数线性代数2数学数学5微积分微积分1先修课先修课类别类别学分学分课程名称课程名称编号编号 建模建模 以以 表示该学生选修课程号为表示该学生选修课程号为 的课程的课程,而而则表示未选修该课程则表示未选修该课程.若希望课程数最少若希望课程数最少,则目标函数为则目标函数为至少选修至少选修2门数学课的要求表现为关系门数学课的要求表现为关系平行可得其它约束条件平行可得其它约束条件,由此得到关系由此得到关系再考虑对先修课的要求再考虑对先修课的要求.例如要选最优化方法例如要选最优化方法,则必须先则必须先修微积分与线性代数修微积分与线性代数,从而有关系从而有关系其它情况完全类似其它情况完全类似,从而有约束条件组从而有约束条件组由此得到问题对应的数学模型由此得到问题对应的数学模型:思考思考:若该学生希望能得到较高的学分而课程数尽可能少若该学生希望能得到较高的学分而课程数尽可能少,又该如何处理？又该如何处理？在问题三中我们看到在问题三中我们看到,由于决策变量表示是否选修第门由于决策变量表示是否选修第门课程课程,其取值只有其取值只有0和和1两种情况两种情况,因而相应的规划称为因而相应的规划称为01规划规划,在实际问题中在实际问题中,01规划出现的情况很多规划出现的情况很多.问题四问题四 背包问题背包问题 某人爬山某人爬山,可携带的物品有可携带的物品有 其重量为其重量为 价值为价值为 又携带的物品的总重量不得超过又携带的物品的总重量不得超过 则该登则该登山人该如何确定其携带方案山人该如何确定其携带方案,使价值为最高？使价值为最高？这样的问题称为这样的问题称为背包问题背包问题.分析分析以以 表示该登山人携带第表示该登山人携带第 种物品种物品,则容易得到则容易得到问题的模型为问题的模型为该问题也可用动态规划的方法求解该问题也可用动态规划的方法求解.01规划的常用解法称为规划的常用解法称为隐枚举法隐枚举法.3.指派问题与匈牙利方法指派问题与匈牙利方法 01规划中的一个重要形式是规划中的一个重要形式是指派问题指派问题.指派问题指派问题 设有设有 项工作项工作,交给交给 个人去完成个人去完成,各人完成每项工作的各人完成每项工作的代价（成本）为已知的代价（成本）为已知的,设第人完成第项工作的代价为设第人完成第项工作的代价为.规规定每人只能完成其中的一项工作定每人只能完成其中的一项工作,求相应的指派方案求相应的指派方案,使使完成这些工作的总代价为最小完成这些工作的总代价为最小.（这样的问题就称为（这样的问题就称为指派指派问题问题.）一个比较典型的指派模型为混合接力队员的选拔）一个比较典型的指派模型为混合接力队员的选拔.分析分析 引入变量引入变量 第第 项工作由第项工作由第 人去完成人去完成;第第 项工作由他人完成项工作由他人完成.注意到每人只能完成其中的一项注意到每人只能完成其中的一项,并且每项工作最多只有并且每项工作最多只有一人完成一人完成,由此相应的约束条件为由此相应的约束条件为及及而完成这些工作的总代价为而完成这些工作的总代价为由此得到指派问题的数学模型由此得到指派问题的数学模型 指派问题对应的数学模型属于指派问题对应的数学模型属于01规划的范畴规划的范畴,可以用可以用求解求解01规划的方法进行求解规划的方法进行求解.但求解相当繁琐但求解相当繁琐,匈牙利匈牙利数学家考尼格（数学家考尼格（Konig）提出了解决该问题的新的算法）提出了解决该问题的新的算法,因因而该方法称为匈牙利方法而该方法称为匈牙利方法.该矩阵称为指派问题中的该矩阵称为指派问题中的代价代价（成本成本）矩阵）矩阵.又引入矩阵又引入矩阵该矩阵称为指派问题中的该矩阵称为指派问题中的指派矩阵指派矩阵.为此首先引入矩阵为此首先引入矩阵 由指派条件由指派条件,矩阵中每行的元素只能有一个是矩阵中每行的元素只能有一个是1及每列的及每列的元素至多有一个元素至多有一个1,其余元均为其余元均为0.这样的矩阵称为指派矩阵这样的矩阵称为指派矩阵,对应的是某个指派方案对应的是某个指派方案.例例4 设指派问题中的代价矩阵为设指派问题中的代价矩阵为则下面的两个矩阵均可视为某个指派方案下的指派矩阵则下面的两个矩阵均可视为某个指派方案下的指派矩阵:相应的代价分别为相应的代价分别为 匈牙利方法匈牙利方法 首先我们讨论指派问题中的特殊形式首先我们讨论指派问题中的特殊形式,即即 的情况的情况.行缩减行缩减每行减去该行的最小数每行减去该行的最小数;列缩减列缩减每列减去该列的最小数；每列减去该列的最小数；判定是否有个独立的零判定是否有个独立的零.若有，则在指派矩阵中对应若有，则在指派矩阵中对应独立的零的独立的零的 取取1,其余的取其余的取0,由此得到最小代价的指派由此得到最小代价的指派方案方案;若没有个独立的零若没有个独立的零,则进行下面的迭代过程则进行下面的迭代过程在未被线划去的数中找最小数在未被线划去的数中找最小数;未被线划去的所有数都减去该数未被线划去的所有数都减去该数,除了两线的交叉点以除了两线的交叉点以外外,被线划去的数保持不变被线划去的数保持不变,而交叉点的数再加上该数而交叉点的数再加上该数;继续判定继续判定.例例5 用匈牙利方法求解指派问题用匈牙利方法求解指派问题,其中的代价矩阵为其中的代价矩阵为 解解 首先进行行列缩减首先进行行列缩减,由此得到由此得到对上面的矩阵对上面的矩阵,可以判定没有四个独立的零可以判定没有四个独立的零.事实上事实上,用三用三条线可以将所有的零划去条线可以将所有的零划去.此时相应的最小数为此时相应的最小数为2,继续迭代有继续迭代有该矩阵中有该矩阵中有4个独立的零个独立的零,因而对应的指派矩阵可取因而对应的指派矩阵可取 即对应的指派方案为即对应的指派方案为 而相应的最小代价为而相应的最小代价为注注 对对 的指派问题的指派问题,可以通过增加零行或零列来进行可以通过增加零行或零列来进行转化转化.思考思考 若若 且所有工作都必须完成且所有工作都必须完成,同时至多只有同时至多只有一个人完成其中的两项工作一个人完成其中的两项工作,该如何确定相应的指派方案该如何确定相应的指派方案?四、用四、用Lingo软件求解线性规划软件求解线性规划 在前面的讨论中我们看到在前面的讨论中我们看到,用手工算法求解一个线性规用手工算法求解一个线性规划问题划问题,即使算法再好即使算法再好,对一个大型的线性规划问题对一个大型的线性规划问题,也是也是相当困难的相当困难的.这里我们介绍一个借助软件来求解线性规划这里我们介绍一个借助软件来求解线性规划的方法的方法.1.用用Lingo软件求解线性规划问题软件求解线性规划问题 Lingo软件是由美国软件是由美国Lindo公司研制开发的公司研制开发的,用于求解线性用于求解线性规划和非线性规划的应用软件规划和非线性规划的应用软件.在在Lingo官方网站上可以得官方网站上可以得到相应的下载软件到相应的下载软件,目前的目前的11.0版本支持版本支持Vista平台平台.其特点其特点是书写简便是书写简便,使用灵活使用灵活.例例6 求解线性规划求解线性规划解解 启动启动Lingo,在主窗口中输入在主窗口中输入主窗口主窗口即即注意表达式注意表达式 执行执行Lingo菜单下的菜单下的Solve命令命令,得到问题的解得到问题的解 执行执行Lingo菜单下的菜单下的Solve命令命令,得到问题的解得到问题的解即问题的最优解为即问题的最优解为 最优解值为最优解值为结果分析结果分析:对于解对于解代入到约束代入到约束条件中条件中,此时条件此时条件1与条件与条件3正好取等式正好取等式,这样的约束条件称为紧约束这样的约束条件称为紧约束条件条件,一般相应的影子价格不为一般相应的影子价格不为0.而变量而变量的意义是的意义是该产品的价值不高该产品的价值不高,没必要投入生产没必要投入生产.例例7 求问题一的解求问题一的解 问题一的规划为问题一的规划为注意到问题中的变量应取整数注意到问题中的变量应取整数,故在程序中增加相应命令故在程序中增加相应命令.指定变量为整数型指定变量为整数型问题的解为问题的解为最优解值为最优解值为 在上面的例子中可以发现在上面的例子中可以发现,当变量较多时当变量较多时,这样的输入这样的输入比较繁琐比较繁琐,在在Lingo中可以通过设置变量来简化输入过程中可以通过设置变量来简化输入过程,我们以下面的简单例子来加以说明其用法我们以下面的简单例子来加以说明其用法.例例8 求解线性规划求解线性规划相应的求解程序为相应的求解程序为运行后得到问题的最优解运行后得到问题的最优解:例例 用用Lingo程序求解规划程序求解规划程序为程序为 说明说明 Set的使用的使用 Set命令是定义命令是定义Lingo中的初始集中的初始集,基本格式为基本格式为 Sets Setname/number_list:attributs_list;Endsets 例如下面命令定义了一个学生集：例如下面命令定义了一个学生集：Sets:Students/1.20/:Sex,Age;Endsets 模型中数据的定义模型中数据的定义 在在Lingo中中,通过命令通过命令Data来定义模型中的数据来定义模型中的数据.其基本其基本格式是格式是Data：Attribute=value_lists；Enddata 数值计算数值计算 在在Lingo中常用的数值计算函数有中常用的数值计算函数有:求和求和,最大值最大值,最小最小值值,求平均值等求平均值等.例如求和命令例如求和命令sum格式格式 sum(set(set_index_list)|condition_qualified:expr).其中其中condition_qualified是个可选参数是个可选参数.循环循环 Lingo中的基本循环命令是中的基本循环命令是for.格式格式 for(set(set_index_list)|condition_qualified:expr).例例9 求解求解01规划规划 解解 相应的相应的Lingo程序如下程序如下运行后得问题的最优解运行后得问题的最优解例例10 运输问题运输问题 有一连锁超市系统有一连锁超市系统,系统中系统中4个存储站和个存储站和10个门市部个门市部,仓仓储站的库存量为储站的库存量为196,187,179,176;10个门市部当前的需个门市部当前的需求量分别为求量分别为75,69,72,83,66,65,74,62,81,56,从仓储从仓储站到门市部的运输成本如下表站到门市部的运输成本如下表:4475568765478985754663875347694528567896787110987654321求相应的运输方案求相应的运输方案,使总运输成本为最小使总运输成本为最小.分析分析 以以 表示第表示第 个仓储站的库存量个仓储站的库存量,为为第第 个门市部的需求量个门市部的需求量,注意到注意到以以 表示第表示第 个仓储站到第个仓储站到第 个门市部的运输量个门市部的运输量.则模型为则模型为并且注意到并且注意到 为整数变量为整数变量.该规划共有该规划共有40个变量个变量,可以看到用手工算法是相当困难可以看到用手工算法是相当困难的的.在在Lingo下编制程序下编制程序:运行后得到问题的最优解为运行后得到问题的最优解为 最小成本为最小成本为 即相应的运输方案为下表即相应的运输方案为下表:56000045000754000021216572003000734400069020816200018000110987654321例例11 求解最小指派问题求解最小指派问题解解 指派问题的数学模型为指派问题的数学模型为相应程序如下相应程序如下:求解后得到问题的最优解求解后得到问题的最优解 最小成本为最小成本为 五、应五、应 用用 应用一应用一 资源分配资源分配 某公司安排职员的工作日程安排某公司安排职员的工作日程安排:一周中每天都需要一周中每天都需要一定数量的员工工作一定数量的员工工作,数量有差异数量有差异.每个员工一周连续工每个员工一周连续工作五天作五天,休息两天休息两天.公司对员工数量要求为下表公司对员工数量要求为下表:14周六周六19周五周五16周四周四15周三周三16周二周二18周一周一12周日周日所需员工数所需员工数时间时间试确定该公司每天应聘用的职员数试确定该公司每天应聘用的职员数.分析分析以以 表示在周表示在周 开始工作的人数开始工作的人数,则问题的目标则问题的目标函数为函数为约束条件为对每天员工数量的要求约束条件为对每天员工数量的要求,即对周一而言有即对周一而言有由此得到问题的数学模型由此得到问题的数学模型:在在Lingo中输入命令中输入命令 运行后得到问题的运行后得到问题的最优解为最优解为下面这段程序给出了用循环的方式的求解命令下面这段程序给出了用循环的方式的求解命令.应用二应用二 货运问题货运问题 问题的提出问题的提出要将要将7种规格的包装箱种规格的包装箱 装到两辆平装到两辆平8466978数量数量10002000400050010003000200064.052.048.772.061.352.048.7平板车上去平板车上去,包装箱的宽度和高度都相同包装箱的宽度和高度都相同,但厚度但厚度及重量及重量 不同不同.下表给出了相应的数据下表给出了相应的数据 每辆平板车有每辆平板车有 长的地方可以用来装箱（像面包长的地方可以用来装箱（像面包那样排列）那样排列）,载重为载重为 由于当地货运的限制由于当地货运的限制,对对 三类包装箱的总数有相应的约束三类包装箱的总数有相应的约束:所占的空间不得超过所占的空间不得超过试建立相应的数学模型试建立相应的数学模型,将这些箱装到平板车将这些箱装到平板车上上,并使浪费的空间为最小并使浪费的空间为最小.分析分析 所有货物的重量之和为所有货物的重量之和为 而两辆车的装哉能力为而两辆车的装哉能力为 故货物不能全部装车故货物不能全部装车,所以应选择一个合适的装运方案所以应选择一个合适的装运方案,使货尽可能地多装使货尽可能地多装,而且浪费的空间为最小而且浪费的空间为最小.问题的关键是确定各车的运输方案问题的关键是确定各车的运输方案.模型建立模型建立 记记 表示第表示第 辆车装运辆车装运 种箱的个数种箱的个数以以 表示表示 的厚度的厚度,则目标函数为则目标函数为 约束条件有约束条件有:对箱数的约束对箱数的约束 对重量的约束对重量的约束:厚度约束厚度约束:对对 的约束的约束:得到问题的最优解为得到问题的最优解为所占空间为所占空间为用用Lingo软件对该问题进行求解软件对该问题进行求解:问题的求解程序为问题的求解程序为最优解为最优解为注注 该问题的解不唯一该问题的解不唯一.应用三应用三 手术安排问题手术安排问题 某大医院向社会提供各种不同的医疗服务某大医院向社会提供各种不同的医疗服务,为获得最好的为获得最好的社会效益和经济效益社会效益和经济效益,医院必须优化其资源配置医院必须优化其资源配置.如果资如果资源配置不是最好的源配置不是最好的,则可能存在有的资源使用率低则可能存在有的资源使用率低,而有而有的资源使用过度的情况的资源使用过度的情况.以下面提供的外科手术数据为例以下面提供的外科手术数据为例,试建立一个能够帮助医院改善其资源配置试建立一个能够帮助医院改善其资源配置,提高效益的的提高效益的的数学模型数学模型.手术类型分为三类手术类型分为三类:简称为大手术（例如心脏搭桥手术）简称为大手术（例如心脏搭桥手术）,中手术（例如胃切除手术）和小手术（例如阑尾手术）中手术（例如胃切除手术）和小手术（例如阑尾手术）.每种手术所需的人数和费用如下表每种手术所需的人数和费用如下表:手术手术主刀医师主刀医师麻醉师麻醉师配合医师配合医师器械护士器械护士大大3112中中2111小小1101手术手术巡回护士巡回护士所需时间所需时间平均费用平均费用大大21天天3万万中中2半天半天1.6万万小小15个个/天天3千千资源数据表资源数据表 现在医院的人员基本情况如下现在医院的人员基本情况如下:高级医师高级医师21人人,普通医师普通医师44人人.只有高级医师才可以充当只有高级医师才可以充当1.假定各种外科手术的病人足够多假定各种外科手术的病人足够多,如何安排每天的日常如何安排每天的日常2.若做手术的病人分布不均若做手术的病人分布不均,如大手术并不常见如大手术并不常见,而小手术而小手术大大,中手术的主刀医师中手术的主刀医师.护士护士100人人,其中只有其中只有60人可以充人可以充当器械护士当器械护士,麻醉师麻醉师30人人.手术使得其经济效益最高手术使得其经济效益最高?则可能较多则可能较多,要求做小手术的病人在手术完成之前一直占要求做小手术的病人在手术完成之前一直占据着医院的床位据着医院的床位,如若床位有限如若床位有限,小手术要求一周内完成小手术要求一周内完成,3.充分考虑社会效益和经济效益充分考虑社会效益和经济效益,如何在原来的计划上作如何在原来的计划上作否则病人要求转院否则病人要求转院.问如何制定一个医院的每周手术安排问如何制定一个医院的每周手术安排计划计划?尽可能小的调整尽可能小的调整,满足急症病人的需要满足急症病人的需要.问题分析问题分析 在第一种情况下在第一种情况下,需要确定各种手术方案需要确定各种手术方案,目标是使得目标是使得 设设 是每天进行的大手术的人数是每天进行的大手术的人数,是每天进行的中手是每天进行的中手手术的人数手术的人数,（为使问题简单（为使问题简单,是实际进行中是实际进行中手术的人数手术的人数,）是进行小手术的人数是进行小手术的人数.则目标函数为则目标函数为相应的收益达到最大相应的收益达到最大,而并不考虑实际情况而并不考虑实际情况.因问题假设因问题假设是有足够多的病人可供选择是有足够多的病人可供选择.再考虑资源的要求再考虑资源的要求:高级医师高级医师:假设小手术中由高级医师主刀的有假设小手术中由高级医师主刀的有 个个,而有普通医师而有普通医师主刀的有主刀的有 个个,普通医师普通医师:麻醉师麻醉师:器械护士器械护士:护士总需要护士总需要:另外另外,所有的所有的 都必须取正整数都必须取正整数.由此得到相应的数学模由此得到相应的数学模型为型为为非负整数为非负整数.由由Lingo程序程序,得到该问题的解得到该问题的解总收益为总收益为 单位单位:万元万元.结果分析结果分析:在这样的安排下在这样的安排下,大手术没有安排（想一下原大手术没有安排（想一下原因是什么因是什么?）高级医师进行的都是中手术高级医师进行的都是中手术.中手术一共完中手术一共完成了成了20个个.小手术安排了小手术安排了100个个,均是由普通医师主刀的均是由普通医师主刀的.此时医师的使用情况是此时医师的使用情况是:高级医师高级医师20,普通医师普通医师30,麻醉师麻醉师30.器械护士器械护士30,巡回护士巡回护士40.2.在第在第1种情况下种情况下,没有安排大手术没有安排大手术,这显然不合理这显然不合理.由于由于大手术并不多见大手术并不多见,故可以考虑在周末安排一到两个大手术故可以考虑在周末安排一到两个大手术.如果尽安排一个大手术的情况下如果尽安排一个大手术的情况下,相应问题的解为相应问题的解为:总收益为总收益为 单位单位:万元万元.对小手术的安排对小手术的安排,不妨可以规定不妨可以规定:在需要进行小手术的在需要进行小手术的病人住院后病人住院后,5天内一定要安排手术天内一定要安排手术.对结果的分析对结果的分析,可以发现可以发现,开刀医生资源并没有充分利开刀医生资源并没有充分利用用.造成这一现象的关键原因是麻醉师不够（当然还得考造成这一现象的关键原因是麻醉师不够（当然还得考虑病区内有值班医师和护士的存在）虑病区内有值班医师和护士的存在）.但如果从增加效益但如果从增加效益的角度来说的角度来说,提高社会效益和医院效益的一个方法是增加提高社会效益和医院效益的一个方法是增加法是增加麻醉师法是增加麻醉师.例如当把麻醉师的数量从例如当把麻醉师的数量从30增加到增加到35人人时时,相应问题的解为相应问题的解为总收益为总收益为 单位单位:万元万元.不断改变麻醉师的数量不断改变麻醉师的数量,可以发现当麻醉师数量上升到可以发现当麻醉师数量上升到45总收益为总收益为 单位单位:万元万元.人时人时,解不再变化解不再变化.问题的解为问题的解为六、用六、用MatLab求解线性规划求解线性规划 设线性规划为设线性规划为 基本格式基本格式例例 求解规划求解规划解解 将问题转化为相应的标准形式将问题转化为相应的标准形式,则有则有此时此时输入语句输入语句结果为结果为即原问题的最优解为即原问题的最优解为不能省略不能省略!也可以简写成也可以简写成例例 求解规划求解规划解解 输入下面语句输入下面语句运行结果为运行结果为例例 求解线性规划求解线性规划解解 输入下面语句输入下面语句运行结果为运行结果为七、非线性规划七、非线性规划 在上面诸节中讨论了线性规划和几类特殊的线性规划在上面诸节中讨论了线性规划和几类特殊的线性规划整数规划及整数规划及01规划和相应的解法规划和相应的解法.所谓线性规划实际上所谓线性规划实际上是指数学规划中的目标函数及约束条件表达式均为线性关是指数学规划中的目标函数及约束条件表达式均为线性关系系.但实际问题中所对应的数学规划其表达式很可能不是线但实际问题中所对应的数学规划其表达式很可能不是线性关系式性关系式.在微积分课程中我们大量遇到该类问题在微积分课程中我们大量遇到该类问题.首先我首先我们看两个简单例子们看两个简单例子.例例12 将边长为的正三角形剪去三个全等的四边形（如图将边长为的正三角形剪去三个全等的四边形（如图所示）所示）,然后将其折起然后将其折起,做成一个无盖的正三棱柱做成一个无盖的正三棱柱,当图中当图中的的 取何值时取何值时,该盒子的容积为最大该盒子的容积为最大 解解 盒子的高为盒子的高为 底面面积为底面面积为故相应的体积为故相应的体积为求导后并令其为零求导后并令其为零,得得所以所以再注意到再注意到,即函数在该点取极大值即函数在该点取极大值,又因驻点唯一又因驻点唯一,故该点一定是最大故该点一定是最大值点值点.该模型是个非线性规划，一般称为该模型是个非线性规划，一般称为无约束的优化问题无约束的优化问题.例例13 某工厂要用铁板做成一个体积为某工厂要用铁板做成一个体积为2的有盖长方体水箱的有盖长方体水箱.问当长问当长,宽宽,高各取多少时高各取多少时,所使用的原料最省？所使用的原料最省？设长方体的三边长分别为设长方体的三边长分别为则水箱的表面积则水箱的表面积为为此为问题的目标函数此为问题的目标函数.而相应的约束条件为而相应的约束条件为由此得到问题的数学模型为由此得到问题的数学模型为 这样的问题称为这样的问题称为有约束的最优化问题有约束的最优化问题.一个标准的无约束的优化问题可以写成一个标准的无约束的优化问题可以写成而有约束的优化问题可以写成而有约束的优化问题可以写成 问题问题 砂石运输问题砂石运输问题.设有设有 立方米的砂立方米的砂,石要由甲地运到乙地石要由甲地运到乙地,运输前需先运输前需先装入一个有底无盖并在底部装有滑行器的木箱中装入一个有底无盖并在底部装有滑行器的木箱中.砂石运砂石运到乙地后到乙地后,从箱中倒出从箱中倒出,在继续用空箱装运在继续用空箱装运.不论箱子大小不论箱子大小,每装运一箱每装运一箱,需需0.1元元,箱底和两端的材料费为箱底和两端的材料费为20元元/米米2,箱箱子两侧的材料费为子两侧的材料费为5元元/米米2,箱底的两个滑行器与箱子同长箱底的两个滑行器与箱子同长,材料费为材料费为2.5元元/米米.问木箱的长宽高各为多少米问木箱的长宽高各为多少米,才能使运费才能使运费与箱子的成本费的总和为最小与箱子的成本费的总和为最小.建模建模 设木箱的长宽高分别为设木箱的长宽高分别为 运费与成本费的总运费与成本费的总和为和为 则目标函数为则目标函数为 若在上述问题中若在上述问题中,箱子的底与两侧使用废料来做箱子的底与两侧使用废料来做,而废而废废料只有废料只有4平方米平方米,则问题为则问题为:在上面问题中在上面问题中,目标函数与约束条件中的每一项可表达目标函数与约束条件中的每一项可表达成成 的形式（其中的的形式（其中的 为整数）为整数）,数学上将其成为广义多项式数学上将其成为广义多项式,相应的规划称为几何规划相应的规划称为几何规划.当系数为正数时当系数为正数时,规划称为正项几何规划规划称为正项几何规划.非线性规划解法非线性规划解法例例1 求解非线性规划求解非线性规划解解1 图解法图解法最优解为最优解为解解2 用用Lingo软件求解软件求解最优解为最优解为 无约束非线性规划解法简介无约束非线性规划解法简介 无约束非线性规划一般可写成无约束非线性规划一般可写成其中其中 解法解法 1.求求 的梯度的梯度 2.令梯度令梯度 解出解出 的驻点的驻点3.验证验证 在该点的在该点的Hessian矩阵是否为正（负）定的矩阵是否为正（负）定的,若成立若成立,则该点为函数的极小（大）值点则该点为函数的极小（大）值点.例例 求函数求函数 的极小点的极小点.解解 的梯度为的梯度为令令 则驻点为则驻点为 函数的函数的Hessian阵为阵为注意到该矩阵为正定阵注意到该矩阵为正定阵,因而该点为极小值点因而该点为极小值点.注意到此方法只有对一些特殊的函数才有效注意到此方法只有对一些特殊的函数才有效.一般情况一般情况1.给出给出 的极小点的极小点 的一个初始估计值的一个初始估计值 称为初始称为初始2.如果如果 已求得已求得,并且不是极小点并且不是极小点,设法选取一个方向设法选取一个方向（该方向称为搜索方向）（该方向称为搜索方向）,使目标函数使目标函数 沿该方沿该方下下,要求出函数的驻点是比较困难的要求出函数的驻点是比较困难的.下面我们简单介绍下面我们简单介绍求解该类问题的数值解法求解该类问题的数值解法.点点;向是下降的（一般取梯度方向的反方向）向是下降的（一般取梯度方向的反方向）;3.在射线在射线 取适当的步长取适当的步长,使使 由此确定点由此确定点 其中的其中的 一般取使得一般取使得4.检验检验 是否为函数是否为函数 的极小值的极小值,或者满足或者满足上式取到极小值的值上式取到极小值的值;精度的要求精度的要求,若不是若不是,再回到第二步再回到第二步.用用MatLab求解非线性规划求解非线性规划 求解二次规划求解二次规划 二次规划的一般形式二次规划的一般形式 基本格式基本格式:例例 求解二次规划求解二次规划:求解程序如下求解程序如下:非线性规划求解非线性规划求解 非线性规划的一般形式非线性规划的一般形式:基本格式基本格式:例例 求解优化问题求解优化问题求解程序如下求解程序如下:应用应用 某公司欲以每件两元的价格购进一批商品某公司欲以每件两元的价格购进一批商品,然后再出售然后再出售.一般说来一般说来,随着商品售价的提高随着商品售价的提高,预期销售量将减少预期销售量将减少,并对并对此进行了估算此进行了估算,结果如下表结果如下表:公司打算做广告公司打算做广告,投入一定费用后投入一定费用后,销售量将有一定增销售量将有一定增长长,由销售增量因子来表示由销售增量因子来表示.据统计据统计,广告费用与销售量广告费用与销售量增长因子也由下表提供增长因子也由下表提供.问公司该采取怎样的经营决策问公司该采取怎样的经营决策,使预期利润最大使预期利润最大?1.81.952.0因子因子765广告费广告费2.02.22.52.8预期预期6.05.55.04.5售价售价1.951.851.71.41.0因子因子43210广告费广告费2.93.23.43.84.1预期预期4.03.53.02.52.0售价售价 模型建立模型建立 以以 分别表示售价分别表示售价,预期销售量预期销售量,广告费广告费,表示表示在投入广告费后在投入广告费后,实际销售量销售的增长因子实际销售量销售的增长因子.为建立模型为建立模型,先画出相应的散点图先画出相应的散点图:销售价与销售量关系图销售价与销售量关系图广告费与增长因子关系图广告费与增长因子关系图 散点图表面散点图表面,销售价格与销售量几乎是线性关系销售价格与销售量几乎是线性关系,而广而广告投入与增长因子近似为抛物线关系告投入与增长因子近似为抛物线关系.为得到系数为得到系数,用最小用最小二乘法作曲线拟合二乘法作曲线拟合,得到多项式系数得到多项式系数.建立曲线拟合建立曲线拟合 由此得到优化模型为由此得到优化模型为求解程序如下求解程序如下:相应的拟合曲线对比图为相应的拟合曲线对比图为销售价与销售量关系图销售价与销售量关系图广告费与增长因子关系图广告费与增长因子关系图 最优解为最优解为:八、用八、用Lingo程序求解数学规划举例程序求解数学规划举例例例 求解线性规划求解线性规划在在Lingo主窗口中输入语句主窗口中输入语句:运行后的结果为运行后的结果为:经济意义经济意义 灵敏度分析灵敏度分析按下面要求进行设置按下面要求进行设置:选该项选该项再进行相应操作再进行相应操作.灵敏度分析报告灵敏度分析报告:例例 一个投资者拟选择一个投资者拟选择 三个业绩好的股票进行长三个业绩好的股票进行长期投资期投资.通过对这三个股票的市场分析和统计预测到相关通过对这三个股票的市场分析和统计预测到相关数据如下表数据如下表:140-3011041-3012036641103618092五年期的协方差五年期的协方差五年期望五年期望收益率收益率/%股票名称股票名称 从两个方面给出相应的投资方案从两个方面给出相应的投资方案:将投资组合中的股票收益率的标准差降到最小将投资组合中的股票收益率的标准差降到最小,以降低以降低投资风险投资风险;并希望期望收益率不少于并希望期望收益率不少于 希望在标准差不超过希望在标准差不超过 的情况下的情况下,获得最大的收益获得最大的收益.建模建模 以以分别表示对这三个股票的投资比例分别表示对这三个股票的投资比例,其五年期的期望收益率分别记为其五年期的期望收益率分别记为则五年后的总则五年后的总收益率为收益率为由方差性质得由方差性质得再由已知条件再由已知条件,得到投资组合的标准差为得到投资组合的标准差为由此得到由此得到:问题问题对应的模型为对应的模型为相应的约束条件为相应的约束条件为问题问题的模型为的模型为相应的约束条件为相应的约束条件为由由Lingo程序可以得到问题的解程序可以得到问题的解:运行后得到问题的解如下运行后得到问题的解如下:相应的标准差为相应的标准差为问题问题的求解程序为的求解程序为运行后得到问题的解如下运行后得到问题的解如下:最优值为最优值为END