Julien Ugon

The 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.

A 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. 

It comprises four parts:

First part: visual intuition.

First 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. 

Second part: algebraic intuition.

In this part, we introduce the student to the steps of the simplex method, by applying algebraic techniques they are familiar with, namely variable substitution. 

First, 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. 

Then, 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.

By 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.

Third part: method of tableaux.

The 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. 

Then, 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. 

Fourth part: conclusion.

Once the student has completed all parts, they are led to a summary of what they did, to recapitulate the process they went through.

This questions gives a bipartite graph and asks students to identify a full matching of the graph, if it exists.

This question uses a Geogebra applet to solve a linear program with two variables using the graphical method. It contains three steps:

1. Construct the feasible area (polygon) by adding the constraints one by one. The students can see what happens when the constraints are added.
2. Add the objective function, and the level set of the objective value is shown, as well as its (normalised) gradient.
3. Compute the optimal solution by moving the level set of the objective around.

In this question the students have to solve a linear recurrence of order 2. The sequence is asked in recurrence form and the goal is to find its closed form.

In this question the students have to solve a linear recurrence of order 1. The sequence is asked in recurrence form and the goal is to find its closed form.

Asks students to apply laws of logical equivalence to prove the equivalence between two logical statements. The quiz should accept any correct answer (as long as each step is included, with one law per step), and provides detailed feedback on mistakes.

This question aims at getting the students to demonstrate their ability to apply the Euclidean algorithm to find the GCD between two numbers.

We provide two randomly generated numbers and ask the students to enter the steps of the Euclidean algorithm, as well as the GCD between the numbers.

Convert a number given in base 10 to a different base.

Convert a number given in base 10 to a different base.

GIve a random linear program and ask the students to convert it to canonical form.

GIve a random linear program and ask the students to convert it to canonical form.

In this question the students have to solve a linear recurrence of order 2. The sequence is asked in recurrence form and the goal is to find its closed form.

This question gives a text encrypted with an affine cipher and asks students to decrypt it.

This question asks students to decrypt a message using a simple Caesar cipher, without giving them the key.

The students should solve a Blakley secret sharing scheme and find the secret.

The purpose of this question is to ask the students to go through one Rijndael round from the AES algorithm.

The purpose of this question is to ask the students to go through one Rijndael round from the AES algorithm.

This question runs the students through the Elliptic Curves version of Diffie Hellman.

In this question the students are given the public and private keys for El Gamal through Elliptic Curve and a message to decrypt. They have to decrypt the message.

This question asks students to solve a discrete logarithm problem with Pollard's rho algorithm as exposed in the book "introduction to cryptography with open source software" by McAndrew.

The purpose of this question is to test student's understanding of the Elliptic curves version of El Gamal encryption. It asks them to go through two steps: the publication of the public key, and the use of this public key to encrypt a message.

The purpose of this question is to ask students to decrypt a message encrypted with a Hill cipher.

This question asks students to identify trees.

This question asks students to find a spanning tree for simple undirected graphs.

Given a linear programming problem in standard form, write down the dual problem.