Exercises Linear Programming Applications for PDF

Preview

Summary

thés ils a course for revercha opérationnel resache for show Wyant to resécha for application pour toute personne qui veut...

Description

EXERCISES Linear Programming Applications Exercise 1: Production Planning – Product Composition A production facility manufactures 5 types of products (1, 2, 3, 4, 5) using two basic processes (lathe and drilling operations). Processing times of the products and company profitability per unit of each product are displayed in the following table.

1

2

3

4

5

Lathe (minutes/unit)

12

20

-

25

15

Drill (minutes/unit)

10

8

16

-

-

Profit ($/unit)

55

60

35

40

20

Furthermore, each unit manufactured needs 20 man-minutes of assembly work. There are 3 lathe and 2 drilling machines in the facility. The lathe and drilling departments are active 6 days per week and both work on two 8-hour shifts. The assembly line employs 8 workers on a single 6-day, 8-hour shift. The production manager wants to determine a weekly production plan that maximizes the total profit.

Write the linear programming model of this problem (definitions of the decision variables, expressions of the objective function and the constraints).

1

Exercise 2: Currency Exchange Planning

An international company has operations in USA, United Kingdom, France, Germany and Japan. The company has daily varying needs and surpluses for cash in these countries’ currencies and, accordingly, needs to do large scale currency exchanges and cash transfers very frequently. The decision of which surplus currencies to exchange for which demanded currencies, is a frequently faced decision that needs a fast answer and in aggregate, considerably effects overall profitability.

On a specific day, French operations have 8 million Franc and Japanese operations have 1280 million yen urgent cash need; while, USA operations have $2 million, British operations have £5 million and German operation have 3 million mark cash surplus. Exchange rates faced by the company between all currency pairs are as follows:

1. Dollar 2. Pound

3. Franc

4. Mark

5. Yen

1. Dollar ($)

1.00000

0.69980

8.07800

2.62700

224.700

2. Pound (£)

1.42500

1.00000

11.55000 3.75400

320.700

3. Franc (FF)

0.12340

0.08647

1.00000

0.32500

27.760

4. Mark (DM)

0.37930

0.26620

3.07300

1.00000

85.510

5. Yen (¥)

0.00443

0.00310

0.03586

0.01163

1.00000

According to the above table, it is possible to buy £0.69980 or 2.62700 DM with $1; while £1 buys $1.425, and 1 DM buys $0.37930. In other words, there is a natural commission and buy/sell loss between buying and selling prices of each currency (while $1 buys £0.69980, £0.69980 buys only 0.69980 × 1.425 = $0.99722). The levels of these commissions and price differentials however, change from one currency pair to another.

Given this information, the problem of which currency needs to satisfy by which currency surpluses, and which currency transactions to undertake, in a way to maximize total remaining assets can be modeled and solved through linear programming. Write the linear programming model of this problem (definitions of the decision variables, expressions of the objective function and the constraints).

2

Exercise 3:

Brazil Fund Inc., a Brazilian investment company, has 2 million United States Dollars ($), 5 million Euro (€), 4 million United Kingdom Pounds (£), and an urgent cash need of 5 million Brazilian Real (R$). The table below provides the spot exchange rates between these currencies.

$

€

£

R$

$

1

0.819

0.701

1.870

€

1.221

1

0.855

2.282

£

1.427

1.169

1

2.671

R$

0.535

0.438

0.374

1

According to the table, $1 buys for example 0.819 €, while 1 € buys $1.221. The company wants to convert its cash surpluses to a combination of Dollars, Euro, Pounds, and Real. In the final mix, the Dollar holdings must be at least 60% of the total Euro and Pound holdings valued in terms of Dollars. Moreover, the final mix cannot contain more than 2 million Euro and 3 million Pounds. Write the linear programming model of this problem that would maximize the overall final holdings valued in terms of Brazilian Real (Give the definitions of the decision variables, the expressions of the objective function and the constraints using the given numerical values).

3

Exercise 4: Personnel Scheduling

A large supermarket desires to vary its number of operational point of sales (POS) during the day in order to match the varying customer demand. Studies undertaken have shown that the desirable number of POS at each hourly period of the day is as follows:

Time interval

Number of POS Time interval Number of POS

09:00 – 10:00

4

15:00 – 16:00

8

10:00 – 11:00

8

16:00 – 17:00

8

11:00 – 12:00

10

17:00 – 18:00

10

12:00 – 13:00

12

18:00 – 19:00

14

13:00 – 14:00

14

19:00 – 20:00

14

14:00 – 15:00

8

20:00 – 21:00

10

The supermarket has 12 full-time (F) cashiers and the management may ask each cashier to work either the 09:00-17:00 or the 13:00-21:00 shift. Each cashier on the 09:00-17:00 shift has one hour lunch break between 12:00-14:00 and gets a daily gross salary of $30. Half of the full-time cashiers that work in the 09:00-17:00 shift are allowed to take their lunch break between 12:00-13:00, and the other half between 13:00-14:00. The cashiers on the 13:00-21:00 shift do not have a lunch break but they get a daily gross salary of $35. In addition to the full-time personnel, the supermarket management has the option of employing part-time cashiers. Each part-time cashier works 4 straight hours per day and may be asked to start at the beginning of any hour (9:00 being the earliest start time and 17:00 being the latest start time). Part-time cashiers do not have lunch breaks and they get a daily gross salary of $20.

