Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | 63x 63x 796x 796x 796x 123x 123x 123x 123x 123x 123x 1395x 1395x 1395x 1395x 123x 123x 123x 123x 123x 887x 887x 13106x 13106x 10273x 13106x 82199x 51556x 51556x 82199x 10273x 887x 6646x 6646x 6646x 887x 13106x 13106x 13106x 887x 887x 887x 123x 230x 230x 996x 996x 6380x 6380x 6380x 6380x 6380x 996x 996x 767x 996x 9944x 9944x 9944x 9944x 9944x 9944x 767x 996x 766x 766x 230x 123x 123x 1395x 1395x 1395x 123x 121x 121x 121x 107x 121x 121x 109x 123x 108x 108x 123x 1195x 108x 123x 796x 63x | 'use strict';
module.exports = ({ numeric: { rational: { zero, one, neg, sub, mul, div, cmp } } }) => {
// Two-phase simplex over exact rational numbers. Variables are nonnegative;
// each constraint is coefficients * x <= bound. Bland's rule prevents cycling.
function maximize(variableCount, constraints, objective) {
const m = constraints.length;
const n = variableCount;
const basic = Array.from({ length: m }, (_, i) => n + i);
const nonbasic = Array.from({ length: n + 1 }, (_, i) => i === n ? -1 : i);
const table = Array.from({ length: m + 2 }, () => Array(n + 2).fill(zero));
constraints.forEach(({ coefficients, bound }, i) => {
for (const [j, value] of coefficients)
table[i][j] = value;
table[i][n] = neg(one);
table[i][n + 1] = bound;
});
for (const [j, value] of objective)
table[m][j] = neg(value);
table[m + 1][n] = one;
function pivot(row, column) {
const inverse = div(one, table[row][column]);
for (let i = 0; i < m + 2; i++) {
if (i === row || !table[i][column].n)
continue;
const factor = mul(table[i][column], inverse);
for (let j = 0; j < n + 2; j++) {
if (j !== column && table[row][j].n) {
table[i][j] = sub(table[i][j], mul(table[row][j], factor));
}
}
}
for (let j = 0; j < n + 2; j++) {
if (j !== column)
table[row][j] = mul(table[row][j], inverse);
}
for (let i = 0; i < m + 2; i++) {
if (i !== row)
table[i][column] = mul(table[i][column], neg(inverse));
}
table[row][column] = inverse;
[basic[row], nonbasic[column]] = [nonbasic[column], basic[row]];
}
function simplex(phase) {
const objectiveRow = phase === 1 ? m + 1 : m;
for (;;) {
let column = -1;
for (let j = 0; j <= n; j++) {
if ((phase === 2 && nonbasic[j] === -1) || table[objectiveRow][j].n >= 0n)
continue;
if (column === -1 || nonbasic[j] < nonbasic[column])
column = j;
}
if (column === -1)
return true;
let row = -1;
for (let i = 0; i < m; i++) {
if (table[i][column].n <= 0n)
continue;
const comparison = row === -1 ? -1 : cmp(div(table[i][n + 1], table[i][column]), div(table[row][n + 1], table[row][column]));
if (comparison < 0 || (comparison === 0 && basic[i] < basic[row]))
row = i;
}
if (row === -1)
return false;
pivot(row, column);
}
}
let row = -1;
for (let i = 0; i < m; i++) {
if (row === -1 || cmp(table[i][n + 1], table[row][n + 1]) < 0)
row = i;
}
if (row !== -1 && table[row][n + 1].n < 0n) {
pivot(row, n);
if (!simplex(1) || table[m + 1][n + 1].n !== 0n)
return { status: 'infeasible' };
row = basic.indexOf(-1);
if (row !== -1) {
let column = -1;
for (let j = 0; j <= n; j++) {
if (table[row][j].n && (column === -1 || nonbasic[j] < nonbasic[column]))
column = j;
}
if (column !== -1)
pivot(row, column);
}
}
if (!simplex(2))
return { status: 'unbounded' };
const solution = Array(n).fill(zero);
for (let i = 0; i < m; i++)
if (basic[i] < n && basic[i] >= 0)
solution[basic[i]] = table[i][n + 1];
return { status: 'optimal', value: table[m][n + 1], solution };
}
return { maximize };
};
|