Linear Programming - Elements of Operation research, Business Mathematics and Statistics | Business Mathematics and Statistics - B Com PDF Download

Operations Research (OR) means a scientific approach to decision making, which seeks to determine how to optimally design and operate a system, usually under conditions requiring the allocation of scarce resources.

An OR study has the following major phases:

I. Define the problem and gather relevant data. ⇒

II. Formulate a mathematical model to represent the problem ⇒

III. Develop a procedure for deriving a solution to the problem ⇒

IV. Test the model and refine it as needed ⇒

V. Implement

Some of these phases will be illustrated the following example.

Prototype Example :

I. The GW firm manufactures two types of products W₁ and W₂ using two types of raw materials S₁ and S₂. The GW firm wishes to determine how many products of each type to produce, so as to achieve the highest possible profit.

II. The following data are available:

– 1 unit of W₁ requires 2 kg of S₁ and 1 kg of S₂.

– 1 unit of W₂ requires 1 kg of S₁ and 1 kg of S₂.

– At present, GW has 100 kg of S₁ and 80 kg of S₂ in stock.

– Each unit of W₁ gives a profit of $3 and each unit of W₂ gives a profit of $2.

– Demand for W₁ equals 40 units and demand for W₂ is unlimited.

III. We define the decision variables: x₁ - amount of product W₁ produced, x₂ amount of product W₂ produced, Z - total profit from producing W₁ and W₂.

The mathematical model is as follows:

max Z = 3x₁ + 2x₂           [Maximize profit]

2x₁ + x₂ ≤ 100               [Constraint on raw material S₁]

x₁ + x₂ ≤ 80                   [Constraint on raw material S₂]

x₁ ≤ 40                           [Demand for W1]

x₁ ≥ 0                             [Sign restriction]

x₂ ≥ 0                             [Sign restriction]

The problem is to choose values of x₁ and x₂, so as to maximize Z = 3x₁ + 2x₂ subject to the restrictions. We want to derive a production plan that maximizes GW’s profit without violating the constraints on limited resources.

IV. We use an algorithm (the next part of the course will focus on the simplex method for solving linear programming problems). We obtain: x₁ = 20, x₂ = 60, Z = 180, so GW should produce 20 units of W₁ and 60 units of W₂ with a resulting total profit of $180.

THE LINEAR PROGRAMMING MODEL

The mathematical model for a general mathematical programming problem is as follows:

max(min)z = f(x₁,...,xn)             [Objective function]

g₁(x₁,...,xn) ≤ (≥, =)b₁                   [Constraint 1]

...

gm(x₁,...,xn) ≤ (≥, =)bm            [Constraint m]

x₁,...,xn are called decision variables (They should completely describe the decision to be made). A solution for which all the constraints are satisfied is called a feasible solution. A feasible solution with the largest (smallest) value of the objective function is called an optimal solution.

The function h(x₁,...,xn) = a₁x₁+a₂x₂+ˇˇˇ+anxn of x₁,x₂,...,xn is a linear function.

A model in which all the functions f,g₁,...,gm are linear is called a linear model or a linear programming problem. A linear programming model(LPM) is defined as follows:

max(min)z = c₁x₁ + c₂x₂ + ˇˇˇ + cnxn [Objective function]

a₁₁x₁ + a₁₂x₂ + ˇˇˇ + a₁nxn ≤ (≥, =)b₁ [Constraint 1]

...

am₁x₁ + am₂x₂ + ˇˇˇ + amnxn ≤ (≥, =)bm [Constraint m]

x₁ ≥ 0,...,xr ≥ 0, r ≤ n [Nonnegativity constraints]

The sign constraints xi ≥ 0 are special linear constraints (nonnegativity constraints).

EXAMPLES OF LINEAR PROGRAMMING

PROBLEMS

1. The Diet Problem. Person X requires that all the food she/he eats come from one of the four ”basic food groups”: butter, bread, orange juice and ham. She/he wants to prepare breakfast only from these foods. Each scoop of butter costs$5, each slice (piece) of bread costs$2, each bottle of orange juice

 EXAMPLES OF LINEAR PROGRAMMING PROBLEMS

costs $3, and each piece (slice) of ham costs $8. Each day X must ingest at least 500 calories, 6 oz of sugar, 10 oz of carbohydrates, and 8 oz of fat. The nutritional content per unit of each food is shown in the following table:

Formulate a linear programming model that satisfies the daily nutritional requirements of person X at minimum cost.

Decision variables:

x₁ - amount(number of scoops) of butter,

x₂ - amount(number of pieces) of bread,

x₃ - number of bottles of orange juice,

x₄ - amount (number of slices) of ham.

Linear Programming Model:

min Z = 5x₁ + 2x₂ + 3x₃ + 8x₄                      [Minimize total cost]

400x₁ + 200x₂ + 150x₃ + 500x₄ ≥ 500      [Calorie constraint]

3x₁ + 2x₂ ≥ 6                                             [Sugar constraint]

2x₁ + 2x₂ + 4x₃ + 4x₄ ≥ 10                        [Carbohydrates constraint]

2x₁ + 4x₂ + x₃ + 5x₄ ≥ 8                             [Fat constraint]

xi ≥ 0, i = 1,..., 4                                         [Sign constraint]

