This tutorial offers various corrected exercises on modeling in primal form of linear programming.
Tutorial
A milling tool manufacturer manufactures two types of cutters: A and B. Type A cutters sell for 300 each, and are manufactured with 1 unit of steel, 2 units of removable carbide and 1 unit of diamond synthetic. Type B cutters sell for 200 each, and are made with 2 units of steel, 1 units of removable carbide and 1 unit of synthetic diamond.
Stocks are 5 units of steel, 5 units of carbide and 2 units of diamond. The fabricator wants to build at least 5 type A cutters and 5 type B cutters. The cost of upkeep of the factory is 2500. How should the fabricator distribute his production to maximize his profit, is it profitable?
First, the linear program must be carried out:
- Objective function: z = 300A + 200B-2500
- Constraints:
- A + 2B ≤ 5
- 2A + B ≤ 5
- A + B ≤ 2
- A ≥ 5
- B ≥ 5
The program is not in canonical form, it must be rendered in this form before solving it.
Let x1 = A-5 and x2 = B-5. The linear program becomes the following:
The linear program has 2 variables, so it is possible to solve it graphically. The constraints give the domain of the following solutions:
The gradient of the objective function is (3,2), which gives the end point the intersection of the second and third constraints. So we have to solve the system:
Which has the vector (10, 2) as its solution. Which gives in the initial problem the vector (15, 7) and for objective function equal to 900. The operation is positive and therefore profitable for the plant.
Exercise 1
A broker needs, for his customers, 108 MWh of electricity for city 1 and 96 MWh of electricity for city 2. However, Kirchhoff's laws do not allow a distributor to target a single city for the energy flow. Two distributors serve these cities: Distributor A can send 12 MWh to city 1 and 8 MWh to city 2 per lot purchased; Distributor B can send 9 MWh to city 1 and 12 MWh to city 2 per lot purchased. The lots all have the same price. How many lots must the broker buy to meet the energy demand of the two cities? Solve by graphical method.
The linear program is as follows: X1 for the first batch and X2 for the second batch
Which gives for graphic resolution:
The gradient is (-1, -1) because it is a minimum (min f(x) = – max -f(x)). In the domain of definition in green, point C is the only extremum being a global optimum. The resolution of the previous system in the form of equality gives for coordinates (6, 4) with Z = 10.
Exercise 2
Solve by the graphical method then by the simplex the following problems:
- A company that manufactures two types of products seeks to maximize its profit. Here is his roadmap.
- Likewise with the following linear program:
The methodology is always identical for the graphic resolution part. Here are the simplex fixes with the initial state and final state of the array for the first example.
Problem 0:
And for solution:
The objective function has for value Z = 1875 with P1 and P2 in base (therefore not zero) having respectively for value (25,15) as stipulated in column b represented by P0.
The second linear program has for solution Z = 8.2 with the vector of basic variables (3.2, 1.8).
Exercise 3
BIM optimizes the construction, renovation and maintenance of buildings. Among the elements to be optimized are the workers. In general, there are 4 types of workers depending on their weekend. The wages of the workers depend on these days off:
The daily demands for workers are as follows:
How many people in each category should be employed in order to satisfy demand and minimize the cost of personnel? Give the canonical form of the problem and solve using the Solver Excel.
The linear program is as follows:
The resolution by Excel is as follows:
The result is the following:
Note that the optimal solution is not unique. The solution gives whole numbers, which is practical given the problem (it seems obvious that “whole” individuals are needed).
Exercise 4
A company manufactures three types of products, A, B and C. Each product requires raw materials and labor, as well as storage space. Here are the raw material, labor and storage requirements for one unit of each of the 3 types of products:
- Product A: 4 kg of raw materials, 2 hours of labor, 1 unit of volume.
- Product B: 2 kg of raw materials, 1/2 hour of labor 1 unit of volume.
- Product C: 1 kg of raw materials, 3 hours of labor, 1 unit of volume.
Each product earns 6 euros if it is type A, 2 euros if it is type B, and 4 euros if it is type C. The available resources are 6000 kg of raw materials, 4000 hours of labor work, and 2500 storage volume units.
Modeling the linear program and solving it by hand using the simplex.
A competitor, who lacks raw materials, offers to buy back 300 kg from this company, at a price of 1.5 euros per kg. Do you think the company should accept this proposal? (It will be assumed that it accepts it if it is profitable, solving the problem by hand with the simplex.)
The problem in standard form is as follows:
With the simplex solution:
The redemption problem has additionally in the objective function 450. The first variable has for element b = 5700. In this case the optimal solution is (1310, 0, 460) with Z = 10150, so the proposition is profitable.
Exercise 5
A company manufactures three types of batteries: dry type 1 (PS1), dry type 2 (PS2) and fuel (PC). The manufacturing process has three stages: assembly, quality testing, insulation treatment. Only batteries that pass the quality test are subjected to the insulation treatment. Batteries that fail the quality test are discarded. Over the next month, the company will have machine time of 9,000 hours for assembly, 1,200 hours for quality testing and 8,500 hours for insulation treatment. The following table summarizes the relevant information of the manufacturing process:
What is the optimal number of batteries of each type to manufacture next month if the company is sure to sell all of its production?
Let X1, X2, X3 be the three variables representing the number of valid stacks of each type and X4, X5, X6 the three variables representing the number of invalid stacks of each type.
The linear program in canonical form is as follows:
This gives as a solution (419417.476, 0, 741176.471) for valid batteries and for objective function Z = 1278957.05. As the solution does not give an integer result, it is possible to truncate the floating part (be careful, this will no longer be an optimal solution!).
Exercise 6
In an electrical network, the amount of energy that can pass from power stations to cities is limited by the capacities of very high voltage lines. The problem is described as follows:
- Sources, represented by vertices, produce a quantity of energy
- Wells, represented by vertices, receive a quantity of energy
- Lines, represented by edges between a pair of vertices, through which energy passes.
This graph reads as follows:
- S is a fictitious source, which describes the production of the energy sources represented by vertex 1 and vertex 2.
- T is a fictitious well, which describes the energy reception of the cities represented by vertex 3 and vertex 4.
- The lines are oriented, ie the energy only passes in one direction. For example the link (1, 3) can circulate up to 4 units of energy between vertex 1 and vertex 3.
- The links between S and the sources describe the energy production of the source. For example the link (S, 1) says that source 1 can produce up to 10 units of energy.
- The links between the wells and T describe the energy demand of the well. For example the link (3, T) says that city 3 requires 10 units of energy.
The objective function of this type of problem is:
- maximize the amount of energy that can flow from S to T. The solution will provide the amount of energy flowing in each row. To calculate this flow, an arc is added between the fictitious sink and the fictitious unconstrained source. The optimal solution is equal to the flow passing through this arc.
This problem is subject to two types of constraints:
- the sum of the energies entering a vertex minus the sum of the energies exiting the same vertex is zero. That is to say that there are no energy losses in the network
- the energy transiting by a line cannot be higher than the capacity of the line.
- the energy passing through a line is positive or zero.
The variables are therefore:
- for each line, a variable describes the amount of energy transiting on it.
Formulate the linear problem for the graph given above and solve it via Excel.
The linear problem is written in Excel as follows:
Which gives as result:
