Conclusion when solving problems in excel. Solving a transport problem using the solution search tool

Usage Microsoft Excel to solve problems linear programming .

In Excel 2007, to enable the analysis package, you need to click go to block Excel Options by pressing the button on the left top corner, and then the button Excel Options"at the bottom of the window:

Next, in the list that opens, you need to select Add-ons, then place the cursor on the item Finding a solution, press the button Go and in the next window enable the analysis package.

In order to solve the LP problem in table processor Microsoft Excel, you need to do the following:

1. Enter the problem condition:

a)create a screen form for entering task conditions :

· variables,

· objective function(CF),

· restrictions,

· boundary conditions;

b) enter the initial data into the screen form :

· TF coefficients,

· coefficients for variables in restrictions,

· right-hand sides of restrictions;

c) enter dependencies from the mathematical model into the screen form :

formula for calculating the CF,

· formulas for calculating the values of the left sides of restrictions;

d) set TF (in the window "Finding a solution"):

target cell

· direction of CF optimization;

e) introduce restrictions and boundary conditions (in the window "Finding a solution"):

· cells with variable values,

· boundary conditions for permissible values of variables,

· ratios between the right and left sides of the constraints.

2. Solve the problem:

a) set parameters for solving the problem (in the window "Finding a solution");

b) run a problem to solve (in the window "Finding a solution") ;

c) select solution output format (in the window "Solution Search Results").

Let us consider in detail the use of MS Excel using the example of solving the following problem.

Task.

The "GRM pic" factory produces two types of breakfast cereals - "Crunchy" and "Chewy". The ingredients used to make both products are essentially the same and are generally not in short supply. The main limitation imposed on the volume of output is the availability of working hours in each of the three workshops of the factory.

Production Manager Joy Deason needs to develop a monthly production plan. The table below shows the total working time and the number of man-hours required to produce 1 ton of product.

*Shop*	*Required working time fund* *person-h/t*		*General working time fund* *person-hour per month*
*Shop*	*"Crunchy"*	*"Chewy"*	*General working time fund* *person-hour per month*
A. Production	10	4	1000
B. Adding seasonings	3	2	360
C. Packaging	2	5	600

The income from the production of 1 ton of "Crunchy" is 150 pounds. Art., and from the production of "Chewy" - 75 f., art. On currently there are no restrictions on possible sales volumes. It is possible to sell all produced products.

Required:

a) Formulate a linear programming model that maximizes the total monthly income of the factory.

b) Solve it using MS Excel.

The formal formulation of this problem has the form:

(1)
Entering initial data
Creating a screen form and entering initial data

Screen form for the solution in MS Excel is presented in Figure 1.

Picture 1.

In the screen form in Figure 1, each variable and each coefficient of the problem is assigned a specific cell on Excel sheet. The cell name consists of a letter denoting a column and a number denoting a row, at the intersection of which is the object of the LP problem. So, for example, the variables of task 1 correspond to the cells B4 (), C4(), the CF coefficients correspond to the cells B6 (150), C6(75), the right-hand sides of the restrictions correspond to the cellsD18 (1000), D19 (360), D20 (600), etc.
Entering dependencies from a formal problem statement into a screen form

To enter dependencies that define the expression for the target function and restrictions, use the MS Excel function SUMPRODUCT, which calculates the sum of pairwise products of two or more arrays.

One of the most simple ways defining functions in MS Excel is to use the mode "Inserting Functions" , which can be called from the menu "Insert" or when pressing a button "

Figure 2

So, for example, the expression for the objective function from Problem 1 is defined as follows:

· cursor in field D6;

· by pressing a button "

· in the window "Function" select function SUMPRODUCT(Fig. 3) ;

Figure 3

in the window that appears "SUMPRODUCT" to line "Array 1" enter expression B$4: C$4 , and to the line "Array 2"- expression B6: C6 (Fig. 4);

Figure 4

The left-hand sides of the constraints of problem (1) are sum of products each of the cells allocated for values problem variables (B3, C3 ), to the corresponding cell reserved for coefficients specific restriction (B13, C13 - 1st limitation ; B14, C14- 2nd limitation and B15, C15- 3rd limitation). Formulas corresponding to the left sides of the restrictions are presented in Table 1.

Table 1.
Formulas describing the limitations of the model (1)

Left side of the constraint	FormulaExcel
	=SUMPRODUCT(B4: C4; B13: C13))
	=SUMPRODUCT(B4: C4; B14: C14))
	=SUMPRODUCT(B4: C4; B15: C15)

