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

更新日時:


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

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

0. 前提条件

1. Ruby スクリプト作成

File: 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
101
102
103
104
105
106
107
108
109
110
111
112
113
#! /usr/local/bin/ruby
# ***************************************
# 線形計画法(シンプレックス法)
# ***************************************
#
class LinearProgrammingSimplex
  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 exec
    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
  rescue => e
    raise
  end

  private

  # 列選択
  def select_col(min)
    y = 0

    begin
      (N_COL - 1).times do |k|
        next unless @a[N_ROW - 1][k] < min
        min, y = @a[N_ROW - 1][k], k
      end
      return [min, y]
    rescue => e
      raise
    end
  end

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

    begin
      (N_ROW - 1).times do |k|
        p = @a[k][N_COL - 1] / @a[k][y].to_f
        next unless  @a[k][y] > 0 && p < min
        min, x = p, k
      end
      return [min, x]
    rescue => e
      raise
    end
  end

  # ピボット係数を p で除算
  def divide_pibot_var(x, y)
    p = @a[x][y]
    N_COL.times { |k| @a[x][k] /= p.to_f }
  rescue => e
    raise
  end

  # ピボット掃き出し
  def sweap_out(x, y)
    N_ROW.times do |k|
      next if k == x
      d = @a[k][y]
      N_COL.times { |j| @a[k][j] -= d * @a[x][j] }
    end
  rescue => e
    raise
  end

  # 結果出力
  def display
    N_VAR.times do |k|
      flag = -1
      N_ROW.times { |j| flag = j if @a[j][k] == 1 }
      puts "x%d = %8.4f" % [k, flag == -1 ? 0.0 : @a[flag][N_COL - 1]]
    end
    puts "z  = %8.4f" % @a[N_ROW - 1][N_COL - 1]
  rescue => e
    raise
  end
end

if __FILE__ == $0
  begin
    # インスタンス化&実行
    LinearProgrammingSimplex.new.exec
  rescue => e
    $stderr.puts "[#{e.class}] #{e.message}"
    e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
  end
end

2. 実行

まず、実行権限を付与。

$ chmod +x linear_programming_simplex.rb

そして、実行。

$ ./linear_programming_simplex.rb
x0 =   2.0000
x1 =   6.0000
z  =  22.0000

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


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

以上。

 

Sponsored Link

 

コメントする