第3章特殊类型的线性规划22

第三章特殊类型的线性规划一般意义的线性规划问题==第一节运输问题先看一个具体的例子——例3-1

某厂下属三个加工厂同生产一种产品，每天的生产量分别是A1=8吨，A2=7吨，A3=10吨；该工厂把这些产品分别运往四个地区的门市部销售，各门市部的销售量分别为B1=3吨，B2=4吨，B3=9吨，B4=9吨。已知从各加工厂到各门市部的每吨运费如下表所示。问该工厂如何制定调运产品的方案，在满足各门市部销售量的情况下，使总的费用为最少？B1B2B3B4A122316A211623A347108先建立数学模型假设从工厂到门市部的运输量为则有Cij为工厂到门市部单位物资的运价ai为第i个工厂的产量bj为第j个门市部的销售量该问题数学模型的特点工厂有3(m)个，门市部有4(n)个有3×4(

m×n)个变量有3+4(m+n)个约束方程用单纯形法求解需添加7个人工变量变量数增加为19个，求解计算量大本例中所建立的数学模型一般意义上的系数矩阵系数矩阵的每一列元素中均只有两个元素为1，其余元素均为零本例中，工厂的产量与门市部的销量相等，称为产销平衡的运输问题。某厂下属三个加工厂同生产一种产品，每天的生产量分别是A1=8吨，A2=7吨，A3=10吨；该工厂把这些产品分别运往四个地区的门市部销售，各门市部的销售量分别为B1=3吨，B2=4吨，B3=9吨，B4=9吨。产销平衡的运输问题一定有最优解例3-2为了简化计算过程，利用运输问题系数矩阵的特点，在单纯形法的基础上，创造了一种专门求解运输问题的方法，称为表上作业法。表上作业法的求解过程也包含如下三个关键步骤：（1）初始基可行解（也称初始运输方案）的确定；（2）基可行解检验数的计算与最优判别；（3）非最优基可行解的改进（迭代）。

例3-3

假设某地区有三个交通发生点和四个交通吸引点，交通发生点的出行产生量ai、交通吸引点的出行吸引量bj以及各交通发生点与吸引点之间的运输费用如下表所示。问如何组织交通，才能使总的运输费用最少？

交通吸引点交通发生点D1D2D3D4aiO144325O2103475O399845bj162615求解该问题分三个步骤确定初始方案检验该方案是否为最优方案调整方案计算停止是否确定初始方案的方法之一

西北角法

西北角法的基本思想是优先产销平衡表的左上角（西北角）的供应关系。步骤一确定初始方案在逐步确定初始运输方案时，一般每步要经过两个过程，先是根据运输费用确定供应关系，然后根据供需要求进行运量分配。为了方便，将产销平衡与运输费用表拆成运输费用与运量分配表。

交通吸引点交通发生点D1D2D3D4aiO144325O2103475O399845bj162615产销平衡与出行费用表步骤一确定初始方案

交通吸引点交通发生点D1D2D3D4O14432O210347O39984运输费用表

交通吸引点交通发生点D1D2D3D4aiO15O25O35bj162615运量分配表从运量分配表的最左上角（西北角）的格子开始。让发生点O1的物资尽可能多地运往吸引点D1。由于吸引点D1需要的物资总量只有1，而发生地O1要求运出的物资总量为5，所以O1要运出的物资总量中1个单位运至D1，即x11=1，将此运量１填入运量分配表的（O1,D1）格子。这时吸引点D1物资需求量已经满足，不再需要其他任何发生地运来物资，由平衡条件得x21=0，x31=0。１步骤一确定初始方案

交通吸引点交通发生点D1D2D3D4O14432O210347O39984出行费用表

交通吸引点交通发生点D1D2D3D4aiO1１5O25O35bj162615运量分配表从运量分配表当前的最左上角（西北角）的格子（O1,D２

）开始。让发生点O1的物资尽可能多地运往吸引点D２。由于吸引点D２需要的物资总量为６，而发生地O1当前能运出的物资总量为４，所以O1能运出的物资总量中４个单位运至D２，即x1２=4，将此运量４填入运量分配表的（O1,D２）格子。这时发生地O1物资运出量已经满足，不能再向其他任何吸引点运送物资，由平衡条件得x1３=0，x1４=0。４步骤一确定初始方案

交通吸引点交通发生点D1D2D3D4O14432O210347O39984出行费用表

交通吸引点交通发生点D1D2D3D4aiO1１４5O25O35bj162615运量分配表从运量分配表当前的最左上角（西北角）的格子（O２,D２）开始。让发生点O２的物资尽可能多地运往吸引点D２。由于当前吸引点D２需要的物资总量只有２，而发生地O２要求运出的物资总量为5，所以O２要运出的物资总量中２个单位运至D２，即x２２=２，将此运量２填入运量分配表的（O２,D２）格子。这时吸引点D２物资需求量已经满足，不再需要其他任何发生地运来物资，由平衡条件得x３２=0。２步骤一确定初始方案

