Linear programming is a mathematical method to achieve the best result for a given problem. This problem is expressed through a mathematical model which represents the real world problem. Also called linear optimization because of it’s essence to optimize a linear objective function.

In other words, linear programming aim to find the optimal input value for the function, value which will also be the optimal solution for the problem. Usually linear optimization is a good method to solve assignment problems which are a fundamental kind of combinatorial optimization problems. Assignment (or allocation) problems are basically the kind of problem that asks for the allocation of scarce resources. Some examples:

• Scheduling problems;
• Resourcing problems;
• Assignment problems;
• Balance your meals to fit your macro nutrient goals;
• Sudoku.

While the first example is focused on explaining the concepts, the second example will be solved using a more straight forward solution without giving redundant explanations.

Example problem 1

To make things more concrete, I will present an example and solve it. Let’s suppose that a certain farmer wants to know which cereal to cultivate in his farm. Let’s suppose that the farmer can grow only 2 kinds of cereals, corn and beans. And the farmers main objective is the maximum profit. The farm has 100 acres, each acre of corn result in 8 sacks while each acre of beans result in 10 sacks. For planting of each acre of corn it is needed 3 hours of work, while for each acre of beans 2 hours of work are needed. The farmer has 240 hours of work available but it costs 200$ for every hour. The maximum demand is limited by the market at a maximum of 480 sacks of corn sold by 150$ each and 800 sacks of beans sold by 120$ each. Which cereal should the farmer grow to have the maximum profit ?

Problem modeling

To model the problem, we need to extract the 3 main characteristics of the problem, determine the variables, determine it’s restrictions and calculate the objective function.

Variables

Variables are everything that you can work on the problem, they are the moving parts and the input of the objective function.

In the case of the proposed problem we have two variables, acres of corn and beans that will be cultivated. For brevity, let’s call corn \(x\) and beans \(y\).

Objective function

It shows our target function to archive, it can be a maximization or minimization of the result of the function \(Z\), or in very rare cases, the objective is to approximate \(Z\) to a certain value. The objective function is created to reflect the impact of the variables on the outcome. In other words, based on the variable values, it output has to represent the outcome in the real world.

For the objective function of the example case above, the main objective is maximum profit, it means to maximize the output of the function that given the amount of corn and beans calculate the profit. We can define what profit is by the \(Profit = Sell Price - Costs\).

So:

\[ Z(x,y) = (150 \times 8 \times x) + (120 \times 10 \times y) - (200 \times 3 \times x) - (200 \times 2 \times y) \]

Let’s break it down in some chunks and analyse it:

• The amount of money obtained for each acre of corn (named \(x\)) grown: \((150 \times 8 \times x)\)
• The amount of money obtained for each acre of beans (named \(y\)) grown: \((120 \times 10 \times y)\)

Then we subtract the costs of cultivating those crops, considering that each work hour costs \(200\) dollars:

• The cost of cultivating one acre of corn \((200 \times 3 \times x)\)
• The cost of cultivating one acre of beans \((200 \times 2 \times y)\)

We can optimize it by writing:

\[ Z(x,y) = (1200 \times x) + (1200 \times y) - (600 \times x) - (400 \times y) \]

And again:

\[ Z(x,y) = (600 \times x) + (800 \times y)\]

Restrictions

Restrictions are any restriction that we need to apply to our variables. The amount of resources, time, effort, etc… One common restriction considering cases where we are applying linear programming to production is the non negativity rule, it means, you can’t produce -1 cars, all numbers of cars produced must be positive or no car produced at all (zero cars).

The maximization or minimization of the function \(Z\) will always end up with on restriction limiting it’s result. So you can analyse that restriction and determine the bottleneck of your function. In case of all restrictions being reached it means that there was no bottleneck and all resources were utilized.

In the example problem we have some restrictions, it will be listed bellow:

• 100 acres available, it means \(x+y \leq 100\)
• The market demand for corn \(8x \leq 480\)
• The market demand for beans \(10y \leq 800\)
• The labour limitation defined by $ 3x + 2y ≤ 240$
• And finally, the non negativity rule, that give us \(x \geq 0\) and \(y \geq 0\)

100 acres available

Since we are calculating with our variables \(x\) and \(y\) being the acres cultivated, they directly represent it, so no transformation is needed.

The market demand for corn

