Linear Programming: How to Find the Optimal Solution

Linear Programming Video Lessons

How to do Linear Programming

What is Linear Programming?

Linear programming is an algebraic method for finding an optimal value in a situation in which there are constraints. The process involves forming constraint equations, graphing the feasible region and substituting vertices into the objective function to find a minimum or maximum value.

• Constraint equations are found for each category. The amounts used in each category are compared to the total amount of each that is available or required.
• The feasible region is the shaded region between the constraint equations. All combinations of coordinates within this region satisfy the requirements of the problem.
• The vertices are the corners of the feasible region. These are the most extreme cases of the solutions found in the feasible region and therefore, the optimal solution is found at one or more of these vertices.
• The objective function is the equation which we want to maximise or minimise.

This process of testing the vertices in the objective function to find the optimal solution is known as the simplex method.

Linear programming is used in a variety of real life contexts such as:

• Manufacturing: Maximising profits by finding the optimal combination of products to manufacture.
• Engineering: Minimising wastage in a design whilst still meeting structural requirements.
• Business: Allocating resources and budgets to complete a project with minimal cost.
• Transportation: Minimising travel time when subject to limited resources or work force.
• Finance: Maximising profit or minimising risk of investments made in a portfolio.
• Scheduling: Minimising project completion time or constructing timetables.

How to Do Linear Programming to Find an Optimal Solution

To Find an optimal solution with linear programming:

1. Form the constraint equations.
2. Sketch the constraint equations.
3. Find the vertices of the feasible region.
4. Substitute the coordinates of the vertices into the objective function.
5. The optimal solution is the vertex at which the maximum or minimum value is obtained.

Linear Programming: How to Find a Minimum

To solve a minimisation linear programming problem:

1. Form the constraint equations.
2. Sketch the constraint equations.
3. Find the vertices of the feasible region.
4. Substitute the coordinates of the vertices into the objective function.
5. The optimal solution is the vertex at which the minimum value is obtained.

A minimisation problem will involve searching for the feasible solution that minimises the objective function.

Typical minimisation problems involve the minimisation of cost, weight or time.

Typically, the constraint equations of a minimisation problem will be of the form instead of . Although this is a generalisation and not always the case.

---

Here is an example of a minimisation problem in linear programming.

An athlete desires to have at least 60g of carbohydrates, 100g of protein and no more that 80g of fat each day.

He considers two different supplements to meet this requirement.

• Tins of supplement A cost $20 and contain 20g of carbohydrates, 25g of protein and 10g of fat.
• Tins of supplement B cost $30 and contain 20g of carbohydrates, 50g of protein and 20g of fat.

Find the combination of supplements that will meet his needs in the cheapest way.

In linear programming, it is helpful to write a paragraph of text as a table of ordered information as this allows the constraint equations to be found more easily.

Label each row of the table with the two items which we want to optimise.

In this example, that is supplement A and supplement B.

Label each column of the table with the categories that the two items contain.

In this example, each supplement contains carbohydrates, protein, fat and they have a cost. Therefore these are the names of each column.

The constraints are written by finding the total amount of each category that is available or required.

In this example, the athlete has a daily requirement for each of carbohydrate, protein and fat.

Since he requires at least 60g of carbohydrates, we write ≥ 60.

The amount of carbohydrates must be at least 60. This means it can be equal to 60 or greater but it cannot be less than 60.

Since he requires at least 100g of protein, we write ≥ 100. This means his total daily protein must be greater than or equal to 100.

However, since he must have no more than 80g of fat, he must have equal to 80g of fat or less than this. He cannot have more than 80g of fat. Therefore we write ≤ 80.

Step 1. Find the Constraint Equations

To write constraint equations:

1. Label the amount of the two items as x and y respectively.
2. For each category, multiply the number each item contains by x or y respectively.
3. Write the sum of these terms ≤ the total maximum limit or ≥ the total minimum requirement.

Here are some common meanings of the inequality signs.

In linear programming, when there is a minimum requirement for a particular resource we use the ≥ symbol.

When there is a fixed total maximum limit of a resource that is available, we use the ≤ symbol.

We will look at the constraint equation for each category individually.

Considering the carbohydrates constraint:

Supplement A (which we will label as x) contains 20g of carbohydrate.

So the total carbohydrate from A is equal to 20x.

Supplement B (which we will label as y) contains 20g of carbohydrate.

