第七章 目标规划.ppt

第七章目标规划 在一般的线性规划问题中 研究的都是只有一个目标的决策问题 在实际问题中 衡量一个方案好与坏的标准往往不止一个 而这些标准彼此又往往不是那么协调的 甚至是互相矛盾的 对立的 这些标准的度量单位也常常各不相同 7 1数学模型 7 1 1引例 在资源的最优利用问题中 除了考虑所得的利润最大 还耍考虑使生产的产品质量最好 劳动生产率最高 对市场的适应性最强等等 一般的线性规划方法无能为力 例1某工厂因生产需要采购某种原料 市场上有甲 乙两个等级 单价分别为2元 斤和1元 斤 现要求所花的总费用不得超过200元 购得原料的总重量不少于100斤 而甲等原料又不得少于50斤 问如何确定最好的采购方案 即花最少的钱 采购最多数量的原料 建立这个问题的基本模型 解 设分别为采购甲等 乙等原料的数量 单位 斤 则得基本模型如下 例1 某工厂生产甲 乙两种产品 已知有关数据见下表 试求获利最大的生产方案 解 这是一个单目标问题 用线性规划模型描述为 最优解为 元 但实际上工厂在作决策时 要考虑市场等一系列其他条件 1 根据市场信息 产品I的销售量有下降的趋势 故考虑产品甲的产量不大于产品II 2 超过计划供应的原材料时 需要高价采购 这就使成本增加 3 应尽可能利用设备I 但不希望加班 4 应尽可能达到并超过计划利润指标56元 例2 市场上有香蕉 苹果 葡萄三种水果 其单价分别为4 2元 斤 2 4元 斤 2 2元 斤 现在某单位要筹办一次茶话会 要求买水果的钱不能超过280元 水果的总量不能少于100斤 香蕉 苹果的总量不能少于60斤 问如何确定最好的购买方案 设x1 x2 x3分别为购买香蕉 苹果 葡萄三种水果的重量 用于买水果的总钱数是Y1 所买水果的总数量是Y2 7 1 2偏差变量 1 设为决策变量 此外 引进正 负偏差变量正偏差变量表示决策值超过目标值的部分 负偏差变量表示决策值未达到目标值的部分 2 绝对约束和目标约束 3 优先因子 优先等级 与权系数 4 目标规划的目标函数 2 要求不超过目标值 既允许达不到目标值 就是正偏差变量尽可能地小 这时 3 要求超过目标值 既超过量不限 但必须是负偏差变量尽可能地小 这时 1 要求恰好达到目标值 既正 负偏差变量都要尽可能地小 这时 7 1 3目标规划的数学模型 目标规划模型的一般形式为 使目标函数 求x x1 xn T 满足条件 7 2解目标规划的单纯形法 1 因目标规划问题的目标函数都是求最小化 所以以为最优准则 2 因非基变量的检验数中含有不同等级的优先因子 即 因P1 P2 PK 从每个检验数的整体来看 检验数的正 负首先决定于P1的系数 1j的正 负 若 1j 0 这时此检验数的正 负就决定于P2的系数 2j的正 负 下面可依此类推 解目标规划问题的单纯形法的计算步骤 1 建立初始单纯形表 在表中将检验数行按优先因子个数分别列成K行 置k 1 2 检查该行中是否存在负数 且对应的前k 1的系数是零 若有 取其中最小者对应的变量为换入变量 转 3 若无负数 则转 5 3 按最小比值规则确定换出变量 当存在两个和两个以上相同的最小比值时 选取具有较高优先级别的变量为换出变量 4 按单纯形法进行基变换运算 建立新的计算表 返回 2 5 当k K时 计算结束 表中的解即为满意解 否则置k k 1 返回到 2 试用单纯形法来求解例2 将例2的数学模型化为标准型 1 取为初始基变量 列初始单纯形表 见表7 1 2 取k 1 检查检验数的P1行 因该行无负检验数 故转 5 5 因k 1 K 3 置k k 1 2 返回到 2 2 查出检验数P2行中有 1 2 取min 1 2 2 它对应的变量x2为换入变量 转入 3 1 P3 1 1 P2 1 P1 cj zj 1 3 1 3 5 3 1 2 1 6 1 6 4 3 1 1 4 x2 1 2 1 2 3 1 1 2 1 2 1 2 2 1 3 xs xs x2 x1 b XB CB P3 P2 P2 P1 cj 2 3 4 3 5 3 x1 7 3应用举例 例7 5 设某农场使用A B两种资源生产甲 乙两种作物 所需资源及收益见表7 7 问怎样安排甲 乙两种作物的生产 使利润最大 解 设甲 乙两种作物的种植面积分别为x1与x2 则线性规划模型为 求x x1 x2 T 满足 使maxf x 30 x1 50 x2 最优解为 x1 300 x2 400 maxf x 30 300 50 400 29000 如果根据市场需求 要求甲种作物播种面积不低于600亩 则在上述规划问题中要增加约束条件x1 600 它与2x1 x2 1000构成一对矛盾方程 用单纯形法求解时 因失去可行解域而无最优解 放宽约束 引入负偏差变量 表示现有资源使用后的剩余部分 把约束条件改定成 x1 d1 600 再加一个条件 要求利润不低于30000元 问甲 乙两种作物应种植多少 解 这个问题共有四个约束条件 资源A与B的可提供数量约束 A种资源约束 B种资源约束 原线性规划的目标函数在这里应列入约束条件 收益指标约束 作物甲的种植面积约束 计划指标约束 目标函数 d1 d1 分别表示两种作物消耗A种资源总量的正 负偏差变量 d2 d2 分别表示两种作物消耗B种资源总量的正 负偏差变量 d3 d3 分别表示收益