The optimal solution to this problem (solved by computer) is x₁ = 0, x₂ = 3, x₃ = 1, x₄ = 0, Z = 9. Thus, the minimum-cost diet incurs a cost of $9 and consists of 3 pieces of bread and one bottle of orange juice.

2. Production Process Model ( W.L. Winston Operations Research: Applications and Algorithms, Example 3.11, pp.87-90) Rylon Corporation manufactures four types of perfumes: Brute, Chanelle, Super Brute and Super Chanelle.

The production process is given in the Figure below.

• Processing 1 lb of raw material requires 1 hour of working time and gives 3 oz of Brute and 4 oz of Chanelle.

• 1 oz of Brute requires an additional 3 hours of processing to yield 1 oz of Super Brute.

• 1 oz of Chanelle requires an additional 2 hours of processing to yield 1 oz of Super Chanelle

•  Rylon has 6000 hours of time available and can purchase up to 4000 lb of raw material.

R.C must determine how much material to purchase and how much of each type of perfume should be produced and wants to maximize profit(=revenues from perfume sales - processing costs).

Decision variables:

• x₁ - number of ounces of Brute sold,

• x₂ - number of ounces of Super Brute sold,

• x₃ - number of ounces of Chanelle sold,

• x₄ - number of ounces of Super Chanelle sold,

• x₅ - number of pounds(lb) of raw material purchased.

Linear Programming Model:

max z = 7x₁ + 14x₂ + 6x₃ + 10x₄ − 3x₅         [Maximize profit]

x₁ + x₂ − 3x₅ = 0                                             [Manufacturing Brute and Super Brute]

x₃ + x₄ − 4x₅ = 0                                             [Manufacturing Chanelle and Super Chanelle]

x₅ ≤ 4000                                                         [Limit on raw materials]

3x₂ + 2x₄ + x₅ ≤ 6000                                      [Limit on working time]

xi ≥ 0, i = 1,..., 5                                                [Sign restrictions]

After solving the model by computer we obtain the following optimal solution:

Z=172 666.667$ (profit), x₁ = 11333.333 oz of Brute, x₂ = 666.667 oz of Super Brute, x₃ = 16000 oz of Chanelle, x₄ = 0 oz of Super Chanelle and x₅ = 4000lb of raw material.

3. An Inventory Model - Multiperiod Decision problems. A factory must produce a certain product over the next four quarters. The demand for each quarter is known. The factory wants to minimize total costs and has to meet all demands on time. The appropriate data are given in the following table

Decision variables:

• x_i - number of units produced during quarter i, i = 1,... 4.

• m_i - number of units of the product in store (on the inventory) at the end of quarter i, i = 1,... 4

Linear Programming Model:

min z = 55x₁ + 50x₂ + 50x₃ + 55x₄ + 2m₁ + 2m₂ + 3m₃      [Minimum total cost]

x₁ − m₁ = 30                                                                        [Balance for I]

m₁ + x₂ − m₂ = 60                                                                [Balance for II]

m₂ + x₃ − m₃ = 70                                                              [Balance for III ]

m₃ + x₄ = 25                                                                        [Balance for IV]

x_i ≤ 60, i = 1,... 4                                                                  [Production capacity]

x_i ≥ 0, m_i ≥ 0, i = 1,..., 4                                                       [Sign restrictions]

The optimal solution to this problem is Z = 9615: x₁ = 40, x₂ = 60, x₃ = 60, x₄ = 25, m₁ = 10, m₂ = 10, m₃ = 0.

4. Multiperiod Financial Model. (W.L. Winston Operations Research: Appli cations and Algorithms, Example 3.13, pp.95-97) Finco Invest. Corp. must determine an investment strategy for the next three years. At present (time 0), $100000 is available for investment. Investments A,B,C,D and E are available. The cash flow associated with investing $1 in each investment is given in the table below

For example, $1 invested in B requires $1 in cash at time 1 and returns $0.5 at time 2 and $1 at time 3. To ensure that the company’s portfolio is diversified, Finco requires that at most $75000 be placed in any single investment. In addition, Finco can earn interest at 8% per year by keeping uninvested cash in a bank. Returns from investments may be immediately reinvested. Formulate a linear programming problem whose solution will maximize the amount of cash in hand at time 3. Finco must decide how much money should be placed in each investment(including the bank).

Decision variables:

• x_A,x_B,x_C ,x_D,x_E - dollars invested in investment A,B,C,D, and E respectively,

• y₀,y₁,y₂ - dollars invested in the bank at time t (t=0,1,2).

The linear programming model:

max z = x_B + 1.9xD + 1.5x_E + 1.08y₂           [Maximize the amount of cash in hand at time 3]

x_A + x_C + x_D + y₀ = 100000                          [Balance at time 0]

0.5x_A + 1.2x_C + 1.08y₀ − x_B − y₁ = 0           [Balance at time 1]

x_A + 0.5x_B + 1.08y₁ − x_E − y₂ = 0                 [Balance at time 2]

x_A,x_B,x_C ,x_D,x_E ≤ 75000                               [Limit on dollars invested in investments]

x_A,...,x_E,y₀,y₁,y₂ ≥ 0                                     [Nonnegativity constraints]

The optimal solution is Z = 218500, x_A = 60000, x_B = 30000, x_D = 40000 , x_E = 75000, x_C = y₀ = y₁ = y₂ = 0. Finco should not invest in C nor in the bank.