// Numbas version: exam_results_page_options
{"name": "Duality of linear programming problems (2 variables)", "extensions": ["optimisation"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variablesTest": {"condition": "", "maxRuns": 100}, "variables": {"maximise": {"templateType": "anything", "group": "Primal problem", "definition": "random(true,false)", "name": "maximise", "description": "<p>Is the primal problem a maximisation problem?</p>"}, "dual_inequality": {"templateType": "anything", "group": "Dual problem", "definition": "latex(if(maximise,'\\\\geq','\\\\leq'))", "name": "dual_inequality", "description": "<p>LaTeX symbol for the inequality used in the dual problem's constraints.</p>"}, "dual_constraint_coefficients": {"templateType": "anything", "group": "Dual problem", "definition": "matrix(map(\n  map(\n    constraint_coefficients[y][x],\n    y,\n    0..dual_variables-1\n  ),\n  x,\n  0..dual_constraints-1\n))", "name": "dual_constraint_coefficients", "description": "<p>Coefficients of the constraints in the dual problem. Same format as in the primal.</p>"}, "constraint_coefficients": {"templateType": "anything", "group": "Primal problem", "definition": "matrix(repeat(\n  random_partition(random(num_variables+1..2*num_variables+1),num_variables,0),\n  num_constraints\n))", "name": "constraint_coefficients", "description": "<p>Element $(i,j)$ is the coefficient of $x_j$ in the $i$th constraint.</p>"}, "dual_constraints_matrix": {"templateType": "anything", "group": "Dual problem", "definition": "matrix(\n  map(\n    list(dual_constraint_coefficients[j])+[dual_constraint_rhs[j]],\n    j,\n    0..dual_constraints-1\n  )\n)", "name": "dual_constraints_matrix", "description": "<p>Matrix of coefficients for the constraints in the dual problem, with another column added giving the right-hand sides of the constraints.</p>\n<p>Used to mark the&nbsp;student's answer for the constraints.</p>"}, "num_constraints": {"templateType": "anything", "group": "Primal problem", "definition": "3", "name": "num_constraints", "description": "<p>Number of constraints in the primal LP</p>"}, "dual_objective_coefficients": {"templateType": "anything", "group": "Dual problem", "definition": "constraint_rhs", "name": "dual_objective_coefficients", "description": "<p>Coefficients of each variable in the dual problem's objective function.</p>"}, "dual_variables": {"templateType": "anything", "group": "Dual problem", "definition": "num_constraints", "name": "dual_variables", "description": "<p>Number of variables in the dual problem (equal to the number of constraints in the primal)</p>"}, "dual_constraint_rhs": {"templateType": "anything", "group": "Dual problem", "definition": "objective_coefficients", "name": "dual_constraint_rhs", "description": "<p>Right-hand sides of the constraints in the dual problem.</p>"}, "inequality": {"templateType": "anything", "group": "Primal problem", "definition": "latex(if(maximise,'\\\\leq','\\\\geq'))", "name": "inequality", "description": "<p>LaTeX symbol for the inequalities in the primal problem's constraints</p>"}, "dual_constraints": {"templateType": "anything", "group": "Dual problem", "definition": "num_variables", "name": "dual_constraints", "description": "<p>Number of constraints in the dual problem (equal to the number of variables in the primal)</p>"}, "num_variables": {"templateType": "anything", "group": "Primal problem", "definition": "2", "name": "num_variables", "description": "<p>Number of variables in the primal LP</p>"}, "constraint_rhs": {"templateType": "anything", "group": "Primal problem", "definition": "repeat(random(1..20),num_constraints)", "name": "constraint_rhs", "description": "<p>Right-hand side of each constraint</p>"}, "objective_coefficients": {"templateType": "anything", "group": "Primal problem", "definition": "repeat(random(1..6),num_variables)", "name": "objective_coefficients", "description": "<p>Coefficients of each variable in the objective function.</p>"}}, "ungrouped_variables": [], "name": "Duality of linear programming problems (2 variables)", "functions": {"describe_objective": {"type": "string", "language": "javascript", "definition": "var c = coefficients.map(function(c,i) {\n  return '('+c+')*x'+(i+1);\n});\nvar expr = c.join(' + ');\nreturn Numbas.jme.display.exprToLaTeX(expr,'all,!noLeadingMinus',Numbas.jme.builtinScope);", "parameters": [["coefficients", "list"]]}, "describe_constraints": {"type": "number", "language": "javascript", "definition": "var num_variables=coefficients[0].length;\nvar o = '\\\\begin{align}';\nvar lines = [];\nfor(var i=0;i<coefficients.length;i++) {\n  var lhs = coefficients[i].map(function(v,i) {\n    return '('+v+')*'+varname+(i+1);\n  });\n  var expr = Numbas.jme.display.exprToLaTeX(lhs.join(' + '),'all,!noLeadingMinus',Numbas.jme.builtinScope);\n  lines.push(expr + '&'+inequality+' '+Numbas.math.niceNumber(rhs[i]));\n}\nvar l = [];\nfor(var i=0;i<num_variables;i++) {\n  l.push(varname+'_{'+(i+1)+'}');\n}\nlines.push(l.join(', ')+' &\\\\geq 0.');\no += lines.join(' \\\\\\\\ ')+'\\\\end{align}';\nreturn o;", "parameters": [["coefficients", "matrix"], ["rhs", "list"], ["inequality", "string"], ["varname", "string"]]}}, "variable_groups": [{"variables": ["maximise", "num_variables", "num_constraints", "objective_coefficients", "constraint_coefficients", "constraint_rhs", "inequality"], "name": "Primal problem"}, {"variables": ["dual_variables", "dual_constraints", "dual_objective_coefficients", "dual_constraint_coefficients", "dual_constraint_rhs", "dual_constraints_matrix", "dual_inequality"], "name": "Dual problem"}], "parts": [{"prompt": "<p>Write the dual of the given LP problem&nbsp;below.&nbsp;Name your variables <code>y1</code>, <code>y2</code>, ...</p>\n<p>(Use the \"rows\" and \"columns\" boxes to&nbsp;change the number of constraints or variables)</p>\n<p>[[0]]</p>\n<p>$w = $&nbsp;[[1]]</p>\n<p>subject to</p>\n<div class=\"constraint-input\">[[2]]&nbsp;</div>\n<p>$y_i \\geq 0$ for all $i$.</p>", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"displayType": "radiogroup", "maxMarks": 0, "choices": ["<p>Maximise</p>", "<p>Minimise</p>"], "showCorrectAnswer": true, "displayColumns": 0, "useCustomName": false, "customName": "", "customMarkingAlgorithm": "", "unitTests": [], "matrix": "if(maximise,[0,1],[1,0])", "shuffleChoices": false, "showFeedbackIcon": true, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "1_n_2", "minMarks": 0, "showCellAnswerState": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}, {"answer": "{dual_objective_coefficients[0]}*y1+{dual_objective_coefficients[1]}*y2+{dual_objective_coefficients[2]}*y3", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "vsetRangePoints": 5, "useCustomName": false, "customName": "", "checkVariableNames": false, "checkingType": "absdiff", "valuegenerators": [{"value": "", "name": "y1"}, {"value": "", "name": "y2"}, {"value": "", "name": "y3"}], "vsetRange": [0, 1], "variableReplacementStrategy": "originalfirst", "marks": 1, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "jme", "unitTests": [], "checkingAccuracy": 0.001, "showPreview": true, "variableReplacements": [], "failureRate": 1, "showFeedbackIcon": true}, {"markPerCell": false, "allowFractions": false, "correctAnswer": "dual_constraints_matrix", "showCorrectAnswer": true, "useCustomName": false, "customName": "", "customMarkingAlgorithm": "", "unitTests": [], "correctAnswerFractions": false, "allowResize": true, "numRows": 1, "scripts": {"constructor": {"script": "this.display.correctAnswerLaTeX = ko.computed(function() {\n  with(question.unwrappedVariables) {\n    var rows = [];\n    for(var i=0;i<dual_constraints;i++) {\n      var row = [];\n      for(var j=0;j<dual_variables;j++) {\n        row.push('{'+dual_constraint_coefficients[i][j]+'}y'+(j+1));\n      }\n      rows.push('\\\\simplify[all,!noleadingminus]{'+row.join(' + ')+'} &'+dual_inequality+' '+dual_constraint_rhs[i]);\n    }\n    return '\\\\begin{align} '+rows.join(' \\\\\\\\ ')+' \\\\end{align}';\n  }\n},this);", "order": "after"}}, "extendBaseMarkingAlgorithm": true, "type": "matrix", "numColumns": "2", "tolerance": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showFeedbackIcon": true}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "statement": "<p>You are given the following primal linear programming problem:</p>\n<p>{if(maximise,'Maximise','Minimise')} $z = \\var{latex(describe_objective(objective_coefficients))}$ subject to</p>\n<p>\\[ \\var{latex(describe_constraints(constraint_coefficients,constraint_rhs,inequality,'x'))} \\]</p>", "tags": [], "rulesets": {}, "preamble": {"css": ".matrix-input .matrix .cell:nth-child(1):not(:last-child)::after {\n  content: 'y\u2081';\n}\n.matrix-input .matrix .cell:nth-child(2):not(:last-child)::after {\n  content: 'y\u2082';\n}\n.matrix-input .matrix .cell:nth-child(3):not(:last-child)::after {\n  content: 'y\u2083';\n}\n.matrix-input .matrix .cell:nth-child(4):not(:last-child)::after {\n  content: 'y\u2084';\n}\n.matrix-input .matrix .cell:nth-child(5):not(:last-child)::after {\n  content: 'y\u2085';\n}\n.matrix-input .matrix .cell:nth-child(6):not(:last-child)::after {\n  content: 'y\u2086';\n}\n.matrix-input .matrix .cell:nth-child(7):not(:last-child)::after {\n  content: 'y\u2087';\n}\n.matrix-input .matrix .cell:nth-child(8):not(:last-child)::after {\n  content: 'y\u2088';\n}\n.matrix-input .matrix .cell:nth-child(9):not(:last-child)::after {\n  content: 'y\u2089';\n}\n.matrix-input .matrix .cell:not(:last-child)::after {\n  margin-left: 0.5em;\n}\n.matrix-input .matrix .cell:not(:last-child):not(:first-child)::before {\n  content: '+';\n  margin-right: 1em;\n}\n\n.matrix-input .matrix .cell:last-child:not(:first-child)::before {\n  margin-right: 1em;\n}\n.minimisation-problem .matrix-input .matrix .cell:last-child:not(:first-child)::before {\n  content: '\u2265';\n}\n.maximisation-problem .matrix-input .matrix .cell:last-child:not(:first-child)::before {\n  content: '\u2264';\n}\n\n.matrix-input .matrix-wrapper .right-bracket, .matrix-input .matrix-wrapper .left-bracket {\n  display: none !important;\n}", "js": "question.onHTMLAttached(function() {\n  var maximise = question.unwrappedVariables.maximise;\n  $(question.display.html).find('.constraint-input').addClass(maximise ? 'minimisation-problem' : 'maximisation-problem');\n});"}, "type": "question", "extensions": ["optimisation"], "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Given a linear programming problem in standard form, write down the dual problem.</p>"}, "advice": "<p>The dual problem swaps the variables and constraints in the primal problem.</p>\n<p>The primal problem is a {if(maximise,'maximisation','minimisation')} problem, so the dual problem is a {if(maximise,'minimisation','maximisation')}&nbsp;problem.</p>\n<ol>\n<li>For each constraint in the primal there is a variable in the dual. So there are {dual_variables} variables in the dual.</li>\n<li>The right-hand side of the constraints in the primal&nbsp;are the coefficients of the objective function.</li>\n<li>The coefficients of $x_i$ in each of the primal problem's constraints form the coefficients of the $i$th constraint in the dual problem.</li>\n<li>The coefficients in the primal's objective function&nbsp;represent the right-hand sides of the constraints in the dual.</li>\n<li>The primal has $\\var{inequality}$ constraints and the dual has $\\var{dual_inequality}$ constraints.</li>\n</ol>\n<p>So, the dual problem is as follows:</p>\n<p>{if(maximise,'Minimise','Maximise')} $w = \\simplify{{dual_objective_coefficients[0]}y1+{dual_objective_coefficients[1]}y2+{dual_objective_coefficients[2]}y3}$ subject to</p>\n<p>\\[ \\var{latex(describe_constraints(dual_constraint_coefficients,dual_constraint_rhs,dual_inequality,'y'))} \\]</p>", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}