声明（求解方式）：
-
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，2和3中有且仅有一项被选中
- 项目3，4只能选中一项
- 项目5被选中的前提是项目1必须被选中
如何在上述条件下选择一个最好的投资方案，使投资收益最大?
分析：
-
每个项目的投资都有相应的门槛（投资额），且每个项目只能投资一次（假设），所以决策变量为：
xi
=
{
1
,
投资
i
项目
0
,
不投资
i
项目
i
=
1
,
2
,
3
,
4
,
5
x_i= \left\{ \begin{aligned} & 1,投资i项目\\ &0 ,不投资i项目\\ \end{aligned} \right.~~~~~~i=1,2,3,4,5
x
i
=
{
1
,
投资
i
项目
0
,
不投资
i
项目
i
=
1
,
2
,
3
,
4
,
5
-
建立整数规划模型：
ma
x
z
=
[
150
,
210
,
60
,
80
,
180
]
T
[
x
1
,
x
2
,
x
3
,
x
4
,
x
5
]
{
x
1
+
x
2
+
x
3
=
1
,
x
3
+
x
4
=
1
,
x
5
≤
M
x
1
210
x
1
+
300
x
2
+
100
x
3
+
130
x
4
+
260
x
5
≤
600
x
i
=
0
或
1
，
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_5\le Mx_1\\ &210x_1+300x_2+100x_3+130x_4+260x_5\le600\\ &x_{i}=0或1，~i=1,2,3,4,5 \end{aligned} \right.
ma
x
z
=
[
150
,
210
,
60
,
80
,
180
]
T
[
x
1
,
x
2
,
x
3
,
x
4
,
x
5
]
⎩
⎨
⎧
x
1
+
x
2
+
x
3
=
1
,
x
3
+
x
4
=
1
,
x
5
≤
M
x
1
210
x
1
+
300
x
2
+
100
x
3
+
130
x
4
+
260
x
5
≤
600
x
i
=
0
或
1
，
i
=
1
,
2
,
3
,
4
,
5
- 其中对于互斥条件，只需要使之和等于1，这样就只能选一个使得等式成立
-
对于条件3（
必要条件
），取M为一个极大的正数，若
x5
=
1
,
而此时
x
1
≠
1
，即
x
1
=
0
,
那么
0
≤
x
5
≤
0
,
x
5
=
0
x_5=1,而此时x_1\neq1，即x_1=0,那么0\le x_5\le0,x_5=0
x
5
=
1
,
而此时
x
1
=
1
，即
x
1
=
0
,
那么
0
≤
x
5
≤
0
,
x
5
=
0
这样就会产生矛盾，所以条件3必须成立。（反之
x1
=
1
,
x
5
x_1=1,x_5
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 建立整数规划模型：
ma
x
z
=
[
3
,
5
,
2
,
4
,
2
,
3
]
T
⋅
X
{
8
x
1
+
13
x
2
+
6
x
3
+
9
x
4
+
5
x
5
+
7
x
6
≤
24
x
i
=
0
或
1
,
i
=
1
,
2
,
3
,
4
,
5
,
6
max~~z=[3,5,2,4,2,3]^T\cdot X\\~~~~~~~~~~~~~~~~~~~~~ \left\{ \begin{aligned} &8x_1+13x_2+6x_3+9x_4+5x_5+7x_6\le 24\\ &x_i=0或1,i=1,2,3,4,5,6 \end{aligned} \right.
ma
x
z
=
[
3
,
5
,
2
,
4
,
2
,
3
]
T
⋅
X
{
8
x
1
+
13
x
2
+
6
x
3
+
9
x
4
+
5
x
5
+
7
x
6
≤
24
x
i
=
0
或
1
,
i
=
1
,
2
,
3
,
4
,
5
,
6
- 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时刻（单位：分钟）
-
可以设决策变量为
xi
j
,
x_{ij},
x
ij
,
代表第i个同学接受第j个考官面试的开始时间，
ti
j
t_{ij}
t
ij
代表这次面试所需的时间 -
目标函数
mi
n
t
i
m
e
=
m
a
x
{
t
i
3
+
x
i
3
}
min~~time=max\{t_{i3}+x_{i3}\}
min
t
im
e
=
ma
x
{
t
i
3
+
x
i
3
}
即
在最优解下三人之中最晚面试的时间
-
约束条件：
-
每个同学的面试顺序：必须挨个面试官进行面试
xi
k
+
t
i
k
<
x
i
+
1
,
k
x_{ik}+t_{ik}<x_{i+1,k}
x
ik
+
t
ik
<
x
i
+
1
,
k
-
同学之间的先后顺序（如甲在秘书面试时，其余三人都不在）：记
yi
k
y_{ik}
y
ik
表示第
kk
k
名同学排在第
ii
i
名同学的前面。
yi
k
=
1
或
0
y_{ik}=1或0
y
ik
=
1
或
0
-
xi
j
+
t
i
j
−
x
k
j
≤
t
i
m
e
y
i
k
,
i
,
k
=
1
,
2
,
3
,
4
,
i
<
k
,
j
=
1
,
2
,
3
x_{ij}+t_{ij}-x_{kj}\le time~y_{ik},i,k=1,2,3,4,i<k,j=1,2,3
x
ij
+
t
ij
−
x
kj
≤
t
im
e
y
ik
,
i
,
k
=
1
,
2
,
3
,
4
,
i
<
k
,
j
=
1
,
2
,
3
-
如果
yi
k
=
1
y_{ik}=1
y
ik
=
1
,
k排在
i
的前面
k排在i的前面
k
排在
i
的前面
，则不等式右边为最晚的面试时间，k开始j面试的时刻-i完成j面试的时刻必然小于最晚的面试时间（最优解下）
因为
ti
m
e
≥
∀
x
i
j
+
t
i
j
time\ge \forall x_{ij}+t_{ij}
t
im
e
≥
∀
x
ij
+
t
ij
（无效约束） -
如果
yi
k
=
0
y_{ik}=0
y
ik
=
0
,那么不等式为
xi
j
+
t
i
j
≤
x
k
j
x_{ij}+t_{ij}\le x_{kj}
x
ij
+
t
ij
≤
x
kj
,即k开始面试的时刻晚于i完成面试的时刻，也就表达了k排在i的后面（有效约束） -
xk
j
+
t
k
j
−
x
i
j
≤
t
i
m
e
(
1
−
y
i
k
)
,
i
,
k
=
1
,
2
,
3
,
4
,
i
<
k
,
j
=
1
,
2
,
3
x_{kj}+t_{kj}-x_{ij}\le time(1-~y_{ik}),i,k=1,2,3,4,i<k,j=1,2,3
x
kj
+
t
kj
−
x
ij
≤
t
im
e
(
1
−
y
ik
)
,
i
,
k
=
1
,
2
,
3
,
4
,
i
<
k
,
j
=
1
,
2
,
3
-
与上述同理，表示的是
yi
k
=
1
y_{ik}=1
y
ik
=
1
时的有效约束
-
与上述同理，表示的是
-
-
每个同学的面试顺序：必须挨个面试官进行面试
-
建立混合整数规划模型：
mi
n
m
a
x
{
t
i
3
+
x
i
3
}
{
x
i
j
+
t
i
j
−
x
k
j
≤
m
a
x
{
t
i
3
+
x
i
3
}
y
i
k
,
x
k
j
+
t
k
j
−
x
i
j
≤
m
a
x
{
t
i
3
+
x
i
3
}
(
1
−
y
i
k
)
x
i
j
+
t
i
j
<
x
i
,
j
+
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.
min
ma
x
{
t
i
3
+
x
i
3
}
⎩
⎨
⎧
x
ij
+
t
ij
−
x
kj
≤
ma
x
{
t
i
3
+
x
i
3
}
y
ik
,
x
kj
+
t
kj
−
x
ij
≤
ma
x
{
t
i
3
+
x
i
3
}
(
1
−
y
ik
)
x
ij
+
t
ij
<
x
i
,
j
+
1
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
)
=
50000
x
+
200
x
2
f(x)=50000x+200x^2
f
(
x
)
=
50000
x
+
200
x
2
,此处
xx
x
为该季度生产发动机的台数。若工厂生产的多，
多余的发动机可移到下季向用户交货
，这样，工厂就需要支付存储费，每台发动机的
存储费为4000元
，问该厂每季应生产多少台发动机，才能既满足交货合同，又使工厂所花费的费用最少（假定第一季度开始时发动机无存货）分析：
-
决策变量：
x1
,
x
2
,
x
3
x_1,x_2,x_3
x
1
,
x
2
,
x
3
为每一季度生产的台数 -
目标函数：
∑f
(
x
i
)
+
4000
(
x
1
−
40
)
+
4000
(
x
1
+
x
2
−
100
)
\sum f(x_i)+4000(x_1-40)+4000(x_1+x_2-100)
∑
f
(
x
i
)
+
4000
(
x
1
−
40
)
+
4000
(
x
1
+
x
2
−
100
)
:每季度生产费用之和+存储费用之和 -
约束条件：
-
控制目标函数中
x1
≤
40
+
y
1
M
,
x
1
+
x
2
≤
100
+
y
2
,
y
i
=
0
或
1
x_1\le40+y_1M,x_1+x_2\le100+y_2,y_i=0或1
x
1
≤
40
+
y
1
M
,
x
1
+
x
2
≤
100
+
y
2
,
y
i
=
0
或
1
,代表该季度是否有存货 -
每季度最多生产100台，所以限制:
0≤
x
≤
100
0\le x\le100
0
≤
x
≤
100
-
每季度都要完成合同的交货量：
-
x1
≥
40
x_1\ge40
x
1
≥
40
-
x2
+
(
x
1
−
40
)
y
1
≥
60
x_2+(x_1-40)y_1\ge60
x
2
+
(
x
1
−
40
)
y
1
≥
60
-
x3
+
(
x
1
+
x
2
−
100
)
y
2
=
100
x_3+(x_1+x_2-100)y_2=100
x
3
+
(
x
1
+
x
2
−
100
)
y
2
=
100
因为第一季度没有存货，所以第三季度应该刚好完成合同要求
-
-
控制目标函数中
-
建立混合整数非线性规划模型如下：
mi
n
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
)
{
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
0
≤
x
i
≤
100
,
i
=
1
,
2
,
3
y
i
=
0
或
1
，
i
=
1
,
2
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_1\le 40+y_1M\\ &x_1+x_2\le100+y_2M\\ &x_1\ge40\\ &x_2+(x_1-40)y_1\ge60\\ &x_3+(x_1+x_2-100)y_2=100\\ &0\le x_i\le100,i=1,2,3\\ &y_i=0或1，i=1,2 \end{aligned} \right.
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
)
⎩
⎨
⎧
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
0
≤
x
i
≤
100
,
i
=
1
,
2
,
3
y
i
=
0
或
1
，
i
=
1
,
2
- 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 已知矩阵
A=
[
1
4
5
4
2
6
5
6
3
]
A=\left[\begin{array}{rrr}1 & 4&5 \\4&2&6\\5&6&3 \end{array}\right]
A
=
⎣
⎡
1
4
5
4
2
6
5
6
3
⎦
⎤
,
x=
[
x
1
x
2
x
3
]
x=\left[\begin{array}{rrr}x_1\\x_2\\x_3\end{array}\right]
x
=
⎣
⎡
x
1
x
2
x
3
⎦
⎤
,求二次型
f(
x
1
,
x
2
,
x
3
)
=
x
T
A
x
f(x_1,x_2,x_3)=x^TAx
f
(
x
1
,
x
2
,
x
3
)
=
x
T
A
x
在单位球面
x1
2
+
x
2
2
+
x
3
2
=
1
x_1^2+x_2^2+x_3^2=1
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种业务，决策变量为：
xi
j
x_{ij}
x
ij
0-1变量，代表第i名员工是否选择第j项业务 -
目标函数为
∑i
=
1
n
∑
j
=
1
n
c
i
j
x
i
j
，
∑
i
=
1
n
∑
j
=
1
n
C
i
j
x
i
j
\sum_{i=1}^{n}\sum_{j=1}^nc_{ij}x_{ij}，\sum_{i=1}^{n}\sum_{j=1}^nC_{ij}x_{ij}
∑
i
=
1
n
∑
j
=
1
n
c
ij
x
ij
，
∑
i
=
1
n
∑
j
=
1
n
C
ij
x
ij
要尽可能让两个目标最大
-