このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

一般的な線形計画問題

ライブ スクリプトを開く

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

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.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
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
19 rows, 19 cols, 61 nonzeros  0s
15 rows, 15 cols, 65 nonzeros  0s
15 rows, 15 cols, 65 nonzeros  0s
Presolve : Reductions: rows 15(-35); columns 15(-33); elements 65(-53)
Solving the presolved LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -8.6188168580e-01 Ph1: 10(11.7103); Du: 1(0.861882) 0s
         16    -7.0000000000e+01 Pr: 0(0) 0s
Solving the original LP from the solution after postsolve
Model   status      : Optimal
Simplex   iterations: 16
Objective value     : -7.0000000000e+01
HiGHS run time      :          0.01

Optimal solution found.

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

exitflag,fval,output.iterations
exitflag = 
1

fval = 
-70.0000

ans = 
16

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