Computation - Operations Research Models and Methods

Computation

Mathematical Programming

Nonlinear Programming

Example Problem

Solving the Problem

Excel Page
Download

	Nonlinear Programming
	- Example Problem - Product Mix with Decreasing Marginal Profit

We modify the product mix example used to illustrate the linear programming add-in to incorporate nonlinear terms in the objective. Management has determined that the marginal profit for each product decreases as the number produced increases. A study determines that the profit for each product is approximated by the quadratic function given below. The table shows the coefficients for each product. With the same constraints on machine time, our goal is to find the product mix that maximizes profit.

The graph at the left shows the profit for the first product as a function of production. The function starts at zero, rises to a maximum and then decreases. This is a concave function of production. The marginal profit, or the derivative of the profit function, is decreasing with production volume.

The mathematical programming model is the same as in the linear programming example except the objective function is now the sum of nonlinear terms. This is called a separable objective function because each term is a function of only one decision variable.

Excel Model

To model this problem with the Mathematical Programming Add-in, select Nonlinear from the OR_MM menu. The Nonlinear Model Dialog presents the same options as the Linear Model Dialog except that it also asks for the number of extra columns. Although not necessary for this problem, we enter 1 as the number of extra columns to illustrate the effect. The remainder of the options on this dialog should be clear from the discussion of the Linear Model Dialog. There are no solver options because only the Excel Solver can handle nonlinear models. Although the Excel Solver does solve problems with integer variables, great care must be exercised when interpreting these answers. Theoretically, all nonlinear solutions should be judged carefully with respect to optimality. Problems may have multiple local optimums, and simple algorithms may reach one of these rather than the global optimum.

The worksheet obtained after data entry and solution is below. The solution was found using the Excel Solver program.

As for linear models, the linear objective coefficient row (row 12) models the linear terms of the objective. These coefficients are multiplied by the vector of variable values by the Excel formula in cell I2. The cell is labeled Linear to indicate that this value is the linear part of the objective function.

The worksheet has two additional rows in the portion of the model describing the variables, one row for nonlinear objective coefficients and the other for nonlinear terms. The space for nonlinear objective coefficients in row 14 is useful for nonlinear terms that have only a single coefficient. In this case it holds the values of -d. The equations for the quadratic terms are entered into row 13. We color the cells in this row from column H through M magenta. This color indicates that the student is to enter Excel formulas in these cells. For example, the equation in I13 is to be the square of the value of P1. That value is in I8, so the formula in I13 is.

=I8^2

This describes the nonlinear effect of the variable in P1 on profit. The rest of the terms in row 13 are similar, but each nonlinear term refers to the variable above it. For example J13 holds the formula (=J8^2). The terms from J13 through M13 are easily copied form I13 using the Excel Fill Right command.

The nonlinear coefficients multiply the nonlinear terms and are summed to obtain the entry called the Nonlinear 1 component of the objective function. The formula for this contribution is in cell I3. In general, row 13 may hold any nonlinear, differentiable functions of the variable values. It is important that the functions be well defined for all values of the variables. For example the function (=1/I13) would fail if I13 were allowed to take on the value 0.

Initially all nonlinear terms are set to zero. Both the nonlinear expressions in row 13 and the nonlinear coefficients in row 14 must be nonzero for the nonlinear terms to affect the objective function.

A column (H) has been created to hold other nonlinear terms that may appear in the objective function and constraints. Although not used for this example, these cells can hold any continuous, differentiable functions of the decision variables. Where problems have several identifiable sources of nonlinear terms, it may be convenient to have more than one column to hold these terms. The nonlinear terms in the extra columns are summed and are shown as the Nonlinear 2 component of the objective function in cell I4. The Linear, Nonlinear 1, and Nonlinear 2 values are summed in cell F4 to obtain the objective function. This quantity is optimized by the Solver.

Nonlinear terms in the constraints can be entered as explicit functions of the decision variable in the range H17:H20. The nonlinear function values are accumulated with the linear constraint functions in the Value column of the constraints.

Sensitivity Analysis

The sensitivity analysis provided by the Excel Solver for nonlinear programming problems has a slightly different format than for linear programming problems as illustrated below. The reduced gradient for a variable is the partial derivative of the objective function with respect to that variable, evaluated at the stopping point of the algorithm. The Lagrange multipliers are similar to the shadow prices associated with a linear problem.