This tutorial offers various corrected exercises on modeling in primal form of linear programming.
Tutorial
A milling tool manufacturer makes 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 manufactured with 2 units of steel, 1 units of removable carbide and 1 unit of synthetic diamond.
The stocks are 5 units of steel, 5 units of carbide and 2 units of diamond. The manufacturer wants to build at least 5 type A cutters and 5 type B cutters. The maintenance cost of the factory is 2500. How should the manufacturer allocate 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 as the end point the intersection of the second and third constraint. We must therefore solve the system:
Which has for solution the vector (10, 2). This 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 factory.
Exercise 1
A brooker needs, for its 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 transit. 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 brooker 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 field of definition in green, point C is the only extremum being a global optimum. Solving the previous system in the form of equality gives the 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 the same for the graphic resolution part. Here are the corrections of the simplexes with the initial state and the final state of the table 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 there are the workers. In general, there are 4 types of workers depending on their weekend. The workers' wages depend on these days of leave:
The daily demands for workers are as follows:
How many people in each category must be employed in order to meet the demand and minimize the cost of personnel? Give the canonical form of the problem and solve it using 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 integers, which is practical given the problem (it seems obvious that “integer” individuals are needed).
Exercise 4
A company makes 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 needs for a 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 brings in 6 euros if it is of type A, 2 euros if it is of type B, and 4 euros if it is of type C. The available resources are 6000 kg of raw materials, 4000 hours of labor. work, and 2,500 storage volume units.
Model the linear program and solve it by hand using the simplex.
A competitor, who lacks raw materials, offers to buy 300 kg from this company, at a price of 1.5 euros per kg. Do you think the company should accept this proposal? (Assume that she accepts it if it is profitable, solve 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 test, insulation treatment. Only batteries which 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 9,000 hours of machine time for assembly, 1,200 hours for quality testing and 8,500 hours for insulation processing. 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 electricity grid, the amount of energy that can pass from power plants 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 the 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, that is to say that 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 be made to transit from S to T. The solution will provide the amount of energy passing through each line. To calculate this flow, an arc is added between the fictitious well and the unconstrained fictitious 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 passing through a line cannot be greater than the capacity of the line.
- the energy passing through a line is positive or zero.
The variables are therefore:
- for each row, a variable describes the amount of energy passing through 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:
EN 
FR 
ES