（精）第三章 运输问题.ppt

2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足： 运输问题的数学模型 例8 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见表3-33。 假定各条航线使用相同型号的船只，又各城市间的航程天数见表3-34。 又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求? 解 该公司所需配备船只分两部分。 (1) 载货航程需要的周转船只数。例如航线1，在港口E装货1天，E→D航程17天，在D卸货1天，总计19天。每天3航班，故该航线周转船只需57条。各条航线周转所需船只数见表3-35。 表3-35 (2) 各港口间调度所需船只数。有些港口每天到达船数多于需要船数，例如港口D，每天到达3条，需求1条；而有些港口到达数少于需求数，例如港口B。各港口每天余缺船只数的计算见 表3-36。 为使配备船只数最少，应做到周转的空船数为最少。因此建立以下运输问题，其产销平衡表见表3-37。 单位运价表应为相应各港口之间的船只航程天数，见表3-38。 用表上作业法求出空船的最优调度方案见表3-39。 解： 这是求获利最大的单目标的规划问题，用x1，x2分别表示Ⅰ，Ⅱ产品的产量，其线性规划模型表述为： 用图解法求得最优决策方案为：x1*=8, x2*=2, z*=64(元)。 从线性规划角度看，问题似乎已经得到了圆满的解决，但是： 第一，一般说来，一个计划问题要满足多方面的要求； 第二，线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容。 第三，线性规划解的可行性和最优性具有十分明确的意义，但那是针对待定数学模型而言的。 上述分析表明，线性规划并非完美无缺。现代决策强调定量分析与定性分析相结合，硬技术和软技术相结合，矛盾和冲突的合理性，妥协和让步的必要性。 1961年，查恩斯(A.Charnes)和库柏(w.w.Cooper)提出目标规划(goal programming)。 目标规划在处理实际问题时，承认各项决策要求，的存在有其合理性；在做最终决策时，不强调其绝对意义上的最优性。 二、目标规划的数学模型 例 2 假设在例1中，计划人员被要求考虑如下的意见： （1) 由于产品II销售疲软，故希望产品II的产量不超过产品I的一半； (2) 原材料严重短缺，生产中应避免过量消耗； （3）最好能节约4h设备工时； （4）计划利润不少于48元。 面对这些意见，希望达成一致意见：原材料使用限额不得突破；产品II产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。 目标规划涉及的相关概念： 1.偏差变量 对每一个决策目标，引入正、负偏差变量d+和d-,分别表示决策值超过或不足目标值的部分。按定义应有d+≥0,d- ≥0, d+*d- =0 2.绝对约束和目标约束 绝对约束是指必须严格满足的约束条件，它是硬约束，对它的满足与否，决定了解的可行性。目标约束是目标规划特有的概念，是一种软约束，目标约束中决策值和目标值之间的差异用偏差变量表示。 3.优先因子和权系数 不同目标的主次轻重有两种差别。一种是绝对的，用优先因子Pl表示，另一种差别是相对的，这些目标具有相同的优先因子，它们的重要程度可用权系数的不同来表示。 4.目标规划的目标函数 目标规划的目标函数由各目标约束的偏差变量及相应的优先因子和权系数构成。由于目标规划追求的是尽可能接近各既定目标值，也就是使各有关偏差变量尽可能小，所以其目标函数只能是极小化。应用时，有三种基本表达式： （1）要求恰好达到目标值。决策值超过或不足目标值都是不希望的，有 （2）要求不超过目标值，但允许不足目标值，不希望决策值超过目标值，有 （3）要求不低于目标值，但允许超过目标值，不希望决策值低于目标值，有 根据上述概念，例2的目标规划数学模型如下： 0 0 0 4 5 1 7 9 5 2 6 11 4 9 5 8 产 量 6 5 3 4 销 量 3 12 3 销地 产地 表 3-14（1） 二、有转运的运输问题 假定m个产地A1，A2，…,Am和n个销地B1,B2,…,B n都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有m+n个。可得一个扩大了的运输问题。令： ai:第i个产地的产量(净供应量)； bj:第j个销地的销量(净需要量); xij:由第i个发送地