Étiquette : solver_tool

As mentioned earlier, Microsoft Excel’s Goal Seek tool allows you to determine the value of a single input cell required to achieve a desired result in a dependent cell (the result cell). Goal Seek can be used for various purposes — for example, it allows you to find the root of an equation directly on a worksheet. However, when solving equations, using Goal Seek requires a relatively large amount of manual work.

Let us outline the basic algorithm of working with Goal Seek in this case:

• Rewrite the equation so that the unknown appears only on the left-hand side, and the right-hand side is a constant. For example, the equation

x²=x+1.

should be rewritten as

x²âˆ’x−1=0.

• Go to the File tab on the ribbon and select Options. In the Excel Options window, choose Formulas on the left. On the right, under Calculation options, specify the relative tolerance for finding the root of the equation. For example, 10^−5.
• On the worksheet, reserve one cell (e.g., B1) for the unknown. Enter the initial approximation of the root into this cell (for example, 1).
• Reserve another cell (e.g., B2) for the left-hand side of the equation. Enter into this cell the formula of the left-hand side of the equation. In this case:

=B1^2-B1-1

• On the ribbon, go to the Data tab → Data Tools group → What-If Analysis → Goal Seek.
• In the Goal Seek dialog box:
  • In the Set cell field, reference the cell containing the left-hand side of the equation (here, B2).
  • In the To value field, enter the constant from the right-hand side of the equation (in this case, 0).
  • In the By changing cell field, reference the cell containing the unknown (here, B1).
  • Click OK.
• The Goal Seek Status dialog box will appear, and the value in B1 will be replaced with the found root. In this example: 1.618037.

Thus, using the standard Goal Seek tool requires quite a bit of manual work. To simplify the process, we can create an application that will automate much of this effort when solving equations.

Building the Application

Create a form with four labels, four input fields, a spinner control, and a button (Figure 9.37). Set the Name property values of the controls as shown in Table 9.14. Enter the given code into the form module and the Sheet1 worksheet module (see also the file 10-Improved Goal Seek.xlsm on the CD).

Table. Name property values set in the Properties window

Control	Name	Description
TextBox	txtBegin	User enters the initial approximation of the root
Label	lblBegin	Caption for txtBegin
TextBox	txtEquation	User enters the left-hand side of the equation. The equation must be rewritten so that its right-hand side equals 0. The expression must begin with an « = » sign, follow programming syntax, and use « x » as the unknown. For example: =x^2-x-1. In the program, the entered expression will be converted into a worksheet formula.
Label	lblEquation	Caption for txtEquation
TextBox	txtRoot	Displays the computed root. This field is read-only.
Label	lblRoot	Caption for txtRoot
TextBox	txtTol	Relative tolerance for root-finding, linked to the spinner
Label	lblTol	Caption for txtTol
Spinner	spnTol	Sets the relative tolerance for root-finding, displayed in txtTol
Button	cmdOK	Reads the initial guess, the left-hand side of the equation, and the tolerance. Assigns cell B1 of the active worksheet the name « x ». Verifies that the entered expression can be converted into a worksheet formula. If not, a message is displayed and the program is stopped. If the input is valid, the initial guess is written to cell B1 (named « x »), and the formula of the left-hand side is written into cell B2. Using the GoalSeek method of the Range object, the root is found. If unsuccessful, a message is displayed. If successful, the root is formatted according to the specified tolerance and displayed in txtRoot.

 

The GoalSeek method of the Range object selects the value of a parameter (an unknown) that is the solution of an equation with one variable.

It is assumed that the equation has the form: the right-hand side of the equation is a constant (independent of the parameter), and the parameter appears only in the left-hand side of the equation, for example:

f(x)=x³âˆ’3x−5=0.

The GoalSeek method automates the Goal Seek procedure. This method computes the root using the method of successive approximations, the result of which generally depends on the initial guess. Therefore, in order to correctly find the root, you must provide a proper initial guess.

expression.GoalSeek(Goal, ChangingCell)

• expression — the cell containing the formula that represents the left-hand side of the equation being solved. In this formula, the parameter (unknown value) is referenced by the cell specified in the ChangingCell argument.
• Goal — a required parameter specifying the value of the right-hand side of the equation, which does not contain the parameter.
• ChangingCell — a required parameter specifying the cell reserved for the parameter (the unknown). The value entered in this cell before activating the GoalSeek method is considered the initial approximation of the root. The value returned to this cell after executing the method is the found approximation of the root.

The precision with which the root is found, and the maximum number of iterations used, are set by the MaxChange and MaxIterations properties of the Application object. For example, defining the root with an accuracy of 0.0001 within a maximum of 1000 iterations is set by the following code:

