Class: Simplex

Inherits:
Object
  • Object
show all
Defined in:
lib/simplex.rb

Constant Summary collapse

DEFAULT_MAX_ITERATIONS = 
1_000_000

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(c, a, b) ⇒ Simplex

Returns a new instance of Simplex.



17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/simplex.rb', line 17

def initialize(c, a, b)
  @max_iterations = DEFAULT_MAX_ITERATIONS
  # Problem dimensions
  @num_non_slack_vars = a.first.length
  @num_constraints    = b.length
  @num_vars           = @num_non_slack_vars + @num_constraints
  @x                  = Array.new(@num_vars)

  # Set up initial matrix A and vectors b, c
  @c = Vector[*c.map {|c1| -1*c1 } + [0]*@num_constraints]
  @a = Matrix[*a.map {|a1| a1.clone + [0]*@num_constraints}]
  @b = Vector[*b.clone]
  0.upto(@num_constraints - 1) {|i| @a[i, @num_non_slack_vars + i] = 1 }

  @basic_vars = ((@num_non_slack_vars)...(@num_vars)).to_a

  # set initial solution: all non-slack variables = 0
  update_solution
  @solved = false
end

Instance Attribute Details

#max_iterations ⇒ Object

Returns the value of attribute max_iterations.



15
16
17
 
# File 'lib/simplex.rb', line 15

def max_iterations
  @max_iterations
end

Instance Method Details

#can_improve? ⇒ Boolean

Returns:

  • (Boolean) 


97
98
99
 
# File 'lib/simplex.rb', line 97

def can_improve?
  !!entering_variable_ix
end

#entering_variable_ix ⇒ Object 



101
102
103
104
105
106
107
108
109
110
111
112
113
 
# File 'lib/simplex.rb', line 101

def entering_variable_ix
  current_min_value = nil
  current_min_index = nil
  @c.each_with_index do |v, i| 
    if v < 0
      if current_min_value == nil || v <= current_min_value
        current_min_value = v
        current_min_index = i
      end
    end
  end
  current_min_index
end

#leaving_variable(pivot_row) ⇒ Object 



115
116
117
118
119
120
121
 
# File 'lib/simplex.rb', line 115

def leaving_variable(pivot_row)
  0.upto(@a.column_count - 1) do |column_ix|
    if @a[pivot_row, column_ix] == 1 and @basic_vars.include?(column_ix)
      return column_ix
    end
  end
end

#minimum_coefficient_ratio_row_ix(column_ix) ⇒ Object 



123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/simplex.rb', line 123

def minimum_coefficient_ratio_row_ix(column_ix)
  current_min_value = nil
  current_min_index = nil
  0.upto(@a.row_count - 1) do |row_ix|
    next if @a[row_ix, column_ix] == 0
    ratio = Rational(@b[row_ix], @a[row_ix, column_ix])
    if ratio > 0 && (!current_min_value || ratio < current_min_value)
      current_min_value = ratio
      current_min_index = row_ix
    end
  end
  return current_min_index
end

#solution ⇒ Object 



92
93
94
95
 
# File 'lib/simplex.rb', line 92

def solution
  solve
  @x.to_a[0...@num_non_slack_vars]
end

#solve ⇒ Object 



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
 
# File 'lib/simplex.rb', line 38

def solve
  return if @solved
  i = 0
  while can_improve? and i < @max_iterations
    i += 1
    pivot_column = entering_variable_ix
    pivot_row    = minimum_coefficient_ratio_row_ix(pivot_column)
    leaving_var = leaving_variable(pivot_row)
    @basic_vars.delete(leaving_var)

    # update objective
    c_ratio = Rational(@c[pivot_column], @a[pivot_row, pivot_column])
    @c = @c - (@a.row(pivot_row)*c_ratio)

    # update pivot row
    ratio = Rational(1, @a[pivot_row, pivot_column])
    0.upto(@a.column_count - 1) do |column_ix|
      @a[pivot_row, column_ix] = ratio * @a[pivot_row, column_ix]
    end
    @b[pivot_row] = ratio * @b[pivot_row]

    # update A and B
    0.upto(@a.row_count - 1) do |row_ix|
      next if row_ix == pivot_row
      ratio = @a[row_ix, pivot_column]
      0.upto(@a.column_count - 1) do |column_ix|
        @a[row_ix, column_ix] = @a[row_ix, column_ix] - ratio*@a[pivot_row, column_ix]
      end
      @b[row_ix] = @b[row_ix] - ratio*@b[pivot_row]
    end

    @basic_vars << pivot_column
    @basic_vars.sort!
    update_solution
  end
  @solved = true
end

#update_solution ⇒ Object 



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/simplex.rb', line 76

def update_solution
  0.upto(@num_vars - 1) {|i| @x[i] = 0 }
  @basic_vars.each do |basic_var|
    row_coeff_1 = nil
    0.upto(@a.row_count - 1) do |row_ix|
      coeff = @a[row_ix, basic_var]
      if coeff == 1
        if row_coeff_1 == nil
          row_coeff_1 = row_ix
        end
      end
    end
    @x[basic_var] = @b[row_coeff_1]
  end
end