We are using acres as our base value, the demand of corn is represented as the amount of \(x\) times how many sacks of corn each acre produces: \(8x \leq 480\)

The market demand for beans

We are using acres as our base value, the demand of beans is represented as the amount of \(y\) times how many sacks of beans each acre produces: \(10y \leq 800\)

The labour limitation

The same logic applies here, since we are using acres as our base value, we multiply the labor needed for each acre of each cereal, it means that corn needs \(3\) hours of labor, and beans need \(2\) hours.

Solving by hand with graphical method

We will apply the graphical solution here where the limitations are plotted so is possible to determine the solution visually. Bellow is the result of the above restrictions plotted in a graph.

Plot the graph

For all restrictions listed above, we will create a table with two lines, one for the restriction result for the smallest value of \(x\) and the maximization of the value \(y\), and the other for the opposite. As you can see, if there is only one variable in the restriction the table is not needed, since we are looking for the maximization of the use, it will result only on a straight line in the graph. In the example case the limitations of the market can be seen in the graph as perpendicular lines across their axis.

Since we are trying to maximize the resource usage, we remove the \(\leq\) and replace it with an equal symbol.

For the labour time restriction \(3x + 2y = 240\)

It means that for this restriction you will draw a line from the point \((0,120)\) to the point \((80,0)\). The are bellow the line, which for all elements there this function is true, is called feasible region.

The second restriction is pretty straight forward, we will analyse the total available area for the crops, which is given by the \(x+y = 100\).

It means that you will draw a line from the point \((0,100)\) to the point \((100,0)\).

The market demand for production of corn \(8x = 480\), that gives us \(x=60\). The market demand for production of beans \(10x = 800\), that gives us \(y=80\). Both will be represented by a straight line each on the given point.

With those restrictions calculated we can have some idea of the dimension of the graph that we are going to plot. Since our max value for \(y\) is 120 (labour restriction) and for \(x\) is 100 (total available area). Also adding a little bit of interpretation to this graph, we can tell that if we only grow corn crops, we won’t be able to use all land that the farmer have, since the bottleneck in this case will be the labor available.

Here is what the graph should look like after it is plotted.

• Colored in orange the 100 acres available, it means \(x+y \leq 100\)

• Colored in red The labour limitation defined by $ 3x + 2y ≤ 240$

• Colored in purple the market demand for corn \(8x \leq 480\)

• Colored in blue the market demand for beans \(10y \leq 800\)

Intersection points

After plotting the restriction functions we have what is called feasible region, a region of the graph that give possible solutions for our problem based on the restrictions only. The second step is to determine which point in this region maximizes or minimizes the result for the objective function \(Z\).

The essence of this method is to create a visual analysis of those points of intersection which are called corner points. If the problem has a solution, this solution will be one of those corner points.

In the example we have 5 intersection points, they will be presented based on which restriction they intersect or 0, to make things easier to reference later, we will name those points with letters.

• A) 0 and demand for beans;
• B) demand for beans and available area;
• C) available area and available labor;
• D) available labor and demand for corn
• E) demand for corn and 0;

Next step is to compile a table with all points and their values or \(x\) and \(y\). But to be able to work with that we need to solve the equations to know their values at their intersection point.

Points A and E won’t require any special effort since they have a know value in one of their axis.

• Point B

  Point B is the intersection between the demand of beans \(y=80\) and the available area \(x+y \leq 100\). So we just solve the system

  \[ x + y = 100 \]

  Replacing \(y\) with it’s value.

  \[ x + 80 = 100 \]

  And

  \[ x = 100 - 80 \]

  It gives us the point \(x=20\) and \(y=80\) \((20,80)\).

• Point C

  Point C is the intersection between the available labor \(3x+2y \leq 240\) and the available area \(x+y \leq 100\). So we just solve the system

  \[ 3x+2y = 240 \]

  \[ x+y = 100 \]

  We need to isolate one factor, so let’s isolate \(y\) in the second equation.

  \[ x+y = 100 (\times -2) \]

  And making one big equation we will have

  \[ 3x +2y -2x -2y = 240 - 200 \]

  \[ x = 40 \]

  Now that we have the \(x\) value, we just need to replace it in any of this two equations and we will have the \(y\) value for that point.

  \[ 40+y=100 \]

  \[ y=60 \]

  It gives us the point \(x=40\) and \(y=60\) \((40,60)\).

