数学建模（1）：线性规划_以下哪些问题线性规划

首先明确，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

在解决这类型的实际问题时，应当选择适当的决策变量来建立有效模型。在数学建模中，涉及到线性规划的问题有以下几个类型：

§1 一般线性规划

简单的线性规划问题都可使用matlab或lingo来处理。但对于matlab来说，所给定的模型必须满足标准型。因此，在matlab中，往往需要人工转化再输入计算。

标准型的转化规则：

1. 目标函数统一求max，若为min则乘以-1，作向量b
2. 约束中出现≥号，两端同时乘以-1，改写为≤号，作向量a
3. 若存在等式约束，令左侧系数为向量aeq，右侧为beq
4. 若需要变量全大于0约束，加入全0阵。全0阵的行为变量个数，列为1。

转化完成后，使用linprog函数做计算即可。例如：

c=[2;3;1]; 
a=[1,4,2;3,2,0];
b=[8;6]; 
[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))
1
2
3
4

使用lingo做计算则更为简便。只需要将约束条件，目标函数直接输入即可。例如：

min=2*x1+3*x2-5*x3;
x1+x2+x3=7;
2*x1-5*x2+x3>=10;
x1+3*x2+x3<=12;
1
2
3
4

注意：在lingo中，默认所有的变量总是大于等于0。

§2 产销问题

产销问题是一种特殊的线性规划问题，可以使用表上作业法，也可以使用lingo来完成。例如，6*8的产销平衡的lingo模型如下：

model:
sets:
  warehouses/wh1..wh6/: capacity;
  reigon/v1..v8/: demand;
  links(warehouses,reigon): cost, volume;
endsets
  min=@sum(links: cost*volume);
  @for(reigon(J):
    @sum(warehouses(I): volume(I,J))=demand(J));
  @for(warehouses(I):
    @sum(reigon(J): volume(I,J))<=capacity(I));
 
data:
  capacity=60 55 51 43 41 52;
  demand=35 37 22 32 41 32 43 38;
  cost=
  	   6 2 6 7 4 2 9 5
       4 9 5 3 8 5 8 2
       5 2 1 9 7 4 3 3
       7 6 7 3 9 2 7 1
       2 3 9 5 7 2 6 5
       5 5 2 2 8 1 4 3;
enddata
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

为什么不适用matlab来处理？因为其使用向量和矩阵表示的形式对于具有双下标决策变量的实际问题显得比较复杂。

§3 指派问题

指派问题可看作0-1规划问题。由于其双下标特性，为求简便，我们同样可以使用lingo来求解。对于一个4*4的指派问题，lingo模型如下：

model:
sets:
emps/1..4/;
tasks/1..4/;
solution(emps,tasks):cost,x;
endsets

data:
cost =
16 15 19 22
17 21 19 18
24 22 18 17
17 19 22 16;
enddata

min = @sum(emps(I) :
    @sum(tasks(J): cost(I,J)*x(I,J))
);
@for(emps(I):
    @sum(tasks(J):x(I,J)) = 1 
);
@for(tasks(J):
    @sum(emps(I):x(I,J)) = 1
);
@for(emps(I):
    @for(tasks(J) : @gin(x(I,J)))
);
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

同样的，指派问题也可用匈牙利算法来求解。算法主要依据以下事实：

如果系数矩阵每一行（或一列）中每一元素都加上或减去同一个数，则得到的新矩阵具有相同的最优指派。

对于矩阵：

其总有最优指派结果相同的变换矩阵：

使得变换矩阵存在n个行列的值不同的0元素，n为矩阵的阶，抽取这些0元素所在的行列的值，就是题目所需要的解。
若矩阵不能找出n个0元素，则可以继续作等价变换，步骤如下：
(1) 对未选出 0 元素的行打∨；
(2) 对∨行中 0 元素所在列打∨；
(3) 对∨列中选中的 0 元素所在行打∨；
(4) 重复2、3直到无法再打∨为止。

§4 原始&对偶问题

有时，题目会给定一对线性规划模型，并要求根据其中一个模型（称原始模型）的性质来求解另一个模型（称对偶模型）的性质。求解它的对偶往往是有一定意义的。例如，其对偶更容易得到所需结果以反推原模型的解。或者，其对偶在另一个角度上存在实际意义。

在一对对偶的线性规划模型中：
（1） 原始问题中的第 j 列系数与其对偶问题中的第 j 行的系数相同
（2） 原始目标函数的各个系数行与其对偶问题右侧的各常数列相同
（3） 原始问题右侧的各常数列与其对偶目标函数的各个系数行相同
（4） 不等式方向和优化方向相反。

不恰当地来说，对偶双方的关系类似于函数与反函数。利用对偶进行计算的行为类似于反证法。

§5 投资问题

在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a ，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。
固定风险水平，优化收益的模型求解可以用matlab定步长探查的方法来求解

clc,clear 
a=0; 
hold on 
while a<0.05     
c=[-0.05,-0.27,-0.19,-0.185,-0.185];    
A=[zeros(4,1),diag([0.025,0.015,0.055,0.026])];    
b=a*ones(4,1);     
Aeq=[1,1.01,1.02,1.045,1.065];     
beq=1;     
LB=zeros(5,1);     
[x,Q]=linprog(c,A,b,Aeq,beq,LB);     
Q=-Q;     
plot(a,Q,'*r');     
a=a+0.001; 
end 
xlabel('a'),ylabel('Q') 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16