はじめに

「線形計画法は、最適化問題を解決するためのツールです。1947 年、George Dantzig は線形計画問題の効果的な解決法、シンプレックス・アルゴリズムを開発しました。シンプレックス・アルゴリズムが開発されてからというもの、銀行業、教育、林業、石油産業、運送業など多種多様な産業で、最適化問題の解決に線形計画法が使われています。フォーチュン 500 社の調査では、回答者の 85% が線形計画法を使用したことがあると答えています。」

Wayne L. Winston 著「Operations Research: Applications and Algorithms, 4th Edition」(Thomson 出版、2004 年) からの引用です。リンクについては「参考文献」を参照してください。

線形計画問題の解決には多くのツールを使用できます。専有ツールは有名ですが、オープン・ソース・コミュニティーのメンバーにはまだ、無料の GLPK ツールは知れ渡っていません。

GLPK の機能とその使用方法を紹介するこの 3 回シリーズではまず、この記事でGLPK を概説し、GLPK で GNU MathProg 言語を適用する例を説明します。

オペレーションズ・リサーチ理論を始めたばかりで、線形問題のモデル化と解決方法を学びたいという方には、この記事が適切なガイドになります。

上に戻る

GNU Linear Programming Kit

GLPK (GNU Linear Programming Kit) は、線形問題を解決するための有名なオペレーションズ・リサーチ・アルゴリズムを使用するルーチンを集めたライブラリーです。これらのルーチンはシンプレックス・アルゴリズム、分岐限定法アルゴリズム、主双対内点法アルゴリズムやその他多くのアルゴリズムを実装します。詳細については、GLPK ダウンロードに付属している GLPK マニュアルを参照してください。(GLPK をダウンロードするには、「参考文献」セクションに GLPK ページ gnu.org へのリンクが記載されています。)

GLPK はプログラムではありません。これは実行することは不可能で、 main() 関数もありません。その代わり、クライアントが GLPK API を使用して問題データをアルゴリズム・ルーチンに送り、結果を受け取ります。GLPK には、この API とインターフェースを取るデフォルトのクライアント、glpsol プログラムがあります。通常、glpsol のようなプログラムはクライアントと言うよりソルバーと呼ばれるので、これ以降はこの用語を使用します。

上に戻る

GNU MathProg モデル化言語

GNU MathProg モデル化言語は、線形問題を分かりやすく簡単に宣言します。通常、問題宣言は以下のものから構成されます。

• 問題決定変数
• 目的 (ターゲット) 関数。目的は名詞で、形容詞ではないことに注意してください。この名前は、オペレーションズ・リサーチ理論での標準です。
• 問題制約
• 問題パラメーター (データ)

それでは、単純な 2 つの変数による例、Giapetto's Woodcarving, Inc. を用いて説明していきましょう。

上に戻る

Operations Research によると、問題は以下のとおりです。

Giapetto's Woodcarving Inc. では 2 種類の木製玩具、兵隊と列車を製造しています。兵隊の販売価格は 27 ドルで、そのうち原材料費は 10 ドルです。1 個の兵隊を製造するごとに、Giapetto 社の人件費と諸経費が 14 ドル加算されます。一方、列車の販売価格は 21 ドルで、そのうち原材料費は 9 ドルです。各列車の製造には、Giapetto 社の人件費と諸経費が 14 ドルかかります。木製の兵隊と列車を製造するには 2 種類の技能作業、木工と仕上げが必要です。兵隊 1 個につき、2 時間の仕上げ作業と、1 時間の木工作業を要します。一方、列車の場合は、1 時間の仕上げ作業と 1 時間の木工作業です。毎週 Giapetto 社では必要なすべての原材料を仕入れますが、仕上げ作業には 100 時間、木工作業には 80 時間の枠しかありません。列車の需要は限りありませんが、兵隊の販売数は毎週多くても 40 個です。Giapetto 社では毎週の利益 (収益マイナス経費) を最大限にしようとしています。

