// Numbas version: finer_feedback_settings {"name": "Canonical form", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Canonical form", "tags": [], "metadata": {"description": "

GIve a random linear program and ask the students to convert it to canonical form.

", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "

Convert the following linear programming problem to canonical form:

\n

\\[\\begin{gathered}
\\var{{optimise}}\\text{ } \\var{objective} \\text{ subject to }\\\\
\\var{system}
\\end{gathered}\\]

\n

\\[x_i≥0, \\forall\\in \\var{Jp}\\]

\n

\\[x_j≤0, \\forall j\\in \\var{Jn}\\]

\n

", "advice": "

In order to convert a problem to canonical form, we need to perform the following changes

\n
    \n
  1. The objective should be maximised.
  2. \n
  3. All variables should be positive.
  4. \n
  5. All constraints should be in the form ≤
  6. \n
\n

Maximised objective

\n

The objective is already being maximised, there is nothing to do here.

\n

The objective is being minimised, so we just multiply it by -1, and the new objective becomes $\\simplify{-{objective}}$.

\n

Changing the variables

\n

We change the variables as follows:

\n\n

The objective function becomes $\\var{objectivev}$ and the constraints become

\n

\\[\\var{systemv}\\]

\n

The constraints

\n

The constraints should be changed as follows:

\n
    \n
  1. Any constraint of the form \"≥\" is multiplied by -1 (both the right and left hand sides).
  2. \n
  3. Any equality constraint is replaced with two \"≤\" constraints, one of which has the same coefficients and the other one multiplied by -1.
  4. \n
\n

The canonical form of the problem is:

\n

\\[\\begin{gathered}
\\text{maximise } \\var{objectivev} \\text{ subject to }\\\\
\\var{systemc}\\\\
y_j\\geq 0, \\forall j=1…\\var{nvarcanonical}
\\end{gathered}\\]

", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true, "j": false}, "constants": [], "variables": {"nvar": {"name": "nvar", "group": "Parameters", "definition": "random(2..3)", "description": "

Number of variables in the system.

", "templateType": "anything", "can_override": true}, "positivity": {"name": "positivity", "group": "Parameters", "definition": "repeat(random([-1,0,1]),nvar)", "description": "

Positivity of each variable: -1 means nonpositive, 1 means nonnegative and 0 means free variable.