交通吸引点交通发生点D1D2D3D4O14432O210347O39984出行费用表

交通吸引点交通发生点D1D2D3D4aiO1１４5O2２5O35bj162615运量分配表从运量分配表当前的最左上角（西北角）的格子（O２,D３）开始。让发生点O２的物资尽可能多地运往吸引点D３。由于吸引点D３需要的物资总量只有２，而发生地O２当前能运出的物资总量为３，所以O２运出的物资总量中２个单位运至D３，即x２３=２，将此运量２填入运量分配表的（O２,D３）格子。这时吸引点D３物资需求量已经满足，不再需要其他任何发生地运来物资，由平衡条件得x３３=0。２步骤一确定初始方案

交通吸引点交通发生点D1D2D3D4O14432O210347O39984出行费用表

交通吸引点交通发生点D1D2D3D4aiO1１４5O2２２5O35bj162615运量分配表从运量分配表当前的最左上角（西北角）的格子（O２,D４）开始。让发生点O２的物资尽可能多地运往吸引点D４。由于吸引点D４需要的物资总量为６，而发生地O２当前能运出的物资总量为１，所以O２运出的物资总量中１个单位运至D４，即x２４=１，将此运量１填入运量分配表的（O２,D４）格子。这时发生地D２物资需求量已经满足，不能再向其他任何吸引点运来物资。１步骤一确定初始方案

交通吸引点交通发生点D1D2D3D4O14432O210347O39984出行费用表

交通吸引点交通发生点D1D2D3D4aiO1１４5O2２２１5O35bj162615运量分配表从运量分配表当前的最左上角（西北角）的格子（O３,D４）开始。让发生点O３的物资尽可能多地运往吸引点D４。由于当前吸引点D４需要的物资总量为５，而发生地O３当前能运出的物资总量为５，所以O３运出的物资总量中５个单位运至D４，即x３４=５，将此运量５填入运量分配表的（O３,D４）格子。５步骤一确定初始方案

交通吸引点交通发生点D1D2D3D4O14432O210347O39984出行费用表

交通吸引点交通发生点D1D2D3D4aiO1１４5O2２２１5O3５5bj162615运量分配表已经找到了一个初始方案＝６１步骤一确定初始方案最小元素法的基本思想是就近供应，即依据单位运价表中最小的运价来确定供需关系。

确定初始方案的方法之二

最小元素法步骤一确定初始方案

交通吸引点交通发生点D1D2D3D4O14432O210347O39984运输费用表

交通吸引点交通发生点D1D2D3D4aiO15O25O35bj162615运量分配表551121从出行费用表中选择最小费用项，确定相应的运量，并使其满足出行总量平衡条件。初始方案的费用为63步骤一确定初始方案最优方案的判别

运输方案的最优性判别，实质上与单纯形法是一样的。首先，计算运量分配表中每个空格（即非基变量）的检验数，然后判别每个检验数的正负。因为运输问题是求目标函数极小化的问题，所以，当所有≥0时，此时的运输方案即为最优运输方案，否则，再改进当前的运输方案。求检验数的方法很多。常用方法有两种：闭回路法和位势法。步骤二最优方案的判别

在原方案的分配表中，从一个空格开始作一条闭回路，这个闭回路的边只能是水平或垂直的；而它的转角，除了开始这个空格之外，其余的都是填有数字的格（有交通量的格）。判别最优方案的方法之一

闭回路法步骤二最优方案的判别

交通吸引点交通发生点D1D2D3D4aiO1１４5O2２２１5O3５5bj162615运量分配表可以证明，运量分配表中的任意一个空格与所有的数字格组成的格子中，一定有且仅有一个闭回路步骤二最优方案的判别根据闭回路求检验数每一个空格对应一个检验数每一个空格的检验数根据该空格的闭回路确定检验数的计算起点空格的运费为正第一个转角的运费为负第二个转角的运费为正第三个转角的运费为负

…

…

…

…

…

…如此正负交替直至回到起点空格将这些数字相加，得到该空格的检验数步骤二最优方案的判别偶数转角运费为正奇数转角运费为负

交通吸引点交通发生点D1D2D3D4aiO1１４5O2２２１5O3５5bj162615运量分配表

交通吸引点交通发生点D1D2D3D4O14432O210347O39984出行费用表检验数λ31=9-4+7-3+4-4=9检验数的含义若存在某检验数小于0，则对应于该检验数的出行量增大，总出行费用将减少。若所有的检验数都为非负，则总的出行费用将不可能减少。步骤二最优方案的判别得到如下的检验数表：

