Fundo

Na aula de álgebra matemática, todos nós nos deparamos com um tópico chamado programação linear. É uma técnica matemática para encontrar o valor de cada variável em um problema que possui tantas equações quanto o número de variáveis ​​que estão sendo procuradas. Como um exemplo:

a +    b = 50
0.1a + 0.6b = 15

1. Faça com que as duas equações tenham uma variável com o mesmo coeficiente, por exemplo entre 1*ae0.1*a
2. Então, na segunda equação, tudo é multiplicado por 10 para que se torne1*a + 6*b = 150
3. Porque a + b = 50então a = 50 — b, e a + 6b = 150entãoa = 150–6b
4. Então 50 - b = 150 – 6bentão 6b — b = 150 – 50, ou 5b = 100, e finalmenteb = 20
5. Porque sabe-se que b = 20, então a + 20 = 50, significaa = 30

Método

Para ser honesto, tentei várias funções matemáticas que me permitem resolver problemas de programação linear com até 3 variáveis ​​(3²) e obter o código como o seguinte (versão inicial):

withAs = (obj, cb) => cb(obj)
// just a callback function

makeArray = num => [...Array(num).keys()]
// make a new array with num length

last = arr => arr.slice(-1)[0]
// get the last element of given array

elim = arr => arr.slice(-2)[0]
// a function to get the second element from right

rmndr = arr => arr.filter(Boolean)
// take everything except 0

blncr = (eq1, eq2) => withAs(
  elim(eq1) * elim(eq2), fct => withAs([
    eq1.map(i => i * fct / elim(eq1)),
    eq2.map(i => i * fct / elim(eq2))
  ], bln => makeArray(eq1.length).map(
    k => bln[0][k] - bln[1][k]
  ))
)
// a function to get an array of difference
// betwen both equation

eqlzr = (eq1, eq2, eq3) => withAs({
// receive 3 equations, only 3
  eq4: rmndr(blncr(eq1, eq2)),
  eq5: rmndr(blncr(eq2, eq3))
// results of previous steps
}, ({eq4, eq5}) => withAs(
  rmndr(blncr(eq4, eq5)), eq6 =>
    withAs(eq6[1] / eq6[0], x =>
      withAs(-(last(eq5) - eq5[0] * x), y =>
        withAs(
          (last(eq1) - (eq1[0] * x + eq1[1] * y))
          / elim(eq1), z => [x, y, z]
        )
      )
    )
    // do as the manual method would
))

console.log(eqlzr(
  [5, -2, -4,  3],
  [3,  3,  2, -3],
  [-2, 5,  3,  3]
)) // get [-1, 2, -3]

Novamente, tive um impasse porque não consegui ajustar o código acima para acomodar N variáveis ​​com várias magnitudes. Mas em meio ao impasse, vejo que existe um padrão que se aplica ao método de eliminação, é a recursão.

Cada vez que tentarmos eliminar uma variável que está do lado direito de uma matriz, tentaremos pegar a equação adjacente e igualar as duas equações até que os coeficientes das variáveis ​​que queremos eliminar estejam equilibrados. A forma que faço aqui é formar o número do Máximo Fator Comum (GCF), ou multiplicar os dois coeficientes diferentes na mesma variável e então esse número se torna uma referência para multiplicar cada equação pela diferença na divisão por GCF.

Depois que as duas equações são multiplicadas por um número que torna o coeficiente de uma variável igual em ambas as equações, o computador procura a diferença de redução entre as duas variáveis ​​e retorna uma nova série, que é o resultado da subtração das 2 equações mais cedo. Claro que nessa nova equação vai ter uma variável com coeficiente 0 porque foi reduzida, é isso que quero dizer com eliminação. Em seguida, o computador é solicitado a repetir o processo em outros pares de equações para produzir uma nova série dos mesmos resultados de eliminação de variáveis.

O fim do processo de eliminação de uma variável continuará até que o número de variáveis ​​continue a diminuir e apenas 1 permaneça lado a lado com o valor final direito que é a soma das variáveis ​​restantes. É aqui que a função termina e retorna o valor dessa 1 variável.

