Let’s carry out stability analysis in Excel on the example of the spinning mill problem.
Example 2. A spinning mill for the production of four types of yarn uses three types of raw materials – pure wool, nylon, acrylic. Table 1 shows the consumption rates of raw materials, its total amount that can be used by the factory during the year; loading of equipment in the production of a ton of yarn and profit from the sale of a ton of yarn of each type. The annual resource of the equipment is 140 thousand machine hours.
It is required to draw up an annual plan for the production of yarn in order to maximize the total profit.
Table 1. Initial data
|Type of raw material||Consumption rates of raw materials per 1 ton of yarn||Quantity of raw materials (t.)|
|View 1||View 2||View 3||View 4|
|Wool Nylon Acrylic||0.5 0.1 0.4||0.2 0.6 0.2||0.3 0.4 0.3||0.2 0.5 0.3|
|Loading of equipment in thousand cars.h||0.06||0.04||0.03||0.09|
|Profit from the sale of 1 ton of yarn (in $)|
Denote: – the volume of production of yarn of the i-th type in tons.
On fig. 14 shows the completed form for entering the condition of the problem in Excel.
The dialog box “Search for a solution” for the problem under consideration with the entered data is shown in fig. fifteen.
|resources||odds||left side||sign||right part|
Rice. 14- Form for entering the condition of the problem in Excel
After clicking the “Run” button, the “Results of Finding a Solution” dialog box is displayed. To receive stability reports, you must select the type of report (all types can be set): “Results”, “Stability”, “Limits” and click the “OK” button (Fig. 16).
Rice. 15. Dialog box “Search for a solution”
Rice. 16. Dialog box “Results of finding a solution”
The results of solving the problem are displayed in the form for entering the conditions of the problem: =235.29; =0; =0; =1352.9; ZFz=18823529.41 (Fig. 17), reports on results, stability and limits are displayed on separate sheets in the current Excel workbook.
|resources||odds||left side||sign||right part|
Rice. 17. The result of solving the problem
Results report . On fig. 18 is a report on the results for the task of example 1.
The results report consists of three parts and contains information about the target function; about the values of variables obtained as a result of solving the problem; about restrictions.
The results report contains: an expression for calculating the value of the objective function, as well as the name of the digital filter, the initial value of the objective function (before solving the problem) and the value of the objective function for the optimal solution. Similar information is provided for all variables of the task: a cell for storing the value of the variable, the designation of the variable, the initial value and the optimal value.
|Microsoft Excel 11.0 Results Report|
|Target Cell (Maximum)|
|$F$12||Acrylic left side||500.00||$F$12<=$H$12||related|
|$F$11||Kapron left side||700.00||$F$11<=$H$11||associated|
|$F$10||Wool left side||388.24||$F$10<=$H$10||not connected.||211.8|
|$F$13||Equipment resources left side||135.88||$F$13<=$H$13||not connected.||4.12|
|$B$3||x1 value||235.29||$B$3>=0||not connected.||235.3|
|$E$3||x4 value||1352.94||$E$3>=0||not connected.|
Rice. 18- Results report
The following information is given for resources: the formula corresponding to the left side of the constraint; constraint name; the value (value) of the resource used for the optimal solution of the problem; formula specifying the constraint; constraint status and difference. If the resource is fully used (that is, the resource is scarce), then in the “Status” (“Status”) column, the corresponding restriction is indicated as “bound”; if the resource is not fully used (that is, the resource is not scarce), this column indicates “not connected”. The “Difference” column shows the difference between the value of the used resource and the initially specified value of the resource. Similar information is provided for the variables of the problem: optimal value, status (bound if the optimal value of the variable is not zero; otherwise unbound), the difference between the optimal value of the variable and the boundary condition specified for it.
In the spinning mill problem, the optimal solution obtained means the production of the first and fourth types of yarn (basic variables: =235.29; u003d 1352.9), it is not profitable to produce yarn of the second and third types ( =0; =0). With such a release plan, the resources (stocks) of acrylic and nylon will be fully used, and the stocks of wool and the resource of equipment are excessive.
The report on the results provides information for the analysis of a possible change in the stocks of non-deficient resources while maintaining the obtained optimal value of the CF. If a resource is subject to a constraint of type ≤, then the “Difference” column gives the amount of the resource that is not used in the implementation of the optimal solution. For example, 388.24 tons of wool are used. 211.76 tons of the total wool reserves remain unused, by this amount it is possible to reduce the “wool” resource without changing the optimal solution. Similarly, you can reduce the resources of the equipment by 4.12 thousand hours and this will not affect the optimal solution.
If a restriction of type ≥ is imposed on the resource, then in the column “Difference” the amount of the resource by which the minimum required norm was exceeded is given. If the resource is increased by this value, the optimal solution of the problem will not change.
Sustainability Report. On fig. 19 shows the stability report for the problem of example 1, which consists of two parts: information on variables and information on constraints.
|Microsoft Excel 11.00 Sustainability Report|
|Res.||Normir.||Target||Let it be mine||Let it be mine|
|Res.||Shadow||Restriction||Let it be mine||Let it be mine|
Rice. 19- Sustainability report
The levelized cost shows how much the value of the CF will change if a unit of this product is forced to be included in the optimal solution. For example, in the sustainability report for this problem, the levelized cost for the second yarn is: -1352.94. This means that if we include 1 ton of yarn of the second type in the release plan, then the new release plan will bring a profit of $1352.94 less than the previous optimal plan. The levelized cost for underlying variables is always zero.
Limit values of increment of target coefficients. For each variable, the given coefficients of the digital filter are indicated, the permissible increase and decrease in the coefficients at which the optimal solution of the problem is preserved. For example, the allowable increase in the price of yarn of the first kind is $2875 per ton, and the allowable decrease is $8600. This means that if the price per ton of yarn of the first type increases by no more than $2875, for example, it becomes equal to $13875, then the optimal solution will remain, only the value of the CF at the optimal point will change.
When going beyond the limits of price changes indicated in the sustainability report, the optimal solution may change both in terms of the range of products produced and in terms of output (without changing the range).
The rest of the Sustainability Report provides information related to limitations. The column “Resulting value” shows the amount of resources used.
Resource increment limits. The columns “Permissible reduction” and “Permissible increase” show how much it is possible to reduce (eliminate surplus) or increase (increase the minimum required requirement) the resource, while maintaining the basis of the optimal solution (change the volume of output without changing the range). Let’s consider the analysis of scarce resources, since the analysis of non- scarce resources was given in the description of the report on the results. In the problem under consideration, such limitations are the scarce resources “acrylic” and “kapron”. For example, if acrylic resources decrease by no more than 80 tons or increase by no more than 33.33 tons, the basis of the problem will not change (it will still be optimal to produce yarns of the first and fourth types, although the output volumes will change).
Shadow price (the value of an additional unit of the i-th resource). The shadow price shows how much the value of the digital filter will increase if an additional unit of the i-th resource is allocated. Obviously, the shadow price is not zero only for scarce resources. For example, if acrylic stocks increase by 1 ton, profit will increase by $25294.12, if nylon stocks increase by 1 ton, then profit will be $8823.53 more than the original one. Therefore, first of all, it is beneficial for the factory to increase stocks of acrylic.
In terms of the duality theory, the shadow price corresponds to the value of the dual valuation of the corresponding resource, and the normalized cost corresponds to the value of the additional dual valuation, which is equal to the difference between the left and right parts in the constraints of the dual problem.
Limit report . For the problem under consideration, the report on the limits is shown in Fig. . 20.
|Microsoft Excel 11.0 Limit Report|
Rice. 20. Limit report
The report on limits shows in what range the values of variables can change, without changing the basis (nomenclature of output). For example, if 235 tons of yarn of the first type will be produced, then in the optimal solution, non-zero variables will correspond to the output volumes of the first and fourth types of yarn. In case of production of more than 235.29 tons of yarn of the first type, the product range will change. The report on limits also provides information on the value of the CF at the lower and upper limit values of the task variables.
1. Setting up MS Excel 4
2. Preparation of a sheet with initial data. 5
How to fill out the sheet. 6
3. Setting the data for the “Search for a solution” package. 6
4. Obtaining the results of the decision. eight
5. Types of reports: 9
6. Solving ILP problems in Excel .. 10
7. An example of solving a transport problem. eleven
8 Investigation of the stability of the solution of the LP problem.. 12
Analysis of decrease or increase in resources: 13
Stability Analysis in Excel 14