《python数学实验与建模》（6）整数与非线性规划

51 阅读 0 评论 34 点赞

我是靠谱客的博主勤劳自行车，最近开发中收集的这篇文章主要介绍《python数学实验与建模》（6）整数与非线性规划，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

声明（求解方式）：

python????
lingo
matlab
6.1 某公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益如表6.6所示.

项目投资额/百万元投资收益/百万元
1 210 150
2 300 210
3 100 60
4 130 80
5 260 180
该公司只有600万资金可用于投资，由于技术上的原因投资收到下列约束:
1. 在项目1，2和3中有且仅有一项被选中
2. 项目3，4只能选中一项
3. 项目5被选中的前提是项目1必须被选中
如何在上述条件下选择一个最好的投资方案，使投资收益最大?

分析：
- 每个项目的投资都有相应的门槛（投资额），且每个项目只能投资一次（假设），所以决策变量为：
  $x_i= left{ begin{aligned} & 1,投资i项目\ &0 ,不投资i项目\ end{aligned} right.~~~~~~i=1,2,3,4,5$
- 建立整数规划模型：
  $max~~z=[150,210,60,80,180]^T[x_1,x_2,x_3,x_4,x_5]\ left{ begin{aligned} &x_1+x_2+x_3=1,\ &x_3+x_4=1,\ &x_5le Mx_1\ &210x_1+300x_2+100x_3+130x_4+260x_5le600\ &x_{i}=0或1，~i=1,2,3,4,5 end{aligned} right.$
  - 其中对于互斥条件，只需要使之和等于1，这样就只能选一个使得等式成立
  - 对于条件3（必要条件），取M为一个极大的正数，若 $x_5=1,而此时x_1neq1，即x_1=0,那么0le x_5le0,x_5=0$ 这样就会产生矛盾，所以条件3必须成立。（反之 $x_1=1,x_5$ 未必为1）
- 这里使用matlab 构造矩阵反而麻烦，不够直观
- lingo
```
sets:
fac/1..5/:x,c,b;

endsets

data:
c=150,210,60,80,180;
b=210,300,100,130,260;
enddata
max=@sum(fac(i):c(i)*x(i));
x(1)+x(2)+x(3)=1;
x(3)+x(4)=1;
x(5)<1000000*x(1);
@sum(fac(i):x(i)*b(i))<600;
@for(fac(i):@bin(x(i)));
# X1=1,X2=0,X3=0,X4=1,X5=1;
#最大值为410
```
- python
```
import cvxpy as cp
import numpy as np
M=1000000
c=np.array([150,210,60,80,180])
beq=np.array([210,300,100,130,260])
x=cp.Variable(5,integer=True)
obj=cp.Maximize(cp.sum(cp.multiply(c,x)))
con=[x[0]+x[1]+x[2]==1,x[2]+x[3]==1,x[4]<=M*x[0],
     cp.sum(cp.multiply(beq,x))<=600,x<=1,x>=0]
prob=cp.Problem(obj,con)
prob.solve()
print("需要投资的项目是:",[i for i in x.value])
print("该组合下最大投资为：",prob.value)

需要投资的项目是: [1.0, 0.0, 0.0, 1.0, 1.0]
该组合下最大投资为： 410.0
```
6.2 一架货机，有效载重为24吨，可运输物品的重量及运费收入如表6.7所示，其中各物品只有一件可供选择，问如何选运物品使得运费总收入最多？

物品 1 2 3 4 5 6
重量/吨 8 13 6 9 5 7
收入/万元 3 5 2 4 2 3
建立整数规划模型：
$max~~z=[3,5,2,4,2,3]^Tcdot X\~~~~~~~~~~~~~~~~~~~~~ left{ begin{aligned} &8x_1+13x_2+6x_3+9x_4+5x_5+7x_6le 24\ &x_i=0或1,i=1,2,3,4,5,6 end{aligned} right.$
- lingo
```
  sets:
fac/1..6/:x,c,b;

endsets

data:
c=3,5,2,4,2,3;
b=8,13,6,9,5,7;
enddata
max=@sum(fac(i):x(i)*c(i));
@sum(fac(i):x(i)*b(i))<24;
@for(fac(i):@bin(x(i)));
#结果如下  
  Objective value:                              10.00000

                                                                          X( 1)        1.000000           
                                                                           X( 2)       0.000000         
                                                                           X( 3)        0.000000        
                                                                           X( 4)        1.000000        
                                                                           X( 5)        0.000000         
                                                                           X( 6)        1.000000           
```
- matlab
```
c=[3,5,2,4,2,3];
A=[8,13,6,9,5,7];b=24;
inction=1:1:6;%决策变量个数向量
[x,fval]=intlinprog(-c,inction,A,b,[],[],zeros(6,1),ones(6,1));
disp('可行解=');disp(x');
disp('最大值=');disp(-fval);

%结果
可行解=
     1     0     0     1     0     1

最大值=
    10
```
- python
```
import cvxpy as cp
import numpy as np
c=np.array([3,5,2,4,2,3])
A=np.array([8,13,6,9,5,7]);b=24
x=cp.Variable(6,integer=True)
obj=cp.Maximize(cp.sum(cp.multiply(c,x)))
con=[cp.sum(cp.multiply(A,x))<=24,x<=1,x>=0]
prob=cp.Problem(obj,con)
prob.solve()
print("可行解为：",x.value)
print('最大值为：',prob.value)

#结果
可行解为： [1. 0. 0. 1. 0. 1.]
最大值为： 10.0
```
6.3 有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书面试，然后到部门主管处面试，最后到经理处面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）

由于4名同学的专业背景不同，所以每个同学在每个阶段面试的时间也不同

如表6.8所示。这四名同学约定一起面试完以后离开公司。假定现在是早晨8：00，请问他们最早何时能离开公司？

秘书初试主管复试经理面试
甲 14 16 21
乙 19 17 10
丙 10 15 12
丁 9 12 13
问题分析：
- 假设，公司的秘书，主管，经理只有一人，需要排队轮流面试，需要确定的是进行秘书的面试的顺序（因为不允许插队，所以当第一轮面试顺序确定之后也就决定了最后的时间）
- 这里记8：00为初始0时刻（单位：分钟）
- 可以设决策变量为 $x_{ij},$ 代表第i个同学接受第j个考官面试的开始时间， $t_{ij}$ 代表这次面试所需的时间
- 目标函数 $min~~time=max{t_{i3}+x_{i3}}$ 即在最优解下三人之中最晚面试的时间
- 约束条件：
  - 每个同学的面试顺序：必须挨个面试官进行面试 $x_{ik}+t_{ik}<x_{i+1,k}$
  - 同学之间的先后顺序（如甲在秘书面试时，其余三人都不在）：记 $y_{ik}$ 表示第 $k$ 名同学排在第 $i$ 名同学的前面。 $y_{ik}=1或0$
    - $x_{ij}+t_{ij}-x_{kj}le time~y_{ik},i,k=1,2,3,4,i<k,j=1,2,3$
    - 如果 $y_{ik}=1$ , $k 排在 i 的前面$ ，则不等式右边为最晚的面试时间，k开始j面试的时刻-i完成j面试的时刻必然小于最晚的面试时间（最优解下）因为 $x_{ij}+t_{ij}$ （无效约束）
    - 如果 $y_{ik}=0$ ,那么不等式为 $x_{ij}+t_{ij}le x_{kj}$ ,即k开始面试的时刻晚于i完成面试的时刻，也就表达了k排在i的后面（有效约束）
    - $x_{kj}+t_{kj}-x_{ij}le time(1-~y_{ik}),i,k=1,2,3,4,i<k,j=1,2,3$
      - 与上述同理，表示的是 $y_{ik}=1$ 时的有效约束
- 建立混合整数规划模型：
  $min~max{t_{i3}+x_{i3}}\ left{ begin{aligned} &x_{ij}+t_{ij}-x_{kj}le max{t_{i3}+x_{i3}}~y_{ik},\ &x_{kj}+t_{kj}-x_{ij}le max{t_{i3}+x_{i3}}(1-~y_{ik})\ &x_{ij}+t_{ij}<x_{i,j+1} end{aligned} right.$
lingo:
```
#参考CSDN
model:
Title 面试问题; 
SETS: Person/1..4/; 
Stage/1..3/; 
PXS(Person,Stage): T, X; 
PXP(Person,Person)|&1 #LT# &2: Y; 
ENDSETS 
DATA: 
T=13, 15, 20, 10 , 20 , 18, 20, 16, 10, 8, 10, 15; 
ENDDATA 
[obj] min=MAXT; 
MAXT>= @max(PXS(i,j)|j#EQ#3:x(i,j)+t(i,j)); 
 
@for(PXS(i,j)|j#LT#3:x(i,j)+t(i,j)<x(i,j+1)); 

@for(Stage(j):   
   @for(PXP(i,k):x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k));  
   @for(PXP(i,k):x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k)))); 
@for(PXP: @bin(y)); 
end
```
6.4某公司向用户提供发动机，按合同规定，其交货数量和日期是：第一季度末交40台，第二季度末交60台，第三季度末交80台。

工厂的最大生产能力为每季100台，每季的生产费用是 $f(x)=50000x+200x^2$ ,此处 $x$ 为该季度生产发动机的台数。若工厂生产的多，多余的发动机可移到下季向用户交货，这样，工厂就需要支付存储费，每台发动机的存储费为4000元，问该厂每季应生产多少台发动机，才能既满足交货合同，又使工厂所花费的费用最少（假定第一季度开始时发动机无存货）

分析：
- 决策变量： $x_1,x_2,x_3$ 为每一季度生产的台数
- 目标函数： $f(x_i)+4000(x_1-40)+4000(x_1+x_2-100)$ :每季度生产费用之和+存储费用之和
- 约束条件：
  - 控制目标函数中 $x_1le40+y_1M,x_1+x_2le100+y_2,y_i=0或1$ ,代表该季度是否有存货
  - 每季度最多生产100台，所以限制: $0 \leq x \leq 100$
  - 每季度都要完成合同的交货量：
    - $x_1ge40$
    - $x_2+(x_1-40)y_1ge60$
    - $x_3+(x_1+x_2-100)y_2=100$ 因为第一季度没有存货，所以第三季度应该刚好完成合同要求
- 建立混合整数非线性规划模型如下：
  $min~~z=50000(x_1+x_2+x_3)+200(x_1^2+x_2^2+x_3^2)+4000(x_1-40)+4000(x_1+x_2-100)\ left{ begin{aligned} &x_1le 40+y_1M\ &x_1+x_2le100+y_2M\ &x_1ge40\ &x_2+(x_1-40)y_1ge60\ &x_3+(x_1+x_2-100)y_2=100\ &0le x_ile100,i=1,2,3\ &y_i=0或1，i=1,2 end{aligned} right.$
- lingo
```
sets:
fac/1..3/:x;
plant/1..2/:y;
endsets
data:
M=10000000000;
enddata
min=50000*@sum(fac:x)+200*@sum(fac:x^2)+4000*(2*x(1)+x(2)-140);
x(1)<40+y(1)*M;
x(1)+x(2)<100+y(2)*M;
x(1)>40;
x(2)+(x(1)-40)*y(1)>60;
x(3)+(x(1)+x(2)-100)*y(2)=100;
@for(fac:@bnd(0,x,100));
@for(fac:@gin(x));
@for(plant:@bin(y));

 Objective value:                             0.1286680E+08
 
                                     M       0.1000000E+11       
                                   X( 1)        57.00000            
                                   X( 2)        66.00000            
                                   X( 3)        77.00000            
                                   Y( 1)        1.000000            
                                   Y( 2)        1.000000            
```
- python（可以看作二次规划）：不建议
6.5 已知矩阵 $\4&2&6\5&6&3 end{array}right]$ , $x=left[begin{array}{rrr}x_1\x_2\x_3end{array}right]$ ,求二次型 $f(x_1,x_2,x_3)=x^TAx$ 在单位球面

$x_1^2+x_2^2+x_3^2=1$ 上的最小值

非线性规划：
- matlab
```
%创建函数文件（等式约束非线性）
function [c,ceq] = func2(x)
 c=[];
 ceq=x(1)^2+x(2)^2+x(3)^2-1;
end
%创建脚本文件
A=[1,4,5;4,2,6;5,6,3];
 f=@(x)x'*A*x;
 [x,fval]=fmincon(f,[0,1,0]',[],[],[],[],[],[],'func2');
disp(x);disp(fval);

x =                   fval =-3.6687 
    0.3130
    0.5774
   -0.7541
```
6.6 某银行营业部设立3个窗口，分别为个人业务，公司业务和特殊业务（如外汇和理财）。现有3名服务人员，每人处理不同的业务的效率（每天服务的最大客户数）见表6.9，以及每人处理不同业务的质量（如客户满意度）见表6.10.如何为服务人员安排相应的工作（服务窗口）才能使服务效率和服务质量都高。

6.9:

个人业务公司业务特殊业务
员工1 20 12 10
员工2 12 15 9
员工3 6 5 10
6.10

个人业务公司业务特殊业务
员工1 6 8 10
员工2 6 5 9
员工3 9 10 8
分析(多目标指派问题)详见多目标规划：
- 假设3名员工各自只能选择1种业务，决策变量为： $x_{ij}$ 0-1变量，代表第i名员工是否选择第j项业务
- 目标函数为 $sum_{i=1}^{n}sum_{j=1}^nc_{ij}x_{ij}，sum_{i=1}^{n}sum_{j=1}^nC_{ij}x_{ij}$ 要尽可能让两个目标最大