• Point D

  Point D is the intersection between the available labor \(3x+2y \leq 240\) and the demand for corn \(x=60\). So we just solve the system by replacing \(x\)

  \[ 180 + 2y = 240 \]

  \[ 2y = 240 - 180 \]

  \[ y = 30 \]

  It gives us the point \(y=30\) and \(x=60\) \((60,30)\).

• Corner points table

  Now that all points are calculated, just replace the \(x\) and \(y\) symbols by their values on the table bellow and calculate the objective function with it. It will give the output for those variables, and using this output if our objective is to maximize the result of the function, we will take the biggest value on the table as the optimal value, if the objective is to minimize, we take the smallest, simple as that.

  Given the objective function

  \[ Z(x,y) = (600 \times x) + (800 \times y)\]

  Point	x	y	Objective Function
  A	0	80	64000
  B	20	80	76000
  C	40	60	72000
  D	60	30	60000
  E	60	0	36000

Conclusion

Based on the table in the last section we can determine that the optimal area for the maximization of the profit is 20 acres of corn and 80 acres of beans, which will give a profit of 76000$.

This is enough, but we can look further and determine the bottlenecks, in other words, what is limiting the maximization of the objective function. In this example, this is a point of the analysis that gives the answer about what should be worked on to improve the profit.

Bottleneck analysis

To determine which restrictions are limiting the objective function, just analyse the values of \(x\) and \(y\), if restrictions match the value it means that this restriction is limiting the best outcome.

Applying our example

• Available area

  All available area was used, since \[ 20+80 = 100 \]

• Demand for corn

  The market demand for corn was not met, it means that if more corn was produced, it would be sold.

  \[ 8 \times 20 \leq 480 \]

• Demand for beans

  The market demand for beans was met, it means that even if more beans were produced, they won’t be sold and won’t generate any profit.

  \[10 \times 80 = 800\]

• Labor limitation

  Still 20 hours of labor remaining after all the production, it can be determined by:

  \[ 3 \times 20 + 2 \times 80 \leq 240 \]

  \[ 220 \leq 240 \]

Solving example 1 with python

For solving this problem with python we are going to use PuLP. To setup PuLP on Debian is easy, just pip3 install pulp and that is it. If you are using Poetry, just run poetry add pulp, or if you are using the Poetry setup in this repository, it is already installed.

Modeling the problem

For modeling this problem using PuLP basically we will need to import it and create a problem:

import pulp
problem = pulp.LpProblem("Farmer", pulp.LpMaximize)

Then we can add our variables to the problem, note that the restrictions based on variable values are mapped here, so the non negativity rule and all others based on the range of values should be applied at this point.

• The minimum bound of a variable is defined by the lowBound parameter.
• The maximum bound of a variable is defined by the upBound parameter.

Continuing our example, to create the \(x\) and \(y\) variables

x = pulp.LpVariable('x', lowBound=0, cat='Continuous')
y = pulp.LpVariable('y', lowBound=0, cat='Continuous')

Now we define our objective function, we can write it as plain python code and just += it into the problem variable like this:

problem += 600 * x + 800 * y, "Z"

Now we do the same to all our restrictions, we can just += them into the problem.

problem += x + y <= 100
problem += 8 * x <= 480
problem += 10 * y <= 800
problem += 3 * x + 2 * y <= 240

To print the actual state of the problem, just type the variable name in the python console:

  >>> problem
  Farmer:
  MAXIMIZE
  600*x + 800*y + 0
  SUBJECT TO
  _C1: x + y <= 100

  _C2: 8 x <= 480

  _C3: 10 y <= 800

  _C4: 3 x + 2 y <= 240

  VARIABLES
  x Continuous
  y Continuous

Solving the problem

After the problem is modelled we can run it to make PuLP find a solution for us by calling the solve() method in the problem object.

problem.solve()

And check the status of the solution passing the problem.status variable to the PuLP array that contains all the status codes:

pulp.LpStatus[problem.status]

As you can check in this problem, the output was Optimal, which means that it found the optimal solution. Depending on the problem status, several outputs can be shown:

• Not Solved: The problem status when it is created, before calling problem.solve() method.
• Optimal: The optimal solution has been found.
• Infeasible: There are no feasible solutions, maybe a contradiction in the problem definition, or a range of variables that can’t exist like define two restrictions, one being \(x \leq 10\) and the other \(x \geq 20\)
• Unbounded: There are no upper or lower bound to the variables, so the solution tend to the positive or negative infinite.
• Undefined: Maybe there is an optimal solution but it may not have been found.

