用Octave计算目标规划问题（线性目标规划）
广告
{{v.name}}
目标规划（Goal Programming, GP）是解决多目标冲突优化的核心方法，核心逻辑是为每个目标设定期望值和优先级，通过引入偏差变量将多目标转化为“最小化偏差”的单目标分层优化问题，最终得到满足决策者优先级要求的满意解（而非普通线性规划的单一最优解）。
目标规划分为线性目标规划（最常用）和非线性目标规划，以下重点讲解线性目标规划的建模思路、核心要素、求解步骤
一、 目标规划的核心要素
目标规划的建模依赖4个核心要素，这是与普通线性规划的核心区别：
1. 偏差变量（\(d_i^-, d_i^+\)）
偏差变量用于衡量实际值与期望值之间的差异，分为负偏差变量 \(d_i^-\) 和正偏差变量 \(d_i^+\)。
负偏差变量 \(d_i^-\)：表示实际值低于期望值的部分，反映了未达成目标的程度。
正偏差变量 \(d_i^+\)：表示实际值高于期望值的部分，反映了超额完成目标的程度。
互斥约束：\(d_i^- \cdot d_i^+ = 0\)（同一目标的正负偏差不能同时存在）。
2. 目标优先级（\(P_k\)）
用于区分不同目标的重要程度层级，优先级满足严格递阶关系：\(P_1 \gg P_2 \gg P_3 \gg \dots\)，即高优先级目标必须优先满足，只有当高优先级目标的偏差已最小化后，才会优化低优先级目标。
3. 重要性系数（\(w_{ki}^\pm\)）
用于衡量同一优先级下不同目标的相对重要性，重要性系数通常为非负数。
同一优先级\(P_k\)内，不同目标偏差的相对重要程度，用于量化同一层级内各偏差的权重（如同一优先级的两个目标，偏差1的权重为2，偏差2的权重为1，表示更关注偏差1的最小化）。
4. 两类约束
目标规划包含两类约束：
- 目标约束：将每个目标转化为包含偏差变量的等式约束，形式为：
\(\sum_{j=1}^n a_{ij}x_j + d_i^- - d_i^+ = g_i\)
其中\(g_i\)为目标\(i\)的期望值，\(x_j\)为决策变量，\(a_{ij}\)为目标系数；
- 系统约束：与普通线性规划一致的硬性约束（如资源限制、产能约束），是必须满足的不等式/等式约束，形式为\(\sum_{j=1}^n c_{ij}x_j \le/\ge/= b_i\)。
二、 目标规划的目标函数构建
目标规划的核心是最小化偏差变量的加权和，按优先级分层构建，高优先级偏差的权重远大于低优先级，形式为：
\(\min Z = P_1\sum(w_{1i}^-d_i^- + w_{1i}^+d_i^+) + P_2\sum(w_{2i}^-d_i^- + w_{2i}^+d_i^+) + \dots + P_m\sum(w_{mi}^-d_i^- + w_{mi}^+d_i^+)\)
偏差变量的选择原则
根据目标的优化要求，选择需要最小化的偏差：
- 目标要求不少于/不低于\(g_i\)（如利润≥100万）：需最小化负偏差\(d_i^-\)（正偏差\(d_i^+\)无要求）；
- 目标要求不超过/不高于\(g_i\)（如产量≤50件）：需最小化正偏差\(d_i^+\)（负偏差\(d_i^-\)无要求）；
- 目标要求恰好等于\(g_i\)（如成本=50万）：需同时最小化\(d_i^-\)和\(d_i^+\)（加权和）。
三、 线性目标规划的求解步骤
目标规划遵循“优先级逐级优化”原则，核心是将多优先级问题转化为一系列线性规划子问题，依次求解，前一级的最优偏差会作为新约束加入后一级的求解中。
通用求解步骤
1. 明确问题：确定决策变量\(x_j\)，梳理所有目标，指定每个目标的期望值\(g_i\)、优先级\(P_k\)、优化要求；
2. 引入偏差变量：为每个目标定义\(d_i^-\)和\(d_i^+\)，所有偏差变量非负；
3. 构建约束：对每个目标建立目标约束，列出所有系统约束；
4. 分层构建目标函数：按优先级从高到低，定义各层级需最小化的偏差加权和；
5. 逐级求解线性规划：
- 第1级：以最高优先级\(P_1\)的偏差和为目标函数，求解线性规划，得到\(P_1\)的最优偏差值\(Z_1^*\)；
- 第2级：将\(Z_1=Z_1^*\)作为硬性约束加入，以\(P_2\)的偏差和为目标函数求解，得到\(Z_2^*\)；
- 后续层级：重复上述操作，直到所有优先级求解完成；
6. 输出满意解：最后一级的决策变量解即为目标规划的满意解，同时输出各目标的实际偏差。
例子：
某工厂生产\(x_1\)、\(x_2\)两种产品，已知：
- 单位利润：\(x_1=5\)元，\(x_2=4\)元；
- 原材料约束：\(2x_1+3x_2 \le 12\)（原材料总量限制）；
- 目标1（\(P_1\)，最高优先级）：总利润不少于20元（优化要求：最小化\(d_1^-\)）；
- 目标2（\(P_2\)，次优先级）：产品\(x_1\)的产量不超过3件（优化要求：最小化\(d_2^+\)）；
- 决策变量非负：\(x_1,x_2 \ge 0\)。
步骤1：引入偏差变量，构建约束
- 目标1（利润≥20）：\(5x_1+4x_2 + d_1^- - d_1^+ = 20\)，\(d_1^-,d_1^+ \ge 0\)（最小化\(d_1^-\)）；
- 目标2（\(x_1≤3\)）：\(x_1 + d_2^- - d_2^+ = 3\)，\(d_2^-,d_2^+ \ge 0\)（最小化\(d_2^+\)）；
- 系统约束：\(2x_1+3x_2 \le 12\)；
- 非负约束：\(x_1,x_2,d_1^-,d_1^+,d_2^-,d_2^+ \ge 0\)。
步骤2：分层构建目标函数
- \(P_1\)：\(\min Z_1 = d_1^-\)；
- \(P_2\)：\(\min Z_2 = d_2^+\)，约束新增：\(d_1^- = Z_1^*\)（\(Z_1^*\)为\(P_1\)的最优解）。
步骤3：逐级求解
第1级：优化\(P_1\)，\(\min Z_1 = d_1^-\)
约束：\(5x_1+4x_2 +d_1^--d_1^+=20\)、\(x_1+d_2^--d_2^+=3\)、\(2x_1+3x_2 \le12\)、所有变量≥0；
求解得：\(Z_1^*=0\)（利润恰好达标/超标），此时可行解如\(x_1=3, x_2=2\)（利润\(5×3+4×2=23≥20\)）。
第2级：优化\(P_2\)，\(\min Z_2 = d_2^+\)
约束：在第1级基础上，新增\(d_1^-=0\)，其余约束不变；
求解得：\(Z_2^*=0\)，最终满意解为\(x_1=3, x_2=2\)，各偏差：\(d_1^-=0, d_1^+=3, d_2^-=0, d_2^+=0\)。
结果分析
- 高优先级目标1完全满足（利润未不足），次优先级目标2完全满足（\(x_1\)未超标）；
- 实际利润23元，超过目标值3元（\(d_1^+=3\)），属于可接受的偏差。
第1级优化：P1，min Z1 = d1- （变量索引3：d1-），代码如下：
>> f1 = [0, 0, 0, 0, 0, 0];
>> f1(3) = 1; % 目标函数仅最小化d1-
定义基础约束（目标约束+系统约束）：Ax ≤ b，代码如下：
>> A_base = [
5, 4, 1, -1, 0, 0;
-5, -4, -1, 1, 0, 0;
1, 0, 0, 0, 1, -1;
-1, 0, 0, 0, -1, 1;
2, 3, 0, 0, 0, 0;
];
定义基础约束右端项 b，代码如下：
>> b_base = [20; -20; 3; -3; 12];
定义变量下界，代码如下：
>> lb = [0, 0, 0, 0, 0, 0]';
变量无上界，代码如下：
>> ub = [];
定义约束类型：5个约束都是 ≤，对应 'UUUUU'，代码如下：
>> ctype = "UUUUU";
定义变量类型：6个变量都是整数变量，对应 'IIIIII'，代码如下：
>> vartype = "IIIIII";
定义优化方向：最小化模型（1），代码如下：
>> s = 1;
定义解算器为单纯形法（默认就是单纯形法），代码如下：
>> param.lpsolver = 1;
定义单纯形法迭代次数为最大100次，代码如下：
>> param.itlim = 100;
求解，代码如下：
>> [x1, fval1, status1, extra] = ...
glpk (f1, A_base, b_base, lb, ub, ctype, vartype, s, param)
x1 =
3
1
1
0
0
0
fval1 = 0
status1 = 0
extra =
scalar structure containing the fields:
time = 0
status = 5
第2级优化：P2，min Z2 = d2+ （变量索引6：d2+），新增约束d1- = fval1，代码如下：
>> f2 = [0, 0, 0, 0, 0, 0];
>> f2(6) = 1; % 目标函数仅最小化d2+
新增约束：d1- = fval1 → d1- ≤ fval1 且 d1- >= fval1，代码如下：
>> A_new = [0,0,1,0,0,0; 0,0,-1,0,0,0];
定义新增约束右端项 b，代码如下：
>> b_new = [fval1; -fval1];
合并基础约束和新增约束，代码如下：
>> A = [A_base; A_new];
>> b = [b_base; b_new];
定义约束类型：7个约束都是 ≤，对应 'UUUUUUU'，代码如下：
>> ctype = "UUUUUUU";
求解，代码如下：
>> [x2, fval2, status2, extra] = ...
glpk (f2, A, b, lb, ub, ctype, vartype, s, param)
x2 =
3
2
0
3
0
0
fval2 = 0
status2 = 0
extra =
scalar structure containing the fields:
time = 0
status = 5