D1D2D3D4O1-2-6O27O3997

交通吸引点交通发生点D1D2D3D4aiO1１４5O2２２１5O3５5bj162615运量分配表步骤二最优方案的判别判别最优方案的方法之二

势位法步骤二最优方案的判别方案的调整若存在检验数小于0，则对应于该检验数的出行量增大，总出行费用将减少，说明可能存在总费用更小的运输方案。步骤三方案的调整步骤三方案的调整选择一个负检验数找出该负检验数对应的闭回路从空格出发，沿闭合回路前进，在各奇数次转角点数字（即出行交通量）中，选择最小值K在闭合回路中，在各奇数次转角点的数字都减K，在各偶数次转角点的数字都加K步骤三方案的调整检验数D1D2D3D4O1-2-6O27O3997选择一个负检验数

交通吸引点交通发生点D1D2D3D4O1１４O2２２１O3找出该负检验数对应的闭回路从空格出发，沿闭合回路前进，在各奇数次转角点数字（即出行交通量）中，选择最小值Kmin（4，1）=1在闭合回路中，在各奇数次转角点的数字都减K，在各偶数次转角点的数字都加K

交通吸引点交通发生点D1D2D3D4O1１31O23２0O3对新得到的分配方案，继续进行检验。检验数D1D2D3D4O1-2O276O33310

交通吸引点交通发生点点D1D2D3D4O1１31O23２O3５存在负检验数，目前的方案没有达到最优步骤三方案的调整检验数D1D2D3D4O1-2O276O3331选择一个负检验数

交通吸引点交通发生点D1D2D3D4O1１31O23２O3５找出该负检验数对应的闭回路从空格出发，沿闭合回路前进，在各奇数次转角点数字（即出行交通量）中，选择最小值Kmin（3，2）=2在闭合回路中，在各奇数次转角点的数字都减K，在各偶数次转角点的数字都加K

交通吸引点交通发生点D1D2D3D4O1１121O2500O3５对新得到的分配方案，继续进行检验。

交通吸引点交通发生点D1D2D3D4O1１121O25O3５检验数D1D2D3D4O1O2726O3333所有的检验数都为非负，则总的出行费用将不可能减少，目前得到的方案为最优的运输方案。运输问题的作业教材习题3-2工程中有些线性规划问题要求解为整数如：

以人员、车辆等规划对象原有的计算方法得到的解存在非整数的可能第二节

整数规划

求解整数规划的方法—分枝定界法先看一个实例先不考虑整数约束，解相应的线性规划问题为了讨论方便，将原线性规划问题称为L1。L1的最优解为x1=2.25，x2=3.75，Z=41.25例3-4L1的最优解为x1=2.25，x2=3.75不满足整数条件划分可行域取x2≤3，x2≥4L2L3任取一个没有满足整数条件的变量L2的最优解为x1=1.8，x2=4，Z=41L3的最优解为x1=3，x2=3，Z=39L2L3已经得到整数解L2的最优解为x1=1.8，x2=4不满足整数条件划分可行域取x1≤1，x1≥2L4L5L4的最优解为x1=1，x2=4.44，Z=40.444L5无最优解L4的最优解为x1=1，x2=4.44不满足整数条件划分可行域取x2≤4，x2≥5L6L7L6的最优解为x1=1，x2=4，Z=37L7的最优解为x1=0，x2=5，Z=40原问题LP1新问题LP2新问题LP3新问题LP5新问题LP4新问题LP7新问题LP6直到找到最优整数解或无最优解汇总整数解非整数解非整数解无最优解整数解整数解非整数解总结：分枝定界法思路：首先不考虑解为整数的要求，用单纯形法求最优解，以此作为目标函数值的上限或下限；其次，选择其中一个非整数的变量，根据与两侧相近的整数划分可行域，在缩小的可行域内寻求最优整数解，以此作为目标函数值的上限或下限；不断重复以上过程，直到每一个可能进一步分解的非整数都找到整数解时为止，整数规划作业教材习题3-70-1整数规划0-1规划是指变量只能取0或1的线性规划，是一种特殊的整数规划。在进行实际问题最优决策和处理问题时常常会碰到这样的0-1规划。例3-5