この問題についての重要な情報と前提を要約すると、次のようになります。

1. 兵隊と列車の 2 種類の木製玩具がある。
2. 兵隊の販売価格は 27 ドルで原材料費は 10 ドル、製造には 14 ドルの人件費と諸経費がかかる。
3. 列車の販売価格は 21 ドルで原材料費は 9 ドル、製造には 10 ドルの人件費と諸経費がかかる。
4. 兵隊には仕上げ作業に 2 時間、木工作業に 1 時間が必要となる。
5. 列車には仕上げ作業に 1 時間、木工作業に 1 時間が必要となる。
6. 毎週使えるのは、仕上げ作業に最大 100 時間、木工作業に最大 80 時間である。
7. 毎週、列車には無制限の需要があり、兵隊の場合は最大でも売り上げが 40 個である。

最終目標は、週次利益を最大限にする兵隊の数と列車の数を見つけることです。

上に戻る

モデル化

線形問題をモデル化するには、最初に決定変数を確立します。決定変数は、シンプレックス・アルゴリズムが反復するごとに変化し、目的関数、すなわち最適解の値を決定するからです。Giapetto 社の工場では目的関数は利益で、これは週ごとの兵隊と列車の生産個数の関数です。したがって、この問題における 2 つの決定変数は以下のようになります。

• x1 : 週ごとの兵隊の生産個数
• x2 : 週ごとの列車の生産個数

決定変数がわかると、この問題の目的関数は単純に x1 と x2 の関数として、各玩具の売上金マイナス経費となります。

利益は x1 と x2 によって線形に代わるという点に注目してください。これが、線形問題です。

一見すると、単純に x1 と x2 を増やせば利益を最大限にできるように思えます。ものごとがそれほど単純にうまくいくとしたら、列車と兵隊の製造を開始してカリブに移住できます! 運悪く、ここには選択可能な決定変数を限定する制約があります (そうでなかったら、おそらく誤ったモデルになるでしょう)。

この問題に設定されている前提を思い出してください。最初の 3 つの前提で決定変数と目的関数が決定されました。4 番目と 6 番目の前提では、兵隊を完成させるには、木工作業と仕上げ作業の時間が必要であるとなっています。ここでの制限は、Giapetto 社での木工作業と仕上げ作業の時間は無限ではないということです。これが、すなわち制約です。それは、これを分析して明確にしましょう。

兵隊 1 個には 2 時間の仕上げ作業が必要で、Giapetto 社には毎週最大 100 時間という仕上げ作業の時間枠があります。そのため、毎週 50 個以上の兵隊は生産できません。同様に、木工作業時間の制約があるため、毎週 80 個を超える兵隊を生産することは不可能です。ここで注意しなければならないのは、最初の制約のほうが 2 つ目の制約より厳しいという点です。最初の制約は事実上、2 つ目の制約のサブセットであるため、2 つ目の制約は冗長です。

前のパラグラフで最適化問題のモデル化方法を説明しましたが、そこでは必要なすべての変数を考慮していなかったため分析は不完全です。Giapetto の問題に対する完璧な解ではありません。それでは、この問題はどのように対処すればいいのでしょうか。

まずは、制限要因を分析して制約を見つけるところから開始します。そもそも、仕上げ作業の時間を制約しているものとは何でしょうか。兵隊と列車にはどちらも仕上げ作業の時間が必要であるため、この両方を考慮しなければなりません。例えば、10 個の兵隊と 20 個の列車を作るとします。これに必要な仕上げ作業の時間は、10×2 時間 (兵隊の場合) と 20×1 時間 (列車の場合) をあわせた合計 40 時間となります。決定変数に関する一般制約は、以下のようになります。

この不等式を満たす (x1,x2 ) の組み合わせは多数あるため、Giapetto 社の工場の場合の最適な組み合わせを決定することにはなりません。

