[经济学]第一章线性规划.ppt

第一章 线性规划及单纯形法 ? 线性规划及其数学模型 ? LP问题的标准型 ? LP问题的解 ? 单纯形法 ? 单纯形法的进一步讨论 ? 关于解的讨论 1.数学规划(最优化问题) 数学规划是应用数学的一门重要学科，其主要研究如何有效地利用有限资源，分配合理生产任务或是选择最佳生产布置及恰当安排调运方案等，以期求得最佳经济效果的问题。 (1) 数学规划研究的对象 (2) 数学规划的数学语言描述 数学规划是研究在所给定的条件下，如何求所得实函数的极（最）大（max）或极（最）小（min），故有时亦称此类问题为最优化问题。 ? 线性规划及其数学模型 2. 数学规划的一般数学模型 (MP) 或 其中： 称为约束条件，其中用等式表示的称为等式约束，用不等式表示的称为不等式约束。 n 元实函数，称为目标函数（或评价函数） 3. 数学规划问题的分类 无约束最优化 有约束最优化 线性规划 非线性规划 最优化问题 4. 几个相关概念 可行解 在（MP）中满足所有约束条件的解； 可行域 由所有的可行解组成的集合； 即：G={x|gi(x)?0, i=1,2,?,m} 最优解 (MP)中使得目标函数取得最大（或最小）的可行解x*，称为最优点，而称f(x*)为最优值；称{x*,f(x*)}为最优解。 注：数学规划中的可行域可能是有限区域，也可能是无限区域。 例1 设某工厂生产A和B两种产品，产量分别为x和y（单位：千件），利润函数为： 已知生产这两种产品时，每件产品均需消耗原材料2000公斤，现有该原料12000公斤，问两种产品各生产多少千件时，总利润最大？ 6 6 x y 则（2，3）及（0，0）都是可行解； （2，-3）及（2，5）均不是可行解； {(x,y)|x+y?6,x?0,y?0}为可行域 5. 线性规划及线性规划模型 例2（利润问题）某厂生产n种产品,每种产品均需m道工序(具体数据如下表),且 (1) 引例 cn ? c2 c1 单位产品利润 bm amn ? am2 am1 m ? ? ? ? ? ? b2 a2n ? a22 a21 2 b1 a1n ? a12 a11 1 每月最多工时 n ? 2 1 工时 产品 工序 （1）第 j 种单位产品在第 i 道工序上所需工时为aij （2）第 j 种单位产品利润为cj （3）由于设备限制,每月第 i 道工序最多可提供bi 工时 试问：如何组织生产，可使每月工厂所获利润最大？ 解 设第 j 种产品的月产量为 xj 则 s.t 若记 则有 可记作 X称为决策变元（或系统变元）；C为价格系数；aij为技术系数；b为资源限度（或资源限制、资源系数）。 例3 (2) 线性规划及其一般模型 目标函数和约束条件都是线性的数学规划称为线性规划，简记LP(Linear Programming)。一般模型为： 6. 线性规划的几何解法 对于变元个数不多于3的LP可用几何解法.因为其 例4 用几何解法解下面LP问题 （1）建立直角坐标系，描述系统约束中（1）～（4）为等式时的直线； （2）依据不等号约束方向，确定（1）～（4）的范围，结合（5）找出其公共部分及可行域D; （3）令2x1+3x2=k,绘出等值线（等值线上的点的目标值均为k； 2x1+3x2=0 （4）显然2x1+3x2=k为与2x1+3x2=0平行的直线族，且沿右上方向移动时k值增大，当移到过点Q时达到最大，即为最优点。 可行域能在平面和三维坐标系中描画出,故较容易观察出最优点的位置. 1. LP问题的标准型及其化法 V: max z=CX s.t AX=b X≥0 (LP) 说明 （1）目标函数一定是求极大； 对于求极小的问题可通过负变换max(-z)将minz转换成求极大问题（注意求得最优值后，请务必变回原来的符号）。 （2） b≥0； 对于资源系数小于零的bi可通过在约束条件的两端同乘负号(注意不等式变向）来实现。 ? LP问题的标准型 （3）系统约束均为等式 对于 的约束可通过加松弛变元xn+k化为等式约束 ；对于 xn+k化为等式约束 的约束可通过减松弛变元 2. 化LP问题为标准型的一般步骤 （1）规范目标函数（使之变为极大化）； （2）规范资源限制(使b≥0)； （3）变系统约束为等