With Application
    .MaxIterations = 1000
    .MaxChange = 0.0001
End With

The GoalSeek method returns True if a solution is found and False otherwise.

Example

The following code (Listing 9.1a) searches for the root of the equation

f(x)=x³âˆ’3x−5=0.

using an initial guess of 1.

Solving an Equation (Standard Module)

Sub DemoGoalSeek()
    Range("A1").Name = "x"
    Range("A1").Value = 1
    Range("B1").Formula = "=x^3-3*x-5"  
    If Range("B1").GoalSeek(Goal:=0, ChangingCell:=Range("x")) Then
        MsgBox "Root: " & Range("A1").Value
    Else
        MsgBox "Root not found"
    End If
End Sub

Solving an Equation (Worksheet Module)

Private Sub CommandButton1_Click()
    DemoGoalSeek
End Sub

MS Excel is a convenient tool for finding the roots of equations. General recommendations for solving equations of arbitrary degree can be formulated as follows:

• Tabulate the given function over a certain interval to identify (localize) the roots of the equation (a sign change in the function values). Sometimes, repeated tabulation is necessary for more accurate estimates.
• After localizing the roots, set the maximum number of iterations and the tolerance for root computation (go to the File tab on the ribbon and select Options; in the Excel Options window, select the Formulas category on the left, and on the right — the Calculation options group).
• Compute the roots directly using the Goal Seek tool (go to the Data tab on the ribbon, and in the Data Tools group select What-If Analysis → Goal Seek).
• Plot the graph of the function for clarity (choose the required chart from the Charts group on the Insert tab of the ribbon).

Example

Suppose we need to find all the roots of the equation:

f(x)=x⁵+2x⁴+5x³+8x²âˆ’7x−3=0.

The solution of this equation is shown:

• Approximate tabulation of the function

f(x)=x⁵+2x⁴+5x³+8x²âˆ’7x−3=0.

over the interval [−10;10][-10; 10].

1. • Enter the argument values for the interval [−10;10][-10; 10] with a step of 1 into cells A12:A32.
   • In cells B12:B32, compute the function f(x)f(x).
     Formula for cell B12:

=A12^5+2*A12^4+5*A12^3+8*A12^2-7*A12-3

• A chart can be built for the tabulated function.
• From the calculations, we determine that f(x)f(x) changes sign on the interval [−3;1][-3; 1]. We then perform more precise tabulation on this interval.
  • Enter the argument values for the interval [−3;1][-3; 1] with a step of 0.1 into cells D12:D52.
  • Compute the function values in column E. Formula for cell E12:

=D12^5+2*D12^4+5*D12^3+8*D12^2-7*D12-3

• The results of precise tabulation show 3 sign changes on the interval [−3;1][-3; 1], which indicates the existence of 3 roots of the equation f(x)=0.
• Using the Goal Seek tool, determine the first root of the equation. Place the cursor in cell E14 (or E15), then go to the Data tab on the ribbon, and in the Data Tools group select What-If Analysis → Goal Seek.
  This tool gives the first root of the equation:

x1=0.789295735548989

• Similarly, the other two roots are calculated:

x2=−0.328038079539342,x3=2.07299390058983.

 

Programming the Solver search can help and significantly speed up data processing when it is necessary to analyze how the optimal solution depends on a parameter. Let us demonstrate this with the simplest problem, which is similar to the nonlinear programming task discussed earlier.

Suppose we need to solve the system of nonlinear equations:

x²+y²âˆ’1=0, 2x+3y−d=0

where the parameter dd varies in the interval from 0.2 to 1 with a step of 0.1.

It is obvious that solving this system is equivalent to solving the equation:

(x²+y²âˆ’1)²+(2x+3y−d)²=0.

The original system of equations cannot, of course, be solved directly using Solver, but the equivalent equation with two unknowns is suitable to attempt solving.

Worksheet Setup

On the worksheet, allocate cells A1 and B1 for the unknowns, cell D1 for the parameter values, and in cell C1 enter the formula for the left-hand side of the equation:

=(A1^2+B1^2-1)^2+(2*A1+3*B1-D1)^2

Also, place a button on the worksheet that will open the form of our application.

Application Interface

Now proceed to constructing the application interface. Create a form with three labels, three input fields, and one button. Set the properties of these controls in the Properties window as shown in Table.

Table. Values of properties set in the Properties window

Object	Property	Value
Form	Name	frmSystemSolver
	Caption	Solving a System Dependent on a Parameter