DF task

Further actions are performed in the window "Finding a solution", which is called from the menu "Service"(Fig.5):

· place the cursor in the field "Set target cell";

· enter the address of the target cell $ D$6 or make one click of the left mouse button on the target cell in the on-screen form ¾ this will be equivalent to entering the address from the keyboard;

· enter the direction of CF optimization by clicking once with the left mouse button on the selector button "maximum value".

Figure 5
Entering Constraints and Boundary Conditions
Setting Variable Cells

Out the window "Finding a solution" in field "Changing Cells" enter addresses $ B$4:$С$4. The required addresses can be entered in the field "Changing Cells" and automatically by selecting the corresponding variable cells with the mouse directly in the screen form.
Setting boundary conditions for acceptable variable values

In our case, only the boundary condition of non-negativity is imposed on the values of the variables, that is, their lower limit must be equal to zero (see Fig. 1).

· Click the button "Add", after which a window will appear "Adding a constraint"(Fig. 6).

· In field "Cell reference" enter variable cell addresses $ B$4:$С$4. This can be done either from the keyboard or by selecting all variable cells directly in the screen form with the mouse.

· In the sign field, open the list of suggested signs and select .

· In field "Limitation" enter 0.

Fig.6 - Adding a condition for non-negativity of problem variables (1)
Specifying Restriction Signs , , =

· Click the button "Add" in the window "Adding a constraint".

· In field "Cell reference" enter the cell address of the left side of a particular constraint, for example $ B$18 . This can be done either from the keyboard or by selecting the desired cell directly in the screen form with the mouse.

· In accordance with the conditions of task (1), select the required sign in the sign field, for example, .

· In field "Limitation" enter the cell address of the right side of the constraint in question, for example $ D$18 .

· Enter restrictions in the same way: $ B$19<=$ D$19 , $ B$20<=$ D$20 .

· Confirm the entry of all the above conditions by pressing the button OK.

Window "Finding a solution" after entering all the necessary data, task (1) is shown in Fig. 5.

If, when entering a task condition, it becomes necessary to change or delete the entered restrictions or boundary conditions, this can be done by clicking the buttons "Change" or "Delete"(see Fig. 5) .
The solution of the problem
Setting parameters for solving a problem

The task is started to be solved in the window "Finding a solution." But first, to set specific parameters for solving optimization problems of a certain class, you need to press the button "Options" and fill in some fields of the window "Solution Search Options"(Fig. 7).

Rice. 7 - Solution search parameters suitable for most LP problems

Parameter "Maximum time" serves to assign time (in seconds) allocated to solve a problem. You can enter a time in this field that does not exceed 32,767 seconds (more than 9 hours).

Parameter "Limit number iterations" serves to control the time required to solve a problem by limiting the number of intermediate calculations. In the field you can enter the number of iterations not exceeding 32,767.

Parameter "Relative error" serves to specify the accuracy with which the cell’s compliance with the target value or its approximation to the specified boundaries is determined. The field must contain a number from 0 to 1. Than less the number of decimal places in the entered number, the below accuracy. High accuracy will increase the time it takes for the optimization process to converge.

Parameter "Tolerance" serves to set the tolerance for deviation from the optimal solution in integer problems. When specifying a larger tolerance, the search for a solution ends faster.

Parameter "Convergence" applies only when solving nonlinear problems. Check the box "Linear model" provides acceleration of the search for a solution to a linear problem through the use of the simplex method.

Confirm the settings by pressing the button " OK" .
Starting a problem to solve

The solution task is launched from the window "Finding a solution" by pressing a button "Run".

After starting to solve the LP problem, a window appears on the screen "Solution Search Results" with a message about the successful solution of the problem presented in Fig. 8.

Rice. 8 -. Message about the successful solution of the task

The appearance of a different message does not indicate the nature of the optimal solution to the problem, but rather that errors were made when entering the conditions of the problem in Excel. errors, preventing Excel from finding the optimal solution that actually exists.

If, when filling out the fields of the window "Finding a solution" errors were made that did not allow Excel to apply the simplex method to solve the problem or complete its solution, then after launching the solution task, a corresponding message will be displayed on the screen indicating the reason why the solution was not found. Sometimes the parameter value is too small "Relative error" does not allow us to find the optimal solution. To correct this situation, increase the error bit by bit, for example from 0.000001 to 0.00001, etc.