", "templateType": "anything", "can_override": false}, "ncons": {"name": "ncons", "group": "Parameters", "definition": "random(2..4)", "description": "", "templateType": "anything", "can_override": true}, "A": {"name": "A", "group": "Parameters", "definition": "repeat(repeat(random(-5..5),nvar),ncons)", "description": "", "templateType": "anything", "can_override": false}, "x": {"name": "x", "group": "Names", "definition": "map(\"x{i}\",i,1..nvar)", "description": "", "templateType": "anything", "can_override": false}, "L": {"name": "L", "group": "Names", "definition": "map(join(map(\"{a}*{v}\",[v,a],zip(x,r)),\"+\"),r,A)", "description": "", "templateType": "anything", "can_override": false}, "Cp": {"name": "Cp", "group": "Names", "definition": "map(\"{l} {d} {r}\",[l,d,r],zip(L,direction,b))", "description": "", "templateType": "anything", "can_override": false}, "direction": {"name": "direction", "group": "Parameters", "definition": "repeat(random([\"\u2265\",\"=\",\"\u2264\"]),ncons)", "description": "", "templateType": "anything", "can_override": false}, "b": {"name": "b", "group": "Parameters", "definition": "repeat(random(-5..5),ncons)", "description": "", "templateType": "anything", "can_override": false}, "Constraints": {"name": "Constraints", "group": "Names", "definition": "map(simplify(expression(v),[\"all\"]),v,Cp)", "description": "", "templateType": "anything", "can_override": false}, "system": {"name": "system", "group": "Names", "definition": "latex(show_system(Constraints, [\"all\"]))", "description": "", "templateType": "anything", "can_override": false}, "C": {"name": "C", "group": "Parameters", "definition": "repeat(random(-5..5),nvar)", "description": "", "templateType": "anything", "can_override": false}, "optimise": {"name": "optimise", "group": "Parameters", "definition": "random([\"maximise\", \"minimise\"])", "description": "", "templateType": "anything", "can_override": false}, "objective_string": {"name": "objective_string", "group": "Names", "definition": "join(map(\"{a}*{v}\",[v,a],zip(x,c)),\"+\")", "description": "", "templateType": "anything", "can_override": false}, "objective": {"name": "objective", "group": "Names", "definition": "simplify(expression(objective_string),['all'])", "description": "", "templateType": "anything", "can_override": false}, "Jp": {"name": "Jp", "group": "Names", "definition": "set(map(k+1,k,indices(positivity, 1)))", "description": "", "templateType": "anything", "can_override": false}, "Jn": {"name": "Jn", "group": "Names", "definition": "set(map(k+1,k,indices(positivity, -1)))", "description": "", "templateType": "anything", "can_override": false}, "Mv": {"name": "Mv", "group": "Solution", "definition": "map(map(if(p=1, [x], if(p=-1, [-x], [x,-x])), [p, x], zip(positivity, R)), R, A)", "description": "", "templateType": "anything", "can_override": false}, "Av": {"name": "Av", "group": "Solution", "definition": "map(foldl((x,y)->x+y, [], R), R, Mv)", "description": "

The update of the matrix A after making all the variables nonnegative.

", "templateType": "anything", "can_override": false}, "Mc": {"name": "Mc", "group": "Constraints Update", "definition": "map(if(p=\"\u2264\", [R], if(p=\"\u2265\", [map(-x,x,R)], [R, map(-x,x,R)])), [p,R], zip(direction, Av))", "description": "

The constraint matrix after making all the constraints less than.

", "templateType": "anything", "can_override": false}, "Ac": {"name": "Ac", "group": "Constraints Update", "definition": "foldl((x,y)->x+y, [], Mc)", "description": "", "templateType": "anything", "can_override": false}, "bv": {"name": "bv", "group": "Constraints Update", "definition": "map(if(p=\"\u2264\", [x], if(p=\"\u2265\", [-x], [x, -x])), [p,x], zip(direction, b))", "description": "", "templateType": "anything", "can_override": false}, "bc": {"name": "bc", "group": "Constraints Update", "definition": "foldl((x,y)->x+y, [], bv)", "description": "", "templateType": "anything", "can_override": false}, "AA": {"name": "AA", "group": "Constraints Update", "definition": "matrix(map(R+[x], [R,x], zip(Ac, bc)))", "description": "", "templateType": "anything", "can_override": false}, "cv": {"name": "cv", "group": "Solution", "definition": "map(if(p=1, [x], if(p=-1, [-x], [x,-x])), [p, x], zip(positivity, c))", "description": "", "templateType": "anything", "can_override": false}, "cc": {"name": "cc", "group": "Solution", "definition": "map(if(optimise=\"maximise\", x, -x), x, foldl((x,y) -> x+y, [],cv))", "description": "", "templateType": "anything", "can_override": false}, "nvarcanonical": {"name": "nvarcanonical", "group": "Solution", "definition": "length(cc)", "description": "", "templateType": "anything", "can_override": false}, "nconscanonical": {"name": "nconscanonical", "group": "Solution", "definition": "length(bc)", "description": "", "templateType": "anything", "can_override": false}, "cstudent": {"name": "cstudent", "group": "Ungrouped variables", "definition": "cc", "description": "", "templateType": "anything", "can_override": false}, "objectivev_string": {"name": "objectivev_string", "group": "Solution", "definition": "join(map(\"{a}*{v}\",[v,a],zip(y,cc)),\"+\")", "description": "", "templateType": "anything", "can_override": false}, "y": {"name": "y", "group": "Solution", "definition": "map(\"y{i}\",i,1..nvarcanonical)", "description": "", "templateType": "anything", "can_override": false}, "objectivev": {"name": "objectivev", "group": "Solution", "definition": "simplify(expression(objectivev_string),['all'])", "description": "", "templateType": "anything", "can_override": false}, "Cpv": {"name": "Cpv", "group": "Solution", "definition": "map(\"{l} {d} {r}\",[l,d,r],zip(Lv,direction,b))", "description": "", "templateType": "anything", "can_override": false}, "Lv": {"name": "Lv", "group": "Solution", "definition": "map(join(map(\"{a}*{v}\",[v,a],zip(y,r)),\"+\"),r,Av)", "description": "", "templateType": "anything", "can_override": false}, "Constraintsv": {"name": "Constraintsv", "group": "Solution", "definition": "map(simplify(expression(v),[\"all\"]),v,Cpv)", "description": "", "templateType": "anything", "can_override": false}, "Systemv": {"name": "Systemv", "group": "Solution", "definition": "latex(show_system(Constraintsv, [\"all\"]))", "description": "", "templateType": "anything", "can_override": false}, "Lc": {"name": "Lc", "group": "Constraints Update", "definition": "map(join(map(\"{a}*{v}\",[v,a],zip(y,r)),\"+\"),r,Ac)", "description": "", "templateType": "anything", "can_override": false}, "Cpc": {"name": "Cpc", "group": "Constraints Update", "definition": "map(\"{l} \u2264 {r}\",[l,r],zip(Lc,bc))", "description": "", "templateType": "anything", "can_override": false}, "Constraintsc": {"name": "Constraintsc", "group": "Constraints Update", "definition": "map(simplify(expression(v),[\"all\"]),v,Cpc)", "description": "", "templateType": "anything", "can_override": false}, "systemc": {"name": "systemc", "group": "Constraints Update", "definition": "latex(show_system(Constraintsc, [\"all\"]))", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "all(map(r -> some(map(x->x <> 0, r)), A)) and some(map(x->x <> 0, c))", "maxRuns": "1000"}, "ungrouped_variables": ["cstudent"], "variable_groups": [{"name": "Parameters", "variables": ["nvar", "positivity", "ncons", "A", "b", "direction", "C", "optimise"]}, {"name": "Names", "variables": ["x", "L", "Cp", "Constraints", "system", "objective_string", "objective", "Jp", "Jn"]}, {"name": "Solution", "variables": ["y", "Mv", "Av", "cv", "cc", "objectivev_string", "objectivev", "Lv", "Cpv", "Constraintsv", "Systemv", "nvarcanonical", "nconscanonical"]}, {"name": "Constraints Update", "variables": ["Mc", "Ac", "bv", "bc", "AA", "Lc", "Cpc", "Constraintsc", "systemc"]}], "functions": {"show_system": {"parameters": [["system", "list of expression"], ["rules", "list of string"]], "type": "string", "language": "javascript", "definition": "const latex = Numbas.jme.display.treeToLaTeX\nconst bscope = Numbas.jme.builtinScope\n//console.log(latex)\n\nconst strings = system.map(s => latex(s,rules.filter(x => x !== \"aligned\"), bscope))\n\nif(rules.includes(\"aligned\")){\nconst alignedstrings = strings.map(s => s.replace(/(=|\\\\[gl]eq)/,\"&$1\"))\nreturn \"\\\\begin{aligned}\"+alignedstrings.join(\"\\\\\\\\\")+\"\\\\end{aligned}\"\n}\n\nreturn \"\\\\begin{gathered}\"+strings.join(\"\\\\\\\\\")+\"\\\\end{gathered}\""}, "find_rows": {"parameters": [["A", "list of list"], ["b", "list of number"]], "type": "list", "language": "jme", "definition": "map([R,l]->indices(map([U,v]->v=l and all(map(s->some(map(t->t=s,U)),R)), zip(A,b)),true),zip(Ac,bc))"}, "find_cols": {"parameters": [["A", "list of list"], ["T", "list of list"]], "type": "list", "language": "jme", "definition": "map(j->indices(map( k->all(map( [x,y]->Ac[x][k]=A[y[0]][j], T)),0..nvarcanonical-1),true),0..nvarcanonical-1)"}, "compare_systems": {"parameters": [["A", "matrix"], ["b", "vector"], ["c", "vector"], ["M", "matrix"], ["u", "vector"], ["v", "vector"]], "type": "list", "language": "javascript", "definition": "/* This function compares two systems of the form `Ax\u2264b` and `My\u2264u`, and objectives `cx` and `vy`. The order of rows and columns in the matrices are shuffled (with the corresponding shuffles in the left hand side and objective vectors).\n\nIn case of mismatch we just return an empty matrix.\n*/\n\n\nfunction rowmatch(x,y){return x.every(e => y.some(f => f==e))}\n\n\nconst nrows = A.length\nconst ncolumns = A[0].length\n\nconst rowRange = [...A.keys()]\nconst colRange = [...A[0].keys()]\n\n/* First step: identify the possible correspondence in rows from M. To do that we take every row of M and find the row of `A` that contains all the same values (not necessarily in the same order). There might be several.*/\nconst T1 = A.map((R,k) => [...M.keys()].filter(i => b[k]===u[i] && rowmatch(R, M[i])))\n\n/* At this point, if a row doesn't have a match we can stop.*/\nconst missingKey = [...A.keys()].some(k => T1.every(v => !v.includes(k)))\nif (T1.some(x => x.length == 0) || missingKey) return [] \n\n\n/* Second step: match the columns. We filter out the rows that are fully identified (only one match) and check the columns so that all the parameters match.*/\nconst T2 = colRange.map(k => colRange.filter( j => [...T1.keys()].every( i => T1[i].length > 1 || A[i][j] == M[T1[i][0]][k] ) ))\n\n/* If a column doesn't have a match we can stop.*/\nconst missingVar = colRange.some(k => T2.every(v => !v.includes(k)))\nif (T2.some(x => x.length == 0) || missingVar) return [] \n\n/* At this point we should hope that there are no duplicates, we should have a match for the variables. Leap of faith...*/\nconst varMatch = T2.map(v => v[0])\n\n/* Now we can finally match the rows. We can reuse the partial matches we found in the first step. */\nconst T3 = T1.map((L,i) => L.filter(k => M[k].every((x,j) => x === A[i][varMatch[j]])))\n\nconst missingCons = rowRange.some(k => T3.every(v => !v.includes(k)))\nif (T3.some(x => x.length == 0) || missingCons) return [] \n\nconst consMatch = T3.map(v => v[0])\n\n\nreturn [varMatch, consMatch ]"}, "same_systems": {"parameters": [["AugmentedA", "matrix"], ["c", "vector"], ["AugmentedM", "matrix"], ["v", "vector"]], "type": "boolean", "language": "javascript", "definition": "/* This function compares two systems of the form `Ax\u2264b` and `My\u2264u`, and objectives `cx` and `vy`. The order of rows and columns in the matrices are shuffled (with the corresponding shuffles in the left hand side and objective vectors).\n\nIn case of mismatch we just return an empty matrix.\n*/\n\nfunction rowmatch(x,y){return x.every(e => y.some(f => f==e))}\n\nconst nrows = AugmentedA.length\nconst ncolumns = AugmentedA[0].length - 1\n\nconst rowRange = [...Array(nrows).keys()]\nconst colRange = [...Array(ncolumns).keys()]\n\nfor(let i=v.length; i colRange.map(i => R[i]))\nconst b = AugmentedA.map(R => R[ncolumns])\n\nconst M = AugmentedM.map(R => colRange.map(i => R[i]))\nconst u = AugmentedM.map(R => R[ncolumns])\n\n/* First step: identify the possible correspondence in rows from M. To do that we take every row of M and find the row of `A` that contains all the same values (not necessarily in the same order). There might be several.*/\nconst T1 = A.map((R,k) => [...M.keys()].filter(i => b[k]===u[i] && rowmatch(R, M[i])))\n\n/* At this point, if a row doesn't have a match we can stop.*/\nconst missingKey = [...A.keys()].some(k => T1.every(v => !v.includes(k)))\nif (T1.some(x => x.length == 0) || missingKey) {return false}\n\n/* Second step: match the columns. We filter out the rows that are fully identified (only one match) and check the columns so that all the parameters match.*/\nconst T2 = colRange.map(k => colRange.filter( j => c[j] === v[k] && [...T1.keys()].every( i => T1[i].length > 1 || A[i][j] === M[T1[i][0]][k] ) ))\n\n/* If a column doesn't have a match we can stop.*/\nconst missingVar = colRange.some(k => T2.every(v => !v.includes(k)))\nif (T2.some(x => x.length == 0) || missingVar) {return false}\n\n/* At this point we should hope that there are no duplicates, we should have a match for the variables. Leap of faith...*/\nconst varMatch = T2.map(v => v[0])\n\n/* Now we can finally match the rows. We can reuse the partial matches we found in the first step. */\nconst T3 = T1.map((L,i) => L.filter(k => M[k].every((x,j) => x === A[i][varMatch[j]])))\n\nconst missingCons = rowRange.some(k => T3.every(v => !v.includes(k)))\nif (T3.some(x => x.length == 0) || missingCons) {return false} \n\nconst consMatch = T3.map(v => v[0])\n\nreturn true"}}, "preamble": {"js": "", "css": ".matrix-input .matrix .cell:nth-of-type(1)::after { content: ' y\u2081 ';}\n.matrix-input .matrix .cell:nth-of-type(2)::after { content: ' y\u2082 ';}\n.matrix-input .matrix .cell:nth-of-type(3)::after { content: ' y\u2083 ';}\n.matrix-input .matrix .cell:nth-of-type(4)::after { content: ' y\u2084 ';}\n.matrix-input .matrix .cell:nth-of-type(5)::after { content: ' y\u2085 ';}\n.matrix-input .matrix .cell:nth-of-type(6)::after { content: ' y\u2086 ';}\n.matrix-input .matrix .cell:nth-of-type(7)::after { content: ' y\u2087 ';}\n.matrix-input .matrix .cell:nth-of-type(8)::after { content: ' y\u2088 ';}\n.matrix-input .matrix .cell:nth-of-type(9)::after { content: ' y\u2089 ';}\n\n.matrix-input .matrix .cell:not(:first-of-type)::before { content: ' + ';}\n\n\n.inequality.constraints .matrix-input .matrix .cell:last-of-type::before { content: ' \u2264 ';}\n.constraints .matrix-input .matrix .cell:last-of-type::after { content: '';}\n\n\n.matrix-input .matrix .cell {\n margin-right: 0;\n padding-right: 0;\n}\n\n\n.matrix-input .left-bracket, .matrix-input .right-bracket {\n display: none !important;\n}\n"}, "parts": [{"type": "information", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

In this quiz you will be asked to convert linear programs to canonical or standard forms. The variables in the solution will be $y_1,\\ldots,y_n$.

\n

After you convert the linear program in your notes, your own solution may have different variable names, for example, your constraints may look like:
\\begin{alignat}{4}
x_1&+3x_2^+&-3x_2^-&&+s_1 &&&= 2\\\\
-2x_1 &-5x_2^+&+5x_2^-&-2x_3 &&+ s_2 &&=3\\\\
3x_1 &&&-x_3 &&&&=5.
\\end{alignat}

\n

Each of your variables should be assigned to one of the $y_i$ variables in the quiz, for example:

\n

\\begin{align}
y_1 &= x_1 & y_2 &= x_2^+ & y_3 &= x_2^-\\\\
y_4 &= x_3 & y_3 &= s_1 & y_4 &= s_2
\\end{align}

\n

In the quiz the constraints then should become

\n

\\begin{alignat}{4}
y_1&+3y_2&-3y_3&+0y_4&+y_5&+0y_6 &&= 2\\\\
-2y_1 &-5y_2&+5y_3&-2y_4&+0y_5&+ y_6 &&=3\\\\
3y_1 &+0y_2&+0y_3&-1y_4&+0y_5&+ 0y_6 &&=5
\\end{alignat}

\n

\n

In order to enter your solution in the boxes, select the appropriate number of rows (number of constraints, here, for example, 3) and of columns (number of variables, plus the right hand side, here 7) and enter the coefficients. For example:

\n

"}, {"type": "gapfill", "useCustomName": true, "customName": "Canonical form", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

maximise [[0]]

\n

subject to

\n
\n

[[1]]

\n
\n

$y_j≥0, ∀j$.

", "gaps": [{"type": "matrix", "useCustomName": true, "customName": "c", "marks": "0", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": false, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "correctAnswer": "matrix(cc)", "correctAnswerFractions": false, "numRows": "1", "numColumns": "1", "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": "10", "minRows": 1, "maxRows": "1", "prefilledCells": ""}, {"type": "matrix", "useCustomName": true, "customName": "System", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "value:\n cstudent[0]\n\nstudent_objective:\n true\n //vector(map(c -> parsenumber(c,allowedNotationStyles), cstudent))\n\nsame_system (compare the sytem entered by the student with the correct one):\n same_systems(AA, vector(cc), studentMatrix, cstudent[0])\n\ncheck_system (check that the sytem is correct):\n apply(same_system);\n //if(same_system = true,correct(\"Your answer is correct\"); end(),incorrect(\"Your answer is incorrect.\");end());\n correctif(same_system);end()\n assert(same_system, \n incorrect(\"You did not enter the correct system\");\n end())\n\nmark:\n apply(any_empty);\n apply(any_invalid);\n //assert(settings[\"precisionType\"]=\"none\" and not settings[\"allowFractions\"], apply(all_same_precision));\n //apply(wrong_size);\n apply(same_system);\n correctif(same_system=true)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [{"variable": "cstudent", "part": "p1g0", "must_go_first": true}], "variableReplacementStrategy": "alwaysreplace", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "correctAnswer": "matrix(AA)", "correctAnswerFractions": false, "numRows": "2", "numColumns": "2", "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": "2", "maxColumns": "10", "minRows": "1", "maxRows": 0, "prefilledCells": ""}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question", "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}]}], "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}