Nonlinear Programming:SAMPLE APPLICATIONS

By -

SAMPLE APPLICATIONS

The following examples illustrate a few of the many important types of problems to which nonlinear programming has been applied.

The Product-Mix Problem with Price Elasticity

In product-mix problems, such as the Wyndor Glass Co. problem introduced in Sec. 3.1, the goal is to determine the optimal mix of production levels for a firm’s products, given limitations on the resources needed to produce those products, in order to maximize the firm’s total profit. In some cases, there is a fixed unit profit associated with each product, so the resulting objective function will be linear. However, in many product-mix prob- lems, certain factors introduce nonlinearities into the objective function.

For example, a large manufacturer may encounter price elasticity, whereby the amount of a product that can be sold has an inverse relationship to the price charged. Thus, the price-demand curve for a typical product might look like the one shown in Fig. 13.1, where p(x) is the price required in order to be able to sell x units. The firm’s profit from produc- ing and selling x units of the product then would be the sales revenue, xp(x), minus the production and distribution costs. Therefore, if the unit cost for producing and distributing the product is fixed at c (see the dashed line in Fig. 13.1), the firm’s profit from pro- ducing and selling x units is given by the nonlinear function

INTRODUCTION TO OPERATIONS RESEARCH-0163

INTRODUCTION TO OPERATIONS RESEARCH-0164

the other hand, it may increase instead, because special measures such as overtime or more expensive production facilities may be needed to increase production further.

Nonlinearities also may arise in the gi(x) constraint functions in a similar fashion. For example, if there is a budget constraint on total production cost, the cost function will be nonlinear if the marginal cost of production varies as just described. For constraints on the other kinds of resources, gi(x) will be nonlinear whenever the use of the corresponding resource is not strictly proportional to the production levels of the respective products.

The Transportation Problem with Volume Discounts on Shipping Costs

As illustrated by the P & T Company example in Sec. 9.1, a typical application of the transportation problem is to determine an optimal plan for shipping goods from various sources to various destinations, given supply and demand constraints, in order to mini- mize total shipping cost. It was assumed in Chap. 9 that the cost per unit shipped from a given source to a given destination is fixed, regardless of the amount shipped. In actu- ality, this cost may not be fixed. Volume discounts sometimes are available for large ship- ments, so that the marginal cost of shipping one more unit might follow a pattern like the one shown in Fig. 13.3. The resulting cost of shipping x units then is given by a non- linear function C(x), which is a piecewise linear function with slope equal to the mar- ginal cost, like the one shown in Fig. 13.4. [The function in Fig. 13.4 consists of a line segment with slope 6.5 from (0, 0) to (0.6, 3.9), a second line segment with slope 5 from

(0.6, 3.9) to (1.5, 8.4), a third line segment with slope 4 from (1.5, 8.4) to (2.7, 13.2), and a fourth line segment with slope 3 from (2.7, 13.2) to (4.5, 18.6).] Consequently, if each combination of source and destination has a similar shipping cost function, so that the cost of shipping xij units from source i (i = 1, 2, . . . , m) to destination j ( j = 1, 2, . . . , n) is given by a nonlinear function Cij(xij), then the overall objective function to be minimized is

INTRODUCTION TO OPERATIONS RESEARCH-0165INTRODUCTION TO OPERATIONS RESEARCH-0166

Amount shipped

Portfolio Selection with Risky Securities

It now is common practice for professional managers of large stock portfolios to use computer models based partially on nonlinear programming to guide them. Because investors are concerned about both the expected return (gain) and the risk associated with their in- vestments, nonlinear programming is used to determine a portfolio that, under certain assumptions, provides an optimal trade-off between these two factors. This approach is based largely on path-breaking research done by Harry Markowitz and William Sharpe that helped them win the 1990 Nobel Prize in Economics.

A nonlinear programming model can be formulated for this problem as follows. Sup- pose that n stocks (securities) are being considered for inclusion in the portfolio, and let the

An Application Vignette

