运筹学-第二三章-运输问题

2023/2/71第二章运输问题

(TransportationProblem,TP)运输问题的数学模型运输问题的求解产销平衡的运输问题求解产销不平衡的运输问题求解应用举例软件应用2023/2/722.1运输问题的数学模型例1

现需将三个供应地KansasCity、Omaha、DesMoines的物品运往三个货物需求地Chicago、St.Louis、Cincinnati，各供应地的供应量、各需求地的需求量和各供应地运往各需求地的每单位物品的运费如表。如何安排运输，可使得总费用最小？ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200100300600275175150产销平衡2023/2/73设为从供应地i调往需求地j

的运输量

2023/2/74产销平衡模型的一般形式这是一个线性规划满足2023/2/752.2运输问题的求解2.2.1产销平衡的运输问题求解求初始基本可行解西北角法最小元素法伏格尔法求最优解 闭合回路法（略）位势法2023/2/76产销平衡的运输问题2023/2/77求初始基本可行解---“西北角法”5025ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200(50)0

100300275175

125

150(0)150100275特点：数字格数=行数+列数-1，其余为空格基解：x11=150,x21=50,x22=100,x23=25,x33=2752023/2/78求初始基本可行解---“最小元素法”175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200(0)10025300275(75)01751502575200特点：数字格数=行数+列数-1，其余为空格基解：x12=25,x23=125,x23=175,x31=200,x32=752023/2/79求初始基本可行解---“伏格尔法”ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200(25)10030027517515017510025150150特点：数字格数=行数+列数-1，其余为空格基解：x13=150,x21=175,x31=25,x32=100,x33=150西北角法最简单，伏格尔法效果较好2023/2/710求最优解

闭合回路法（略）位势法2023/2/711DLP互补松弛条件：2023/2/712位势法步骤：Step1：确定初始基本可行解

（西北角法，最小元素法，伏格尔法）Step2：检验计算各点位势值计算非基变量（空格）的检验数检验非基变量的检验数是否0。若是，得到最优解；若不是，转入Step32023/2/713Step3：选择进基变量在小于0的非基变量的检验数中，选择最小的，它所对应的变量进基，也即它从空格变为数字格Step4：选择出基变量寻找进基变量的闭合回路选择负号格最小的运量为调整运量它对应的变量出基，也即它从数字格变为空格Step5：修正表格，得到新的基本可行解。转入Step22023/2/714以例1的最小元素法得到的初始基本可行解开始175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply67481151011122001003006002751751502575200Step12023/2/715

ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111220010030027517515020001-378107517512525Step2计算各点位势值

2023/2/716ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111220010030027517515001-37810-152-1Step3计算各个空格的检验数，判断是否最优？2023/2/717175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply67481151011122001003006002751751502575200（+）（+）（-）（-）Step4确定格子（1，1）的闭合回路（也即确定了进基变量）；确定该闭合回路的负号格，得到负号格的最小运量；确定出基变量

2023/2/718175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111220010030060027517515025100175Step5修正表格再转入Step2

2023/2/719175125ToFromKansasCityOmahaDesMoinesvjChicagoSt.LouisCincinnatiui67481151011126710600-210251001750431转入Step2计算各个空格的检验数，判断是否最优？--最优2023/2/72023/2/721课堂练习如何安排运输，可使总运费最小？2023/2/7222.2.2产销不平衡的运输问题求解产量大于销量（供大于求）的运输问题销量大于产量（供不应求）的运输问题

转化为产销平衡的运输问题2023/2/723对例1做些修改ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200100300275175200产量大于销量（供大于求）的情形2023/2/724增加一个虚拟需求地Virtualcity，设其需求量为50，单位运费为0，从而把产销不平衡问题转化为产销平衡问题

ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111220010030027517520050000650Virtualcity模型没有改变！2023/2/725对例1做些修改ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112280100300275175150销量大于产量（供不应求）的情形2023/2/726增加一个虚拟供应地Virtualcity，设其供应量为80，单位运费为0，从而把产销不平衡问题转化为产销平衡问题ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112280100300680275175150Virtualcity00080模型没有改变！2023/2/727课堂练习如何安排运输，可使总运费最小？2023/2/728转化为产销平衡问题如下：2023/2/729课堂练习如何安排运输，可使总运费最小？2023/2/730转化为产销平衡问题如下：2023/2/731注意：有相同的运价，如何选择？有相同的需求量和供应量，如何处理？进基变量有相同的检验数，如何处理？有相同的调整运量，如何处理？对最大化的问题，如何处理？2023/2/732（1）带罚款的运输问题设有运输问题：From\ToB1 B2 B3供应量A1 5 1 7 10A2 6 4 6 80 A3 5 2 515需求量707050供不应求的情形！若销地B1、B2、B3的需求没有满足，则单位罚款成本分别为4、3、2，求总费用最小的运输方案2.3应用举例2023/2/733设为从工厂Ai运到销售点Bj

