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

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

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

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

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

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

 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函数表示整数约束。

版权声明：本文为博主原创文章，未经博主允许不得转载。