用Octave计算参数线性规划问题（目标函数参数规划）
广告
{{v.name}}
目标函数参数规划示例
以最大化问题为例，目标函数为 \(Z(\lambda) = (c_1^0+\lambda c_1^1)x_1 + \dots + (c_n^0+\lambda c_n^1)x_n\)，约束为 \(Ax = b, x\ge0\)。
求解步骤
1. 初始求解：令 \(\lambda=0\)，用单纯形法求解 \(\max Z(0) = c^0x\)，得到最优基 \(B\)，基变量 \(x_B = B^{-1}b\)，检验数 \(\sigma_j^0 = c_B^0 B^{-1}a_j - c_j^0 \le 0\)。
2. 代入参数 \(\lambda\)：
目标函数系数变为 \(c_j(\lambda) = c_j^0 + \lambda c_j^1\)，基系数 \(c_B(\lambda) = c_B^0 + \lambda c_B^1\)。
检验数变为：\( \sigma_j(\lambda) = c_B(\lambda) B^{-1}a_j - c_j(\lambda) = \sigma_j^0 + \lambda (c_B^1 B^{-1}a_j - c_j^1) = \sigma_j^0 + \lambda \Delta \sigma_j\)
3. 求参数区间：令所有 \(\sigma_j(\lambda) \le 0\)，解不等式组：
\(\sigma_j^0 + \lambda \Delta \sigma_j \le 0, \quad j=1,2,...,n\)
得到 \(\lambda\) 的区间 \([\lambda_1, \lambda_2]\)，此区间内最优基 \(B\) 不变，最优解 \(x_B = B^{-1}b\)，最优值 \(Z(\lambda) = c_B(\lambda)x_B\)。
4. 区间端点处理：当 \(\lambda = \lambda_1\) 或 \(\lambda=\lambda_2\) 时，某一非基变量的检验数 \(\sigma_k(\lambda)=0\)，最优基发生切换，需重新计算新基的单纯形表。
例子：
\( \max\ Z = 10(2+λ)x_1 + 6(3-2λ)x_2 + 4(4+3λ)x_3 \hspace{2em} (-5 \le λ \le 5) \)
\( s.t. \begin{cases} x_1 + x_2 + x_3 \le 100 \\ 10x_1 + 4x_2 + 5x_3 \le 600 \\ 2x_1 + 2x_2 + 6x_3 \le 300 \\ x_1,x_2,x_3 \ge 0 \end{cases} \)
定义约束系数矩阵 A，代码如下：
>> A = [ 1, 1, 1;
     10, 4, 5;
      2, 2, 6];
定义约束右端项 b，代码如下：
>> b = [100, 600, 300]';
定义变量下界，代码如下：
>> lb = [0, 0, 0]';
变量无上界，代码如下：
>> ub = [];
定义约束类型：3个约束都是 ≤，对应 'UUU'，代码如下：
>> ctype = "UUU";
定义变量类型：3个变量都是连续变量，对应 'CCC'，代码如下：
>> vartype = "CCC";
定义优化方向：最大化模型（-1），代码如下：
>> s = -1;
定义解算器为单纯形法（默认就是单纯形法），代码如下：
>> param.lpsolver = 1;
定义单纯形法迭代次数为最大100次，代码如下：
>> param.itlim = 100;
定义参数范围，代码如下：
>> lambda = linspace(-5,5,100);
定义结果矩阵，代码如下：
>> xmin_list = zeros(3,length(lambda));
>> fmin_list = zeros(size(lambda));
定义目标函数系数（max Z = 10(2+λ)x1 + 6(3-2λ)x2 + 4(4+3λ)x3），求解，代码如下：
>> c = [10, 6, 4]';

>> for i = 1:length(lambda)
    lam = lambda(i);
    c_param = c .* [2+lam; 3-2*lam; 4+3*lam];
    [xmin, fmin, status, extra] = ...
        glpk (c_param, A, b, lb, ub, ctype, vartype, s, param);
    xmin_list(:,i) = xmin;
    fmin_list(i) = fmin;
endfor
绘图分析最优值随λ的变化，代码如下：
>> figure; plot(lambda, fmin_list, 'LineWidth', 2); xlabel('λ'); ylabel('最优值 Z(λ)'); title('最优值随参数变化');
结果如图12-1所示。
绘图分析最优解随λ的变化，代码如下：
>> figure; plot(lambda, xmin_list(1,:), 'r-', lambda, xmin_list(2,:), 'g-', lambda, xmin_list(3,:), 'b-', 'LineWidth',2); xlabel('λ'); ylabel('最优解 x1,x2,x3'); zlabel('Z(λ)'); title('最优解随参数变化');
结果如图12-2所示。
友链