# The Liner Programming Problem Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

TDC which is an investment advisory company, would like to design and adopt an assess allocation model which uses to recommend its customer to invest in a portfolio of funds in order to maximizing the investment whilst minimizing the risk of the customer.

The purpose of this problem are (1.2.1) to identify the optimal level of yield for the portfolio which contains each of three investment options including an growth stock fund, an income fund, and an money market fund whilst calculating the annual yield for the investment recommendation above; after that, it tests sensitivity of this model: how would the investment amount and annual yield change in two particular situations: (1.2.4.1) the annual yield for the income fund reduce to 10% and (1.2.4.2) the client has another \$100,000 to invest.

\$ 800,000 should be invested in the portfolio.

The overall risk index for the Portfolio of each client has a maximum of 0.05

Table1.1 Data for the TDC -A Maximization Problem

The first procedure is to build up a linear programming model for maximizing the return on investment subject to several constraints.

## Define Variables:

Let G be the amount of money should be invested in growth fund; I be the amount of money should be invested in income fund; and M be the amount of money should be invested in money market fund.

## Objective Function:

The objective of this problem is to maximize the total profit P from the combination of the three funds, where total profit of the portfolio is equal to the sum of the amount of money invested in per each fund. Hence, the objective function is

where G, I, M are defined earlier, the amount of money invested in growth fund, income fund and money market fund respectively.

## Constraint Relationships:

The sums of the amount of money must be less than or equal to the total amount of money available, which is \$ 800,000. The relationship can be express as

The overall risk index the Portfolio of each client has a maximum of 0.05, where the risk of the growth fund is 0.10 G. Similarly, the risk of income fund and money market fund can be express as 0.07 I and 0.01 M. With an utilisation of a weight average of each risk index for three funds, the following constraint is developed

For growth fund, which must be satisfied within the amount limits of the total portfolio value from 20 % up to 40%, the constraint is

For income fund, which must be satisfied within the amount limits of the total portfolio value from 20 % up to 50%, the constraint is

For money market fund, where the amount limits of the total portfolio value for it must be up 30%, the constraint is

Finally, as the assumption of all linear programming models, all variable are not possible to be negative. Therefore, each of variables should be nonnegative:

Equations 1 through 7 compose a linear-programming formulation of this profit maximization problem.

## 1.2.2 Solution

As this problem involving more than two variable, therefore, graphical method can not be used to obtain an optimal solution. Therefore, "Excel Solver" is employed to solve of this linear programming problem.

The data are type in and formulas used in this problem are set up as follow.

Figure 1.1 A spreadsheet formulation of this Maximization Problem

The following solver settings are specified

Figure 1.2 Beginning the Excel solver parameters setup

## 1.2.3 Interpretation

The optimal solution of this problem is illustrated in below

Figure 1.3 A spreadsheet solution of this Maximization Problem

Finally by rounding up the amount, the investment recommendation for the clients is as follow: \$ 248,889 should be invested in growth fund; \$ 160,000 should be invested in income fund; and \$ 391,111 should be invested in money market fund to obtain a maximum profit of \$ 94,133 (\$ 248,889*0.18 + \$ 160,000*0.125 + \$ 391,111*0.075). The annual yield for the entire recommended portfolio is \$ 94,133 / \$ 800,000 = 0.118 = 11.8 %

## 1.2.4.1 Change of Annual Yield for Income Fund

Since the annual yield for the income fund drop from 12.5 % to 10%, and the remaining formulas and solver settings used in part 1.2.2 maintain the same.

Figure 1.4 A spreadsheet solution for the change of Annual Yield for Income Fund

The solutions of the investment amount remain unchanged. After rounding up, the new allocation should now be \$ 248,889 for growth fund, \$ 160,000 for income fund; and \$ 391,111 for money market fund.

The amount of money allocation would not be changed can be explain by the Sensitivity report of the period analysis progress.

Figure 1.5 The Sensitivity report for the original analysis

Table 1.2 the range of objective coefficient range for each fund return

If the change of the annual yield is with the objective function coefficients, the resolving the problem is not required.

Although the annual yield for the income fund drop from 12.5 % to 10%, but 0.10 is still within the objective coefficient range for the income fund return, therefore the amount of money allocation for the portfolio would be no change. However, a decrease in return on investment is expected equal to \$ 160,000 * (0.125-0.10) = \$4000.

Therefore, the annual profit changed to \$ 90,133 (\$ 248,889*0.18 + \$ 160,000*0.10 + \$ 391,111*0.075) or (\$ 94,133-\$4000). And the portfolio annual yield is \$ 90,133/ \$ 800,000 = 0.113 =11.3 %