仕上げ作業時間の制約は用意できたので、今度は木工作業時間の制約を同じようにして見つけます。

これで、この問題に残された制約はあと 1 つとなりました。兵隊の毎週の需要です。問題の説明によると、毎週生産される兵隊は最大で 40 個です。

列車の需要は無制限であるため、これに対する制約は作成できません。完成したモデルは、以下の式で構成されます。

最後の制約を注意して見てください。この制約は、決定変数が常に正数になることを確実にしています。問題はこれを明示的に述べていませんが、それでも重要 (かつ明らか) なことです。

これで、線形最適化問題を解決するのが得意な GLPK によってモデルを解決できます。

上に戻る

ちょっとした理論

問題の解空間を見てみましょう。決定変数が 2 つあるため、この解空間は二次元となっています。

第 1 象限 (ここではすべての値が正の数) の外部にある (x1,x2 ) の解はすでに省いています。それでもまだ、この解空間は無限であることに注意してください。(これでよければ、とっくにカリブに移住しています!)

制約が追加されているので、この無限の解空間に境界ができています。上記の不等式 (6) によって、さらに興味深い結果になります。

解空間には、仕上げ作業時間の制約を満たす、すべての可能な (x1,x2 ) の解が第 1 象限に含まれています。

不等式 (7) を追加すると、結果セットが絞り込まれます。

解空間が狭まったことに注意してください。つまり、(x1,x2 ) の解が少なくなったということです。不等式 (8) を追加すると、結果はさらに絞り込まれます。

解空間がさらに狭まりました。すべての制約を満たす解空間は、実行可能領域と呼ばれます。図 4 は、Giapetto 社の工場での実行可能領域を示しています。この領域に収まっているすべての (x1,x2 ) の組み合わせが、この問題に対する潜在的な解です。

ここで疑問となるのは、どれが Giapetto 社の利益を最大限にするか、です。

上に戻る

GLPK を使用してモデルを解決する

GLPK はこの問題を解決するための優れたツールです。Giapetto 社の問題を数学的に定式化するには、GNU MathProg 言語を使用します。宣言しなければならない重要な項目は、以下のとおりです。

• 決定変数
• 目的関数
• 制約
• 問題データ・セット

以下のコードで、Giapetto 社の問題を MathProg で解決する方法を示します。このコードの行番号は、コード自体に含まれるものではなく、コードを参照する目的で追加されています。

                
 1  #
 2  # Giapetto's problem
 3  #
 4  # This finds the optimal solution for maximizing Giapetto's profit
 5  #
 6
 7  /* Decision variables */
 8  var x1 >=0;  /* soldier */
 9  var x2 >=0;  /* train */
10
11  /* Objective function */
12  maximize z: 3*x1 + 2*x2;
13
14  /* Constraints */
15  s.t. Finishing : 2*x1 + x2 <= 100;
16  s.t. Carpentry : x1 + x2 <= 80;
17  s.t. Demand    : x1 <= 40;
18
19  end;
 

行 1 から行 5 はコメントです。行の先頭にある # は、その行の終わりまでがコメントであることを示します。行 7 に示すように、C スタイルのコメントも使用可能で、このようなコメントは宣言の途中でも機能します。

MathProg の最初のステップは、決定変数を宣言することです。行 8 と行 9 は、それぞれ x1 と x2 を宣言しています。決定変数の宣言は、キーワード var から始まります。符号の制約 (不等式 (9) を参照) を単純化するため、MathProg では行 8 と行 9 に示すように、決定変数の宣言内で a >= 0 を使用できます。GNU MathProg 内のすべてのセンテンスは、セミコロン (;) で終わらなければなりません。x1 は兵隊の数を表し、x2 は列車の数を表すことを思い出してください。これらの変数は soldiers と trains と呼ぶこともできますが、そのような呼び方では読者の数学者を混乱させることになります。