Getting the solution

To get the values for the solution of the problem, you can access both variables directly or you can access them using the problem variable. With the problem variable will look like this:

[(v.name, v.value()) for v in problem.variables()]

And it will show an array of tuples with the variables names and values

[('x', 20.0), ('y', 80.0)]

As you can check, we modelled the corn as being the \(x\) variable, and the optimal solution given by PuLP matches the optimal solution that we found by hand. The same occurs to the beans that we modelled as \(y\) variable.

You can also access directly the variables x and y.

>>> y.value()
80.0
>>> x.value()
20.0

The very last thing is to know our profit, it can be accessed using the pulp.value(objective) method, the objective variable that it expects is the problem.objective value. An example:

>>> pulp.value(problem.objective)
76000.0

As you can check, the very same solution that we found by hand. Here is the complete source code:

import pulp
problem = pulp.LpProblem("Farmer", pulp.LpMaximize)
x = pulp.LpVariable('x', lowBound=0, cat='Continuous')
y = pulp.LpVariable('y', lowBound=0, cat='Continuous')
problem += 600 * x + 800 * y, "Z"
problem += x + y <= 100
problem += 8 * x <= 480
problem += 10 * y <= 800
problem += 3 * x + 2 * y <= 240
problem.solve()

print("Problem status: " + pulp.LpStatus[problem.status])
print("Optimal corn amount to grow: "+str(x.value()))
print("Optimal beans amount to grow: "+str(y.value()))
print("By growing them the profit will be: "+str(pulp.value(problem.objective)))

Solving the example 1 by hand with tableau simplex method

To make it possible to solve a linear programming problem using the tableau simplex method, the first thing to be done is to rearrange the problem into the standard form.

Modeling example 1 in the standard form

In the standard form restriction equations can’t be written as inequalities, for example \(x <= 10\) is an inequality, and should be written as \(x = 10\). To make this transformation valid, we have to add another variable to the equation, this will be our slack variable \(fn\), so the equation will be rewritten as \(x + f1 = 10\).

If it is an \(\leq\) restriction, the \(fn\) variable is added to the equation, the opposite is also true, if the restriction is a \(\geq\) restriction, the \(fn\) variable is subtracted from the equation.

In case of a subtraction

For every slack variable that is subtracted, an artificial variable should be added \(a\) this variable is used to give an initial solution to the problem. Also, an artificial objective function \(W\) should be added, which initially is represented as:

\(W= a_1 + a_2 + a_3 + … + a_n\)

But before writing the \(W\) function we have to rewrite it as an expression using the problem variables instead of the artificial variables.

For example consider 3 restrictions:

• \(3x + 1y - f1 + a1 = 12\)
• \(3x + 4y - f2 + a2 = 30\)
• \(2x + 7y - f3 + a3 = 28\)

We isolate the artificial variable \(a\) as:

• \(a1 = 12 - 3x - 1y + f1\)
• \(a2 = 30 - 3x - 4y + f2\)
• \(a3 = 28 - 2x - 7y + f3\)

Then the initial \(W = a1 + a2 + a3\) that will be rewritten as:

\(W = (12 - 3x -1y + f1)+(30 - 3x -4y +f2)+(28 -2x -7y +f3)\)

\(W = 70 -8x -12y + f1 + f2 + f3\) \(W + 8x + 12y -f1 -f2 -f3 = 70\)

Then the \(W\) objective function is used in the first phase of this resolution instead of the original objective function \(Z\).

Continuing

All values presented in the right side of the equal sign must be constant, it include the objective function \(Z\). So any term in any equation in the right side that isn’t constant should be transfered to the left side of the equation.

The restrictions can be translated into the following equations:

• \(x + y + f1 = 100\)
• \(3x + 2y + f2 = 240\)
• \(y + f4 = 80\)
• \(x + f3 = 60\)
• \(x,y,f1,f2,f3,f4 \geq 0\)

With the objective function being translated into:

\(Z - 600x - 800y = 0\)

Table modeling

The tableau simplex method is based on tables, where each table represents a possible solution to the problem, it doesn’t mean that every table found is an optimal solution for the problem, but is a solution. This table is called basic feasible solution (BFS).