In the window "Solution Search Results" The names of three types of reports are presented: "Results", "Sustainability", "Limits". They are necessary when analyzing the resulting solution for sensitivity. To receive the answer (values of variables, digital functions and left parts of restrictions) directly on the screen, simply press the button " OK". After this, the optimal solution to the problem appears on the screen (Fig. 9).

Fig.9 - Screen form of the problem (1) after obtaining the solution

Introduction

4.1. Initial data

4.2. Formulas for calculations

4.3. Filling out the Find Solution dialog box

4.4. Solution results

Conclusion

References

Introduction

linear programming excel optimization problem

The solution to a wide range of problems in the electric power industry and other sectors of the national economy is based on the optimization of a complex set of dependencies described mathematically using a certain “objective function” (TF). Similar functions can be written to determine the cost of fuel for power plants, the loss of electricity during its transport from the power plant to consumers, and many other problematic tasks. In such cases, it is necessary to find the CF under certain restrictions imposed on its variables. If the CF linearly depends on the variables included in its composition and all restrictions form a linear system of equations and inequalities, then such a particular form optimization problem called “linear programming problems.”

The topic of the course work is “Solving linear programming problems in MS Excel”, using the example of a “transport problem” taken from the field of general energy, to gain practical skills in using Microsoft Excel spreadsheets and solving optimization problems of linear programming.

1. Initial data for solving the problem

Initial data includes - a layout diagram of coal basins (CB) and electric power stations (PP), indicating transport connections between them, tables containing information on the annual productivity and specific price of CB fuel, installed capacity, number of hours of use of installed capacity and specific consumption fuel on the ES, distances between UB and ES and the unit cost of transporting fuel along the UB-ES routes.

Fig.1. Initial data

2. Brief information about spreadsheets MS Excel

Rice. 2. Application window view

Spreadsheet processes are software packages designed to create spreadsheets and manipulate their data. The use of spreadsheets simplifies working with data and allows you to automate calculations without the use of special programming. The most widespread use is in economic and accounting calculations. MS Excel provides the user with the opportunity to:

.Use complex formulas containing built-in functions.

2.Organize connections between cells and tables, while changing data in the source tables automatically changes the results in the resulting tables.

.Create pivot tables.

.Apply sorting and filtering of data to tables.

.Perform data consolidation (combining data from several tables into one).

.Use scripts - named arrays of source data, from which the final total values are formed in the same table.

.Perform automated search for errors in formulas.

.Protect data.

.Use data structuring (hide and show parts of tables).

.Apply autocomplete.

.Use macros.

.Build diagrams.

.Use autocorrect and spell check.

.Use styles, templates, auto-formatting.

.Exchange data with other applications.

Key Concepts:

.Workbook - basic documents, stored in a file.

2.Sheet (volume: 256 columns, 65536 rows).

.A cell is the smallest structural unit of data placement.

.Cell address - determines the position of the cell in the table.

.A formula is a mathematical notation of calculations.

.Link - record the cell address as part of a formula.

.A function is a mathematical notation indicating the execution of certain computational operations. Consists of a name and arguments.

Data input:

The data can be of the following types -

· Numbers.

· Text.

· Functions.

· Formulas.

You can enter -

· In cells.

· To the formula bar.

If ######## appears on the screen in a cell after entering, it means the number is long and does not fit in the cell, then you need to increase the width of the cell.

Formulas- determine how the values in the cells are related to each other. Those. The data in the cell is not obtained by filling, but is automatically calculated. When you change the contents of cells referenced in a formula, the result in the calculated cell also changes. All formulas begin with =. Further may follow -

· Cell reference (for example, A6).

· Function.

· Arithmetic operator (+, -, /, *).

· Comparison operators (>,<, <=, =>, =).

You can enter formulas directly into a cell, but it is more convenient to enter using the formula bar.

Functions- These are standard formulas for performing certain tasks. Functions are used only in formulas.

Way: Insert - Functionor in the formula bar, click on = . A dialog box appears listing ten recently used functions. To expand the list, select Other functions...,another dialog box will open, where functions are grouped by type (category), a description of the purpose of the function and their parameters is given.

A complete description of working with MS Excel spreadsheets can be found in textbooks and manuals (specialized).

3. Mathematical formulation of the problem

Based on the criterion of minimum fuel costs for the ES of the specified power supply region, it is necessary to determine their optimal fuel supply from three coal basins, taking into account the limitations on the needs of the ES and the productivity of the UB.