Label	Caption	Initial Value
TextBox	Name	txtBegin
Label	Caption	Final Value
TextBox	Name	txtEnd
Label	Caption	Step Size
TextBox	Name	txtStep
Button	Name	cmdOK
	Caption	OK

Code Requirements

Before entering the necessary code into the form module and worksheet module Sheet1 , make sure that a reference to Solver.xlam is enabled in the References window.

Thus, to solve the problem it is sufficient to enter the initial value, final value of the parameter, and the step size into the input fields. After pressing the OK button, the application will find the solutions and display the parameter values in column E, and the unknowns x and y in columns F and G.

NOTE

From a geometric point of view, the problem considered here also represents finding the intersection point of a line and a circle. Clearly, this problem either has no solution (the line does not intersect the circle), exactly one solution (the line is tangent to the circle), or two solutions (the line intersects the circle).

Our program found only half of the solutions. This is because all solutions were found using the same initial approximation—namely, zero.

Let us create a simple application that solves the transportation problem. In this application, the user will specify references to the cell ranges containing the transportation costs, the volumes of products imported to consumption points, and exported from production points, as well as define the cell range reserved for the calculated transportation volumes. All other necessary actions will be performed by the application: entering auxiliary formulas into the worksheet cells that return the total transportation cost and the volumes of imported and exported products at each point; checking whether the model is balanced; setting all required parameters for the solution search; and starting the execution. The result of the solution will be displayed as a corresponding note on the worksheet.

Let us proceed to the construction of the application. First, place the necessary data on the worksheet and reserve space for the target cell. Also, place a button on the worksheet that will launch the appropriate form for your application. Next, create a form, place four labels, four RefEdit controls, and one button on it, and set their property values in the Properties window as shown in Table.

Table. Values of properties set in the Properties window

Object	Property	Value
Form	Name	frmSolver
	Caption	Transportation Problem
Label	Caption	Transportation Costs
RefEdit	Name	refCosts
Label	Caption	Export Volumes
RefEdit	Name	refOut
Label	Caption	Import Volumes
RefEdit	Name	refIn
Label	Caption	Transportation Volumes
RefEdit	Name	refVar
Button	Name	cmdSolve
	Caption	Execute

Before writing the code, make sure that the reference to Solver.xlam is enabled in the References window, which is displayed on the screen by selecting the menu command Tools | References. If Solver.xlam is missing from the list of Available References, click Browse and open Solver.xla from the directory
C:\Program Files\Microsoft Office\Office14\Library\SOLVER.

Enter the required code accordingly into the modules of the form and the worksheet module Sheet1 .

NOTE

Notice how the Evaluate method is used in the program to convert an expression into a value. This approach saved us from the need to add two loops in the code to determine the total volumes of imported and exported products or to insert unnecessary additional formulas into the worksheet cells.

NOTE

The use of the SolverReset() function in the program before setting the solution search parameters is essential. By setting the solver parameters to their default values, the SolverReset() function clears the Solver window of all previous settings. If the function SolverReset() is not used, the constraints added by the SolverAdd() functions will accumulate with each click of the Execute button. It is easy to imagine what would happen to the Constraints list in the Solver window after, for example, a dozen clicks of the Execute button!

After solving a transportation problem manually with the Solver tool, let us consider examples that demonstrate its programmatic use. For solving optimization problems in VBA, the following functions are available:

• SolverAdd()
• SolverOk()
• SolverChange()
• SolverOptions()
• SolverDelete()
• SolverReset()
• SolverFinish()
• SolverSave()
• SolverLoad()
• SolverSolve()

SolverOk()

Defines the optimization problem. It sets the parameters that are normally specified manually in the Solver Parameters dialog box.

Syntax:

SolverOk(SetCell, MaxMinVal, ValueOf, ByChange)

• SetCell — specifies the target cell containing the objective function.
• MaxMinVal — specifies the type of optimization:
  • 1 = maximize
  • 2 = minimize
  • 3 = set to a specific value
• ValueOf — if MaxMinVal = 3, this parameter specifies the target value.
• ByChange — specifies the range of variable cells.

SolverAdd()

Adds a constraint to the model. Equivalent to manually adding a constraint in the Add Constraint dialog.

Syntax:

SolverAdd(CellRef, Relation, FormulaText)

• CellRef — left-hand side of the constraint (cell or range).
• Relation — integer from 1 to 5 specifying the relation type:
  • 1 = ≤
  • 2 = =
  • 3 = ≥
  • 4 = integer constraint
  • 5 = binary (0 or 1) constraint
• FormulaText — right-hand side of the constraint (cell, range, or value). For relations 4 and 5, this parameter is omitted.