的运输量

如何化为供需平衡的运输问题呢？2023/2/734求解过程见教科书销售点工厂A1A2A3需求量B1B2B3供应量565142765707050158010A443285转化为供需平衡的运输问题2023/2/735（2）指派问题

现由四人负责承担四家公司的税务工作，规定每个工作人员只能负责一家公司，已知各费用如下：

问如何安排，可使总费用最小？2023/2/736转化为供需平衡的运输问题2023/2/737求解过程见教科书2023/2/738（3）生产计划问题

某企业和用户签定了设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度末的交货量如表。若生产出的设备当季度不交货，每台设备每季度需支付保管费用0.5万元，试问在遵守合同的条件下，企业应当如何安排生产计划，才能使年消耗费用最低？2023/2/739问题转化为2023/2/740设xij是i季度生产用于j季度销售的量如何化为供需平衡的运输问题呢？2023/2/741转化为供需平衡的运输问题M为充分大的数2023/2/742(4)特殊要求的运输问题有A、B、C三个工厂生产同一种玩具，供应给Ⅰ、Ⅱ、Ⅲ、Ⅳ四个地区进行销售。各工厂的产量，各地区的需求量以及运输价格如表。试求总费用最省的运输方案2023/2/743设xij是第i工厂运往第j地区的运量如何化为供需平衡的运输问题呢？2023/2/744转化为供需平衡的运输问题M为充分大的数2023/2/7452.4软件应用

对例1，输入到LINDO的主界面从Solve菜单中选择Solve命令，或者单击按钮

同理其他例题2023/2/746对例1，输入到LINGO

的主界面同理其他例题2023/2/72023/2/748第三章整数规划引论整数规划模型纯0-1模型混合0-1模型整数规划的求解指派问题软件应用2023/2/7493.1引论定义整数规划：部分或全部变量限制为整数的规划问题整数线性规划：变量限制为整数的线性规划问题整数规划分类如不加特殊说明，一般指整数线性规划对于整数线性规划模型大致可分为两类：纯（完全）整数规划：变量全限制为整数混合整数规划：部分变量限制为整数整数规划的求解比线性规划要困难得多！2023/2/750考虑

其最优解为

若要求x1,x2为整数，则最优解为

无论“四舍五入”，还是“只舍不入”、“只入不舍”，都不能通过求解上面的线性规划得到最优解

2023/2/751背包问题（投资问题）某公司现有资金100万，有5个项目可以投资，每个项目的投资成本和利润如下：

如何安排投资，可使总利润最大？3.2整数规划模型2023/2/752令表示项目j

被采纳表示项目j

不被采纳则模型为

，2023/2/753附加条件项目1和项目3至少采纳一个：项目2和项目5不能同时采纳：项目1仅在项目2采纳后才可考虑是否采纳：项目1仅在项目2和3同时采纳后才可考虑是否采纳：项目1，2，3不能同时采纳：或者选择项目1和2，或者选择项目3：2023/2/754集合覆盖问题某部门准备建消防队，有五个候选队址。将其管辖地区划分为七个区域，每个候选队址可覆盖若干不同区域（覆盖指规定时间内可达到），如下表。已知候选队址1、2、3、4、5建设消防队的建设费用分别为3.1、2.3、3.7、2.6、1.8（百万元）。问应选哪几个队址可覆盖七个区域，且建设费最小?2023/2/755则模型为2023/2/756运输问题工厂A1和A2生产某种产品，由于这种产品供不应求，故需要再建一家工厂，可供选择的建厂方案有A3、A4、A5，生产的产品运往B1,B2,B3,B4。已知单位运价、需求量和年生产能力如表所示。若工厂A3、A4、A5开工后，每年的生产费用分别为1200、1500、2000元。问如何决定，可使总费用最小？2023/2/757设xij为Ai

