数学规划公开课.ppt

第二章 数学规划模型 ; 数学规划模型的一般表达式： 为目标函数， 为约束函数， 为可控变量， 为已知参数， 为随机参数。 数学规划分为线性规划、非线性规划、动态规划、 随机规划、整数规划、分式规划、几何规划、目标规划、平衡规划、参数规划、多目标规划等十几种。当然这么多规划其中亦有交叉。又可经过组产生新的规划，每一种规划有专著问世。 ;第一节 线性规划模型; 就模型而言，线形规划模型类似于高等数学中的条件极值问题，只是其目标函数和约束条件都限定为线性函数。线性规划模型的求解方法目前仍以单纯形法为主要方法。本节将介绍的主要内容：线性规划模型的建立及标准形式；线性规划模型的解和单纯形法；整数线性规划模型及建模案例等。; ;建模过程： 设甲、乙两种产品计划生产量分别为 和 （件），总的利润为 （元）。那么我们的任务就是：求变量的值为多少时，才能使总利润 最大，由已知条件， ， 要受下列限制： (1)生产甲、乙两种产品所用钢材的总数不能超过现有钢材数，即 (2)生产甲、乙两种产品所用铜材的总数不能超过现有铜材数，即 (3)生产两种产品所用的设备能力的总数不能超过现有设备能力的台时数，即 ;表2—2;用 表示生产第 种产品计划数，则问题归结为如下数学问题（数学模型）： 约束条件的意义是：每种原料生产n种产品所需要的资源总量不能超过该种资源的库存量；每种产品的生产计划数不能为负。 ;例2.3 运输问题 设某类物资有 个产地， 个销售地. 第 个产地的产量为 ,第 个销售地的需要量为 .从产地 到销售地 运输单位物资的运价（单价）为 .今考虑在产销平衡（即 )的条件下，应如何 组织运输，才能使得即满足各地的需要，又使总运费最小。 ;表2; 建模过程: 用 ???示产地 供给销地 的物资数量，则问题变成在产销平衡条件下，求解以下数学问题（模型）： 考察上述几个问题的数学模型，他们的目标函数及约束函数都是自变量的线性函数，故称这类数学问题为线性规划问题。;类似的问题很多，诸如下料问题、配料问题、分配问题、工厂选址问题等等。它们的解决都是归结上述的线性规划问题，只是约束条件有的是等式，有的是不等式。 通过以上两例可以看出：尽管所提问题的内容不同，但从构成数学问题的结构来看，却属于同一类优化问题，其结构具有如下特征： （1）目标函数是决策变量的线性函数。 （2）约束条件都是决策变量的线性等式或不等式。; 二、线性规划的解法概述、解的性质及单纯形法 我们称如下的条件极值问题 为标准的线性规划问题。; 若引进记号 则（LP）可简单地表示为 进一步，若令 ，则（LP）可表示为： ; 对于非标准形式的线性规划，可通过下列办法化成标准形式。 ①若求 ,可化为求 . ②若约束条件中含有不等式 或 则可引进新变量 （称为松弛变量），化为等式约束： 或 ③今后总假定 ，否则在等式两边乘以-1即可。 ④若变量 无非负限制，则引入两个非负变量 与