So the total carbohydrate from supplement B is equal to 20y.

The total carbohydrate from both supplements is therefore 20x + 20y.

In total, at least 60g of carbohydrate is required so we write ≥ 60.

Therefore, the constraint equation for carbohydrate is 20x + 20y ≥ 60.

This equation can be simplified easily by dividing all terms by 10 to obtain 2x + 2y ≥ 6.

It could also be simplified further by halving each term to obtain x + y ≥ 3 if needed.

The simplification of the constraint equations is not a necessary step.

Considering the protein constraint:

Each tin of supplement A contains 25g of protein, so the total protein from all of supplement A is 25x.

Each tin of supplement B contains 50g of protein, so the total protein from all of supplement B is 50y.

The total protein from both supplements is therefore 25x + 50y.

The athlete requires at least 100g of protein each day, so we write ≥100.

Therefore the constraint equation is 25x + 50y ≥ 100.

This can be simplified by dividing each term by 25 to obtain x + 2y ≥ 4.

Considering the fat constraint:

Each tin of supplement A contains 10g of fat, so the total fat from all of supplement A is 10x.

Each tin of supplement B contains 20g of fat, so the total fat from all of supplement B is 20y.

The athlete must have no more than 80g of fat in total so we write ≤ 80.

The inequality is now less than or equal to as the total fat must be less than or equal to 80.

The constraint is 10x + 20y ≤ 80.

This can be simplified by dividing each term by 10 to obtain x + 2y ≤ 8.

How to Find the Objective Function

The objective function is the equation that is to be maximised or minimised. It is of the form O = px+qy where x and y are the number of the two items being used and p and q are the constraints.

• If the cost is being minimised then p and q are the costs of x and y respectively.
• If the profit is being maximised then p and q are the profits from x and y respectively.
• If the weight is being minimised then p and q are the weights of x and y respectively.
• If the time is being minimised then p and q are the times of x and y respectively.
• If the volume is being maximised then p and q are the volumes of x and y respectively.

In this example, we are maximising cost. Therefore p and q are the costs of x and y respectively.

We write C = 20x + 30y.

Step 2. Sketch the Constraint Equations and Feasible Region

To sketch constraint equations:

1. Substitute x = 0 and solve for y to find the y-intercept.
2. Substitute y = 0 and solve for x to find the x-intercept.
3. Draw the line between the intercepts.
4. Draw a horizontal line if the constraint is of the form y=a and a vertical line if it is of the form x=b.
5. Shade below the line if y<, above the line if y>, left of the line if x< and right of the line if x>.

A summary of where to shade for each given inequality is shown below.

If the constraint is of the form:

• x≤a then shade left of the line.
• x≥a then shade right of the line.
• y≤a then shade below the line.
• y≥a then shade above the line.
• x+y≤a then shade below the line.
• x+y≥a then shade above the line.

Note that if the coefficients of x or y are negative, then the opposite will apply.

---

The first constraint to draw is 2x + 2y ≥ 6.

The x intercept is found by substituting y=0 into 2x + 2y = 6.

We obtain 2x = 6 and so, x = 3.

The y intercept is found by substituting x=0 into 2x + 2y = 6.

We obtain 2y = 6 and so, y = 3.

We connect the x and y intercepts with a straight line as shown below.

Since the equation contains a greater than or equal to sign (≥), we shade above the line.

The next constraint to draw is x + 2y ≥ 4.

The x intercept is found by substituting y=0 into x + 2y = 4.

We obtain x = 4 and so, x = 4.

The y intercept is found by substituting x=0 into x + 2y = 4.

We obtain 2y = 4 and so, y = 2.

We connect the x and y intercepts with a straight line as shown below.

Since the equation contains a greater than or equal to sign (≥), we shade above the line.

The final constraint to draw is x + 2y ≤ 8.

The x intercept is found by substituting y=0 into x + 2y = 8.

We obtain x = 8.

The y intercept is found by substituting x=0 into x + 2y = 8.

We obtain 2y = 8 and so, y = 4.

We connect the x and y intercepts with a straight line as shown below.

Since the equation contains a greater than or equal to sign (≤), we shade below the line.

The feasible region is the region that satisfies all of the constraint equations. To graph the feasible region, shade above lines containing ‘≥’ and below lines containing ‘≤‘. If the coefficients of x or y are negative, the opposite applies.

