用Octave计算线性规划问题（图解法）
广告
{{v.name}}
图解法（适用于 2 个决策变量）
当线性规划只有 2 个决策变量（\(x_1,x_2\)）时，可通过坐标系画图求解，步骤如下：
1. 确定决策变量：设待优化的变量为 \(x_1,x_2\)
2. 写出目标函数和约束条件
3. 绘制约束条件的可行域
- 将每个约束不等式视为等式，画出直线
- 根据不等式方向确定可行区域（满足所有约束的公共区域）
- 可行域是凸多边形（可能有界或无界）
4. 求最优解
- 目标函数 \(Z = c_1x_1+c_2x_2\) 可变形为 \(x_2 = -\frac{c_1}{c_2}x_1 + \frac{Z}{c_2}\)，这是一族斜率固定的平行线
- 平移该直线，与可行域有交点且使 Z 取最值的点，就是最优解
- 最优解一定出现在可行域的顶点上
例子：
\( max\ Z = 2x_1 + 3x_2 \)
\( s.t. \begin{cases} x_1 + 2x_2 \le 8 \\ 4x_1 \le 16 \\ 4x_2 \le 12 \\ x_1,x_2 \ge 0 \end{cases} \)
1. 画出约束直线，确定可行域是五边形 \(O(0,0), A(4,0), B(4,2), C(2,3), D(0,3)\)
2. 计算各顶点的 Z 值：
- \(O(0,0)\): \(Z=0\)
- \(A(4,0)\): \(Z=8\)
- \(B(4,2)\): \(Z=14\)
- \(C(2,3)\): \(Z=13\)
- \(D(0,3)\): \(Z=9\)
3. 最优解为 \(x_1=4, x_2=2\)，最优值 \(Z=14\)
代码如下：
将\(x_1 + 2x_2 \le 8\) 转化为 \(x_1 + 2x_2 - 8 = 0\)
>> ezplot(@(x1, x2) x1 + 2*x2 - 8)
>> hold on
将\(4x_1 \le 16\) 转化为 \(4x_1 - 16 = 0\)
>> ezplot(@(x1, x2) 4*x1 - 16)
>> hold on
将\(4x_2 \le 12\) 转化为 \(4x_2 - 12 = 0\)
>> ezplot(@(x1, x2) 4*x2 - 12)
>> hold on
将\(x_1,x_2 \ge 0\) 转化为 \(x_1 = 0, x_2 = 0\)
>> ezplot(@(x1, x2) x1)
>> hold on
>> ezplot(@(x1, x2) x2)
>> hold on
结果如图2-1所示。
由图可以猜测存在交点\(O(0,0)\)。要证明交点是不是(0,0)，需要求解方程组：
\( \begin{cases} x_1 = 0 \\ x_2 = 0 \end{cases} \)
代码如下：
>> pkg install optim-1.6.2-patched.tar.gz
>> pkg load optim

function F = f1(z)
    x1 = z(1);
    x2 = z(2);
    F(1) = x1;
    F(2) = x2;
endfunction

>> fsolve(@f1, [0, 0])
ans =

   0   0
由图可以猜测存在交点\(A(4,0)\)。要证明交点是不是(4,0)，需要求解方程组：
\( \begin{cases} 4x_1 - 16 = 0 \\ x_2 = 0 \end{cases} \)
代码如下：
function F = f2(z)
    x1 = z(1);
    x2 = z(2);
    F(1) = 4*x1 - 16;
    F(2) = x2;
endfunction

>> fsolve(@f2, [4, 0])
ans =

   4   0
由图可以猜测存在交点\(B(4,2)\)。要证明交点是不是(4,2)，需要求解方程组：
\( \begin{cases} 4x_1 - 16 = 0 \\ x_1 + 2x_2 - 8 = 0 \end{cases} \)
代码如下：
function F = f3(z)
    x1 = z(1);
    x2 = z(2);
    F(1) = 4*x1 - 16;
    F(2) = x1 + 2*x2 - 8;
endfunction

>> fsolve(@f3, [4, 2])
ans =

   4   2
由图可以猜测存在交点\(C(2,3)\)。要证明交点是不是(2,3)，需要求解方程组：
\( \begin{cases} 4x_2 - 12 = 0 \\ x_1 + 2x_2 - 8 = 0 \end{cases} \)
代码如下：
function F = f4(z)
    x1 = z(1);
    x2 = z(2);
    F(1) = 4*x2 - 12;
    F(2) = x1 + 2*x2 - 8;
endfunction

>> fsolve(@f4, [2, 3])
ans =

   2   3
由图可以猜测存在交点\(D(0,3)\)。要证明交点是不是(0,3)，需要求解方程组：
\( \begin{cases} 4x_2 - 12 = 0 \\ x_1 = 0 \end{cases} \)
代码如下：
function F = f5(z)
    x1 = z(1);
    x2 = z(2);
    F(1) = 4*x2 - 12;
    F(2) = x1;
endfunction

>> fsolve(@f5, [0, 3])
ans =

   0   3
计算各顶点的 Z 值，代码如下：
>> z=@(x1, x2) 2 * x1 + 3 * x2
z =

@(x1, x2) 2 * x1 + 3 * x2
>> z(0, 0)
ans = 0
>> z(4, 0)
ans = 8
>> z(4, 2)
ans = 14
>> z(2, 3)
ans = 13
>> z(0, 3)
ans = 9
最优值为14
友链