工厂运到Bj仓库的数量(i

＝1,…,5，

j＝1,2,3,4)，要在A3,A4,

A5

中选择一家建厂，所以设2023/2/758生产计划问题

某机器制造厂可生产四种产品，对于三种主要资源（钢材，人力，能源）的单位消耗及单位利润见表。问如何安排生产，可使总利润最大？2023/2/759设xj表示第j种产品的生产量(j=1，2，3，4)，则模型为最优解为最大利润为

z=6660

增加其他要求后如何建模？

2023/2/760（1）固定成本增加假设：产品3的生产需要用某一特定机器，固定成本为3000；产品2和4的生产需要用同一特定机器，固定成本为1000试建立最佳生产计划模型2023/2/761

目标函数修正为

增加约束

其中M为充分大的正数(本例)若x3>0，则显然有y3=1若x3=0，由于目标函数中-3000y3的存在，必有y3=0.另一部分同理

2023/2/762得到数学模型2023/2/763（2）批量生产增加假设：产品4要求批量生产，批量为不少于500件试建立最佳生产计划模型增加约束2023/2/764得到数学模型2023/2/765（3）销售政策：增加假设：市场上要求4种产品中至少3种的供应量不少于100件试建立最佳生产计划模型2023/2/766定义四个0-1变量yj

(j=1，2，3，4)

增加约束2023/2/767得到数学模型2023/2/768（4）规模经济增加假设：产品3售价20，成本如下：试建立最佳生产计划模型2023/2/7692023/2/770得模型为产品3的单位销售价为20，则相应利润为2023/2/72023/2/772选址问题

有m

个地方可建厂，预计产量分别为ai(i=1,…,m)，建设费用分别为

fi(i=1,…,m)

。现在有n

个销点，各销点的需求量分别为bj(j=1,…,n)，厂址i

到销点j

的运价为cij。现要求从m个厂址中选择Ｍ个建厂。问如何选择，可使建设费用和运输费用之和最小？（要求满足需要）2023/2/773设xij为厂址i向销点j的运送量(i=1,2,…,m,j=1,2,…,n)，并设则模型为2023/2/774排序问题

三种产品A,B,C各要在三台机器上加工，加工顺序是1-2-3，其他数据如表。每台机器同时只能加工一种产品。问如何安排，可以在最短的时间内完成三种产品的加工？2023/2/775设xij为产品i在机器j上开始加工的时间(i=A,B,C，

j=1,2,3)；z为从开始到所有产品加工完所用的时间；yj为0-1变量，表示j

机器加工产品的顺序(j=1,2,3)

2023/2/776得模型为其中M是充分大的正数2023/2/7770-1变量使用技巧条件

等价于其中M为充分大的正数2023/2/778ai1

x1+ai2

x2

+…+ainxn

bi(i=1,…,m)为互相独立m

个约束，但只有一个起作用ai1

x1+…+ainxn

bi+(1-yi)M

(i=1,…,m)y1

+…+ym=1yi=0或1，M>0条件

其中M是充分大的正数

等价于2023/2/779条件等价于

2023/2/7803.3整数规划的求解含0-1变量的整数规划纯0-1规划：枚举法，隐枚举法（过滤隐枚举法；分枝隐枚举法）混合0-1规划：特别处理不含0-1变量的整数规划：分枝定界法，割平面法2023/2/781纯0-1规划求解之枚举法：考虑变量的每一种可能取值（总数有限），通过比较得到最优解枚举法只适用于变量个数较少的情形！国际象棋的例子2023/2/78251234678f1=0x3=0x2=0f2=15x3=1x1=0f3=-(不可行)x3=0x2=1f4=-(不可行)x3=1f5=20x3=0x2=0x3=1f6=35x1=1f7=-(不可行)x2=1x3=0f8=-（不可行)x3=12023/2/783纯0-1规划求解之隐枚举法：只选择性检查一部分变量取值，就可能得到最优解2023/2/784√√√√√√√√√√

