Arrière plan

En cours de mathématiques d'algèbre, nous avons tous rencontré un sujet appelé programmation linéaire. C'est une technique mathématique pour trouver la valeur de chaque variable dans un problème qui a autant d'équations que le nombre de variables recherchées. Par exemple:

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

1. Faire en sorte que les deux équations aient une variable avec le même coefficient, par exemple entre 1*aet0.1*a
2. Ensuite, dans la deuxième équation, tout est multiplié par 10 pour qu'il devienne1*a + 6*b = 150
3. Parce a + b = 50qu'alors a = 50 — b, et a + 6b = 150puisa = 150–6b
4. Alors 50 - b = 150 – 6bpuis 6b — b = 150 – 50, ou 5b = 100, et enfinb = 20
5. Parce qu'on sait que b = 20, alors a + 20 = 50, signifiea = 30

Méthode

Pour être honnête, j'ai essayé diverses fonctions mathématiques qui me permettent de résoudre des problèmes de programmation linéaire avec jusqu'à 3 variables (3²) et d'obtenir le code comme suit (première version):

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]

Encore une fois, j'ai eu une impasse parce que je ne pouvais pas ajuster le code ci-dessus pour accueillir N variables avec différentes grandeurs. Mais au milieu de l'impasse, je peux voir qu'il y a un modèle qui s'applique à la méthode d'élimination, c'est la récursivité.

Chaque fois que nous essayons d'éliminer une variable qui se trouve sur le côté droit d'une matrice, nous essaierons de prendre l'équation adjacente et d'égaliser les deux équations jusqu'à ce que les coefficients des variables que nous voulons éliminer soient équilibrés. La façon dont je le fais ici est de former le nombre du plus grand facteur commun (GCF), ou de multiplier les deux coefficients différents sur la même variable, puis ce nombre devient une référence pour multiplier chaque équation par la différence de division par GCF.

Une fois les deux équations multipliées par un nombre qui rend le coefficient d'une variable identique dans les deux équations, l'ordinateur recherche la différence de réduction entre les deux variables et renvoie une nouvelle série, qui est le résultat de la soustraction des 2 équations plus tôt. Bien sûr dans cette nouvelle équation il y aura une variable avec un coefficient de 0 car elle a été réduite, c'est ce que j'entends par élimination. Ensuite, l'ordinateur est invité à répéter le processus sur d'autres paires d'équations pour produire une nouvelle série des mêmes résultats d'élimination de variables.

La fin du processus d'élimination d'une variable se poursuivra jusqu'à ce que le nombre de variables continue de diminuer et qu'il ne reste plus que 1 côte à côte avec la bonne valeur finale qui est la somme des variables restantes. C'est là que la fonction se termine et renvoie la valeur de cette 1 variable.

L'ordinateur n'utilise pas les valeurs obtenues pour être transmises comme matériau à l'itération suivante, mais crée uniquement une nouvelle matrice dont la composition variable est modifiée en déplaçant les variables à côté vers la droite pour subir le processus d'élimination comme dans les variables précédentes . En conséquence, le code que j'ai conçu peut accepter des problèmes de programmation linéaire de n'importe quelle taille de variables (N) et générera une série de nombres aussi longue que la valeur N.

Résultat

Voici le code final pour trouver la réponse à un problème de programmation linéaire avec n'importe quelles variables N :

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]
)

Plongée profonde

Pour ceux qui sont curieux de savoir comment ce code fonctionne ligne par ligne, voici l'explication :

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]
)

Je n'aurais jamais pensé pouvoir créer une fonction comme celle-ci. Chaque essai et erreur me déprime et je ne sais pas si cette fonction peut exister. Après une courte pause et en demandant de l'aide à Dieu, je suis retourné au codage et cela a fonctionné. Je ne sais pas si cette création deviendra virale ou sera utile à beaucoup de gens dans le futur. La clé à retenir est que ce code prouve que tout ce que nous voulons, nous pouvons le faire.

Mise à jour!!

Plus tôt, nous avons expliqué comment la fonction ci-dessus peut théoriquement résoudre des problèmes de programmation linéaire avec n'importe quel nombre. Je suis tellement curieux, que se passe-t-il si je crée une autre fonction qui peut créer des problèmes de programmation linéaire avec N variables, qui peuvent ensuite être utilisées pour tester la robustesse de la fonction précédente. Créons :

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!
*/

randomizeest une fonction qui, lorsqu'on lui donne un nombre, renverra un nombre aléatoire à N chiffres comme demandé. Rien d'extraordinaire ici.

troubleMakerest une fonction qui, lorsqu'on lui donne un nombre de variables voulues à l'intérieur de la matrice, créera une matrice avec N lignes et N+1 colonnes où le +1 est la somme de chaque variable multipliée par les coefficients correspondants. Jetez un œil ci-dessous pour savoir comment fonctionne la fonction.

Comme présenté ci-dessus, la fonction de réponse n'a eu aucun mal à résoudre le problème de programmation linéaire avec 3 variables et a correctement donné la bonne réponse. J'ai continué à expérimenter en augmentant les variables N jusqu'à 7, et quelque chose d'étrange se produit lorsque je suis allé au-delà :

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
]*/

Pour votre information, voici l'environnement avec lequel je travaille : Intel Celeron 1007U, 4 Go de RAM, 256 Go de SSD, système d'exploitation élémentaire, Node 18+ et le dernier Google Chrome. Si le problème était lié au matériel, vous pourriez trouver d'autres circonstances sur un autre système. Essaye.