用Octave计算参数线性规划问题（右端项参数规划）
广告
{{v.name}}
右端项参数规划示例
约束右端项为 \(b(λ) = b^0 + λ b^1\)，目标函数 \(Z = cx\)，约束 \(Ax = b(λ), x\ge0\)。
求解步骤
1. 初始求解：令 \(\lambda=0\)，得到最优基 \(B\)，基解 \(x_B^0 = B^{-1}b^0 \ge 0\)，检验数 \(\sigma_j = c_B B^{-1}a_j - c_j \le 0\)。
2. 代入参数 \(\lambda\)：
基解变为：\(x_B(\lambda) = B^{-1}b(\lambda) = B^{-1}b^0 + \lambda B^{-1}b^1 = x_B^0 + \lambda \Delta b_B\)
3. 求参数区间：令所有基解非负 \(x_B(\lambda) \ge 0\)，解不等式组：
\(x_{Bi}^0 + \lambda \Delta b_{Bi} \ge 0, \quad i=1,2,...,m\)
得到 \(\lambda\) 的区间 \([\lambda_3, \lambda_4]\)，此区间内最优基不变，检验数不变，最优值 \(Z(\lambda) = c_B x_B(\lambda)\)。
4. 区间端点处理：当 \(\lambda\) 超出区间时，某一基变量 \(x_{Br}(\lambda)=0\)，基变量出基，需用对偶单纯形法求新的最优基。
例子：
\( \max\ Z = 10x_1 + 6x_2 + 4x_3 \)
\( s.t. \begin{cases} x_1 + x_2 + x_3 \le 100(2+λ) \\ 10x_1 + 4x_2 + 5x_3 \le 600(3-2λ) \\ 2x_1 + 2x_2 + 6x_3 \le 300(4+3λ) \\ x_1,x_2,x_3 \ge 0 \\ -5 \le λ \le 5 \end{cases} \)
定义目标函数系数（max Z = 10x1 + 6x2 + 4x3），代码如下：
>> c = [10, 6, 4]';
定义约束系数矩阵 A，代码如下：
>> A = [ 1, 1, 1;
     10, 4, 5;
      2, 2, 6];
定义变量下界，代码如下：
>> 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));
定义约束右端项 b，求解，代码如下：
>> b = [100, 600, 300]';

>> for i = 1:length(lambda)
    lam = lambda(i);
    b_param = b .* [2+lam; 3-2*lam; 4+3*lam];
    [xmin, fmin, status, extra] = ...
        glpk (c, A, b_param, 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('最优值随参数变化');
结果如图13-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('最优解随参数变化');
结果如图13-2所示。
友链