The initial data of the problem and the variables to be determined during its solution can be presented in the form of Table 3

Data designation:

IN dec1 , IN ub2 , IN ub3 - productivity of coal basins, thousand tons;

WITH dec1 , WITH ub2 , WITH ub3 - cost of fuel in coal basins, c.u./ton;

L at - length of the railway track between UB to ES, km;

WITH at - specific cost of transporting fuel along the route from UB to ES, c.u./ton*km (C 11=C 12=C 13=C 21=C 22=C 23=C 31=C 32=C 33);

IN at - volume of fuel delivered from the UB to the power plant, thousand tons;

IN ES1 , IN ES2 , IN ES3 - annual fuel demand of the first, second, third power plants, respectively, thousand tons;

IN at - are the parameters of the target function variables to be determined in the process of solving the problem;

It is necessary to determine the optimal volume of fuel (V at ), delivered from the UB to each of the ES, at which the total fuel costs for all three ES will be minimal.

The objective function to be optimized in the process of solving the problem will be the total fuel costs for all three ES.

4. Solution of the linear programming problem

.1 Initial data

Rice. 4. Initial data

4.2 Formulas for calculations

Fig.5. Intermediate calculations

4.3 Filling out the “Search for Solution” dialog box

Rice. 6. Optimization process.

Fig.6.1. Setting restrictions (fuel must be>0).

Fig.6.2. Setting restrictions (number of imports = quantity of fuel consumed).

Fig.6.3. Setting restrictions (annual shipment, do not exceed production UB1).

Fig.6.4. Setting restrictions (annual shipment, do not exceed production UB2).

Fig.6.5. Setting restrictions (annual shipment, do not exceed production UB3).

.4 Solution results

Fig.8. Results of solving the problem

Answer: Amount of fuel (thousand tons) delivered to:

ES4 from UB1 is 118.17 tons;

ES6 from UB1 is 545.66 tons;

ES5 from UB2 is 19.66 tons;

ES6 from UB2 is 180.34 tons;

ES5 from UB3 is 277.94 tons;

ES6 from UB3 is 526.00t;

ES4 total 118.17 tons;

ES5 total 297.60 tons;

ES6 total 1252.00t;

Fuel costs amounted to (cu):

For ES4 - 496314.00.

For ES5 - 227064.75.

For ES6 - 23099064.78.

The total costs for all ES are 23822443.53 USD;

Conclusion

Brief information about MS Excel spreadsheets. Solution of a linear programming problem. Solution using Microsoft Excel tools for an economic optimization problem, using the example of " transport problem". Features of the design of a MS Word document.

IN course work shows how to create and work when designing a MS Word document, within the framework of which the solution to an economic optimization problem is considered, using the example of a “transport problem” taken from the field of general energy, Microsoft means Excel.

Let's look at linear programming in Excel using the example of a problem previously solved.

Task. Nikolai Kuznetsov runs a small mechanical plant. Next month, he plans to produce two products (A and B), for which the specific marginal profit is estimated at 2,500 and 3,500 rubles, respectively. Both products require machining, raw materials and labor costs to make. It takes 3 hours to produce each unit of product A. machining, 16 units of raw materials and 6 units of labor. The corresponding unit requirements for Product B are 10, 4, and 6. Nicholas predicts that next month he can supply 330 hours of machining, 400 units of raw materials, and 240 units of labor. The technology of the production process is such that at least 12 units of product B must be produced in each specific month. Need to determine the number of units of products A and B that Nikolay must produce in the next month to maximize contribution margin.

Download the note in format, example in format

1. Let's use the mathematical model constructed. This is the model:

Maximize: Z = 2500 * x 1 + 3500 * x 2

Provided that: 3 * x 1 + 10 * x 2 ≤ 330

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

2. Let's create a screen form and enter the initial data into it (Fig. 1).

Rice. 1. Screen form for entering data for a linear programming problem

Pay attention to the formula in cell C7. This is the objective function formula. Similarly, formulas for calculating the left side of the restrictions are entered into cells C16:C18.

3. Check if you have the “Search for a solution” add-on installed (Fig. 2), skip this point.

Rice. 2. The Search for Solution add-on is installed; Data tab, Analysis group

If you don’t find the “Search for a solution” add-in on the Excel ribbon, click the button Microsoft Office, and then Excel Options (Figure 3).

Rice. 3. Excel Options

