运筹学作业辅导.pptx

运筹学作业精讲 第一单元 某企业生产甲 乙两种产品 其单位利润分别为20元和30元 每生产一件甲产品需劳动力3个 原材料2千克 设备4小时 每生产一件乙产品需劳动力7个 原材料4千克 设备3小时 企业现有劳动力240个 原材料150千克 设备可用时间为250小时 问 如何安排生产计划 才能使所获总利润最大 写出线性规划模型 化成标准形式 用图解法进行求解 解 设x1和x2分别表示产品甲和乙的产量 这样可以建立如下的数学模型 目标函数 max20 x1 30 x2约束条件 s t 3x1 7x2 240 劳动力限制 2x1 4x2 150 原材料限制 4x1 3x2 250 设备限制 x1 x2 0 非负约束 化为标准型 目标函数 max20 x1 30 x2约束条件 s t 3x1 7x2 x3 2402x1 4x2 x4 1504x1 3x2 x5 250 x1 x2 x3 x4 x5 0 阴影部分为可行域 虚线为目标函数线 由图可知最优解为约束2和约束3的交点 解得坐标为 55 10 故最优生产计划为生产甲产品55件 乙产品10件 最大利润为20 55 30 10 1400元 第二单元 某厂生产三种型号的铝锅 已知单耗数据如下 试制定最优生产计划使总收入最大 解 设x1 x2 x3分别表示大号 中号 小号铝锅的产量 这样可以建立如下的数学模型 目标函数 max50 x1 40 x2 30 x3约束条件 s t 6x1 2x2 4x3 400 铝板限制 4x1 8x2 6x3 360 劳力限制 8x1 4x2 10 x3 420 机器限制 x1 x2 x3 0 非负约束 化为标准型 目标函数 max50 x1 40 x2 30 x3约束条件 s t 6x1 2x2 4x3 x4 4004x1 8x2 6x3 x5 3608x1 4x2 10 x3 x6 420 x1 x2 x3 x4 x5 x6 0 使用单纯形法求解 得到最优解 40 25 0 110 0 0 最优值3000 即应该生产大号铝锅40个 中号铝锅25个单位 小号铝锅产量为0 不生产 最大利润为3000元 第三单元 线性规划maxz 5x1 5x2 13x3s t x1 x2 3x3 2012x1 4x2 10 x3 90 x1 x2 x3 0的最优表为 分析在下列条件下 最优解分别有什么变化 1 b2由90变为70 2 c1由 5变为 10 3 增加一个约束条件4x1 3x2 6x3 50 解 1 由最优基不变的条件max bi ir ir 0 dbr min bi ir ir 0 得 10 10 1 db2b2由90变为70 超出了允许变化范围 继续计算或者由b 1 b db 20 10 t可以知道最优基发生变化 继续迭代 最优解变为x1 0 x2 5 x3 5 x4 0 x5 0 最优值z 90 2 c1是非基变量的系数 最优解不变的条件是 dc1 s1 c1由 5 10 dc1 5 0 s1 不影响最优解 3 增加一个约束条件4x1 3x2 6x3 50 原最优解不满足这个约束 引入松弛变量 得到4x1 3x2 6x3 x6 50填入最优单纯形表 进一步求解 得到最优解为x 0 10 10 3 t 最优值为280 3 第四单元 对于以下的运输问题 若各个销地少得到1个单位的产品 将要求得到赔偿 金额分别为9 12 6 12 问如何组织运输 才能使总费用最低 建立运输模型 用最小元素法求初始解 并求出最优解 解 总产量为99 55 110 264 总销量44 88 88 77 297 产销不平衡且供不应求 增加一个虚拟产地a4 其产量为297 264 33 由虚拟产地运往销地的费用即为赔偿金额 因此可以建立运输模型如下 使用最小元素法求初始解 说明 每次选择最小元素 因此依次选择3 x33 6 x22 9 x41 12 x11 15 x14 21 x32 33 x12 得到初始解x11 11 x12 11 x14 77 x22 55 x32 22 x33 88 x41 33 其余运量为0 总运费为3003 使用位势法计算各非基变量检验数 填入括号中 令u1 0 由基变量满足ui vj cij 依次得到各位势v1 12 v2 33 v4 15 u4 3 u2 27 u3 12 v3 15 再根据公式sij cij ui vj计算各非基变量检验数 进行调整 选负检验数中最小的s42 那么x42为主元 作为进基变量 以x42为起点找一条闭回路x42 x41 x11 x12 取偶数标号格的最小运量11作为调整量 调整后运量为x42 11 x41 22 x11 22 x12 0 调整为非基变量 得到新的基本解 并重新用位势法计算检验数 令v2 0 如下表所示 所有非基变量检验数均非负 得到最优解为x11 22 x14 77 x22 55 x32 22 x33 88 x41 22 x42 11 其余运量为0 最小的总运费为2805 第五单元 有一个工厂要确定明年各季度的生产计划 通过订货了解到各季度对产品的需求量dk分别为4000件 3000件 4000件和4000件 又知 工厂生产该产品的季度固定成本为10万元 但如果在某季度中 该种产品1件也不生产 则不需支付固定成本费 单位产品的可变成本为50元 由于设备的能力所限 每季度最多只能生产5000件 若产品销售不出 则每件每季度的存贮费为8元 假设本年底无存货转入下年 明年末也不需要留有存货 问每季度的生产计划应如何安排 假设生产产量以千件为单位 才能使生产的总费用最省 解 首先建立动态规划模型 1 阶段k 每个季度作为一个阶段 k 1 2 3 4 2 状态变量sk 第k个季度初的库存量 千件 3 决策变量uk 第k个季度的生产量 千件 4 状态转移方程 sk 1 sk uk dk 需求 千件 即季度末库存量 季度初库存量 季度生产量 季度销售量或需求量 5 阶段指标 gk sk uk 生产成本c uk 库存成本e sk 6 最优指标函数fk sk 第k个季度的状态为sk时从该季度至计划结束的最低总费用 万元 7 递推方程 fk sk min gk sk uk fk 1 sk 1 8 终端条件 f5 s5 0 下面进行求解 采用逆序解法 1 k 5 f5 s5 0 2 k 4 0 s4 4 u4 4 s4 s5 s4 u4 d4 说明 第4季度的需求为4千件 因此库存量不应超过4且显然非负 所以有0 s4 4 年底不需要有库存 所以生产量u4 4 s4 3 k 3 0 s3 5 5 4 3 3 s4 s3 u3 d3 s3 u3 4 max 0 4 s3 u3 min 5 8 s3 说明 前两季度总产量为5 5 10千件 需求量为3 4 7千件 所以第3季度初最大库存量 10 7 3千件 在产量需求方面 为了满足需求 至少生产d3 u3 4 u3 且最大产量为5千件 后两个季度总需求为4 4 8千件 产量不应该超过8 s3 因此有0 s3 3 max 0 4 s3 u3 min 5 8 s3 4 k 2 0 s2 5 4 1 s3 s2 u2 d2 s2 u2 3 max 0 3 s2 u2 min 5 11 s2 5 k 1 s1 0 s2 s1 u1 d1 u1 4 4 u1 5最优解为s1 0 u1 5 s2 1 u2 5 s3 3 u3 5 s4 4 u4 0即前3个季度均生产5000件 第4个季度不生产 最低总费用为111 4万元 第六单元 某企业生产甲 乙两种产品 生产一件甲产品需要使用劳动力4小时 能源2个单位 销售利润为16万元 生产一件乙产品需要使用劳动力2小时 能源4个单位 销售利润为20万元 企业目前拥有劳动力可用时间22小时 能源20个单位 在制定生产计划时 决策者考虑下述4项目标 首先 乙产品的产量不低于甲产品的产量 其次加班费用比较高 尽量不要加班 第三 尽可能充分利用能源 但是又不希望再购买 最后 利润尽量不少于112万元 求决策方案 建立目标规划模型并用单纯形法求解 解 设x1 x2分别表示甲产品和乙产品的产 以建立如下的目标规划模型 目标函数 minf p1d1 p2d2 p3 d3 d3 p4d4 约束条件 x1 x2 d1 d1 04x1 2x2 d2 d2 222x1 4x2 d3 d3 2016x1 20 x2 d4 d4 112x1 x2 di di 0 i 1 2 3 4 说明 目标1和2是不超过目标值 因此正偏差变量尽量小 目标3是恰好达到目标值 因此要求正 负偏差变量都尽量小 目标4要求不少于目标值 因此是负偏差变量尽量小 下面用单纯形法进行求解 列出单纯形表 取d1 d2 d3 d4 为初始基变量 把最小化问题转为为最大化问题 所以目标函数系数均乘以 1 基变量的检验数应该为0 处理初始基本可行解对应的各级检验数 由于p1 p2优先级对应目标函数中不含di 其检验数只需取系数负值 分别为 0 0 0 1 0 0 0 0 0 0 0 和 0 0 0 0 0 1 0 0 0 0 0 p3优先级对应的目标函数中含d3 所以其检验数需要把第3个约束行加到取负值的这一行上 得到 2 4 0 0 0 0 0 2 0 0 20 p4优先级对应的目标函数中含d4 所以其检验数需要把第4个约束行加到取负值的这一行上 得到 16 20 0 0 0 0 0 0 0 1 112 列目标规划的初始单纯形表如下 下面进行计算 1 k 1 在初始单纯形表中基变量为 d1 d2 d3 d4 0 22 20 112 2 因为p1与p2优先级的检验数均已经为非正 所以这个单纯形表对p1与p2优先级是最优单纯形表 3 下面考虑p3优先级 第二列的检验数为4最大 此为进基变量 计算相应的比值bi aij写在q列 通过比较 得到d3 对应的比值最小 于是取a32 标 号 为转轴元进行矩阵行变换得到新的单纯形表如下 4 下面考虑p4优先级 第一列的检验数为6最大 此为进基变量 计算相应的比值bi aij写在q列 通过比较 得到d4 对应的比值最小 于是取a41 标 号 为转轴元进行矩阵行变换得到新的单纯形表如下 5 当前的单纯形表各优先级的检验数均满足了最优条件 故为最优单纯形表 于是得到最优解x1 2 x2 4 第七单元 下图为一个交通运输网络图 道路 即弧 旁的权数表示该道路的容量和目前的运输量 cij fij 求出该交通运输网络的最大运输能力 即网络最大流 解 第一次标号 1 首先给vs标号 0 2 看vs 在弧 vs v2 上 fs2 cs2 2 不具备标号条件 在弧 vs v1 上 fs1 50 故给v4标号 v1 l v4 其中l v4 min l v1 f41 min 3 2 2 4 看v3 在弧 v3 vt 上 f3t 5 c3t 9 给vt标号 v3 l vt 其中l vt min l v3 c3t f3t min 3 9 5 3 因为vt被标上号 根据标号法 转入调整过程 进入第一次调整过程 从vt开始 按照标号点的第一个标号 用反向追踪的方法 找出一条从vs到vt的增广链 如上图中双箭线所示 不难看出 vs v1 v1 v3 v3 vt 空集 取 3 在 上调整f 在 上增加3 在 上减少3 其他不变 调整后的可行流f 如下图所示 再对这个可行流从新进行标号过程 寻找增广链 首先给vs标号 0 看vs 在弧 vs v1 上fs1 cs1 弧 vs v2 上fs2 cs2 均不符合条件 因此标号过程无法进行下去 不存在从vs到vt的增广链 算法结束 目前的运输方案就是最优方案 第八单元 某服装厂准备大批量生产一种新服装 估计