2023/2/7850-1规划的隐枚举法的具体步骤第一步：将模型标准化：1.目标函数为最小优化2.目标函数中变量的系数都为正（x

1-x）3.目标函数中变量按系数值从小到大排列，约束函数中变量的排列次序也做相应改变第二步：在标准化后的模型中，令所有的变量为0，以此作为母方案。检验母方案是否满足所有约束条件，如果满足即为问题的最优解，否则进入第三步第三步：分枝与择优2023/2/72023/2/786不含0-1变量的整数规划之分枝定界法

2023/2/7872023/2/788maxz=2x1

+x2

s.t.

x2

3

3x1

+x2

12

x1+x2

5

x1，x2

0

且为整数例

2023/2/789z=02023/2/790分枝定界法2023/2/791B1问题2023/2/792B1问题2023/2/793B1问题2023/2/794B2问题2023/2/795B2问题2023/2/796B2问题2023/2/797不含0-1变量的整数规划之割平面法：求得线性规划的最优解后，通过增加“割约束”割掉最优解，但不割掉任何整数可行解，逐步求得原问题的最优解割约束2023/2/798maxz=2x1

+x2

s.t.x2

3

3x1

+x2

12

x1

+x2

5

x1，x2

0

且为整数例2023/2/799相当于增加约束：2023/2/7100增加割约束之后的单纯形表2023/2/7101得到最优解：2023/2/7102变换一下还可以得到另一个最优解：2023/2/7103整数规划模型举例：选择/是非问题、大型设备问题等整数规划求解纯0-1规划：枚举法、隐枚举法不含0-1变量的整数规划：分枝定界法、割平面法指派问题：匈牙利法2023/2/71043.4指派问题指派问题的数学模型

现要安排四位工作人员完成四种工作，每人只完成一种。记工作种类分别为A、B、C、D，工作人员分别为甲、乙、丙、丁，已知工作人员完成各工作所需要的费用如表所示。应指派何人去完成何项工作，可使所需的总费用最少？

2023/2/7105设

指派问题模型为2023/2/7106练习1

现由五家建筑公司完成建造五家新商店，规定每家建筑公司只能建造一家商店，已知各费用如表。问如何安排，可使总费用最小?

2023/2/7107Ex3.1-(7)

分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如下表。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案2023/2/71082023/2/72023/2/7109指派问题的求解之“匈牙利算法”

Step1：对矩阵(cij)做如下变换，使其在各行各列中都出现0每行元素减去该行的最小元素（若该行已有0则不必变换）再将每列减去该列的最小元素（若该列已有0则不必变换）2023/2/72023/2/7110Step2：进行试指派以寻求最优解。为此按如下五个分步骤进行从只有一个0的行/列开始，给这个0加圈（下记为），然后划去所在的列/行的其它0（下记为Ø）。这表示该列/行所代表的任务已被指派在剩余的行列中，给只有一个0的行/列的0加圈，然后划去所在列/行的0重复进行上述步骤，直到所有0都被圈出或划掉为止若同行/列不止一个0（表示对这个人可以从几项任务中指派其一），则可用不同的方案去试探。从所剩0最少的行/列开始，比较该行/列0所在列/行中0的数目，选择0少的列/行的0加圈（表示选择性多的要“礼让”选择性少的）。然后划掉同行/列的其它0。反复进行直到所有0都已被圈出或划掉若的数目m

等于矩阵阶数

n

，则得到指派问题的最优解。若m<n

，则转入Step32023/2/72023/2/7111例2023/2/7112找到了4个不同行不同列的元素，所以该问题的最优解矩阵是

意即：指定甲完成工作A乙完成工作C丙完成工作B丁完成工作D所需最少总费用为322023/2/7113例：求如下系数矩阵所对应的指派问题由于独立

元素的个数m=4<5，所以解题没有完成，应按下面的步骤继续进行2023/2/7114Step3：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素。为此按以下步骤进行：对没有的行打

对已打的行中包含有Ø

元素的列打

再对有打的列中含有的行打

重复上述步骤直到得不出新的打的行、列为止对没有打的行画横线，对打的列画纵线，这就得到了能够覆盖所有0元素的最少直线数。令直线数为l。若l<n，则说明必须再变换当前的系数矩阵，才能找到n

个独立的

元素，为此转入Step4。若l=n，应回到