OR operations

Simplex Algorithm.coffee

#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<sub>#{i}</sub>" for i in [1...matrix[0].length - 1]).join '\t'
  head += "\tRHS"
  I = ["z"].concat I
  head += "<br>" + ((for row, i in matrix
    I[i] + "\t" + (el for el in row[1..]).join '\t'
  ).join '<br>') + "<br><br>"
      
    
  
  
  
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]