第二部分 最优化.ppt

第二部分 最优化第2章 线性规划问题 2.3 求解线性规划的图解法 首先绘出可行域，然后绘制目标函数等值线。 Z=10x1+5x2 是一直线，不同等值线具有相同的斜率。 （1）改变约束条件 （2）改变约束条件 （3）改变目标函数 小结 线性规划问题可能出现四种情况：1）没有解，2）无界解，3）唯一解，4）无穷解。 图形法的优点是简单直观，但有很大局限性，它只适合于含有两个决策变量的线性规划问题。 2.4求解线性规划问题的单纯形法 用单纯形法求解线性规则问题的方法如下： (1) 求一个初始基本可行解； (2) 从基本可行解出发 转移到另一个目标函数值更小的基本可行解； (3) 逐步迭代计算, 当目标函数值不再减小, 即满足最优性条 件 时, 计算结束得到最优基本可行解。 例子 (1) 先将原问题化为标准形 (2) 为标准形找出一个基本可行解 原则：在约束方程系数矩阵中寻找m个线性独立的单位向量，m个单位向量可作为一个初始可行基。 例子 1) 转化为标准型 2) 找出一个基本可行解 3)建立单纯形表 初等行变换 ≥0满足最优解条件 约束方程的系数矩阵 * 例 1：某化工厂三种原料R1,R2,R3生产两种产品Q1,Q2。生产每公斤产品所需要的各单位原料量，工厂每天所拥有的各资源最大量及每公斤产品所获得的销售利润见下表，问每天应生产多少公斤Q1,Q2产品，才能利润最大？ 例2 ：某有色金属冶炼厂混合5种合金，制成一种含铅30%，含锌20%，含锡50%的新合金。问如何混合生产费用最小？ 例3：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。试计算工厂应如何安排生产可获得最大的总利润？ 综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型： 约束条件s.t. 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值。 2.1 线性规划问题的数学描述 线性规划是求一组非负变量。这些变量在满足一定的线性约束条件下，使一个线性函数达到极小或极大。即： 为了便于求解，通常要把上述线性规划问题的一般模型转化成下面的标准形式： (iii) 将自由变量化为非负变量 在线性规划的数学模型中， 若变量xk 没有非负的限制 则称xk 为自由变量。通过变换 可将一个自由变量化为两个非负变量；或者设法在约束条件和目标函数中消去自由变量。 例 4：将以下线性规划问题转化为标准形式。 2.2 线性规划模型的解 线性规划问题的标准数学模型也可以写成如下矩阵形式： 对于上述线性规划问题， 如果满足式 （4-15）， 则称为问题的可行解，全部可行解组成问题的可行域。 如果可行解满足式(4-14)， 则此可行解称为问题的最优解。 将矩阵 A看成由n 个列向量组成， 即 设 A的秩为m ( m ≤ n)，从 A的n 列中选出m个线性无关的列组成一个m阶矩阵。 假设选择的是前 m列，用B 表示这个矩阵。 B 称为问题的一个基， 它由m列线性无关的列向量组成。 与 B 对应的XB 的分量称为基本变量； 与 N 对应的XN 的分量称为非基本变量。由于 B 线性无关， 故有 即基变量XB可用非基变量XN线性表示。 可以改写成 若令XN =0，则 (4-19) 式(4-19)是 的一个解， 称为线性规划问题关于基B 的基本解。 若B-1b ≥ 0，称 B 为可行基。 此时， 称 为关于可行基B 的基本可行解。 max s.t. x2 x1 10 30 50 10 30 最优点 由上图可知，当等值线通过两直线的交点时，具有最大值。 max s.t. x2 x1 10 30 50 10 30 由上图可知，在第I象限内，离原点越远，目标函数值越大。虽然可行解存在，但是目标函数无上界，因此无最优解。这种情况是因为数学模型中缺少必要的约束条件。 max s.t. x2 x1 10 30 50 10 30 从图形可以看出，同时满足约束条件的点(x1、x2)不存在， 因此其可行域变为空，没有可行解，则没有最优解。 这种情况是数学模型中的约束条件有矛盾，需要调整。 max s.t. A B x2 x1 10 30