线性规划及其基本理论课件

运筹学Operationsresearch陈志松Mob筹学1线性规划及其基本理论口线性规划概述口线性规划问题口线性规划数学模型般模型标准模型口线性规划解的概念可行解、最优解基阵、基解、基可行解口线性规划的基本性质线性规划及其基本理论2线性规划概述口线性规划(LinearProgramming,简记为LP)是运筹学中的一个最重要、应用最广泛的分支。口线性规划及其通用解法-单纯形法一般认为是美国学者丹捷格(GDantzig)在1947年研究美国空军军事规划时提出的口苏联学者康托洛维奇在1939年解决工业生产组织与计划问题时就提出类似线性规划的模型及解法;康托洛维奇的工作当时没有被重视,但直到1960年康托洛维奇再次发表《最佳资源利用的经济计算》一书后,才受到重视些常见的带有Spreadsheet的软件,如:Excel、Lotus1-2-3等,均有内置的线性规划求解功能最优化问题求解软件,如:Lindo、Lingo、Matlab等。线性规划概述3线性规划问题提出在生产管理和经营活动中经常会提出这样一类问题:如何利用有限的人力、物力、财力等资源,取得最好的效果。例如:口配载问题交通工具,运输几种不同体积、重量的物资,如何装配所运的物资最多?口下料问题用圆钢制造长度不等的机轴,如何下料,所剩的余料最少?口生产计划问题企业生产A、B两种电器产品,两种产品的市场需求状况可以确定,按当前的定价可确保所有产品均能销售出去企业可提供的两种原材料和劳动时间的数量是有限的。产品A与产品B各应生产多少,可使企业总利润最大?线性规划问题提出4线性规划问题提出上述这些问题有如下共同特点:□问题解决要满足一定条件,称为约束条件;口问题有多个满足条件的解决方案;口问题解决有明确的目标要求,对应不同方案有不同目标值,可表示成目标函数线性规划问题提出5何谓线性规划问题口最优化问题我们称如下一般问题:“在一定约束条件下,求目标函数的最大或最小值”为最优化问题,用数学模型描述的最优化问题,称为数学规划问题口线性规划问题在最优化问题中,如果约束条件与目标函数均是线性的,我们就称之为线性规划问题。何谓线性规划问题6线性规划问题的三个要素口决策变量决策问题待定的量值称为决策变量决策变量的取值有时要求非负。口约束条件任何问题都是限定在一定的条件下求解,把各种限制条件表示为一组等式或不等式,称之为约束条件。■约束条件是决策方案可行的保障LP的约束条件,都是决策变量的线性函数目标函数衡量决策方案优劣的准则,如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。■有的目标要实现极大,有的则要求极小线性规划问题的三个要素7线性规划数学模型例生产计划问题某厂生产甲乙两种产品,各自的零部件分别在A、B车间生产,最后都需在c车间装配,相关数据如表所示:产品工时单耗生产能力车间乙ABc甲1333822451236单位产品获利问如何安排甲、乙两产品的产量,使利润为最大线性规划数学模型8线性规划数学模型口建立数学模型的步骤:Step1分析实际问题;Step2确定决策变量;Step3找出约束条件;Step4确定目标函数;Step5整理、写出数学模型。线性规划数学模型9线性规划问题举例例1.1】某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建,各体系资源用量及今年供应量见下表:资源造价钢材水泥砖人工住宅体系〔元/m2)(公斤/m2)(公斤/m)(块/m2)(工日/m2)砖混住宅105121102104.5壁板住宅135301903.0大模住宅120251803.5资源限量11000020000|1500001470004000(千元)(吨)(吨)(千块)(千工日要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2),求建造方案。线性规划问题举例10线性规划及其基本理论课件11线性规划及其基本理论课件12线性规划及其基本理论课件13线性规划及其基本理论课件14线性规划及其基本理论课件15线性规划及其基本理论课件16线性规划及其基本理论课件17线性规划及其基本理论课件18线性规划及其基本理论课件19线性规划及其基本理论课件20线性规划及其基本理论课件21线性规划及其基本理论课件22线性规划及其基本理论课件23线性规划及其基本理论课件24线性规划及其基本理论课件25线性规划及其基本理论课件26线性规划及其基本理论课件27线性规划及其基本理论课件28线性规划及其基本理论课件29线性规划及其基本理论课件30线性规划及其基本理论课件31线性规划及其基本理论课件32线性规划及其基本理论课件33线性规划及其基本理论课件34线性规划及其基本理论课件35线性规划及其基本理论课件36线性规划及其基本理论课件37线性规划及其基本理论课件38线性规划及其基本理论课件39线性规划及其基本理论课件40线性规划及其基本理论课件41线性规划及其基本理论课件42线性规划及其基本理论课件43线性规划及其基本理论课件44运筹学Operationsresearch陈志松Mob筹学45线性规划及其基本理论口线性规划概述口线性规划问题口线性规划数学模型般模型标准模型口线性规划解的概念可行解、最优解基阵、基解、基可行解口线性规划的基本性质线性规划及其基本理论46线性规划概述口线性规划(LinearProgramming,简记为LP)是运筹学中的一个最重要、应用最广泛的分支。口线性规划及其通用解法-单纯形法一般认为是美国学者丹捷格(GDantzig)在1947年研究美国空军军事规划时提出的口苏联学者康托洛维奇在1939年解决工业生产组织与计划问题时就提出类似线性规划的模型及解法;康托洛维奇的工作当时没有被重视,但直到1960年康托洛维奇再次发表《最佳资源利用的经济计算》一书后,才受到重视些常见的带有Spreadsheet的软件,如:Excel、Lotus1-2-3等,均有内置的线性规划求解功能最优化问题求解软件,如:Lindo、Lingo、Matlab等。线性规划概述47线性规划问题提出在生产管理和经营活动中经常会提出这样一类问题:如何利用有限的人力、物力、财力等资源,取得最好的效果。例如:口配载问题交通工具,运输几种不同体积、重量的物资,如何装配所运的物资最多?口下料问题用圆钢制造长度不等的机轴,如何下料,所剩的余料最少?口生产计划问题企业生产A、B两种电器产品,两种产品的市场需求状况可以确定,按当前的定价可确保所有产品均能销售出去企业可提供的两种原材料和劳动时间的数量是有限的。产品A与产品B各应生产多少,可使企业总利润最大?线性规划问题提出48线性规划问题提出上述这些问题有如下共同特点:□问题解决要满足一定条件,称为约束条件;口问题有多个满足条件的解决方案;口问题解决有明确的目标要求,对应不同方案有不同目标值,可表示成目标函数线性规划问题提出49何谓线性规划问题口最优化问题我们称如下一般问题:“在一定约束条件下,求目标函数的最大或最小值”为最优化问题,用数学模型描述的最优化问题,称为数学规划问题口线性规划问题在最优化问题中,如果约束条件与目标函数均是线性的,我们就称之为线性规划问题。何谓线性规划问题50线性规划问题的三个要素口决策变量决策问题待定的量值称为决策变量决策变量的取值有时要求非负。口约束条件任何问题都是限定在一定的条件下求解,把各种限制条件表示为一组等式或不等式,称之为约束条件。■约束条件是决策方案可行的保障LP的约束条件,都是决策变量的线性函数目标函数衡量决策方案优劣的准则,如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。■有的目标要实现极大,有的则要求极小线性规划问题的三个要素51线性规划数学模型例生产计划问题某厂生产甲乙两种产品,各自的零部件分别在A、B车间生产,最后都需在c车间装配,相关数据如表所示:产品工时单耗生产能力车间乙ABc甲1333822451236单位产品获利问如何安排甲、乙两产品的产量,使利润为最大线性规划数学模型52线性规划数学模型口建立数学模型的步骤:Step1分析实际问题;Step2确定决策变量;Step3找出约束条件;Step4确定目标函数;Step5整理、写出数学模型。线性规划数学模型53线性规划问题举例例1.1】某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建,各体系资源用量及今年供应量见下表:资源造价钢材水泥砖人工住宅体系〔元/m2)(公斤/m2)(公斤/m)(块/m2)(工日/m2)砖混住宅105121102104.5壁板住宅135301903.0大模住宅120251803.5资源限量11000020000|1500001470004000(千元)(吨)(吨)(千块)(千工日要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2),求建造方案。线性规划问题举例54线性规划及其基本理论课件55线性规划及其基本理论课件56线性规划及其基本理论课件57线性规划及其基本理论课件58线性规划及其基本理论课件59线性规划及其基本理论课件60线性规划及其基本理论课件61线性规划及其基本理论课件62线性规划及其基本理论课件63线性规划及其基本理论课件64线性规划及其基本理论课件65线性规划及其基本理论课件66线性规划及其基本理论课件67线性规划及其基本理论课件68线性规划及其基本理论课件69线性规划及其基本理论课件70线性规划及其基本理论课件71线性规划及其基本理论课件72线性规划及其基本理论课件73线性规划及其基本理论