For every table we will have variables with positive values called basic variables and null variables (with their value being \(0\)) denominated non-basic variables. The number of basic variables in a problem is equivalent to the number of restrictions.

For every equation, the value in the right side of the equal sign is called Right Hand value.

For every restriction, there will be a line in the table and after it another line for the objective function \(Z\). The values of the non-basic variables will be added accordingly with their respective values in the restriction that they represent.

For this example, the first table will look like:

Table solving

The initial table state is the initial problem state, where no action has been taken, even solution will result in a new table after the calculations have done. To determine if the current table is an optimal solution there are two rules:

• No right hand value can be negative.
• In the case of a maximization problem, no value in the objective \(Z\) line can be negative. In the opposite case, a minimization problem the opposite is also true, we have an optimal solution if we only have any \(n \leq 0\) values.

The very first step to solve the table is to pick a pivot column, a column which will be the base for the calculation of the next table. So we choose the column (variable) that has more impact (has the smallest value) on the \(Z\) function, in this case the \(y\) column where the impact is \(-800\).

The second step is to choose the pivot line which means which restriction will be exhausted. So, for every value in the column, it will be checked against every restriction to determine which one will result in more performance for the \(Z\) function.

Using our example problem:

• Line 1, \(100 / 1 = 100\)
• Line 2, \(240 / 2 = 120\)
• Line 3, will generate a division by zero in the \(y\) column, it means that this line and column combination won’t affect the current situation.
• Line 4, \(80 / 1 = 80\)

Next step is define the pivotal line, this line means the best current move to explore so we can archive the desired goal for our objective function \(Z\). The line is chosen based on the smallest value on the list above, in this case, the line 4 with the value \(80\).

After that, the next step is to divide the whole pivot line by the value on the pivot column. And calculate the new values for the other lines by subtracting the chosen variable, in this case \(y\) by the value that we set in the pivot line, as following:

The new line 4 will be defined by \(NewLine4 = Line4 / y\), since \(y\) is 1, no changes will happen.

Where \(y=1\), meaning the value in the intersection between the pivot line and column. In the bellow examples, the \(y\) value mean the \(y\) value on the line of the respective line being calculated and \(NewLine4\) is the value for that column in the pivot line (Line 4).

• Line 1, \(NewLine1 = Line1 - y \times NewLine4\)
• Line 2, \(NewLine2 = Line2 - y \times NewLine4\)
• Line 3, \(NewLine3 = Line3 - y \times NewLine4\)
• Line \(Z\), \(NewLineZ = LineZ - y \times NewLine4\)

Making it more visual

Since the \(y=1\) this example isn’t that illustrative as the next ones will be it can seem a little confusing. Also we set the variable in the column as the variable (Basic Variable) in the first column. This will be the resulting table:

If still any negative value in the \(Z\) line, it means that we don’t have the optimal solution yet.

The next column will be the \(x\) column, since is the only one left, and the column will be calculated based on:

• Line 1: \(20 / 1 = 20\)
• Line 2: $80 / 3 = 26.66…$
• Line 3: \(60 / 1 = 60\)

The smallest value belongs to the line 2, so this will be our pivot line. Since again the value of \(x\) in the pivot line and column is one, the line 2 will be kept the same.

There are no more negative values in the \(Z\) line, so we archived the optimal solution. The final result will be the variable noted in the first column (Basic variable) with the value at the Right Hand, it will give \(x=20\) and \(y=80\).

Example 2

Since linear programming advances were due to the war, this example focus on the following problem. Imagine that there is a tank production factory, where to produce the tanks they need to cut some metal plates. Those plates come in 50cm sheets, and can be cut in three ways, a 15cm cut, a 17.5cm cut and a 20cm cut. The max allowed for any plates to be stored is 10 units per cut, it means that if you can’t produce 10 units of any measure above the required amount.

To finish the current tank is needed 32 plates of 15cm, 17 plates of 17.5cm and 21 plates of 20cm. How to cut the metal plates to minimize the loss and how many metal plates will be needed ?

Modeling the problem

The current problem is a minimization problem. An uncut metal plate have 50cm and can be cut in 3 ways, 15cm, 17.5cm and 20cm. So the first step is to determine the combination of possibilities and their respective losses.

Variables

This problem have only one variable, the amount of metal sheets cut under each size. But how to determine the possibilities ?

