数理計画問題の定式化

オペレーションズリサーチA
第８回ソフトウェアを用いた演習
• 授業サポートページ
http://www.morito.mgmt.waseda.ac.jp/ora/
• ソフトウェアAMPL＋CPLEXインストール（確認）
• 問題がある場合[email protected]
• 第８回ソフトウェアを用いた演習
演習問題
• 分枝停止となる場合、分枝停止理由をファイルに表
示させる
– 整数解が得られた
– 実行不可能
– 暫定値よりよい解がない（限定操作）
• 対象とする問題（4変数ナップサック）は、第6回演習
課題であり、講義内で説明済。
• （問題）min 15x1+18x2+6x3+2x4
subject to 4x1+5x2+2x3+x4≦6
x1, x2, x3, x4∈{0,1}
• 提出するファイルは、bb-knapsack.sol(結果ファイ
ル）のみ
分枝停止理由をファイルに表示させる
•
以下の条件文をbb-knapsack.runに追加する。
•
ヒント：追加する位置は、分枝されない時であるため、分枝される場合の後になる。
•
第6回演習課題の結果と同じになることを確認すること。分枝停止する理由が追加される。
•
特に、限定操作が行われることに注意。
•
実行不可能
if (solve_result="infeasible") then
{
printf: "BRANCHING stopped: infeasibility \n" >bb-knapsack.sol;
}
•
整数解が得られた
if ((forall {i in 1..Nitem} x[i]*(1-x[i]) < epsilon)
and (solve_result="solved")) then
{
printf: "BRANCHING stopped: integer solution obtained \n" >bb-knapsack.sol;
}
•
暫定値よりよい解がない（限定操作）
if ( (Profit <= tmpprofit)
and (solve_result="solved")) then
{
printf: "BRANCHING stopped: bounding procedure \n" >bb-knapsack.sol;
}

Download Report