Select the Add-ons line, and then at the very bottom of the “Manage” window Microsoft add-ons Excel" select "Go" (Fig. 4).

Rice. 4. Excel add-ins

In the “Add-Ins” window, check the “Search for a solution” checkbox and click Ok (Fig. 5). (If Solver is not listed in the Add-ons field, click Browse to find the add-in. If you receive a message that the Solver add-in is not installed on your computer, click Yes to install it.)

Rice. 5. Activation of the “Search for a solution” add-on

After loading the add-in for searching for a solution, the Search for a solution command becomes available in the Analysis group on the Data tab (Fig. 2).

4. The next step is to fill in Excel window“Finding a solution” (Fig. 6)

Rice. 6. Filling out the “Search for a solution” window

In the “Set target cell” field, select the cell with the value of the target function – $C$7. We choose whether to maximize or minimize the objective function. In the “Changing cells” field, select cells with the values of the desired variables $C$4:$D$4 (as long as they contain zeros or empty). In the “Constraints” area, using the “Add” button, we place all the restrictions of our model. Click “Run”. In the “Solution Search Result” window that appears, select all three report types (Fig. 7) and click Ok. These reports are needed to analyze the resulting solution. You can read more about the data presented in the reports.

Rice. 7. Selecting report types

The values of the maximized objective function appeared on the main sheet - 130,000 rubles. and variable parameters x 1 = 10 and x 2 = 30. Thus, to maximize marginal income, Nicholas should produce 10 units of product A and 30 units of product B next month.

If something else appears instead of the “Solution Search Result” window, Excel was unable to find a solution. Check that the “Search for a solution” window is filled out correctly. And one more little trick. Try reducing the precision of the solution search. To do this, in the “Search for a solution” window, click on Parameters (Fig. 8.) and increase the calculation error, for example, to 0.001. Sometimes, due to high accuracy, Excel does not have time to find a solution in 100 iterations. You can read more about the parameters for finding a solution.

Rice. 8. Increase in calculation error

It is necessary to determine in what quantity it is necessary to produce products of four types Prod1, Prod2, Prod3, Prod4, 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 production of this 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 Fig. 1.

Resource	Cont1	Prod2	Prod3	Prod4	Sign	Availability
Profit
Labor
Raw materials
Finance

Picture 1.

Mathematical model the task has the form:

where x j is the quantity of manufactured products of the jth type; F – goal function; the left sides of the constraint expressions indicate the values required resource, and the right sides show the quantity available resource.

Entering task conditions

To solve the problem with using Excel You should create a form to enter the initial data and enter it. The input form is shown in Fig. 2.

In cell F6, an expression for the objective function is introduced as the sum of the products of the profit values from the release of a unit of product of each type by the number of products of the corresponding type. For clarity, in Fig. Figure 3 shows the form for inputting initial data in formula output mode.

The left parts of the restrictions for resources of each type are entered into cells F8:F10.

Figure 2.

Figure 3.

Solving a linear programming problem

To solve linear programming problems in Excel, use powerful tool, called Finding a solution . Access to the Search for a solution is carried out from the menu Service , the Search for a Solution dialog box appears on the screen (Fig. 4).

Figure 4.

Entering the conditions of a problem to find its solution consists of the following steps:

1 Assign a target function by placing the cursor in the field Set target cell window Search for a solution and click in cell F6 in the input form;

2 Turn on the switch for the value of the objective function, i.e. indicate it Equal Maximum value ;

3 Enter the addresses of the variables to be changed (x j): to do this, place the cursor in the field Changing cells window Search for a solution, and then select the range of cells B3:E3 in the input form;

4 Press the button Add Solution search windows for entering constraints for a linear programming problem; a window appears on the screen Adding a constraint (Fig. 5) :

Enter boundary conditions for the variables x j (x j ³0), for this in the field Cell reference indicate cell B3 corresponding to x 1, select the desired sign (³) from the list in the field Limitation indicate the cell of the input form in which the corresponding value of the boundary condition is stored (cell B4), click the button Add ; repeat the described steps for the variables x 2, x 3 and x 4;

Enter restrictions for each type of resource in the field Cell reference window Adding a constraint indicate cell F9 of the input form, which contains the expression of the left side of the restriction imposed on labor resources in the fields Limitation indicate the £ sign and the H9 address on the right side of the restriction, press the button Add ; similarly introduce restrictions on other types of resources;

After entering the last constraint, instead of Add press OK and return to the Search for a solution window.

