情報学最終課題の内容

2015/7/21
情報学
～最終課題の説明と演習2～
2015年7月21日
笠井俊信
最終課題の内容
• シンプレックス法をBASICで記述
– データはプログラム内に記述
– 来週，途中まで演習・解説
– 続きを完成させてメールで提出
• 〆切
8月10日（月）
– 8月11日にHPに解答例を公開
1
2015/7/21
【例題】
ある会社が、A、Bという製品を売り出している。それら
を製作するための材料はプラスチック、アルミ、ゴムであ
る。それぞれ１個を製作するために必要な材料の量は
下の表のとおりである。
プラスチック
アルミゴム
単価
A
1ｋｇ
1ｋｇ
3ｋｇ
２万円
B
2ｋｇ
1ｋｇ
1ｋｇ
３万円
材料の量
14ｋｇ
8ｋｇ
18ｋｇ
このとき、手持ちの材料の範囲内で売上高を最大
にするためには、A、Bをそれぞれいくつつくったら
よいか？
シンプレックス表の作成
Z  2 x1  3 x2
0
x1  2 x2  x3
x1  x2
 14
 x4
3x1  x2
8
 x5  18
xn  (n  1,2,3,4,5)
基底変数
x1
x2
x3
x4
x5
定数項
Z
-2
-3
0
0
0
0
x3
1
2
1
0
0
14
x4
1
1
0
1
0
8
x5
3
1
0
0
1
18
2
2015/7/21
出力結果例
シンプレックス法の解法手順
• 終了条件：
– 目的関数の係数がすべて正になったら終了
• 手順1
– 目的関数の係数の中から最小なものがある列qを抽出
• 手順2
– 手順1で求めたq列にある各行の要素で各行の定数項
を割ったものが最小となる行pを抽出（目的関数以外の行）
• 手順3
– p行q列をピボットにして掃き出し演算を行う
終了条件を満たすまで手順1に戻り繰り返す
3
2015/7/21
課題を数ステップに分割
1. プログラム内のデータを変数に読み込む
2. 終了条件を記述（後回し）
– 終了条件を満たさない限り繰り返す
3.
4.
5.
6.
手順1（q列の抽出）を記述
手順2（p行の抽出）を記述
手順3（掃き出し演算）を記述
結果の出力
１．データを変数に読み込む
100 DIM X(10,10)
110 READ G,R
120 FOR I=1 TO G
130 FOR J=1 TO R
140 READ X(I,J)
150 NEXT J
160 NEXT I
600 DATA 4,7
610 DATA 0,-2,-3,0,0,0,0
620 DATA 3,1,2,1,0,0,14
630 DATA 4,1,1,0,1,0,8
640 DATA 5,3,1,0,0,1,18
650 END
2次元配列のすべてのデータを操作するには
For文を入れ子にする必要がある
4
2015/7/21
元データを出力してみよう
シンプレックス法の解法手順
• 終了条件：
– 目的関数の係数がすべて正になったら終了
• 手順1
– 目的関数の係数の中から最小なものがある列qを抽出
• 手順2
– 手順1で求めたq列にある各行の要素で各行の定数項
を割ったものが最小となる行pを抽出（目的関数以外の行）
• 手順3
– p行q列をピボットにして掃き出し演算を行う
終了条件を満たすまで手順1に戻り繰り返す
5
2015/7/21
３．手順1（q列の抽出）を記述
手順1
目的関数の係数の中から最小
なものがある列qを抽出
X(1,2) ～ X(1,R-1) の最小のデータの列の場所を
抽出。
戦略例：
変数K，Mの初期値を０にしておき， X(1,2) ～ X(1,R-1) で
M未満のデータの値をMに，その列をKに代入する。
最終的なKが求めるq
戦略例：
変数K，Mの初期値を０にしておき， X(1,2) ～ X(1,R-1) で
M未満のデータの値をMに，その列をKに代入する。
最終的なKが求めるq
• 変数K, Mに0を代入
• （繰り返し）Jを2からR-1以下まで繰り返す
– （条件分岐）X(1,J)がM以上か？
• 真ならば6行目へ
• 偽ならば M=X(1,J) K=J
– Jを1増やす
6
2015/7/21
100 REM Program 0722
110 DIM X(10,10)
120 READ G,R
130 FOR I=1 TO G
140 FOR J=1 TO R
150 READ X(I,J)
160 NEXT J
170 NEXT I
180 PRINT "元データ"
190 FOR I=1 TO G
200 FOR J=1 TO R
210 PRINT X(I,J);
220 NEXT J
230 PRINT ""
240 NEXT I
250 LET K=0
260 LET M=0
270 FOR J=2 TO R-1
280 IF X(1,J) >= M THEN 310
290 LET K=J
300 LET M=X(1,J)
310 NEXT J
320 PRINT K
600 DATA 4,7
610 DATA 0,-2,-3,0,0,0,0
620 DATA 3,1,2,1,0,0,14
630 DATA 4,1,1,0,1,0,8
640 DATA 5,3,1,0,0,1,18
650 END
7

Download Report