Linear programming in excel production plan. Solving transport problems. Purpose of the laboratory lesson
An example of solving a linear programming problem using MS Excel
The farm specializes in field farming for the production of grain, sugar beets and sunflowers. In agriculture The enterprise has 3,200 hectares of arable land, labor resources in the amount of 7,000 man-days and mineral fertilizers in the amount of 15,000 c.d.w. It is necessary to find a combination of acreage that would ensure maximum profit.
It should also be taken into account that
- the area sown with industrial crops (sugar beets and sunflowers) should not exceed 25% of the total area of arable land;
- The farm concluded a contract for the sale of grain in the amount of 65,000 c.
To develop an economic and mathematical model, it is necessary to prepare input information (Table 1).
Table 1
|
Indicators |
Agricultural crops |
||
|
cereals |
sugar beet |
sunflower |
|
|
Productivity, c/ha |
|||
|
Selling price of 1 centner of products, rub./c. |
|||
|
Cost of marketable products per 1 ha, thousand rubles. |
5,59 |
20,62 |
6,73 |
|
Costs per 1 ha: MDS, thousand rubles. |
12,7 |
||
|
labor, man-days |
|||
|
mineral fertilizers, c.d.v. |
|||
|
Profit from 1 ha, rub. |
2,89 |
7,93 |
3,63 |
As unknowns we will take the area under crops by type:
X 1 - grain crops
X 2 - sugar beets
X 3 - sunflower
To build an economic and mathematical model of the problem, it is necessary to take into account all the conditions. IN in this case, according to these conditions, five restrictions can be drawn up:
- the sum of the area sown with agricultural crops should not exceed the area available on the farm (3200 hectares). The coefficients for the unknowns in this limitation characterize the consumption of arable land per 1 hectare of each crop. In this case, the technical and economic coefficients for the unknowns will be equal to one. The total area of the arable land is recorded on the right side.
1) X1+X2+X3<=3200
- the sum of the areas sown with industrial crops should not exceed the area that can be allocated for this purpose (3200 * 0.25 = 800 hectares). The coefficients for the unknowns in this limitation characterize the consumption of arable land allocated for sowing industrial crops per 1 hectare of each industrial agricultural crop. In this case, the technical and economic coefficients for the unknowns X2 and X3 will be equal to one, and for non-technical agricultural crops (X3) - zero. On the right side is written the maximum area of arable land that can be allocated for planting industrial crops.
2) X2+X3<=800
- the third and fourth restrictions ensure that the use of labor resources and mineral fertilizers does not exceed their availability on the farm. In other words, the sum of the products of resource consumption rates per 1 hectare on the area sown with the corresponding agricultural crops should not exceed the volume of resources available in agriculture. enterprise. The coefficients for the unknowns in these constraints will be the rates of resource consumption (in the third constraint - labor resources, in the fourth - mineral fertilizers) per 1 hectare of crop area. In this case, the technical and economic coefficients are taken from Table 1. The availability of these resources on the farm is recorded on the right side.
3) 1.5X1+4.5X2+1.5X3<=7000
4) 2Х1+15Х2+2.3Х3<=15000
- the fifth constraint guarantees the production of the planned volume of grain. The coefficients for the variables are the grain yield per 1 hectare of agricultural crop area. crops When X1 is unknown, this is the grain yield (Table 1). For variables X2 and X3, this coefficient is zero. On the right side is the grain production plan.
5) 26Х1>=65000
As a result, a system of five linear inequalities with three unknowns is obtained. It is required to find such non-negative values of these unknowns X1>=0; X2>=0; X3>=0, which would satisfy this system of inequalities and ensure maximum profit from the crop production industry as a whole:
Z max = 2.89Х1+7.93Х2+3.53Х3
The coefficients for the unknowns in the objective function are the profit received from 1 hectare of area under crops. These coefficients are calculated based on the data in Table 1.
Because the this task solved using MS Excel , then it is advisable to prepare all the input information for constructing an economic and mathematical model using this table processor(Figure 1). This facilitates not only the calculation of technical and economic coefficients and other data, but also makes it possible in the future automatic update information in the economic and mathematical model.
Picture 1
All developed information is summarized into a detailed economic and mathematical model and entered into the MS worksheet Excel. (Fig. 2.)
Figure 2
It is recommended to enter data into the model in the form of links to cells with relevant information in calculation worksheets or worksheets with initial information. Figure 3 shows how in a cell F9 information is provided on the rate of fertilizer consumption per 1 hectare of sunflower sowing.
Figure 3
To columns A («№»), IN("Restrictions"), WITH(“Units”) andH(“Constraint type”), the corresponding data is entered directly into the model (Fig. 1). They are not used in calculations and serve for informational purposes and to facilitate understanding of the contents of the model. To column I(“Scope of restrictions”), links are entered to cells containing information corresponding to the column name (the values of the right-hand sides of the inequalities constructed earlier).
For the desired values of the variables X1, X2, X3 we left empty cells - accordingly D5, E 5, F 5. Initially empty cells program MS Excel perceives as cells whose value is zero. Column G, called by us " Sum of products", is intended to determine the sum of products of the values of the unknown unknowns (cells D5, E 5, F 5) and technical and economic coefficients according to the corresponding restrictions (lines 6-10) and objective function(line 11). Thus, in the column G defined:
- - amount of resources used (cell G6– total area of arable land; G7– arable land that can be used for planting industrial crops; G8– labor resources; G9– mineral fertilizers);
- - amount of grain produced (cell G10);
- - profit amount (cell G11).
Figure 2 shows how in a cell G11 the recording of the sum of the products of the values of variables is implemented (areas sown with agricultural crops - cells D5, E 5, F 5) for the corresponding profits from 1 hectare of their crops (cells D11, E 11, F 11)using the MS function Excel « SUMPRODUCT" Since when writing this formula, absolute addressing to cells from D5 beforeF 5,this formula can be copied to other cells fromG 6 before G10.
Thus, a reference plan was constructed (Fig. 2) and the first feasible solution was obtained. Values of the unknowns X1, X2, X3 are equal to zero (cells D5, E 5, F 5 -empty cells), column cells G The “sum of products” across all constraints (lines 6-10) and the target line (line 11) also have zero values.
The economic interpretation of the first basic plan is as follows: the farm has resources, all technical and economic coefficients have been calculated, but the production process has not yet begun; resources were not used, and, accordingly, there was no profit.
To optimize the existing plan, we will use the tool Finding a solution, which is in the menu Service. If there is no such command in the menu Service, required at point Superstructure check the box Finding a solution. After this, this procedure will become available in the menu Service.
After selecting this command, a dialog box will appear (Fig. 4).
Figure 4
Since we chose profit maximization as an optimization criterion, in the field Set target cell Enter a link to the cell containing the profit calculation formula. In our case this is the cell $G$11. To maximize the value of the final cell by changing the values of the influencing cells (the influencing cells, in this case these are the changing cells, are the cells that are designed to store the values of the unknown unknowns), set the switch to the position maximum value;
In field Changing cells enter references to the cells to change, separating them with commas; or, if the cells are adjacent, indicating the first and last cell, separating them with a colon ( $ D$5:$F$5).
In field Restrictions enter all restrictions imposed on the search for a solution. Let's consider adding a constraint using the example of adding the first constraint on the total area of arable land.
In chapter Restrictions dialog box Finding a solution click the button Add. The following dialog box will appear (Fig. 5)
Figure 5
In field Cell reference Enter the address of the cell whose value is being constrained. In our case, this is the cell $ G$6, where is the formula for calculating the arable land used in the current plan.
Select from drop down list conditional operator <= , which should be located between the link and the constraint.
In field Limitation Enter a link to the cell that contains the value of the availability of arable land on the farm, or a link to this value. In our case, this is the cell $ I $6
As a result, the dialog box will take the following form (Fig. 6).
Figure 6
To accept the restriction and begin entering a new one, click the button Add. Other restrictions are introduced similarly. To return to the dialog box Finding a solution, press the button OK.
After following the above instructions, the dialog boxFinding a solutionwill have the following form (Fig. 7).
Figure 7
To change or remove restrictions in the list Restrictions dialog box Finding a solution specify the restriction you want to change or remove. Select a team Change and make changes or click the button Delete.
Checkbox Linear model in the dialog box Options Finding a solution(Fig. 8) allows you to set any number of restrictions. Checkbox Non-negative values will allow us to comply with the condition of non-negativity of variables (when solving our problem, this is mandatory). You can leave the remaining parameters unchanged, or set the parameters you need, using the help if necessary.
Figure 8
To start the solution task, click the button Execute and do one of the following:
- to restore original data, select option Restore original values.
Figure 9
To stop searching for a solution, press the key ESC.
Sheet Microsoft Excel will be recalculated taking into account the found values of the influencing cells. As a result of solving and saving the search results on the sheet, the model will take the following form (Table 10).
Figure 10
In cells D5-F5 the values of the required unknowns are obtained (the crop area is equal to: grain - 2500 ha, sugar beet - 661 ha, sunflower - 39 ha), in cells G6-G9 the volumes of resources used were determined (total area of arable land - 3200 hectares; area of arable land that can be used for sowing industrial crops - 700 hectares; labor - 6781.9 man-days; mineral fertilizers - 15000 c.d.v.), in cell G10 the amount of grain produced was established (65,000 centners). With all these values, the profit reaches 12603.5 thousand rubles. (cell G11).
If the search did not find a solution that satisfies the specified conditions, in the dialog box Solution search results a corresponding message will appear (Fig. 11).
Figure 11
One of the most common reasons for the impossibility of finding an optimal solution is the situation when, as a result of solving a problem, it turns out that there are restrictions that are not met. Having saved the found solution on the sheet, you need to compare the obtained values of the “Sum of Products” and “Volume of Constraints” columns line by line and check whether the relationship between them satisfies the constraint in the “Type of Constraints” column. Having thus found unfulfilled restrictions, it is necessary to find and eliminate the reasons that make it impossible to comply with this specific condition (this may be, for example, too large or, conversely, very small planned volumes of restrictions, etc.).
If there are a lot of restrictions in the model, then visually it is quite difficult to compare and check each line for accuracy. To make it easier, it is recommended to add another “Validation” column to the model, where using MS functions Excel « IF" And " ROUND» you can organize an automatic check (Fig. 12).
Figure 12
Target: learn to solve problems linear programming in Excel using the Solution Search add-in.
Brief theoretical information
Optimization problems are widely used in various areas of practical activity: in organizing the operation of transport systems, in the management of industrial enterprises, in drawing up projects of complex systems. Many common classes of system analysis problems, in particular, problems of optimal planning, distribution of various resources, inventory management, scheduling, and interindustry balance, fit within the framework of linear programming models.
Statement of the linear programming problem (LPP).
There are many variables X= (x 1, x 2,..., x n). The objective function depends linearly on the controlled parameters:
There are constraints that are linear shapes
Where 
(2)
It is required to determine the maximum (minimum) of a linear function
provided that the point (x 1, x 2,..., x n) belongs to some set D, which is determined by a system of linear inequalities
(4)
Any set of values (x 1 *, x 2 *,..., x n *) that satisfies the system of inequalities (4) of the linear programming problem is a valid solution to this problem. If the inequality holds
c 1 x 1 o + c 2 x 2 o +..+ c n x n o ≥ c 1 x 1 + c 2 x 2 +..+ c n x n
for the entire set of values x 1, x 2,..., x n, then the value x 1 o .. x n o is the optimal solution to the linear programming problem.
An example of constructing a mathematical model and solving a ZLP.
Task. It is necessary to determine in what quantity it is necessary to produce products of four types A, B, C and D, the production of which requires three types of resources: labor, raw materials and finance. The amount of each type of resource required to produce a unit of product of a given type is called the consumption rate. Consumption rates, as well as the profit received from the sale of a unit of each type of product, are shown in table 1. The availability of available resources is also shown there.
Table 1.
|
Resource |
A |
B |
C |
D |
sign |
Availability |
|
labor |
||||||
Let's create a mathematical model, for which we introduce the following notation:
x i - quantity of products of the i-th type, i = 1,2,3,4
b j – amount of available resource of the jth type, j = 1,2,3
a ji – consumption rate of the j-th resource for the production of i-th products
c i – profit from the sale of a unit of product of the i-th type.
As can be seen from Table 1, for a unit of output A 6 units of raw materials are required, which means to produce all products A 6 required x 1 units of raw materials, where x 1- quantity of products produced A. Taking into account that for other types of products the dependencies are similar, the limitation on raw materials will look like:
6x 1+ 5x 2+ 4x 3+ 3x 4≤ 110
In this constraint, the left side is equal to the amount of the required resource, and the right side shows the amount of the available resource.
Similarly, you can create restrictions for other types of resources and write a dependency for the objective function. Then the mathematical model of the problem will look like:
x 1+ x 2+ x 3+ x 4≤ 16
6x 1+ 5x 2+ 4x 3+ 3x 4≤ 110
4x 1+ 6x 2+ 10x 3+ 13x 4≤ 100
x i≥ 0, i=1,2,3,4
1. To enter the conditions of the problem, create a form in Excel (Fig. 1). Cells B3:E3 will display the calculated values x i .
Fig.1. Form for entering problem conditions
2. Let's enter the coefficients of the objective function and constraints into the form. Let us introduce dependencies from the mathematical model. The entered data is shown in Fig. 2.
Fig.2. Task input data
Cell F6 contains the formula of the objective function, and F9-F11 contains the left parts of the constraints from the mathematical model. In Fig. Figure 3 shows the formula presentation mode. You can switch to this mode using the following sequence of actions: press the button Microsoft Office, click Excel Options open the tab Additionally and check the box Show formulas, not their values.
Fig.3. Formula presentation mode.
3. Download the add-on search for a solution Data│Analysis│Finding a solution.
4. In the field Set target cell Let's enter a link to the target cell by placing the cursor in the field and left-clicking on cell F6.
5. Select the search direction by checking the box equal to maximum value.
6. Place the cursor in the field Changing cells and use the mouse to enter the names of the cells B3:E3 to be changed. In these cells, as a result of searching for a solution, the solution will be displayed - the values of the variables x i., at which the objective function has a maximum value under given restrictions.
7. Let us introduce restrictions on the required variables: x i ≥ 0 (default lower bound is 0, output quantity cannot be negative). We will also introduce restrictions on resources 
(more resources cannot be used than their reserves). Let's click on the button Add, in the window that appears Adding a constraint in the left field using the mouse, enter a link to cell B3, select the sign from the drop-down list ≥,
in the right field, click on cell B4 (Fig. 4). Let us introduce the remaining restrictions in the same way.
Fig.4. Window for adding restrictions.
Figure 5 shows the completed Search for a Solution window.
Fig.5 Filled window Search for a solution
8. Next, click on the button Execute. The Solution Search Results dialog box appears (Fig. 6). The solution has been found. All restrictions and optimality conditions are met. We save the found solution. In this window you can also get three types of reports: on results, stability and limits, reports are generated in new worksheets.
Fig.6. Solution search results window
The results of the optimal solution to the problem are shown in the table (Fig. 7).
Fig.7. Optimal Solution Results
Thus, the optimal solution was obtained (10;0;6;0), i.e. It is advisable to produce 10 units of product A and 6 units of product C. The maximum profit is 1320 monetary units, while all labor and financial resources are used, 84 units of raw materials, 26 units of raw materials remain in stock.
Laboratory work assignments.
Create a mathematical model and solve the resulting linear programming problem in Excel using the Solution Search add-in.
To transport goods, machines of types A and B are used. The carrying capacity of both types of machines is the same and equal to h t. In one trip, machine A consumes a 11 kg lubricants and a 12 l of fuel, car B - a 21 kg lubricants and a 22 l fuel. The base has d 1 kg lubricants and d 2 l fuel. The profit from transporting one car A is from 1 rub., cars B - from 2 rub. It is necessary to transport Ht of cargo (the initial data is given in the table below).
How many vehicles of both types must be used in order to maximize income from cargo transportation?
|
Option No. |
||||||||||
Instructions for performing laboratory work.
- Study theoretical material.
- Run the given example.
- Select your option based on the last digit.
- Create a mathematical model of the problem.
- Find the optimal solution using Solution Finder.
- Draw conclusions based on the solutions obtained, generate reports on the solution results, stability and limits.
- Create a lab report.
- Title page.
- Verbal statement of the problem.
- Mathematical formulation of the problem.
- Filled window Search for a solution
- Results of the search for a solution (table).
- Conclusions on the solutions obtained.
List of sources
- Gelman V.Ya. Solving mathematical problems using Excel: Workshop. – St. Petersburg: Peter, 2003
- Kuritsky B.Ya. Search for optimal solutions using Excel. – St. Petersburg: BHV-St. Petersburg, 1997
- Pazyuk K.T. Mathematical methods and models in economics. – Khabarovsk: KhSTU Publishing House, 2002
- John Walkenbach. MS OfficeExcel 2007 - User's Bible, Publisher: Williams, 2008
To solve linear programming problems simplex method in the MS Excel environment, cells are filled with source data in number mode and mathematical model formulas.
MS Excel allows you to obtain an optimal solution without limiting the dimension of the system of inequalities of the objective function.
Let’s solve the problem of manufactured products using the simplex method using the “Solution Search” add-in in MS Excel.
1. Fill out the Excel table in numbers mode (Fig. 1)
2. Fill out the Excel table in formula mode (Fig. 2)
Fig.1 Table in number mode
Fig.1 Table in formula mode
Here: B9:C9 – result (optimal number of products of each type);
В6:С6 – coefficients of the objective function;
B10 – value of the objective function;
В3:С5 – limitation coefficients;
D12:D14 – right side of restrictions;
B12:B14 – calculated (actual) values of the left side of the restrictions.
Let's solve the problem using the Data/Solution Search command. The Search for Solution dialog box appears on the screen.
In the Set target function field, a link to the active cell will be shown, i.e. on B10. Moreover, this link is absolute. In the Equal section, set the switch to Maximum (minimum) value depending on the target function. Restrictions are set using the Add button, which opens the Add Restriction input dialog box.
In the Cell Link: input field, indicate the address of the cell containing the formula on the left side of the constraint. Then the sign of the ratio is selected from the list. The Constraint field specifies the address of the cell containing the right side of the constraint. Click on the Add button and repeat until the next constraint. After entering all restrictions, click OK.
Since all variables carry non-negativity conditions, their positivity is set through the Parameters button in the Search for a Solution dialog box. After clicking on it, the Solution Search Options window appears on the screen.
Check the Make unconstrained variables non-negative checkbox and select Solution method Search for solutions to linear problems using the simplex method. Click on the Find Solution button.
Excel will present a Solution Search Results window with a message that a solution has been found, or that it cannot find a suitable solution.
If the calculation was successful, Excel will present the following summary window. You can keep them or discard them. In addition, you can get one of three types of reports (Results , Sustainability , Limits) that allow us to better understand the results obtained, including assessing their reliability.
After the solution is found, the optimal number of products of each type will appear in cells B9:C9.
When saving the report, select – Report on results (Fig. 3).
The report shows that resource 1 is not fully used by 150 kg, while resources 2 and 3 are fully used.
As a result, an optimal plan was obtained in which products of type 1 must be produced in the amount of 58 pieces, and products of type 2 in the amount of 42 pieces. At the same time, the profit from their sale is maximum and amounts to 4,660 thousand rubles.
Fig.3 Results report
1. Passenger and fast trains consisting of reserved seat, compartment and soft carriages depart daily from the formation station. The number of seats in a reserved seat car is 54, in a compartment car – 36, in a soft car – 18. The table shows the composition of each type of train and the number of cars of various types available in the fleet. Determine the number of fast and passenger trains that need to be formed daily so that the number of passengers transported is maximum.
Solution transport tasks
Transport problems are the tasks of determining the optimal plan for transporting cargo from given points of departure to given points of consumption.
| b 1 | b 2 | … | b k | … | b g | |
| a 1 | }
The last notes
|
