This question uses a Geogebra applet to solve a linear program with two variables using the graphical method. It contains three steps:
\nThe purpose of this question is to apply the graphical method to solve the following linear program.
\\begin{align}
\\text{Maximise } \\var{c}\\text{ subject to}\\\\
\\var{system}\\\\
x\\geq 0, y\\geq 0
\\end{align}
Plotting the problem will give us the following graph:
\n{final_plot}
\nWe can evaluate the objective at each of the vertices of the polygon:
\n{values}
\nFrom there we conclude that the optimal value is {cstar} and the solution is $\\var{xstar[0]}$ set is the segment $\\var{xstar}$.
", "rulesets": {}, "extensions": ["mygeogebra"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true, "j": false}, "constants": [], "variables": {"c": {"name": "c", "group": "Objective", "definition": "objective", "description": "", "templateType": "anything", "can_override": false}, "cstar": {"name": "cstar", "group": "Solution", "definition": "max(costs)", "description": "", "templateType": "anything", "can_override": false}, "edges": {"name": "edges", "group": "Constraints", "definition": "nonnegativity", "description": "", "templateType": "anything", "can_override": false}, "num_points": {"name": "num_points", "group": "polygon", "definition": "7", "description": "", "templateType": "anything", "can_override": false}, "points": {"name": "points", "group": "polygon", "definition": " if(forceorigin,[vector(0,0)],[]) + sort(repeat(\n vector([random(0..factor),random(0..factor)]),num_points\n ))", "description": "", "templateType": "anything", "can_override": false}, "vertices": {"name": "vertices", "group": "polygon", "definition": "map(v -> vector(v), quickhull(points))", "description": "", "templateType": "anything", "can_override": false}, "factor": {"name": "factor", "group": "polygon", "definition": "5//10", "description": "", "templateType": "anything", "can_override": false}, "Pol": {"name": "Pol", "group": "polygon", "definition": "//geogebra_applet(800,800,\n [\n \"points\": [\n \"definition\": vertices,\n \"visible\": true,\n \"line_thickness\": 1,\n \"label_visible\": false\n\n ],\n \"vertices\": [\n \"definition\": map(v -> vector(v), vertices),\n visible: true\n ],\n \"c(x,y)\":[\n \"definition\": \"-y\"\n ],\n \"lines\":[\n \"definition\": \"x>=0 &&y>=0 &&\"+join(map(s -> string(s), lines), \" && \"),\n visible: true,\n \"line_thickness\": 1,\n label_visible: false\n ],\n \"poly\": [\n \"definition\": \"Polygon(vertices)\"\n ]]\n//,[])", "description": "", "templateType": "anything", "can_override": false}, "slopes": {"name": "slopes", "group": "Constraints", "definition": "map( k -> vertices[mod(k+1,length(vertices))] - vertices[k], 0..length(vertices)-1)", "description": "", "templateType": "anything", "can_override": false}, "lhs": {"name": "lhs", "group": "Constraints", "definition": "map( v-> simplify(expression(\"{random(1..3)}*(-{v[1]}*x+{v[0]}*y)\"),['all','expandbrackets']), slopes)", "description": "", "templateType": "anything", "can_override": false}, "rhs": {"name": "rhs", "group": "Constraints", "definition": "map( [l,v] -> eval(l, ['x':v[0], 'y': v[1]]), zip(lhs, vertices))", "description": "", "templateType": "anything", "can_override": false}, "lines": {"name": "lines", "group": "Constraints", "definition": "shuffle(map( [_,l,r] -> expression(\"{l}<={r}\"), constraintpairs))", "description": "", "templateType": "anything", "can_override": false}, "system": {"name": "system", "group": "Constraints", "definition": "latex(show_system(lines, [\"all\"]))", "description": "", "templateType": "anything", "can_override": false}, "constraintpairs": {"name": "constraintpairs", "group": "Constraints", "definition": "filter( [s,l,r] -> r<>0 or s[0]*s[1] <> 0 , zip(slopes,lhs,rhs))", "description": "", "templateType": "anything", "can_override": false}, "costs": {"name": "costs", "group": "Objective", "definition": "map( v -> eval(objective, ['x':v[0], 'y': v[1]]),vertices)", "description": "", "templateType": "anything", "can_override": false}, "Xstar": {"name": "Xstar", "group": "Solution", "definition": "map( [v,c] -> v, filter( [v,c] -> c = cstar, zip(vertices, costs)))", "description": "", "templateType": "anything", "can_override": false}, "forceorigin": {"name": "forceorigin", "group": "polygon", "definition": "true", "description": "Force the origin (0,0) to be a feasible point.
", "templateType": "anything", "can_override": false}, "objective": {"name": "objective", "group": "Objective", "definition": "simplify(expression(\"{random(-5..5)}*x+{random(-5..5)}*y\"),['all'])", "description": "", "templateType": "anything", "can_override": false}, "lastconstraint": {"name": "lastconstraint", "group": "Interactions", "definition": "expression(\"x>=0\")", "description": "", "templateType": "anything", "can_override": false}, "nonnegativity": {"name": "nonnegativity", "group": "Constraints", "definition": "map(v -> expression(v + \">=0\"), [\n \"x\", \"y\"])", "description": "", "templateType": "anything", "can_override": false}, "final_Plot": {"name": "final_Plot", "group": "Solution", "definition": "geogebra_applet(800,800,\n [\n \"points\": [\n \"definition\": vertices,\n \"visible\": true,\n \"line_thickness\": 1,\n \"label_visible\": false\n\n ],\n \"vertices\": [\n \"definition\": map(v -> vector(v), vertices),\n visible: true\n ],\n \"c(x,y)\":[\n \"definition\": objective\n ],\n \"lines\":[\n \"definition\": \"x>=0 &&y>=0 &&\"+join(map(s -> string(s), lines), \" && \"),\n visible: true,\n \"line_thickness\": 1,\n label_visible: false\n ],\n \"poly\": [\n \"definition\": \"Polygon(vertices)\"\n ],\n \"Solutions\":[\n definition: Xstar\n ],\n \"A\":[\n definition: M,\n visible: false,\n ],\n \"value\": [\"definition\": \"c(A)\"],\n \"levelSet\": [\n \"definition\": safe(\"Element({c = value},1)\"),\n label_style: 2,\n caption: \"Level Set\",\n \"label_visible\": true\n ],\n \"P\": [\n \"definition\": \"UnitPerpendicularVector(levelSet)\",\n \"visible\": false\n ],\n \"up\": [\n \"definition\": \"Vector(A,A+P)\"\n ],\n \"Information\": [\n definition: \"Text(\\\"Objective Value: \\\"+value, (-4,3))\"\n ]\n ]\n,[])", "description": "", "templateType": "anything", "can_override": false}, "M": {"name": "M", "group": "Solution", "definition": "foldl( (x,y) -> x+y, Vector(0,0), Xstar)/length(Xstar)", "description": "", "templateType": "anything", "can_override": false}, "values": {"name": "values", "group": "Solution", "definition": "table(map([v,c]->[v[0],v[1],c],zip(vertices,costs)),[\"x\",\"y\",objective])", "description": "", "templateType": "anything", "can_override": false}, "graphwidth": {"name": "graphwidth", "group": "Interactions", "definition": "400", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "eval(objective, ['x':1, 'y': 0]) <> 0 or eval(objective, ['x':0, 'y': 1]) <> 0", "maxRuns": 100}, "ungrouped_variables": [], "variable_groups": [{"name": "polygon", "variables": ["forceorigin", "num_points", "factor", "points", "vertices", "Pol"]}, {"name": "Constraints", "variables": ["nonnegativity", "edges", "slopes", "lhs", "rhs", "constraintpairs", "lines", "system"]}, {"name": "Objective", "variables": ["objective", "c", "costs"]}, {"name": "Solution", "variables": ["cstar", "Xstar", "M", "final_Plot", "values"]}, {"name": "Interactions", "variables": ["lastconstraint", "graphwidth"]}], "functions": {"add_edges_applet": {"parameters": [["constraints", "list of expression"], ["part_path", "string"]], "type": "ggbapplet", "language": "jme", "definition": "geogebra_applet(graphwidth,graphwidth,\n [\n \"newconstraint\": [\n definition: lastconstraint,\n label_visible: true,\n label_style: 2,\n line_thickness: 2,\n visible: true,\n color: \"#ff0000\"\n ],\n \"p\": [\n \"definition\": join(map(s -> string(s), constraints), \" && \"),\n \"visible\": true,\n \"line_thickness\": 1,\n \"label_visible\": false\n ]\n ],\n [\n [\"newconstraint\",part_path]\n ]\n)"}, "add_objective_applet": {"parameters": [["edges", "list of expression"], ["c", "expression"], ["part_path", "string"]], "type": "ggbapplet", "language": "jme", "definition": "geogebra_applet(graphwidth,graphwidth,\n [\n \"p\": [\n \"definition\": join(map(s -> string(s), edges), \" && \"),\n \"visible\": true,\n \"line_thickness\": 1,\n \"label_visible\": false\n\n ],\n \"A\": [\n \"definition\": vector(0,0),\n \"label_visible\": false,\n \"visible\": true\n ],\n \"c(x,y)\": [\"definition\": \"y\",\n \"visible\": false],\n \"value\": [\"definition\": \"c(A)\"],\n \"ctmp(x,y)\": [\n \"definition\": \"If(c(1,0)==c(2,0) && c(0,1)==c(0,2),x, c)\",\n \"visible\": false\n ],\n \"eq\": [\n \"definition\": safe(\"Element({ctmp = value},1)\"),\n \"visible\": true,\n \"label_visible\": false\n ],\n \"P\": [\n //\"definition\": \"Vector((0,0))\",\n //\"definition\": \"UnitPerpendicularVector(eq)\",\n \"definition\": \"If(c(1,0)==c(2,0) && c(0,1)==c(0,2), Vector((0,0)), UnitPerpendicularVector(eq))\",//A+(x(eq),y(eq))\",\n \"visible\": false\n ],\n \"up\": [\n \"definition\": \"Vector(A,A+P)\"\n ]\n ],\n [ \n [\"c(x,y)\",part_path]\n ]\n)"}, "find_solution_applet": {"parameters": [["edges", "list of expression"], ["c", "expression"], ["part_path", "string"]], "type": "ggbapplet", "language": "jme", "definition": "geogebra_applet(graphwidth,graphwidth,\n [\n \"p\": [\n \"definition\": join(map(s -> string(s), edges), \" && \"),\n \"visible\": true,\n \"line_thickness\": 1,\n \"label_visible\": false\n\n ],\n \"A\": [\n \"definition\": vector(0,0),\n \"label_visible\": false,\n \"visible\": true\n ],\n \"c(x,y)\": [\"definition\": c],\n \"value\": [\"definition\": \"c(A)\"],\n \"eq\": [\n \"definition\": safe(\"Element({c = value},1)\"),\n label_style: 2,\n caption: \"Level Set\",\n \"label_visible\": true\n ],\n \"P\": [\n \"definition\": \"UnitPerpendicularVector(eq)\",//A+(x(eq),y(eq))\",\n \"visible\": false\n ],\n \"Information\": [\n definition: \"Text(\\\"Objective Value: \\\"+value, (-4,3))\"\n ],\n \"up\": [\n \"definition\": \"Vector(A,A+P)\"\n ]\n ],\n [ \n [\"A\",part_path]\n ]\n)"}, "quickhull": {"parameters": [["points", "list of vector"]], "type": "list", "language": "javascript", "definition": "function comparepoints(x,y){\n return x[0]>y[0] || (x[0]==y[0] && x[1]>y[1])\n}\n\nfunction different(x,y){\n return (x[0] !== y[0]) && (x[1] !== y[1])\n}\n\nfunction signedarea(T){\n var ab, ac;\n [_,ab,ac] = T.map(x => [x[0]-T[0][0], x[1]-T[0][1]])\n //console.debug(ab, ac)\n return ab[0]*ac[1] - ab[1]*ac[0]\n}\n\nfunction area(T){\n return Math.abs(signedarea(T))\n}\n\nfunction distance(S,x){\n return signedarea(S.concat([x]))\n}\n\nfunction inside(z,T){\n var triangles = T.map(x => T.filter(y => different(x,y)).concat(z))\n var areas = triangles.map(area)\n return areas.reduce( (x,y) => x+y, 0) == area(T)\n}\n\nfunction addpoints(S, points){\n var pospoints = points.filter(x => distance(S,x) > 0)\n var addedpoints = []\n \n if(pospoints.length > 0){\n /* Find furthest point from the segment */\n var newpoint = pospoints.sort((x,y) => distance(S,x) < distance(S,y))[0]\n addedpoints = addedpoints.concat(addpoints([S[0],newpoint], pospoints))\n addedpoints = addedpoints.concat([newpoint])\n addedpoints = addedpoints.concat(addpoints([newpoint,S[1]], pospoints))\n\n }\n return addedpoints\n}\n\n/* Start by finding the points with the smallest and largest x values. */\nvar spoints = points.sort(comparepoints)\nvar vertices = []\nvar vertices = [spoints[0], spoints[spoints.length - 1]]\nvar segment = [spoints[0], spoints[spoints.length - 1]]\n\nvar newpoints = [segment[0]]\nnewpoints = newpoints.concat(addpoints(segment, spoints))\nnewpoints = newpoints.concat( [segment[1]])\nnewpoints = newpoints.concat(addpoints([segment[1],segment[0]],spoints))\n\n\n//newpoints = \n\n/* Now we loop through the vertices.*/\n\nreturn newpoints"}, "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\"))\nreturn \"\\\\begin{aligned}\"+alignedstrings.join(\"\\\\\\\\\")+\"\\\\end{aligned}\"\n}\nreturn \"\\\\begin{gathered}\"+strings.join(\"\\\\\\\\\")+\"\\\\end{gathered}\""}, "isfeasible": {"parameters": [["x", "matrix"], ["constraints", "list of expression"]], "type": "boolean", "language": "jme", "definition": "all( map(c -> eval(c, ['x':x[0][0], 'y': x[1][0]]), constraints))"}}, "preamble": {"js": "", "css": "div.plot, div.added-constraints{\n display: inline-block;\n margin: 0;\n}\n\ndiv.added-constraints{\n padding-left: 1em;\n}\n\ndiv.show-output{display: flex;\n align-items: start}\n\np.system{\n text-align: center;\n}"}, "parts": [{"type": "jme", "useCustomName": true, "customName": "Add an edge", "marks": "0", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": false, "showFeedbackIcon": false, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Include constraint and add another edge", "rawLabel": "Include constraint and add another edge", "otherPart": 0, "variableReplacements": [{"variable": "edges", "definition": "edges+[interpreted_answer]"}, {"variable": "lastconstraint", "definition": "interpreted_answer"}], "availabilityCondition": "answered", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}, {"label": "Include constraint and add the objective", "rawLabel": "Include constraint and add the objective", "otherPart": 1, "variableReplacements": [{"variable": "edges", "definition": "edges+[interpreted_answer]"}], "availabilityCondition": "answered", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}, {"label": "Add the objective without including additional constraint", "rawLabel": "Add the objective without including additional constraint", "otherPart": 1, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "{add_edges_applet(edges,part_path)}
\nThe constraints added to the system are: {show_system(edges, ['all'])}
\nWrite the constraint below and click on submit to visualise it on the graph. To add it to the system, select one of the options below.
", "answer": "x>=0", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": [{"name": "x", "value": ""}]}, {"type": "jme", "useCustomName": true, "customName": "Add the objective", "marks": "0", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": false, "showFeedbackIcon": false, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Find the solution", "rawLabel": "Find the solution", "otherPart": 2, "variableReplacements": [{"variable": "c", "definition": "interpreted_answer"}], "availabilityCondition": "answered", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "{add_objective_applet(edges,c,part_path)}
\nThe feasible set is displayed on the graph and is determined by the system: {show_system(edges, ['all'])}
\nEnter your objective function, and click on submit to display one of its level sets. You can drag the point around the area to visualise the other level sets of the function.
\nTo accept this function as the objective of your system, select the option below.
", "answer": "{c}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "matrix", "useCustomName": true, "customName": "Find the solution", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "objectivevalue (Get the objective value at the student's response):\n eval(objective, ['x':studentMatrix[0][0], 'y': studentMatrix[1][0]])\n\ncheckvalue (Compare the value of the objective at the student's answer against the optimal one):\n if(objectivevalue <> cstar, incorrect(\"You did not find the optimal solution\"), correct(\"Your answer is correct\"))\n\nfeasible (check that the answer is feasible):\n assert(isfeasible(studentMatrix, lines + nonnegativity), incorrect(\"Your solution is not feasible.\"); end())\n\nmark:\n apply(any_empty);\n apply(any_invalid);\n assert(settings[\"precisionType\"]=\"none\" and not settings[\"allowFractions\"], apply(all_same_precision));\n apply(wrong_size);\n apply(feasible);\n apply(objectivevalue);\n apply(checkvalue)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "{find_solution_applet(edges,c,part_path)}
\nThe plot represents the following problem:
\nMaximise $\\var{c}$ subject to {show_system(edges, ['all'])}
\nFind the solution to the problem using the graphical method.
", "correctAnswer": "Xstar[0]", "correctAnswerFractions": false, "numRows": "2", "numColumns": 1, "allowResize": false, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}], "partsMode": "explore", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "when-active", "penaltyVisibility": "when-active", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}