問題解決の数理(’17)

放送大学教養学部専門科目(情報) 共用科目(自然と環境) 科目コード:1570242 主任講師:大西 仁

第14章・第14回 組み合わせ最適化法

概要
組み合わせ最適化問題とは、条件を満たす変数の組み合わせの中で最適なものを求める問題である。組み合わせ最適化問題は実世界にあふれている。その多くは解くための計算量が莫大になり、素朴な探索では解くことができないが、様々な工夫が施され、年々規模の大きな問題を解くことができるようになっている。代表的な組み合わせ最適化問題と解法について解説する。
【キーワード】
組み合わせ最適化問題,分枝限定法,欲張り法,動的計画法
放送授業パタン,台本(字幕代りにどうぞ)
パタン
パタンA4版背景なし
台本
Excelソルバーによる整数最適化法
ナップサック問題
R (lpSolveパッケージ)による整数最適化法
ナップサック問題
GLPKによる整数最適化法
ナップサック問題
プログラム
/* Knapsack Problem */

var x1, binary;
var x2, binary;
var x3, binary;

maximize z: 6*x1 + 3*x2 + 4*x3;

s.t. CAPACITY: 4*x1 + 3*x2 + 6*x3 <= 9;

end;
出力
Problem:    KP
Rows:       2
Columns:    3 (3 integer, 3 binary)
Non-zeros:  6
Status:     INTEGER OPTIMAL
Objective:  z = 9 (MAXimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 z                           9                             
     2 CAPACITY                    7                           9 

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 x1           *              1             0             1 
     2 x2           *              1             0             1 
     3 x3           *              0             0             1 

Integer feasibility conditions:

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

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

End of output
このページのトップへ
最小木問題
プログラム
/* Minimum Spanning Tree Problem */

var x12, binary;
var x13, binary;
var x14, binary;
var x15, binary;
var x23, binary;
var x24, binary;
var x25, binary;
var x34, binary;
var x35, binary;
var x45, binary;

minimize z: x12 + 4*x13 + 5*x14 + 3*x15 + 2*x23 + 6*x24 + 7*x45;

s.t. SPANNING: x12 + x13 + x14 + x15 + x23 + x24 + x45 = 4;
s.t. Loop_3_1: x12 + x13 + x14 + x23 + x24 + x34 <= 3;
s.t. Loop_3_2: x12 + x13 + x15 + x23 + x25 + x35 <= 3;
s.t. Loop_3_3: x12 + x14 + x15 + x24 + x25 + x45 <= 3;
s.t. Loop_3_4: x13 + x14 + x15 + x34 + x35 + x45 <= 3;
s.t. Loop_3_5: x23 + x24 + x25 + x34 + x35 + x45 <= 3;
s.t. Loop_2_1: x12 + x13 + x23 <= 2;
s.t. Loop_2_2: x12 + x14 + x24 <= 2;
s.t. Loop_2_3: x13 + x14 + x34 <= 2;
s.t. Loop_2_4: x23 + x24 + x34 <= 2;
s.t. Loop_2_5: x12 + x15 + x25 <= 2;
s.t. Loop_2_6: x13 + x15 + x35 <= 2;
s.t. Loop_2_7: x23 + x25 + x35 <= 2;
s.t. Loop_2_8: x14 + x15 + x45 <= 2;
s.t. Loop_2_9: x24 + x25 + x45 <= 2;
s.t. Loop_2_10: x34 + x35 + x45 <= 2;

end;
出力
Problem:    minSpanningTree
Rows:       17
Columns:    10 (10 integer, 10 binary)
Non-zeros:  74
Status:     INTEGER OPTIMAL
Objective:  z = 11 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 z                          11                             
     2 SPANNING                    4             4             = 
     3 Loop_3_1                    3                           3 
     4 Loop_3_2                    3                           3 
     5 Loop_3_3                    3                           3 
     6 Loop_3_4                    2                           3 
     7 Loop_3_5                    1                           3 
     8 Loop_2_1                    2                           2 
     9 Loop_2_2                    2                           2 
    10 Loop_2_3                    1                           2 
    11 Loop_2_4                    1                           2 
    12 Loop_2_5                    2                           2 
    13 Loop_2_6                    1                           2 
    14 Loop_2_7                    1                           2 
    15 Loop_2_8                    2                           2 
    16 Loop_2_9                    0                           2 
    17 Loop_2_10                   0                           2 

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 x12          *              1             0             1 
     2 x13          *              0             0             1 
     3 x14          *              1             0             1 
     4 x15          *              1             0             1 
     5 x23          *              1             0             1 
     6 x24          *              0             0             1 
     7 x25          *              0             0             1 
     8 x34          *              0             0             1 
     9 x35          *              0             0             1 
    10 x45          *              0             0             1 

Integer feasibility conditions:

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

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

End of output

このページのトップへ