Skip to content

Instantly share code, notes, and snippets.

@komasaru
Last active April 19, 2018 05:28
Show Gist options
  • Save komasaru/8928838 to your computer and use it in GitHub Desktop.
Save komasaru/8928838 to your computer and use it in GitHub Desktop.
Ruby script to execute linear programming with Simplex method.
#! /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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment