数学建模笔记-最优化问题

一、基本概念

最优化：首先是一种理念，其次才是一种方法，它所追求的是一种“至善”之道，一种追求卓越的精神。
例子：小明同学，烧一壶水要8分钟，灌开水要1分钟，取牛奶和报纸要5分钟，整理书包要6分钟，为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？

最优化问题的数学模型的一般形式为：

\begin{align*} &\text{opt } z = f(x) \\ &\text{s.t. } h_i(x) = 0, \quad i = 1, \cdots, l \\ &\qquad g_j(x) \leq 0, \quad j = 1, \cdots, m \\ &\qquad t_k(x) \geq 0, \quad k = 1, \cdots, n \\ &\qquad x \in D \subseteq \mathbb{R}^s \end{align*}

opt是最优化的缩写，问题应该针对的是求最大值或者求最小值的问题，st是约束

三个要素：决策变量（decision variable）、目标函数（objective function）、约束条件（constraints）

满足st的解x称为可行解(feasiblesolution)，
同时满足st和opt的解x称为最优解(Cptimal solution)，
整个可行域上的最优解称为全局最优解(globaloptimalsolution)，
可行域中某个领域上的最优解称为局部最优解(localoptimalsolution)，
最优解所对应的目标函数值称为最优值(optimum)。

优化模型的分类

（一）按有无约束条件可分为：
1.无约束优化(unconstrained optimization)
2.约束优化(constrained optimization)
大部分实际问题都是约束优化的问题

（二）按决策变量取值是否连续
1.数学规划或连续优化
可继续划分为
线性规划(LP)Linear programming 和 非线性规划(NLP) Nonlinear programming
在非线性规划中有一种规划叫做二次规划(QP)Quadratic programming，目标为二次函数，约束为线性函数。
2.离散优化或组合优化
包含：
整数规划(IP)Integer programming，整数规划中又包含很重要的一类规划：0-1（整数)规划Zero-oneprogramming，这类规划问题的决策变量只取0或者1。

（三)按目标的多少可分为：
1.单目标规划
2.多目标规划

（四）按模型中参数和变量是否具有不确定性可分为：
1.确定性规划
2不确定性规划

二、单目标规划

​​例题1:问题描述​​

汽车厂需制定生产计划，在以下约束条件下实现利润最大化

例题1图表：汽车厂生产计划参数表​​

​​决策变量​​：
设生产小型、中型、大型汽车数量分别为 $$x_{1},x_{2},x_{3}$$​

总获利

$$ \text{Max } z = 2x_{1} + 3x_{2} + 4x_{3} $$

原料供应

$$ 1.5x_{1} + 3x_{2} + 5x_{3} \leq 600 $$

劳动时间

$$ 280x_{1} + 250x_{2} + 400x_{3} \leq 60000 $$

非负约束

$$ x_{1}, x_{2}, x_{3} \geq 0 \text{且为整数}$$

生产小型64台，中型168台，大型0台，利润632

例题2：问题描述​​

某自来水公司需从A、B、C三个水库向甲、乙、丙、丁四个用户供水，目标是通过合理分配供水量使公司获利最大。具体参数如下：

1. ​​水库供水量（千吨）​​：
   • A：50
   • B：60
   • C：50
2. ​​用户用水需求（千吨）​​：
   • ​​基本用水量​​（必须满足）：
     • 甲：30 | 乙：70 | 丙：10 | 丁：10
   • ​​额外用水量​​（可选择性满足）：
     • 甲：50 | 乙：30 | 丙：无 | 丁：无
3. ​​成本与收入​​：
   • ​​收入​​：900元/千吨（所有用户统一）。
   • ​​其他支出​​：450元/千吨（固定成本）。
   • ​​引水管理费​​（元/千吨，见下表）。

表1：引水管理费（元/千吨）​​

​​表2：用户用水量约束（千吨）​​

引水管理费表中缺的数值可以写一个超级大的数避免引去那边。

决策变量

水库i向j区的日供水量为 x[i,j] (x[3,4]=0)

目标函数

$$ Min\,Z = \begin{aligned}[t] &160x_{11} + 130x_{12} + 220x_{13} + 170x_{14} \\ &+ 140x_{21} + 130x_{22} + 190x_{23} + 150x_{24} \\ &+ 190x_{31} + 200x_{32} + 230x_{33} \end{aligned} $$

供应约束

