Skip to content

Instantly share code, notes, and snippets.

@xixixao
Created February 14, 2014 17:54
Show Gist options
  • Save xixixao/9005731 to your computer and use it in GitHub Desktop.
Save xixixao/9005731 to your computer and use it in GitHub Desktop.
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<sub>#{i}</sub>" for i in [1...matrix[0].length - 1]).join '\t'
I = ["z"].concat I
head += "<br>" + ((for row, i in matrix
I[i] + "\t" + (toSimpleFraction el for el in row).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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment