第五章 线性规划及其应用.ppt

例3 运输问题 某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？ 第三节 线性规划模型的单纯形法 一．用换元迭代法解线性规划问题 这种方法的过程的几何意义为：从凸多边形（或多面体）线性规划问题解的一个顶点（可行基）经换基迭代转变到另一顶点（可行基），最终达到最优顶点，这就是线性规划问题解的换元迭代法，它奠定了矩阵形式的单纯形方法的基础。 二．单纯形方法的理论基础 三. 换基迭代求最优解的过程 例5 求解下列线性规划问题 第五节 求解线性规划的计算软件 一． 用LINDO软件解线性规划 LINDO是“Linear interactive and discrete optimizer”的缩写，它是解决线性规划，整数规划等规划问题的有力工具，在大型计算机上，它可用于解决50000个约束条件，200000个变量的线性规划问题。 安装好LINDO软件后，在桌面上双击LINDO图标，得一个空白图框，然后在空白图框内输入求解问题，如 二． 用MATLAB优化工具箱解线性规划 MATLAB是Matrix Laboratory（矩阵实验室）的缩写。它早期是线性代数课的教学软件，后来逐步应用于实际工程问题的计算，目前已成为工程界和应用数学人员常用的数学软件之一。MATLAB是一种交互式的高级计算机软件，有如下特点： 它以矩阵运算为基本运算，用命令式语句运行，附有数值计算，最优化，信号处理，系统识别，控制系统等几十个工具箱（Toolbox）； MATLAB使用十分方便，几乎是直接把算式键入计算机，立刻得出计算结果，因此有“电子草稿纸”的美誉； 具有很强的图形表现能力。 结果： x= 15.0000 5.0000 10.0000 Z= 25.0000 近三十年来，约束优化方法有了很大的发展，求解方法大 体上可分为以下几类： 利用问题的最优性条件来求解的方法（如例题6.9中用的方法）。 用线性规划或二次规划来逐次逼近非线性优化问题的方法，例如线性逼近法（SLP法）、二次逼近法（序列二次规划法，简记为SQP法）等。 把约束非线性规划问题转化为一个或一系列无约束非线性规划问题来求解的方法，例如惩罚函数法（也叫SUMT外点法）、碰壁函数法（也叫SUMT内点法）、混合罚函数法、精确罚函数法和乘子法等。 对约束非线性规划问题不预先进行转换，直接进行处理的分析方法，如可行方向法、梯度投影法、既约梯度法、广义既约梯度法（GRG法）、凸单纯形法等。 对约束非线性规划问题不预先作转换的直接求解方法，如随机试验法等。 数值试验和应用实践证实：20世纪70年代以来出现的一些新方法，如乘子法、精确罚函数法、GRG法和SQP法是比较有效的求解方法，它们已经研制成了计算软件，并在实际中得到了成功的应用。 2、增加新约束的灵敏度分析 Final tableau (Total iteration=3) 35.333 0 -0.167 0 -1.170 0 0 0 0 0 0 0 C(j)-Z(j) *Big M 0 0 3.333 7.333 2.000 -0.833 -0.333 0.500 0.167 0.667 -0.500 1.000 0 0 0 0 1.000 0 1.000 0 0 3.000 4.000 S1 X1 X2 A(i,j) 0 0 0 3.000 4.000 B(i) B(i) S3 S2 S1 X2 X1 C(j) Basis 练习1：一家企业制造三种产品，需三种资源，技术服务、劳力、行政管理，下表列出了三种产品每单位数量对每种资源的需要量 4 6 10 单位利润 300 6 2 2 行政管理 600 5 4 10 劳力 100 1 1 1 技术服务 资源限量 C B A 产品 （1）问如何安排生产，可使利润最大？ （2）C产品的单位利润为多少时才值得生产？ （3）若劳力资源增加到800小时，问最优计划是否要改变，若要改变，应如何改变？ （4）制造部门提出要生产一种产品，需要技术服务1小时、劳力4小时、行政管理3小时，问其单位利润为多少方可否投产？ （5）若有一种原材料，如今受到限制，限制条件为 ，问最优计划是否受到影响？ 0 0 8/3 10/3 2/3 0 2200/3 Z 0 1 5/6 5/3 -1/6 0 1