② A，C，E 选且只选一项： x1 x3 x5 1
③ B，D 选且只选一项： x2 x4 1
④ 选 C 必须先选 D ：
x3 1 x4 1 , 或x3 0 x4 0 或1 ,
x3 x4
于是数学模型为以下 0－1 规划：
max z 10 x1 8x2 7 x3 6 x4 9 x5
• 约束—总金额不超过限制
n
bjxj B
j 1
• 目标—总收益最大
n
max c j x j j 1
n
max c j x j j 1
n
s.t. j1 b j x j B

x
j
1,0;
j
1,2...,n
例2 一家昼夜服务的饭店，24小时中需要的服
务员数如下表所示。每个服务员每天连续工作8 小时，且在时段开始时上班。问：最少需要多少 名服务员？试建立该问题的线性规划模型。
解
用 xj 分别表示 A ，B ，C ，D ，E 的被选情况，则
1, 项目 j 被选中, x j 0, 项目 j未 被选中,
j 1, 2, 3, 4, 5
于是投资总收益期望值：
z 10 x1 8x2 7x3 6x4 9x5
约束条件：
① 资金总额限制：
6x1 4x2 2x3 4x4 5x5 15
例3 投资项目选取问题 某单位拟利用闲置资金15 万元进行对外投资，现有 5个投资项
目可供选择，所需资金及投资回报收益期望值为
项目 A B C D E
所需资金（万元） 6 4 2 4 5
收益期望值（万元） 10 8 7 6 9
A，B，C，D，E 之间的关系是： ① A、C、E 三项中需且只能选一项； ② B、D 两项中需且只能选一项； ③ 选 C 必须先选 D 。 问题：如何选择投资决策，使总投资期望值最大？
起迄时间
2----6 时 6---10 时 10--14 时 14--18 时 18--22 时 22---2 时
服务员人数 4 8 10 7 12 4
模型：
设以xj表示第j时段开始上班工作的服务员数， 则
Min z=x1+x2+x3+x4+x5+x6 st. x6+x14 x1+x28 x2+x310 x3+x47 x4+x512 x5+x64 xj0, xj为整数(j=1,2,---,6)
线性规划建模
例1
• 某财团有 B万元的资金，经出其考察选中 n
个投资项目，每个项目只能投资一个。其
中 年第后获j个利项c目（j 需j 投1资,2.金..,额n）为万b j元万，元问，应预如计何5
选择项目使得5年后总收益最大？
ቤተ መጻሕፍቲ ባይዱ
模型
• 变量—每个项目是否投资
x j 1,0 j 1,2...,n
表
A BCD 甲 15 20 9 10 乙 12 16 10 12
6 x1 4 x2 2 x3 4 x4 5x5 15

x1 x3 x5 1 x2 x4 1

x3 x4
x j 0或1，j 1, 2,3, 4,5
练习题1、有四项工作指派给甲、乙两人完成， 每人完成两项工作．两人完成各项工作的时间 （小时）见表，怎样安排工作使总时间最少．