整数规划及运输问题.ppt

5整数规划IntegerProgramming 简称IP 一 整数规划的一般模型 LP maxz CXAX bX 0 IP maxz CXAX bX 0X为整数 例一 合理下料问题设用某型号的圆钢下零件A1 A2 Am的毛坯 在一根圆钢上下料的方式有B1 B2 Bn种 每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量 如表所示 怎样安排下料方式 使得即满足需要 所用的原材料又最少 整数规划的模型 设 xj表示用Bj j 1 2 n 种方式下料根数模型 整数规划的模型 纯整数规划 所有决策变量要求取非负整数 这时引进的松弛变量和剩余变量可以不要求取整数 全整数规划 除所有决策变量要求取非负整数外 系数aij和常数bi也要求取整数 这时引进的松弛变量和剩余变量也必须是整数 混合整数规划 只有一部分的决策变量要求取非负整数 另一部分可以取非负实数 0 1整数规划 所有决策变量只能取0或1两个整数 整数规划的数学模型 从数学模型上看整数规划似乎是线性规划的一种特殊形式 求解只需在线性规划的基础上 通过舍入取整 寻求满足整数要求的解即可 但实际上两者却有很大的不同 通过舍入得到的解 整数 也不一定就是最优解 有时甚至不能保证所得倒的解是整数可行解 整数规划与线性规划的关系 例 设整数规划问题如下 首先不考虑整数约束 得到线性规划问题 一般称为松弛问题 整数规划与线性规划的关系 且为整数 用图解法求出最优解x1 3 2 x2 10 3且有Z 29 6 x1 x2 3 3 3 2 10 3 现求整数解 最优解 如用 舍入取整法 可得到4个点即 1 3 2 3 1 4 2 4 显然 它们都不可能是整数规划的最优解 按整数规划约束条件 其可行解肯定在线性规划问题的可行域内且为整数点 故整数规划问题的可行解集是一个有限集 如图所示 整数规划与线性规划的关系 因此 可将集合内的整数点一一找出 其最大目标函数的值为最优解 此法为完全枚举法 如上例 其中 2 2 3 1 点为最大值 Z 4 目前 常用的求解整数规划的方法有 分支定界法和割平面法 对于特别的0 1规划问题采用隐枚举法和匈牙利法 整数规划与线性规划的关系 考虑纯整数问题 整数问题的松弛问题 分枝定界法 1 先不考虑整数约束 解 IP 的松弛问题 LP 可能得到以下情况之一 若 LP 没有可行解 则 IP 也没有可行解 停止计算 若 LP 有最优解 并符合 IP 的整数条件 则 LP 的最优解即为 IP 的最优解 停止计算 若 LP 有最优解 但不符合 IP 的整数条件 转入下一步 为讨论方便 设 LP 的最优解为 分枝定界法 2 定界 记 IP 的目标函数最优值为Z 以Z 0 作为Z 的上界 记为 Z 0 再用观察法找的一个整数可行解X 并以其相应的目标函数值Z 作为Z 的下界 记为Z Z 也可以令Z 则有 Z Z 3 分枝 在 LP 的最优解X 0 中 任选一个不符合整数条件的变量 例如xr b r 不为整数 以 b r 表示不超过b r的最大整数 构造两个约束条件xr b r 和xr b r 1 分枝定界法 将这两个约束条件分别加入问题 IP 形成两个子问题 IP1 和 IP2 再解这两个问题的松弛问题 LP1 和 LP2 4 修改上 下界 按照以下两点规则进行 在各分枝问题中 找出目标函数值最大者作为新的上界 从已符合整数条件的分枝中 找出目标函数值最大者作为新的下界 5 比较与剪枝 各分枝的目标函数值中 若有小于Z者 则剪掉此枝 表明此子问题已经探清 不必再分枝了 否则继续分枝 如此反复进行 直到得到Z Z 为止 即得最优解X 分枝定界法 例一 用分枝定界法求解整数规划问题 记为 IP 解 首先去掉整数约束 变成一般线性规划问题 记为 LP 分枝定界法 用图解法求 LP 的最优解 如图所示 x1 x2 3 3 18 11 40 11 对于x1 18 11 1 64 取值x1 1 x1 2对于x2 40 11 3 64 取值x2 3 x2 4先将 LP 划分为 LP1 和 LP2 取x1 1 x1 2 x1 18 11 x2 40 11Z 0 218 11 19 8 即Z 0 是 IP 最小值的下限 分枝定界法 有下式 现在只要求出 LP1 和 LP2 的最优解即可 分枝定界法 x1 x2 3 3 18 11 40 11 先求 LP1 如图所示 此时B在点取得最优解 x1 1 x2 3 Z 1 16找到整数解 问题已探明 此枝停止计算 1 1 同理求 LP2 如图所示 在C点取得最优解 即x1 2 x2 10 3 Z 2 56 3 18 7 Z2 Z1 16 原问题有比 16 更小的最优解 但x2不是整数 利用3 10 3 4加入条件 B A C 分枝定界法 加入条件 x2 3 x2 4有下式 只要求出 LP3 和 LP4 的最优解即可 分枝定界法 x1 x2 3 3 18 11 40 11 1 1 B A C 先求 LP3 如图所示 此时D在点取得最优解 即x1 12 5 2 4 x2 3 Z 3 87 5 17 4 Z 19 8但x1 12 5不是整数 可继续分枝 即3 x1 2 D 求 LP4 如图所示 无可行解 不再分枝 分枝定界法 在 LP3 的基础上继续分枝 加入条件3 x1 2有下式 只要求出 LP5 和 LP6 的最优解即可 分枝定界法 x1 x2 3 3 18 11 40 11 1 1 B A C D 先求 LP5 如图所示 此时E在点取得最优解 即x1 2 x2 3 Z 5 17找到整数解 问题已探明 此枝停止计算 E 求 LP6 如图所示 此时F在点取得最优解 x1 3 x2 2 5 Z 6 31 2 15 5 Z 5 F 如对Z 6 继续分解 其最小值也不会低于 15 5 问题探明 剪枝 分枝定界法 至此 原问题 IP 的最优解为 x1 2 x2 3 Z Z 5 17以上的求解过程可以用一个树形图表示如右 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 5 LP3x1 12 5 x2 3Z 3 17 4 LP4无可行解 LP5x1 2 x2 3Z 5 17 LP6x1 3 x2 5 2Z 6 15 5 x1 1 x1 2 x2 3 x2 4 x1 2 x1 3 分枝定界法 二 0 1整数规划 投资场所的选址问题指派问题固定费用问题背包问题消防队问题 1 投资场所的选址问题某城市拟在东 西 南三区设立商业网点 备选位置有A1 A7共7个 如果选Ai 估计投资为bi元 利润为ci元 要求总投资不超过B元 规定东区 A1 A2 A3中至多选2个西区 A4 A5中至少选一个南区 A6 A7中至少选一个问如何设点使总利润最大 maxz xi 0或1 i 1 7 x1 x2 x3 2 x4 x5 1 x6 x7 1 s t 课堂练习1 某钻井队要从S1 S10共10个井位中确定五个钻井探油 如果选Si 估计钻探费用为ci元 并且井位选择上要满足下列条件 1 或选择S1和S7 或选择S8 2 选择了S3或S4就不能选择S5 反过来也一样 3 在S5 S6 S7 S8中最多只能选两个 问如何选择井位使总费用最小 课堂练习1 某钻井队要从S1 S10共10个井位中确定五个钻井探油 如果选Si 估计钻探费用为ci元 并且井位选择上要满足下列条件 1 或选择S1和S7 或选择S8 2 选择了S3或S4就不能选择S5 反过来也一样 3 在S5 S6 S7 S8中最多只能选两个问如何选择井位使总费用最小 minz s t 或1 i 1 10 某篮球队有8名队员 其身高和专长如下表 现要选拔5名球员上场参赛 要求 1 中锋只有1人上场 2 后卫至少有一人上场 3 只有2号上场 6号才上场要求平均身高最高 应如何选拔队员 课堂练习2 maxz 或1 i 1 8 s t 某篮球队有8名队员 其身高和专长如下表 现要选拔5名球员上场参赛 要求 1 中锋只有1人上场 2 后卫至少有一人上场 3 只有2号上场 6号才上场要求平均身高最高 应如何选拔队员 2 指派问题 例 有一份中文说明书 需译成英 日 德 俄四种文字 分别记作任务E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成不同语种说明书所需的时间如下表所示 问应指派何人去完成何项任务 使所需总时间最少 问题描述 n项任务可由n个人完成 由于专长不同 各人完成各任务的时间也不同 求最优安排 要求 每人只能完成一项任务 每项任务只能由一人完成 x11 x12 x13 x14 1 甲只能干一项工作 x21 x22 x23 x24 1 乙只能干一项工作 x31 x32 x33 x34 1 丙只能干一项工作 x41 x42 x43 x44 1 丁只能干一项工作 x11 x21 x31 x41 1 E任务只能一人干 x12 x22 x32 x42 1 J任务只能一人干 x13 x23 x33 x43 1 G任务只能一人干 x14 x24 x34 x44 1 R任务只能一人干 xij 0或1 i j 1 2 3 4 minz 2x11 15x12 13x13 4x14 10 x21 4x22 14x23 15x24 9x31 14x32 16x33 13x34 7x41 8x42 11x43 9x44 二 解题步骤 指派问题是0 1规划的特例 也是运输问题的特例 当然可用整数规划 0 1规划或运输问题的解法去求解 这就如同用单纯型法求解运输问题一样是不合算的 利用指派问题的特点可有更简便的解法 这就是匈牙利法 即系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数 第一步 变换指派问题的系数矩阵 cij 为 bij 使在 bij 的各行各列中都出现0元素 即 1 从 cij 的每行元素都减去该行的最小元素 2 再从所得新系数矩阵的每列元素中减去该列的最小元素 第二步 进行试指派 以寻求最优解 在 bij 中找尽可能多的独立0元素 若能找出n个独立0元素 就以这n个独立0元素对应解矩阵 xij 中的元素为1 其余为0 这就得到最优解 找独立0元素 常用的步骤为 1 从只有一个0元素的行 列 开始 给这个0元素加圈 记作 然后划去 所在列 行 的其它0元素 记作 这表示这列所代表的任务已指派完 不必再考虑别人了 2 给只有一个0元素的列 行 中的0元素加圈 记作 然后划去 所在行的0元素 记作 3 反复进行 1 2 两步 直到尽可能多的0元素都被圈出和划掉为止 4 若仍有没有划圈的0元素 且同行 列 的0元素至少有两个 则从剩有0元素最少的行 列 开始 比较这行各0元素所在列中0元素的数目 选择0元素少的那列的这个0元素加圈 表示选择性多的要 礼让 选择性少的 然后划掉同行同列的其它0元素 可反复进行 直到所有0元素都已圈出和划掉为止 5 若 元素的数目m等于矩阵的阶数n 那么这指派问题的最优解已得到 若m n 则转入下一步 第三步 作最少的直线覆盖所有0元素 1 对没有 的行打 号 2 对已打 号的行中所有含 元素的列打 号 3 再对打有 号的列中含 元素的行打 号 4 重复 2 3 直到得不出新的打 号的行 列为止 5 对没有打 号的行画横线 有打 号的列画纵线 这就得到覆盖所有0元素的最少直线数l l应等于m 若不相等 说明试指派过程有误 回到第二步 4 另行试指派 若l m n 须再变换当前的系数矩阵 以找到n个独立的0元素 为此转第四步 第四步 变换矩阵 bij 以增加0元素 在没有被直线覆盖的所有元素中找出最小元素 然后打 各行都减去这最小元素 打 各列都加上这最小元素 以保证系数矩阵中不出现负元素 新系数矩阵的最优解和原问题仍相同 转回第二步 例一 2 4 9 7 4 2 例二 求解过程如下 第一步 变换系数矩阵 5 第二步 试指派 找到3个独立零元素但m 3 n 4 第三步 作最少的直线覆盖所有0元素 独立零元素的个数m等于最少直线数l 即l m 3 n 4 第四步 变换矩阵 bij 以增加0元素 没有被直线覆盖的所有元素中的最小元素为1 然后打 各行都减去1 打 各列都加上1 得如下矩阵 并转第二步进行试指派 得到4个独立零元素 所以最优解矩阵为 15 练习 11 5 7 6 4 戊 6 9 6 3 7 丁 8 6 4 5 8 丙 9 11 7 12 9 乙 11 8 9 5 7 甲 E D C B A 费工作用人员 1 2 l m 4 n 5 l m 4 n 5 此问题有多个最优解 28 用匈牙利法求解下列指派问题 已知效率矩阵分别如下 3 固定费用问题 例 生产三种型号的防寒服 其消耗资源及单件成本如表 此外 每种防寒服不管生产多少 都要支付一定的固定费用 今要生产500件防寒服 确定总费用最低的生产方式 一般描述 已知 生产某产品有m种方式 设第j种生产方式的固定成本为kj 可变成本为cj 问题 应选择哪几种生产方式 分别生产多少产量可使总成本最低 分析 这是一个混合0 1规划问题 设第j种生产方式的产量为xj 于是该问题可表示为 xj Myj 例 生产三种型号的防寒服 其消耗资源及单件成本如表 此外 每种防寒服不管生产多少 都要支付一定的固定费用 今要生产500件防寒服 确定总费用最低的生产方式 MinZ 13x1 12x2 10 x3 120y1 150y2 180y3 1 5x1 1 7x2 1 8x3 15001 3x1 1 5x2 1 6x3 10004x1 4 5x2 5x3 35002 8x1 3 8x2 4 2x3 2800X1 x2 x3 500 xi Myi i 1 2 3 xi 0 yi 0或1 4 背包问题 问题描述 已知 一个背包最大容量为b公斤 有m件物品供选择 每件物品重ai公斤 价值为ci i 1 m 问题 携带哪些物品可使总价值最大 一般模型 s t 1 物品i被选中0 物品i没被选中 xi 例 一个徒步旅行者要在背包中选择一些最有价值的物品携带 他最多能带115kg的物品 现有5件物品 分别重54 35 57 46 19kg 其价值依次为7 5 9 6 3 问携带哪些物品可使总价值最大 解 模型为 s t 5 消防队问题 某城市的消防总部将全市划分为11个防火区 设有4个消防救火站 下图 表示消防站 1 11表示防火区域 图中连线表示各地区由哪个消防站负责 问题 可否减少消防站的数目 仍能同样负责各地区的防火任务 如果可以 应关闭哪个消防站 则模型为 课堂练习 某市为方便学生上学 拟在新建的居民小区增设若干所小学 已知备选校址代号及其能覆盖的居民小区编号如表所示 问为覆盖所有小区至少应建多少所小学 备选校址代号 覆盖的居民小区编号 ABCDEF 1 5 7 1 2 5 1 3 5 2 4 5 3 6 4 6 问题实例 例某公司用两种原油 A和B 混合加工成两种汽油 甲和乙 甲 乙两种汽油含原油A的最低比例分别为50 和60 每吨售价分别为4800元和5600元 该公司现有原油A和B的库存量分别为500吨和1000吨 还可以从市场上买到不超过1500吨的原油A 原油A的市场价为 购买量不超过500吨时的单价为10000元 吨 购买量超过500吨但不超过1000吨时 超过500吨的部分8000元 吨 购买量超过1000吨时 超过1000吨的部分6000元 吨 该公司应如何安排原油的采购和加工 建立模型 问题分析安排原油采购 加工的目标是利润最大 题目中给出的是两种汽油的售价和原油A的采购价 利润为销售汽油的收入与购买原油A的支出之差 这里的难点在于原油A的采购价与购买量的关系比较复杂 是分段函数关系 能否及如何用线性规划 整数规划模型加以处理是关键所在 模型建立设原油A的购买量为x 吨 根据题目所给数据 采购的支出c x 可表为如下的分段线性函数 以下价格以千元 吨为单位 1 设原油A用于生产甲 乙两种汽油的数量分别为x11和x12 吨 原油B用于生产甲 乙两种汽油的数量分别为x21和x22 吨 则总的收入为4 8 x11 x21 5 6 x12 x22 千元 于是本例的目标函数 利润 为 2 约束条件包括加工两种汽油用的原油A 原油B库存量的限制 和原油A购买量的限制 以及两种汽油含原油A的比例限制 它们表示为 3 4 5 6 7 8 由于 1 式中的c x 不是线性函数 1 8 给出的是一个非线性规划 而且 对于这样用分段函数定义的c x 一般的非线性规划软件也难以输入和求解 能不能想办法将该模型化简 从而用现成的软件求解呢 求解模型 3种解法 第1种解法将原油A的采购量x分解为三个量 即用x1 x2 x3分别表示以价格10 8 6千元 吨采购的原油A的吨数 总支出为c x 10 x1 8x2 6x3 且 9 这时目标函数 2 变为线性函数 10 应该注意到 只有当以10千元 吨的价格购买x1 500 吨 时 才能以8千元 吨的价格购买x2 0 这个条件可以表示为 11 同理 只有当以8千元 吨的价格购买x2 500 吨 时 才能以6千元 吨的价格购买x3 0 于是 12 此外 x1 x2 x3的取值范围是 13 由于有非线性约束 11 12 3 13 构成非线性规划模型 LINGO程序 Model Max 4 8 x11 4 8 x21 5 6 x12 5 6 x22 10 x1 8 x2 6 x3 x11 x120 0 4 x12 0 6 x22 0 x x1 x2 x3 x1 500 x2 0 x2 500 x3 0 bnd 0 x1 500 bnd 0 x2 500 bnd 0 x3 500 end 将文件存储并命名为exam0501a lg4 执行菜单命令 LINGO Solve 运行该程序得到 Localoptimalsolutionfound Objectivevalue 4800 000Totalsolveriterations 26 VariableValueReducedCostX11500 00000 000000X21500 00000 000000X120 0000000 000000X220 0000000 000000X10 0000000 000000X20 0000000 000000X30 0000000 000000X0 0000000 000000 最优解 用库存的500吨原油A 500吨原油B生产1000吨汽油甲 不购买新的原油A 利润为4800 千元 但是此时LINGO得到的结果只是一个局部最优解 可以用菜单命令 LINGO Options 在 GlobalSolver 选项卡上启动全局优化 UseGlobalSolver 选项 然后重新执行菜单命令 LINGO Solve 得到 Globaloptimalsolutionfound Objectivevalue 5000 002Extendedsolversteps 3Totalsolveriterations 187 VariableValueReducedCostX110 0000000 000000X210 0000000 000000X121500 0000 000000X221000 0000 000000X1500 00000 000000X2499 99900 000000X30 9536707E 030 000000X1000 0000 000000 此时LINGO得到的结果是一个全局最优解 Globaloptimalsolution 购买1000吨原油A 与库存的500吨原油A和1000吨原油B一起 共生产2500吨汽油乙 利润为5000 千元 高于刚刚得到的局部最优解对应的利润4800 千元 第2种解法 引入0 1变量将 11 和 12 转化为线性约束 令y1 1 y2 1 y3 1分别表示以10千元 吨 8千元 吨 6千元 吨的价格采购原油A 则约束 11 和 12 可以替换为 14 15 16 y1 y2 y3 0或1 17 3 10 13 17 构成混合整数线性规划模型 将它输入LINDO软件 Max4 8x11 4 8x21 5 6x12 5 6x22 10 x1 8x2 6x3stx x1 x2 x3 0 x11 x12 x00 4x12 0 6x22 0 x1 500y10 x2 500y3 0endinty1inty2inty3 运行该程序得到 OBJECTIVEFUNCTIONVALUE1 5000 000VARIABLEVALUEREDUCEDCOSTY11 0000000 000000Y21 0000002200 000000Y31 0000001200 000000X110 0000000 800000X210 0000000 800000X121500 0000000 000000X221000 0000000 000000X1500 0000000 000000X2500 0000000 000000X30 0000000 400000X1000 0000000 000000 这个结果与前面非线性规划模型用全局优化得到的结果相同 2020 3 16 77 可编辑 易拉罐下料问题 例5 4某公司采用一套冲压设备生产一种罐装饮料的易拉罐 这种易拉罐是用镀锡板冲压制成的 参见图5 3 易拉罐为圆柱形 包括罐身 上盖和下底 罐身高10厘米 上盖和下底的直径均为5厘米 该公司使用两种不同规格的镀锡板原料 规格1的镀锡板为正方形 边长24厘米 规格2的镀锡板为长方形 长 宽分别为32和28厘米 由于生产设备和生产工艺的限制 对于规格1的镀镀锡板原料 只可以按照图2中的模式1 2或3进行冲压 对于规格2的镀锡板原料只能按照模式4进行冲压 使用模式1 2 3 4进行每次冲压所需要的时间分别为1 5 2 1 3 秒 模式4 图5 3易拉罐下料模式 该工厂每周工作40小时 每周可供使用的规格1 2的镀锡板原料分别为5万张和2万张 目前每只易拉罐的利润为0 10元 原料余料损失为0 001元 厘米2 如果周末有罐身 上盖或下底不能配套组装成易拉罐出售 也看作是原料余料损失 工厂应如何安排每周的生产 已知上盖和下底的直径d 5厘米 可得其面积为 19 6厘米2 表5 44种冲压模式的特征 问题的目标显然应是易拉罐的利润扣除原料余料损失后的净利润最大 约束条件除每周工作时间和原料数量外 还要考虑罐身和底 盖的配套组装 模型建立 决策变量用xi表示按照第i种模式的冲压次数 i 1 2 3 4 y1表示一周生产的易拉罐个数 为计算不能配套组装的罐身和底 盖造成的原料损失 用y2表示不配套的罐身个数 y3表示不配套的底 盖个数 虽然实际上xi和y1 y2 y3应该是整数 但是由于生产量相当大 可以把它们看成是实数 从而用线性规划模型处理 决策目标假设每周生产的易拉罐能够全部售出 公司每周的销售利润是0 1y1 原料余料损失包括两部分 4种冲压模式下的余料损失 和不配套的罐身和底 盖造成的原料损失 按照前面的计算及表2的结果 总损失为0 001 222 6x1 183 3x2 261 8x3 169 5x4 157 1y2 19 6y3 于是 决策目标为 47 约束条件 时间约束 每周工作时间不超过40小时 144000 秒 由表2最后一列得 48 原料约束 每周可供使用的规格1 2的镀锡板原料分别为50000张和20000张 即 49 50 配套约束 由表2一周生产的罐身个数为x1 2x2 4x4 一周生产的底 盖个数为10 x1 4x2 16x3 5x4 因为应尽可能将它们配套组装成易拉罐销售 所以y1满足 51 这时不配套的罐身个数y2 和不配套的底 盖个数y3应为 52 53 47 53 就是我们得到的模型 其中 51 是一个非线性关系 不易直接处理 但是它可以等价为以下两个线性不等式 54 55 模型求解 将模型 47 50 和 52 55 直接输入LINDO 输入LINGO也可以 求解时LINDO发出警告信息 程序和警告信息参见图5 4 图中错误编号 66 的含义 参见第4章的错误代码表 是 模型中数据不平衡 所以发出警告信息 注意 只是警告信息 所以仍然可以继续求解 求解结果是 OBJECTIVEFUNCTIONVALUE1 4298 337VARIABLEVALUEREDUCEDCOSTY1160250 0000000 000000X10 0000000 000050X240125 0000000 000000X33750 0000000 000000X420000 0000000 000000Y20 0000000 223331Y30 0000000 036484 图5 4模型中数据不平衡的警告信息 这个结果可靠吗 由于LINDO警告模型中数据之间的数量级差别太大 所以我们可以进行预处理 缩小数据之间的差别 实际上 约束 48 50 中右端项的数值过大 与左端的系数相比较 LINDO在计算中容易产生比较大的误差 所以出现此警告信息 为了解决这一问题 可以将所有决策变量扩大10000倍 相当于xi以万次为单位 yi以万件为单位 此时 目标 47 可以保持不变 记住得到的结果单位为万元就可以了 而约束 48 50 改为 56 57 58 将模型 47 和 52 58 输入LINDO 易拉罐下料 均衡数据 Max0 100y1 0 2226x1 0 1833x2 0 2618x3 0 1695x4 0 1571y2 0 0196y3s t 1 5x1 2 0 x2 1 0 x3 3 0 x4 010 x1 4x2 16x3 5x4 2y1 0 x1 2x2 4x4 y1 y2 010 x1 4x2 16x3 5x4 2y1 y3 0end 求解得到 OBJECTIVEFUNCTIONVALUE 1 0 4298337 VARIABLEVALUEREDUCEDCOSTY116 0250000 000000X10 0000000 000050X24 0125000 000000X30 3750000 000000X42 0000000 000000Y20 0000000 223331Y30 0000000 036484 即模式1不使用 模式2使用40125次 模式3使用3750次 模式4使用20000次 可生产易拉罐160250个 罐身和底 盖均无剩余 净利润为4298元 运输问题 1运输问题2运输问题的表上作业法3运输问题的进一步讨论 第一节运输问题及其数学模型 运输问题是一类特殊的线性规划问题 本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性 运输问题的对偶问题及其对偶变量与原问题检验数的关系 典型背景 单一物资运输调度问题设某种物品有 m个产地 产量 n个销地 销量 从产地到销地的单位运价是 求总运费最小的调度方案 决策变量表示由到的物品数量 产销平衡问题 总产量 总销量即产销不平衡问题 总产量 总销量 产销平衡问题的数学模型 运输问题数学模型的特点 运输问题有有限最优解运输问题约束条件的系数矩阵 下页 约束条件系数矩阵每一列只有两个1 其余为0 对产销平衡问题约束条件均为等式 且产量之和 销量之和 约束条件的独立方程最多有m n 1个 即 i j 其中 运输问题的对偶问题 对偶变量与原问题检验数的关系 对产销平衡运输问题 若用分别表示前m个约束等式相应的对偶变量 用分别表示后n个约束等式相应的对偶变量 即对偶变量为 运输问题的对偶问题可写为 运输问题的对偶问题 对偶变量与原问题检验数的关系 线性规划问题变量的检验数为 运输问题的对偶问题 对偶变量与原问题检验数的关系 变量的检验数为 设运输问题的一个基可行解的变量为 由于基变量的检验数为零 故有 运输问题的对偶问题 对偶变量与原问题检验数的关系 方程组含有m n 1个方程 m n个变量可证明方程组有解 且不唯一 求出方程组的解 称为位势 则变量的检验数为 运输问题的对偶问题 对偶变量与原问题检验数的关系 第二节运输问题的表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性 本节将由此给出运输问题的比单纯形法更为简便的求解方法 表上作业法 表上作业法是单纯形法在求解运输问题的一种简便方法 单纯形法与表上作业法的关系 1 找出初始基可行解 2 求各非基变量的检验数 3 判断是否最优解 换基 4 确定换入变量和换出变量找出新的基可行解 5 重复 2 3 直至求出最优解 停止 举例说明表上作业法 例1 某部门三个工厂生产同一产品的产量 四个销售点的销量及单位运价如下表 第一步 确定初始基可行解 最小元素法 伏格尔法 最小元素法思路 从单价中最小运价确定供应量 逐步次小 直至得到m n 1个数字格 最小元素法举例 8 2 2 0 10 10 0 6 14 8 6 8 0 0 0 0 6 0 最小元素法举例 最小元素法缺点 会出现顾此失彼 运费差额问题 考虑运价差 罚数 即差额 次小运价 最小运价罚数 或差额 的解释 差额大 则不按最小运费调运 运费增加大 差额小 则不按最小运费调运 运费增加不大 对差额最大处 采用最小运费调运 伏格尔法思路 结合例1说明这种方法 0 4 4 0 第一次 结合例1说明这种方法 1 3 2 1 第一次 结合例1说明这种方法 1 第一次 结合例1说明这种方法 4 2 2 2 1 5 3 第一次 结合例1说明这种方法 14 8 0 优先安排销地 否则运价会更高 下次不考虑该列 第一次 第二次 结合例1说明这种方法 优先安排销地 否则运价会更高 8 0 6 下次不考虑该行 结合例1说明这种方法 下次不考虑该列 8 0 2 第三次 结合例1说明这种方法 4 12 0 下次不考虑该列 第四次 结合例1说明这种方法 4 2 0 0 0 第五次 例1用伏格尔法得到的初始基可行解 目标函数值 用最小元素法求出的目标函数z 246 一般说来 伏格尔法得出的初始解的质量最好 常用来作为运输问题最优解的近似解 第二步 解的最优性检验 闭回路法思路 计算空格 非基变量 的检验数 若令则 如何求检验数 分析 即增加1个单