MC0079-Spring Drive Assignment-2012

1. Explain the structure of Mathematical model in OR.

Ans

Many industrial and business situations are concerned with planning activities. In each case of planning, there are limited sources, such as men, machines, material and capital at the disposal of the planner. One has to take decision regarding these resources to either maximise production, or minimise the cost of production or maximise the profit. These problems are referred as the problems of constrained optimisation.

Linear programming is a technique for determining an optimal schedule of interdependent activities, for the given resources. Therefore, you can say that programming refers to planning and the process of decision-making about a particular plan of action from a given set of alternatives.

Any business activity or production activity to be formulated as a mathematical model can best be discussed through its parts which are as follows:

1. Decision variables

2. Objective function

3. Constraints

4. Diet problem

Decision variables

Decision variables are the unknowns, which you need to determine from the solution of the model. The parameters represent the controlled variables of the system.

Objective function

The objective function defines the measure of effectiveness of the system as a mathematical function of its decision variables. The optimal solution to the model is obtained when the corresponding values of the decision variable yield the best value of the objective function whilst satisfying all constraints. Therefore, you can say that the objective function acts as an indicator for the achievement of the optimal solution.

While formulating a problem, the desire of the decision-maker is expressed as a function of ‘n’ decision variables. This function is a linear programming problem that is each of its items will have only one variable raised to the power one). Some of the objective functions in practice are:

· Maximisation of contribution or profit

· Minimisation of cost

· Maximisation of production rate or minimisation of production time

· Minimisation of labour turnover

· Minimisation of overtime

· Maximisation of resource utilisation

· Minimisation of risk to environment or factory

Constraints

To account for the physical limitations of the system, you need to ensure that the model includes constraints, which limit the decision variables to their feasible range or permissible values. These are expressed as constraining mathematical functions.

For example, in chemical industries, restrictions come from the government about throwing gases in the environment. Restrictions from sales department about the marketability of some products are also treated as constraints. A linear programming problem then has a set of constraints in practice.

The mathematical models in OR may be viewed generally as determining the values of the decision variables x _J, J = 1, 2, 3, —— n, which will optimize Z = f (x ₁, x ₂, —- x _n).

Subject to the constraints:

g _i (x ₁, x ₂ —– x _n) ~ b _i, i = 1, 2, —- m

And x_J ³ 0 j = 1, 2, 3 —- n where ~ is £, ³ or =.

The function f is called the objective function, where x_j ~ b_i, represent the i^th constraint for i = 1, 2, 3 —- m where b _i is a known constant. The constraints x _j ³  0 are called the non-negativity condition, which restrict the variables to zero or positive values only.

Diet problem

Formulate the mathematical model for the following:

Vitamin – A and Vitamin – B are found in food –1 and food – 2.

One unit of food – 1 contains 5 units of vitamin – A and 2 units of vitamin–B.

One unit of food – 2 contains 6 units of vitamin – A and 3 units of vitamin–B.

The minimum daily requirement of a person is 60 units of vitamin – A and 80 units of Vitamin – B.

The cost per one unit of food – 1 is Rs. 5/- and one unit of food–2 is Rs. 6/-. Assume that any excess units of vitamins are not harmful. Find the minimum cost of the mixture (of food–1 and food–2) which meets the daily minimum requirements of vitamins.

Mathematical Model of the Diet Problem: Suppose x₁ = the number of units of food–1 in the mixture and x₂ = the number of units of food–2 in the mixture.

Let’s formulate the constraint related to vitamin-A. Since each unit of food–1 contains 5 units of vitamin– A, we have that x­₁ units of food–1 contains 5x₁ units of vitamin– A. Since each unit of food– 2 contains 6 units of vitamin–A, we have that x₂ units of food–2 contains 6x₂ units of vitamin–A. Therefore, the mixture contains 5x₁ + 6x₂ units of vitamin-A. Since the minimum requirement of vitamin– A is 60 units, you can say that 5x_­1 + 6x_­2 ³ 60.

