运筹学第1章线性规划和单纯形法复习试题.ppt

上述线性规划问题： 用 Matlab 语言来改写，则有： 在 Matlab 语言中，以矩阵作为基本计算单位，向量可以看作是矩阵的特殊情况，用“；”表示矩阵的分行，用“，”表示两个元素的分隔，用“[ ]”表示矩阵整体。 利用 Matlab 进行线性规划问题求解的命令格式为： X=lp(c , A , b , XLB , XUB , x0 , nEq) 在上述式子中： c 是目标函数中的系数向量； A 为约束方程组（不等式组）的系数矩阵； b 为约束方程组（不等式组）的右端列向量； XLB 为决策向量 X 的下限； XUB 为决策向量 X 的上限； x0 为决策向量 X 的初值； nEq 为约束方程中等式的个数。 各参量在 Matlab 命令中使用的名称可以根据需要而不同，但是出现的顺序不能发生改变。 对于前述的线性规划问题，我们已经给出了 c , A , b，并且我们知道约束条件中等式有三个，即 nEq=3，但是我们还没有给出决策向量的上限、下限和初值。 决策向量的上限、下限和初值我们可以根据实际情况自己进行估计，在该问题中，我们可以设上限为每种方案最多使用100根钢筋，最少使用0根，初值可以设为全都取0。 因此我们输入的屏幕显示为： 回车后得到计算结果： 这个数据似乎与前面结果不同，但是仍然有 min z=16这时我们认为两个结果是等效的。 例2. 混合配料问题 某糖果厂用原料A、B、C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表，问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大，试建立该问题的线性规划数学模型。 解：用 i = 1 , 2 , 3 分别代表原料A、B、C，用 j = 1, 2, 3 分别代表甲、乙、丙三种糖果。设 xij 为生产第 j 种糖果使用的第 i 种原料的质量，则问题的数学模型可归结为： 目标函数 约束条件为 例3. 投资项目的组合问题 兴安公司有一笔 30 万元的资金，考虑今后三年内用于下列项目的投资： 1. 三年内的每年年初均可投入，每年获利为投资额的 20%，其本利可一起用于下一年的投资； 2. 只允许第一年初投入，于第二年年末收回，本利合计为投资额的150%，但此类投资限额15万以内； 3. 允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元以内； 4. 允许于第三年初投入，年末收回，可获利40%，但限额为10万元以内； 试为该公司确定一个使第三年末本利总和为最大的投资组合方案。 解：用 xij 表示第 i 年初投放到 j 项目的资金数，则可投资的变量表如下 由于第三年末收回的本利只包含第三年初项目一的投资、第二年初项目三的投资和第三年初项目四的投资，因此目标函数为： 第一年初投资总额为30万，因此有： 第二年初的投资额与第一年末收回的本利总额相同： 第三年初投资额与第二年末收回的本利总额相同： 再考虑各项目的投资限额，得到该问题的线性规划模型如下： 服务理念中的“点点” ◆理解多一点 真情浓一点 ◆学习勤一点 品质高一点 ◆理由少一点 效率高一点 ◆处理问题灵活点 工作过程用心点 ◆对待同事宽容点 互相协作快乐点 * 当E=1时，作为复合医院的产出量也有可能超过省医院的产出量，所以不一定是最优的。 （一）、基本思想 将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。 （二）、线性规划模型的标准形式 §4 单纯形法的计算步骤 例 一、将下列线性规划问题化为标准形式 为无约束（无非负限制） 解: 用 替换 ，且 ， 将第3个约束方程两边乘以（－1） 将极小值问题反号，变为求极大值 标准形式如下： 引入变量 找出一个初始可行解 是否最优 转移到另一个基本可行解 最优解 是 否 循 环 核心是：变量迭代 结束 （三）求解步骤 （四）单纯形表 例 题： §5、单纯形法的进一步讨论 (1) 构造初始基本可行解的大M法 模型1 模型2 (其中M为充分大的正数) 定理: 如果 是模型2的最优解,则当Y*=0时, X*一定是模 型1的最优解; 当Y*≠0时, 模型1没有可行解. 反