In this example, we shade where the previously drawn lines are all pointing.

That is, above 2x+2y≥6. above x+2y≥4 and below x+2y≤8.

Step 3. Find the vertices of the feasible region.

The vertices of the feasible region are the corners of the shaded region. They are found wherever two or more constraint lines intersect. The optimal solution will be found at one or more of these vertices.

The vertices of this feasible region are:

(0,3) (0,4) (2,1) (4,0) and (8,0).

Step 4. Substitute the coordinates of the vertices into the objective function.

The vertices made up of a pair of coordinates (x, y) and are found at the corners of the feasible region. Substitute the values of x and y from these coordinates into the objective function to find the optimal solution.

We will do this ‘simplex process’ for each of the vertices.

The objective function is C = 20x + 30y.

• At (0, 3), x=0 and y=3. The objective function becomes .
• At (0, 4), x=0 and y=4. The objective function becomes .
• At (2, 1), x=2 and y=1. The objective function becomes .
• At (4, 0), x=4 and y =0. The objective function becomes .
• At (8, 0), x=8 and y=0. The objective function becomes .

Step 5. The optimal solution is the vertex at which the minimum value is obtained

In linear programming, the optimal solution is the maximum or minimum value of the objective function. This is always found at one of the vertices of the feasible region.

In this example, we wish to find the combination of supplements that meet the athlete’s needs at the cheapest cost.

The cheapest combination was the value which minimised the cost equation.

This was at the vertex (2, 1) with a cost of $70.

The vertex (2, 1) means that x=2 and y=1.

x is the number of supplement A that should be used.

y is the number of supplement B that should be used.

Therefore, the athlete should use 2 tins of supplement A and 1 tin of supplement B at a total cost of $70.

Linear Programming: How to Find a Maximum

To solve a maximisation linear programming problem:

1. Form the constraint equations.
2. Sketch the constraint equations.
3. Find the vertices of the feasible region.
4. Substitute the coordinates of the vertices into the objective function.
5. The optimal solution is the vertex at which the maxmimum value is obtained.

Here is an example of maximising an objective function using linear programming.

A restaurant produces two different breakfast options, small and large. Each day there are only 20 eggs and 12 tomatoes available to use in these breakfasts.

The small breakfast sells for $10 profit and contains 2 eggs and 1 tomato.

The large breakfast sells for $15 profit and contains 2 eggs and 2 tomatoes.

No more than 4 large breakfasts can be produced each day.

Find the number of each breakfast that should be made to maximise profit.

Step 1. Form the constraint equations.

We will let x be the number of small breakfasts produced each day.

We will let y be the number of large breakfasts produced each day.

Considering the eggs constraint:

The total eggs used in small breakfasts is 2x.

The total eggs used in large breakfasts is 2y.

There are only 20 eggs available therefore the total eggs used in all breakfasts must be less than or equal to 20.

2x + 2y ≤ 20.

We can simplify this by dividing each term by 2 to obtain x + y ≤ 10.

Considering the tomatoes constraint:

The number of tomatoes in the small breakfasts is just x.

The number of tomatoes in the large breakfasts is 2y.

There are only 12 tomatoes available so the total tomatoes must be less than or equal to 12.

x + 2y ≤ 12.

Considering that no more than 4 large breakfasts can be produced:

y is the number of large breakfasts. From this constraint, the number of large breakfasts must be less than or equal to 4.

Therefore y ≤ 4.

The objective function is the profit since we wish to maximise this.

The profit from the small breakfasts is 10x and the profit from the large breakfasts is 15y.

Therefore the objective function is P = 10x + 15y.

Considering the non-negative constraints:

We know that it is impossible to produce less than 0 of each type of breakfast, therefore the number of each type of breakfast must be greater than or equal to zero.

In linear programming, the non-negative constraints are x≥0 and y≥0. This means that the problem is confined to the positive quadrant involving only positive values of x and y.

They are included whenever the quantities being optimised cannot be negative, which is the case in the production or consumption found in real life problems.

Step 2. Graph the Constraint Equations

The non-negative constraints require us to only consider the top right quadrant with positive x and y values. The feasible region will be above the x-axis and to the right of the y-axis.

We have the three constraints x+y≤10, x+2y≤12 and y≤4.

Considering x+y≤10:

The x-intercept is found by substituting y=0 into x+y=10. We obtain x=10.