## 1.2.4.2 Change of Total Money Available

The client has another \$100,000 to invest, which means that the total money available is \$ 900,000. And the remaining formulas and solver settings used in part 2.2 maintain the same.

Figure 1.6 A spreadsheet solution for the Change of the Total Money Available

The solutions of the investment amount and profit changed. Therefore, the amount of money invested should now be \$ 280,000 for growth fund, \$ 180,000 for income fund; and \$ 440,000 for market fund. And the annual profit increase to \$ 105,900 (\$280,000*0.18 + \$ 180,000*0.125 + \$ 440,000*0.075). And the portfolio annual yield is \$ 105,900/ \$ 900,000 = 0.118 =11.8 %

1.3 Conclusion and Recommendation

Compare the results of "investing \$ 800,000" and "decreasing the return to 0.10" solved above, under the other constraints remain the same apart from a decrease of 0.25% of income fund yield, but the annual profit fall \$ 4,000 from \$ 94,133 to \$ 90,133. The company could suggest its clients according to the reasonable return and risk expectation of its clients can afford, since it is always a case in investment like that high risk associate with high return. For most cases in financial industry, companies always prefer a strategy which could gain a profit with a lower risk.

Compare the results of "investing \$ 800,000" and "\$ 900,000" situations solved above, there is no difference in the annual yield return between the two situations, having 11.8 % because of the annual yield for each fund and other constraints are fixed. This means that it is no difference between two situations in term of risk. Therefore, based on the annual yield for whole portfolio is fixed, the result of maximising profit is totally depends on how much money that the client could invest.

As the solution above using rounding method to make the numbers become integer, if the company needs a more precise integer solution, it may be better to set the decision variables with "int" constrains in the setting solver parameters step.

## 2.0 Literature Review

2.1 Introduction

This section presents a summary of "Nu-Kote's Spreadsheet Linear-Programming Models for Optimizing Transportation" which is a case study of spreadsheet Liner-Programming models LeBlanc et al (2004) published.

Nu-Kote is the world's largest cartridges re-manufacturer especially in printers, copiers, and fax machines, severing 5000 customers.

The purpose of this journal is to aid managers of Nu-Kote International to minimize the shipping expenditure of transferring manufacturing materials and finished products between 5 vendors, 5 plants, 4 warehouses and customer whist to maximize the responsiveness to its customers.

2.2 Problem

Nu-Kote as many companies transferred its production plant to china in order to maintain the position of the low-cost leader in the industry. However, this has resulted in increasingly complex shipment flow without reviewing the total transportation costs. Hence, Nu-Kote needed to optimize its inbound (from vendors and plants to warehouses) and outbound (from warehouses to customers) logistics.

## Distributions of plants, warehouse, and customers:

The company has plants and warehouse in Zhu Hai City, China; Chatsworth, California; Franklin, Tennessee (headquarter of the company); Connellsville, Pennsylvania; Rochester, New York.

Currently, Franklin covers within 500 miles of 50% populations of the United States, and within 1000 miles of 80% of its key customers. However, approximately 80 % of its products are produced in other 4 plants expect from Franklin. Currently, those warehouses are storing raw materials and ï¬nished products which ship to Franklin later. What if other warehouses change its/ their nature operating like Franklin.

Therefore, in order to distribute products in a cost effective approach, it is needed to use a Linear-Programming Model to solve this problem.

2.3 Formulation of Problem

This problem is a transportation problem type of a linear programming problem due to the fact that it involves using the linear programming to determine optimally transport program. As this problem is similar with most applications of the transportation problems having a great deal number of constraints and variables, so to apply the proper computational procedure should be used to solve this type of questions (Hillier and Lieberman, 2005).

At the beginning, the authors initiated to perform this study with a non-linear version to calculate costs in a more accurate way. However, they noticed that optimal solutions could not be generated for models with large amount of non-linear and non-convex cost terms. Therefore, they used a linear approximation for the transportation cost, and assumed the transportation cost of per unit is constant. Finally, they found nearly all the shipment of Nu-Kotes were generally linear.

There are three phases involved to formulate the Nu-Kote's LP model.