行 12 は、ターゲット (目的) 関数を宣言しています。線形問題は、最大化あるいは最小化できます。Giapetto 社の数学的モデルは最大化問題であるため、当然キーワードは minimize ではなく maximize となることを覚えていてください。目的関数は z という名前で、これは 3x1 + 2x2 と等価です。以下の点に注意してください。

• コロン (:) は目的関数の名前とその定義を区分します。
• アスタリスク (*) は乗算を示し、同様にプラス (+)、マイナス (-)、スラッシュ (/) はそれぞれ加算、減算、除算を示します。

行 15、行 16、行 17 は制約を定義します。制約を宣言する行を s.t. で開始する必要はありませんが、これによってコードが読みやすくなります。

Giapetto 社の 3 つの制約には、Finishing、Carpentry、および Demand というラベルが付いています。それぞれが数学的モデルでの場合と同じように宣言されています。<= と >= の記号は、不等式です。各宣言の終わりには、セミコロン (;) を忘れないでください。

行 19 に示すように、すべての GNU MathProg ファイルは end; で終わらなければなりません。

これで、glpsol がこのファイルを入力として使用できるわけですが、ちょっと待ってください。問題のデータ・セクションはどこにあるのでしょう。この問題はあまりにも単純なため、データ・セクションは、宣言内の決定変数の係数として目的関数と制約宣言に直接組み込まれています。例えば、目的関数では係数 3 と 1 が問題のデータ・セットの一部となっています。データ・セットを使ってこの問題を作成し直せば、データ・セットがどのように機能するかが明らかになりますが、ここではとりあえず省略します。

MathProg 入力ファイルには .mod 拡張子を使い、解は拡張子 .sol のファイルに転送することをお勧めします。ただし、これは必須ではないので、任意のファイル名と拡張子を使用しても構いません。この例での Giapetto 社の MathProg ファイルは giapetto.mod で、出力ファイルは giapetto.sol です。それでは、お好みのコンソールで以下の glpsol を実行してください。

glpsol -m giapetto.mod -o giapetto.sol

このコマンド行では、2 つの glpsol オプションを使用しています。

• -m オプションでは、入力を GNU MathProg に書き込むことを指定しています。
• -o オプションでは、出力を giapetto.sol に送ることを指定しています。

