25.1 線形プログラミング
Octaveは関数を使って線形計画問題を解くことができますglpk 。つまり、Octaveは
min C'*x
線形制約 A*x = b（x ≥ 0）に従う。
このglpk関数は、この問題のバリエーションもサポートします。
: glpk [xopt, fmin, errnum, extra] = (c, A, b, lb, ub, ctype, vartype, sense, param)
GNU GLPKライブラリを使用して線形計画問題を解きます。
3 つの引数が与えられた場合、glpk次の標準 LP を解きます。
min C'*x
対象となる
A*x = b x >= 0
しかし、次のような問題も解決できるかもしれない。
[ min | max ] C'*x
対象となる
A*x [ "=" | "<=" | ">=" ] b x >= LB x <= UB
入力引数:
ｃ
目的関数の係数を含む列配列。
A
制約係数を含む行列。
b
制約マトリックス内の各制約の右側の値を含む列配列。
lb
各変数の下限を含む配列。lb が指定されていない場合、 変数のデフォルトの下限は 0 になります。
ub
各変数の上限を含む配列。ub が指定されていない場合、 デフォルトの上限は無限大であると見なされます。
ctype
制約マトリックス内の各制約の意味を含む文字の配列。配列の各要素は、次のいずれかの値になります。
"F"
自由（無制限）制約（制約は無視されます）。
"U"
上限 ( A(i,:)*x <= b(i)) を持つ不等式制約。
"S"
等式制約（A(i,:)*x = b(i)）。
"L"
A(i,:)*x >= b(i)下限値 ( ) を持つ不等式。
"D"
上限と下限 ( A(i,:)*x >= -b(i))および( A(i,:)*x <= b(i)) の両方を持つ不等式制約。
vartype
変数の型を含む列配列。
"C"
連続変数。
"I"
整数変数。
sense
senseが 1 の場合、問題は最小化です。senseが -1 の場合、問題は最大化です。デフォルト値は 1 です 。
param
ソルバーの動作を定義するために使用される次のパラメータを含む構造体。構造体内の欠落している要素はデフォルト値を取得するため、デフォルトから変更する要素のみを設定する必要があります。
整数パラメータ:
msglev (default: 1)
ソルバールーチンによって出力されるメッセージのレベル:
0 ( GLP_MSG_OFF)
出力なし。
1 （GLP_MSG_ERR）
エラーと警告メッセージのみ。
2 （GLP_MSG_ON）
通常出力。
3 （GLP_MSG_ALL）
完全な出力（情報メッセージを含む）。
scale (default: 16)
スケーリング オプション。値はビット単位の OR 演算子で組み合わせることができ、次のようになります。
1 （GLP_SF_GM）
幾何平均スケーリング。
16 （GLP_SF_EQ）
平衡スケーリング。
32 （GLP_SF_2N）
スケール係数を 2 の累乗に丸めます。
64 （GLP_SF_SKIP）
問題が適切にスケールされている場合はスキップします。
あるいは、128 ( ) の値GLP_SF_AUTOを指定することもできます。その場合、ルーチンはスケーリング オプションを自動的に選択します。
dual (default: 1)
シンプレックス法オプション:
1 （GLP_PRIMAL）
2 相プライマリシンプレックスを使用します。
2 （GLP_DUALP）
2 相デュアル シンプレックスを使用し、失敗した場合はプライマル シンプレックスに切り替えます。
3 （GLP_DUAL）
2相デュアルシンプレックスを使用します。
price (default: 34)
価格オプション（プライマルシンプレックスとデュアルシンプレックスの両方）：
17 （GLP_PT_STD）
教科書の価格設定。
34 （GLP_PT_PSE）
最も急なエッジ価格設定。
itlim (default: intmax)
単体反復の制限。単体反復が 1 回実行されるたびに 1 ずつ減少し、値が 0 に達するとソルバーに検索を停止するように指示します。
outfrq (default: 200)
出力頻度（反復単位）。このパラメータは、ソルバーがソリューションに関する情報を標準出力に送信する頻度を指定します。
branch (default: 4)
分岐手法オプション (MIP のみ):
1 （GLP_BR_FFV）
最初の小数変数。
2 （GLP_BR_LFV）
最後の小数変数。
3 （GLP_BR_MFV）
最も小数的な変数。
4 （GLP_BR_DTH）
Driebeck と Tomlin によるヒューリスティック。
5 （GLP_BR_PCH）
ハイブリッド疑似コストヒューリスティック。
btrack (default: 4)
バックトラッキング手法オプション (MIP のみ):
1 （GLP_BT_DFS）
深さ優先探索。
2 （GLP_BT_BFS）
幅優先探索。
3 （GLP_BT_BLB）
最高の地元密着型。
4 （GLP_BT_BPH）
最良の投影ヒューリスティック。
presol (default: 1)
このフラグが設定されている場合、シンプレックス ソルバーは組み込みの LP プリゾルバーを使用します。設定されていない場合、LP プリゾルバーは使用されません。
lpsolver (default: 1)
使用するソルバーを選択します。問題が MIP 問題の場合、このフラグは無視されます。
1
修正された単体法。
2
内点法。
rtest (default: 34)
比率テスト手法:
17 （GLP_RT_STD）
標準（「教科書」）。
34 （GLP_RT_HAR）
ハリスの2パス比率テスト。
tmlim (default: intmax)
検索時間の制限（ミリ秒単位）。
outdly (default: 0)
出力遅延（秒単位）。このパラメータは、ソルバーがソリューションに関する情報を標準出力に送信するまでの遅延時間を指定します。
save (default: 0)
このパラメータがゼロ以外の場合、問題のコピーをCPLEX LP形式でファイルに保存します。「outpb.lp」現時点では出力ファイルの名前を変更する方法はありません。
実パラメータ:
tolbnd (default: 1e-7)
現在の基本ソリューションが基本的に実行可能かどうかを確認するために使用される相対許容値。このパラメータの目的を詳細に理解していない限り、このパラメータを変更することはお勧めしません。
toldj (default: 1e-7)
現在の基本ソリューションが二重実行可能かどうかを確認するために使用される絶対許容値。このパラメータの目的を詳細に理解していない限り、このパラメータを変更することはお勧めしません。
tolpiv (default: 1e-10)
シンプレックス テーブルの適切な主要要素を選択するために使用される相対許容値。このパラメータの目的を詳細に理解していない限り、このパラメータを変更することはお勧めしません。
objll (default: -DBL_MAX)
目的関数の下限。目的関数がこの制限に達して減少し続ける場合、ソルバーは検索を停止します。このパラメータは、デュアル シンプレックス法でのみ使用されます。
objul (default: +DBL_MAX)
目的関数の上限。目的関数がこの制限に達し、増加し続ける場合、ソルバーは検索を停止します。このパラメータは、デュアル シンプレックスでのみ使用されます。
tolint (default: 1e-5)
現在の基本ソリューションが整数実行可能かどうかを確認するために使用される相対許容値。このパラメータの目的を詳細に理解していない限り、このパラメータを変更することはお勧めしません。
tolobj (default: 1e-7)
目的関数の値が既知の最良の整数実行可能解よりも優れていないかどうかを確認するために使用される相対許容値。このパラメータの目的を詳細に理解していない限り、このパラメータを変更することはお勧めしません。
出力値:
xopt
オプティマイザー（最適時の決定変数の値）。
フォプト
目的関数の最適値。
エラー番号
エラーコード。
0
エラーはありません。
1 （GLP_EBADB）
無効な基準です。
2 （GLP_ESING）
特異行列。
3 （GLP_ECOND）
条件の悪いマトリックス。
4 （GLP_EBOUND）
境界が無効です。
5 （GLP_EFAIL）
ソルバーが失敗しました。
6 （GLP_EOBJLL）
目的関数の下限に達しました。
7 （GLP_EOBJUL）
目的関数の上限に達しました。
8 （GLP_EITLIM）
反復回数の制限に達しました。
9 （GLP_ETMLIM）
制限時間が切れました。
10 （GLP_ENOPFS）
根本的な実行可能な解決策はありません。
11 （GLP_ENODFS）
二重に実行可能な解決策はありません。
12 （GLP_EROOT）
ルート LP 最適値が提供されていません。
13 （GLP_ESTOP）
アプリケーションによって検索が終了しました。
14 （GLP_EMIPGAP）
相対的な MIP ギャップ許容値に達しました。
15 （GLP_ENOFEAS）
第一/第二の実行可能な解決策はありません。
16 （GLP_ENOCVG）
収束なし。
17 （GLP_EINSTAB）
数値の不安定性。
18 （GLP_EDATA）
無効なデータです。
19 （GLP_ERANGE）
結果が範囲外です。
余分な
次のフィールドを含むデータ構造:
lambda
二重変数。
redcosts
コスト削減。
time
LP/MIP 問題を解決するために使用された時間 (秒単位)。
status
最適化のステータス。
1 （GLP_UNDEF）
ソリューションのステータスは未定義です。
2 （GLP_FEAS）
解決策は実行可能です。
3 （GLP_INFEAS）
解決策は実行不可能です。
4 （GLP_NOFEAS）
問題には実行可能な解決策がありません。
5 （GLP_OPT）
解決策は最適です。
6 （GLP_UNBND）
この問題には無制限の解決策はありません。
例：
c = [10, 6, 4]';
A = [ 1, 1, 1;
10, 4, 5;
2, 2, 6];
b = [100, 600, 300]';
lb = [0, 0, 0]';
ub = [];
ctype = "UUU";
vartype = "CCC";
s = -1;
param.msglev = 1;
param.itlim = 100;
[xmin, fmin, status, extra] = ...
glpk (c, A, b, lb, ub, ctype, vartype, s, param);