Figure 5.

Solving a linear programming problem begins with setting the search parameters:

In the window Finding a solution press the button Options , a window appears on the screen Solution Search Options (Fig. 6);

Check box Linear model, which ensures the use of the simplex method;

Specify the maximum number of iterations (the default is 100, which is suitable for solving most problems);

Check box , if you need to review all stages of searching for the optimal solution;

Click OK , return to window Finding a solution .

Figure 6.

To solve the problem, press the button Execute in the window Finding a solution , there is a window on the screen Solution search results (Fig. 7), which contains the message The solution has been found. All restrictions and optimality conditions are met. If the conditions of the problem are inconsistent, a message is displayed Search can't find suitable solution . If the objective function is not limited, then the message appears Target cell values do not converge.

Figure 7.

For the example under consideration, a solution has been found and the result of the optimal solution to the problem is displayed in the form of input: the value of the objective function corresponding maximum profit and equal to 1320, indicated in cell F6 of the input form, the optimal production plan x 1 =10, x 2 =0, x 3 =6, x 4 =0 is indicated in cells B3:C3 of the input form (Fig. 8).

The amount of resources used to produce products is displayed in cells F9:F11: labor - 16, raw materials - 84, finance - 100.

Figure 8.

If, when setting parameters in the window Solution Search Options (Fig. 6) the checkbox was checked Show iteration results , then all search steps will be shown sequentially. A window will appear on the screen (Fig. 9). In this case, the current values of the variables and the goal functions will be shown in the input form. Thus, the results of the first iteration of searching for a solution to the original problem are presented in the input form in Figure 10.

Figure 9.

Figure 10.

To continue searching for a solution, click the button Continue in the window Current state searching for a solution .

Analysis of the optimal solution

Before proceeding to the analysis of the solution results, let us present the original problem in the form

by introducing additional variables for i, representing the values of unused resources.

Let's create a dual problem for the original problem and introduce additional dual variables v i .

Analysis of the results of the search for a solution will allow us to link them with the variables of the initial and dual problems.

Using a window Solution search results You can call up three types of reports that allow you to analyze the optimal solution found:

Results,

Sustainability,

Limits.

To call a report in a field Report type highlight title the right type and press OK .

1 Results report(Fig. 11) consists of three tables:

Table 1 contains information about the objective function; in the column Originally the value of the objective function is indicated before the calculations begin;

Table 2 contains the values of the required variables x j obtained as a result of solving the problem (optimal production plan);

Table 3 shows the results of the optimal solution for the constraints and for the boundary conditions.

For Restrictions in the column Formula the dependencies that were entered when setting restrictions in the window are shown Finding a solution ; in the column Meaning the values of the resource used are indicated; in the column Difference shows the amount of unused resource. If the resource is fully used, then in the column State message is displayed related ; if the resource is not fully used, this column indicates not connected. For Boundary conditions similar values are given with the only difference that instead of an unused resource, the difference between the value of the variable x j in the found one is shown optimal solution and the boundary condition specified for it (x j ³0).

It is in the column Difference you can see the values of additional variables y i of the original problem in formulation (2). Here y 1 =y 3 =0, i.e. the amount of unused labor and financial resources is zero. These resources are fully utilized. At the same time, the amount of unused resources for raw materials y 2 = 26, which means there is a surplus of raw materials.

Figure 11.

2 Sustainability report(Fig. 12)consists of two tables.

Table 1 shows the following values:

The result of solving the problem (optimal release plan);

- Normir. price, i.e. values showing how much the objective function will change when forced inclusion units of production of the corresponding type into the optimal plan;

Objective function coefficients;

Limit values for the increment of coefficients of the objective function at which the optimal production plan is maintained.

Table 2 contains similar data for restrictions:

Amount of resources used;

- Shadow price, showing how the objective function changes when the value of the corresponding resource changes by one;

Valid values increments of resources at which the optimal production plan is maintained.

Figure 12.

The sustainability report allows for dual assessments.

As is known, dual variables z i show how the objective function changes when the resource of the i-th type changes by one. In an Excel report, the dual estimate is called Shadow price.

In our example, the raw material is not fully used and its resource y 2 = 26. Obviously, an increase in the amount of raw materials, for example, to 111, will not entail an increase in the objective function. Therefore, for the second constraint the dual variable z 2 =0. Thus, if according to this resource there is a reserve, then additional variable will be greater than zero, and dual assessment of this constraint is zero.

