This lesson's interactive features are locked, please to keep using them

Simplex Algorithm for Solving LP Problems

We're going to build a SimplexSolver from scratch! Unfortunately, a simplex solver that can handle a large numbers of vertices in more than 2 dimensions is a bit more complex than the simple examples we've looked at so far. We'll be building the more complex, more robust, and more useful version! Don't worry, we'll do it piece-by-piece.

SimplexSolver is a class that holds the state of the algorithm in its data member variables:

self.objective: The bottom row of the simplex matrix, or tableau. It holds the coefficients of the objective function.
self.rows: The other rows of the simplex tableau. This is a list of lists (i.e., rows x columns).
self.constraints: A list of the constraint values.

For example, in our bakery scenario from before, we have the following data, where cakes = x and cookies = y.

Objective Function

profit = (x * 5) + y

profit - 5x - y = 0

Constraints

x <= 250
y <= 200
x + y <= 300
0 <= x
0 <= y

self.constraints = [250, 200, 300]

# Tableau
self.rows = [
    [1.0, 0.0],
    [0.0, 1.0],
    [1.0, 1.0],
]
self.objective = [-5.0, -1.0]

We'll only be supporting "less than or equal to" constraints for the sake of simplicity. Most problems can be modeled using only the <= operator.

Assignment

At Mappy we sell 3 different subscriptions to our app:

basic – $30/mo.
pro – $60/mo.
enterprise – $120/mo.

Due to the number of external API licenses that we hold, we have the following constraints:

We can sell no more than 100 basic subscriptions each month.
We can sell no more than 25 pro subscriptions each month.
We can sell no more than 10 enterprise subscriptions each month.
We have 150 API keys available each month. A basic subscription uses 1 key, a pro subscription uses 2, and an enterprise subscription uses 3.

We'll be using our simplex solver to help answer the question:

How many of each subscription should we sell to maximize profit?

Complete the __init__ and add_constraint functions.

The constructor, __init__(self, func_coefficients: list[int]) -> None, should create the three data members described above.
1. Initialize self.objective as an empty list, then iterate over the provided coefficients and append each.
2. Make self.rows an empty list.
3. Make self.constraints an empty list.
For add_constraint(self, coefficients: list[int], value: int) -> None:
1. Append a new list containing all the provided coefficients to self.rows. This creates a new row in the tableau.
2. Append the provided value to the solver's list of constraints.