Main Content

一般的な線形計画問題

ライブ スクリプトを開く

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

minxfTxsuchthat{A⋅x≤b,Aeq⋅x=beq,x≥0.

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.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
37 rows, 37 cols, 93 nonzeros
20 rows, 20 cols, 61 nonzeros
15 rows, 15 cols, 59 nonzeros
12 rows, 12 cols, 58 nonzeros
12 rows, 12 cols, 58 nonzeros
Presolve : Reductions: rows 12(-38); columns 12(-36); elements 58(-60)
Solving the presolved LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -8.6188182138e-01 Ph1: 9(12.9103); Du: 1(0.861882) 0s
         14    -7.0000000000e+01 Pr: 0(0) 0s
Solving the original LP from the solution after postsolve
Model   status      : Optimal
Simplex   iterations: 14
Objective value     : -7.0000000000e+01
HiGHS run time      :          0.00

Optimal solution found.

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

exitflag,fval,output.iterations
exitflag = 1

fval = -70.0000

ans = 14

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