Now let’s formulate the constraint related to vitamin–B. Since each unit of food–1 contains 2 units of vitamin–B we have that x₁ units of food–1 contains 2x₁ units of vitamin-B. Since each unit of food–2 contains 3 units of vitamin–B, we have that x₂ units of food–2 contains 3x₂ units of vitamin–B.

Therefore the mixture contains 2x₁ + 3x₂ units of vitamin–B. Since the minimum requirement of vitamin–B is 80 units, you can say that

2x₂ + 3x₂ ³ 80

Next let’s formulate the cost function. Given that the cost of one unit of food–1 is Rs. 5/- and one unit of food – 2 is Rs. 6/-. Therefore, x₁ units of food–1 costs Rs. 5x_1, and x₂ units of food – 2 costs Rs. 6x₂.

Therefore, the cost of the mixture is given by Cost = 5x₁ + 6x₂.

If we write z for the cost function, then you can write z = 5x₁ + 6x_2.

Since cost is to be minimised, you can write min z = 5x₁ + 6x_2.

Since the number of units (x₁ or x₂) are always non-negative, therefore, you have x₁ ³ 0, x₂ ³ 0.

Therefore, the mathematical model is:

5x₁ + 6x₂ ³ 60

2x₁ + 3x₂ ³ 80

x₁ ³ 0, x₂ ³ 0, min z = 5x₁ + 6x_2.

2. Explain briefly the graphical method of analyzing a linear programming problem. Can a LPP

have unbounded solution?

Ans:

Linear programming (LP) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear equations.

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Given a polytope and a real-valued affine function defined on this polytope, a linear programming method will find a point on the polytope where this function has the smallest (or largest) value if such point exists, by searching through the polytope vertices.

An Algorithm for solving a linear programming problem by Graphical Method:

(This algorithm can be applied only for problems with two variables).

Step – I:

Formulate the linear programming problem with two variables (if the given problem has more than two variables, then we cannot solve it by graphical method).

Step – II:

Consider a given inequality. Suppose it is in the form

a₁x₁+ a₂x₂ <= b (or a₁x₁ + a₂x₂ >= b). Then consider the relation a₁x₁+ a₂x₂= b. Find two distinct points (k, l), (c, d) that lie on the straight line a₁x₁+ a₂x₂= b. This can be found easily: If x₁= 0, then x₂ = b / a₂.

If x₂=0, then x₁ = b / a1. Therefore (k, l) = (0, b / a₂) and (c, d) = (b / a₁, 0) are two points on the straight line a₁x₁+a₂x₂= b.

Step – III:

Represent these two points (k, l), (c, d) on the graph which denotes X–Y-axis plane. Join these two points and extend this line to get the straight line which represents a₁x₁+ a₂x₂= b.

Step – IV:

a₁x₁ + a₂x₂= b divides the whole plane into two half planes, which are a₁x₁+ a₂x₂ <= b (one side) and a₁x₁+ a₂x₂ >= b (another side). Find the half plane that is related to the given inequality.

Step – V:

Do step-II to step-IV for all the inequalities given in the problem.

The intersection of the half-planes related to all the inequalities and x₁ >= 0,

x₂ >= 0 , is called the feasible region (or feasible solution space). Now find this feasible region.

Step – VI:

The feasible region is a multisided figure with corner points A, B,

C, … (say). Find the co-ordinates for all these corner points. These corner points are called as extreme points.

Step – VII:

Find the values of the objective function at all these corner/extreme points.

Step – VIII:

If the problem is a maximization (minimization) problem, then the maximum (minimum) value of z among the values of z at the corner/extreme points of the feasible region is the optimal value of z. If the optimal value exists at the corner/extreme point, say A (u, v), then we say that the solution x₁= u and x₂= v is an optimal feasible solution.

