mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

Ruby - 線形計画法(シンプレックス法)!

[ プログラミング, 数学 ] [ Ruby ]

こんばんは。

前回は、C++ による「線形計画法(シンプレックス法)」のアルゴリズムを紹介しました。

今回は、同じアルゴリズムを Ruby で実現してみました。アルゴリズムについては、上記リンクの記事を参照してください。

以下、Ruby によるサンプルスクリプトです。

0. 前提条件

1. Ruby スクリプト作成

今回作成した Ruby ソースは以下の通りです。

linear_programming_simplex.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# ***************************************
# 線形計画法(シンプレックス法)
# ***************************************

# 計算クラス
class Calc
  # 定数
  N_ROW = 4  # 行数
  N_COL = 6  # 列数
  N_VAR = 2  # 変数の数

  def initialize
    # 係数行列
    @a = [
      [ 1.0,  2.0,  1.0,  0.0,  0.0, 14.0],
      [ 1.0,  1.0,  0.0,  1.0,  0.0,  8.0],
      [ 3.0,  1.0,  0.0,  0.0,  1.0, 18.0],
      [-2.0, -3.0,  0.0,  0.0,  0.0,  0.0]
    ]
  end

  # 線形計画法
  def calc_linear_programming
    loop do
      # 列選択
      min, y = select_col(9999)
      break if min >= 0

      # 行選択
      min, x = select_row(9999, y)

      # ピボット係数を p で除算
      divide_pibot_var(x, y)

      # ピボット列の掃き出し
      sweap_out(x, y)
    end

    # 結果出力
    display
  end

  private

  # 列選択
  def select_col(min)
    y = 0
    0.upto(N_COL - 2) do |k|
      if @a[N_ROW - 1][k] < min
        min = @a[N_ROW - 1][k]
        y   = k
      end
    end

    return [min, y]
  end

  # 行選択
  def select_row(min, y)
    x = 0
    0.upto(N_ROW - 2) do |k|
      p = @a[k][N_COL - 1] / @a[k][y].to_f
      if @a[k][y] > 0 && p < min
        min = p
        x   = k
      end
    end

    return [min, x]
  end

  # ピボット係数を p で除算
  def divide_pibot_var(x, y)
    p = @a[x][y]
    0.upto(N_COL - 1) { |k| @a[x][k] = @a[x][k] / p.to_f }
  end

  # ピボット掃き出し
  def sweap_out(x, y)
    0.upto(N_ROW - 1) do |k|
      unless k == x
        d = @a[k][y]
        0.upto(N_COL - 1) { |j| @a[k][j] -= d * @a[x][j] }
      end
    end
  end

  # 結果出力
  def display
    0.upto(N_VAR - 1) do |k|
      flag = -1
      0.upto(N_ROW - 1) { |j| flag = j if @a[j][k] == 1 }
      printf("x%d = %8.4f\n", k, flag == -1 ? 0.0 : @a[flag][N_COL - 1])
    end
    printf("z  = %8.4f\n", @a[N_ROW - 1][N_COL - 1])
  end
end

# インスタンス化&実行
Calc.new.calc_linear_programming

2. 実行

実際に、実行してみる。

1
2
3
4
$ ruby linear_programming.rb
x0 =   2.0000
x1 =   6.0000
z  =  22.0000

コンソールには商品の生産量とそのときの売上高が出力される。


色々と数値を変えてみたり、元の数を増やしてみるのもよいでしょう。

以上。

Comments