整数問題
提供: Internet Web School
(間の9版分が非表示) | |||
6 行: | 6 行: | ||
ただし,生産量は整数値でなければならない。 | ただし,生産量は整数値でなければならない。 | ||
+ | {| border="3" class="wikitable" style="text-align: center; " | ||
+ | |原材\製品名 | ||
+ | |A | ||
+ | |B | ||
+ | |C | ||
+ | |使用できる上限 | ||
+ | |- | ||
+ | |Ⅰ | ||
+ | |4 | ||
+ | |0 | ||
+ | |7 | ||
+ | |90 | ||
+ | |- | ||
+ | |Ⅱ | ||
+ | |1 | ||
+ | |3 | ||
+ | |9 | ||
+ | |60 | ||
+ | |- | ||
+ | |Ⅲ | ||
+ | |6 | ||
+ | |0 | ||
+ | |14 | ||
+ | |110 | ||
+ | |- | ||
- | + | |Ⅳ | |
- | + | |4 | |
+ | |10 | ||
+ | |1 | ||
+ | |75 | ||
+ | |} | ||
この問題は以下のように数学的に定式化される. | この問題は以下のように数学的に定式化される. | ||
44 行: | 73 行: | ||
[[ファイル:整数計画.pdf]] | [[ファイル:整数計画.pdf]] | ||
+ | 作成したデータは以下の通りである. | ||
+ | [[ファイル:LP-Fig30 ページ 2.jpg|500px]] | ||
- | + | [[ファイル:LP-Fig30 ページ 3.jpg|500px]] | |
- | |||
ソルバーのパラメータ 入力は以下の通りである. | ソルバーのパラメータ 入力は以下の通りである. | ||
- | [[ファイル:LP- | + | [[ファイル:LP-Fig30 ページ 4.jpg|500px]] |
ソルバーによる結果は以下の通りである. | ソルバーによる結果は以下の通りである. | ||
- | |||
- | + | [[ファイル:LP-Fig30 ページ 5.jpg|500px]] | |
- | $ | + | |
- | + | $x_1=16,x_2=1,x_3=1$ | |
- | [[ファイル: | + | |
+ | のときに | ||
+ | |||
+ | $L\left(x_1,x_2, x_3\right)=80x_1+110x_2+95x_3$ | ||
+ | |||
+ | が最大値1485をもつことを表す.制約条件は満たされている. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | フリーソフトOpenOfficeの表計算(Calc) でも同様に解くことができる. | ||
+ | |||
+ | Calcの線形計画法解析ソフトもExcelと同じ名前の「ソルバー」である. | ||
+ | メニューの「ツール」の「ソルバー」である. | ||
+ | Excelのソルバーと操作法は殆ど同じある. | ||
+ | |||
+ | ベクトルの内積もExcelと同様にsumproductである. | ||
+ | 行ベクトルと行ベクトルとの区切りが,ではなく;であることが異なる。 | ||
+ | ベクトル(B4,C4,D4) と(B2,C2,D2)の内積 B4*B2+C4*C2+D4*D2 | ||
+ | はsumproduct(B4:D4;B2:D2)で表される. | ||
+ | また, | ||
+ | |||
+ | $ | ||
+ | x_1,0 x_2,x_3 | ||
+ | $ | ||
+ | が自然数であるという制約条件 | ||
+ | ソルバーのメニューのオプションを使う. | ||
+ | |||
+ | |||
+ | 変数を整数と想定 | ||
+ | |||
+ | 変数を負でないと想定 | ||
+ | |||
+ | の両方にチェックを入れる. | ||
+ | |||
+ | |||
+ | 以下にデータの入力とソルバーの設定例を示す. | ||
+ | |||
+ | [[ファイル:Open整数計画.jpg|800px]] |
2021年1月18日 (月) 09:23 時点における最新版
整数計画
生産計画で述べた条件と全く同様に,企業では製品A,B,Cを原料Ⅰ,Ⅱ,Ⅲ,Ⅳ用いて生産している. 製品A,B,C の1単位当たり利益をそれぞれ80,110,95とする. また, 製品A,B,Cを1単位生産するのに必要な原料Ⅰ,Ⅱ,Ⅲ,Ⅳのそれぞれ量と使用可能な上限が次の表で与えられる. これらの条件のもとに,利益を最大にするには製品A,B,Cをそれぞれ,どれだけ生産すれば良いか?. ただし,生産量は整数値でなければならない。
原材\製品名 | A | B | C | 使用できる上限 |
Ⅰ | 4 | 0 | 7 | 90 |
Ⅱ | 1 | 3 | 9 | 60 |
Ⅲ | 6 | 0 | 14 | 110 |
Ⅳ | 4 | 10 | 1 | 75 |
この問題は以下のように数学的に定式化される.
整数計画法
製品A,B,Cをそれぞれx1,x2,x3 単位生産するときx1,x2,x3は以下の不等式を満たす.
4x1+0x2+7x3≤901x1+3x2+9x3≤606x1+0x2+14x3≤1104x1+10x2+1x3≤75 (1)
x1,x2,x3∈N,0≤x1,0≤x2,0≤x3(2)
この制約条件のもとに
L(x1,x2,x3)=80x1+110x2+95x3(3)
を最大にするx1,x2,x3を求めよ.
この問題を解くのにはMicrosoft Excelのソルバーや フリーソフトのOpen Office で提供されるソルバーと同等の機能をもつソフトを用いることができる.
この問題のMicrosoft Excelのソルバーによる解法例を示す。 ファイル:整数計画.pdf
作成したデータは以下の通りである.
ソルバーのパラメータ 入力は以下の通りである.
ソルバーによる結果は以下の通りである.
x1=16,x2=1,x3=1
のときに
L(x1,x2,x3)=80x1+110x2+95x3
が最大値1485をもつことを表す.制約条件は満たされている.
フリーソフトOpenOfficeの表計算(Calc) でも同様に解くことができる.
Calcの線形計画法解析ソフトもExcelと同じ名前の「ソルバー」である. メニューの「ツール」の「ソルバー」である. Excelのソルバーと操作法は殆ど同じある.
ベクトルの内積もExcelと同様にsumproductである. 行ベクトルと行ベクトルとの区切りが,ではなく;であることが異なる。 ベクトル(B4,C4,D4) と(B2,C2,D2)の内積 B4*B2+C4*C2+D4*D2 はsumproduct(B4:D4;B2:D2)で表される. また,
x1,0x2,x3 が自然数であるという制約条件 ソルバーのメニューのオプションを使う.
変数を整数と想定
変数を負でないと想定
の両方にチェックを入れる.
以下にデータの入力とソルバーの設定例を示す.