The number of full-time cashiers employed cannot exceed 12, but may be reduced, if desired. However, because of quality and customer satisfaction considerations, the supermarket management would like to meet at most two thirds of its daily cashier-hour needs through part-time personnel.

Under the above stated conditions, the supermarket’s cashier schedule, number and shifts of full-time and part-time cashiers to be employed, in a way to minimize personnel costs may be determined through linear programming. Write the linear programming model of this problem.

4

Exercise 5:

A large department store operates 7 days a week. The manager estimates that the minimum number of salespersons required to provide prompt service is 12 for Monday, 18 for Tuesday, 20 for Wednesday, 28 for Thursday, 32 for Friday, 40 for Saturday, and 40 for Sunday. Each salesperson works 5 days a week, with the two consecutive off-days staggered throughout the week. For example, if 14 salespersons are contracted, 3 can take their off-days on Monday and Tuesday, 2 on Tuesday and Wednesday, 4 on Wednesday and Thursday, 1 on Thursday and Friday, 1 on Friday and Saturday, 2 on Saturday and Sunday, and 1 on Sunday and Monday. Write the linear programming model of this problem that would determine the minimum number of salespersons to be contracted and the way that their off-days should be allocated (Give the definitions of the decision variables, the expressions of the objective function and the constraints using the given numerical values).

Exercise 6:

In most Belgian university campuses, students are contracted by academic departments to assist firstyear bachelors-degree exercise sessions. The need for such service fluctuates during work hours (8:00 A.M. to 5:00 P.M). In one department, the minimum number of students needed is 2 between 8:00 A.M. and 10:00 A.M., 3 between 10:01 A.M. and 11:00 A.M., 4 between 11:01 A.M. and 1:00 P.M., and 3 between 1:01 P.M. and 5:00 P.M. Each student works for 3 consecutive hours (except for those starting at 3:01 P.M. who work for 2 hours, and those who start at 4:01 P.M. who work for 1 hour). Because of their flexible schedule, students can usually start at any hour during the workday, except at lunchtime (12:01 noon). However, there are only 2 students that are available to start to work at 2:01 P.M. A student is paid 24 € if he works for 3 consecutive hours, 18 € if he works for 2 consecutive hours and, 10 € if he works just for one hour. Moreover, each student that works during the lunchtime (between 12:01 P.M. and 1:00 P.M.) gains an additional

2 €.

Write the linear programming model of this problem that would determine a time schedule specifying the time of the day and the number of students reporting to work (Give the definitions of the decision variables, the expressions of the objective function and the constraints using the given numerical values).

5

Exercise 7: Cash Flow Planning

A textile manufacturer has to plan its cash flow for the coming winter season. It is known that preseason stocking would require large cash outflows during the September-November period, while in season sales usually lead to large cash inflows in the December-January period. Expected cash flows are displayed in the following table (in units of $1,000).

1. Aug. 2. Sept. 3. Oct. 4. Nov. 5. Dec.

6. Jan.

Notes Receivable

700

500

700

1,000

1,200

500

Purchasing (cash payments)

800

1,000

1,000

600

400

400

300

600

900 300

1500

Cash Needs of Com. Activities Cash Surplus of Com. Activities

200

Three borrowing tools may be employed in meeting short term cash needs:

a.

Open credit account with notes receivable as collateral: Through this method, the company may borrow from its bank, up to 75% of the coming month’s notes receivable total, by showing those notes receivable as collateral. The duration of the loan is one month and its interest rate is 1.5% per month.

b. Delayed payment (one month) in purchase of goods: Through this method, the company may pay the full cost of merchandise purchased in one month, the next month. However, in this case, they will lose the 3% price reduction associated with cash payments. c.

Six month, fixed term credit with company general assets as collateral: Through this method, the company may borrow from its bank, up to $800,000, by showing its general assets as collateral. The duration of this loan is fixed at six months and its interest rate is 1% per month. However, it can only be applied for and obtained at the beginning of August to be repaid at the beginning of February; it cannot be increased or decreased during the planning period.

Each month, the company may invest its short term cash surplus, generated during the month, in government bonds, which have an interest rate of 0.5% per month and may be cashed in anytime. Assume that all monetary transactions (such as getting credit, payment for purchases, payment of interest, surplus of or need for cash in commercial activities, investment in government bonds) associated with any month occur at the beginning of the month. Write the linear programming model of this problem, which will maximize end of period assets.

6

Exercise 8:

Investor Doe has $10,000 to invest in four projects. The following table gives the cash flow for the four investments.

Cash flow at the start of Project

Year 1

Year 2

Year 3

Year 4

Year 5

1

-1

0.5

0.3

1.8

1.2

2