O computador não utiliza os valores obtidos para serem passados ​​como material na próxima iteração, mas apenas cria uma nova matriz cuja composição variável é alterada deslocando as variáveis ​​próximas a ela para a direita para passar pelo processo de eliminação como nas variáveis ​​anteriores . Como resultado, o código que desenhei pode aceitar problemas de programação linear de qualquer tamanho de variável (N) e irá gerar uma série de números tão longos quanto o valor de N.

Resultado

Este é o código final para encontrar a resposta para um problema de programação linear com quaisquer N variáveis:

withAs = (obj, cb) => cb(obj)
makeArray = num => [...Array(num).keys()]
elim = (arr, n = 0) => arr.slice(-2-n)[0]
rest = (arr, n = 0) => arr.filter(
  (i, j) => j !== arr.length - 2 - n
)

gcf = (eq1, eq2) => elim(eq1) * elim(eq2)
multi = (eq1, eq2) => [
  eq1.map(i => i * gcf(eq1, eq2) / elim(eq1)),
  eq2.map(i => i * gcf(eq1, eq2) / elim(eq2))
]

diff = (eq1, eq2) => rest(
  makeArray(eq1.length).map(i =>
    multi(eq1, eq2)[0][i] -
    multi(eq1, eq2)[1][i]
  )
)

reduce = mat =>
  mat.length === 1 ? [] : [
    diff(mat[0], mat[1]),
    ...reduce(mat.slice(1-mat.length))
  ]

solve = mat =>
  mat[0].length === 2 ?
  mat[0][1] / mat[0][0]
  : solve(reduce(mat))

swap = (arr, n) => [elim(arr, n), ...rest(arr, n)]

answer = mat =>
  mat.length >= mat[0].length - 1 &&
  makeArray(mat[0].length - 1).map(
    i => mat.map(j => swap(j, i))
  ).map(solve).reverse()

console.log(
  answer([
    [1, 1, 50],
    [0.1, 0.6, 15]
  ]), // get [30, 20]
  answer([
    [5,-2,-4, 3],
    [3, 3, 2,-3],
    [-2,5, 3, 3],
  ]), // get [-1, 2, -3]
  answer([
    [5, 7, 9, -1, 67],
    [1, 9, 6, -5, 3],
    [-5, -6, 1, -2, -33],
    [-7, -4, -5, -1, -64],
  ]), // get [3, 1, 6, 9]
)

Mergulho profundo

Para quem tem curiosidade de como funciona esse código linha por linha, segue a explicação:

withAs = (obj, cb) => cb(obj)
// just a callback function

makeArray = num => [...Array(num).keys()]
// function to make an array with N length

elim = (arr, n = 0) => arr.slice(-2-n)[0]
// function to get a number which shall be eliminated
//                     ^ always get the second number from right
//           ^ allow to get other position

rest = (arr, n = 0) => arr.filter(
  (i, j) => j !== arr.length - 2 - n
)
// a function to get the rest of the numbers
// which doesn't contain the eliminated number

gcf = (eq1, eq2) => elim(eq1) * elim(eq2)
// abbreviation of Greatest Common Factor
// multiplication of both coefficients of the same variable

multi = (eq1, eq2) => [
// multiply each number according to
// it's difference from GCF value
  eq1.map(i => i * gcf(eq1, eq2) / elim(eq1)),
  eq2.map(i => i * gcf(eq1, eq2) / elim(eq2))
]

diff = (eq1, eq2) => rest(
// calculate the difference of each variables
// and create a new array based on that
  makeArray(eq1.length).map(i =>
    multi(eq1, eq2)[0][i] -
    multi(eq1, eq2)[1][i]
  )
)

reduce = mat =>
// receive a matrix of equations
  mat.length === 1 ? [] : [
// if the leftover contain only 1 Eq
// then give an empty array
    diff(mat[0], mat[1]),
//  find difference of adjacent equations
    ...reduce(mat.slice(1-mat.length))
//  recursively repeat this process
//  to the rest of the equations
  ]

solve = mat =>
// receiva a matrix of equations
  mat[0].length === 2 ?
// if the remaining variable is 1
// then divide the summation to it's coefficient
  mat[0][1] / mat[0][0]
  : solve(reduce(mat))
//  recursively repeat the process
//  until the value of 1 variable found