SolverDelete() and SolverChange()

• SolverDelete() removes a constraint.
• SolverChange() modifies a constraint.
  Their syntax is the same as SolverAdd().

SolverDelete(CellRef, Relation, FormulaText)
SolverChange(CellRef, Relation, FormulaText)

SolverOptions()

Sets advanced options of Solver (as in the Solver Options dialog box).

Syntax:

SolverOptions(MaxTime, Iterations, Precision, AssumeLinear, StepThru, _
              Estimates, Derivatives, Search, IntTolerance, Scaling, _
              Convergence, AssumeNonNeg)

Closely related is SolverReset(), which restores default option values. It has no parameters.

SolverSolve()

Runs the Solver — equivalent to pressing the Solve button in the Solver Parameters dialog.

Syntax:

SolverSolve(UserFinish, ShowRef)

• UserFinish — Boolean. If False (default), results are displayed in the Solver Results dialog box. If True, results are applied automatically without showing the dialog.
• ShowRef — reference to a macro that is run between iterations.

Returns 0 if a solution is found.

SolverSave() and SolverLoad()

• SolverSave(SaveArea) — saves the model into the specified cell range.
  Example:
• SolverSave « Sheet1!A1:A3 »
• SolverLoad(LoadArea) — loads a model from the specified range.

SolverFinish()

Applies the results (as if pressing OK in the Solver Results dialog).

Important Note

Before using these functions in VBA:

• Set a reference to Solver in the Visual Basic Editor: Tools → References → Solver.
• If Solver is not listed in Available References, click Browse and open Solver.xlam, usually located at:

C:\Program Files\Microsoft Office\OfficeXX\Library\Solver

(where X is your Office version, e.g., Office14).

A nonlinear programming (NLP) problem is formulated similarly to a linear programming (LP) problem, except that the objective function and/or at least one constraint is nonlinear. Consequently, NLP problems are harder than LP problems, and there is no general method analogous to the Simplex method for LP. NLP also includes nonlinear integer and discrete optimization problems.

By solution approach, nonlinear optimization problems are divided into:

• Constrained optimization (finding extrema subject to constraints and bounds), and
• Unconstrained optimization (finding extrema without additional conditions).

There exist many numerical methods; the appropriate choice depends on the type of nonlinearity. The Excel Solver add-in helps with the numerical solution of NLP problems.

Solving a System of Nonlinear Equations with Solver

Consider the system

(1)

where f_i(x,y), i=1,2 are nonlinear functions of x,y and C_i are constants.

A pair (x,y) solves if it solves the single nonlinear equation

(2)

Geometrically, solutions (1) are the intersection points of the curves f₁(x,y)=C_{1 ,} f₂(x,y)=C_2.

Root-finding procedure:

• Determine (at least approximately) an interval where solutions may exist for (1) or (2). Consider domains, behavior of the functions, etc. Sometimes a reasonable initial guess is used.
• Tabulate the function in (2) over a grid of x,yx,y on the chosen interval, or plot the curves f₁(x,y)=C_1  and f₂(x,y)=C_2..
• Localize candidate roots—pick grid points where (2) is minimal, or identify curve intersections for (1).
• Use Solver to refine each candidate into an accurate root.

Worked Example.

Let’s solve the following system of nonlinear equations:

(x-1)^2 + (y+1)^2 = 4
5x + 4y = 2.

It is easy to see that the solutions are the intersection points of a circle (radius = 2, center (1, –1)) and a line.

We can replace this system by the equivalent single equation:

(x - 1)^2 + (y + 1)^2 - 4 + (5x + 4y - 2)^2 = 0

for which we will find the solutions using the Solver add-in.

1.Interval for exploration and plotting

From the graphs, a reasonable search box is [−3,3][-3,3] for both x and y.

• Cells B3:B43: values of x.
• Plotting formulas (Excel) for the two branches of the circle and the line:
  • C3: =-1+SQRT(4-(B3-1)^2)
  • D3: =-1-SQRT(4-(B3-1)^2)
  • E3: =(2-5*B3)/4

2. Tabulation on [−3,3][-3,3] with step 0.5

Create a grid and compute the objective

Φ(x,y)=((x−1)2+(y+1)2−4)2+(5x+4y−2)2

to identify small values (potential roots).

3. Root localization on a grid

• A47:A59: x-values on [−3,3][-3,3] with step 0.5.
• B46:N46: y-values on [−3,3][-3,3] with step 0.5.
• B47 (copy to B47:N59):
• =((($A47-1)^2+(B$46+1)^2-4)^2+(5*$A47+4*B$46-2)^2)
• B62 (copy across to get row minima as needed):
• =MIN(B47:B60)