In the first phase, the data about all participants involving in logistic system (such as the capacities of vendor, locations, plant production and warehouse storage; the clients' locations and demands for each product) are collected and integrated. What is more, two assumptions were established: the demand of clients at particular location was calculated by grouping all customers with the same zip code considering as a single customer location; the number of products was divided into six categories.

In the second phase, the coefficients for the transportation costs between various entities combinations were estimated. As the different shipments cost between shipment of inbound logistic (using truck load (TL) carriers) and outbound logistic to customer (using less than truckload (LTL) carriers) are existed, freight costs were determined by using separate regression model to consider it with weight and distance for one unit of product, causing that coefficients for the cost of holding and handling inventory at warehouse was added. Following by this, the validation of the regression analysis was implemented by putting a great deal of real shipping data into the model and comparing the actual and predicted costs (total cost includes the costs of the inbound and outbound transportation and holding and handling inventory). Since the difference between the model and actual is within five percent, they judged it to be acceptable. After calculations, the regression equation "total shipping cost = 0.000133 * distance * weight" was obtained. The Figure 2.1 shows one of the records. In order to estimate the distances more precise, authors used the ZIPFINDDELUXE to generate the actual distance and let it multiplied by 1.14 (which is recommended by Simchi-Levi et al (2000)).

Figure 2.1 one of the records in the compression of actual and predicted total distribution cost per unit.

In the third phase, the spreadsheet LP models were constructed to minimize cost to transfer products from their origins to customer, accounting with the cost of inventory holding and handling, and to maximize the responsiveness to customers which used the method advocated by Robinson et al (1993) and requested by company's managersâ”€ quantify this responsiveness as 1,000-miles shipping distance (Since customer service is only available within 1,000-miles radius) from a particular warehouse to a client. Figure 2.2, 2.3, 2.4 are the snapshot of the excel spreadsheet table attached in the original journal.

Figure 2.2 the excel spreadsheet with changing cells and target cell.

Figure 2.3 the excel spreadsheet with vendor and plant constraints.

Figure 2.4 the excel spreadsheet with warehouse balance, customer location, and warehouse capacity constrains.

After the LP model was developed and all referring variables were deleted, this excel-based LP model contains between 5,000 and 9,700 variables, and approximately 2,454 constraints.

## Decision variables

For

This LP model is used within a 1,000 mile allowable delivery distance only.

## Objective Function

The objective of this problem is to minimise the total shipping cost while meeting the capacities of each site, the lead times for shipment and remanufacturing, the demands of customer and so forth in specific period. The objective function is:

## Constraints

2.4 Results of model

As this LP model is large-scale contains over thousands of variables and constrains, the authors purchased the premium Excel Solver which particular design for solving large-scale LP problem in order to solve it in Excel. The duration of solution time was approximately 25 minutes.

By using different configurations of its warehouse to customer to assess the lowest overall cost of combining with two, three and four warehouses where include Franklin. After calculation, authors found that combination of Franklin in Tennessee and Chatsworth in California would be the optimal solution for coping with outbound logistic rather than only the Franklin warehouse (refer to Figure 2.4).

Figure 2.4 the combination of outbound warehouse(s)

corresponding to its/their relative overall costs

In order to gain further insight into how the allowable shipping miles affect on total cost with the optimal solution mentioned above, a graph of the related values was summarised (refer to Figure 2.5 ). As can be seen, the annual transportation cost can be reduced sharply if company extends its shipping distance from 1,000 to 1,500 or 2,000 miles. However, as the company requested, it only serves the customer within 1,000 miles limit.

Figure 2.5 the value of outbound warehouse(s) in terms of the

allowable shipping miles v.s. normalized total shipping cost.

Based on the solution mentioned above, company found it is worth to expand the Chatsworth warehouse as outbound warehouse and factory warehouse simultaneously, and decided to do so. After this expansion completed, customers are sent products from two warehouses and the total shipping costs reduced approximately \$1 million annually. Moreover, the averaged delivery time to customer decreased from four to six days to two days.

To sum up, the LP model have given a thorough insight to the company's manager, supported their decisions making and choose a proper combination of warehouse as outbound warehouses, to minimise the shipping distances, to improve its customer responsiveness, and to reduce markedly in spending.

2.5 Shortcoming and limitations of the model

There are several disadvantages regarding to this model:

Is extremely time-consuming to obtain solutions. This problem is a large-scale spread-sheet model; it is always likely to take longer time to process. This workload may also cause may cause Excel crashes during the solution process if a computer is not sufficiently powerful.

Is complicated and difficult to identify, reformulate and modify if there needs to making additional changes for specific cells. Since the model contains a great number of complex formulae and equations. With manual modifications, such as copy and paste operation, replace might lead errors occur easily.

Lack of flexibility of the expansion for the model. As the characteristic of spread-sheet, there are limited columns and rows, its capabilities of handling and inputting data are limited. In addition, Excel is limited in using rectangular range, having maximum up to 256 columns.

As the change of customer demands, the LP model will need to constantly modify in order to ensure to obtain accurate solutions. Therefore, it may not be appropriate to adopt this model if a company is in a rapid change industry.

## 3.0 Assignment Problem

3.1 Introduction

The head of research and development(R&D) in Ampshire, which is a pharmaceutical manufacturing company, will need to assist the project director for each project, there are five senior scientist (Dr. Jvaal, Dr. Zuner, Dr. Tsai, Dr. Mickey, Dr. Rollins) , and the following list is the five tasks which the R&D department has to handle.

Project name: Project Description

Project Up: Develop a more effective antidepressant that does not cause serious mood swings

Project Stable: Develop a drug that addresses manic-depression

Project Choice: Develop a less intrusive birth control method for women

Project Hope: Develop a vaccine to prevent HIV infection

Project Release: Develop a more effective drug to lower blood pressure

In order to be better assign the project, a bidding system was employed which ask the scientists to bid to each task considering their preferences. Table below shows the bid points of each scientist with the corresponding tasks.

Table 3.1 The bidding results

The purpose of this problem are (3.2.1) to allocate one of scientists to be responsible for one of five tasks whilst maximize their preference; (3.2.3.1) to identify which project should be give up if Dr. Rollins left, and the rule remains the same- each assignee only perform exactly one project, and some project will not be done; (3.2.3.2) to reallocate the assignment of the projects since either Dr. Zuner or Dr. Mickey can be assigned to perform more than one project simultaneously; (3.2.3.3) to reallocate the assignment of the projects since either Dr. Zuner or Dr. Mickey can be assigned to perform more than one project simultaneously and Dr. Zuner wish to update her bid points for each projects; (3.2.3.4) to reallocate the assignment of the projects with certain projects cannot be performed by several of five assignees them; (3.2.3.5) to reallocate the assignment of the projects since involving two more assignees, and the projects hope and release can be performed jointly by at most two assignees.

3.2 Analysis Process

3.2.1 Formulation

The problem is an assignment problem model.

## Objective Function:

The objective of this problem is to maximise the scientists' preferences by considering their bid points. Let Z be total bid points, the objective function is:

The first constrain indicates that each scientist is to lead exactly on project, whereas the second set indicate that each project to be leaded by exactly on scientist.

3.2.2 Solution

The Excel Solver is used to solve this assignment problem. The follow figure shows a spreadsheet model for this problem.

Figure 3.1 A spreadsheet model for this assignment problem.

Table 3.1 is placed at the top. And the number of assignees is equal to the number of projects. The objective is to determine which project should be assign to the appropriate scientist with maximising their preferences or total bid points which show in Cell C13. And the value of cell B17: F21 show the optimal allocation obtained from the excel solver for assigning the scientist to the projects.

The value of 1 in Supply (G5 : G9 or I17 : I21) represent that each scientist showed in column A must perform exactly one project. And the values of 1 in Demand (B10: F10 or B 24 : F24) represent that each project must be performed y exactly one scientist. These constraints can set in the Solver dialogue box.

Figure 3.2 Beginning the Excel solver parameters setup

After setting up the parameters and constraints and clicking on the Solve button, the optimal solution is obtained and illustrated as following:

Figure 3.3 the optimal solution obtained for this assignment problem

## 3.2.3 Interpretation

The optimal solution of this problem is to: assign Dr Tsai to complete "Project UP"; assign Dr. Kvaal to do "Project Stable"; assign Dr. Zuner to handle "Project Choice"; assign Dr. Mickey to perform "Project Hope"; assign Dr. Rollins to lead "Project Release". And the total bid points given in the Cell C13 is 2551.

## 3.2.4.1 Assignee < Project (each assignee only perform exactly one project, and some project will not be done)

Now suppose that Dr. Rollin is leaving, there are only four scientists available. Therefore introducing a dummy assignee is needed in order to solve this revised problem. And as the dummy assignee will not take part in any project, therefore, it is necessary to set the bid point of that dummy scientist as -1.

Figure 3.4 A spreadsheet model for this revised assignment problem.

After that, setting the solver parameters and clicking on solve, the new solution is illustrated.

Figure 3.5 The optimal solution obtained for this revised assignment problem.

Therefore, as the figure 3.5 illustrated, the "Project Up" should be given up.

## 3.2.4.2 Assignee < Project (certain assignee can be assigned to perform more than one project simultaneously)

Due to that fact that sacrificing any project is not acceptable and there are only four scientists available, either Dr. Zuner or Dr. Mickey has to lead two projects at the same time. Therefore, the spreadsheet model has to be revised. Firstly, double those two assignees into the problem, namely Dr. Zuner (1), Dr. Zuner (2), Dr. Mickey (1), Dr. Mickey (2). In order to solve this problem, the dummy task should be added because of the equal rule for the number of assignees and projects. After this, giving a large negative number to Dr. Kvaal nor Dr. Tsai ensure null of them will can get the dummy project while setting the bid point of that dummy project as -1 in those assignees Dr. Zuner (1), Dr. Zuner (2), Dr. Mickey (1), Dr. Mickey (2).

Figure 3.6 A spreadsheet model for this revised assignment problem.

After that, setting the solver parameters and clicking on solve, the new solution is illustrated.

Figure 3.7 The optimal solution obtained for this revised assignment problem.

Therefore, as the figure 3.7 illustrated, the solution is to assign Dr. Kvaal to lead "Project Stable"; assign Dr. Zuner to lead "Project Choice"; assign Dr. Tsai to handle "Project Release"; assign Dr. Mickey to perform "Project Up" and "Project Hope".

## 3.2.4.3 Assignee < Project (certain assignee can be assigned to perform more than one project simultaneously with updating bid points)

As Dr. Zuner decided to update her bids for the project (Project Up: 20; Project Stable: 450; Project Choice: 451; Project Hope: 39; Project Release: 40), the model has to be revised.

Figure 3.8 A spreadsheet model for this revised assignment problem.

After that, setting the solver parameters and clicking on solve, the new solution is illustrated.

Figure 3.9 The optimal solution obtained for this revised assignment problem.

As the figure 3.9 illustrated, the solution is to assign Dr. Kvaal to lead "Project Stable"; assign Dr. Zuner to lead "Project Choice"; assign Dr. Tsai to handle "Project Release"; assign Dr. Mickey to perform "Project Up" and "Project Hope". Although Dr. Zuner gave new bids, there is no difference of the assignment' result illustrated in 3.2.4.2.

## 3.2.4.4 Assignee = Project (Certain assignees are unable to perform certain projects)

Consider all of five scientists again, however, certain scientists are unable to perform certain projects. According the new bids of Dr. Mickey, Dr. Kvaal, and Dr. Rollins, revised the model. For the projects are unable to perform for certain scientist, a large negative number is used as the bid point.

Figure 3.10 A spreadsheet model for this revised assignment problem.

After that, setting the solver parameters and clicking on solve, the new solution is illustrated.

Figure 3.11 The optimal solution obtained for this revised assignment problem.

As the figure 3.11 illustrated, the solution is to assign Dr. Kvaal to lead "Project Stable"; assign Dr. Zuner to lead "Project Choice"; assign Dr. Tsai to handle "Project Release"; assign Dr. Mickey to perform "Project Up"; assign Dr. Rollins to do "Project Hope".

## 3.2.4.5 Assignee > Project (Each projects can be performed jointly by at most two assignees)

As hiring two more scientists, and the projects hope and release can be handled by at most two assignees, the model has to be revised as following. Therefore, the projects hope and release need to be duplicate, namely, Project Hope (1), Project Hope (2), Project Release (1), Project Release(2). Furthermore, as both new scientists can be leaded project Choice, therefore, a large negative number is used instead of assigning 0 bid points.

Figure 3.12 A spreadsheet model for this revised assignment problem.

After that, setting the solver parameters and clicking on solve, the new solution is illustrated.

Figure 3.13 T he optimal solution obtained for this revised assignment problem.

As the figure 3.11 illustrated, the solution is to assign Dr. Kvaal to lead "Project Stable"; assign Dr. Zuner to lead "Project Choice"; assign Dr. Tsai to handle "Project Release"; assign Dr. Mickey to perform "Project Up"; assign Dr. Rollins to do "Project Release"; assign Dr. Arriaga to perform "Project Hope"; assign Dr. Santos to do "Project Hope".

3.3 Conclusion and Recommendation

There are six examples are presented above to illustrate the different situations. Due to the assumptions of the problem are changed, reformulating the model to make it fit the format for all the assumptions of the problem. We can simply change the spreadsheet model directly and solve it by using the excel solver. However, sometimes it is necessary to do some adjustment before solving it, such as: introduce "some dummy elements" or "duplicate the assignees or projects" in order to make the equal number of assignees and projects; or set a large negative number as a bid point for those projects can be handled to avoid the chance to assign the project to corresponding assignee.