In the example under consideration, labor resources and finances were fully used, so their additional variables are equal to zero (y 1 =y 3 =0). If a resource is fully used, then its increase or decrease will affect the volume of output, and therefore the value of the objective function. Dual estimates of restrictions on labor and financial resources are different from zero, i.e. z 1 =20, z 3 =10.

The values of the dual estimates are found in Sustainability report, in table 2, in the column Shadow price.

With an increase (decrease) in labor resources by one unit, the objective function will increase (decrease) by 20 units and be equal to

F=1320+20×1=1340 (with magnification).

Similarly, when the volume of finance increases by one unit, the objective function will be

F=1320+10×1=1330.

Here, in the graphs Permissible increase And Allowable reduction Table 2 shows the permissible limits for changing the amount of resources of the jth type. For example, when the increment in the value of labor resources changes from –6 to 3.55, as shown in the table, the structure of the optimal solution is preserved, i.e. the greatest profit is provided by the output of Prod1 and Prod3, but in different quantities.

Additional dual variables are also reflected in Sustainability report in the column Normir. price table 1.

If the main variables are not included in the optimal solution, i.e. are equal to zero (in the example x 2 =x 4 =0), then the corresponding additional variables have positive values (v 2 =10, v 4 =20). If the main variables are included in the optimal solution (x 1 =10, x 3 =6), then their additional dual variables are equal to zero (v 1 =0, v 3 =0).

These values show how much the objective function will decrease (therefore the minus sign in the values of the variables v 2 and v 4) with the forced release of a unit of this product. Therefore, if we want to forcefully release a unit of product of the type Prod3, then the objective function will decrease by 10 units and will be equal to 1320 -10×1 = 1310.

Let us denote by Dс j the change in the coefficients of the objective function in the original model (1). These coefficients determine the profit received from the sale of a unit of product of the jth type.

In graphs Permissible increase And Allowable Reduction table 1 Sustainability report the limits of change Dс j are shown at which the structure is preserved optimal plan, i.e. It will be profitable to continue to produce products of the type Prodj. For example, if Dc 1 changes within -12 £ Dc 1 £ 40, as shown in the report, it will still be profitable to produce products of the type Prod1. In this case, the value of the objective function will be F=1320+x 1 ×Dс j =1320+10×Dс j .

3 Limit report shown in Fig. 13. It shows within what limits the values x j included in the optimal solution can change while maintaining the structure of the optimal solution. In addition, for each type of product, the values of the objective function are given, obtained by substituting into the optimal solution the value of the lower limit of production of products of the corresponding type with constant values of output of other types. For example, if for the optimal solution x 1 =10, x 2 =0, x 3 =6, x 4 =0 we put x 1 =0 (lower limit) with x 2, x 3 and x 4 unchanged, then the value of the objective function will be equals 60×0+70×0+120×6+130×0=720.

Let's consider an example of a linear programming problem.

It is necessary to determine in what quantity it is necessary to produce products of four types Prod1, Prod2, Prod3, Prod4, 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 Fig. 1.

Resource	Cont1	Prod2	Prod3	Prod4	Sign	Availability
Profit
Labor
Raw materials
Finance

Picture 1.

The mathematical model of the problem has the form:

Entering task conditions

To solve the problem using Excel, you should create a form for entering initial data and enter it. The input form is shown in Fig. 2.

The left parts of the restrictions for resources of each type are entered into cells F8:F10.

Figure 2.

Figure 3.

Solving a linear programming problem

To solve linear programming problems in Excel, you use a powerful tool called Finding a solution . Access to the Search for a solution is carried out from the menu Service , the Search for a Solution dialog box appears on the screen (Fig. 4).

Figure 4.

Entering the conditions of a problem to find its solution consists of the following steps:

1 Assign a target function by placing the cursor in the field Set target cell window Search for a solution and click in cell F6 in the input form;

2 Turn on the switch for the value of the objective function, i.e. indicate it Equal to the Maximum value ;

4 Press the button Add Solution search windows for entering constraints for a linear programming problem; a window appears on the screen Adding a constraint (Fig. 5) :

After entering the last constraint, instead of Add press OK and return to the Search for a solution window.

Figure 5.

Solving a linear programming problem begins with setting the search parameters:

In the window Finding a solution press the button Options , a window appears on the screen Solution Search Options (Fig. 6);

Check box Linear model, which ensures the use of the simplex method;