From this coarse scan, example candidate pairs include (−2.5,−2.5)(-2.5,-2.5), (2,−2)(2,-2), (0,0.5)(0,0.5), (0,1)(0,1).

4. Refinement with Solver

• Place initial guesses in D69:E72 (each row one candidate (x,y)(x,y)).
• Objective cell G69 (copy to G69:G72):
• =((D69-1)^2+(E69+1)^2-4)^2+(5*D69+4*E69-2)^2

• Open Solver:
  • Set Objective: G69 (then G70, … for each row).
  • To: Min.
  • By Changing Variable Cells: D69:E69.
  • Subject to the Constraints: (none needed here; unconstrained).
  • Options: For nonlinear problems, you may use GRG Nonlinear; provide reasonable starting values.

Run Solver for each initial guess.

Results (as reported):
The system has two solutions:

• (x,y)≈(2.3675745729901,  −2.45934248863711)
• (x,y)≈(−0.123564081639673,  0.654434224216163)

Discrete programming studies extremum problems in which the decision variables are subject to discreteness and the feasible set is finite. These are primarily problems where many factors and objects are physically indivisible. Discrete programming also includes a range of integer programming problems in which the decision variables take only integer values (e.g., staffing/scheduling) or logical, Boolean values 0 or 1 (e.g., the assignment problem). Below we consider the solution of an assignment problem.

Each instructor can teach certain types of classes. The hourly pay cij for instructor ii on class type is given in Table. Construct a teaching plan so that all class types are covered, each instructor teaches only one class type, and the total hourly cost is minimized.

Table. Hourly costs

Instructors \ Courses	1	2	3	4
1	350	420	610	200
2	890	130	650	900
3	430	520	600	720
4	830	610	780	470

Steps to Solve

Check balance

The problem is balanced because the number of instructors equals the number of class types. If unbalanced, introduce the missing number of dummy instructors (rows) or dummy class types (columns).

Constructing the mathematical model of the problem.
Let x_ij=1 if the i-th teacher performs the j-th type of class, and x_ij=0 otherwise.
Then the mathematical model is: minimize the functional

subject to the constraints:

Solve with the Solver add-in

Prepare the worksheet as in Fig.

The calculation formulas are shown in Table.

Table. Worksheet formulas for the assignment problem

Description	Cell	Formula
Constraints	G11	=SUM(C11:F11)
	G12	=SUM(C12:F12)
	G13	=SUM(C13:F13)
	G14	=SUM(C14:F14)
Constraints	C15	=SUM(C11:C14)
	D15	=SUM(D11:D14)
	E15	=SUM(E11:E14)
	F15	=SUM(F11:F14)
Quality functional (work cost)	G17	=SUMPRODUCT(C5:F8; C11:F14)

In the Solver Parameters window :

• Set Objective: the total cost cell.
• To: Min.
• By Changing Variable Cells: the assignment matrix x_ij.
• Subject to the Constraints:
  • Row sums =1=1 (each instructor once).
  • Column sums =1=1 (each class once).
  • Binary on all xijcells.
• In Options, ensure appropriate precision; enable Assume Linear Model if using Simplex with binary constraints (still requires Binary flag).

The resulting optimal assignment is shown:

In the general case, the transportation problem can be formulated as follows: in mm supply points A₁,…,A_m there is a homogeneous commodity with quantities a₁,…,a_m units, respectively. This commodity must be delivered to consumers B₁,…,B_n with demands b₁,…,b_n. The cost of transporting one unit from supply point i (i=1,…,m) to destination j (j=1,…,n) is c_ij. It is required to construct a shipping plan that fully satisfies consumer demand while minimizing the total transportation cost.

Mathematically, the transportation problem can be written as:

Thus, given the system of constraints with and the linear objective, the task is to find among all solutions a non-negative solution that minimizes if the total supply equals the total demand:

If either of the following holds:

then the model is called open (unbalanced).

To make an open transportation problem solvable, it should be transformed into a closed one:

• If

introduce a dummy destination B_n+1 (i.e., add an extra column). The demand of the dummy consumer is  .

The transportation costs to the dummy destination are taken equal (usually zero, if no storage cost is specified), i.e .

• If

introduce a dummy supplier A_m+1 (i.e., add an extra row). The supply of the dummy supplier is

 .

The transportation costs from the dummy supplier are taken equal (usually zero, if no penalty costs for under-delivery are specified), i.e.,

.

When transforming an open problem into a closed one, the objective function does not change, since all terms corresponding to the additional (dummy) shipments are zero.