Latar belakang

Di kelas matematika aljabar, kami semua menemukan topik yang disebut pemrograman linier. Ini adalah teknik matematika untuk menemukan nilai setiap variabel dalam suatu masalah yang memiliki persamaan sebanyak jumlah variabel yang dicari. Sebagai contoh:

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

1. Jadikan kedua persamaan memiliki satu variabel dengan koefisien yang sama, misalnya antara 1*adan0.1*a
2. Kemudian pada persamaan kedua semuanya dikalikan 10 sehingga menjadi1*a + 6*b = 150
3. Karena a + b = 50kemudian a = 50 — b, dan a + 6b = 150kemudiana = 150–6b
4. Kemudian 50 - b = 150 – 6bkemudian 6b — b = 150 – 50, atau 5b = 100, dan akhirnyab = 20
5. Karena diketahui bahwa b = 20, maka a + 20 = 50, artinyaa = 30

metode

Sejujurnya, saya telah mencoba berbagai fungsi matematika yang memungkinkan saya untuk menyelesaikan masalah pemrograman linier hingga 3 variabel (3²) dan mendapatkan kode seperti berikut (versi awal):

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]

Sekali lagi, saya mengalami kebuntuan karena saya tidak dapat menyesuaikan kode di atas untuk mengakomodasi variabel N dengan berbagai besaran. Namun di tengah kebuntuan tersebut, saya dapat melihat bahwa ada pola yang berlaku pada metode eliminasi, yaitu rekursi.

Setiap kali kita mencoba menghilangkan variabel yang berada di ruas kanan matriks, kita akan mencoba mengambil persamaan yang berdekatan dan menyamakan kedua persamaan tersebut hingga koefisien dari variabel yang ingin kita hilangkan seimbang. Cara saya disini adalah dengan membentuk bilangan Faktor Persekutuan Terbesar (FPB), atau mengalikan dua koefisien yang berbeda pada variabel yang sama dan kemudian bilangan tersebut menjadi acuan untuk mengalikan setiap persamaan dengan selisih pembagian dengan FPB.

Setelah kedua persamaan tersebut dikalikan dengan suatu bilangan yang menjadikan koefisien suatu variabel sama pada kedua persamaan tersebut, selanjutnya komputer mencari selisih reduksi kedua variabel tersebut dan mengembalikan deret baru yang merupakan hasil pengurangan kedua persamaan tersebut. lebih awal. Tentu saja dalam persamaan baru ini akan ada variabel dengan koefisien 0 karena telah dikurangi, inilah yang saya maksud dengan eliminasi. Kemudian komputer diminta untuk mengulang proses tersebut pada pasangan persamaan yang lain untuk menghasilkan deret baru dari hasil eliminasi variabel yang sama.

Akhir dari proses penghilangan suatu variabel akan terus berlanjut hingga jumlah variabel terus berkurang dan tinggal 1 yang tersisa berdampingan dengan nilai ujung kanan yang merupakan penjumlahan dari variabel yang tersisa. Di sinilah fungsi berakhir dan mengembalikan nilai untuk 1 variabel itu.

Komputer tidak menggunakan nilai yang diperoleh untuk diteruskan sebagai bahan pada iterasi berikutnya, melainkan hanya membuat matriks baru yang komposisi variabelnya diubah dengan cara menggeser variabel di sebelahnya ke kanan untuk menjalani proses eliminasi seperti pada variabel sebelumnya. . Hasilnya, kode yang saya rancang dapat menerima masalah pemrograman linier ukuran variabel (N) berapa pun dan akan menghasilkan rangkaian angka sepanjang nilai N.

Hasil

Ini adalah kode terakhir untuk menemukan jawaban atas masalah pemrograman linier dengan N variabel apa pun:

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

Menyelam dalam

Bagi yang penasaran bagaimana kode ini bekerja baris demi baris, berikut penjelasannya:

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

Saya tidak pernah berpikir saya bisa membuat fungsi seperti ini. Setiap coba-coba membuat saya kecewa dan tidak yakin apakah fungsi ini bisa ada. Setelah istirahat sejenak, dan meminta bantuan Tuhan, saya kembali ke coding dan berhasil. Saya tidak tahu apakah kreasi ini akan menjadi viral atau bermanfaat bagi banyak orang di masa depan. Kuncinya adalah, kode ini membuktikan bahwa apapun yang kita inginkan, kita bisa membuatnya.

Memperbarui!!

Sebelumnya kita telah membahas bagaimana fungsi di atas secara teoritis dapat menyelesaikan masalah program linier dengan bilangan berapa pun. Saya sangat penasaran, bagaimana jika saya membuat fungsi lain yang dapat membuat masalah pemrograman linier dengan variabel N, yang nantinya dapat digunakan untuk menguji kekokohan fungsi sebelumnya. Mari kita buat:

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

randomizeadalah fungsi yang ketika diberi nomor, itu akan mengembalikan nomor acak dengan N digit seperti yang diminta. Tidak ada yang mewah di sini.

troubleMakeradalah suatu fungsi yang jika diberikan sejumlah variabel yang diinginkan di dalam matriks, maka akan terbentuk matriks dengan N baris dan N+1 kolom dimana +1 merupakan penjumlahan dari masing-masing variabel dikalikan dengan koefisien yang bersesuaian. Lihat di bawah untuk mengetahui cara kerjanya.

Seperti yang disajikan di atas, fungsi jawaban tidak mengalami kesulitan dalam menyelesaikan masalah program linier dengan 3 variabel dan menghasilkan jawaban yang tepat. Saya terus bereksperimen dengan meningkatkan variabel N hingga ke-7, dan sesuatu yang aneh terjadi ketika saya melampaui itu:

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

FYI, ini adalah lingkungan tempat saya bekerja: Intel Celeron 1007U, RAM 4Gb, SSD 256Gb, OS Dasar, Node 18+, dan Google Chrome terbaru. Jika masalahnya terkait dengan perangkat keras, Anda mungkin menemukan keadaan lain di sistem lain. Selamat mencoba.