2024年4月15日发(作者：南通数学试卷谁出的)

第五讲 整数线性规划应用之一----指派问题

问题1

五名游泳运动员的四种泳姿的百米最好成绩（单位：秒）如下表所示。应从中选哪四个人组

成一个4×100米混合接力队？

人

泳姿

蝶 泳

仰 泳

蛙 泳

自由泳

甲

66.8

75.6

87

58.6

乙

57.2

66

66.4

53

丙

78

67.8

84.6

59.4

丁

70

74.2

69.6

57.2

戊

67.4

71

83.8

62.4

传统指派问题（Ⅰ型指派问题）：

c

ij

:效益（时间、利润、费用等）

问题1：如何安排工作，使总效益最大（时间最少、费用最小、利润最大等）？

决策变量的选取

引入0-1变量

x

ij

约束条件

n

1,员工i做第j项工作

0，员工i不做第j项工作

x

j1

n

ij

1,i1,2,

,n

1,j1,2,

,n

x

i1

ij

x

ij

0or1i,j1,2,

,n

目标函数

z

优化目标

视具体问题而定（max 或 min）

模型



cx

i1j1

nn

ijij

minz



c

ij

x

ij

i1j1

nn

n

x

ij

1,i1,2,

,n

j1

n

s.t.

x

ij

1,j1,2,

,n

i1

x

ij

0or1i,j1,2,

,n

问题1 的Excel求解

问题2

在一次国际会议上，大会秘书组需要将一份以中文书写的文件尽快翻译成英、俄、日、德、


更多推荐

问题,目标,变量