-1

0.6

0.2

1.5

1.3

3

0

-1

0.8

1.9

0.8

4

-1

0.4

0.6

1.8

0.95

The information in the table can be interpreted as follows: For project 1, $1 invested at the start of year 1 will yield $0.5 at the start of year 2, $0.3 at the start of year 3, $1.8 at the start of year 4, and $1.2 at the start of year 5. The remaining entries can be interpreted similarly. The entry 0 indicates that no transaction is taking place. Doe has the additional option of investing in a bank account that earns 6.5% annually. All the funds accumulated at the end of one year can be reinvested in the following year. Write the linear programming model of this problem that would determine the optimal allocation of funds to investment opportunities in a way to maximize the funds at the end of year 4 (Give the definitions of the decision variables, the expressions of the objective function and the constraints using the given numerical values).

7

Exercise 9: Advertising Planning

A large food manufacturer is planning an advertising campaign for a new product being prepared for marketing. The company’s expectation is to increase sales through this campaign. They want to reach to the maximum possible number of potential customers while keeping the overall campaign within a predetermined budget of $50,000. The company’s advertising agency has suggested the employment of two TV Channels, two daily newspapers, two weekly magazines and one radio station during this campaign. It has also emphasized the additional importance of reaching high income potential customers.

The research department of the advertising agency has carefully estimated the cost of each ad, the number of potential customers and the number of high income potential customers it will reach, as given in the following table. In TV ads, a 30-second spot is considered as one unit. Prime-time (PT) and non prime time (non PT) ads are treated separately, since they differ both in cost and in reachability. Following the suggestions of the agency, the company would like to reach at least 2,000,000 high income potential customers during this campaign. They would also like to spend at most $30,000 on TV ads, and at most $20,000 on printed media. Furthermore, the manager would like to give at least two ads to each TV Channel and each newspaper to keep up the good relations with these organizations. On the other hand, since the duration of the campaign is three weeks, there is time to place at most 3 ads in each of the magazines.

Media Type

Cost per Ad

# of Potential

# of High Income Potential

Customers Reached

Customers Reached

TV 1 (PT)

$ 3,000

5,000,000

75,000

TV 1 (non PT)

$ 2,000

3,000,000

60,000

TV 2 (PT)

$ 2,700

4,000,000

100,000

TV 2 (non PT)

$ 1,800

2,500,000

75,000

$ 500

400,000

24,000

Paper 1

$ 1,600

2,300,000

50,000

Paper 2

$ 1,200

1,300,000

49,000

Magazine 1

$ 750

500,000

60,000

Magazine 2

$ 700

600,000

55,000

Radio

Write the linear programming model of this problem.

8

Exercise 10: Transportation Planning

The firm TRN has two plants (Seattle, Saint Diego) that are serving three market areas (New York, Chicago, Topeka). The vice president of the firm knows the production capacity (in tons) of each plant and the expected demand (in tons) of each demand area:

Plant

Production capacity

Seattle

350

Saint Diego

600

Market

Demand

New York

325

Chicago

300

Topeka

275

The distances between the plants and the markets (in millions of miles) are as follows:

Distance

New York

Chicago

Topeka

Seattle

2.5

1.7

1.8

San Diego

2.5

1.8

1.4

The transportation cost of a ton for one million miles is $90. The vice president of TRN wants to know the distribution strategy that specifies the quantities to transport between the plants and the markets, and that minimizes the total transportation cost.

Write the linear programming model of this problem.

9

Exercise 11:

A company wants to determine its production plan that defines the quantity of material to be produced in each quarter of 2012, that satisfies the forecasted demand of each quarter, and that minimizes the related annual costs. The demand forecasts for these four quarters are as follows:

Quarter 1 2 3 4

Demand Forecast 180,000 400,000 190,000 390,000

Backorders are not allowed. It is known that an employee can produce 150 units per day. The number of working days for each quarter is given in the following table:

Quarter 1 2 3 4

Working Days 62 64 55 59

At the beginning of the first quarter, the company has 32 employees. The initial inventory level is zero. The cost of hiring an employee is 20,000 €. The cost of lay-off is 50,000 €. The inventory holding cost of a unit during a quarter is 10 €. We suppose that employees can be hired or laid off just at the beginning of each quarter. Moreover, for commercial reasons, the company wants to have a minimum inventory level at the end of each quarter:

Quarter 1 2 3 4

Minimum inventory level required 55,000 85,000 50,000 100,000

Write the linear programming model of this problem.

10

Exercise 12:

MarcVender is a company that produces two major components, A and B, and then assembles one component A with two components B in order to obtain one finished product P. Production capacities vary from month to month. The production capacities and the demand forecasts for the next three months are as follows:

Month

1 2 3

Production capacity for product A 140 90 130

Production capacity for product B 250 200 250

Production capacity for product P 60 100 150

Demand forecast for product P 70 90 170

MarcVender estimates that, after deducing the material and production costs, the gain from selling one unit of finished product in the market is 50 €. MarcVender has the option of not meeting all the demand of the finished pr...