// Numbas version: finer_feedback_settings
{"name": "Hungarian algorithm to maximise cost", "extensions": ["optimisation"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"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}], "name": "Hungarian algorithm to maximise cost", "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>", "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}