一般的な線形計画問題

この例では、次のような典型的な線形計画問題を解きます。

$\min_{x} f^{T} x s u c h t h a t {\begin{array}{cccccccccccccccccccc} A \cdot x \leq b, \\ A e q \cdot x = b e q, \\ x \geq 0 . \end{array}$

sc50b.mat ファイルを読み込みます。このファイルはこの例を実行する際に使用でき、行列およびベクトル A、Aeq、b、beq、f、ならびに下限 lb が含まれます。

load sc50b

この問題には 48 の変数、30 の不等式、20 の等式があります。

disp(size(A))

    30    48

disp(size(Aeq))

    20    48

dual-simplex アルゴリズムと反復表示を使用するようにオプションを設定します。

options = optimoptions(@linprog,Algorithm="dual-simplex",Display="iter");

この問題に上限はないため、ub を [] に設定します。

ub = [];

linprog を呼び出して問題を解きます。

[x,fval,exitflag,output] = ...
    linprog(f,A,b,Aeq,beq,lb,ub,options);

Running HiGHS 1.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
LP   has 50 rows; 48 cols; 118 nonzeros
Coefficient ranges:
  Matrix [3e-01, 3e+00]
  Cost   [1e+00, 1e+00]
  Bound  [0e+00, 0e+00]
  RHS    [3e+02, 3e+02]
Presolving model
37 rows, 37 cols, 93 nonzeros  0s
21 rows, 21 cols, 63 nonzeros  0s
16 rows, 16 cols, 58 nonzeros  0s
Dependent equations search running on 2 equations with time limit of 1000.00s
Dependent equations search removed 0 rows and 0 nonzeros in 0.00s (limit = 1000.00s)
14 rows, 14 cols, 63 nonzeros  0s
Presolve : Reductions: rows 14(-36); columns 14(-34); elements 63(-55)
Solving the presolved LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -8.6188182450e-01 Ph1: 10(13.6343); Du: 1(0.861882) 0s
         17    -7.0000000000e+01 Pr: 0(0) 0s
Solving the original LP from the solution after postsolve
Model status        : Optimal
Simplex   iterations: 17
Objective value     : -7.0000000000e+01
P-D objective error :  0.0000000000e+00
HiGHS run time      :          0.00

Optimal solution found.

問題を解くために linprog によって使用される終了フラグ、解での目的関数値、および反復の回数を検証します。

exitflag,fval,output.iterations

exitflag = 
1

fval = 
-70.0000

ans = 
17

反復表示で目的関数値および反復の回数を確認することもできます。