第10次课--第三章运输问题

信息系统与管理学院第三章运输问题温故知新信息系统与管理学院2对偶解的经济含义是在其他条件不变的情况下，单位资源变化引起的目标函数最优值的变化。这是该资源的一种价格表征，经济学上称之为“影子价格”。第五节对偶问题的经济解释**1,2,,iizyimb信息系统与管理学院3原问题单纯形表的检验数行对应其对偶问题的一个基解。BXNXsX10sY21NBsCCBNY1BCBY1sY对应原问题中基变量BX的剩余变量。2sY是对应原问题中非基变量NX的剩余变量。第六节对偶单纯形法信息系统与管理学院4保持对偶问题的解是基可行解（即保持单纯型表中检验数行为非正），而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样就得到了最优解。对偶单纯形法的思路第六节对偶单纯形法优点：原问题的初始解不一定要是基可行解，可从非基可行解开始迭代。信息系统与管理学院5计算步骤：⑴根据线性规划问题找到对偶问题的可行基，列出单纯形表。b列的数字若都为非负，而检验数都为非正，则已得到最优解。b列的数字若至少还有一个负分量，检验数保持非正，则进行以下计算：第六节对偶单纯形法信息系统与管理学院6⑶确定换入变量若存在0lja。计算min0jjkkljjljlkczczaaa按此规则所对应的列的非基变量kx为换入变量。⑵确定换出变量按111min0iiliBbBbBb对应的基变量lx为换出变量。先确定换出变量！确定换入变量的方法不同！目的要维持检验数的非正。第六节对偶单纯形法保持检验数非正信息系统与管理学院7若所有0lja，则无可行解。按此规则所对应的列的非基变量kx为换入变量，这样可保证得到的对偶问题的解仍为可行解。第六节对偶单纯形法⑷以lka为主元素，按原单纯形法在表中进行迭代运算。得到新的计算表。重复（1）－（4）。为什么？信息系统与管理学院8对偶单纯形法优缺点分析对偶单纯形法一般很少单独应用，主要用于灵敏度分析与整数规划等问题上。初始解（基解）可以是非可行解。当检验数都为非负时，就可以进行基变换，这时不需加入人工变量，可简化计算。对变量多于约束条件的线性规划问题，用对偶单纯形法可以减少计算量。具有很大的局限性：很难找到一个初始基，使对偶问题的解是基可行解。第六节对偶单纯形法信息系统与管理学院9第七节灵敏度分析信息系统与管理学院10灵敏度分析含义:指对系统或事物因外在条件变化显示出来的敏感程度的分析。第七节灵敏度分析在前面讲的线性规划问题中，都假定问题中的资源向量b，价值向量c，约束系数矩阵A是已知常数。信息系统与管理学院11研究对象实际上这些数往往是一些估计和预测的数字，如市场条件一变相应的价值向量C就会变化，A值随工艺技术条件的改变而改变，而b值则是根据资源投入后能产生多大经济效果来决定的决策选择。由此需要研究的问题是资源向量b，价值向量C，约束系数矩阵A变化时带来的影响？第七节灵敏度分析信息系统与管理学院12两类变化问题参数发生变化时，问题的最优解会有什么变化？参数在一个多大范围内变化时，问题的最优解或最优基不变？第七节灵敏度分析信息系统与管理学院13新的办法？有关参数发生改变后，以新的值重新用单纯形法计算，获取新的最优解。计算量大解决办法没有必要直接将有关变化反映到最终单纯形表中！为什么？每次运算只和当前基B有关！如何实施？第七节灵敏度分析信息系统与管理学院14jcBCBXb1x…mx1mx…nxij1cmc1mcnc1mcc1mxx1mbb1m10011,1,1mmmaa1nmnaa01,11mmiimicca1mniinicca0决策变量的价值系数基变量基变量价值系数基变量的取值基矩阵的逆矩阵左乘系数矩阵B-1A（B-1P1,…,B-1Pn）θ值决策变量的检验数B-1b(0,CN-CBB-1N)假设已得最优解，其最终单纯形表为：第七节灵敏度分析信息系统与管理学院15工厂生产优化的例子某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，产品售出可获得相应利润，相关数据如下表所示，那么该工厂应该如何安排生产使得利润最大？产品甲产品乙总数设备(台时)128原材料A(吨)4016原材料B(吨)0412利润(万元)23？第七节灵敏度分析信息系统与管理学院16解：设该工厂生产x1单位甲产品，生产x2单位乙产品，用数学表达式量化描述问题的目标准则，资源约束以及决策变量，建立如下数学模型：12121212max2328416412,0Zxxxxxxxx第七节灵敏度分析信息系统与管理学院1712123142512345max2328416412,,,,0Zxxxxxxxxxxxxxx将上述模型化为标准形式如下，建立单纯形表进行求解：第七节灵敏度分析信息系统与管理学院18解得该工厂应该安排生产产品甲4个单位，产品乙2个单位，可以获利最大为14万元。若该工厂决定不生产产品甲和产品乙，而将其所有资源出售。这时工厂考虑给每种资源定价，相应地满足出售条件的最优方案对应于对偶问题的最优解。即单位设备台时获利3/2万元，单位原材料A获利1/8万元就可以满足要求。第七节灵敏度分析信息系统与管理学院19工厂面临的若干新情况：1.原材料A的供应可能发生变化，变化范围为多大时，最优基保持不变？3.由于市场原因，产品乙的售价可能发生变化，变化范围为多大时，仍然可以按照当前最优方案进行生产？2.工厂决定扩大生产，现新调进4台设备投入生产，那么最优生产方案应如何调整？第七节灵敏度分析4.由于市场原因，产品甲的售价变为1，最优方案是否发生变化？产品甲的售价变为3呢？信息系统与管理学院205.工厂经过技术革新，生产产品甲的工艺发生了改变，每生产单位产品新工艺需要2个设备台时，原材料A5吨，原材料B2吨，相应产品利润提高到4万元，对生产计划有什么影响？6.由于市场变化，工厂考虑生产一种新产品丙，已知每生产单位产品丙需要使用设备2个台时，分别消耗原材料A、B为6吨和3吨；产品售出单位可获利5万元，决策层如何决定是否应该生产，如果要生产，应该安排生产多少？第七节灵敏度分析工厂面临的若干新情况：信息系统与管理学院21情况1：原材料A的供应可能发生变化，变化范围为多大时，最优基保持不变？'1122040.25040.5020.12500bBbBbb28168,32b解得即得变化范围为，最，优基不变。是多少？最优解不变？第七节灵敏度分析信息系统与管理学院22情况2：工厂决定扩大生产，现新调进4个设备台时投入生产，那么最优生产方案应该调整为多少？'11401/4044421/210421/21/8004bBbBb这时b列有负数，而检验数仍保持非正，即原问题为非可行解，对偶问题为可行解，故用对偶单纯形法求解。第七节灵敏度分析信息系统与管理学院23工厂面临的若干新情况：1.原材料A的供应可能发生变化，变化范围为多大时，最优基保持不变？3.由于市场原因，产品乙的售价可能发生变化，变化范围为多大时，仍然可以按照当前最优方案进行生产？2.工厂决定扩大生产，现新调进4台设备投入生产，那么最优生产方案应如何调整？第七节灵敏度分析4.由于市场原因，产品甲的售价变为1，最优方案是否发生变化？产品甲的售价变为3呢？信息系统与管理学院24第一步：将参数的改变反应到最终单纯形表中；第二步：检查原问题是否仍为可行解；第三步：检查对偶问题是否仍为可行解；第四步：分情况处理，继续进行计算。第七节灵敏度分析（1）参数发生变化时，问题的最优解会有什么变化？解决步骤：信息系统与管理学院25参数改变后的情况及其处理原问题对偶问题处理办法可行解可行解只需重新计算目标函数可行解非可行解用单纯形继续迭代计算非可行解可行解用对偶单纯形继续计算非可行解非可行解加入人工变量，编制新的单纯形重新计算第七节灵敏度分析信息系统与管理学院26第一步：将参数的变化设为一个变量△；第二步：将变量△反应到最终单纯形表中；第三步：根据最优解或最优基不变的条件确定变量△的范围；第四步：由变量△的范围计算得到参数的变化范围。第七节灵敏度分析（2）参数在一个多大范围内变化时，问题的最优解或最优基不变？解决步骤：信息系统与管理学院27课后习题P903.9（1），3.10（1）、（2）、（3）。课后作业信息系统与管理学院28某参数如果连续变化，使目标函数最优解发生变化的临界点在哪里？课外进一步思考参数线性规划第七节灵敏度分析信息系统与管理学院第三章运输问题第三章运输问题信息系统与管理学院第三章运输问题A3（9）A2（4）A1（7）B1（3）B2（6）B3（5）B4（6）信息系统与管理学院第三章运输问题例1.战略物资产品运输问题。已知3个后方加工厂的产量、4个前方基地的需求量，以及从各工厂到各基地单位产品运价，如下表，问后勤部门应如何调运产品，在满足军事需求量的前提下，使总运费最少？数学模型销地产地1B2B3B4B产量（吨）123AAA317119432101085749销量（吨）3656单位运价：万元/吨信息系统与管理学院第三章运输问题在经济、军事等领域，物资调运现象非常普遍。比如，对煤、钢铁等物资，在全国有若干生产基地，根据已有的交通网该如何制定调运方案，将这些物资运到各消费地点，而总费用要最小。此类问题称为运输问题信息系统与管理学院第三章运输问题运输问题早在20世纪三四十年代已为人们关注。比如，前苏联的康托洛维奇及希区柯克等人均研究过（康托洛维奇因研究此问题而获得1975年诺贝尔经济学奖），但把它与单纯形法联系起来则是50年代以后的事，由丹捷格（Dantzig）完成。信息系统与管理学院第三章运输问题第1节运输问题的数学模型第2节产销平衡运输问题的表上作业法第3节产销不平衡运输问题及其求解方法第4节总结、思考练习信息系统与管理学院第三章运输问题已知：有m个产地,1,2,,iAim可供应某种物资，其供应量（产量）分别为,1,2,,iaim有n个销地,1,2,,jBjn，其需要量（销量）分别为,1,2,,jbjn从iA到iB运输单位物资的运价（单价）为ijc。求总运费最小的调运方案？数学模型运输问题的数学语言描述：信息系统与管理学院第三章运输问题产销量表销地产地12n产量12m12maaa销量12nbbb运输问题的数据可汇总于产销量表和单位运价表中数学模型单位运价表销地产地12n12m111212121212nnmmmnccccccccc信息系统与管理学院第三章运输问题产销量与单位运价表销地产地12n产量12m111212121212nnmmmnccccccccc12maaa销量12nbbb可以把两表合二为一数学模型信息系统与管理学院第三章运输问题满足产销平衡条件，称为产销平衡问题，否则称为产销不平衡问题。求解运输问题，首先要判断产销平衡条件。我们首先讨论产销平衡问题。产销平衡条件：11nmjijiba数学模型信息系统与管理学院第三章运输问题数学模型决策变量销地产地12n12m111212121212nnmmmnxxxxxxxxx构建模型：设表示从Ai到Bj的运量ijx产销量与单位运价表销地产地12n产量12m111212121212nnmmmnccccccccc12maaa销量12nbbb1.确定决策变量信息系统与管理学院第三章运输问题数学模型11minmnijijijZcx构建模型：2.确定目标函数信息系统与管理学院第三章运输问题0(1,1)ijximjn3.确定约束条件数学模型i产地总产量总调出量？j销地总销量总调入量？非负约束供应约束需求约束ia1,1,2,,n