解レポートは giapetto.sol に出力されますが、GLPK の所要時間と使用メモリーに関する一部の情報はシステムの標準出力に表示されます。

                
ceron@curly ~ $ glpsol -m giapetto.mod -o giapetto.sol
Reading model section from giapetto.real.mod...
19 lines were read
Generating z...
Generating Finishing...
Generating Carpentry...
Generating Demand...
Model has been successfully generated
lpx_simplex: original LP has 4 rows, 2 columns, 7 non-zeros
lpx_simplex: presolved LP has 2 rows, 2 columns, 4 non-zeros
lpx_adv_basis: size of triangular part = 2
*     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
*     2:   objval =   1.400000000e+02   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1M (151326 bytes)
lpx_print_sol: writing LP problem solution to `giapetto.sol'...

上記のレポートは、glpsol がモデルを読み取り、GLPK API 関数を呼び出して目的関数を生成した後、別の API 関数を呼び出して制約を生成したことを示しています。モデルが生成されると、glpsol は、問題がどのように GLPK で内部処理されたかを簡単に説明します。最後に、解、そしてGLPK がその解を導くために使用したリソースに関する情報が表示され、解が最適解であると示されます。

見事なレポートですが、決定変数の実際の最適値はこのレポートではなく、giapetto.sol ファイルにあります。

                
Problem:    giapetto
Rows:       4
Columns:    2
Non-zeros:  7
Status:     OPTIMAL
Objective:  z = 180 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B            180
     2 Finishing    NU           100                         100             1
     3 Carpentry    NU            80                          80             1
     4 Demand       B             20                          40

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           B             20             0
     2 x2           B             60             0

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err. = 0.00e+00 on column 0
        max.rel.err. = 0.00e+00 on column 0
        High quality

KKT.DB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

End of output

解は以下の 4 つのセクションに分かれています。

• 問題に関する情報と、目的関数の最適値
• 目的関数の状況および制約に関する正確な情報
• 決定変数の最適値に関する正確な情報
• 最適性条件に関する情報 (該当する場合)

この特定の問題に対して、解が OPTIMAL で、Giapetto 社の最大週次利益は 180 ドルになることがわかります。

Finishing 制約の状況は NU (St 列) となっています。NU は、その制約の上限に基本変数以外の変数があることを意味します。オペレーションズ・リサーチ理論の知識がある場合は、シンプレックス表を作成してチェックしてみてください。簡単には、以下のように説明できます。

制約がその上限または下限に達する場合は常に、その制約は境界制約と呼ばれます。境界制約は、目的関数が最適値に達する妨げとなります。例えば、それ以上回すことができない音量調節ツマミにこれを当てはめてみてください。このような事態になると、glpsol は制約の状況を NU または NL (それぞれ上限と下限) として表示し、限界価値 (潜在価格とも呼ばれる) の値を示します。限界価値とは、制約が1 単位緩和されたとしたら (音量調節ツマミがもう少し回ったとしたら)、目的関数が増加するであろう増分値です。この増分は、目標がターゲット関数の最小化か、または最大化であるかによって異なることに注意してください。例えば、最大化を目標にするGiapetto 社の問題の場合、限界価値の値 1 は、仕上げ作業時間を 1 時間増やすと目的関数が1 増えることを意味します。つまり、仕上げ作業時間の制約は上限であるため、数値は減るのではなく増えることになります。

木工作業時間と兵隊の需要に関する制約も同様です。木工作業時間の制約も同じく上限であることに注意してください。そのため、制約を 1 単位緩和すると (1 時間増加)、目的関数の最適値は限界価値 1 だけ良くなり 181 となります。

一方、兵隊の需要には境界がないため、状況は B となっています。この制約を緩和しても、目的関数の最適値は変わりません。

それぞれの境界制約の値を 1 ずつ緩和し、変更された問題を解決して、目的関数の最適値がどのように変動するかを調べてください。また、境界なしの制約の値を変更しても解が変わらないことを確認してください。

最後に、glpsol のレポートには決定変数の値として、x1 = 20、および x2 = 60 が示されます。これは、Giapetto 社が 20 個の兵隊と 60 個の列車を生産すれば、週次利益を最大限にすることができることを示しています。

Giapetto 社の問題は非常に小さな規模です。もっと多くの決定変数と制約がある問題では、変数と制約をそれぞれ個別に宣言する必要があるのかどうか疑問に思っていませんか。また、兵隊の販売価格などの問題のデータを調整したい場合、この値が現れるすべての箇所を変更しなければならないのでしょうか。次のセクションでは、そのような疑問に答えます。

上に戻る

Giapetto 問題のモデル・セクションとデータ・セクションを使用する

MathProg モデルには通常モデル・セクションとデータ・セクションがあり、場合によっては、この 2 つのセクションは別々のファイルに分かれています。これらのセクションにより、glpsol では異なるデータ・セットを使ってモデルを簡単に解決し、新しいデータでは解がどのようになるかを調べることができます。以下のリストでは、Giapetto 社の問題が一層洗練された方法で記述されています。

                
 1      #
 2      # Giapetto's problem
 3      #
 4      # This finds the optimal solution for maximizing Giapetto's profit
 5      #
 6
 7      /* Set of toys */
 8      set TOY;
 9
10      /* Parameters */
11      param Finishing_hours {i in TOY};
12      param Carpentry_hours {i in TOY};
13      param Demand_toys     {i in TOY};
14      param Profit_toys     {i in TOY};
15
16      /* Decision variables */
17      var x {i in TOY} >=0;
18
19      /* Objective function */
20      maximize z: sum{i in TOY} Profit_toys[i]*x[i];
21
22      /* Constraints */
23      s.t. Fin_hours : sum{i in TOY} Finishing_hours[i]*x[i] <= 100;
24      s.t. Carp_hours : sum{i in TOY} Carpentry_hours[i]*x[i] <= 80;
25      s.t. Dem {i in TOY} : x[i] <= Demand_toys[i];
26
27
28      data;
29      /* data  section */
30
31      set TOY := soldier train;
32
33      param Finishing_hours:=
34      soldier         2
35      train           1;
36
37      param Carpentry_hours:=
38      soldier         1
39      train           1;
40
41      param Demand_toys:=
42      soldier        40
43      train    6.02E+23;
44
45      param Profit_toys:=
46      soldier         3
47      train           2;
48
49      end;
 

上記では、2 つの別個のファイルではなく、モデル化セクション (行 1 から行 27) とデータ・セクション (行 28 から行 49) を持つ単一のファイルで問題が記述されています。

行 8 は SET を定義しています。SET は要素の領域です。例えば、数学的に xi, for all i in {1;2;3;4} と宣言する場合、x は 1 から 4 の範囲の配列として表されているため、x1 , x2 , x3 , x4 が得られます。この場合のセットは、{1;2;3;4} です。Giapetto 社の問題では、TOY という名前のセットがあります。このセットの実際の値はどこかと言うと、ファイルのデータ・セクション内にあります。行 31 を見てください。この行は TOY セットには soldier と train が含まれると定義しています。ご覧のとおり、このセットは数値の範囲ではありませんが、どうしてこのようなことが可能なのでしょう。これは、GLPKによる独特の処理方法により可能になっています。その使用方法については後で説明するとして、ここではデータ・セクションでのSET 宣言の構文に慣れてください。

set label := value1 value2 ... valueN ;

行 11 と行 12 は、問題のパラメーターを定義しています。パラメーターには、 Finishing_hours 、Carpentry_hours, and Demand_toys の 3 つがあります。この 3 つのパラメーターが問題のデータ行列を構成し、後で説明するように制約の計算に使用されます。

Finishing_hours パラメーターを例に挙げると、これは TOY セットで定義されているため、TOY セットに含まれるそれぞれの種類の玩具は Finishing_hours の値を持ちます。各兵隊には 2 時間の仕上げ作業が必要で、各列車には 1 時間の仕上げ作業が必要であることを覚えていてください。ここで、行 33、行 34、行 35 を見てください。種類ごとの玩具に対する仕上げ作業時間が定義されています。当然、これらの行は Finishing_hours[soldier]=2、Finishing_hours[train]=1 と宣言しています。つまり、Finishing_hours は 1 行 と 2 列で構成される行列となります。

木工作業時間と需要のパラメーターも同じように宣言されています。列車の需要は無制限であるため、行 43 では非常に大きな値が上限となっています。この値は見慣れた値ですか？

行 17 は、TOY に含まれるすべての i に対する変数 x を定義し (その結果、x[soldier] および x[train] となる)、そして値がゼロ以上になるように制約しています。このように、セットがあれば変数を宣言するのがとても簡単になります。

行 20 は、目的 (ターゲット) 関数を z の最大化として宣言しています。これは、各種類の玩具 (列車と兵隊の 2 種類) の利益を合計したものです。例えば兵隊の場合、この利益は、兵隊の数に兵隊ごとの利益を掛けた数値となります。

行23、行 24、および行 25 での制約も同じように宣言されています。仕上げ作業時間の制約を例に取ると、2 種類の玩具 (列車と兵隊) に対して、この制約は玩具の種類ごとの仕上げ作業の合計時間に、その種類の玩具の生産個数を掛けた値で、この値は 100 以下でなければなりません。同様に、木工作業時間の合計は 80 以下でなければなりません。

需要の制約は、前の 2 つとは少々異なります。その理由は、すべての種類の玩具の合計としてではなく、玩具の種類ごとに定義されるためです。したがって、行 25 から分かるように、需要の制約は列車用と兵隊用の 2 つが必要になります。インデックス変数 ( {i in TOY} ) はコロン (:) の前に置かれていることに注意してください。これは、GLPK にTOY に含まれる玩具の種類ごとに制約を作成するよう指示し、各制約を規定する等式がコロン (:) の後に来るということです。この場合、GLPK は以下を作成します。

Dem[soldier] : x[soldier] <= Demand[soldier]

Dem[train] : x[train] <= Demand[train]

この新しいモデルを解決すると、以下のように同じ結果になります。

                
Problem:    giapetto2
Rows:       5
Columns:    2
Non-zeros:  8
Status:     OPTIMAL
Objective:  z = 180 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B            180
     2 Fin_hours    NU           100                         100             1
     3 Carp_hours   NU            80                          80             1
     4 Dem[soldier] B             20                          40
     5 Dem[train]   B             60                    6.02e+23

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x[soldier]   B             20             0
     2 x[train]     B             60             0

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err. = 0.00e+00 on column 0
        max.rel.err. = 0.00e+00 on column 0
        High quality

KKT.DB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

End of output

TOY セットに続いて制約と決定変数が簡潔に整然と指定されていることがわかりますか。お見事です。Giapetto の利益が最大限になりました。

上に戻る

まとめ

今回は、最初に単純な 2 つの変数を持つ線形問題を定式化する方法、次に単純な MathProg プログラムで、セット、パラメーター、制約、決定変数、および目的 (ターゲット) 関数を使用して問題を解決する方法を学びました。このプログラムでは、セットの合計とパラメーター・データ・セクションが使用されました。最後に、最大化問題の結果を解釈する方法を学びました。

この 3 回シリーズでは次回、間違ったダイエット方法を最大限に利用する方法を紹介します。

上に戻る

ダウンロード

ダウンロード形式について

参考文献

学ぶために

• この記事で取り上げた問題は、Wayne L. Winston著「Operations Research: Applications and Algorithms, 4th Edition」(Thomson 出版、2004 年) の了承を得ています。
  
  
• GLPKのオンライン資料 には、GLPK に関する詳細、ソフトウェアの入手方法、そして GLPK コミュニティーへの参加方法が記載されています。
  
  
• Wikipedia で GLPK の項目を調べてください。
  
  
• GLPK のヘルプ・メーリング・リストまたはバグ・レポート・メーリング・リストに登録してください。
  
  
• developerWorks Linux ゾーン には、Linux 開発者用のリソースが多数あります。
  
  
• developerWorks technical events and Webcastsを利用して、最新技術を学んでください。
  
  

製品や技術を入手するために

• developerWorks から直接ダウンロードできる IBM トライアル・ソフトウェアを使用して、Linux で次の開発プロジェクトを構築してください。
  
  

議論するために

• developerWorks ブログにアクセスして、developerWorks コミュニティーに参加してください。
  
  

著者について

Rodrigo Ceron Ferreira de Castro は、IBM Linux Technology Center のスタッフ・ソフトウェア・エンジニアです。2004 年にカンピーナス州立大学 (UNICAMP) を卒業する際には、State Engineering Institute および Engineering Council Certification of Honor を受賞しています。ブラジルやその他の国でのオープン・ソース・コンファレンスでスピーチを行った経験もあります。

この記事を評価する

コメント

上に戻る

目次

• はじめに
• GNU Linear Programming Kit
• GNU MathProg モデル化言語
• Operations Research によると、問題は以下のとおりです。
• モデル化
• ちょっとした理論
• GLPK を使用してモデルを解決する
• Giapetto 問題のモデル・セクションとデータ・セクションを使用する
• まとめ
• ダウンロード
• 参考文献
• 著者について
• コメント