Step – IX:

Write the conclusion (that include the optimum value of z, and the co-ordinates of the corner point at which the optimum value of z exists).

Yes ,LPP can have unbounded solution. This is shown in given example

Example for Unbounded Solution:

Maximize Z = 2x₁+3x₂

Subject to

x₁ – x₂ ≤ 2

x₁ + x₂ ≥ 4

and x₁, x₂ ≥ 0

The intersection point A of the straight lines x₁ – x₂ = 2 and x₁+x₂ = 4 is A(3, 1). Here the

solution space is unbounded. The vertices of the feasible region are A(3, 1) and B (0, 4). Value of

objective at these vertices are

Z _atA(31) = 2 x 3+3 x1 = 9

Z _{at B(0, 4)} = 2x0+4x3 = 12.

But there are points in the convex region for which Z will have much higher values. For example E

(10, 9) lies in the shaded region and the value of Z there at 47. In fact, the maximum values of Z

occurs at infinity. Thus the problem has an unbounded solutions.

3. Apply simplex procedure to solve the L.P.P. maximize z = 3x₁ + 4x₂ subject to 5x₁ + 4x₂

≤ 200; 3x₁ + 5x₂ ≤ 150; 5x₁ + 4x₂ ≥ 100; 8x₁ + 4x₂ ≥ 80, x₁ ≥ 0, x₂ ≥ 0.

Ans.

4. Solve the following transportation problem 

 

Ans:

5. Explain Project Management (PERT).

Ans:

PERT :

Complex projects require a series of activities, some of which must be performed sequentially and others that can be performed in parallel with other activities. This collection of series and parallel tasks can be modeled as a network.In 1957 the Critical Path Method (CPM) was developed as a network model for project management. CPM is a deterministic method that uses a fixed time estimate for each activity. While CPM is easy to understand and use, it does not consider the time variations that can have a great impact on the completion time of a complex project.

The Program Evaluation and Review Technique (PERT) is a network model that allows for randomness in activity completion times. PERT was developed in the late 1950's for the U.S. Navy's Polaris project having thousands of contractors. It has the potential to reduce both the time and cost required to complete a project.

The Network Diagram

In a project, an activity is a task that must be performed and an event is a milestone marking the completion of one or more activities. Before an activity can begin, all of its predecessor activities must be completed. Project network models represent activities and milestones by arcs and nodes. PERT originally was an activity on arc network, in which the activities are represented on the lines and milestones on the nodes. Over time, some people began to use PERT as an activity on node network. For this discussion, we will use the original form of activity on arc.

The PERT chart may have multiple pages with many sub-tasks. The following is a very simple example of a PERT diagram:

The milestones generally are numbered so that the ending node of an activity has a higher number than the beginning node. Incrementing the numbers by 10 allows for new ones to be inserted without modifying the numbering of the entire diagram. The activities in the above diagram are labeled with letters along with the expected time required to complete the activity.

Steps in the PERT Planning Process

PERT planning involves the following steps:

Identify the specific activities and milestones.

Determine the proper sequence of the activities.

Construct a network diagram.

Estimate the time required for each activity.

Determine the critical path.

Update the PERT chart as the project progresses.

6. Explain the use of finite queuing tables .

Ans.

Use of finite queuing tables

The above table gives values of F and D for different values of N, M and X. They are arranged in the ascending order of the values of the population. For each N, the value of X increases from .001 to .950. For a given service factor X, several values of M can be found. For each value of X and M, values of D and F are tabulated. The steps for finite queuing tables are as follows:

i) Find mean service time T and mean running time U.

ii) Compute the service factor.

iii) Select the table corresponding to the population N.

iv) For the given population, locate the service factor value.

v) Read off from tables, values of D and F for the number of service crews M.

vi) If necessary, these values may be interpolated between relevant values of X.

vii) Calculate the other measures L, W, H, and J from the formulae given.