线性规划的扩展II课件

指派问题及其解法

n项任务（B1,B2,…,Bn)由n个人(A1,A2,…,An)去完成，每项任务交给一人，每人只有一项任务。第i个人Ai去做第j项任务Bj的工作效率（如工时、成本或价值等）为Cij。问如何安排人员使总工作效率最好？设Xij表示Ai完成Bj工作，并令

1当指派Ai去完成Bj工作

Xij=0当不指派Ai去完成Bj工作第四章线性规划的扩展(II)第四章线性规划的扩展(II)指派问题数学模型的标准型

MINZ=（Cij≥0)

（i=1,2,…,n)(j=1,2,…,n)

Xij

皆为0或1

由Cij

组成的方阵C=(Cij

)n×n

称为效率矩阵

第四章线性规划的扩展(II)指派问题标准型的求解－匈牙利法指派问题有以下性质：

若从效率矩阵C的任何一行（列）各元素中分别减去一个常数K（K可正可负）得到新矩阵D,则以D为效率矩阵的指派问题与原问题有相同的解，但最优值比原问题最优值小K。

匈牙利法条件：

MIN、i=j、Cij≥0第四章线性规划的扩展(II)非标准指派型问题的标准化

MAX、i≠j、Cij<0、Cij

缺省例4－5：将下表所示指派问题（利润）标准化：甲乙丙丁ABC

32-212-20-110第四章线性规划的扩展(II)

（1）目标利润MAX：MAX→MIN?

找出最大元素，分别用它去减每一个非缺省元素。新矩阵对应的目标即为MIN，而且也使Cij≥0。（2）C的缺省：缺省意味着不胜任，因此在缺省处填上充分大的正数，使成本很大。（3）i≠j：添上一行（一列）零元素。第四章线性规划的扩展(II)（1）本例中最大元素为3，除缺省外，其余元素均被3去减;（2）在缺省处填上充分大的正数M;

(3)行比列少一，因此填上一行0元素

（1）（2）（3)01521534230152153M

M4230152153M

M4230000第四章线性规划的扩展(II)匈牙利法的主要步骤：

第一步：变换效率矩阵，使在各行各列都出现零元素。

1、从矩阵C的每行元素减去该行的最小元素；

2、再从所得矩阵的每列中减去该列最小元素。

第二步：以最少数目的水平线和垂直线划去所有的零元素。如果所用的直线等于行或列数，则结束指派。否则继续。

第三步：找到没有被划去的最小的元素，所有没有被划中的元素减去这一最小值。而被划中两次的元素（该元素行列都被划中）则要加上这一最小值。再返回到第二步。第四部：最后根据零元素的位置，确定最优分配方案。

第四章线性规划的扩展(II)

例4－6：教材P113实例5.7

泊位

12345

1810936

2781129

324644

477527

510810311

船第四章线性规划的扩展(II)

泊位

12345最小值

1810936327811292324644247752725108103113船找出行最小值，去减行中每一值第四章线性规划的扩展(II)船

泊位

12345最小值

15760325690730

24224553

05575708

最小值

02302找出列最小值，去减列中每一值第四章线性规划的扩展(II)船

泊位

12345最小值

15530125460530

01204530

03573406

最小值用最少的线划去所有的零直线数为3不等于5

继续！第四章线性规划的扩展(II)船

泊位

12345最小值

15530125460530

01204530

03573406

最小值没有划去的最小值为1直线交叉元素加1，其余不在线上的减1加1第四章线性规划的扩展(II)船

泊位

12345最小值

14420024350430

0130453013562305

最小值用最少的线划去所有的零直线数为4不等于5

继续！第四章线性规划的扩展(II)船没有划去的最小值为1船

泊位

12345最小值

14420024350430

0130453013562305

最小值没有划去的最小值为2直线交叉元素加2，其余不在线上的减2第四章线性规划的扩展(II)船

泊位

12345最小值

14422022130230

0150453033540103

最小值用最少的线划去所有的零直线数为5等于5

结束循环第四章线性规划的扩展(II)船船

泊位

12345

1

020

30

0

04050

0

13245

先找只有一个0的行（列），先确定位置，划去列（行）中其余的0，再定其它。根据的零的位置确定最优方案第四章线性规划的扩展(II)船船

泊位

12345

1

622

32

4558

最小成本：23作业：有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表：

四位教师每人只能教一门课，每一门课只能由一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。

第四章线性规划的扩展(II)运输问题

从产地到销地之间运送货物的最佳路径。

多个产地和多个销地；每个产地的产量不同，每个销地的销量也不同；各产销两地之间的运价不同。如何组织调运，才能既满足各销地的要求，又使总的运输费用（或里程、时间等）最小。第四章线性规划的扩展(II)

设有同一种货物从m个出发地1，2，…，m运往n个到达地1，2，…，n。第i个出发地的供应量（Supply）为si（si≥0），第j个到达地的需求量（Demand）为dj（dj≥0）。每单位货物从产地i运到销地j的运价为Cij。求一个使总运费最小的运输方案。

123…n供应

1c11c1ns1

2c21成本

c2ns2

…cij……mcm1cmnsm

需求d1dn

∑出发地到达地第四章线性规划的扩展(II)

三类运输问题：产销平衡：产大于销：产小于销：第四章线性规划的扩展(II)产销平衡的运输问题模型令Xij为从i地运到j地的数量

MINZ=（Cij≥0)

（i=1,2,…,m)供应约束

(j=1,2,…,n)需求约束

Xij≥0

由Cij、Si、dj

组成的（m+1)×(n+1)矩阵称为运输矩阵第四章线性规划的扩展(II)产大于销时约束条件？

（j=1,2,…,n)

产小于销时约束条件？

（i=1,2,…,m)（i=1,2,…,m)（j=1,2,…,n)产销不平衡的运输问题模型第四章线性规划的扩展(II)

2321341运输问题网络图s2=10s3=15d1=13d2=21d3=9d4=7s1=25供应量供应地运价需求量需求地6753842759106第四章线性规划的扩展(II)运输问题线性规划模型供应地约束需求地约束m×n个变量，m+n个条件，约束条件系数矩阵前m行系数(0,1)和等于后n行和第四章线性规划的扩展(II)运输问题的表格表示销地产地XijCij第四章线性规划的扩展(II)运输问题初始可行解最小元素法：最小运价，“就近就省运给”

先给表中最小运价那格安排运量，调整相应的供给和需求余量，然后划去该运价所在余量为零的行或者列；接下去继续这样做，每次总在表中剩余运价的最小元