Solve a linear program

Notebook to demonstrate the Simplex Method

The example of this notebook is based on the book [1].

[1] Hors W. Hamacher, Kathrin Klamroth. Lineare Optimierung und Netwerkoptimierung - Zweisprachige Ausgabe Deutsch Englisch. Vieweg, 2006.

The company “Chocolate & Co.” is in the process of changing its product range. Several chocolate products produced so far will be eliminated from the offer and will be replaced by two new products. The first product P1 is a fine cocoa powder, and the second product P2 is a tart dark chocolate. The company uses three production facilities F1, F2 and F3 to manufacture these two products. In the central plant F1, the cocoa beans are cleaned, roasted and broken. In F2 and F3, the prepared cocoa beans are then used to produce the cocoa powder and chocolate, respectively. Since the chocolate products produced are of very high quality, it can be assumed that the entire production quantity is also sold. The profit per sold production unit (100 kg cocoa powder) of P1 = 3 (30,00 €) and per sold production unit (100 kg chocolate) of P2 = 5 (50,00 €). The capacities of the production plants F1, F2 and F3 are, however, limited. The numerical values result from the following table:

	P1	P2	availabel capacity (in % of the daily capacity)
F1	3	2	18
F2	1	0	4
F3	0	2	12

(For example, the line corresponding to F1 states that \(3\)% and \(2\)% of the daily capacity of the F1 production plant is required per unit of P1 and P2, respectively, and a total of \(18\)% of the total capacity of F1 is available daily \(18\)% for products P1 and P2).

The task now is to figure out how many units \(x_1\) of product P1 and \(x_2\) of product P2 to produce daily to maximize profit (given the capacity constraints). Mathematically, this problem can be formulated as a linear program (LP):

\[\begin{align*} \max & & 3 x_1 + 5 x_2 & \\ \text{s.t.} & & 3 x_1 + 2 x_2 & \leq 18 \\ & & x_1 & \leq 4 \\ & & 2x_2 & \leq 12 \\ & & x_1, x_2 & \geq 0. \end{align*}\]

To solve this problem with oppy, we need the necessary solver (simplex) as usual, and we need to define the cost vector \(c\) as well as the matrix \(A\) and the vector \(b\) for the linear constraints.

import numpy as np
from oppy.linOpt import simplex

# define cost
c = np.array([3, 5])
# define matrix A and vector b -> constraints
A = np.array([[3, 2], [1, 0], [0, 2]])
b = np.array([18, 4, 12])
# and solve with simplex
res = simplex(c, A, b)
print(res.x_opt)

[2. 6.]

As we can see, the solution of our problem is to take \(2\) units of \(x_1\) and \(6\) units of \(x_2\).