The y-intercept is found by substituting x=0 into x+y=10. We obtain y=10.

We then connect these intercepts to find the line.

We shade below the line since the inequality in the constraint is ‘≤’.

Considering x+2y≤12:

The x-intercept is found by substituting y=0 into x+2y=12. We obtain x=12.

The y-intercept is found by substituting x=0 into x+2y=12. We obtain 2y=12 and y = 6.

We then connect these intercepts to find the line.

We shade below the line since the inequality in the constraint is ‘≤’.

Considering y≤4:

y=4 is a horizontal line at a height of y=4.

We shade below the line since the inequality in the constraint is ‘≤’.

Step 3. Find the Vertices of the Feasible Region

The feasible region is found below all three of the given constraint equations.

This is the shaded region shown below.

The vertices of this region are: (0,4), (4, 4), (8, 2) and (10,0). There is also (0,0) but producing zero of each breakfast option will certainly not result in the optimal profit.

Step 4. Substitute the coordinates of the vertices into the objective function.

The objective function to be maximised is P = 10x + 15y.

• At (0, 4), x=0 and y=4. The objective function becomes .
• At (4, 4), x=4 and y=4. The objective function becomes .
• At (8, 2), x=8 and y=2. The objective function becomes .
• At (10, 0), x=10 and y=0. The objective function becomes .

Step 5. The optimal solution is the vertex at which the maximum value is obtained.

The optimal solution is produced from the vertex which maximises the profit.

This is found at (8, 2) where $110 profit is made.

This is the largest profit result produced.

Therefore 8 small breakfasts and 2 large breakfasts should be produced to maximise the profit and make $110.

How to Find Vertices in Linear Programming

The vertices can be observed by looking at the corners of the feasible region. Where the coordinates are not clear, vertices can be calculated accurately by solving the simultaneous equations formed by the two constraint equations that intersect at that particular point.

For example, consider the feasible region given by the constraints:

and .

From the graph below it can be seen that the vertex lies at the coordinate (5, 3). This is where x=5 and y=3.

However, if we were not sure of this, we could find the coordinate of the vertex by solving the two constraint equations simultaneously.

We will call equation (1).

We will call equation (2).

To solve these equations simultaneously, we will multiply the equations so that there is a common term in both.

Multiplying equation (1) by 2, we obtain:

Multiplying equation (2) by 5, we obtain:

We write the equations above one another like so:

We subtract the top equation from the bottom equation to obtain:

Dividing both sides of the equation by 19, we obtain .

To find y, we substitute back into one of the original equations. We will use equation (1).

becomes or .

Subtracting 15 from both sides, we obtain .

Dividing both sides by 15 results in .

Therefore, we obtain (5, 3) as the vertex.

Linear Programming with Multiple Optimal Solutions

Multiple optimal solutions occur if two or more vertices result in the same optimal solution. All points between these vertices will be optimal solutions too. Multiple solutions occur when the slope of the objective function is parallel to the constraint line connecting the multiple optimal solutions.

---

Here is an example of linear programming in which multiple optimal solutions occur.

A car manufacturer has access to 16 exhausts, 36 metal panels and 14 gearboxes.

He is able to manufacture 2 different models of car: Car model A and Car model B.

Car model A costs $20 000 and it requires 1 exhaust, 1 metal panel and 1 gearbox.

Car model B costs $40 000 and it requires 2 exhausts, 6 metal panels and 1 gearbox.

They wish to decide on the number of each car model to make to maximise their profits.

Since the total number of exhausts used must be less than or equal to 16, we obtain:

Since the total number of metal panels used must be less than or equal to 36, we obtain:

Since the total number of gearboxes used must be less than or equal to 14, we obtain:

The objective function to be maximised is the cost.

The constraints are drawn resulting in the feasible region shown below.

The vertices of the feasible region are: (0, 6), (6, 5), (12, 2) and (14, 0).

Substituting these into the objective function results in two maximum values.

Both (6, 5) and (12, 2) result in the objective function maximised at 320.

Since both (6, 5) and (12, 2) provide the optimal solution, we must also look at all solutions that lie on the line connecting these two points.

Since we are considering how many of each car model to manufacture, the solutions must be whole numbers rather than decimals.

So along with (6, 5) and (12, 2), we also have (8, 4) and (10, 3) as shown below.

