FrançaisGet started

The linear programme: standard form and duality

The linear programme with several variables: putting it in standard form with slack variables, the dual programme and the price of a resource, integer variables and relaxation, and using a solver.

  • 29 cards
  • 5 topics
  • Free
Study this deck

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

  1. Concepts
  2. Questions
  3. Sort and link
  4. The numbers
  5. Scenarios

A few cards from the deck

  • Standard form of a linear programme: what is it?

    Show the answer

    A way of writing the programme in which every constraint is an equality with a non-negative right-hand side and every variable is non-negative.

    You get there by adding one variable to each inequality. The simplex method starts from this form, because equalities can be handled with row operations on a tableau.

  • This script tries to maximise the profit 30x + 20y subject to 2x + y ≤ 100 and x + y ≤ 80. It returns x = 0 and y = 0, a zero profit. What is the cause?

    ```python
    from scipy.optimize import linprog

    res = linprog(c=[30, 20], A_ub=[[2, 1], [1, 1]], b_ub=[100, 80])
    print(res.x, res.fun)
    # [0. 0.] 0.0
    `

    • linprog minimises: you must pass c=[-30, -20] and read the profit as -res.fun
    • bounds=(0, None) is missing, without which the variables are forced to 0 and linprog returns the zero point
    • b_ub must hold negative values, because linprog reads constraints in the ≥ form
    • A_ub must be transposed before the call: linprog expects one variable per row
    Show the answer

    linprog minimises: you must pass c=[-30, -20] and read the profit as -res.fun

    linprog always minimises c @ x. With c = [30, 20] and x, y ≥ 0, the minimum is at (0, 0). The default bounds are already (0, None). With c = [-30, -20] you get x = 20, y = 60 and res.fun = -1800.0: the profit is 1,800.

  • A linear programme optimises a linear objective under … constraints; if the feasible region is bounded, the optimum is reached at a ….

    Show the answer

    A linear programme optimises a linear objective under linear constraints; if the feasible region is bounded, the optimum is reached at a vertex.

    The objective and the constraints are linear combinations of the variables, hence a polyhedral region whose corner is where the objective reaches its extremum.

  • Slack variable: what is it?

    Show the answer

    A non-negative variable added to the left-hand side of a ≤ constraint to turn it into an equality; it measures the amount of the resource left unused.

    2x + y ≤ 100 becomes 2x + y + e1 = 100. With x = 10 and y = 20, e1 = 60: 60 units are left. With x = 20 and y = 60, e1 = 0: the resource is used up.

Study this deck