• Determine the possible arranges for the variables

  To determine the possibilities a simple combinatorial algorithm can answer how many different combinations and their respective losses.

    def combination(available, cuts):
        solutions = []
        for cut in cuts:
            if available >= cut:
                next = combination(available - cut, cuts)
                if len(next) == 0:
                    solutions.append([cut])
                else:
                    for possibilities in next:
                        possibilities.append(cut)
                        solutions.append(possibilities)
        return solutions
  
    combinations=list(set(map(tuple, map(sorted, combination(50, [15, 17.5, 20])))))
    for combination in combinations:
        print(str(combination) + " with loss of " + str(50-sum(combination)))
  

  It will output the combination of cuts that can be done for each 50cm metal plate as well how much metal will be lost with each combination.

  (15, 15, 17.5) with loss of 2.5
  (20, 20) with loss of 10
  (15, 15, 15) with loss of 5
  (15, 15, 20) with loss of 0
  (17.5, 20) with loss of 12.5
  (15, 17.5, 17.5) with loss of 0.0
  

  That can be translated into the list bellow:

  • \(x_1 = 15, 15, 15, Loss = 5\)
  • \(x_2 = 15, 15, 17.5, Loss = 2.5\)
  • \(x_3 = 15, 17.5, 17.5, Loss = 0.0\)
  • \(x_4 = 15, 15, 20, Loss = 0\)
  • \(x_5 = 17.5, 20, Loss = 12.5\)
  • \(x_6 = 20, 20, Loss = 10\)

Restrictions

• The max spare cut plate is 10 units of each size.
• minimum of 32 plates of 15cm
• minimum of 17 plates of 17.5cm
• minimum of 21 plates of 20cm

That using the variables above can be translated into:

• Min on 15cm plates: \(3 \times x_1 + 2 \times x_2 + 1 \times x_3 \geq 32\)
• Max on 15cm plates: \(3 \times x_1 + 2 \times x_2 + 1 \times x_3 \leq 42\)
• Min on 17.5cm plates: \(1 \times x_2 + 2 \times x_3 + 1 \times x_5 \geq 17\)
• Max on 17.5cm plates: \(1 \times x_2 + 2 \times x_3 + 1 \times x_5 \leq 27\)
• Min on 20cm plates: \(1 \times x_4 + 1 \times x_5 + 2 \times x_6 \geq 21\)
• Max on 20cm plates: \(1 \times x_4 + 1 \times x_5 + 2 \times x_6 \leq 31\)

And finally the non negativity rule: \(x_i \geq 0\)

Objective function

Since the problem is based on the minimization of loss, the output value of \(Z\) function is based on the loss of each cut.

\(Z = 5 \times x_1 + 2.5 \times x_2 + 0 \times x_3 + 0 \times x_4 + 12.5 \times x_5 + 10 \times x_6\)

For keep the explanation clear and straight to the point, all above formulas weren’t optimized in any way.

import pulp
problem = pulp.LpProblem("Tank", pulp.LpMinimize)

Then we create the \(x\) variables as integers (cat=Integer).

x_1 = pulp.LpVariable('x_1', lowBound=0, cat='Integer')
x_2 = pulp.LpVariable('x_2', lowBound=0, cat='Integer')
x_3 = pulp.LpVariable('x_3', lowBound=0, cat='Integer')
x_4 = pulp.LpVariable('x_4', lowBound=0, cat='Integer')
x_5 = pulp.LpVariable('x_5', lowBound=0, cat='Integer')
x_6 = pulp.LpVariable('x_6', lowBound=0, cat='Integer')

Next step is just transcribe the \(Z\) function and the restrictions as python code:

problem += (5 * x_1) + (2.5 * x_2) + (0 * x_3) + (0 * x_4) + (12.5 * x_5) + (10 * x_6), "Z"
problem += (3 * x_1) + (2 * x_2) + x_3 >= 32
problem += (3 * x_1) + (2 * x_2) + x_3 <= 42
problem += x_2 + (2 * x_3) + x_5 >= 17
problem += x_2 + (2 * x_3) + x_5 <= 27
problem += x_4 + x_5 + (2 * x_6) >= 21
problem += x_4 + x_5 + (2 * x_6) <= 21

Then just solve it calling problem.solve() function and print the results.

problem.solve()

