// Numbas version: exam_results_page_options
{"questions": [], "duration": 0, "name": "Assignment problem", "showQuestionGroupNames": false, "allQuestions": true, "percentPass": 0, "feedback": {"showanswerstate": true, "advicethreshold": 0, "showactualmark": true, "allowrevealanswer": true, "showtotalmark": true}, "shuffleQuestions": false, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Hungarian algorithm", "extensions": ["optimisation"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "variable_groups": [{"variables": ["worker", "job", "workers", "jobs"], "name": "Text"}, {"variables": ["num_workers", "num_jobs", "costs"], "name": "Setup"}, {"variables": ["solution", "total_cost"], "name": "Solution"}], "variables": {"solution": {"templateType": "anything", "group": "Solution", "definition": "hungarian(costs)", "description": "", "name": "solution"}, "costs": {"templateType": "anything", "group": "Setup", "definition": "matrix(\n  repeat(\n    repeat(\n      random(1..9),\n      num_jobs\n    ),\n    num_workers\n  )\n)", "description": "", "name": "costs"}, "job": {"templateType": "string", "group": "Text", "definition": "safe(\"school\")", "description": "", "name": "job"}, "num_jobs": {"templateType": "anything", "group": "Setup", "definition": "num_workers", "description": "", "name": "num_jobs"}, "worker": {"templateType": "string", "group": "Text", "definition": "safe(\"inspector\")", "description": "", "name": "worker"}, "jobs": {"templateType": "string", "group": "Text", "definition": "safe(\"schools\")", "description": "", "name": "jobs"}, "workers": {"templateType": "string", "group": "Text", "definition": "safe(\"school inspectors\")", "description": "", "name": "workers"}, "total_cost": {"templateType": "anything", "group": "Solution", "definition": "sum(map(\n  let(x,p[0],y,p[1],\n    costs[x][y]*solution[x][y]\n  ),\n  p,\n  product(list(0..num_workers-1),list(0..num_jobs-1))\n))", "description": "", "name": "total_cost"}, "num_workers": {"templateType": "anything", "group": "Setup", "definition": "5//random(3..5)", "description": "", "name": "num_workers"}}, "ungrouped_variables": [], "functions": {"calculate_cost": {"type": "string", "language": "javascript", "definition": "var o = [];\nfor(var i=0;i<costs.rows;i++) {\n  for(var j=0;j<costs.columns;j++) {\n    if(solution[i][j]) {\n      o.push(costs[i][j]);\n    }\n  }\n}\nvar s = new Numbas.jme.types.TString(o.join(' + '));\ns.latex = true;\nreturn s;", "parameters": [["costs", "matrix"], ["solution", "matrix"]]}}, "parts": [{"displayType": "radiogroup", "showCellAnswerState": false, "useCustomName": false, "prompt": "<p>Find an assignment of {workers} to {jobs} which minimises the total distance travelled.</p>", "minAnswers": 0, "maxAnswers": 0, "shuffleChoices": false, "warningType": "none", "showCorrectAnswer": true, "type": "m_n_x", "minMarks": 0, "shuffleAnswers": false, "variableReplacements": [], "layout": {"type": "all", "expression": ""}, "choices": ["{capitalise(worker)} 1", "{capitalise(worker)} 2", "{capitalise(worker)} 3", "{capitalise(worker)} 4", "{capitalise(worker)} 5"], "extendBaseMarkingAlgorithm": true, "matrix": "solution", "customMarkingAlgorithm": "student_cost:\n  sum(map(if(studentAnswer[x][y],costs[y][x],0),[x,y],tick_indexes))\n\noptimal_cost:\n  correctif(student_cost<=total_cost)\n\nanyone_unassigned:\n  assert(all(map(some(studentAnswer[row]),row,0..numAnswers-1)),\n    warn(\"You have not assigned an inspector to every school.\");\n    fail(\"You have not assigned an inspector to every school.\");\n    true\n  )\n\nschools_unassigned:\n  assert(all(map(some(map(studentAnswer[row][col],row,0..numAnswers-1)),col,0..numChoices-1)),\n    warn(\"You have not assigned every inspector to a school.\");\n    fail(\"You have not assigned every inspector to a school.\");\n    true\n  )\n\nmark:\n  assert(marks>0,correct());  // any answer is correct when 0 marks are available\n  assert(numTicks>0,\n    warn(translate(\"part.marking.nothing entered\"));\n    fail(translate(\"part.marking.nothing entered\"))\n  );\n  apply(anyone_unassigned);\n  apply(schools_unassigned);\n  apply(optimal_cost)", "customName": "", "unitTests": [], "answers": ["{capitalise(job)} 1", "{capitalise(job)} 2", "{capitalise(job)} 3", "{capitalise(job)} 4", "{capitalise(job)} 5"], "scripts": {}, "maxMarks": 0, "variableReplacementStrategy": "originalfirst", "marks": 0, "showFeedbackIcon": true}, {"prompt": "<p>How many miles will the {workers} have to travel, in total?</p>\n<p>[[0]] miles.</p>", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "total_cost", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "scripts": {}, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "showFeedbackIcon": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "maxValue": "total_cost"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "<p>{num_workers} {workers}&nbsp;have to decide who will attend each of {num_jobs} {jobs}&nbsp;on a particular day. The distances, in miles, that each {worker}&nbsp;would have to travel to each {job}&nbsp;are given below.</p>\n<p>{job_cost_table(costs,capitalise(worker),capitalise(job))}</p>", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": ""}, "advice": "<h4>a)</h4>\n<p>Use the Hungarian algorithm to find the assignment giving the minimum total&nbsp;distance.</p>\n<p>{hungarian_display(costs)}</p>\n<h4>b)</h4>\n<p>The total distance&nbsp;is $\\var{calculate_cost(costs,solution)} = \\var{total_cost}$ miles.</p>"}, {"name": "Hungarian algorithm to maximise cost", "extensions": ["optimisation"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [{"variables": ["worker", "job", "workers", "jobs"], "name": "Text"}, {"variables": ["num_workers", "num_jobs", "max_costs", "top_cost", "min_costs"], "name": "Setup"}, {"variables": ["solution", "total_cost"], "name": "Solution"}], "variables": {"max_costs": {"templateType": "anything", "group": "Setup", "definition": "matrix(\n  repeat(\n    repeat(\n      random(1..9),\n      num_jobs\n    ),\n    num_workers\n  )\n)", "description": "", "name": "max_costs"}, "solution": {"templateType": "anything", "group": "Solution", "definition": "hungarian(min_costs)", "description": "", "name": "solution"}, "min_costs": {"templateType": "anything", "group": "Setup", "definition": "matrix(\n  map(\n    map(\n      top_cost-max_costs[x][y],\n      y,\n      0..num_jobs-1\n    ),\n    x,\n    0..num_workers-1\n  )\n)", "description": "", "name": "min_costs"}, "job": {"templateType": "string", "group": "Text", "definition": "\"machine\"", "description": "", "name": "job"}, "num_workers": {"templateType": "anything", "group": "Setup", "definition": "5//random(3..5)", "description": "", "name": "num_workers"}, "num_jobs": {"templateType": "anything", "group": "Setup", "definition": "num_workers", "description": "", "name": "num_jobs"}, "worker": {"templateType": "string", "group": "Text", "definition": "\"worker\"", "description": "", "name": "worker"}, "jobs": {"templateType": "string", "group": "Text", "definition": "\"machines\"", "description": "", "name": "jobs"}, "top_cost": {"templateType": "anything", "group": "Setup", "definition": "max(map(max(r),r,list(max_costs)))", "description": "", "name": "top_cost"}, "total_cost": {"templateType": "anything", "group": "Solution", "definition": "sum(map(\n  let(x,p[0],y,p[1],\n    max_costs[x][y]*solution[x][y]\n  ),\n  p,\n  product(list(0..num_workers-1),list(0..num_jobs-1))\n))", "description": "", "name": "total_cost"}, "workers": {"templateType": "string", "group": "Text", "definition": "\"workers\"", "description": "", "name": "workers"}}, "ungrouped_variables": [], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"calculate_cost": {"type": "string", "language": "javascript", "definition": "var o = [];\nfor(var i=0;i<costs.rows;i++) {\n  for(var j=0;j<costs.columns;j++) {\n    if(solution[i][j]) {\n      o.push(costs[i][j]);\n    }\n  }\n}\nvar s = new Numbas.jme.types.TString(o.join(' + '));\ns.latex = true;\nreturn s;", "parameters": [["costs", "matrix"], ["solution", "matrix"]]}}, "showQuestionGroupNames": false, "parts": [{"displayType": "radiogroup", "minMarks": 0, "layout": {"type": "all", "expression": ""}, "choices": ["{capitalise(worker)} 1", "{capitalise(worker)} 2", "{capitalise(worker)} 3", "{capitalise(worker)} 4", "{capitalise(worker)} 5"], "showCorrectAnswer": true, "matrix": "solution", "prompt": "<p>Find an assignment of {workers} to {jobs} which maximises the total number of&nbsp;units produced.</p>", "type": "m_n_x", "maxAnswers": 0, "shuffleChoices": false, "warningType": "none", "scripts": {"mark": {"script": "var costs = question.unwrappedVariables.max_costs;\nvar validation = this.validation = {\n  numTicks: 0\n};\nvar t = 0;\nthis.answered = true;\nfor(var i=0;i<costs.rows;i++) {\n  for(var j=0;j<costs.columns;j++) {\n    t += this.ticks[j][i] ? costs[i][j] : 0;  // the ticks array goes [column][row] - the opposite of the matrix type\n    validation.numTicks += this.ticks[j][i] ? 1 : 0;\n  }\n}\nif(t==question.unwrappedVariables.total_cost) {\n  this.setCredit(1,R('part.marking.correct'));\n} else {\n  this.setCredit(0,R('part.marking.incorrect'));\n}", "order": "instead"}}, "marks": 0, "minAnswers": 0, "maxMarks": 0, "shuffleAnswers": false, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "answers": ["{capitalise(job)} 1", "{capitalise(job)} 2", "{capitalise(job)} 3", "{capitalise(job)} 4", "{capitalise(job)} 5"]}, {"prompt": "<p>How many units&nbsp;will the {workers} produce, in total?</p>\n<p>[[0]]&nbsp;units.</p>", "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "total_cost", "minValue": "total_cost", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showPrecisionHint": false}], "type": "gapfill", "showCorrectAnswer": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}], "statement": "<p>A manager must decide which of {num_workers} {workers} will work on&nbsp;each of {num_jobs} {jobs} in a factory. The number of units each {worker} can produce at each {job} in a day are given below.</p>\n<p>{job_cost_table(max_costs,capitalise(worker),capitalise(job))}</p>", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": ""}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "<h4>a)</h4>\n<p>Maximising the total production&nbsp;$\\sum_i\\sum_j c_{ij} x_{ij}$ is the same as minimising the objective function $\\sum_i \\sum_j (-c_{ij})x_{ij}$. So,&nbsp;negate every number in the table, and add $\\var{top_cost}$ so that every element is nonnegative. Then proceed with the standard Hungarian algorithm to minimise the objective function.</p>\n<p>{hungarian_display(min_costs)}</p>\n<h4>b)</h4>\n<p>The total number of units produced&nbsp;is $\\var{calculate_cost(max_costs,solution)} = \\var{total_cost}$.</p>"}], "name": "", "pickQuestions": 0}], "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "<p>Use the Hungarian algorithm to&nbsp;find the optimal assignment of workers to tasks.</p>"}, "type": "exam", "navigation": {"onleave": {"action": "none", "message": ""}, "reverse": true, "browse": true, "showresultspage": "oncompletion", "preventleave": true, "allowregen": true, "showfrontpage": true}, "timing": {"timedwarning": {"action": "none", "message": ""}, "timeout": {"action": "none", "message": ""}, "allowPause": true}, "pickQuestions": 0, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "extensions": ["optimisation"], "custom_part_types": [], "resources": []}