Specify the maximum number of iterations (the default is 100, which is suitable for solving most problems);

Check box , if you need to review all stages of searching for the optimal solution;

Click OK , return to window Finding a solution .

Figure 6.

To solve the problem, press the button Execute in the window Finding a solution , there is a window on the screen Solution search results (Fig. 7), which contains the message The solution has been found. All restrictions and optimality conditions are met. If the conditions of the problem are inconsistent, a message is displayed Search cannot find a suitable solution. If the objective function is not limited, then the message appears Target cell values do not converge.

Figure 7.

For the example under consideration, a solution has been found and the result of the optimal solution to the problem is displayed in the input form: the value of the objective function corresponding to the maximum profit and equal to 1320 is indicated in cell F6 of the input form, the optimal production plan x 1 =10, x 2 =0, x 3 =6, x 4 =0 is indicated in cells B3:C3 of the input form (Fig. 8).

The amount of resources used to produce products is displayed in cells F9:F11: labor - 16, raw materials - 84, finance - 100.

Figure 8.

Figure 9.

Figure 10.

To continue searching for a solution, click the button Continue in the window Current state of the search for a solution .

Analysis of the optimal solution

Before proceeding to the analysis of the solution results, let us present the original problem in the form

by introducing additional variables for i, representing the values of unused resources.

Let's create a dual problem for the original problem and introduce additional dual variables v i .

Analysis of the results of the search for a solution will allow us to link them with the variables of the original and dual problems.

Using a window Solution search results You can call up three types of reports that allow you to analyze the optimal solution found:

Results,

Sustainability,

Limits.

To call a report in a field Report type highlight the name of the desired type and press OK .

1 Results report(Fig. 11) consists of three tables:

Table 1 contains information about the objective function; in the column Originally the value of the objective function is indicated before the calculations begin;

Table 2 contains the values of the required variables x j obtained as a result of solving the problem (optimal production plan);

Table 3 shows the results of the optimal solution for the constraints and for the boundary conditions.

For Restrictions in the column Formula the dependencies that were entered when setting restrictions in the window are shown Finding a solution ; in the column Meaning the values of the resource used are indicated; in the column Difference shows the amount of unused resource. If the resource is fully used, then in the column State message is displayed related ; if the resource is not fully used, this column indicates not connected. For Boundary conditions similar values are given with the only difference that instead of an unused resource, the difference between the value of the variable x j in the found optimal solution and the boundary condition specified for it (x j ³0) is shown.

Figure 11.

2 Sustainability report(Fig. 12)consists of two tables.

Table 1 shows the following values:

The result of solving the problem (optimal release plan);

- Normir. price, i.e. values showing how much the objective function will change when a unit of production of the corresponding type is forced to be included in the optimal plan;

Objective function coefficients;

Limit values for the increment of coefficients of the objective function at which the optimal production plan is maintained.

Table 2 contains similar data for restrictions:

Amount of resources used;

- Shadow price, showing how the objective function changes when the value of the corresponding resource changes by one;

Acceptable values of resource increments at which the optimal production plan is maintained.

Figure 12.

The sustainability report allows for dual assessments.

As is known, dual variables z i show how the objective function changes when the resource of the i-th type changes by one. In an Excel report, the dual estimate is called Shadow price.

In our example, the raw material is not fully used and its resource y 2 = 26. Obviously, an increase in the amount of raw materials, for example, to 111, will not entail an increase in the objective function. Therefore, for the second constraint the dual variable z 2 =0. Thus, if there is a reserve for a given resource, then additional variable will be greater than zero, and dual assessment of this constraint is zero.

The values of the dual estimates are found in Sustainability report, in table 2, in the column Shadow price.

With an increase (decrease) in labor resources by one unit, the objective function will increase (decrease) by 20 units and be equal to

F=1320+20×1=1340 (with magnification).

Similarly, when the volume of finance increases by one unit, the objective function will be

F=1320+10×1=1330.

Additional dual variables are also reflected in Sustainability report in the column Normir. price table 1.

In graphs Permissible increase And Allowable Reduction table 1 Sustainability report the limits of change in Dc j are shown at which the structure of the optimal plan is preserved, i.e. It will be profitable to continue to produce products of the type Prodj. For example, if Dc 1 changes within -12 £ Dc 1 £ 40, as shown in the report, it will still be profitable to produce products of the type Prod1. In this case, the value of the objective function will be F=1320+x 1 ×Dс j =1320+10×Dс j .