$$ \begin{cases} x_{11} + x_{12} + x_{13} + x_{14} = 50 \\ x_{21} + x_{22} + x_{23} + x_{24} = 60 \\ x_{31} + x_{32} + x_{33} = 50 \end{cases} $$

需求约束

$$ \begin{cases} 30 \leq x_{11} + x_{21} + x_{31} \leq 80 & \text{引水管理费：24400（元）} \\ 70 \leq x_{12} + x_{22} + x_{32} \leq 140 & \text{最大利润：47600（元）} \\ 10 \leq x_{13} + x_{23} + x_{33} \leq 30 \\ 10 \leq x_{14} + x_{24} \leq 50 \end{cases} $$

例题4（下料问题）问题描述​​

某工厂需使用长度为5.5米的圆钢原材料，切割成以下三种规格的圆钢材料：

• ​​A型​​：长度3.1米，需求100根
• ​​B型​​：长度2.1米，需求200根
• ​​C型​​：长度1.2米，需求400根

​​目标​​：通过合理选择下料方式，使所需圆钢原材料总数最少（或余料总量最省）。

​​下料方式与余料分析​​

现有五种下料方式（一至五），每种方式切割后产生的A、B、C型数量及余料如下表所示：

​​图表：下料方案与余料统计表​​

决策变量

设第i种截法的数量为 \( x_i \)

目标函数

min \( Z = \sum_{i=1}^{5} x_i \)

约束条件有：

需求约束

• \( x_1 + x_2 \geq 100 \)
• \( x_1 + 2x_3 + x_4 \geq 200 \)
• \( 2x_2 + x_3 + 2x_4 + 4x_5 \geq 400 \)

非负约束

\( x_i \geq 0, i = 1, 2, \ldots, 5 \) 且为整数

下面是LINGO的代码：

MODEL:
SETS:
HANG/1..3/:A;
LIE/1..5/:B,X;
XISHU(HANG,LIE):C;
ENDSETS
DATA:
A=100 200 400;
B=0.3 0 0.1 1.0 0.7;
C=1 1 0 0 0
    1 0 2 1 0
    0 2 1 2 4;
ENDDATA
MIN=@SUM(LIE(J):X(J)); !MIN=@SUM(LIE(J):b(J)*X(J));
@FOR(HANG(I):@SUM(LIE(J):C(I,J)*X(J))>A(I));
@FOR(LIE(J):@GIN(X(J)));
END

MODEL:
SETS:
HANG/1..3/:A;
LIE/1..5/:B,X;
XISHU(HANG,LIE):C;
ENDSETS
DATA:
A=100 200 400;
B=0.3 0 0.1 1.0 0.7;
C=1 1 0 0 0
    1 0 2 1 0
    0 2 1 2 4;
ENDDATA
MIN=@SUM(LIE(J):X(J)); !MIN=@SUM(LIE(J):b(J)*X(J));
@FOR(HANG(I):@SUM(LIE(J):C(I,J)*X(J))>A(I));
@FOR(LIE(J):@GIN(X(J)));
END

一维下料问题的一般表述

需要m种材料 \( A_1, A_2, \ldots, A_m \)，数量分别为 \( b_j \)，对一件长的原材料可得出k种不同的切割方法，\( n_{ij} \) 表示第i种方法得到 \( A_j \) 部件的数量。用 \( x_i \) 表示第i种截法的原材料数量，则该问题的模型为：

目标函数

约束条件

例5 任务分配

分配甲，乙，丙，丁，戊去完成A，B，C，D，E五项任务，每人完成一项，每项任务只能由一个人去完成，五个人分别完成各项任务所需要的时间如下表，试作出任务分配使总时间最少。表格如下：

指派问题或最优匹配问题

设有n项工作分配给n个人去做，每人做一项，由于各人的工作效率不同，因而完成同一工作所需要的时间
也就不同，设人员i完成工作j所需要的时间为c，问如何分配工作，使完成所有工作所用的总时间最少。（效率最高）？
常用解法：0-1规划

决策变量

\[ x_{ij} = \begin{cases} 0, & \text{第$i$个人不做第$j$项工作} \\ 1, & \text{第$i$个人做第$j$项工作} \end{cases} \]

目标函数

\[ \min Z = \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij} \]

约束条件

\[ \begin{cases} \sum\limits_{i=1}^{n} x_{ij} = 1, & j=1,2,\cdots,n \\[8pt] \sum\limits_{j=1}^{n} x_{ij} = 1, & i=1,2,\cdots,n \\[8pt] x_{ij} \in \{0,1\}, & i,j=1,2,\cdots,n \end{cases} \]