The Bank Hapoalim Group is Israel’s largest banking group, providing services throughout the country. As of the beginning of 2012, it had approximately 300 branches and eight regional business centers in Isreal. It also oper- ates worldwide through many branches, offices, and sub- sidiaries in major financial centers in North and South America and Europe.

A major part of Bank Hapoalim’s business involves providing investment advisors for its customers. To stay ahead of its competitors, management embarked on a restructuring program to provide these investment advisors with state-of-the-art methodology and technology. An OR team was formed to do this.

The team concluded that it needed to develop a flexi- ble decision-support system for the investment advisors that could be tailored to meet the diverse needs of every customer. Each customer would be asked to provide extensive information about his or her needs, including choosing among various alternatives regarding his or her investment objectives, investment horizon, choice of an index to strive to exceed, preference with regard to liquidity and currency, etc. A series of questions also would be asked to ascertain the customer's risk-taking classification.

The natural choice of the model to drive the resulting decision-support system (called the Opti-Money System) was the classical nonlinear programming model for port- folio selection described in this section of the book, with modifications to incorporate all the information about the needs of the individual customer. This model generates an optimal weighting of 60 possible asset classes of equities and bonds in the portfolio, and the investment advisor then works with the customer to choose the specific equities and bonds within these classes.

During the first year of full implementation, the bank’s investment advisors held some 133,000 consultation sessions with 63,000 customers while using this decision-support system. The annual earnings over benchmarks to customers who follow the investment advice provided by the system total approximately US$244 million, while adding more than US$31 million to the bank’s annual income.

Source: M. Avriel, H. Pri-Zan, R. Meiri, and A. Peretz: “Opti- Money at Bank Hapoalim: A Model-Based Investment Decision- Support System for Individual Customers,” Interfaces, 34(1): 39–50, Jan.–Feb. 2004. (A link to this article is provided on our website, www.mhhe.com/hillier.)

decision variables xj ( j = 1, 2, . . . , n) be the number of shares of stock j to be included. Let J.j and ujj be the (estimated) mean and variance, respectively, of the return on each share of stock j, where ujj measures the risk of this stock. For i = 1, 2, . . . , n (i * j ), let uij be the covariance of the return on one share each of stock i and stock j. (Because it would be difficult to estimate all the uij values, the usual approach is to make certain assumptions about market behavior that enable us to calculate uij directly from uii and ujj .) Then the ex- pected value R(x) and the variance V(x) of the total return from the entire portfolio are

INTRODUCTION TO OPERATIONS RESEARCH-0167

where L is the minimum acceptable expected return, Pj is the price for each share of stock j, and B is the amount of money budgeted for the portfolio.

One drawback of this formulation is that it is relatively difficult to choose an appro- priate value for L for obtaining the best trade-off between R(x) and V(x). Therefore, rather than stopping with one choice of L, it is common to use a parametric (nonlinear) pro- gramming approach to generate the optimal solution as a function of L over a wide range of values of L. The next step is to examine the values of R(x) and V(x) for these solutions that are optimal for some value of L and then to choose the solution that seems to give the best trade-off between these two quantities. This procedure often is referred to as gen- erating the solutions on the efficient frontier of the two-dimensional graph of (R(x), V(x)) points for feasible x. The reason is that the (R(x), V(x)) point for an optimal x (for some L) lies on the frontier (boundary) of the feasible points. Furthermore, each optimal x is effi- cient in the sense that no other feasible solution is at least equally good with one mea- sure (R or V ) and strictly better with the other measure (smaller V or larger R).

This application of nonlinear programming is a particularly important one. The use of nonlinear programming for portfolio optimization now lies at the center of modern fi- nancial analysis. (More broadly, the relatively new field of financial engineering has arisen to focus on the application of OR techniques such as nonlinear programming to various finance problems, including portfolio optimization.) As illustrated by the application vignette in this section, this kind of application of nonlinear programming is having a tremendous impact in practice. Much research also continues to be done on the properties and application of both the above model and related nonlinear programming models to sophisticated kinds of portfolio analysis.3

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more