Therefore the optimal solutions are (6, 5), (8, 4), (10, 3) and (12, 2).

All of these solutions will result in the same optimal objective function of 320.

This means that we should produce either of the following combinations to make a profit of $320 000:

6 of Car A, 5 of Car B

8 of Car A, 4 of Car B

10 of Car A, 3 of Car B

12 of Car A, 2 of Car B.

---

We will now look algebraically how multiple optimal solutions can be identified.

Multiple optimal solutions will be present when the objective function is parallel to a constraint of the feasible region. That is, the objective function will be a multiple of one of the constraint equations.

In this example, the objective function is .

can simplify to by dividing both terms by 20.

This is the same form as the constraint equation on which the multiple optimal solutions lie.

Therefore if the objective function is a multiple of one of the constraint equations, it will be parallel to it and multiple optimal solutions will lie on this line.

The objective function is parallel to the constraint .

When the cost is equal to 320 (the maximum value of the objective function), we have .

The line of is identical to the line of .

Therefore the optimised value of the objective function is 320.

The optimised value of the objective function is the value that the objective function is equal to so that when graphed, the objective function line lies on the boundary of the feasible region.

Infinite Solutions in Linear Programming

Linear programming problems can have infinite optimal solutions if two vertices result in the same optimised value of the objective function and the solutions can take non-integer values. The infinite solutions are found between the values of the two vertices.

---

Here is an example of a linear programming problem with infinite solutions.

A company has 18kg of gravel, 21kg of cement, 4kg of sand with which it can make two different concrete mixes.

Concrete A costs $2000 and it requires 3kg of gravel, 7kg of cement and 1kg of sand.

Concrete B costs $2000 and it requires 6kg of gravel, 3kg of cement and 1kg of sand.

The company can produce concrete in any measure quantity and wish to maximise their profits.

The constraint equations are given by:

Gravel:

Cement:

Sand:

The objective function is the cost of purchase, which we wish to maximise.

The objective function is written as .

The feasible region is shown below all three of the constraint lines.

The vertices of the feasible region are: (0, 3), (2, 2), (2.25, 1.75) and (3,0).

Substituting these vertices into the objective function, we obtain two optimal answers of $8000 found at both (2,2) and (2.25, 1.75).

Since the concrete can be produced in any given quantity, the optimal solution does not need to take integer solutions and so, (2.25, 1.75) is a valid solution.

It simply means 2.25kg of concrete A and 1.75kg of concrete B.

Since there are two vertices which maximise the objective function, we have multiple solutions.

When two vertices optimise the objective function, they are both solutions and all points between these two points are also solutions.

Since the concrete does not need to take only integer values, it can take all decimal values between the points of (2,2) and (2.25, 1.75).

There are an infinite number of different decimal numbers this could be and therefore there are infinite solutions to this linear programming problem.

Whenever a linear problem has multiple solutions and can take non-integer values, there are an infinite number of solutions.

The green line below shows the range where the infinite solutions take place. All of these combinations of concrete result in a cost of purchase of $8000.

Integer Solutions to Linear Programming

If a linear programming solution can only take integer (whole number) values then also consider integer solutions inside the feasible region that are close to any decimal vertices and substitute these into the objective function as well.

Many linear programming problems deal with quantities that must take integer values.

Integers are whole numbers.

Only linear programming involving continuously measured quantities will permit non-integer solutions. Examples where non-integer solutions are allowed include problems involving weight, volume, capacity, area and length.

---

Here is an example in which only integer solutions are permitted.

A construction needs to be able to support at least 4 units of lateral load and at least 10 units of vertical load.

Steel beams weigh 50kg and support 1 unit of lateral load and 5 units of vertical load.

Wooden beams weigh 30kg and support 2 units of lateral load and 2 units of vertical load.

Find the optimal combination of beams that support the required loads but minimise the weight.

Since we cannot use fractional amounts of each beam, we can only use whole numbers in our solution. We can only take integer solutions.

The lateral support constraint is: .

The vertical support constraint is: .

The objective function that must be minimised is the weight: .

The two constraint equations are shown graphed on the axes below.

We shade above both lines.

The vertices of the feasible region are (0, 5), (4,0) and (1.5, 1.25).

At (0,5) we the value of the objective function is 150 and at (4, 0) the value of the objective function is 200.