例6：料场选址

某公司有6个建筑工地要开工，工地位置 (xi​,yi​)（单位：km）和水泥日用量 di​（单位：t）由下表给出。公司目前有两个临时存放水泥的料场，分别位于 A(5,1) 和 B(2,7)，日存储量各20t。

1. 假设从料场到工地之间均有直线道路相连，试制定日运输计划，即从 A，B 分别向各工地送多少水泥，使总吨·千米数最小。
2. 为进一步减少吨·千米数，打算舍弃目前的两个料场，改建两个新料场，日存储量不变，问建在何处为好？

问题一部分：

决策变量

料场的位置用 \(px_{j},py_{j}\) 表示，日存储用 \(g_{j}\) 表示，从料场 j 向工地 i 日运输量为 \(c_{ij}\)

目标函数

\[ \min Z = \sum_{i=1}^{6}\sum_{j=1}^{2} c_{ij}\sqrt{(px_{j}-x_{i})^{2} + (py_{j}-y_{i})^{2}} \]

约束条件

\[ \text{s.t.}\ \begin{cases} \sum\limits_{i=1}^{6}c_{ij} \leq g_{j}, & j=1,2 \\[10pt] \sum\limits_{j=1}^{2}c_{ij} = d_{i}, & i=1,2,\cdots,6 \end{cases} \]

Model:
Sets:
    Gd/1..6/: x, y, d;
    lch/a, b/: px, py, g;
    Links(gd, lch): c;
Endsets

Data:
    X = 1.25 8.75 0.5 5.75 3 7.25;
    Y = 1.25 0.75 4.75 5 6.5 7.75;
    D = 3 5 4 7 6 11;
    Px = 5 2; py = 1 7; g = 20 20;
Enddata

Min = @sum(links(i,j): c(i,j)*@sqrt((px(j)-x(i))^2+(py(j)-y(i))^2));
@for(gd(i): @sum(lch(j): c(i,j)) = d(i));
@for(lch(j): @sum(gd(i): c(i,j)) <= g(j));
end

Model:
Sets:
    Gd/1..6/: x, y, d;
    lch/a, b/: px, py, g;
    Links(gd, lch): c;
Endsets

Data:
    X = 1.25 8.75 0.5 5.75 3 7.25;
    Y = 1.25 0.75 4.75 5 6.5 7.75;
    D = 3 5 4 7 6 11;
    Px = 5 2; py = 1 7; g = 20 20;
Enddata

Min = @sum(links(i,j): c(i,j)*@sqrt((px(j)-x(i))^2+(py(j)-y(i))^2));
@for(gd(i): @sum(lch(j): c(i,j)) = d(i));
@for(lch(j): @sum(gd(i): c(i,j)) <= g(j));
end

第二问的实质是c[i,j]和px与py都成为了变量，使得之前一问的线性规划问题变成了非线性规划问题，模型本质上是一样的，只需要在LINGO软件里面把px和py的数据删掉就可以了

Model:
Sets:
    Gd/1..6/: x, y, d;
    lch/a, b/: px, py, g;
    Links(gd, lch): c;
Endsets

Data:
    X = 1.25 8.75 0.5 5.75 3 7.25;
    Y = 1.25 0.75 4.75 5 6.5 7.75;
    D = 3 5 4 7 6 11;
    g = 20 20;
Enddata

Min = @sum(links(i,j): c(i,j)*@sqrt((px(j)-x(i))^2+(py(j)-y(i))^2));
@for(gd(i): @sum(lch(j): c(i,j)) = d(i));
@for(lch(j): @sum(gd(i): c(i,j)) <= g(j));
end

Model:
Sets:
    Gd/1..6/: x, y, d;
    lch/a, b/: px, py, g;
    Links(gd, lch): c;
Endsets

Data:
    X = 1.25 8.75 0.5 5.75 3 7.25;
    Y = 1.25 0.75 4.75 5 6.5 7.75;
    D = 3 5 4 7 6 11;
    g = 20 20;
Enddata

Min = @sum(links(i,j): c(i,j)*@sqrt((px(j)-x(i))^2+(py(j)-y(i))^2));
@for(gd(i): @sum(lch(j): c(i,j)) = d(i));
@for(lch(j): @sum(gd(i): c(i,j)) <= g(j));
end

问题是，非线性规划使用的非线性求解器实质上是只能求局部最优解的，利用的是一个近似迭代的方式，如果想要一个更好的解就需要调整参数，我也不咋会，自己试试咯……？