print("problem status: " + pulp.LpStatus[problem.status])
print("Optimal amount to cut into x_1 = [15,15,15]: "+str(x_1.value()))
print("Optimal amount to cut into x_2 = [15,15,17.5]: "+str(x_2.value()))
print("Optimal amount to cut into x_3 = [15,17.5,17.5]: "+str(x_3.value()))
print("Optimal amount to cut into x_4 = [15,15,20]: "+str(x_4.value()))
print("Optimal amount to cut into x_5 = [17.5,20]: "+str(x_5.value()))
print("Optimal amount to cut into x_6 = [20,20]: "+str(x_6.value()))
print("The total metal loss is: "+str(pulp.value(problem.objective)))

plate15 = (3 * x_1.value()) + (2 * x_2.value()) + x_3.value()
plate17 = x_2.value() + (2 * x_3.value()) + x_5.value()
plate20 = x_4.value() + x_5.value() + (2 * x_6.value())

print("Total of 15cm plates "+str(plate15))
print("Total of 17.5cm plates "+str(plate17))
print("Total of 20cm plates "+str(plate20))

Bellow the whole code:

import pulp
problem = pulp.LpProblem("Tank", pulp.LpMinimize)
x_1 = pulp.LpVariable('x_1', lowBound=0, cat='Integer')
x_2 = pulp.LpVariable('x_2', lowBound=0, cat='Integer')
x_3 = pulp.LpVariable('x_3', lowBound=0, cat='Integer')
x_4 = pulp.LpVariable('x_4', lowBound=0, cat='Integer')
x_5 = pulp.LpVariable('x_5', lowBound=0, cat='Integer')
x_6 = pulp.LpVariable('x_6', lowBound=0, cat='Integer')
problem += (5 * x_1) + (2.5 * x_2) + (0 * x_3) + (0 * x_4) + (12.5 * x_5) + (10 * x_6), "Z"
problem += (3 * x_1) + (2 * x_2) + x_3 >= 32
problem += (3 * x_1) + (2 * x_2) + x_3 <= 42
problem += x_2 + (2 * x_3) + x_5 >= 17
problem += x_2 + (2 * x_3) + x_5 <= 27
problem += x_4 + x_5 + (2 * x_6) >= 21
problem += x_4 + x_5 + (2 * x_6) <= 21
problem.solve()

print("problem status: " + pulp.LpStatus[problem.status])
print("Optimal amount to cut into x_1 = [15,15,15]: "+str(x_1.value()))
print("Optimal amount to cut into x_2 = [15,15,17.5]: "+str(x_2.value()))
print("Optimal amount to cut into x_3 = [15,17.5,17.5]: "+str(x_3.value()))
print("Optimal amount to cut into x_4 = [15,15,20]: "+str(x_4.value()))
print("Optimal amount to cut into x_5 = [17.5,20]: "+str(x_5.value()))
print("Optimal amount to cut into x_6 = [20,20]: "+str(x_6.value()))
print("The total metal loss is: "+str(pulp.value(problem.objective)))

plate15 = (3 * x_1.value()) + (2 * x_2.value()) + x_3.value()
plate17 = x_2.value() + (2 * x_3.value()) + x_5.value()
plate20 = x_4.value() + x_5.value() + (2 * x_6.value())

print("Total of 15cm plates "+str(plate15))
print("Total of 17.5cm plates "+str(plate17))
print("Total of 20cm plates "+str(plate20))

It will output the result of the problem:

problem status: Optimal
Optimal amount to cut into x_1 = [15,15,15]: 6.0
Optimal amount to cut into x_2 = [15,15,17.5]: 1.0
Optimal amount to cut into x_3 = [15,17.5,17.5]: 13.0
Optimal amount to cut into x_4 = [15,15,20]: 21.0
Optimal amount to cut into x_5 = [17.5,20]: 0.0
Optimal amount to cut into x_6 = [20,20]: 0.0
The total metal loss is: 32.5
Total of 15cm plates 33.0
Total of 17.5cm plates 27.0
Total of 20cm plates 21.0

Conclusion

This is just an introduction to solving these kind of problems. If you are interested into getting more info, there are several books out there about it.

If you think that you can help make this post better, send me a PR

References

• Feasible Region
• PuLP Homepage
• PuLP Repository
• Simplex Algorithm
• Tableau Simplex
• The Simplex Method: Step by Step with Tableaus
• The Simplex Method in Tabular Form
• Lecture on Simplex method
• PERT page wikipedia

Bibliography

For further reading on this topic the book Linear programming and extensions by George Dantzig is recommended.