​

Transportation and Game theory

(BMG6SEC42)

INTRODUCTION

• It is an optimization method applicable for the solution of optimization problem where objective function and the constraints are linear.
• It was first applied in 1930 by economist, mainly in solving resource allocation problem During World War II, the US Air force sought more effective procedure for allocation of resources George B. Dantzig, a member of the US Air Force formulate general linear problem for solving the resources allocation problem.

“A Linear Programming Problem is one that is concerned with finding the optimal value (maximum or minimum value) of a linear function (called objective function) of several variables (say x and y), subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints). The term linear implies that all the mathematical relations used in the problem are linear relations while the term programming refers to the method of determining a particular programme or plan of action.”

Problem: All products manufactured are shipped out of the storage area at the end of the day. Therefore, the two products must share the total raw material, storage space, and production time. The company wants to determine how many units of each product to produce per day to maximize its total income.

Solution

• The company has decided that it wants to maximize its sale income, which depends on the number of units of product I and II that it produces.
• Therefore, the decision variables, x1 and x2 can be the number of units of products I and II, respectively, produced per day.

BCN67755

Decision and Risk Analysis

Syed M. Ahmed, Ph.D.

• The object is to maximize the equation:

Z = 13x₁ + 11x₂

subject to the constraints on storage space, raw materials, and

production time.

​

​

• Each unit of product I requires 4 ft² of storage space and each unit of product II requires 5 ft². Thus a total of 4x₁ + 5x₂ ft² of storage space is needed each day. This space must be less than or equal to the available storage space, which is 1500 ft². Therefore,

4X₁ + 5X₂ ≤ 1500

• Similarly, each unit of product I and II produced requires 5 and 3 1bs, respectively, of raw material. Hence a total of 5x_l + 3x₂ Ib of raw material is used.

BCN67755

Decision and Risk Analysis

Syed M. Ahmed, Ph.D.

• This must be less than or equal to the total amount of raw material

available, which is 1575 Ib. Therefore,

5x₁ + 3x₂ ≤ 1575

• Prouct I can be produced at the rate of 60 units per hour. Therefore, it must take I minute or 1/60 of an hour to produce I unit. Similarly, it requires 1/30 of an hour to produce 1 unit of product II. Hence a total of x₁/60 + x₂/30 hours is required for the daily production. This quantity must be less than or equal to the total production time available each day. Therefore,

x₁ / 60 + x₂ / 30 ≤ 7 or x₁ + 2x₂ ≤ 420

• Finally, the company cannot produce a negative quantity of any

product, therefore x₁ and x₂ must each be greater than or equal to zero.

BCN67755

Decision and Risk Analysis

Syed M. Ahmed, Ph.D.

• The linear programming model for this example can be summarized as:

…..Eq (4)

Graphical Solution to LP Problems

Complications in Simplex Method

BCN67755

Decision and Risk Analysis

Syed M. Ahmed, Ph.D.

Example: Greater- Than-Or-Equal- To Constraints

• To start the solution, slack variables must first be assigned to convert all in-equalities to equalities. Let S₁ and S₂ be slack variables.
• Re- arrange the objective function so that all the variables are on

the left-hand side of the equation.

…….Eq. (1)

Complications in Simplex Method

• The negative signs for S₁ and S₂ make it no longer feasible to set all the decision variables (i.e., y₁, y₂, y₃) equal to zero as the initial solution.
• To assure a starting feasible solution, artificial variables can be added to the greater-than-or-equal-to constraints. Let W₁ and W₂ be two artificial variables. Hence the Eq. (2) becomes:

…….Eq. (3)

BCN67755

Decision and Risk Analysis

Syed M. Ahmed, Ph.D.

…….Eq. (2)

Complications in Simplex Method

BCN67755

Decision and Risk Analysis Syed M. Ahmed, Ph.D.

• A starting feasible solution can be easily derived from Eq. (3) as follows:

​

• The objective function in Eq. (3) then becomes:

​

…….Eq. (4)

• From Eq. (3):

• The coefficients and constants in Eq. (5) can now be arranged in the Tableau format as shown in next slide.

• Substituting these expressions in Eq. (4) yields the following new expression for the objective function:

​

• The objective function may now be combined with Eq. (3) to express the problem model as follows:

Complications in Simplex Method

Duality of LPP

• With every linear programming problem, there is associated another linear programming problem which is called the dual of the original (or the primal) problem.

Formulating the Dual problem

​

• Consider again the production mix problem of N. Dustrious Company.
• Suppose that the company is considering leasing out the entire production facility to another company, and it must decide on the minimum daily rental price that will be acceptable.
• This decision problem can also be formulated as a linear

programming problem.

Example on Dual LPP

• The primal problem can now take the following standard form:

• The dual of this problem can now be obtained as follows:

Thank you