Instantly share code, notes, and snippets.

# xixixao/-

Created February 14, 2014 17:54
Star You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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] ] 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] step = (matrix, I) -> [objective, basics...] = matrix [value, newBasic] = max objective if value <= 0 return [value, newNonBasicI] = min (row[row.length - 1] / row[newBasic] for row in basics) 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) -> for i in [0...limit] res = step matrix, I break unless res printTableau [matrix, I] = res printTableau = ([matrix, I]) -> head = "\tz\t" + ("x#{i}" for i in [1...matrix.length - 1]).join '\t' I = ["z"].concat I head += "
" + ((for row, i in matrix I[i] + "\t" + (toSimpleFraction el for el in row).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]