class Simplex
Constants
- DEFAULT_MAX_PIVOTS
Attributes
max_pivots[RW]
Public Class Methods
new(c, a, b)
click to toggle source
# File lib/simplex.rb, line 15 def initialize(c, a, b) @pivot_count = 0 @max_pivots = DEFAULT_MAX_PIVOTS # Problem dimensions @num_non_slack_vars = a.first.length @num_constraints = b.length @num_vars = @num_non_slack_vars + @num_constraints # Set up initial matrix A and vectors b, c @c = Vector[*c.map {|c1| -1*c1 } + [0]*@num_constraints] @a = a.map {|a1| Vector[*(a1.clone + [0]*@num_constraints)]} @b = Vector[*b.clone] unless @a.all? {|a| a.size == @c.size } and @b.size == @a.length raise ArgumentError, "Input arrays have mismatched dimensions" end 0.upto(@num_constraints - 1) {|i| @a[i][@num_non_slack_vars + i] = 1 } # set initial solution: all non-slack variables = 0 @x = Vector[*([0]*@num_vars)] @basic_vars = (@num_non_slack_vars...@num_vars).to_a update_solution end
Public Instance Methods
assert(boolean)
click to toggle source
# File lib/simplex.rb, line 187 def assert(boolean) raise unless boolean end
basic_variable_in_row(pivot_row)
click to toggle source
# File lib/simplex.rb, line 129 def basic_variable_in_row(pivot_row) column_indices.detect do |column_ix| @a[pivot_row][column_ix] == 1 and @basic_vars.include?(column_ix) end end
can_improve?()
click to toggle source
# File lib/simplex.rb, line 69 def can_improve? !!entering_variable end
column_indices()
click to toggle source
# File lib/simplex.rb, line 139 def column_indices (0...@a.first.size).to_a end
current_solution()
click to toggle source
# File lib/simplex.rb, line 46 def current_solution @x.to_a[0...@num_non_slack_vars] end
entering_variable()
click to toggle source
# File lib/simplex.rb, line 77 def entering_variable variables.select { |var| @c[var] < 0 }. min_by { |var| @c[var] } end
formatted_tableau()
click to toggle source
# File lib/simplex.rb, line 143 def formatted_tableau if can_improve? pivot_column = entering_variable pivot_row = pivot_row(pivot_column) else pivot_row = nil end num_cols = @c.size + 1 c = formatted_values(@c.to_a) b = formatted_values(@b.to_a) a = @a.to_a.map {|ar| formatted_values(ar.to_a) } if pivot_row a[pivot_row][pivot_column] = "*" + a[pivot_row][pivot_column] end max = (c + b + a + ["1234567"]).flatten.map(&:size).max result = [] result << c.map {|c| c.rjust(max, " ") } a.zip(b) do |arow, brow| result << (arow + [brow]).map {|a| a.rjust(max, " ") } result.last.insert(arow.length, "|") end lines = result.map {|b| b.join(" ") } max_line_length = lines.map(&:length).max lines.insert(1, "-"*max_line_length) lines.join("\n") end
formatted_values(array)
click to toggle source
# File lib/simplex.rb, line 170 def formatted_values(array) array.map {|c| "%2.3f" % c } end
last_min_by(array) { |element| ... }
click to toggle source
like Enumerable#min_by except if multiple values are minimum it returns the last
# File lib/simplex.rb, line 176 def last_min_by(array) best_element, best_value = nil, nil array.each do |element| value = yield element if !best_element || value <= best_value best_element, best_value = element, value end end best_element end
pivot()
click to toggle source
# File lib/simplex.rb, line 82 def pivot pivot_column = entering_variable pivot_row = pivot_row(pivot_column) raise UnboundedProblem unless pivot_row leaving_var = basic_variable_in_row(pivot_row) replace_basic_variable(leaving_var => pivot_column) pivot_ratio = Rational(1, @a[pivot_row][pivot_column]) # update pivot row @a[pivot_row] *= pivot_ratio @b[pivot_row] = pivot_ratio * @b[pivot_row] # update objective @c -= @c[pivot_column] * @a[pivot_row] # update A and B (row_indices - [pivot_row]).each do |row_ix| r = @a[row_ix][pivot_column] @a[row_ix] -= r * @a[pivot_row] @b[row_ix] -= r * @b[pivot_row] end update_solution end
pivot_row(column_ix)
click to toggle source
# File lib/simplex.rb, line 115 def pivot_row(column_ix) row_ix_a_and_b = row_indices.map { |row_ix| [row_ix, @a[row_ix][column_ix], @b[row_ix]] }.reject { |_, a, b| a == 0 }.reject { |_, a, b| (b < 0) ^ (a < 0) # negative sign check } row_ix, _, _ = *last_min_by(row_ix_a_and_b) { |_, a, b| Rational(b, a) } row_ix end
replace_basic_variable(hash)
click to toggle source
# File lib/simplex.rb, line 108 def replace_basic_variable(hash) from, to = hash.keys.first, hash.values.first @basic_vars.delete(from) @basic_vars << to @basic_vars.sort! end
row_indices()
click to toggle source
# File lib/simplex.rb, line 135 def row_indices (0...@a.length).to_a end
solution()
click to toggle source
# File lib/simplex.rb, line 41 def solution solve current_solution end
solve()
click to toggle source
# File lib/simplex.rb, line 61 def solve while can_improve? @pivot_count += 1 raise "Too many pivots" if @pivot_count > max_pivots pivot end end
update_solution()
click to toggle source
# File lib/simplex.rb, line 50 def update_solution 0.upto(@num_vars - 1) {|i| @x[i] = 0 } @basic_vars.each do |basic_var| row_with_1 = row_indices.detect do |row_ix| @a[row_ix][basic_var] == 1 end @x[basic_var] = @b[row_with_1] end end
variables()
click to toggle source
# File lib/simplex.rb, line 73 def variables (0...@c.size).to_a end