swap = (arr, n) => [elim(arr, n), ...rest(arr, n)]
// receive an array and shift the position 
// of a column to the first position

answer = mat =>
// receive a matrix of equations
  mat.length >= mat[0].length - 1 &&
// continue only when amount of equations
// equal or more than provided variables
  makeArray(mat[0].length - 1).map(
// make a set of matrixes with alternated
// shifting of variable positions
    i => mat.map(j => swap(j, i))
  ).map(solve).reverse()
// keep solving each matrix to find
// each variable value

console.log(
  answer([
    [1, 1, 50],
    [0.1, 0.6, 15]
  ]), // get [30, 20]
  answer([
    [5,-2,-4, 3],
    [3, 3, 2,-3],
    [-2,5, 3, 3],
  ]), // get [-1, 2, -3]
  answer([
    [5, 7, 9, -1, 67],
    [1, 9, 6, -5, 3],
    [-5, -6, 1, -2, -33],
    [-7, -4, -5, -1, -64],
  ]), // get [3, 1, 6, 9]
)

Eu nunca pensei que poderia criar uma função como esta. Cada tentativa e erro me deixa para baixo e não tenho certeza se essa função pode existir. Depois de uma pequena pausa, e pedindo ajuda a Deus, voltei a codificar e funcionou. Não sei se essa criação vai viralizar ou ser útil para muitas pessoas no futuro. A principal conclusão é que esse código prova que o que quisermos, podemos fazer.

Atualizar!!

Anteriormente discutimos como a função acima pode teoricamente resolver problemas de programação linear com qualquer número. Estou tão curioso, e se eu criar outra função que pode criar problemas de programação linear com N variáveis, que podem ser usadas posteriormente para testar a robustez da função anterior. Vamos criar:

sum = array => array.reduce((acc, inc) => acc + inc)

randomize = digits => x => Math.round(
  Math.random() * Math.pow(10, digits)
)

randomize(2)() // get 17
randomize(3)() // get 895

troubleMaker = num => withAs(
  makeArray(num).map(randomize(2)),
  ranVar => makeArray(num).map(i => withAs(
    makeArray(num).map(randomize(2)),
    mlt => [...mlt, sum(
      mlt.map((j, k) => j * ranVar[k])
    )]
  ))
)

genProb = troubleMaker(3)
console.log(genProb, answer(genProb))

/* get the result
generated problem = [
  [ 51, 22, 2, 3008 ],
  [ 10, 22, 74, 6262 ],
  [ 80, 19, 35, 5529 ]
]
answer found = [ 26, 71, 60 ] CORRECT!
*/

randomizeé uma função que, ao receber um número, retornará um número aleatório com N dígitos conforme solicitado. Nada extravagante aqui.

troubleMakeré uma função que ao receber um número de variáveis ​​desejado dentro da matriz, criará uma matriz com N linhas e N+1 colunas onde o +1 é a soma de cada variável multiplicada pelos coeficientes correspondentes. Veja abaixo como funciona a função.

Conforme apresentado acima, a função de resposta não teve problemas em resolver o problema de programação linear com 3 variáveis ​​e forneceu corretamente a resposta correta. Continuei experimentando aumentando as variáveis ​​N até o 7º, e algo estranho ocorreu quando fui além disso:

console.log(answer(troubleMaker(7)))
/* get the result
[
  67.99999999999986,
  78.99999999999993,
  70.0000000000002,
  38.0000000000001,
  2.000000000000014,
  58.99999999999992,
  84.00000000000006
]
*/

console.log(answer(troubleMaker(8)))
/* get the result
[
  NaN, NaN, NaN,
  NaN, NaN, NaN,
  NaN, NaN
]*/

console.log(answer(troubleMaker(9)))
/* get the result
[
  NaN, NaN, NaN,
  NaN, NaN, NaN,
  NaN, NaN
]*/

Para sua informação, este é o ambiente com o qual trabalho: Intel Celeron 1007U, 4 Gb RAM, 256 Gb SSD, Elementary OS, Node 18+ e o mais recente Google Chrome. Se o problema estiver relacionado ao hardware, você poderá encontrar outras circunstâncias em outro sistema. Tente.