index.html

<!DOCTYPE html>
<meta charset="utf-8">

<body>
    Please write a linear program in canonical form:<br />
    <textarea oninput="compute()" id="input" rows="10" cols="40"></textarea>
    <input id="bland" type="checkbox" oninput="compute()"></input>
    <label for="bland"
        title="if checked, apply Bland's rule which selects the first variable in the variable list / otherwise, selects the variable in the objective with the greatest coefficient">Bland's
        rule </label>
    <div id="error"></div>
    <div id="output"></div>

    <style>
        canvas {
            width: 160px;
            height: 120px;
        }

        body {
            vertical-align: top;
            background-color: black;
            color: lightyellow;
        }

        #error {
            color: red;
        }

        #output {
            border: 0px;
        }

        textarea {
            background-color: black;
            color: greenyellow;
        }

        body {
            background-color: black;
        }

        .max {
            font-weight: bold;
            margin-right: 8px;
        }

        .nonbasicvariable {
            color: lightgray;
        }

        .basicvariable {
            color: lightskyblue;
        }


        .pivot {
            margin: 8px;
            padding-left: 16px;
        }

        .obj {
            background-color: darkgreen;
            padding: 2px;
        }


        .tableau {
            margin: 8px;
            padding: 8px;
            background-color: rgb(60, 60, 60);
            display: inline-block;
            border-radius: 8px;
            vertical-align: top;
        }
    </style>

    <script>
        const SLACKVARIABLEPREFIX = "ε";
        /**
         * @description represents a Tableau in the simplex algorithm
         **/
        class Tableau {

            /**
             * v is the current value of the objective
             * c are the coefficients on the objective (as a JS object dictionnary var |-> value)
             * A the matrix (as a JS object of JS objects)
             * b the column vector (as a JS object)
             **/
            constructor(v, c, A, b) {
                this.v = v;
                this.c = c;
                this.A = A;
                this.b = b;

                const varsN = new Set([...Object.keys(c)]);

                for (const vB in A)
                    for (const vN in A[vB])
                        varsN.add(vN);

                const varsB = new Set([...Object.keys(A)]);

                for (const vB in A)
                    for (const vN of varsN) {
                        if (A[vB][vN] == undefined)
                            A[vB][vN] = 0;
                    }

                for (const vN of varsN) if (c[vN] == undefined) c[vN] = 0;

                this.varsB = varsB;
                this.varsN = varsN;
            }

            /**
             * @returns a textual representation of the tableau
             * */
            toString() {
                let s = "max " + ((this.v == 0) ? "" : (numberToStr(this.v) + " + ")) + mapToStr(this.c);
                for (let v in this.b) {
                    s += "\n" + v + " = " + numberToStr(this.b[v]) + " + " + mapToStr(this.A[v]);
                }
                s = s.replaceAll(" + -", " - ");
                // s += "\n\n" + "variables in the base: " + [...T.varsB] + "\n" + "variables outside the base: " + [...T.varsN] + "\n\n    ---------------    \n";
                return s;
            }


            /**
             * @parameters an array of variable names
             * @return an array with the values (if the variable is in the base, the value is taken from this.b[v], otherwise it is 0)
             * */
            evalVars(vars) { return vars.map((v) => this.b[v] ? this.b[v] : 0); }

            /**
             * @returns an HTML element representing the tableau
             * */
            toHTMLElement() {
                const el = document.createElement("div");
                let s = "<div class='tableau'><span class='max'>max</span>" + "<span class='obj'>" + numberToStr(this.v) + "</span> + "
                    + mapToHTML(this.c) + "<br/>";
                for (let v in this.b) {
                    s += "\n" + `<span class="basicvariable">${v}</span>` + " = " + numberToStr(this.b[v]) + " + " + mapToHTML(this.A[v]) + "<br/>";
                }
                s = s.replaceAll(" + -", " - ");
                s = s + "</div>";
                el.innerHTML = s;
                return el;
            }

            /**
             * @returns true iff the tableau has a basic solution
             * */
            get hasBasicSolution() {
                for (const v in this.b) {
                    if (this.b[v] < 0)
                        return false;
                }
                return true;

            }


        }


        function numberToStr(x) {
            return +parseFloat(x).toFixed(2);
        }

        /**
         * @parameter c an object for instance c = {x:1, y:-3, z:2} 
         * @returns a string representing the coefficients c
         * @example returns x + -3y + 2z if c = {x:1, y:-3, z:2} 
         * **/
        function mapToStr(c) {
            const A = [];
            for (let v in c) if (c[v] != 0) {
                A.push((
                    (c[v] == 1) ? "" : (c[v] == -1) ? "-" : numberToStr(c[v])) + v);
            }
            return A.join(" + ");
        }


        /**
         * @parameter c an object for instance c = {x:1, y:-3, z:2} 
         * @returns a string representing the coefficients c
         * @example returns x + -3y + 2z if c = {x:1, y:-3, z:2} 
         * **/
        function mapToHTML(c) {
            const A = [];
            for (let v in c) if (c[v] != 0) {
                A.push((
                    (c[v] == 1) ? "" : (c[v] == -1) ? "-" : numberToStr(c[v])) + `<span class="nonbasicvariable">${v}</span>`);
            }
            return A.join(" + ");
        }

        /**
         * @parameter line is a string, e.g. x - 3y + 2z
         * @returns a object {x:1, y:-3, z:2} 
         **/
        function lineToMap(line) {
            const lineCorrected1 = line.replaceAll("-", "+-");
            const lineCorrected = lineCorrected1.startsWith("+-") ? lineCorrected1.substr(1) : lineCorrected1;
            const termsStr = lineCorrected.split("+");
            const c = {};

            /**
             * @parameter a string for instance "2x"
             * @returns an array [coeff, variableName], e.g. [2, "x"]
             **/
            function splitTerm(termStr) {
                termStr = termStr.trim();

                let i;
                for (i = 0; i < termStr.length; i++)
                    if (["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", ".", "-", " ", "+"].indexOf(termStr[i]) < 0)
                        break;

                let numberStr = termStr.substr(0, i).trim();
                if (numberStr == "")
                    numberStr = "1";
                if (numberStr == "-")
                    numberStr = "-1";

                const coeff = parseFloatStrong(numberStr);
                if (coeff == undefined)
                    throw "the coefficient " + numberStr + " is not correct";
                const variablePart = termStr.substr(i).trimLeft();

                const variableName = (variablePart.startsWith("*")) ? variablePart.substr(1).trimLeft() : variablePart;

                if (variableName.indexOf(" ") >= 0)
                    throw "there are misplaced spaces in the term " + termStr;

                if (variableName == "")
                    throw "a variable name is missing";

                if (variableName.search(/^[a-zA-Z]?[a-zA-Z0-9]*$/) < 0)
                    throw "Problem with " + variableName + ": a variable name should start with a letter and can be followed by letters and/or digits";

                return [coeff, variableName];

            }

            for (const termStr of termsStr)
                if (termStr.trim() != "") {
                    const [val, varName] = splitTerm(termStr);

                    if (c[varName] != undefined)
                        throw "variable " + varName + " appears several times";
                    c[varName] = val;
                }
                else
                    throw " a term like 2x, -3y or something is missing";

            return c;
        }

        /**
         * @paramter a string representing a tableau for instance "max 2x \n x + y <= 5 \n x <= 6"
         * @returns The corresponding Tableau object
         **/
        function strToTableau(strCanonicalForm) {
            const lines = strCanonicalForm.split("\n");
            const objStr = lines.shift().trim();
            if (!objStr.toLowerCase().startsWith("max "))
                throw "error: the first line should start with 'max' followed by the objective function";
            const obj = lineToMap(objStr.substr(4));

            const A = {};
            const b = {};
            let i = 1;
            for (const line of lines) if (line.trim() != "") {
                const D = line.split("<=");
                if (D.length != 2)
                    throw "Each constraint should be of the form 'linear function <= value'";

                const coeffs = lineToMap(D[0]);

                for (const v in coeffs)
                    coeffs[v] = - coeffs[v];

                const bc = parseFloatStrong(D[1].trim());
                if (bc == undefined)
                    throw `The value in 'linear function <= value' should be a number. Sorry but ${D[1]} is not a number`;
                A[SLACKVARIABLEPREFIX + i] = coeffs;
                b[SLACKVARIABLEPREFIX + i] = bc;
                i++;
            }

            return new Tableau(0, obj, A, b);
        }


        function parseFloatStrong(str) {
            str = str.trim();
            const re = new RegExp(/^[+-]?\s*\d+(\.\d+)?$/);
            if (str.search(re) == -1)
                return undefined;
            str = str.replaceAll(" ", "").trim();
            const bc = parseFloat(str);
            return bc;
        }


        const WIDTH = 320;
        const HEIGHT = 240;


        /**
         * represents the polyhedron, i.e. the graph where the nodes are the tableau and edges are pivots
         * */
        class Polyhedron {
            constructor(initialTableau) {
                this.physicalVars = Array.from(initialTableau.varsN);
                this.vertices = {};
                this.edges = [];
                this.maxValue = 0;
                const LIMIT = 100;
                let i = 0;
                const L = [];
                L.push(initialTableau);
                while (L.length > 0) {
                    if (i > LIMIT) return;
                    i++;

                    const T = L.pop();

                    const values = T.evalVars(this.physicalVars);
                    this.maxValue = Math.max(this.maxValue, ...values);

                    if (this.vertices[T.toString()] == undefined) {
                        this.vertices[T.toString()] = T;
                        for (let j of Object.keys(T.c)) {
                            for (let i of getAllLeavingVariables(T, j)) {
                                let T2 = applyPivot(T, j, i);
                                this.edges.push([T, T2]);
                                L.push(T2);
                            }
                        }
                    }
                }
            }

            /**
             * @parameter ctx a Canvas context
             * @parameter T a tableau (or undefined)
             * @description draw the polyhedron + a point for the vertex associated with T (or nothing is T == undefined)
             * */
            draw(ctx, T) {
                const directions = [{ x: 1, y: 0 }, { x: 0, y: 1 }, { x: 0.5, y: 0.2 }, { x: 0.3, y: 0.5 }];
                /**
                 * @parameter p an array of p.length numbers that represents a point in the space in p.length dimension
                 * @returns a two 2D point {x, y} that is the projection of p
                 **/
                function to2D(p) {
                    if (p[2] == undefined) p[2] = 0;

                    let x = 0;
                    let y = 0;

                    for (let i = 0; i < p.length; i++) {
                        x += p[i] * directions[i % 4].x;
                        y -= p[i] * directions[i % 4].y;
                    }
                    return { x, y };
                }

                ctx.clearRect(0, 0, WIDTH, HEIGHT);
                ctx.save();
                ctx.translate(32, HEIGHT - 32);
                const scaleFactor = 150 / this.maxValue;
                ctx.scale(scaleFactor, scaleFactor);
                ctx.lineWidth = 0.8 / scaleFactor;
                ctx.strokeStyle = "white";
                for (const [T, T2] of this.edges) {
                    const p = T.evalVars(this.physicalVars);
                    const p2 = T2.evalVars(this.physicalVars);
                    const p2D = to2D(p);
                    const p22D = to2D(p2);

                    ctx.beginPath();
                    ctx.moveTo(p2D.x, p2D.y);
                    ctx.lineTo(p22D.x, p22D.y);
                    ctx.stroke();
                }

                if (T) {
                    const p = T.evalVars(this.physicalVars);
                    const p2D = to2D(p);
                    ctx.beginPath();
                    ctx.fillStyle = "lightgreen";
                    ctx.arc(p2D.x, p2D.y, 7 / scaleFactor, 0, Math.PI * 2);
                    ctx.fill();
                }
                ctx.restore();
            }

        }


        function compute() {
            let T = undefined;
            let polyhedron = undefined;


            function createHTMLElementForTableau(T) {
                const el = T.toHTMLElement();
                el.prepend(createCanvasPolyhedron(T));
                return el;
            }
            function init() {
                const initialTableau = strToTableau(input.value);
                T = initialTableau;
                polyhedron = new Polyhedron(T);

                if (!T.hasBasicSolution) {
                    throw "the initial tableau has no basic solution";
                }


                output.appendChild(createHTMLElementForTableau(initialTableau));
            }


            function step() {
                const pivotFunction = document.getElementById("bland").checked ? blandRule : biggestCoeffRule;
                const { j, i } = pivotFunction(T);
                T = applyPivot(T, j, i);

                const elPivot = document.createElement("div");
                elPivot.innerHTML = `<div class="pivot"><span class="basicvariable">${j}</span> ← <span class="nonbasicvariable">${j}</span><br/>` +
                    `<span class="basicvariable">${i}</span> → <span class="nonbasicvariable">${i}</span><br/></div>`;

                output.appendChild(elPivot);
                output.appendChild(createHTMLElementForTableau(T));

            }


            function createCanvasPolyhedron(T) {
                const canvas = document.createElement("canvas");
                canvas.width = WIDTH;
                canvas.height = HEIGHT;
                polyhedron.draw(canvas.getContext("2d"), T);
                return canvas;
            }

            noError();
            output.innerHTML = "";

            try {
                if (input.value.trim() == "")
                    throw "write a linear program, for instance <br/> max x+y <br/> x + 2y <= 3<br> x -y <= 5";
                init();
            }
            catch (e) {
                showError(e);
                return;
            }
            try {
                const LIMIT = 50;
                for (let i = 0; i < LIMIT; i++)
                    step();

            }
            catch (e) {
                const el = document.createElement("div");
                el.innerHTML = e;
                output.appendChild(el);
            }
        }


        function chooseEnteringVariableBiggestCoeff(T) {
            let j = undefined;
            let max = 0;
            for (let v in T.c)
                if (T.c[v] > max) {
                    j = v;
                    max = T.c[v];
                }
            return j;
        }


        function chooseEnteringVariableSmallestSubscript(T) {
            for (let v of Object.keys(T.c).sort()) if (T.c[v] > 0)
                return v;
            return undefined;
        }

        function chooseLeavingVariableSmallestSubscript(T, j) {
            let min = Infinity;
            let vI = undefined
            // in order to have the smallest index, we reverse the array of keys
            for (let i of Object.keys(T.A).reverse()) if (T.A[i][j] < 0 && -T.b[i] / T.A[i][j] < min) {
                vI = i;
                min = -T.b[i] / T.A[i][j];
            }
            return vI;
        }


        function getAllLeavingVariables(T, j) {
            let min = Infinity;
            let varsLeaving = [];
            for (let i in T.A) if (T.A[i][j] < 0 && -T.b[i] / T.A[i][j] < min)
                min = -T.b[i] / T.A[i][j];

            for (let i in T.A) if (min == -T.b[i] / T.A[i][j])
                varsLeaving.push(i);

            return varsLeaving;
        }

        /**
         * @parameter a Tableau object
         * @returns an object {i: variableNameI, j: variableNameJ} 
         * where variableNameI and variableNameJ are the variables used to perform the pivot 
         **/
        function blandRule(T) {
            const j = chooseEnteringVariableSmallestSubscript(T);
            if (j == undefined) throw "We found the max!";

            const i = chooseLeavingVariableSmallestSubscript(T, j);
            if (i == undefined) throw "unbounded because of variable " + j;

            return { i, j };
        }


        /**
         * same typing than Bland rule
         **/
        function biggestCoeffRule(T) {
            const j = chooseEnteringVariableBiggestCoeff(T);
            if (j == undefined) throw "We found the max!";

            const i = chooseLeavingVariableSmallestSubscript(T, j);

            if (i == undefined) throw "unbounded because of variable " + j;

            return { i, j };
        }


        /**
         * @parameter T a tableau
         * @parameter j0
         * @parameter i0
         * @returns the tableau obtained from T by applying the pivot according to i0 and j0
         **/
        function applyPivot(T, j0, i0) {

            const v = T.v - T.b[i0] * T.c[j0] / T.A[i0][j0];
            const c = {};

            for (const j of T.varsN) if (j != j0)
                c[j] = T.c[j] - T.c[j0] * T.A[i0][j] / T.A[i0][j0];

            c[i0] = T.c[j0] / T.A[i0][j0];
            const b = {};

            for (const i of T.varsB) if (i != i0)
                b[i] = T.b[i] - T.A[i][j0] * T.b[i0] / T.A[i0][j0];

            b[j0] = -T.b[i0] / T.A[i0][j0];

            const A = {};

            for (const i of T.varsB) if (i != i0) {
                A[i] = {};
                for (const j in T.c) if (j != j0)
                    A[i][j] = T.A[i][j] - T.A[i][j0] * T.A[i0][j] / T.A[i0][j0];

                A[i][i0] = T.A[i][j0] / T.A[i0][j0];
            }

            A[j0] = {};
            A[j0][i0] = 1 / T.A[i0][j0];

            for (const j of T.varsN) if (j != j0)
                A[j0][j] = -T.A[i0][j] / T.A[i0][j0];

            return new Tableau(v, c, A, b);
        }

        function showError(msg) { document.getElementById("error").innerHTML = msg; }
        function noError() { document.getElementById("error").innerHTML = ""; }

        compute();
    </script>