数学规划模型
贵州财经学院数学建模培训班
简介数学规划模型
引例（生产规划问题）：某厂利用a、b、c三种原料生产A、B、C三种产品，已知生产每种产品在消耗原料方面的各项技术条件和单位产品的利润，以及可利用的各种原料的量（具体数据如下表），试制订适当的生产规划使得该厂的总的利润最大。
什么是线性规划
3
4
2
单位产品利润
80
2
3
1
c
40
2
1
2
b
60
2
4
3
a
C
B
A
现有原料的量
生产每单位产品所消耗的原料
产品
原料
线性规划模型
整数规划模型
非线性规划模型
以
分别表示生产A、B、C三种产品的量，
称之为决策变量，则
3
4
2
单位产品利润
80
2
3
1
c
40
2
1
2
b
60
2
4
3
a
C
B
A
现有原料的量
生产每单位产品所消耗的原料
产品
原料
目标函数
约束条件
目标函数：利润最大化、成本最小化，表现为决策变量的一个函数；
约束条件：资源、工期等，表现为决策变量的一些等式或不等式。
线性规划问题：在满足由一些线性等式或不等式组成的约束条件下，求决策变量的一组具体取值，使得一个线性目标函数实现最优（大或小）化。
线性规划的数学式子
线性规划实例：某机床厂生产甲、乙两种机床，每台销售后的利润分别为4元与3元。生产甲机床需用A、B机器加工，加工时间分别为每台 2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各多少台，才能使总利润最大？
非线性规划问题：目标函数或存在约束条件函数是决策变量的非线性函数的最优化问题
整数规划问题：决策变量限取整数值的最优化问题；
数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，则 x1 、x2应满足
max z =4x1 + 3x2
2x1 + x2 ≤10 生产甲用A，生产乙用A，
x1 + x2 ≤8 生产甲用B，生产乙用B （1） x2 ≤7 生产乙用C
x1 , x2 ≥0
线性规划的 求解方法
单纯形法（表上作业法）
图解法
软件求解法（用Lingo或Lingdo软件）
求解线性规划的方法（图解法）
图1
显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为x*=(2,6)T ，最优目标值z*=26 。
可行点：满足线性规划所有约束条件的点称为问题的可行点。
可行域：所有可行点构成的集合称为问题的可行域，记为R。
等位线：对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线。
当z变动时，我们得到一族平行直线（图1）。
求解线性规划的方法（软件实现）
model: ！程序开始
sets: ！变量集合开始
var/1..2/:x; ！说明x是二维变量
endsets ！集合说明结束
max=4*x(1)+3*x(2); ！目标函数求极大
2*x(1)+x(2)<=10; ！约束函数
x(1)+x(2)<=8; ！约束函数
x(2)<=7; ！约束函数
End ！程序结束 如果不加以
说明,LINGO认为所有变量非负
Global optimal solution found at iteration: 4
Objective value:
Variable Value Reduced Cost
X( 1)
X( 2)
Row Slack or Surplus Dual Price
1
2
3
4
求解报告窗口
不需要变量说明的程序
没有变量说明的程序
model:
max=2*x1+4*x2+3*x3;
3*x1+4*x2+2*x3<=60;
2*x1+x2+2*x3<=40;
x1+3*x2+3*x3<=80;
End
Global optimal solution found.
Objective value:
Total solver iterations: 2
Variable Value Reduced Cost
X1
X2
X3
Row Slack or Surplus Dual Price
1
2
3
4
3
4
2
单位产品利润
80
2
3
1
c
40
2
1
2
b
60
2
4
3
a
C
B
A
现有原料的量
生产每单位产品所消耗的原料
产品
原料
有变量说明的程序
model:
sets:
var/1..3/:x;
endsets
max=2*x(1)+4*x(2)+3*x(3);
3*x(1)+4*x(2)+2*x(3)<=60;
2*x(1)+x(2)+2*x(3)<=40;
x(1)+3*x(2)+3*x(3)<=80;
End
Global optimal solution found.
Objective value:
Total solver iterations: 2
Variable Value Reduced Cost
X( 1)
X( 2)
X( 3)
Row Slack or Surplus Dual Price
1
2
3
4
练习：建立下列数学模型
1、 某厂生产A、B两种产品，消耗三种资源。已知单位产品消耗资源数量以及单位产品销售利润如表所示。假设一个月内工厂可利用的煤W吨，可利用的技术工时为Q小时，工厂在一个月内必须完成的利润为P元。在充分发挥人力的条件下（即Q小时全部用完），如何安排生产任务，既要完成利润计划，又要使消耗电量最省。
12
8
8 10 4
4 2 6
A
B
单位产品利润
技工 电力 煤
（小时） （度） （吨）
资源
单位产品消耗资源
产品
2、某车间在未来的五天内所需的某种刀具统计资料如表所示。每把刀具成本元。用过的刀具送机修车间研磨，每把需花费元。刀具每天用过后，如果立即送去磨，两天后可以磨好送回，供当天的需要。第五天后，刀具全部换新的。假设开始时，该车间没有任何刀具。问这个车间需要多少刀具才能应付需要，而成本又最低
120 85 160 145 300
刀具数
1 2 3 4 5
日期
Global optimal solution found.
Objective value:
Infeasibilities:
Total solver iterations: 0
Variable Value Reduced Cost
X1
X2
X3
X4
X5
Row Slack or Surplus Dual Price
1
2
3
4
5
6
model:
min=*(x1+x2+x3+x4+x5)+*x1+*x2+*(x1+x3);
x1>=120;
x2>=85;
x1+x3>=160;
x2+x4>=145;
x1+x3+x5=300;
end
§ 奶制品的生产与销售
一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛
奶可以在设备甲上用12小时加工成3公斤A1，或者在设
备乙上用8小时加工成4公斤A2。根据市场需求，生产的
A1，A2全部能售出，且每公斤A1获利24元，每公斤A2获
利16元。现在加工厂每天能得到50桶牛奶的供应，每天
正式工人总的劳动时间为480小时，并且设备甲每天至多
能加工100公斤A1，设备乙的加工能力没有限制。试为该
厂制定一个生产计划，使每天获利最大，
并且进一步讨论以下三个附加问题。
（1）若用35元可以买到一桶牛奶，应否作这项投资？若投资，每天至多买多少桶牛奶？
（2）若可以聘用临时工以增加劳动时间，付给临时工的工资最多每小时几元？
（3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？
企业生产计划
奶制品的生产与销售
空间层次
工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；
车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。
时间层次
若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。
本节课题
加工奶制品的生产计划
1桶牛奶
3公斤A1
甲12小时
乙8小时
4公斤A2
或
获利24元/公斤
获利16元/公斤
50桶牛奶
时间480小时
至多加工100公斤A1
制订生产计划，使每天获利最大
35元可买到1桶牛奶，买吗？若买，每天最多买多少?
可聘用临时工人，付出的工资最多是每小时几元?
A1的获利增加到 30元/公斤，应否改变生产计划？
每天：
1桶牛奶
3公斤A1
12小时
8小时
4公斤A2
或
获利24元/公斤
获利16元/公斤
x1桶牛奶生产A1
x2桶牛奶生产A2
获利 24×3x1
获利 16×4 x2
原料供应
劳动时间
加工能力
决策变量
目标函数
每天获利
约束条件
非负约束
线性规划模型(LP)
时间480小时
至多加工100公斤A1
50桶牛奶
每天
模型求解
图解法
x1
x2
0
A
B
C
D
l1
l2
l3
l4
l5
约束条件
目标函数
Z=0
Z=2400
Z=3600
z=c (常数) ~等值线
c
在B(20,30)点得到最优解
目标函数和约束条件是线性函数
可行域为直线段围成的凸多边形
目标函数的等值线为直线
最优解一定在凸多边形的某个顶点取得。
模型求解（软件求解）
model:
sets:
var/1..2/:x;
endsets
max=72*x(1)+64*x(2);
x(1)+x(2)<=50;
12*x(1)+8*x(2)<=480;
3*x(1)<=100;
end
求解结果及其解释
max 72x1+64x2
st
2）x1+x2<50 牛奶原料
3）12x1+8x2<480 劳动时间
4）3x1<100 加工能力
end
三种资源
原料无剩余
时间无剩余
加工能力剩余40
“资源” 剩余为零的约束为紧约束（有效约束）
原料增加1单位, 利润增长48
时间增加1单位，利润增长2
加工能力增加，利润不增加
回答模型中的问题
OBJECTIVE FUNCTION VALUE
1)
VARIABLE VALUE REDUCED COST
X1
X2
ROW SLACK OR SURPLUS DUAL PRICES
2)
3)
4)
原料增加1单位, 利润增长48
时间增加1单位, 利润增长2
加工能力增长不影响利润
35元可买到1桶牛奶，要买吗？
35 <48, 应该买！
聘用临时工人付出的工资最多每小时几元？
2元！
影子价格：资源增加1单位，效益的增量称为影子价格 。
对偶价格给出3种资源在最优解下资源
增加1单位的效益增量。也就是影子价格
用程序验证我们的分析结果
牛奶：51桶
利润：3360+48=3408
灵敏性分析
一般情况下，目标函数的系数发生变化，最优解会发生变化，那么，系数在什么范围内最优解不发生变化呢？
注：约束条件不变！！
分析一：分析最优解不变时（即不改变生产计
划）目标函数系数的允许变化范围。
Ranges in which the basis is unchanged:
Objective Coefficient Ranges
Current Allowable Allowable
Variable Coefficient Increase Decrease
X( 1)
X( 2)
Righthand Side Ranges
Row Current Allowable Allowable
RHS Increase Decrease
2
3
4 INFINITY
x1系数范围(64,96)
x2系数范围(48,72)
A1获利增加到 30元/千克，应否改变生产计划
x1系数由24 3=72增加为303=90，在允许范围内
不变！
软件使用方法：lingo菜单 Range，查看灵敏性分析
分析二：原料是否可以无限制的增加
结果解释
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1
X2
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2
3
4 INFINITY
影子价格有意义时约束右端的允许变化范围
原料最多增加10
时间最多增加53
35元可买到1桶牛奶，每天最多买多少？
最多买10桶!
(目标函数不变)
问题：为什么原料的减少量不能少于桶
软件介绍
1、问题的输入
model: ！程序开始
sets: ！变量集合开始
var/1..2/:x; ！说明x是二维变量
endsets ！集合说明结束
max=4*x(1)+3*x(2); ！目标函数求极大
2*x(1)+x(2)<=10; ！约束函数
x(1)+x(2)<=8; ！约束函数
x(2)<=7; ！约束函数
End ！程序结束 如果不加以
说明,LINGO认为所有变量非负
max=Cx
Ax≤b
x≥0
用拒阵乘法编的程序
model:
sets:
row/1..3/:b; ！定义3 维向量
col/1..2/:c,x; ！定义2个二维向量
matrix(row,col):A; 定义3×2的矩阵
endsets
max=@sum(col:c*x); ！目标函数
@for(row(i):
@sum(col(j):A(i,j)*x(j))<=b(i));
data:
c=4,3;
b=10,8,7;
A=2,1,
1,1,
0,1;
enddata
end
问题的求解
求解图标
结果分析
LINGO菜单介绍
1.文件（File）菜单
（1）新建
（2）打开
（3）保存
（4）另存为
（5）关闭
（6）打印
（7）打印设置
（8）打印预览
（9）输出到文本文件
（10）批处理文件（命令文件和模型文件打包，以便自动运行）
（11）引入lingo文件
（12）退出
2、编辑（Edit）菜单
（1）恢复（取消上次操作）
（2）再恢复（撤销上次撤销的操作）
（3）剪切
（4）复制
（5）粘贴
（6）全部选定（Select all）
（7）查找
（8）再次查找上次查找内容
（9）替换
（10）到指定行：到达当前活动窗口中输入数字的指定行
（11）匹配表示
（12）粘贴函数
（13）选择新的字体
3、lingo菜单
（1）求解模型
（2）求解结果的显示
（3）查看当前模型灵敏度分析结果
（4）选项（改变模型参数)
(5)显示模型
（6）模型图片
（7）模型计算结果统计
（8）查看（look）
4、窗口（window)菜单
（1）打开命令窗口
（2）打开状态窗口
（3）窗口切换
（4）关闭全部窗口
（5）窗口平铺（将打开窗口在lingo程序窗口中平铺）
（6）窗口排列
复习上节内容
利用lingo求解可以得到以下结果
（1）最优解 （最优生产计划及获得最优效益）
（2）影子价格（即:资源增加一个单位效益增加量）
利用lingo可以查看灵敏度分析
（1）分析最优解不变时（即不改变生产计划），目标函数系数的允许变化范围。
（2）原料是否可以无限制的增加
例2 奶制品的生产销售计划
在例1基础上深加工
1桶牛奶
3千克A1
12小时
8小时
4公斤A2
或
获利24元/公斤
获利16元/公斤
千克B1
2小时,3元
1千克
获利44元/千克
千克B2
2小时,3元
1千克
获利32元/千克
制订生产计划，使每天净利润最大
30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？
50桶牛奶, 480小时
至多100公斤A1
B1，B2的获利经常有10%的波动，对计划有无影响？
例1： 一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1，A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。(最优生产计划：20捅生产A1，30捅生产A2）
在例1基础上进行深加工：加工的A1一部分用来生产B1，每千克A1生产千克B1，费用3元，所用时间2小时，每千克B1获利44元。加工的A2一部分用来生产B2，每千克A2生产千克B2，费用3元，所用时间2小时，每千克B2获利32元。
试为该厂制定一个生产计划，使每天获利最大，
1桶牛奶
3千克 A1
12小时
8小时
4千克 A2
或
获利24元/千克
获利16元/kg
千克 B1
2小时,3元
1千克
获利44元/千克
千克 B2
2小时,3元
1千克
获利32元/千克
出售x1 千克 A1, x2 千克 A2，
x3千克 B1, x4千克 B2
原料供应
劳动时间
加工能力
决策变量
目标函数
利润
约束条件
非负约束
x5千克 A1加工B1， x6千克 A2加工B2
附加约束
模型求解
软件实现
LINGO
model:
sets:
var/1..6/:x;
endsets
max=24*x(1)+16*x(2)+44*x(3)+32*x(4)-3*x(5)-3*x(6);
4*x(1)+3*x(2)+4*x(5)+3*x(6)<=600;
4*x(1)+2*x(2)+6*x(5)+4*x(6)<=480;
x(1)+x(5)<=100;
x(3)=*x(5);
x(4)=*x(6);
end
Global optimal solution found at iteration: 2
Objective value:
Variable Value Reduced Cost
X( 1)
X( 2)
X( 3)
X( 4)
X( 5)
X( 6)
Row Slack or Surplus Dual Price
1
2
3
4
5
6
Objectivevalue:
1)
Variable Value Reduced Cost
A1 X1
A2 X2
B1 X3
B2 X4
A1~B1 X5
A2~B2 X6
Row Slack or Surplus Dual Price
牛奶 2)
时间 3)
加工能力4)
5)
6)
结果解释
每天销售168 千克A2和 千克B1，24千克A1加工成B1,
利润（元）
24/3=8桶牛奶加工成A1，168/4=42桶牛奶加工成A2，
将得到的24千克A1全部加工成B1
结果解释
增加1桶牛奶使利润增长×12=
增加1小时时间使利润增长
30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？
投资150元增加5桶牛奶，可赚回元。（大于增加时间的利润增长）
Objectivevalue:
1)
Variable Value Reduced Cost
A1 X1
A2 X2
B1 X3
B2 X4
A1~B1 X5
A2~B2 X6
Row Slack or Surplus Dual Price
牛奶 2)
时间 3)
加工能力4)
5)
6)
结果解释
Ranges in which the basis is unchanged:
Objective Coefficient Ranges
Current Allowable Allowable
Variable Coefficient Increase Decrease
X( 1) INFINITY
X( 2)
B1 X( 3)
B2 X( 4) INFINITY
X( 5)
X( 6) INFINITY
Righthand Side Ranges
Row Current Allowable Allowable
RHS Increase Decrease
2
3
4 INFINITY
5 INFINITY
6 INFINITY
灵敏性计算方法：菜单lingo(option）—选择General Solver—选择Price & Range
≤B1≤44+,B1获利下降10%，即 超出X3 系数允许范围
≤B2≤32, B2获利上升10%，即32+,超出X4 系数允许范围
结论：波动对计划有影响
生产计划应重新制订：如将x(3)的系数改为计算（B1利润下降10％），会发现结果有很大变化。
B1,B2的获利有10%的波动，对计划有无影响
X(3)系数变为
结论：将x3的系数改为计算，生产计划发生了很大变化。
作业
设某工厂有甲、乙、丙、丁四台机床，生产A、B、C、D、E、F六种产品，加工每一件产品所需时间（工时）和每一件产品的单价已知，如下表所示，表中没有填数的表示这台机床不能加工这种零件。假设甲、乙、丙、丁四台机床的最大工作能力分别为850、700、600、900工时，问在机床能力许可的条件下，每件产品应生产多少才能使该厂生产的利润最大。试建立此数学模型并求解。
80
64
72
32
28
40
每件产品单价
8
3
丁
5
2
丙
5
2
乙
3
3
3
1
1
1
甲
F
E
D
C
B
A
产品
加工产品所需时间
机床
自来水输送与货机装运
生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；
运输问题
各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。
问题：某城市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应，四个区基本用水量（必须保证）分别为30、70、10、10千吨，三个水库最多供水量分别50、60、50千吨。自来水公司从水库向各个小区送水付出引水管理费不同，其它管理费是450元/千吨。各小区收费相同，标准900元/千吨。此外，四个小区申请额外用水量分别50、70、20、40千吨，该公司应如何分配供水量能使利润最大？若水库供水量都提高一倍，公司利润可增加到多少？
例1 自来水输送
元/千吨
甲
乙
丙
丁
A
160
130
220
170
B
140
130
190
150
C
190
200
230
/
其他费用:450元/千吨
应如何分配水库供水量，公司才能获利最多？
若水库供水量都提高一倍，公司利润可增加到多少？
元/千吨
甲
乙
丙
丁
A
160
130
220
170
B
140
130
190
150
C
190
200
230
/
引水管理费
例1 自来水输送
收入：900元/千吨
支出
A：50
B：60
C：50
甲：30；50
乙：70；70
丙：10；20
丁：10；40
水库供水量(千吨)
小区基本用水量(千吨)
小区额外用水量(千吨)
（以天计）
总供水量：160
确定送水方案使利润最大
问题分析
A：50
B：60
C：50
甲：30；50
乙：70；70
丙：10；20
丁：10；40
< 总需求量：120+180=300
总收入900160=144,000(元)
收入：900元/千吨
其他费用:450元/千吨
支出
引水管理费
其他支出450160=72,000(元)
使引水管理费最小
供应限制
约束条件
需求限制
线性规划模型(LP)
目标函数
水库i 向j 区的日供水量为 xij（x34=0）
决策变量
模型建立
确定3个水库向4个小区的供水量
模型求解
model:
sets:
kar/1..3/;
car/1..4/;
var(kar,car):x;
endsets
min=160*x(1,1)+130*x(1,2)+220*x(1,3)+
170*x(1,4)+140*x(2,1)+130*x(2,2)+190*x(2,3)
+150*x(2,4)+190*x(3,1)+200*x(3,2)+230*x(3,3);
x(1,1)+x(1,2)+x(1,3)+x(1,4)=50;
x(2,1)+x(2,2)+x(2,3)+x(2,4)=60;
x(3,1)+x(3,2)+x(3,3)=50;
x(1,1)+x(2,1)+x(3,1)<=80;
x(1,1)+x(2,1)+x(3,1)>=30;
x(1,2)+x(2,2)+x(3,2)<=140;
x(1,2)+x(2,2)+x(3,2)>=70;
x(1,3)+x(2,3)+x(3,3)<=30;
x(1,3)+x(2,3)+x(3,3)>=10;
x(1,4)+x(2,4)<=50;
x(1,4)+x(2,4)>=10;
End
Objective value:
Variable Value Reduced Cost
X( 1, 1)
X( 1, 2)
X( 1, 3)
X( 1, 4)
X( 2, 1)
X( 2, 2)
X( 2, 3)
X( 2, 4)
X( 3, 1)
X( 3, 2)
X( 3, 3)
X( 3, 4)
结果解释
利润=总收入-其它费用-引水管理费=144000-72000-24400 = 47600（元）
A(50)
B(60)
C(50)
甲(30;50)
乙(70;70)
丙(10;20)
丁(10;40)
50
50
40
10
10
引水管理费 24400(元)
Objective value:
Variable Value Reduced Cost
X( 1, 1)
X( 1, 2)
X( 1, 3)
X( 1, 4)
X( 2, 1)
X( 2, 2)
X( 2, 3)
X( 2, 4)
X( 3, 1)
X( 3, 2)
X( 3, 3)
X( 3, 4)
目标函数
总供水量(320) > 总需求量(300)
每个水库最大供水量都提高一倍
利润 = 收入(900) –其它费用(450) –引水管理费
利润(元/千吨)
甲
乙
丙
丁
A
290
320
230
280
B
310
320
260
300
C
260
250
220
/
供应限制
问题讨论
确定送水方案使利润最大
需求约束不变
计算三个水库分别向四个小区供应每千吨水的利润
利润/千吨 = 收入(900) –其它费用(450) –引水管理费
=450-引水管理费
元/千吨
甲
乙
丙
丁
A
160
130
220
170
B
140
130
190
150
C
190
200
230
/
引水
管理费
利润(元/千吨)
甲
乙
丙
丁
A
290
320
230
280
B
310
320
260
300
C
260
250
220
/
利
润
模型程序及求解结果
model:
sets:
kar/1..3/;
car/1..4/;
var(kar,car):x;
endsets
max=290*x(1,1)+320*x(1,2)+230*x(1,3)+280*x(1,4)+
310*x(2,1)+320*x(2,2)+260*x(2,3)+300*x(2,4)+
260*x(3,1)+250*x(3,2)+220*x(3,3);
x(1,1)+x(1,2)+x(1,3)+x(1,4)<=100;
x(2,1)+x(2,2)+x(2,3)+x(2,4)<=120;
x(3,1)+x(3,2)+x(3,3)<=100;
x(1,1)+x(2,1)+x(3,1)<=80;
x(1,1)+x(2,1)+x(3,1)>=30;
x(1,2)+x(2,2)+x(3,2)<=140;
x(1,2)+x(2,2)+x(3,2)>=70;
x(1,3)+x(2,3)+x(3,3)<=30;
x(1,3)+x(2,3)+x(3,3)>=10;
x(1,4)+x(2,4)<=50;
x(1,4)+x(2,4)>=10;
end
Global optimal solution found at iteration: 0
Objective value:
Variable Value Reduced Cost
X( 1, 1)
X( 1, 2)
X( 1, 3)
X( 1, 4)
X( 2, 1)
X( 2, 2)
X( 2, 3)
X( 2, 4)
X( 3, 1)
X( 3, 2)
X( 3, 3)
X( 3, 4)
结果解释
Objective Value
1)
Variable Value Reduced Cost
X11
X12
X13
X14
X21
X22
X23
X24
X31
X32
X33
这类问题一般称为“运输问题”
(Transportation Problem)
总利润 88700（元）
A(100)
B(120)
C(100)
甲(30;50)
乙(70;70)
丙(10;20)
丁(10;40)
40
100
50
30
50
30
例2 货机装运
问题：某架货机有三个货仓：前仓，中仓和后仓．三个货仓的载重量和体积都有限制．为了保持飞机的平衡，三个货舱中实际载货的重量与其最大容许重量成正比．如何安排装运，使该货机本次飞行获利最大？
如何装运，使本次飞行获利最大？
三个货舱最大载重(吨),最大容积(米3)
货机装运
重量（吨）
空间( 米3/吨）
利润（元/吨）
货物1
18
480
3100
货物2
15
650
3800
货物3
23
580
3500
货物4
12
390
2850
三个货舱中实际载重必须与其最大载重成比例
前仓：
10吨；6800m3
中仓：
16吨；8700m3
后仓：
8吨；5300m3
飞机平衡
目标函数(利润)
货机装运
模型建立
xij--第i 种货物装入第j 个货舱的重量
x43
x42
x41
（货物） 4
x33
x32
x31
（货物） 3
x23
x22
x21
（货物） 2
x13
x12
x11
（货物） 1
（后舱） 3
（中舱） 2
（前舱） 1
货舱容积
约束条件
货舱重量
10；6800
16；8700
8；5300
x43
x42
x41
（货物） 4
x33
x32
x31
（货物） 3
x23
x22
x21
（货物） 2
x13
x12
x11
（货物） 1
（后舱） 3
（中舱） 2
（前舱） 1
平衡要求
货物供应
货机装运
模型建立
10；6800
16；8700
8；5300
x43
x42
x41
（货物） 4
x33
x32
x31
（货物） 3
x23
x22
x21
（货物） 2
x13
x12
x11
（货物） 1
（后舱） 3
（中舱） 2
（前舱） 1
model:
sets:
kar/1..4/;
car/1..3/;
var(kar,car):x;
endsets
max=3100*(x(1,1)+x(1,2)+x(1,3))+
3800*(x(2,1)+x(2,2)+x(2,3))+
3500*(x(3,1)+x(3,2)+x(3,3))+
2850*(x(4,1)+x(4,2)+x(4,3));
x(1,1)+x(2,1)+x(3,1)+x(4,1)<=10;
x(1,2)+x(2,2)+x(3,2)+x(4,2)<=16;
x(1,3)+x(2,3)+x(3,3)+x(4,3)<=8;
480*x(1,1)+650*x(2,1)+580*x(3,1)+390*x(4,1)<=6800;
480*x(1,2)+650*x(2,2)+580*x(3,2)+390*x(4,2)<=8700;
480*x(1,3)+650*x(2,3)+580*x(3,3)+390*x(4,3)<=5300;
8*(x(1,1)+x(2,1)+x(3,1)+x(4,1))-5*(
x(1,2)+x(2,2)+x(3,2)+x(4,2))=0;
(x(1,2)+x(2,2)+x(3,2)+x(4,2))-2*
(x(1,3)+x(2,3)+x(3,3)+x(4,3))=0;
x(1,1)+x(1,2)+x(1,3)<=18;
x(2,1)+x(2,2)+x(2,3)<=15;
x(3,1)+x(3,2)+x(3,3)<=23;
x(4,1)+x(4,2)+x(4,3)<=12;
end
Objective value:
Variable Value Reduced Cost
X( 1, 1)
X( 1, 2)
X( 1, 3)
X( 2, 1)
X( 2, 2)
X( 2, 3)
X( 3, 1)
X( 3, 2)
X( 3, 3)
X( 4, 1)
X( 4, 2)
X( 4, 3)
计算程序及计算结果
货物2：前仓７,后仓8； 货物3: 前仓3, 中仓13；货物4: 中仓3。
货机装运
结果解释
最大利润约121516元
货物-供应点
货舱-需求点
平衡要求
运输问题
运输问题的扩展
Objective value:
Variable Value Reduced Cost
X( 1, 1)
X( 1, 2)
X( 1, 3)
X( 2, 1)
X( 2, 2)
X( 2, 3)
X( 3, 1)
X( 3, 2)
X( 3, 3)
X( 4, 1)
X( 4, 2)
X( 4, 3)
练习
问题：有七种规格的包装箱要装到两节铁路平板车上.包装箱的宽和长是一样的,但厚度(t,cm)和重量(w,kg)是不同的.表中给出包装箱的规格.每节平板车有厚度的地方可用来装包装箱,载重为40t,由于当地货物的限制,对于c5,c6,c7类包装箱的总数有一个特别的限制:这类箱子所占的空间(厚度)不能超过,试把包装箱装到平板车上去使得浪费的空间最小
8 7 9 6 6 4 8
个数 n /件
2000 3000 1000 500 4000 2000 1000
重量 w/kg
厚度 t /cm
C1 C2 C3 C4 C5 C6 C7
种类
汽车生产与原油采购
问题：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。
(1)制订月生产计划，使工厂的利润最大.
(2)如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？
例1 汽车厂生产计划
小型 中型 大型 现有量
钢材（吨） 3 5 600
劳动时间（小时） 280 250 400 60000
利润（万元） 2 3 4
设每月生产小、中、大型汽车的数量分别为x1, x2, x3
汽车厂生产计划
模型建立
小型 中型 大型 现有量
钢材 3 5 600
时间 280 250 400 60000
利润 2 3 4
线性规划模型(LP)
模型求解
3） 模型中增加条件：x1, x2, x3 均为整数，重新求解。
即整数规划求解
Objective value:
Variable Value Reduced Cost
X( 1)
X( 2)
X( 3)
Row Slack or Surplus Dual Price
1
2
3 -02
结果为小数，怎么办？
1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值相差不大。
2）试探：如取x1=65，x2=167,z=631；x1=64，x2=168，z=632;通过比较得出x1=64，x2=168是更优的解。
但必须检验它们是否满足约束条件。为什么？
整数规划(Integer Programming,简记IP)
@gin (x(1))表示x(1)是整数变量．
书中的说法对软件linDo有效！！
IP 的最优解x1=64，x2=168，x3=0，最优值z=632
model:
sets:
var/1..3/:x;
endsets
max=2*x(1)+3*x(2)+4*x(3);
*x(1)+3*x(2)+5*x(3)<=600; 280*x(1)+250*x(2)+400*x(3)<=60000;
@gin (x(1));
@gin (x(2));
@gin (x(3));
end
Objective value:
Variable Value Reduced Cost
X( 1)
X( 2)
X( 3)
Row Slack or Surplus Dual Price
1
2
3
模型求解
IP
结
果
输
出
model:
sets:
row/1..2/:b;
var/1..3/:c,x;
matrix(row,var):A;
endsets
max=@sum(var:c*x);
@for(row(i):@sum(var(j):A(i,j)*x(j))<=b(i));
@for(var:@gin(x));
data:
c=2,3,4;
b=600,60000;
A=,3,5,280,250,400;
enddata
end
其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：
方法1：分解为8个LP子模型
汽车厂生产计划
若生产某类汽车，则至少生产80辆，求生产计划。
x1,x2,, x3=0 或 80
x1=80，x2= 150，x3=0，最优值z=610
方法2：引入0-1变量，化为整数 0-1 规划
M为大的正数，可取1000
若生产某类汽车，则至少生产80辆，求生产计划。
x1=0 或 80
x2=0 或 80
x3=0 或 80
化为0-1规划的求解结果
model:
sets:
var/1..3/:x;
dar/1..3/:y;
endsets
max=2*x(1)+3*x(2)+4*x(3);
*x(1)+3*x(2)+5*x(3)<=600;
280*x(1)+250*x(2)+400*x(3)<=60000;
x(1)-1000*y(1)<=0;
x(1)-80*y(1)>=0;
x(2)-1000*y(2)<=0;
x(2)-80*y(2)>=0;
x(3)-1000*y(3)<=0;
x(3)-80*y(3)>=0;
@gin (x(1));
@gin (x(2));
@gin (x(3));
@bin (y(1));
@bin (y(2));
@bin (y(3));
end
Objective value:
Variable Value Reduced Cost
X( 1)
X( 2)
X( 3)
Y( 1)
Y( 2)
Y( 3)
Row Slack or Surplus Dual Price
1
2
3
4
5
6
7
8
9
最优解同前
LINGO中对0-1变量的限定：bin y1
bin y2
bin y3
NLP虽然可用现成的数学软件求解(如LINGO, MATLAB)，但是其结果常依赖于初值的选择。
方法3：化为非线性规划
非线性规划（Non- Linear Programming，简记NLP）
实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。
若生产某类汽车，则至少生产80辆，求生产计划。
x1=0 或 80
x2=0 或 80
x3=0 或 80
例2 原油采购与加工
问题：某公司用两种原油（Ａ和Ｂ）混合加工成两种汽油甲和乙．甲和乙两种汽油含原油Ａ的最低比例分别为50％和60％，每吨售价分别为4800元和5600元。该公司现有原油Ａ和Ｂ的库存量500吨和1000吨，还可以从市场上买回不超过1500吨原油Ａ。原油Ａ的价格为：购买量不超过500吨，单价1000元/吨；购买量在500～1000吨之间，超过500吨的部分，单价8000元/吨，购买量超过1000吨，超过1000吨的部分，单价6000元/吨；该公司应如何安排原油的采购和加工 ？
应如何安排原油的采购和加工 ？
原油采购与加工
市场上可买到不超过1500吨的原油A：
购买量不超过500吨时的单价为10000元/吨；
购买量超过500吨但不超过1000吨时，超过500吨的 部分8000元/吨；
购买量超过1000吨时，超过1000吨的部分6000元/吨。
售价4800元/吨
售价5600元/吨
库存500吨
库存1000吨
汽油甲(A50%)
原油A
原油B
汽油乙 (A60%)
决策变量
目标函数
问题分析
利润：销售汽油的收入 - 购买原油A的支出
难点：原油A的购价与购买量的关系较复杂
甲(A50%)
A
B
乙(A60%)
购买x
x11
x12
x21
x22
千元/吨
千元/吨
原油A的购买量,原油A, B生产汽油甲,乙的数量
c(x) ~ 购买原油A的支出
利润(千元)
c(x)如何表述？
原油供应
约束条件
x 500吨单价为10千元/吨；
500吨 x 1000吨，超过500吨的8千元/吨；
1000吨 x 1500吨，超过1000吨的6千元/吨。
目标函数
购买x
A
B
x11
x12
x21
x22
库存500吨
库存1000吨
汽油含原油A的比例限制
约束条件
甲(A50%)
A
B
乙(A60%)
x11
x12
x21
x22
目标函数
约束条件
数学模型
目标函数中c(x)不是线性函数，是非线性规划；
对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；
想办法将模型化简，用现成的软件求解。
x1 , x2 , x3 ~以价格10, 8, 6(千元/吨)采购A的吨数
目标函数
只有当以10千元/吨的价格购买x1=500(吨)时，才能以8千元/吨的价格购买x2
方法1：化为非线性规划求解
非线性规划模型，可以用LINGO求解
x= x1+x2+x3, c(x) = 10x1+8x2+6x3
500吨 x 1000吨，超过500吨的8千元/吨
增加约束
x= x1+x2+x3, c(x) = 10x1+8x2+6x3
方法1：LINGO求解
Model:
Max= *x11 + *x21 + *x12 + *x22 - 10*x1 - 8*x2 - 6*x3;
x11+x12 < x + 500;
x21+x22 < 1000;
x11 - x21 > 0;
2*x12 - 3*x22 > 0;
x=x1+x2+x3;
(x1 - 500) * x2=0;
(x2 - 500) * x3=0;
x1 < 500;
x2 < 500;
x3 < 500;
x > 0;
x11 > 0;
x12 > 0;
x21 > 0;
x22 > 0;
x1 > 0;
x2 > 0;
x3 > 0;
end
Objective value:
Variable Value Reduced Cost
X11 +00
X21 +00
X12 +00 +00
X22 +00 +00
X1 -13
X2 +00
X3 +00
X +00 +00
LINGO得到的是局部最优解，还能得到更好的解吗？
用库存的500吨原油A、500吨原油B生产汽油甲，不购买新的原油A，利润为4,800千元。
y1, y2 , y3=1 ~以价格10, 8, 6(千元/吨)采购A
增加约束
方法2：化为０～１规划模型求解
x1 , x2 , x3 ~以价格10, 8, 6(千元/吨)采购A的吨数
求解结果
Model:
Max= *x11 + *x21 + *x12
+ *x22 - 10*x1 - 8*x2 - 6*x3;
x=x1+x2+x3;
x11+x12 < x + 500;
x21+x22 < 1000;
x11 - x21 > 0;
2*x12 - 3*x22 > 0;
x1-500*y1<=0;
x2-500*y2<=0;
x3-500*y3<=0;
x1-500*y2>=0;
x2-500*y3>=0;
@bin(y1);
@bin(y2);
@bin(y3);
end
Objective value: 5000
Variable Value Reduced Cost
X11
X21
X12
X22
X1
X2
X3
X
Y1
Y2
Y3
购买1000吨原油A，与库存的500吨原油A和1000吨原油B一起，生产汽油乙，利润为5,000千元 。
优于方法1的结果；方法２是最优解，方法１是局部最优解。
b1 b2 b3 b4
方法3：直接处理分段线性函数c(x)
b1 xb2，x= z1b1+z2b2，
z1+z2=1，z1, z20,
c(x)= z1c(b1)+z2c(b2)
=10×500z2
c(x)
x
12000
9000
5000
0
500
1000
1500
b2 x b3，x= z2b2+z3b3，
z2+z3=1，z2, z3 0,
c(x)= z2c(b2)+z3c(b3)
=5000z2+9000z3
b3 x b4，x= z3b3+z4b4，
z3+z4=1，z3, z4 0,
c(x)= z3c(b3)+z4c(b4)
=9000z3+12000z4
为了表示x在哪个区间，引入0-1变量yk (K=1,2,3)
当x在第k个区间，yk =1，否则yk =0
(1) y1=1,表示x在第一个区间，y2 = y3 =0, z1+z2=1,z3=0,z4=0
则 z1≤y1 =1 ， z2≤y1 +y2 =1 ，z3≤y2 +y3 =0 , z4≤y3 =0 ; z1 +z2 +z3+z4=1,记 x= z1b1+z2b2 =500z2，
c(x)=5000z2
(2) y2=1,表示x在第二个区间，y1 = y3 =y4 =0
则 z1≤y1 =0， z2≤y1 +y2 =1 ， z3≤y2 +y3 =1 , z4≤y3 =0 z1 + z2 +z3 +z4=1,记 x= z2b2 +z3b3=500z2 +1000z3，
c(x)=5000z2+9000z3
(3) y3=1,表示x在第三个区间，y1 = y2 =y4 =0
则 z1≤y1 =0， z2≤y1 +y2 =0 ， z3≤y2 +y3 =1 , z4≤y3 =1 ; z1 + z2 +z3 +z4=1 ,记 x= z4b4 +z3b3=1500z4+1000z3，
c(x)=9000z3+12000z4
所以，统一表示
x= z1 b1 +z2 b2 +z3b3 +z4b4
=500z2 +1500z4+1000z3
z1+z2+z3+z4=1
c(x)=5000z2 +9000z3+12000z4
y1，y2， y3 =0或1
bkxbk+1yk=1,否则,yk=0
处理分段线性函数的方法更具一般性
bkxbk+1 ,x= zkbk+z k+1 bk+1
zk+zk+1 =1，zk, zk+1 0,
c(x)= zkc(bk)+zk+1 c(bk+1 ).
c(x)
x
12000
9000
5000
0
500
1000
1500
b1 b2 b3 b4
对于k=1,2,3
总结：
z1≤y1 ， z2≤y1 +y2，
z3≤y2 +y3，
z4≤y3，z1 + z2 +z3 +z4=1
z1 ≥0，z2≥0，
z3 ≥0， z4≥0
y1,y2, y3 , y4 =1 or 0
约
束
条
件
目标函数：
问题转化为
IP模型，LINGO求解，得到的结果与方法2相同.
介绍分派问题的数学模型
拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费Cij单位时间，问应如何分配工作才能使工人花费的总时间最少？
容易看出，只要给出指派问题的系数矩阵
C=（Cij）,引入变量xij，若分配i人干j项工作，则取xij =1，否则取xij =0。
上述指派问题的数学模型为
目标函数
约束条件
j=1,…n,第j项工作只有1人干
i=1,…n,第i个人只干1项工作
一般情况：人数＝工作数
特殊情况：人数≠工作数
接力队选拔和选课策略
若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。
若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。
分派问题
问题:某班准备从5名游泳队员中选择4人组成接力队,参加学校的4×100m混合接力比赛,5名队员4种泳姿的百米平均成绩见表,问应如何选拔队员?
例1 混合泳接力队的选拔
甲
乙
丙
丁
戊
蝶泳
1’06”8
57”2
1’18”
1’10”
1’07”4
仰泳
1’15”6
1’06”
1’07”8
1’14”2
1’11”
蛙泳
1’27”
1’06”4
1’24”6
1’09”6
1’23”8
自由泳
58”6
53”
59”4
57”2
1’02”4
5名候选人的百米成绩
甲
乙
丙
丁
戊
蝶泳
1’06”8
57”2
1’18”
1’10”
1’07”4
仰泳
1’15”6
1’06”
1’07”8
1’14”2
1’11”
蛙泳
1’27”
1’06”4
1’24”6
1’09”6
1’23”8
自由泳
58”6
53”
59”4
57”2
1’02”4
(2)若丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？
(1)如何选拔队员组成4100米混合泳接力队?
穷举法：组成接力队的方案共有5!=120种。
目标函数
若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0
0-1规划模型
cij(秒)~队员i 第j 种泳姿的百米成绩
约束条件
每人最多入选泳姿之一
cij
i=1
i=2
i=3
i=4
i=5
j=1
78
70
j=2
66
71
j=3
87
j=4
53
每种泳姿有且只有1人
模型求解程序
model:
sets:
row/1..5/;
col/1..4/;
var(row,col):C,x;
endsets
min=@sum(var(i,j):c(i,j)*x(i,j));
@for(row(i):@sum(col(j):x(i,j))<=1);
@for(col(j):@sum(row(i):x(i,j))=1);
@for(var(i,j):@bin(x(i,j)));
data:
c= ,87,
,66,,53,
78,,,,
70,,,,
,71,,;
enddata
end
Objective value:
X( 1, 1)
X( 1, 2)
X( 1, 3)
X( 1, 4)
X( 2, 1)
X( 2, 2)
X( 2, 3)
X( 2, 4) X( 3, 1) X( 3, 2) X( 3, 3) X( 3, 4) X( 4, 1) X( 4, 2) X( 4, 3) X( 4, 4) X( 5, 1) X( 5, 2) X( 5, 3) X( 5, 4)
模型求解结果
最优解：x14 = x21 = x32 = x43 = 1, 其它变量为0;
成绩为(秒)=4’13”2
甲
乙
丙
丁
戊
蝶泳
1’06”8
57”2
1’18”
1’10”
1’07”4
仰泳
1’15”6
1’06”
1’07”8
1’14”2
1’11”
蛙泳
1’27”
1’06”4
1’24”6
1’09”6
1’23”8
自由泳
58”6
53”
59”4
57”2
1’02”4
甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳.
丁蛙泳c43 =，戊自由泳c54= , 方案是否调整？
敏感性分析？
乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳、戊~ 自由泳
注意：IP规划一般没有与LP规划相类似的理论，LINＧO输出的敏感性分析结果通常是没有意义的。
最优解：x21 = x32 = x43 = x51 = 1, 成绩为4’17”7
c43, c54 的新数据重新输入模型，求解得出
讨论
甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳.
原方案
为了选修课程门数最少，应学习哪些课程 ？
例2 选课策略
要求至少选两门数学课、三门运筹学课和两门计算机课
课号
课名
学分
所属类别
先修课要求
1
微积分
5
数学
2
线性代数
4
数学
3
最优化方法
4
数学；运筹学
微积分；线性代数
4
数据结构
3
数学；计算机
计算机编程
5
应用统计
4
数学；运筹学
微积分；线性代数
6
计算机模拟
3
计算机；运筹学
计算机编程
7
计算机编程
2
计算机
8
预测理论
2
运筹学
应用统计
9
数学实验
3
运筹学；计算机
微积分；线性代数
选修课程最少，且学分尽量多，应学习哪些课程 ？
0-1规划模型
决策变量
目标函数
xi=1 ~选修课号i 的课程（xi=0 ~不选）
选修课程总数最少
约束条件
最少2门数学课，3门运筹学课，
2门计算机课。
课号
课名
所属类别
1
微积分
数学
2
线性代数
数学
3
最优化方法
数学；运筹学
4
数据结构
数学；计算机
5
应用统计
数学；运筹学
6
计算机模拟
计算机；运筹学
7
计算机编程
计算机
8
预测理论
运筹学
9
数学实验
运筹学；计算机
先修课程要求
0-1规划模型
约束条件
x3=1必有x1 = x2 =1
课号
课名
先修课要求
1
微积分
2
线性代数
3
最优化方法
微积分；线性代数
4
数据结构
计算机编程
5
应用统计
微积分；线性代数
6
计算机模拟
计算机编程
7
计算机编程
8
预测理论
应用统计
9
数学实验
微积分；线性代数
模型求解程序（LINＧO）
model:
sets:
row/1..9/:x;
endsets
min=@sum(row(i):x(i));
@sum(row(i)|i #LE# 5:x(i))>=2;
x(3)+x(5)+x(6)+x(8)+x(9)>=3;
x(4)+x(6)+x(7)+x(9)>=2;
2*x(3)-x(1)-x(2)<=0;
x(4)-x(7)<=0;
2*x(5)-x(1)-x(2)<=0;
x(6)-x(7)<=0;
x(8)-x(5)<=0;
2*x(9)-x(1)-x(2)<=0;
@for(row(i):@bin(x(i)));
end
Objective value:
Variable Value Reduced Cost X( 1) X( 2) X( 3) X( 4) X( 5) X( 6) X( 7) X( 8) X( 9)
最优解： x1 = x2 = x3 = x6 = x7= x9 =1, 其它为0；6门课程，总学分21
课号
课名
先修课要求
1
微积分
2
线性代数
3
最优化方法
微积分；线性代数
4
数据结构
计算机编程
5
应用统计
微积分；线性代数
6
计算机模拟
计算机编程
7
计算机编程
8
预测理论
应用统计
9
数学实验
微积分；线性代数
学分最多
多目标优化的处理方法：化成单目标优化。
两目标(多目标)规划
讨论：选修课程最少，学分尽量多，应学习哪些课程？
课程最少
以学分最多为目标，
不管课程多少。
以课程最少为目标，
不管学分多少。
最优解如上，6门课程，总学分21 。
最优解显然是选修所有9门课程 。
多目标规划
在课程最少的前提下以学分最多为目标。
最优解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它为0；总学分由21增至22。
注意：最优解不唯一！
课号
课名
学分
1
微积分
5
2
线性代数
4
3
最优化方法
4
4
数据结构
3
5
应用统计
4
6
计算机模拟
3
7
计算机编程
2
8
预测理论
2
9
数学实验
3
LINGO无法告诉优化问题的解是否唯一。
可将x9 =1 易为x6 =1
增加约束 ，
以学分最多为目标求解。
多目标规划化为单目标规划的方法
对学分数和课程数加权形成一个目标
最优解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1，
其它为0；总学分28。
课号
课名
学分
1
微积分
5
2
线性代数
4
3
最优化方法
4
4
数据结构
3
5
应用统计
4
6
计算机模拟
3
7
计算机编程
2
8
预测理论
2
9
数学实验
3
讲解该例题有两个目的
（1）0－1规划的建模思想，特别是选甲必选乙
的数学处理方法；
（2）多目标规划的处理方法；
(2)假定已经与四家确定代理关系,但每年年初可以决定是中断代理还是恢复代理,如何调整代理关系?
(1)与哪几家确定代理关系,费用最少?
例3 销售代理的开发与中断
问题:某公司开发销售代理,已经确定5年业务量,每年分别是400,500,600,700,800,已经有四家侯选代理,其费用见表.
9
2
3.
70
200
代理4
1
4
90
300
代理3
4
3
80
250
代理2
5
5
100
350
代理1
恢复费用
中断费用
年运行费
一次性费用
年业务量
一次性费用＋五年运行费用
0-1规划模型(多阶段）
xit＝１表示代理i 在第ｔ年建立了代理关系，（xit=0表示不建立代理关系，ｉ=1,2,3,4；t=1,2,3,4,5）
假设公司可以在５年中的任何一年开始与代理建立关系,并且只要建立了关系，就一直保持关系.
模型
假设
目标
函数
决策
变量
约束
条件1
每个代理5年中最多建立一次关系
一次性
费用
9
2
3.
70
200
代理4
1
4
90
300
代理3
4
3
80
250
代理2
5
5
100
350
代理1
恢复费用
中断费用
年运行费
一次性费用
年业务量
因为每个代理最多只建立一次关系
一次性费用＋五年运行费用
目标函数
计算代理１五年的运行费（已知代理1年运行费)
第一年就建立了代理关系，x11=1,x12=0,x13=0,x14=0,
X15=0,则５年的运行费用:
×５x11
第二年才建立了代理关系，x11=0,x12=1,x13=0,x14=0,
X15=0,则５年的运行费用
×（０＋4x12）;
第三年才建立了代理关系，x11=0,x12=0,x13=1,x14=0,
X15=0,则５年的运行费用
×（０＋０＋3x13）;
第四年才建立了代理关系 x11=0,x12=0,x13=0,x14=1,
X15=0,则５年的运行费用
×（０＋０＋０＋2x14）;
第五年才建立了代理关系，x11=0,x12=0,x13=0,x14=0, x15=1，则５年的运行费用
×（０＋０＋０＋０＋x15）;
所以代理1，５年的运行费用
×（5x11＋4x12＋3x13＋2x14＋１x15）;
5年运行费用
目标
函数
9
2
3.
70
200
代理4
1
4
90
300
代理3
4
3
80
250
代理2
5
5
100
350
代理1
恢复费用
中断费用
年运行费
一次性费用
年业务量
约束条件2
每年公司业务量由建立关系的代理完成
第一年：
第二年：
第三年：
第四年：
第五年：
建立的0－1规划数学模型
约束条件
目标函数
模
型
求
解
程
序
model:
sets:
row/1..4/;
tim/1..5/;
matrix(row,tim):x,c;
endsets
min=@sum(matrix(i,t):c(i,2)*x(i,t))+
@sum(row(i):c(i,3)*(5*x(i,1)+4*x(i,2)+3*x(i,3)+2*x(i,4)+x(i,5)));
@for(row(i):@sum(tim(t):x(i,t))<=1);
@for(row(i):@sum(tim(t):x(i,t))<=1);
@sum(row(i):c(i,1)*x(i,1))>=400;
@sum(row(i):c(i,1)*(x(i,1)+x(i,2)))>=500;
@sum(row(i):c(i,1)*(x(i,1)+x(i,2)+x(i,3)))>=600;
@sum(row(i):c(i,1)*(x(i,1)+x(i,2)+x(i,3)+x(i,4)))>=700;
@sum(row(i):c(i,1)*(x(i,1)+x(i,2)+x(i,3)+x(i,4)+x(i,5)))>=800;
@for(matrix(i,j):@bin(x(i,j)));
data:
c=350,100,,5,5,
250,80,,3,4,
300,90,,4,1,
200,70,,2,9;
enddata
end
Objective value:
Variable Value Reduced Cost
X( 1, 1)
X( 1, 2)
X( 1, 3)
X( 1, 4)
X( 1, 5)
X( 2, 1)
X( 2, 2)
X( 2, 3)
X( 2, 4)
X( 2, 5)
X( 3, 1)
X( 3, 2)
X( 3, 3)
X( 3, 4)
X( 3, 5)
X( 4, 1)
X( 4, 2)
X( 4, 3)
X( 4, 4)
X( 4, 5)
最优解： x11 =1, x21 = 1,
x44 = 1,其它为0；第一年与代理1,代理2建立代理关系,第四年与代理4建立代理关系,总费用万元
模型求解结果
讨论：假定已经与四家确定代理关系,但每年年初可以决定是中断代理还是恢复代理,如何调整代理关系?
引入
决策
变量
初始状态:已经与四家有代理关系:即
Xit＝１表示代理i 在第ｔ年从事代理业务,（０表示不从事代理业务),但第ｔ+1年不一定从事代理业务;
注意:与刚才问题不同!!
Yit=1 表示代理i 在第ｔ年初中断代理业务;
Z it=1 表示代理i 在第ｔ年初恢复代理业务;
(ｉ=1,2,3,4；t=1,2,3,4,5）
年运
行费
中断业
务费
恢复业务费
函数
目标
Min=5年运行费+中断代理费+恢复代理费
注意:没有一次费用!!
9
2
3.
70
200
代理4
1
4
90
300
代理3
4
3
80
250
代理2
5
5
100
350
代理1
恢复费用
中断费用
年运行费
一次性费用
年业务量
约束条件
包括:业务量约束,业务中断约束,业务恢复约束
业务量
约束
业务中
断约束
业务恢
复约束
第t年代理i从事业务,第t+1年代理i中断业务,Yit=1
第t年代理i从事业务,第t+1年代理i仍然从事业务,Yit=0
模
型
求
解
程
序
model:
sets:
row/1..4/;
tim/1..5/:b;
matrix(row,tim):x,y,z,c;
endsets
min=@sum(matrix(i,t):c(i,3)*x(i,t))+
@sum(matrix(i,t):c(i,4)*y(i,t))+@sum(matrix(i,t):c(i,5)*z(i,t));
@for(tim(t):@sum(row(i):c(i,1)*x(i,t))>=b(t));
@for(row(i):1-x(i,1)<=y(i,1));
!t=0,x(i,0)=1是初始条件;
@for(row(i):@for(tim(t)|t #LE# 4:x(i,t)-x(i,t+1)<=y(i,t+1)));
@for(row(i):@for(tim(t)|t #LE# 4:x(i,t+1)-x(i,t)<=z(i,t+1)));
@for(matrix(i,j):@bin(x(i,j)));
@for(matrix(i,j):@bin(y(i,j)));
@for(matrix(i,j):@bin(z(i,j)));
data:
c=350,100,,5,5,
250,80,,3,4,
300,90,,4,1,
200,70,,2,9;
b=400,500,600,700,800;
enddata
end
每年代理变量
Objective value:
Variable Value Reduced Cost
X( 1, 1)
X( 1, 2)
X( 1, 3)
X( 1, 4)
X( 1, 5)
X( 2, 1)
X( 2, 2)
X( 2, 3)
X( 2, 4)
X( 2, 5)
X( 3, 1)
X( 3, 2)
X( 3, 3)
X( 3, 4)
X( 3, 5)
X( 4, 1)
X( 4, 2)
X( 4, 3)
X( 4, 4)
X( 4, 5)
模
型求解结果
中断代理决策变量
Y( 1, 1)
Y( 1, 2)
Y( 1, 3)
Y( 1, 4)
Y( 1, 5)
Y( 2, 1)
Y( 2, 2)
Y( 2, 3)
Y( 2, 4)
Y( 2, 5)
Y( 3, 1)
Y( 3, 2)
Y( 3, 3)
Y( 3, 4)
Y( 3, 5)
Y( 4, 1)
Y( 4, 2)
Y( 4, 3)
Y( 4, 4)
Y( 4, 5)
第1年中断代理2和代理3的业务
恢复代理决策变量
Z( 1, 1)
Z( 1, 2)
Z( 1, 3)
Z( 1, 4)
Z( 1, 5)
Z( 2, 1)
Z( 2, 2)
Z( 2, 3)
Z( 2, 4)
Z( 2, 5)
Z( 3, 1)
Z( 3, 2)
Z( 3, 3)
Z( 3, 4)
Z( 3, 5)
Z( 4, 1)
Z( 4, 2)
Z( 4, 3)
Z( 4, 4)
Z( 4, 5)
第1年中断代理2和代理3的业务;
第3年恢复代理2的业务;
最小费用万元
注意:书中最小费用万元有误!!
