// Numbas version: exam_results_page_options
{"name": "Simplex method - 4 or 5 random inequalities", "extensions": ["optimisation"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [], "variables": {"lines": {"group": "Ungrouped variables", "templateType": "anything", "definition": "map(\n  line_through_points(raw_lines[j][0],raw_lines[j][1],j,len(raw_lines)),\n  j,\n  0..len(raw_lines)-1\n)", "description": "<p>Encodings of the edges as equations for the simplex method.</p>\n<p>Each equation has a coefficient of x1 and x2, a coefficient of 1 for one of the slack variables, and a constant on the right hand side.</p>", "name": "lines"}, "sol": {"group": "Ungrouped variables", "templateType": "anything", "definition": "simplex(objective,lines)", "description": "<p>Solution to the optimisation problem, found through the simplex&nbsp;method.</p>", "name": "sol"}, "points": {"group": "Ungrouped variables", "templateType": "anything", "definition": "repeat(\n  repeat(random(1..20),2),\n  num_points\n)", "description": "<p>Some random points uniformly distributed in a box</p>", "name": "points"}, "raw_lines": {"group": "Ungrouped variables", "templateType": "anything", "definition": "shuffle(map(\n  let(p1,hull[j],p2,hull[mod(j+1,len(hull))],\n    [p1,p2]\n  ),\n  j,\n  0..len(hull)-1\n))", "description": "<p>Each of the edges of the convex hull</p>", "name": "raw_lines"}, "basic_rows": {"group": "Ungrouped variables", "templateType": "anything", "definition": "simplex_find_basics(optimal_tableau)", "description": "<p>Which row each variable is basic in (or -1 if not basic)</p>", "name": "basic_rows"}, "num_points": {"group": "Ungrouped variables", "templateType": "anything", "definition": "5", "description": "<p>Number of points to generate</p>", "name": "num_points"}, "solution_feasible": {"group": "Ungrouped variables", "templateType": "anything", "definition": "abs(matrix(lines)*(vector(sol)+vector(repeat(0,len(sol)-1)+[-1])))<10^(-13)", "description": "<p>Are all the constraints satisfied? Multiply the solution vector by&nbsp;a matrix representing the lines, and subtract the right-hand sides. If any element of the result&nbsp;is non-zero, the solution is infeasible.</p>\n<p>This works in floating-point, so there's a margin of tolerance of 10^-13 to account for rounding errors. An infeasible solution would produce a value much bigger than that, closer to an integer</p>", "name": "solution_feasible"}, "optimal_tableau": {"group": "Ungrouped variables", "templateType": "anything", "definition": "simplex_optimal_tableau(objective,lines)", "description": "", "name": "optimal_tableau"}, "optimal_profit": {"group": "Ungrouped variables", "templateType": "anything", "definition": "sol[0]*objective[0] + sol[1]*objective[1]", "description": "<p>Value of the objective function at the optimal solution.</p>", "name": "optimal_profit"}, "objective": {"group": "Ungrouped variables", "templateType": "anything", "definition": "[random(1..10),random(1..10)]+repeat(0,len(lines))", "description": "<p>The objective function to be maximised - coefficients of each variable.</p>", "name": "objective"}, "hull": {"group": "Ungrouped variables", "templateType": "anything", "definition": "convex_hull(points)", "description": "<p>The convex hull of the generated points.</p>\n<p>It looks like about 50% of the time there are 4 points on the convex hull, when num_points=5.</p>", "name": "hull"}}, "ungrouped_variables": ["num_points", "points", "hull", "raw_lines", "lines", "objective", "sol", "optimal_profit", "optimal_tableau", "basic_rows", "solution_feasible"], "name": "Simplex method - 4 or 5 random inequalities", "functions": {"line_through_points": {"type": "list", "language": "javascript", "definition": "var dx = p2[0]-p1[0];\nvar dy = p2[1]-p1[1];\nvar g = dx==0 ? dy==0 ? 1 : Math.abs(dy) : dy==0 ? Math.abs(dx) : Numbas.math.gcd(Math.abs(dx),Math.abs(dy));\nvar c = dx*p1[1]-dy*p1[0]\ng = Numbas.math.gcd(g,Math.abs(c));\nvar a = -dy/g;\nvar b = dx/g;\nc = c/g;\nif(false && dx<0) {\n  a = -a;\n  b = -b;\n  c = -c;\n}\nvar line = [a,b];\nfor(var i=0;i<j;i++) {\n  line.push(0)\n}\nline.push(1);\nfor(var i=j+1;i<n;i++) {\n  line.push(0);\n}\nline.push(c);\nreturn line;", "parameters": [["p1", "list"], ["p2", "list"], ["j", "number"], ["n", "number"]]}, "show_points": {"type": "html", "language": "javascript", "definition": "var canvas = document.createElement('canvas');\ncanvas.setAttribute('width',400);\ncanvas.setAttribute('height',400);\nvar ctx = canvas.getContext('2d');\n\nfunction tx(x) {\n  return x*19+10;\n}\nfunction ty(y) {\n  return 400-y*19+10;\n}\n\nfunction draw() {\n  ctx.clearRect(0,0,400,400);\n\n  ctx.beginPath();\n  ctx.fillStyle = 'rgba(0,0,0,0.05)';\n  hull.forEach(function(p) {\n    ctx.lineTo(tx(p[0]),ty(p[1]));\n  });\n  ctx.closePath();\n  ctx.fill();\n\n\n  points.forEach(function(p,i) {\n    if(hull.indexOf(p)>=0) {\n      ctx.fillStyle ='rgba(0,0,0,1)';\n      ctx.fillRect(tx(p[0])-2.5,ty(p[1])-2.5,5,5);\n    } else {\n      ctx.fillStyle ='rgba(0,0,0,0.5)';\n      ctx.fillRect(tx(p[0])-1.5,ty(p[1])-1.5,3,3);\n    }\n  });\n  \n  hull.forEach(function(p,i) {\n    ctx.fillStyle = 'rgba(0,0,0,1)';\n    ctx.font = \"16px sans-serif\";\n    ctx.fillText(i, tx(p[0]), ty(p[1]));\n  });\n\n  var op = hull[hull.length-1];\n  ctx.strokeStyle = 'rgba(0,0,0,0.2)';\n  hull.forEach(function(p,i) {\n    var dx = (p[0]-op[0]);\n    var dy = (p[1]-op[1]);\n    if(dx<0) {\n      dx = -dx;\n      dy = -dy;\n    }\n    var m = dy/dx;\n    var c = p[1]-m*p[0];\n    ctx.moveTo(tx(0),ty(c));\n    ctx.lineTo(tx(20),ty(20*m+c));\n    op = p;\n  })\n  ctx.closePath();\n  ctx.stroke();\n  \n  ctx.fillStyle='rgba(0,0,255,1)';\n  ctx.fillRect(tx(solution[0])-2,ty(solution[1])-2,4,4);\n}\n\n\nvar frame = function() {\n  requestAnimationFrame(frame);\n  draw();\n}\nframe();\nreturn new Numbas.jme.types.THTML(canvas);\n", "parameters": [["points", "list"], ["hull", "list"], ["solution", "list"]]}, "lines_as_inequalities": {"type": "string", "language": "javascript", "definition": "var out = '\\\\begin{align} '\nvar olines = [];\nfor(var i=0;i<lines.length;i++) {\n  var a = lines[i][0];\n  var b = lines[i][1];\n  var c = lines[i][lines[i].length-1];\n  var op = c>=0 ? '\\\\leq' : '\\\\geq';\n  if(c<0) {\n    a = -a;\n    b = -b;\n    c = -c;\n  }\n  var expr = '('+a+')x1 + ('+b+')x2';\n  var latex = Numbas.jme.display.exprToLaTeX(expr,'all,!noLeadingMinus',Numbas.jme.builtinScope);\n  olines.push(latex+' &'+op+' '+Numbas.math.niceNumber(c));\n}\nolines.push('x_1, x_2 &\\\\geq 0');\nout += olines.join(' \\\\\\\\ ')+'\\\\end{align}'\nreturn out", "parameters": [["lines", "list"]]}}, "parts": [{"prompt": "<p>Use the optimal simplex tableau below to identify the optimal solution to the linear program.</p>\n<p>{simplex_final_tableau(objective,lines)}</p>\n<p>$x_1 = $&nbsp;[[0]]</p>\n<p>$x_2 = $&nbsp;[[1]]</p>", "customMarkingAlgorithm": "all_valid:\n  map(assert(x[\"valid\"], concat_feedback(x[\"feedback\"],1/len(gaps))), x, marked_original_order)\n\n\nx1: \n  interpreted_answers[0]\n\nx2: \n  interpreted_answers[1]\n\nconditions:\n  map(\n    line[0]*x1 + line[1]*x2 <= line[len(line)-1],\n    line,\n    lines\n  )\n\nconditions_unsatisfied:\n  assert(all(conditions),\n    incorrect(\"Your solution does not satisfy all of the conditions.\");\n    end();\n    true\n  )\n\nstudent_profit:\n  x1*objective[0] + x2*objective[1]\n\nprofit_optimal:\n  if(student_profit >= optimal_profit,\n    correct(\"Your solution is optimal.\")\n  ,\n    incorrect(\"There is another solution which gives a higher objective value.\")\n  )\n\n\nmark:\n  apply(all_valid);\n  apply(conditions_unsatisfied);\n  apply(profit_optimal)", "extendBaseMarkingAlgorithm": true, "useCustomName": false, "customName": "", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "gaps": [{"correctAnswerFraction": true, "customName": "", "allowFractions": true, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "sol[0]", "useCustomName": false, "maxValue": "sol[0]", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "showFeedbackIcon": false, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1, "mustBeReducedPC": 0}, {"correctAnswerFraction": true, "customName": "", "allowFractions": true, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "sol[1]", "useCustomName": false, "maxValue": "sol[1]", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "showFeedbackIcon": false, "scripts": {}, "notationStyles": ["plain", "en", "si-en"], "type": "numberentry", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1, "mustBeReducedPC": 0}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 0, "sortAnswers": false}, {"mustBeReduced": false, "maxValue": "optimal_profit", "useCustomName": false, "prompt": "<p>What is the value of the objective function for&nbsp;this solution?</p>", "showFractionHint": true, "correctAnswerStyle": "plain", "variableReplacementStrategy": "originalfirst", "showFeedbackIcon": true, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "correctAnswerFraction": true, "variableReplacements": [], "allowFractions": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "minValue": "optimal_profit", "customName": "", "unitTests": [], "scripts": {}, "showCorrectAnswer": true, "marks": 1, "mustBeReducedPC": 0}], "variablesTest": {"condition": "solution_feasible", "maxRuns": "100"}, "statement": "<p>You are asked to maximise the objective function $z(x_1,x_2) = \\simplify[all,!noLeadingMinus]{{objective[0]}*x1 + {objective[1]}*x2}$ subject to</p>\n<p>\\[ \\var{latex(lines_as_inequalities(lines))} \\]</p>", "tags": ["simplex"], "rulesets": {}, "preamble": {"css": "/* hide the feedback icons on the part a gaps */\n.parts > .part:nth-child(1) .part .feedback-icon {\n  display: none;\n}", "js": ""}, "type": "question", "extensions": ["optimisation"], "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Abstract simplex method question.&nbsp;Given optimal tableau, student must identify optimal solution and objective value.</p>"}, "advice": "<h4>a)</h4>\n<p>$x_1$ is basic in row {basic_rows[0]+1}, so its value in the optimal solution is $\\var{optimal_tableau[basic_rows[0]][len(lines)+2]}$.</p>\n<p>$x_2$ is basic in row {basic_rows[1]+1}, so its value in the optimal solution is $\\var{optimal_tableau[basic_rows[1]][len(lines)+2]}$.</p>\n<h4>b)</h4>\n<p>The objective function is $z(x_1,x_2) = \\simplify[all,!noLeadingMinus]{{objective[0]}*x1 + {objective[1]}*x2}$. Substituting in the values for $x_1$ and $x_2$ above, we have</p>\n<p>\\[ z(\\var{sol[0]},\\var{sol[1]}) =&nbsp;\\simplify[all,!collectNumbers,!noLeadingMinus]{{objective[0]}*{sol[0]} + {objective[1]}*{sol[1]}} = \\var{optimal_profit} \\]</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/"}]}