We do cannot use the third vertex of (1.5, 1.25) as it does not contain only whole numbers.
We cannot use 1.5 or 1.25 of a beam in this problem.

Therefore we must look at whole number points that are inside the feasible region, near to this decimal vertex of (1.5, 1.25).

The closest whole number solutions are shown below with red coordinates.

We can look at (2, 2), (3, 1) and (1, 3).

We see that (2, 2) gives an objective function result of 160, (3, 1) results in 180 and (1, 3) results in 140.

Therefore the weight is minimised at (1, 3) with a weight of 140kg.

It is important to notice that the optimal solution in this example was found at (1, 3) which was not a vertex of the feasible region.

In all other instances, the optimal solution is always found at a vertex.

However, if one vertex is a decimal, it is possible that the optimal solution may be found inside the feasible region, nearby to it.

Linear Programming Without Graphing

Linear programming can be solved algebraically without graphing. Whilst graphing is often a faster process that assists the visualisation of the solution, it may not be practical for problems involving more constraints and linear programming can be solved in an algebraic manner or using a computer.

To solve linear programming problems without graphing:

• Find the point of intersection for each of the possible different pairs of constraint equations.
• Substitute these points into the other constraint inequalities.
• Remove any points that fail the constraint inequalities.
• Substitute the remaining points into the objective function to find the optimal solution.

Here is an example of solving a linear programming constraint problem without graphing.

Step 1. Find the point of intersection for each of the possible different pairs of constraint equations

We consider and .

Solving these equations simultaneously, we obtain and .

This results in a vertex at (2, 1).

We test this solution in the other constraint equations of , and .

and both values are greater than zero. Therefore this solution (2, 1) is valid and is inside the feasible region.

Now we consider the pair of constraints and .

These equations have a solution of and .

This results in a vertex of (-2, 5).

However x=-2 does not satisfy the constraint of and so, this solution cannot be used as it lies outside of our feasible region.

The final combination of constraints is and .

There is no solution to this pair of equations.

We now continue by considering the solutions found by the following pairs of constraints.

and : We obtain (0, 3).

and : We obtain (3, 0). However this solution does not satisfy and so it must be removed.

and : We obtain (0, 2). However this solution does not satisfy and so we remove it.

and : We obtain (4, 0).

and : We obtain (0, 4).

and : We obtain (8, 0).

The final list of vertices is therefore:

(0, 3), (0, 4), (2, 1), (4, 0), (8, 0).

These are then all substituted into the objective function to find the optimal result.

In this example, the objective function is and it is minimised with the solution (2, 1) with a value for the objective function of $70.

Linear Programming with 3 Variables

Linear programming problems with 3 variables can be solved graphically in 3 dimensions. 3D software is beneficial. Alternatively, it can be easier to solve linear programming with 3 or more variables computationally.

Here is an example in which a linear program problem involving 3 variables will be solved graphically.

We will see how linear programming constraint equations will be created in 3 variables: x, y and z.

---

A tour operator offers three different tours each day.

The City Tour requires 1 bus, 3 tour guides and 2 microphones. It makes $1000 profit.

The Country Tour requires 3 buses, 4 tour guides and 3 microphones. It makes $3000 profit.

The Scenic Tour requires 2 buses, 6 tour guides and 6 microphones. It makes $2500 in profit.

In total the tour operator has 20 buses, 50 tour guides and 42 microphones available to allocate.

The information is laid out as in the table above for clarity.

The bus constraint equation is .

The tour guide constraint equation is .

The microphone constraint equation is

The objective function that we wish to maximise is the profit: .

With linear programming with 3 variables 3 dimensions are considered in which each constraint equation forms a plane rather than a line.

The three constraint equations are depicted below as planes. The feasible region is bounded below each of these planes and the x, y and z axes.

The vertices of the feasible region can be found where each plane intersects the axes and also where the three planes intersect.

The vertices of this feasible region are where the three planes intersect and also where the planes intersect each axis.

The vertices of the feasible region are (16.67, 0, 0), (0, 0, 7), (0, 6.67, 0), (6, 2, 4), (0, 3, 5.5) and (8, 0, 4.33).

Substituting these values into the objective function, it is maximised at (0, 3, 5.5).

However since we cannot use decimal solutions (we cannot have 5.5 of a tour), we must search nearby to this vertex for other optimal solutions.

Instead the optimal solution is (1, 3, 5) which results in a profit of $22 500.