// Numbas version: exam_results_page_options {"name": "Duality", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Duality", "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": "Find the dual problem for the following linear program:
\n\\[\\begin{gathered}
\\var{{optimise}}\\text{ } \\var{objective} \\text{ subject to }\\\\
\\var{system}
\\end{gathered}\\]
\\[x_i≥0, \\forall j\\in \\var{Jp}\\]
\n\\[x_j≤0, \\forall j\\in \\var{Jn}\\]
", "advice": "In order to convert a problem to canonical form, we need to perform the following changes
\n\\[\\begin{gathered}
\\var{{optimise}}\\text{ } \\var{objective} \\text{ subject to }\\\\
\\var{system}
\\end{gathered}\\]
\\[x_i≥0, \\forall\\in \\var{Jp}\\]
\n\\[x_j≤0, \\forall j\\in \\var{Jn}\\]
\n\nThe dual problem is:
\n\\[\\begin{gathered}
\\var{optimised}\\text{ } \\var{objectived} \\text{ subject to }\\\\
\\var{systemd}
\\end{gathered}\\]
\\[y_i≥0, \\forall\\in \\var{Jdp}\\]
\n\\[y_j≤0, \\forall j\\in \\var{Jdn}\\]
\n", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true, "j": false}, "constants": [], "variables": {"nvar": {"name": "nvar", "group": "Parameters", "definition": "random(3..5)", "description": "Number of variables in the system.
", "templateType": "anything", "can_override": true}, "positivity": {"name": "positivity", "group": "Parameters", "definition": "repeat(random([\"\u22640\",\"free\",\"\u22650\"]),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(5..8)", "description": "Number of constraints in the system.
", "templateType": "anything", "can_override": true}, "A": {"name": "A", "group": "Parameters", "definition": "repeat(repeat(random(-5..5),nvar),ncons)", "description": "Constraint matrix (left hand side).
", "templateType": "anything", "can_override": false}, "x": {"name": "x", "group": "Primal Problem", "definition": "map(\"x{i}\",i,1..nvar)", "description": "Variable names for the primal problem.
", "templateType": "anything", "can_override": false}, "L": {"name": "L", "group": "Primal Problem", "definition": "map(join(map(\"{a}*{v}\",[v,a],zip(x,r)),\"+\"),r,A)", "description": "Left hand sides for the primal, in equation form.
", "templateType": "anything", "can_override": false}, "Cp": {"name": "Cp", "group": "Primal Problem", "definition": "map(\"{l} {d} {r}\",[l,d,r],zip(L,direction,b))", "description": "The constraints of the primal, in equation form.
", "templateType": "anything", "can_override": false}, "direction": {"name": "direction", "group": "Parameters", "definition": "repeat(random([\"\u2265\",\"=\",\"\u2264\"]),ncons)", "description": "Directions of the constraints.
", "templateType": "anything", "can_override": false}, "b": {"name": "b", "group": "Parameters", "definition": "repeat(random(-5..5),ncons)", "description": "Right hand side of the constraints.
", "templateType": "anything", "can_override": false}, "Constraints": {"name": "Constraints", "group": "Primal Problem", "definition": "map(simplify(expression(v),[\"all\"]),v,Cp)", "description": "The constraints of the primal, in mathematical expressions.
", "templateType": "anything", "can_override": false}, "system": {"name": "system", "group": "Primal Problem", "definition": "systema", "description": "Latex representation of the constraints of the primal.
", "templateType": "anything", "can_override": false}, "C": {"name": "C", "group": "Parameters", "definition": "repeat(random(-5..5),nvar)", "description": "Cost vector
", "templateType": "anything", "can_override": false}, "optimise": {"name": "optimise", "group": "Parameters", "definition": "random([\"maximise\", \"minimise\"])", "description": "Optimisation direction.
", "templateType": "anything", "can_override": true}, "objective_string": {"name": "objective_string", "group": "Primal Problem", "definition": "join(map(\"{a}*{v}\",[v,a],zip(x,c)),\"+\")", "description": "A string represneting the objective of the primal.
", "templateType": "anything", "can_override": false}, "objective": {"name": "objective", "group": "Primal Problem", "definition": "simplify(expression(objective_string),['all'])", "description": "The objective function of the primal problem.
", "templateType": "anything", "can_override": false}, "Jp": {"name": "Jp", "group": "Primal Problem", "definition": "set(map(k+1,k,indices(positivity, Nonnegativitycodes[2])))", "description": "List of nonnegative variables in the pimal problem.
", "templateType": "anything", "can_override": false}, "Jn": {"name": "Jn", "group": "Primal Problem", "definition": "set(map(k+1,k,indices(positivity, Nonnegativitycodes[0])))", "description": "List of nonpositive variables in the primal problem.
", "templateType": "anything", "can_override": false}, "Mv": {"name": "Mv", "group": "Dual Problem", "definition": "map(map(if(p=nonnegativitycodes[2], [x], if(p=nonnegativitycodes[0], [-x], [x,-x])), [p, x], zip(positivity, R)), R, A)", "description": "", "templateType": "anything", "can_override": false}, "cstudent": {"name": "cstudent", "group": "Ungrouped variables", "definition": "b", "description": "", "templateType": "anything", "can_override": false}, "objectived_string": {"name": "objectived_string", "group": "Dual Problem", "definition": "join(map(\"{a}*{v}\",[v,a],zip(y,b)),\"+\")", "description": "", "templateType": "anything", "can_override": false}, "y": {"name": "y", "group": "Dual Problem", "definition": "map(\"y{i}\",i,1..ncons)", "description": "", "templateType": "anything", "can_override": false}, "objectived": {"name": "objectived", "group": "Dual Problem", "definition": "simplify(expression(objectived_string),['all'])", "description": "", "templateType": "anything", "can_override": false}, "Cpd": {"name": "Cpd", "group": "Dual Problem", "definition": "map(\"{l} {d} {r}\",[l,d,r],zip(Ld,directionv,c))", "description": "", "templateType": "anything", "can_override": false}, "Ld": {"name": "Ld", "group": "Dual Problem", "definition": "map(join(map(\"{a}*{v}\",[v,a],zip(y,r)),\"+\"),r,Ad)", "description": "", "templateType": "anything", "can_override": false}, "Constraintsd": {"name": "Constraintsd", "group": "Dual Problem", "definition": "map(simplify(expression(v),[\"all\"]),v,Cpd)", "description": "", "templateType": "anything", "can_override": false}, "Systemd": {"name": "Systemd", "group": "Dual Problem", "definition": "latex(show_system(Constraintsd, [\"all\"]))", "description": "", "templateType": "anything", "can_override": false}, "max_conversion": {"name": "max_conversion", "group": "Ungrouped variables", "definition": "[[\"\u2265\", \"\u22640\"],[\"=\", \"free\"],[\"\u2264\", \"\u22650\"], [\"\u22640\", \"\u2264\"], [\"free\", \"=\"], [\"\u22650\", \"\u2265\"],[\"maximise\", \"minimise\"]]", "description": "", "templateType": "anything", "can_override": false}, "min_conversion": {"name": "min_conversion", "group": "Ungrouped variables", "definition": "map([x,y] -> [y,x], max_conversion)", "description": "", "templateType": "anything", "can_override": false}, "conversion": {"name": "conversion", "group": "Ungrouped variables", "definition": "dict(map([x,y] -> [\"{x}\",y],if(optimise=\"maximise\",max_conversion, min_conversion)))", "description": "", "templateType": "anything", "can_override": false}, "Ad": {"name": "Ad", "group": "Dual Problem", "definition": "transpose(A)", "description": "", "templateType": "anything", "can_override": false}, "Jdn": {"name": "Jdn", "group": "Dual Problem", "definition": "map(k->k+1,set(indices(map(x->conversion[x] = nonnegativitycodes[0], direction),true)))", "description": "", "templateType": "anything", "can_override": false}, "Jdp": {"name": "Jdp", "group": "Dual Problem", "definition": "map(k->k+1,set(indices(map(x->conversion[x] = nonnegativitycodes[2], direction),true)))", "description": "", "templateType": "anything", "can_override": false}, "directionv": {"name": "directionv", "group": "Dual Problem", "definition": "map(x->conversion[\"{x}\"], positivity)", "description": "", "templateType": "anything", "can_override": false}, "optimised": {"name": "optimised", "group": "Dual Problem", "definition": "conversion[optimise]", "description": "", "templateType": "anything", "can_override": false}, "Adlt": {"name": "Adlt", "group": "Dual Problem", "definition": "matrix(map(Ad[k]+[c[k]],k,indices(directionv,\"\u2264\")))", "description": "", "templateType": "anything", "can_override": false}, "Adgt": {"name": "Adgt", "group": "Dual Problem", "definition": "matrix(map(Ad[k]+[c[k]],k,indices(directionv,\"\u2265\")))", "description": "", "templateType": "anything", "can_override": false}, "Adeq": {"name": "Adeq", "group": "Dual Problem", "definition": "matrix(map(Ad[k]+[c[k]],k,indices(directionv,\"=\")))", "description": "", "templateType": "anything", "can_override": false}, "test": {"name": "test", "group": "Test", "definition": "2//same_systems([Adlt, Adgt, Adeq],vector(b),[Jdp,Jdn],[A1,A2,A3],c1,[J1,J2])", "description": "", "templateType": "anything", "can_override": false}, "I1": {"name": "I1", "group": "Test", "definition": "matrix(map(k -> Id(ncons)[k], reorder))", "description": "", "templateType": "anything", "can_override": false}, "A1": {"name": "A1", "group": "Test", "definition": "if(length(Adlt)=0,Adlt,Adlt*I2)", "description": "", "templateType": "anything", "can_override": false}, "A2": {"name": "A2", "group": "Test", "definition": "if(length(Adgt)=0,Adgt,Adgt*I2)", "description": "", "templateType": "anything", "can_override": false}, "A3": {"name": "A3", "group": "Test", "definition": "if(length(Adeq)=0,Adeq,Adeq*I2)", "description": "", "templateType": "anything", "can_override": false}, "I2": {"name": "I2", "group": "Test", "definition": "combine_diagonally(I1,matrix([1]))", "description": "", "templateType": "anything", "can_override": false}, "c1": {"name": "c1", "group": "Test", "definition": "vector(b)*I1", "description": "", "templateType": "anything", "can_override": false}, "J1": {"name": "J1", "group": "Test", "definition": "set(map(k -> reorder[k-1]+1, Jdp))", "description": "", "templateType": "anything", "can_override": false}, "reorder": {"name": "reorder", "group": "Test", "definition": "shuffle(0..ncons-1)", "description": "", "templateType": "anything", "can_override": false}, "J2": {"name": "J2", "group": "Test", "definition": "set(map(k -> reorder[k-1]+1, Jdn))", "description": "", "templateType": "anything", "can_override": false}, "nonnegativityCodes": {"name": "nonnegativityCodes", "group": "Ungrouped variables", "definition": "[\"\u22640\",\"free\",\"\u22650\"]", "description": "Positivity of each variable: -1 means nonpositive, 1 means nonnegative and 0 means free variable.
", "templateType": "anything", "can_override": false}, "systema": {"name": "systema", "group": "Primal Problem", "definition": "latex(latexconstraints(A,direction,b,map(s->latex(expression(s)),x)))", "description": "A latex representation of the constraints of the primal, where the variables are aligned.
", "templateType": "anything", "can_override": false}, "systemb": {"name": "systemb", "group": "Primal Problem", "definition": "latex(show_system(Constraints, [\"all\"]))", "description": "A latex representation of the constraints of the primal, where the variables are not aligned.
", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": "1000"}, "ungrouped_variables": ["cstudent", "max_conversion", "min_conversion", "conversion", "nonnegativityCodes"], "variable_groups": [{"name": "Parameters", "variables": ["nvar", "ncons", "positivity", "A", "b", "direction", "C", "optimise"]}, {"name": "Primal Problem", "variables": ["x", "L", "Cp", "Constraints", "system", "objective_string", "objective", "Jp", "Jn", "systema", "systemb"]}, {"name": "Dual Problem", "variables": ["y", "Ad", "Mv", "objectived_string", "objectived", "Ld", "Cpd", "Constraintsd", "Systemd", "Jdn", "Jdp", "directionv", "optimised", "Adlt", "Adgt", "Adeq"]}, {"name": "Test", "variables": ["reorder", "I1", "I2", "A1", "A2", "A3", "c1", "J1", "J2", "test"]}], "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\")).map(s => s.replace(/(?<=.)([+-])/g,\"&$1\"))\nreturn \"\\\\begin{aligned}\"+alignedstrings.join(\"\\\\\\\\\")+\"\\\\end{aligned}\"\n}\n\nreturn \"\\\\begin{gathered}\"+strings.join(\"\\\\\\\\\")+\"\\\\end{gathered}\""}, "same_systems": {"parameters": [["AugmentedA", "list of matrix"], ["c", "matrix"], ["Ja", "list of list"], ["AugmentedM", "list of matrix"], ["u", "matrix"], ["Jm", "list of list"]], "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\nconsole.log(\"Starting maching\")\n\nfunction rowmatch(x,y){\n return x[1]===y[1] && x[0].every(e => y[0].some(f => f==e))\n}\n\nJm = [Jm[0][0], Jm[1][0]]\n\n/* Check that the number of columns is the same for all (nonempty) systems. */\nconst ncolumns = c[0].length\nfor(let i=u[0].length; i[[0]] [[1]]
\nsubject to
\nSet the number of rows/columns to 0 manually if a constraint type does not exist in the dual.
\n[[2]]
\n[[3]]
\n[[4]]
\n$y_j≥0, ∀j∈${[[5]]}.
\n$y_j≤0, ∀j∈${[[6]]}.
\n