{{ message }}

Instantly share code, notes, and snippets.

# xixixao/Simplex Algorithm.coffee

Last active Aug 29, 2015
OR operations
 #I = [5, 6, 7] #matrix = [ # [1, 10, -57, -9, -24, 0, 0, 0, 0] # [0, 0.5, -5.5, -2.5, 9, 1, 0, 0, 0] # [0, 0.5, -1.5, -0.5, 1, 0, 1, 0, 0] # [0, 1, 0, 0, 0, 0, 0, 1, 1] #] I = [4, 7, 6, 8] matrix = [ [1, 3, 1, -1, 0, -1, 0, 0, 0, 6] [0, -1, 2, 0, 1, 0, 0, 0, 0, 2] [0, 2, 1, 0, 0, -1, 0, 1, 0, 6] [0, 3, -1, 0, 0, 0, 1, 0, 0, 9] [0, 1, 0, -1, 0, 0, 0, 0, 1, 0] ] max = (array) -> m = -Infinity mI = 0 for el, i in array if el > m m = el mI = i [m, mI] min = (array) -> m = Infinity mI = 0 for el, i in array if el < m m = el mI = i [m, mI] firstPositive = (array) -> for el, i in array if el > 0 and i > 0 return [el, i] return [-1] step = (matrix, I, rule = max) -> [objective, basics...] = matrix [value, newBasic] = rule objective[...objective.length - 1] log newBasic if value <= 0 return [value, newNonBasicI] = min (for row in basics if row[newBasic] < 0 Infinity else row[row.length - 1] / row[newBasic] ) if value is Infinity return newNonBasic = I[newNonBasicI] pivotRow = basics[newNonBasicI] pivot = pivotRow[newBasic] pivotRow = (el / pivot for el in pivotRow) newMatrix = for row in matrix q = row[newBasic] for el, i in row el - q * pivotRow[i] newMatrix[1 + newNonBasicI] = pivotRow newI = for v in I if v is newNonBasic newBasic else v [newMatrix, newI] simplex = (matrix, I, limit, rule = max) -> for i in [0...limit] res = step matrix, I, rule break unless res printTableau [matrix, I] = res printTableau = ([matrix, I]) -> head = "\nBV\t" + ("x#{i}" for i in [1...matrix[0].length - 1]).join '\t' head += "\tRHS" I = ["z"].concat I head += "
" + ((for row, i in matrix I[i] + "\t" + (el for el in row[1..]).join '\t' ).join '
') + "

" toSimpleFraction = (x) -> [v, d] = toFraction x if d == 1 v else "#{v}/#{d}" toFraction = (x, error = 0.000001) -> n = Math.floor x x -= n if x < error return [n, 1] else if 1 - error < x return [n + 1, 1] # The lower fraction is 0/1 lower_n = 0 lower_d = 1 # The upper fraction is 1/1 upper_n = 1 upper_d = 1 loop # The middle fraction is (lower_n + upper_n) / (lower_d + upper_d) middle_n = lower_n + upper_n middle_d = lower_d + upper_d # If x + error < middle if middle_d * (x + error) < middle_n # middle is our new upper upper_n = middle_n upper_d = middle_d # Else If middle < x - error else if middle_n < (x - error) * middle_d # middle is our new lower lower_n = middle_n lower_d = middle_d # Else middle is our best fraction else return [n * middle_d + middle_n, middle_d]