某道桥公司在同一时间内可参加A1、A2、A3、A4四项工程的投标。这些项目要求的工期相同。公司根据招标文件和本公司的技术水平对每项工程进行了仔细的研究和计算，将各项工程的预期利润，主要工序的工程量及本企业的施工能力见下表。问该公司对哪几种项目投标可能获得的总利润最大？试建立这个问题的数学模型。工程项目预期利润（万元）土石方量（m3）混凝土量（m3）其他材料（m3）A1542002802500A282300880480A37.548003001500A4923009005200施工能力1200016009000建立模型设则建立的数学模型0-1规划的一般形式0-1规划的求解方法——穷举法每个变量都只取0，1两个值，变量取值的0-1组合是有限的。先列出各变量分别取0或1值的每一种组合，然后在满足约束条件的变量的0-1组合中找出使目标函数达到最优值的组合即是该0-1规划的最优解。用这种方法求解变量个数为n的0-1规划，通常需检查2n个组合计算量大，随变量数量的增加呈集合级数增长设计一种方法，只要检查变量取值的一部分就能得到原问题的最优解。这种方法称为隐枚举法。例3-6解：首先，通过试探的方法找到一个可行解。容易看出,(x1,x2,x3)=(1,0,0)是满足约束条件的可行解。相应的目标函数值为S=3。对于最大化问题，希望S≥3，因此，增加一个约束条件过滤条件新的0-1规划问题为（0）全部枚举的方法，3个变量有8种组合原先4个约束方程，需要32次计算增加过滤条件后，可减少计算次数解约束条件是否满足条件？S值（0）（1）（2）（3）（4）（0，0，0）0（0，0，1）5-11015（0，1，0）-2（0，1，1）315（1，0，0）311103（1，0，1）802118（1，1，0）1（1，1，1）626（0）0-1规划作业教材习题3-5第三节资源分配问题

有n项任务，分配给n个人去完成，要求每个人完成其中一项任务，每项任务只交给其中一个人完成，已知每个人完成各项任务的成本（或效率），求使总成本最少的分配方案。

目的地车辆编号D1D2D3D4D5D6146665559202822481256225913282239502786446314547545856544644331606322434243364设某运输队有6辆卡车，需分派驶往6个不同的目的地，由于各辆卡车的性能、消耗和效率不同，因而驶往各目的地的运输成本也不同，如下表所示。试求能使总成本最低的车辆分派方案。例3-7效率矩阵建立数学模型资源分配问题的一般模型minZ=s.t.运输问题整数规划资源分配问题资源分配问题的求解方法—匈牙利法定理

效率矩阵的任意一行（列）各元素中分别减去同一常数，得一变换了的矩阵，则以之为效率矩阵的分派问题最优解与原问题的最优解相同。

匈牙利法的指导思想设法对效率矩阵进行变换，使变换后的效率矩阵中有n个位于不同行不同列的零元素（以下称为独立零元素），没有负元素。令n个独立零元素对应的n个xij＝１，其余的xij＝0匈牙利法的解题步骤——例3-8

有5辆公交车可以在5条公交线路上行驶。不同车辆在不同的路线上发生的年平均交通事故数如下表所示。这5辆公交车如何分配，才能使全年的总事故数最少？匈牙利法的解题步骤

线路编号车辆R1R2R3R4R5D173328D2108697D392706D460835D553427使费用矩阵每行中出现零元素在各行中减去各行的最小元素使费用矩阵出现0元素332886972706083553427110620312706083531205初始的费用矩阵110620312706083531205第一列、第五列中无0元素。在第一列、第五列中分别减该列的最小元素。使费用矩阵出现0元素2110512030627053083401204费用矩阵每行、每列中都出现了0元素检验是否存在位于

不同行不同列的n个0元素检验是否存在不同行列的0元素2110512030627053083401204行检验：若某行只有一个零元素，则给这零元素加“Δ”，该零元素为独立零元素。若某行零元素多于一个，则暂不标号。每行、每列只能有一个独立零元素检验是否存在不同行列的0元素2110512030627053083401204列检验：若某列只有一个零元素，则给这零元素加“Δ”，该零元素为独立零元素。若某列零元素多于一个，则暂不标号。没有得到位于不同行不同列的n个0元素方案的变换方案变换在所有没有被分配的行打上“”号。2110512030627053083401204在已打“”号的行中找出打“”的列，并打“”。在已打“”号的列中找出打“Δ”的行，并打“”。重复以上过程，直到无法打“”时为止。方案变换2110512030627053083401204对所有打“”号的列和未打“”号的行划线。这些线可以将所有的0元素至少覆盖一次。如果是MM矩阵，而又要使最优解分配在0元素位置上，划线数量应为M。本例还没有达到最优解。方案变换在未划线的元素中找出最小元素2110512030627053083401204未划线的各行元素减去这个最小元素已划线的各列元素加上这个最小元素1000412040516043084401214对新的费用矩阵进行行检验与列检验1000412040516043084401214行检验：若某行只有一个零元素，则给这零元素加“Δ”，该零元素为独立零元素。若某行零元素多于一个，则暂不标号。1000412040516043084401