南邮运筹学实验3：01整数规划

题目：某公司计划在市区的东、西、南、北四区建立销售中心，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：

在东区由A1 ， A2 ，A3 三个点至多选择两个；

在西区由A4 ， A5 两个点中至少选一个；

在南区由A6 ， A7 两个点中至少选一个；

在北区由A8 ， A9 ， A10 三个点中至少选两个。

	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
投资额	110	120	150	80	70	90	80	140	160	180
利润	36	40	50	25	20	30	25	48	58	60

Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过750万元，问应选择哪几个销售点，可使年利润为最大?

解：

一、建立模型

这是一道整数规划问题。写出目标函数，求年利润最大。

先设东区选择A1位置：x1。以此类推，自变量设为：

东区：x1，x2，x3。

西区：x4，x5。

南区：x6，x7。

北区：x8，x9，x10。

所以，目标函数为：

max z = 36x1+40x2+50x3+25x4+20x5+30x6+25x7+48x8+58x9+60x10

约束条件为：

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2

110x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤750

Xi=0或1，i =1,2,3,4,5,6,7,8,9,10

先转化为标准型。

min z = -36x1-40x2-50x3-25x4-20x5-30x6-25x7-48x8-58x9-60x10

约束条件为：

x1+x2+x3≤2

-x4-x5≤1

-x6-x7≤1

-x8-x9-x10≤2

110x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤750

Xi=0或1，i =1,2,3,4,5,6,7,8,9,10

二、计算过程

1. Excel

约束条件位置，输入公式：=SUMPRODUCT(B2:K2,B5:K5)

以此类推，其他四个约束条件位置也是如此输入公式。

总利润，输入公式：=SUMPRODUCT(B2:K2,B3:K3)

得出结果：

2. Lingo

model:
max = 36*x1+40*x2+50*x3+25*x4+20*x5+30*x6+25*x7+48*x8+58*x9+60*x10;
x1+x2+x3<=2;
x4+x5>=1;
x6+x7>=1;
x8+x9+x10>=2;
110*x1+120*x2+150*x3+80*x4+70*x5+90*x6+80*x7+140*x8+160*x9+180*x10<=750;
@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);
@bin(x6);@bin(x7);@bin(x8);@bin(x9);@bin(x10);
end

3. Matlab

f=[-36 -40 -50 -25 -20 -30 -25 -48 -58 -60];
ic=[1,2,3,4,5,6,7,8,9,10];
A=[1,1,1,0,0,0,0,0,0,0;0,0,0,-1,-1,0,0,0,0,0;0,0,0,0,0,-1,-1,0,0,0;0,0,0,0,0,0,0,-1,-1,-1;110,120,150,80,70,90,80,140,160,180];
b=[2,-1,-1,-2,750];  
lb=zeros(10,1);  
ub=ones(10,1);  
[x,fval,flag]=intlinprog(f,ic,A,b,[],[],lb,ub)

f表示目标函数的系数矩阵，即利润。

ic表示10个自变量。

A表示5个约束条件前的变量系数矩阵。

b表示5个约束条件后面的值。

lb表示10个自变量最小值取0。

ub表示10个自变量最大只能是1。

在上述的代码中：[x,fval,flag]=intlinprog(f,ic,A,b,[],[],lb,ub)

[] 代表不存在或空，因为在上面的例子中不存在等式约束，所以 Aeq 和 beq 的位置为 []。intlinprog函数表示整数约束。