// Numbas version: finer_feedback_settings {"name": "Simplex Method", "extensions": ["geogebrax"], "custom_part_types": [{"source": {"pk": 309, "author": {"name": "Julien Ugon", "pk": 3575}, "edit_page": "/part_type/309/edit"}, "name": "labelled cells", "short_name": "prepended-cells", "description": "
Ask students for a vector of values, with some pre-specified text appearing in front.
", "help_url": "", "input_widget": "matrix", "input_options": {"correctAnswer": "settings[\"correctAnswer\"]", "hint": {"static": true, "value": ""}, "allowResize": {"static": true, "value": false}, "numRows": {"static": false, "value": "numrows(settings[\"correctAnswer\"])"}, "numColumns": {"static": true, "value": 1}, "parseCells": {"static": true, "value": true}, "allowedNotationStyles": {"static": true, "value": ["plain", "en", "si-en"]}, "allowFractions": {"static": true, "value": true}, "showBrackets": {"static": true, "value": false}, "rowHeaders": {"static": false, "value": "settings[\"labels\"]"}, "columnHeaders": {"static": true, "value": []}, "prefilledCells": {"static": false, "value": "[ [ ] ]"}, "gridlinesRows": {"static": false, "value": "[ ]"}, "gridlinesColumns": {"static": false, "value": "[ ]"}}, "can_be_gap": true, "can_be_step": true, "marking_script": "mark:\nif(len(correct_cells)=len(cell_indexes),\n correct()\n, incorrect(); end()\n)\n\ninterpreted_answer:\n studentAnswer\n\ncell_indexes:\n product(list(0..rows-1), [0])\n\nrows:\nlen(studentAnswer)\n\nstudentnumbers:\n list(studentAnswer)\n\ncorrect_cells:\n filter(\n withintolerance(interpreted_answer[p[0]][p[1]], settings[\"correctAnswer\"][p[0]][p[1]], settings['tolerance']),\n p, \n cell_indexes\n )", "marking_notes": [{"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "if(len(correct_cells)=len(cell_indexes),\n correct()\n, incorrect(); end()\n)"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": " studentAnswer"}, {"name": "cell_indexes", "description": "The index of each cell in the student's answer", "definition": " product(list(0..rows-1), [0])"}, {"name": "rows", "description": "
The number of rows in the student's answer", "definition": "len(studentAnswer)"}, {"name": "studentnumbers", "description": "", "definition": " list(studentAnswer)"}, {"name": "correct_cells", "description": "
The indexes of the cells which are correct", "definition": " filter(\n withintolerance(interpreted_answer[p[0]][p[1]], settings[\"correctAnswer\"][p[0]][p[1]], settings['tolerance']),\n p, \n cell_indexes\n )"}], "settings": [{"name": "correctAnswer", "label": "Correct Answer", "help_url": "", "hint": "Enter the correct answer here.", "input_type": "code", "default_value": "", "evaluate": true}, {"name": "labels", "label": "Labels", "help_url": "", "hint": "Enter the labels for each row.", "input_type": "code", "default_value": "", "evaluate": true}, {"name": "tolerance", "label": "Tolerance", "help_url": "", "hint": "Up to how many decimal places for correct answer.", "input_type": "code", "default_value": "0.01", "evaluate": true}], "public_availability": "restricted", "published": false, "extensions": []}, {"source": {"pk": 300, "author": {"name": "Julien Ugon", "pk": 3575}, "edit_page": "/part_type/300/edit"}, "name": "tableau", "short_name": "tableau", "description": "
A simplex tableau
", "help_url": "", "input_widget": "matrix", "input_options": {"correctAnswer": "settings[\"correctAnswer\"]", "hint": {"static": true, "value": ""}, "allowResize": {"static": true, "value": false}, "numRows": {"static": false, "value": "let(M,settings[\"correctAnswer\"],\n numrows(M))"}, "numColumns": {"static": false, "value": "let(M,settings[\"correctAnswer\"],\n numcolumns(M))"}, "parseCells": {"static": true, "value": true}, "allowedNotationStyles": {"static": true, "value": ["en", "si-en"]}, "allowFractions": {"static": true, "value": true}, "showBrackets": {"static": true, "value": false}, "rowHeaders": {"static": false, "value": "let(\n variables, settings[\"variables\"],\n basis, settings[\"basis\"],\n [\"\"] + map( k -> variables[k], basis))"}, "columnHeaders": {"static": false, "value": "settings[\"variables\"]"}, "prefilledCells": {"static": false, "value": "settings['prefilled_cells']"}, "gridlinesRows": {"static": false, "value": "[ ]"}, "gridlinesColumns": {"static": false, "value": "[ ]"}}, "can_be_gap": true, "can_be_step": true, "marking_script": "mark:\n apply(normdiff);\n if(normdiffThe purpose of this activity is to guide the student to understand how the simplex method works, and to then show how it can be applied through the method of tableaux. The focus is on understanding the mechanisms.
\nA random linear program with two variables is generated. This allows the student to visualise what happens as he applies the steps of the simplex method.
\nIt comprises four parts:
\nFirst we get the student to visually inspect the feasible polygon and move the point along its edges. The coefficients of the objective along each edge are shown, so they can see which edge provides an ascent direction, and which edge provides a descent direction. The student can then move the solution along edges until they reach an optimal point.
\nIn this part, we introduce the student to the steps of the simplex method, by applying algebraic techniques they are familiar with, namely variable substitution.
\nFirst, the student is asked to rewrite the constraints and the objective as equality constraints (for each constraint, a slack variable is added and an extra variable is added for the objective). This gives them an underdetermined linear system.
\nThen, the student is guided through a sequence of substitution steps, where they choose which variable to substitute into the equations, and which equation to use to construct the substitution. Once the substitution is done, the student is then shown that this yields a solution at a different vertex of the polygon, and they can repeat the operation until the solution they have found is optimal.
\nBy the end of this part, the student should have a good understanding of how the simplex algorithm works, as repeated application of operations like substitution/elimination, and why the pivot is chosen as it is.
\nThe last part repeats the operations in the first part, but using the method of tableaux. The student is first asked to generate their tableau, from the linear equations they obtained at the start of Part 2. They will see that this is nothing but an augmented matrix.
\nThen, the student is guided through a series of elimination steps. This is the simplex method as it is conventionally applied. The operation is repeated until a solution is attained.
\nOnce the student has completed all parts, they are led to a summary of what they did, to recapitulate the process they went through.
", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "\n", "advice": "", "rulesets": {}, "extensions": ["geogebrax"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true, "j": false}, "constants": [], "variables": {"forceorigin": {"name": "forceorigin", "group": "polygon", "definition": "true", "description": "Set this to true to make sure that the point (0,0) is a vertex of the feasible set. In general this should be set true, as the way this question is set up, it won't work unless the origin is feasible.
", "templateType": "anything", "can_override": false}, "num_points": {"name": "num_points", "group": "polygon", "definition": "7", "description": "Upper bound for the number of vertices of the feasible region of the LP.
", "templateType": "number", "can_override": true}, "factor": {"name": "factor", "group": "polygon", "definition": "5", "description": "Scaling factor for the random generator of the coordinates of the vertices.
", "templateType": "number", "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": "The feasible region is the convex hull of the selected points in this variable.
", "templateType": "anything", "can_override": false}, "vertices": {"name": "vertices", "group": "polygon", "definition": "map(v -> vector(v), quickhull(points))", "description": "Vertices of the feasible region of the linear program. Obtained by finding the convex hull of the points in `points`.
\nNote that the vertices are in clockwise order, which will make finding the edges easier.
", "templateType": "anything", "can_override": false}, "nonnegativity": {"name": "nonnegativity", "group": "Constraints", "definition": "map(v -> expression(\"{v}>=0\"), mainvars)", "description": "Nonnegativity constraints.
", "templateType": "anything", "can_override": false}, "lhs": {"name": "lhs", "group": "Constraints", "definition": "map( c -> formula_from_vector(c,mainvars), list(A))", "description": "Left Hand Side of the constraints defining the edges, as linear equations.
", "templateType": "anything", "can_override": false}, "rhs": {"name": "rhs", "group": "Constraints", "definition": "map(k->tlines[k][1],order)", "description": "Right Hand Side of the constraints defining the edges.
", "templateType": "anything", "can_override": false}, "lines": {"name": "lines", "group": "Constraints", "definition": "map( [l,r] -> expression(\"{l}<={r}\"), zip(lhs,rhs))// + nonnegativity", "description": "Linear Constraints defining the feasible region.
", "templateType": "anything", "can_override": false}, "system": {"name": "system", "group": "Constraints", "definition": "latex(show_system(lines, [\"all\",\"aligned\"]))", "description": "A LaTeX representation of the constraints.
", "templateType": "anything", "can_override": false}, "ccoefs": {"name": "ccoefs", "group": "Objective", "definition": "vector(repeat(random(1..5),2))", "description": "coefficients of the objective.
", "templateType": "anything", "can_override": false}, "objective": {"name": "objective", "group": "Objective", "definition": "simplify(expression(\"{ccoefs[0]}*x+{ccoefs[1]}*y\"),['all'])", "description": "Objective function to maximise.
", "templateType": "anything", "can_override": false}, "costs": {"name": "costs", "group": "Solution", "definition": "map( v -> eval(objective, ['x':v[0], 'y': v[1]]),vertices)", "description": "Objective value at each vertex.
", "templateType": "anything", "can_override": false}, "cstar": {"name": "cstar", "group": "Solution", "definition": "max(costs)", "description": "Optimal cost
", "templateType": "anything", "can_override": false}, "Xstar": {"name": "Xstar", "group": "Solution", "definition": "map( [v,c] -> v, filter( [v,c] -> c = cstar, zip(vertices, costs)))", "description": "Extreme points of the solution set. The convex hull of these points is the optimal set.
", "templateType": "anything", "can_override": false}, "gfinal": {"name": "gfinal", "group": "Geogebra Applet and other displayed variables", "definition": "geogebra_applet(\"https://www.geogebra.org/m/tgsutwen\",\nparameters+[\"X\":[\"definition\": X, \"fixed\": true]]\n)", "description": "", "templateType": "anything", "can_override": false}, "parameters": {"name": "parameters", "group": "Geogebra Applet and other displayed variables", "definition": "[\n \"Vertices\": [\n \"definition\": map(v -> vector(v), vertices),\n ],\n \"c\": [ \"definition\": 3/length(ccoefs)*ccoefs ],\n \"order\": [\"definition\": order],\n] ", "description": "Parameters of the problem to be passed to the geogebra applet.
", "templateType": "anything", "can_override": false}, "equality_with_slacks": {"name": "equality_with_slacks", "group": "Equality Constrained System", "definition": "let(eqlhs, map( c -> formula_from_vector(c,variables), list(M)),\nmap([l,r] -> expression(\"{l}={r}\"), zip(eqlhs,rhs)))", "description": "The constraints transformed into equality constraints by adding slack variables.
", "templateType": "anything", "can_override": false}, "slacks": {"name": "slacks", "group": "Equality Constrained System", "definition": "map(k->\"s_{k}\", 1..numrows(A))", "description": "The names of the slack variables.
", "templateType": "anything", "can_override": false}, "student_constraints": {"name": "student_constraints", "group": "Interactions", "definition": "[]", "description": "List of equality constraints added by the student. This is a placeholder. Initially empty, but will gradually fill up with each part (and replacement).
", "templateType": "anything", "can_override": false}, "student_system": {"name": "student_system", "group": "Interactions", "definition": "latex(show_system(student_constraints + map(k->expression(\"\"),length(student_constraints)..length(lines)), [\"all\",\"aligned\"]))", "description": "The system obtained from the student's input.
", "templateType": "anything", "can_override": false}, "k": {"name": "k", "group": "Interactions", "definition": "0", "description": "Index of the inequality currently being converted to an equality constraint. This value is updated by a variable replacement as the student progresses through the question.
", "templateType": "anything", "can_override": false}, "equality_system": {"name": "equality_system", "group": "Equality Constrained System", "definition": "latex(show_system(equality_with_slacks, [\"all\",\"aligned\"]))", "description": "The constraint set rewritten as equality constraints, with slack variables.
", "templateType": "anything", "can_override": false}, "X": {"name": "X", "group": "Interactions", "definition": "Vector([0,0])", "description": "The solution $(x,y)$ at the current iterate.
", "templateType": "anything", "can_override": false}, "solution": {"name": "solution", "group": "Interactions", "definition": "dict(zip(varnames + slacks, solution_vector))", "description": "the full solution, including the values of the slack variables, at the current iterate.
", "templateType": "anything", "can_override": false}, "solution_vector": {"name": "solution_vector", "group": "Interactions", "definition": "vector(X + list((vector(rhs) - A*X)))//[solution['x'], solution['y']] + map( k -> solution['s_{k+1}'], 0..length(lines)-1)", "description": "The current solution as a vector.
", "templateType": "anything", "can_override": false}, "shown_system": {"name": "shown_system", "group": "Geogebra Applet and other displayed variables", "definition": "system", "description": "The system shown to the student at each part of the question. This will be updated using the variable replacement rules.
", "templateType": "anything", "can_override": false}, "M": {"name": "M", "group": "Equality Constrained System", "definition": "augment(A, Id(numrows(A)))", "description": "The constraint matrix, augmented with slack variables.
", "templateType": "anything", "can_override": false}, "T": {"name": "T", "group": "Simplex Formulation System", "definition": "augment(Ms,transpose(matrix(rhs)))", "description": "The simplex tableau, as a matrix. Top left block are the constraints. Last column are the values of the slack variables, last row are the coefficients for the (transformed) objective.
", "templateType": "anything", "can_override": false}, "base_index": {"name": "base_index", "group": "Pivoting", "definition": "list(2..length(slacks)+1)", "description": "The indices of the current basic variables. This gets updated as the student progresses through the simplex algorithm.
", "templateType": "anything", "can_override": false}, "fixed_variables": {"name": "fixed_variables", "group": "Pivoting", "definition": "filter(x->not (x in basic_variables), variables)", "description": "list of non-basic variables, as a list of expressions.
", "templateType": "anything", "can_override": false}, "nonbasetext": {"name": "nonbasetext", "group": "Pivoting", "definition": "join(map(s->\"$\"+latex(s)+\"=0$\",fixed_variables),\" and \")", "description": "Text to display that the values of the non-basic variables are all 0.
", "templateType": "anything", "can_override": false}, "variables": {"name": "variables", "group": "Equality Constrained System", "definition": "map(x->expression(x),varnames+slacks)", "description": "All the variables in the problem, including slack variables.
", "templateType": "anything", "can_override": false}, "basic_variables": {"name": "basic_variables", "group": "Pivoting", "definition": "map(k->variables[k],base_index)", "description": "List of basic variables, as a list of expressions.
", "templateType": "anything", "can_override": false}, "cost_vector": {"name": "cost_vector", "group": "Simplex Formulation System", "definition": "vector(list(ccoefs) + repeat(0,length(slacks)))", "description": "The cost vector at the current simplex iteration, augmented with 0 coefficients for the slack variables.
", "templateType": "anything", "can_override": false}, "entering_variable": {"name": "entering_variable", "group": "Pivoting", "definition": "variables[pj]", "description": "Symbol of the variable entering the base.
", "templateType": "anything", "can_override": false}, "leaving_variable": {"name": "leaving_variable", "group": "Pivoting", "definition": "basic_variables[pk]", "description": "Symbol of the variable leaving the base.
", "templateType": "anything", "can_override": false}, "ratios": {"name": "ratios", "group": "Pivoting", "definition": "map(r -> r[-1]/r[pj], list(T)[0..length(basic_variables)])", "description": "Ratio of the right hand side (last column of T) to the coefficient of the entering variable in that row.
", "templateType": "anything", "can_override": false}, "pj": {"name": "pj", "group": "Pivoting", "definition": "indices(T[-1],min_cost)[0]", "description": "Index of the variable entering the base
", "templateType": "anything", "can_override": false}, "pk": {"name": "pk", "group": "Pivoting", "definition": "indices(max_increases,max_increase)[0]", "description": "index of the variable leaving the base.
", "templateType": "anything", "can_override": false}, "varnames": {"name": "varnames", "group": "polygon", "definition": "[\"x\",\"y\"]", "description": "The names of the main variables in the linear program. Typically, x and y, but possibly could be $x_1$ and $x_2$ if one wanted?
", "templateType": "anything", "can_override": true}, "mainvars": {"name": "mainvars", "group": "polygon", "definition": "map(z->expression(z),varnames)", "description": "The main variables of the linear program, as expressions.
", "templateType": "anything", "can_override": false}, "order": {"name": "order", "group": "Constraints", "definition": "shuffle(0..length(tlines)-1)", "description": "Order in which the constraints are presented in the system.
", "templateType": "anything", "can_override": false}, "tdir": {"name": "tdir", "group": "Constraints", "definition": "map( k -> normal(vertices[mod(k+1,length(vertices))]- vertices[k]), 0..length(vertices)-1)", "description": "Normal vectors to the edges of the polytope, taken in clockwise order, starting from (0,0) and ending at (0,0).
", "templateType": "anything", "can_override": false}, "tlines": {"name": "tlines", "group": "Constraints", "definition": "filter( [u,a] -> a <>0 or u[0]*u[1] <> 0, map(\n [u,v] -> let(\n f,random(1..3),\n [f*u,f*dot(u,v)]),zip(tdir,vertices)))", "description": "The normal vectors and right hand side for every edge of the polytope, with the edges along either axis excluded (since those edges are already described by the nonnegativity constraints).
", "templateType": "anything", "can_override": false}, "A": {"name": "A", "group": "Constraints", "definition": "matrix(map(k->tlines[k][0],order))", "description": "Right hand side of the constraints for the linear program (which will minimise a linear function subject to constraints $Ax≤b$).
", "templateType": "anything", "can_override": false}, "cost_variable": {"name": "cost_variable", "group": "Simplex Formulation System", "definition": "expression(\"z\")", "description": "A variable name for the cost. The LP will be rewritten as:
\n\\begin{gather}
\\text{maximise }z\\text{ s.t.}\\\\
Mx=b\\\\
x≥0
\\end{gather}
with M now including the former objective as a constraint involving $z$.
", "templateType": "anything", "can_override": false}, "Ms": {"name": "Ms", "group": "Simplex Formulation System", "definition": "stack(M,Matrix(-cost_vector + [1]))", "description": "The constraint matrix for the LP, rewritten to use equality constraints (with slack variables) and a single variable ($z$, or whichever name is used in cost_variable) to maximise.
Linear constraints capturing the entire system, as a set of equations.
", "templateType": "anything", "can_override": false}, "simplex_system": {"name": "simplex_system", "group": "Simplex Formulation System", "definition": "latex(show_system(simplex_constraints, [\"all\",\"aligned\"]))", "description": "A LaTeX representation of the linear system capturing the linear program we are trying to solve.
", "templateType": "anything", "can_override": false}, "sub_nonbasic_variables": {"name": "sub_nonbasic_variables", "group": "Simplex Formulation System", "definition": "map(s -> simplify(substitute(dict(map(v -> [v,0],map(w -> \"{w}\", fixed_variables))),s),['all']),simplex_constraints)", "description": "Values of the basic variables, at the current solution (as given by setting the basic variables to 0).
", "templateType": "anything", "can_override": false}, "simplex_system_subbed": {"name": "simplex_system_subbed", "group": "Simplex Formulation System", "definition": "latex(show_system(sub_nonbasic_variables, [\"all\",\"aligned\"]))", "description": "A LaTeX representation of the values of the basic variables.
", "templateType": "anything", "can_override": false}, "min_cost": {"name": "min_cost", "group": "Pivoting", "definition": "min(T[-1])", "description": "the smallest coefficient (most negative) in the last column of the simplex tableau. This will correspond to the variable entering the base.
", "templateType": "anything", "can_override": false}, "max_increases": {"name": "max_increases", "group": "Pivoting", "definition": "map(r -> if(r>0,r,infinity),ratios)", "description": "Maximum value that the variable entering the base can attain, to keep each base variable nonnegative. It is either equal to the ratio (if positive), or infinite. Note that the ratio can never be 0.
", "templateType": "anything", "can_override": false}, "max_increase": {"name": "max_increase", "group": "Pivoting", "definition": "min(max_increases)", "description": "the maximal increase that the variable entering the base can reach at this iteration. This will be the minimum value among all the (positive) ratios contained in max_increases.
The value of the variable we are going to substitute away from all other constraints.
", "templateType": "anything", "can_override": false}, "substitution_line": {"name": "substitution_line", "group": "Pivoting", "definition": "-T[pk]/T[pk][pj]", "description": "We are going to add a multiple of this line to the rows of T (aside from the row of the pivot).
", "templateType": "anything", "can_override": false}, "Tupdate": {"name": "Tupdate", "group": "Pivoting", "definition": "matrix(map(\n [k,r] -> \n if(k<>pk,\n r[pj]*substitution_line+vector(r),\n -substitution_line),\n enumerate(list(T))))", "description": "The new simplex tableau, after applying an elimination step (ie, the next iteration of the simplex method).
", "templateType": "anything", "can_override": false}, "updated_constraints": {"name": "updated_constraints", "group": "Pivoting", "definition": "let(\n eqlhs, map( c -> formula_from_vector(c,variables + [cost_variable]), list(Tupdate)),\n eqrhs, map( c -> c[-1], list(Tupdate)), \n map([l,r] -> expression(\"{l}={r}\"), zip(eqlhs,eqrhs))\n)", "description": "The constraints corresponding to the updated simplex tableau.
", "templateType": "anything", "can_override": false}, "student_simplex_constraints": {"name": "student_simplex_constraints", "group": "Interactions", "definition": "[]", "description": "List of constraints entered by the student when they rewrite the linear system using variable substitutions (ie, when they are applying one step of the simplex method). This is initially empty and will be gradually filled as the student progresses through the question.
", "templateType": "anything", "can_override": false}, "student_simplex_equations": {"name": "student_simplex_equations", "group": "Interactions", "definition": "let(\n nc, length(student_simplex_constraints), // nc is the number of constraints entered by the student so far.\n if(ncstudent_simplex_constraints.", "templateType": "anything", "can_override": false}, "student_simplex_system": {"name": "student_simplex_system", "group": "Interactions", "definition": "latex(show_system(student_simplex_equations,[\"all\",\"aligned\"]))", "description": "The student's update of the linear system during a simplex operation, gradually updated from student_simplex_equations and student_simplex_constraints.
indices of the new basic variables in the updated simplex tableau.
", "templateType": "anything", "can_override": false}, "new_values": {"name": "new_values", "group": "Pivoting", "definition": "dict(map([var,val] -> [\"{var}\",val[-1]], zip(basic_variables,T[0..-1])) + map( var -> [\"{var}\",0], fixed_variables))", "description": "the values of all the variables at the solution represented in the current simplex tableau.
", "templateType": "anything", "can_override": false}, "S": {"name": "S", "group": "Pivoting", "definition": "vector([new_values['x'],new_values['y']])", "description": "the solution (without slack variables) represented by the current simplex tableau.
", "templateType": "anything", "can_override": false}, "is_optimal": {"name": "is_optimal", "group": "Pivoting", "definition": "T[-1][-1] = cstar", "description": "whether the current simplex tableau is at an optimal solution.
", "templateType": "anything", "can_override": false}, "Taugmented": {"name": "Taugmented", "group": "Pivoting", "definition": "augment(T,transpose(matrix(max_increases)))//augment(T[0..numrows(T)-1],transpose(matrix(max_increases)))", "description": "The current simplex tableau, augmented with one column of ratios (when positive) or ∞ (when ratio is negative).
", "templateType": "anything", "can_override": false}, "is_next_optimal": {"name": "is_next_optimal", "group": "Pivoting", "definition": "not some(map(v->v<0,list(Tupdate[-1][0..length(variables)])))", "description": "whether the next iteration of the simplex method yields the optimal solution.
", "templateType": "anything", "can_override": false}, "T_as_html": {"name": "T_as_html", "group": "Simplex Formulation System", "definition": "table(list(T),map(v->\"$\"+\"{v}\"+\"$\",variables + [cost_variable]) + [\"RHS\"], map(v->\"$\"+\"{v}\"+\"$\",basic_variables + [\"z\"]))", "description": "", "templateType": "anything", "can_override": false}, "test": {"name": "test", "group": "Ungrouped variables", "definition": "map(k -> if(k=pk,\n map(j -> if(j=pj,\"1\",\"\"), 0..numcolumns(Tupdate)),\n map(j -> if(j=pj,\"0\",\"\"), 0..numcolumns(Tupdate))),\n 0..numrows(Tupdate))", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "length(filter(x->x[0]=0, vertices)) >= 2 && length(filter(x->x[1]=0, vertices)) >= 2", "maxRuns": 100}, "ungrouped_variables": ["test"], "variable_groups": [{"name": "polygon", "variables": ["forceorigin", "num_points", "factor", "points", "vertices", "varnames", "mainvars"]}, {"name": "Constraints", "variables": ["nonnegativity", "tdir", "tlines", "order", "A", "rhs", "lhs", "lines", "system"]}, {"name": "Objective", "variables": ["ccoefs", "objective"]}, {"name": "Solution", "variables": ["costs", "cstar", "Xstar"]}, {"name": "Interactions", "variables": ["student_constraints", "student_system", "k", "X", "solution", "solution_vector", "student_simplex_constraints", "student_simplex_equations", "student_simplex_system"]}, {"name": "Pivot", "variables": []}, {"name": "Rewriting System", "variables": []}, {"name": "Equality Constrained System", "variables": ["slacks", "variables", "M", "equality_with_slacks", "equality_system"]}, {"name": "Simplex Formulation System", "variables": ["cost_vector", "cost_variable", "Ms", "T", "T_as_html", "simplex_constraints", "simplex_system", "sub_nonbasic_variables", "simplex_system_subbed"]}, {"name": "Placeholder", "variables": []}, {"name": "Geogebra Applet and other displayed variables", "variables": ["parameters", "gfinal", "shown_system"]}, {"name": "Pivoting", "variables": ["base_index", "basic_variables", "fixed_variables", "nonbasetext", "min_cost", "pj", "entering_variable", "ratios", "max_increases", "max_increase", "Taugmented", "pk", "leaving_variable", "substitution_line", "substitution_constraint", "Tupdate", "updated_constraints", "new_base", "new_values", "S", "is_optimal", "is_next_optimal"]}], "functions": {"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\nfunction latexify(s){\nif(s){\n return latex(s,rules.filter(x => x !== \"aligned\"), bscope)\n}\n else return \"\"\n}\n\nconst strings = system.map(latexify)\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}\""}, "side_by_side": {"parameters": [["system1", "list of expression"], ["system2", "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\nfunction latexify(s){\nif(s){\n return latex(s,rules.filter(x => x !== \"aligned\"), bscope)\n}\n else return \"\"\n}\n\nconst strings1 = system1.map(latexify)\nconst strings2 = system2.map(latexify)\n\nconst strings = strings1.map( (s,k) => s + \" & \" + strings2[k])\n\nif(rules.includes(\"aligned\")){\nconst alignedstrings = strings.map(s => s.replace(/(=|\\\\[gl]eq)/g,\"&$1\"))\nreturn \"\\\\begin{aligned}\"+alignedstrings.join(\"\\\\\\\\\")+\"\\\\end{aligned}\"\n}\nreturn \"\\\\begin{gathered}\"+strings.join(\"\\\\\\\\\")+\"\\\\end{gathered}\""}, "simplex_tableau": {"parameters": [["T", "matrix"], ["variables", "list of string"], ["basis", "list of number"]], "type": "html", "language": "javascript", "definition": "const numrows = T.length\nconst numcols = T[0].length\n\nconst head = \"The purpose of this activity is to understand the simplex method to solve the following linear program.
\\begin{align}
\\text{Maximise } \\var{objective}\\text{ subject to}\\\\
\\var{shown_system}\\\\
x\\geq 0, y\\geq 0
\\end{align}
The simplex method can be applied to problems of any number of variables, as it is an algebraic method, rather than a visual one. In this activity we will start from visualisations, to build intuition, and gradually move towards applying the simplex method algebraically. Although the simplex method can work on any number of variables and constraints, we are going to work a problem of two variables, so that we can visualise its steps.
\nThe activity comprises the following parts:
\nThe simplex method works by traveling along the edges. In the graph below, you can move the point $X$ along any edge of the feasible region. You cannot see the edge until the point is on it. The yellow regions are infeasible regions.
\nThe black arrow indicates the cost vector, which we want to maximise: any point in this direction is better. The red arrows are the projection of this vector along each edge. Following any arrow will improve the solution. Going in the opposite direction decreases the objective value.
\nMove the point $X$ on the graph below until it reaches the optimal solution.
\nNow that we have built a visual intuition on how the simplex method works, by sliding along edges from vertex to vertex, let us see how we can use algebra to identify the edge along which to slide, and then the vertex that will be visited next.
\nIn order to use algebra, it is more convenient to deal with linear equalities rather than inequalities. So, our first step will be to rewrite our linear program to only have equations.
\n"}, {"type": "jme", "useCustomName": true, "customName": "Rewriting the system", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "correctlhs (putting everything in the lhs for the correct equation, and evaluating the line equation):\n expression(join(split(\"{correctExpr}\",\"=\"),\"-\"))\n\nstudentlhs (putting everything in the lhs for the student's equation, and evaluating the line equation):\n expression(join(split(\"{studentExpr}\",\"=\"),\"-\"))\n\n\nstudentCompare (The part of the student's expression to compare):\n if(settings[\"mustMatchPattern\"]=\"\" or compareName=\"\",\n replace(formula_replacement_pattern, formula_replacement, studentlhs)\n ,\n studentMatch[\"groups\"][compareName]\n )\n\ncorrectCompare (The part of the correct expression to compare):\n if(settings[\"mustMatchPattern\"]=\"\" or compareName=\"\",\n replace(formula_replacement_pattern, formula_replacement, correctlhs)\n ,\n correctMatch[\"groups\"][compareName]\n )", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Rewrite the next constraint", "rawLabel": "Rewrite the next constraint", "otherPart": 3, "variableReplacements": [{"variable": "k", "definition": "k+1"}, {"variable": "student_constraints", "definition": "student_constraints + [interpreted_answer]"}], "availabilityCondition": "(kNow that we have built a visual intuition on how the simplex method works, by sliding along edges from vertex to vertex, let us see how we can use algebra to identify the edge along which to slide, and then the vertex that will be visited next.
\nNotice that each vertex corresponds to the intersection of (at least) two edges (or, in general, in dimension $n$, every vertex is the intersection of $n$ edges, and it is also the intersection of $n$ facets).
\nWe are going to capture that by rewriting the constraints into equality constraints, using slack variables.
\nWe will add constraints to the following (incomplete) system:
\n\\begin{align}\\text{Maximise } \\var{objective}\\text{ subject to}\\\\\\var{system}\\\\
x\\geq 0, y\\geq 0\\end{align}
\\begin{align}\\text{Maximise } \\var{objective}\\text{ subject to}\\\\\\var{student_system}\\\\
x\\geq 0, y\\geq 0\\end{align}
Rewrite the constraint $\\var{lines[k]}$ into an equality constraint using the slack variable $\\var{latex(slacks[k])}$ (use {slacks[k]})
The next step is to introduce a variable, $z$ that captures the value of the objective function. To do that we will need to introduce a new constraint that binds $z$ to the objective value $\\var{objective}$. Rewrite the equation $z=\\var{objective}$ so that all variables are on the left hand side.
", "answer": "{simplex_constraints[-1]}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": true, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "notation": "standard", "mustmatchpattern": {"pattern": "? = `+- (real:$n `| rational:$n)", "partialCredit": 0, "message": "", "nameToCompare": "", "warningTime": "submission"}, "valuegenerators": [], "functionsets": ["extension:geogebrax", "arithmetic"], "enabledfunctions": ["="], "disabledfunctions": []}, {"type": "information", "useCustomName": true, "customName": "Understanding the linear system", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Let us do this.", "rawLabel": "Let us do this.", "otherPart": 6, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "We have now constructed a linear system:
\n$$\\var{simplex_system}$$
\nthat captures all the information in our linear program (keeping in mind that the variable $\\var{cost_variable}$ will represent our objective value). Let us take a moment to look at it.
\nThe simplex method works by applying algebraic manipulation to the system of linear equations, so that:
\nNow that we have built a visual intuition on how the simplex method works, by sliding along edges from vertex to vertex, let us see how we can use algebra to identify the edge along which to slide, and then the vertex that will be visited next.
\nOur rewritten system is:
\n$$\\var{simplex_system}$$
\nOur current solution, {nonbasetext}, corresponds to a vertex in the feasible set. We will \"move\" to another vertex by swapping one of the non-basic variables with one of the basic variables.To do that we need to:
\nWe will repeat this procedure until we have reached the vertex giving the optimal solution.
"}, {"type": "1_n_2", "useCustomName": true, "customName": "Choose a variable to enter the base.", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "selected_variable (the variable selected by the student, as an expression):\n fixed_variables[interpreted_answer]\n\nselected_variable_index (the index of the variable selected by the student in the list of variables):\n indices(variables,selected_variable)[0]\n\nselected_coefficient (the coefficient for the selected variable in the last row of the system of equations):\n T[-1][selected_variable_index]\n\nis_increase_direction (does increasing the selected variable induce an increase in the objective value?):\n selected_coefficient < 0\n \nis_maximal_increase (does increasing the selected variable induce the maximal increase in the objective value?):\n selected_coefficient = min_cost\n \nscore_ticks:\n apply(is_increase_direction);\n apply(is_maximal_increase);\n if(is_increase_direction,\n if(is_maximal_increase,\n correct(\"You have selected a variable that yields the maximal increase direction for the objective.\"),\n correct(\"You have selected a variable that yields an increase direction for the objective, and is therefore a valid choice. Note that this variable does not yield the maximal possible increase direction, and is not the one that would be selected in the classical simplex algorithm.\")\n ),\n incorrect(\"The variable you selected does not induce an increase of the objective, and therefore is not a valid option to enter the base.\");end()\n )\n\ntotal_score: 1\n\nmark:\n assert(numTicks>0,\n warn(translate(\"part.marking.nothing entered\"));\n fail(translate(\"part.marking.nothing entered\"))\n );\n apply(score_ticks)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Choose which variable gets replaced in the base.", "rawLabel": "Choose which variable gets replaced in the base.", "otherPart": 8, "variableReplacements": [{"variable": "pj", "definition": "selected_variable_index"}], "availabilityCondition": "answered and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "Considering our linear system
\n$$\\var{simplex_system}$$
\nPick which variable will enter the base (ie, which variable will yield an increase of the objective function).
", "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showBlankOption": true, "showCellAnswerState": true, "interpretedAnswerForm": "index of choice", "choices": "map(x->\"$\"+\"{x}\"+\"$\", fixed_variables)", "matrix": "[1,1]"}, {"type": "gapfill", "useCustomName": true, "customName": "Pivot rule: which variable leaves the base", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Start rewriting the linear system.", "rawLabel": "Start rewriting the linear system.", "otherPart": 9, "variableReplacements": [{"variable": "pk", "definition": "interpreted_answer[2]"}], "availabilityCondition": "answered and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "The linear program we are solving is:
\n{geogebra_applet(\"https://www.geogebra.org/m/tgsutwen\", parameters +[\"X\":[\"definition\": S, \"fixed\": true]])}
\n$$\\var{simplex_system}$$
\nNow we have chosen $\\var{entering_variable}$ to enter the base. We need to find by how much we can increase its value. This will be limited by the equations in the system, and the values of the other variables having to remain nonnegative. Using the constraints, complete the table below. If for a particluar constraint/variable, there is no upper limit to $\\var{entering_variable}$, enter infinity.
[[0]]
\nTherefore, in order for all variables to remain nonnegative, the maximal increase will be [[1]].
\nThe variable leaving the base is (one of) the variable that becomes 0 when $\\var{entering_variable}$ reaches this value. Select which variable will leave the base: [[2]]
\n", "gaps": [{"type": "prepended-cells", "useCustomName": true, "customName": "Increase", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "settings": {"correctAnswer": "{transpose(matrix(max_increases))}", "labels": "{map(x -> \"to keep $\" + \"{x}\" + \"\u22650$, we need $\" + \"{entering_variable}\" + \"\u2264$\",basic_variables)}", "tolerance": "0.01"}}, {"type": "numberentry", "useCustomName": true, "customName": "maximal increase", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "minValue": "max_increase-0.01", "maxValue": "max_increase+0.01", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "1_n_2", "useCustomName": true, "customName": "Variable leaving the base", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "selected_variable (the variable selected by the student, as an expression):\n fixed_variables[interpreted_answer]\n\nselected_variable_index (the index of the variable selected by the student in the list of variables):\n indices(variables,selected_variable)[0]\n\nselected_increase (the amount the entering variable can increase based on the selected variable):\n max_increases[interpreted_answer]\n \nyields_maximal_increase (does the selected variable leaving the base induce the maximal increase in the objective value?):\n selected_increase = max_increase\n \nscore_ticks:\n apply(yields_maximal_increase);\n if(yields_maximal_increase,\n correct(\"You have selected a variable that, when leaving the base, yields the maximal increase direction for the objective.\"),\n incorrect(\"Picking this variable to leave the base would make other variables negative.\");end()\n )\n\ntotal_score: 1\n\nmark:\n assert(numTicks>0,\n warn(translate(\"part.marking.nothing entered\"));\n fail(translate(\"part.marking.nothing entered\"))\n );\n apply(score_ticks)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showBlankOption": true, "showCellAnswerState": true, "interpretedAnswerForm": "index of choice", "choices": "map(x->\"$\"+\"{x}\"+\"$\", basic_variables)", "matrix": "repeat(1,length(basic_variables))"}], "sortAnswers": false, "inlineCorrectAnswer": true}, {"type": "gapfill", "useCustomName": true, "customName": "Rewrite the constraints: part 1", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Substitute your expression into the constraints", "rawLabel": "Substitute your expression into the constraints", "otherPart": 10, "variableReplacements": [{"variable": "k", "definition": "if(pk=0,1,0)"}, {"variable": "substitution_constraint", "definition": "interpreted_answer[0]"}, {"variable": "student_simplex_constraints", "definition": "[]"}], "availabilityCondition": "answered and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "Now that we have identified the variable entering the base, $\\var{entering_variable}$ and the variable leaving the base, $\\var{leaving_variable}$, we can now rewrite the system accordingly. The way we will do that is to use the constraint $\\var{simplex_constraints[pk]}$ to express $\\var{entering_variable}$ in terms of the other variables, and then substitute this into the other constraints.
\nUsing $\\var{simplex_constraints[pk]}$ find an expression for $\\var{entering_variable}$: $\\var{entering_variable}=$[[0]].
", "gaps": [{"type": "jme", "useCustomName": true, "customName": "substitution expression", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "answer": "{substitution_constraint}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "notation": "standard", "valuegenerators": [], "functionsets": ["extension:geogebrax", "arithmetic", "complex_numbers", "exponentials", "trigonometry", "rounding", "number_theory", "comparison", "linear_algebra", "booleans", "set_theory", "intervals", "number_ranges", "lists", "dictionaries", "strings", "type_casting", "number_parsing", "precision", "json", "jme", "pattern_matching", "html", "randomisation", "control_flow", "comprehensions", "calculus", "marking", "http", "promises"], "enabledfunctions": [], "disabledfunctions": []}], "sortAnswers": false, "inlineCorrectAnswer": true}, {"type": "jme", "useCustomName": true, "customName": "substituting into the constraints", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "correctlhs (putting everything in the lhs for the correct equation, and evaluating the line equation):\n expression(join(split(\"{correctExpr}\",\"=\"),\"-\"))\n\nstudentlhs (putting everything in the lhs for the student's equation, and evaluating the line equation):\n expression(join(split(\"{studentExpr}\",\"=\"),\"-\"))\n\n\nstudentCompare (The part of the student's expression to compare):\n if(settings[\"mustMatchPattern\"]=\"\" or compareName=\"\",\n replace(formula_replacement_pattern, formula_replacement, studentlhs)\n ,\n studentMatch[\"groups\"][compareName]\n )\n\ncorrectCompare (The part of the correct expression to compare):\n if(settings[\"mustMatchPattern\"]=\"\" or compareName=\"\",\n replace(formula_replacement_pattern, formula_replacement, correctlhs)\n ,\n correctMatch[\"groups\"][compareName]\n )", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Substitute into the next constraint", "rawLabel": "Substitute into the next constraint", "otherPart": 10, "variableReplacements": [{"variable": "k", "definition": "if(k+1=pk,k+2,k+1)"}, {"variable": "student_simplex_constraints", "definition": "student_simplex_constraints + [interpreted_answer]"}], "availabilityCondition": "length(student_simplex_constraints)We now need to substitute the expression $\\var{expression(\"{entering_variable}={substitution_constraint}\")}$ in each line of the system.
\nSubstitute the expression $\\var{expression(\"{entering_variable}={substitution_constraint}\")}$ into $\\var{simplex_constraints[k]}$.
", "answer": "{updated_constraints[k]}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": true, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "notation": "standard", "mustmatchpattern": {"pattern": "? = `+- (real:$n `| rational:$n)", "partialCredit": 0, "message": "Please ensure that your answer takes the form of a linear equation, with the constant term on the right hand side", "nameToCompare": "", "warningTime": "submission"}, "valuegenerators": [], "functionsets": ["arithmetic"], "enabledfunctions": ["="], "disabledfunctions": []}, {"type": "1_n_2", "useCustomName": true, "customName": "Check if solution is optimal", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Perform another iteration of the Simplex algorithm", "rawLabel": "Perform another iteration of the Simplex algorithm", "otherPart": 7, "variableReplacements": [], "availabilityCondition": "answered", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}, {"label": "Apply the Simplex Algorithm through the Tableau method", "rawLabel": "Apply the Simplex Algorithm through the Tableau method", "otherPart": 12, "variableReplacements": [{"variable": "T", "definition": "augment(Ms,transpose(matrix(rhs)))"}, {"variable": "base_index", "definition": "list(2..length(slacks)+1)"}, {"variable": "pj", "definition": "indices(T[-1],min_cost)[0]"}, {"variable": "pk", "definition": "indices(max_increases,max_increase)[0]"}], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "Congratulations, you have reached the next vertex in your polytope. The new set of basic variables is $\\var{basic_variables}$. By setting these variables to 0, we can immediately access the values of the basic variables.
\nThe new linear system is:
\n{geogebra_applet(\"https://www.geogebra.org/m/tgsutwen\", parameters +[\"X\":[\"definition\": S, \"fixed\": true]])}
\n$$\\var{simplex_system}$$
\nYour current solution is $\\var{S}$ and the current objective value is $\\var{T[-1][-1]}$.
\nLooking a the last line of the system, is the current solution optimal, or do we need another iteration of the Simplex algorithm?
", "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showBlankOption": true, "showCellAnswerState": true, "interpretedAnswerForm": "list of list of boolean", "choices": ["The current solution is optimal.", "We need to run another iteration of the simplex algorithm."], "matrix": ["if(is_optimal,1,0)", "if(is_optimal,0,1)"], "distractors": ["", ""]}, {"type": "tableau", "useCustomName": true, "customName": "Tableau Representation", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Find the pivot", "rawLabel": "Find the pivot", "otherPart": 13, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "Now that you have learnt how the simplex method works, let us make it easier to apply.
\nThe steps of the simplex method may remind you of how you solve linear systems. Here we have used substitution, where we use an equality constraint to express one variable in terms of the other variable, and then substitute this value into the other linear equations.
\nLike with solving linear system, we can alternatively use a (Gaussian) elimination step. We will represent the linear system in (augmented) matrix form, which we call a \"tableau\". Then, like with Gaussian elimination, we select a pivot, which identifies both the row (the constraint) we will subtract from all the other ones, and the column (the variable) which we will eliminate from all other rows.
\nLet us start by representing the linear system
\n$$\\var{simplex_system}$$ in matrix form. Enter the coefficients of the system in their relevant place below.
", "settings": {"correctAnswer": "{T}", "variables": "{map(v -> \"$\"+\"{v}\"+\"$\", variables) + [\"$z$\", \"RHS\"]}", "basis": "{base_index + [length(variables)]}", "prefilled_cells": "[[]]", "tolerance": "0.01"}}, {"type": "gapfill", "useCustomName": true, "customName": "Tableau: Find the pivot", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "// First gap marking\n\nentering_variable (the variable selected by the student, as an expression):\n fixed_variables[interpreted_answers[0]]\n\nentering_variable_index (the index of the variable selected by the student in the list of variables):\n indices(variables,entering_variable)[0]\n\nentering_coefficient (the coefficient for the selected variable in the last row of the system of equations):\n T[-1][entering_variable_index]\n\nis_increase_direction (does increasing the selected variable induce an increase in the objective value?):\n entering_coefficient < 0\n \nis_maximal_increase (does increasing the selected variable induce the maximal increase in the objective value?):\n entering_coefficient = min_cost\n \nscore_entering_variable:\n apply(is_increase_direction);\n apply(is_maximal_increase);\n if(is_increase_direction,\n if(is_maximal_increase,\n correct(\"You have selected a variable that yields the maximal increase direction for the objective.\"),\n correct(\"You have selected a variable that yields an increase direction for the objective, and is therefore a valid choice. Note that this variable does not yield the maximal possible increase direction, and is not the one that would be selected in the classical simplex algorithm.\")\n ),\n incorrect(\"The variable you selected does not induce an increase of the objective, and therefore is not a valid option to enter the base.\");end()\n )\n\nmark_gap_zero:\n let(\n answer, studentAnswer[0],\n result, submit_part(gaps[0][\"path\"],answer),\n gap, gaps[0],\n name, gap[\"name\"],\n noFeedbackIcon, not gap[\"settings\"][\"showFeedbackIcon\"],\n non_warning_feedback, filter(x[\"op\"]<>\"warning\",x,result[\"feedback\"]),\n assert(noFeedbackIcon,\n assert(name=\"\" or len(gaps)=1 or len(non_warning_feedback)=0,feedback(translate('part.gapfill.feedback header',[\"name\": name])))\n );\n concat_feedback(non_warning_feedback, if(marks>0,result[\"marks\"]/marks,1/len(gaps)), noFeedbackIcon);\n non_warning_feedback\n )\n\n// Second gap marking:\n\nratios (ratios for the simplex tableau based on the entering variable selected by the student):\n map(r -> r[-1]/r[entering_variable_index], list(T)[0..length(basic_variables)])\n\nmax_increases (maximal increase allowed for each basic variable):\n map(r -> if(r>0,r,infinity),ratios)\n\nmax_increase (maximal increase allowed for the entering variable):\n min(max_increases)\n\nstudent_last_column (last column of the tableau as entered by the student):\n take(length(max_increases),p->true,map(x->x[-1], list(interpreted_answers[1])))\n\ncompare_tables (compare the student's response with the correct one):\n all(map([u,v] -> ((u=infinity and v=infinity) or (abs(u-v)<0.1)), zip(max_increases,student_last_column)))\n\n\nscore_tableau (check whether the table is correct or not):\n apply(ratios);\n apply(max_increases);\n apply(max_increase);\n apply(student_last_column);\n if(compare_tables,\n correct(\"The ratios you entered in the table are correct.\"),\n incorrect(\"Some of the ratios that you entered are incorrect\"); end()\n )\n\n// Third gap:\n\nleaving_variable (the variable selected by the student, as an expression):\n fixed_variables[interpreted_answers[2]]\n\nleaving_variable_index (the index of the variable selected by the student in the list of variables):\n indices(variables,leaving_variable)[0]\n\nleaving_increase (the amount the entering variable can increase based on the selected variable):\n max_increases[interpreted_answers[2]]\n \nyields_maximal_increase (does the selected variable leaving the base induce the maximal increase in the objective value?):\n leaving_increase = max_increase\n \nscore_leaving_variable:\n apply(yields_maximal_increase);\n if(yields_maximal_increase,\n correct(\"You have selected a variable that, when leaving the base, yields the maximal increase direction for the objective.\"),\n incorrect(\"Picking this variable to leave the base would make other variables negative.\");end()\n )\n\ngap_feedback_old (Feedback on each of the gaps):\n map(\n try(\n let(\n answer, studentAnswer[answer_number],\n result, submit_part(gaps[gap_number][\"path\"],answer),\n gap, gaps[gap_number],\n name, gap[\"name\"],\n non_warning_feedback, filter(x[\"op\"]<>\"warning\",x,result[\"feedback\"]),\n concat_feedback(non_warning_feedback, if(marks>0,result[\"marks\"]/marks,1/len(gaps)), true);\n non_warning_feedback\n ),\n err,\n fail(translate(\"part.gapfill.error marking gap\",[\"name\": gaps[gap_number][\"name\"], \"message\": err]))\n ),\n [gap_number,answer_number],\n zip(gap_order,answer_order)\n )\n\ntest:\n studentAnswer[2]\n\ngap_feedback (Feedback on each of the gaps):\n [let(\n answer, studentAnswer[0],\n result, submit_part(gaps[0][\"path\"],answer),\n gap, gaps[0],\n name, gap[\"name\"],\n non_warning_feedback, filter(x[\"op\"]<>\"warning\",x,result[\"feedback\"]),\n concat_feedback(non_warning_feedback, if(marks>0,result[\"marks\"]/marks,1/len(gaps)), false);\n non_warning_feedback\n ),\n let(\n answer, matrix([max_increases, student_last_column]),\n //answer, studentAnswer[1],\n result, submit_part(gaps[1][\"path\"],answer),\n gap, gaps[1],\n name, gap[\"name\"],\n non_warning_feedback, filter(x[\"op\"]<>\"warning\",x,result[\"feedback\"]),\n concat_feedback(non_warning_feedback, if(marks>0,result[\"marks\"]/marks,1/len(gaps)), false);\n non_warning_feedback\n ),\n let(\n answer,repeat(yields_maximal_increase,length(studentAnswer[2])),\n //answer, studentAnswer[2],\n result, submit_part(gaps[2][\"path\"],answer),\n gap, gaps[2],\n name, gap[\"name\"],\n non_warning_feedback, filter(x[\"op\"]<>\"warning\",x,result[\"feedback\"]),\n concat_feedback(non_warning_feedback, if(marks>0,result[\"marks\"]/marks,1/len(gaps)), false);\n non_warning_feedback\n )]", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Update the tableau", "rawLabel": "Update the tableau", "otherPart": 14, "variableReplacements": [{"variable": "pj", "definition": "interpreted_answer[0]"}, {"variable": "pk", "definition": "interpreted_answer[2]"}], "availabilityCondition": "answered and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "Looking at the tableau below, Pick a variable to enter the base (ie, pick the column that has a [most] negative entry in the last row).
\n[[0]]
\nFor this variable, enter the maximal increase that each basic variable will enable. If there is no limit, enter infinity.
[[1]]
\nSelect a variable to leave the base:
\n[[2]]
", "gaps": [{"type": "1_n_2", "useCustomName": true, "customName": "Variable entering the base", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "selected_variable (the variable selected by the student, as an expression):\n fixed_variables[interpreted_answer]\n\nselected_variable_index (the index of the variable selected by the student in the list of variables):\n indices(variables,selected_variable)[0]\n\nselected_coefficient (the coefficient for the selected variable in the last row of the system of equations):\n T[-1][selected_variable_index]\n\nis_increase_direction (does increasing the selected variable induce an increase in the objective value?):\n selected_coefficient < 0\n \nis_maximal_increase (does increasing the selected variable induce the maximal increase in the objective value?):\n selected_coefficient = min_cost\n \nscore_ticks:\n apply(is_increase_direction);\n apply(is_maximal_increase);\n if(is_increase_direction,\n if(is_maximal_increase,\n correct(\"You have selected a variable that yields the maximal increase direction for the objective.\"),\n correct(\"You have selected a variable that yields an increase direction for the objective, and is therefore a valid choice. Note that this variable does not yield the maximal possible increase direction, and is not the one that would be selected in the classical simplex algorithm.\")\n ),\n incorrect(\"The variable you selected does not induce an increase of the objective, and therefore is not a valid option to enter the base.\");end()\n )\n\ntotal_score: 1\n\nmark:\n assert(numTicks>0,\n warn(translate(\"part.marking.nothing entered\"));\n fail(translate(\"part.marking.nothing entered\"))\n );\n apply(score_ticks)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showBlankOption": true, "showCellAnswerState": true, "interpretedAnswerForm": "index of choice", "choices": "map(x->\"$\"+\"{x}\"+\"$\", fixed_variables)", "matrix": "[1,1]"}, {"type": "tableau", "useCustomName": true, "customName": "Tableau", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "max_increases:\n interpreted_answer[0]\n\nstudent_last_column:\n interpreted_answer[1]\n\nagree:\n map([u,v] -> ((u=infinity and v=infinity) or (abs(u-v)<0.1)), zip(max_increases,student_last_column))\n\nmark:\n apply(agree);\n if(all(agree), correct(\"The ratios you have entered are correct\"), incorrect(\"The last column of your table is incorrect.\"))", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": false, "showFeedbackIcon": false, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "settings": {"correctAnswer": "{Taugmented}", "variables": "{map(v -> \"$\"+\"{v}\"+\"$\", variables) + [\"$z$\", \"RHS\",\"ratio\"]}", "basis": "{base_index + [length(variables)]}", "prefilled_cells": "map(r->map(x->\"{x}\",r) + [\"\"],list(T[0..numrows(T)-1])) + [map(x->\"{x}\",list(T[-1])) + \"infinity\"]", "tolerance": "0.01"}}, {"type": "1_n_2", "useCustomName": true, "customName": "Variable leaving the base", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "vals:\n studentAnswer\n\nvala:\n interpreted_answer\n\nmark:\n if(studentAnswer[0],correct(\"You have picked an appropriate variable to leave the base.\"),incorrect(\"The variable you have picked to leave the base is not correct.\"))", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showBlankOption": true, "showCellAnswerState": true, "interpretedAnswerForm": "index of choice", "choices": "map(x->\"$\"+\"{x}\"+\"$\", basic_variables)", "matrix": "[1] + repeat(0,length(basic_variables)-1)"}], "sortAnswers": false, "inlineCorrectAnswer": true}, {"type": "gapfill", "useCustomName": true, "customName": "Applying an elimination step", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Find the next pivot", "rawLabel": "Find the next pivot", "otherPart": 13, "variableReplacements": [{"variable": "T", "definition": "Tupdate"}, {"variable": "base_index", "definition": "new_base"}], "availabilityCondition": "not is_next_optimal and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": true}, {"label": "\u2139\ufe0f Conclusion", "rawLabel": "", "otherPart": 15, "variableReplacements": [], "availabilityCondition": "is_next_optimal and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "You have selected the variable $\\var{entering_variable}$ (ie, column $\\var{pj+1}$) to enter the base, and the variable $\\var{leaving_variable}$ (ie row $\\var{pk+1}$) to leave it.
\nThe current tableau is:
\nApply an elimination step in this tableau to construct the new tableau by:
\n[[0]]
\nHave we arrived at the solution?
\n[[1]]
", "gaps": [{"type": "tableau", "useCustomName": true, "customName": "Next Tableau", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "settings": {"correctAnswer": "{Tupdate}", "variables": "{map(v -> \"$\"+\"{v}\"+\"$\", variables) + [\"$z$\", \"RHS\"]}", "basis": "{new_base + [length(variables)]}", "prefilled_cells": "map(k -> if(k=pk,\n map(j -> if(j=pj,\"1\",\"\"), 0..numcolumns(Tupdate)),\n map(j -> if(j=pj,\"0\",\"\"), 0..numcolumns(Tupdate))),\n 0..numrows(Tupdate))", "tolerance": "0.01"}}, {"type": "1_n_2", "useCustomName": true, "customName": "optimality", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showBlankOption": true, "showCellAnswerState": true, "interpretedAnswerForm": "list of list of boolean", "choices": ["The new tableau represents an optimal solution.", "Another iteration of the simplex method is necessary."], "matrix": ["if(is_next_optimal,1,0)", "if(is_next_optimal,0,1)"], "distractors": ["", ""]}], "sortAnswers": false, "inlineCorrectAnswer": true}, {"type": "information", "useCustomName": true, "customName": "\u2139\ufe0f Conclusion", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "adaptiveMarkingUseCondition": "", "adaptiveMarkingNotUsedMessage": "", "exploreObjective": null, "prompt": "Congratulations, you have successfully completed the activity.
\nWe have gone through the following steps:
\n