Subject: Quantitative Techniques

1. Define Linear Programming. What are the essential Characteristics required for a
linear programming model?
Ans: Linear Programming is considered an important technique which is used to find the
optimum resource utilization. The terminology “liner programming” has two words
“linear” and “programming” says about the process of selecting the best solution from
different alternatives.
The Linear programming method is for optimizing the operations with some constraints.
The main point of linear programming is to minimize or maximize the numeric value. It
has also the linear functions that are subjected to the constraints in the form of linear
equations or in the form of linear inequalities.

In the words of William M. Fox, “Linear programming is a planning technique that

permits some objective function to be minimized or maximized within the framework of
given situational restrictions.

The essential characteristics of a linear programming model are explained below:

1. Limited resources: limited number of labor, material equipment and finance

2. Objective: refers to the aim to optimize (maximize the profits or minimize the costs).
3. Linearity: increase in labor input will have a proportionate increase in output.
4. Homogeneity: the products, workers' efficiency, and machines are assumed to be
identical.
5. Divisibility: it is assumed that resources and products can be divided into fractions.
(in case the fractions are not possible, like production of one-third of a computer, a
modification of linear programming called integer programming can be used).

2. What is the major limitation of the graphical method?

Ans: There are various limitations of the graphical method of solving linear
equations, the major one being that the method is inapplicable to problems having
three or more variables.
Following are the various limitations of graphical method:
 Linear programming is applicable only to problems where the constraints and
objective function are linear i.e., where they can be expressed as equations
which represent. In real life situations, when constraints or objective
functions are not linear, this technique cannot be used.
  Factors such as uncertainty, weather conditions etc. are not taken into
consideration.
 There may not be an integer as the solution, e.g., the number of men
required may be a fraction and the nearest integer may not be the optimal
solution.i.e., Linear programming technique may give practical valued answer
which is not desirable.
 Only one single objective is dealt with while in real life situations, problems
come with multi-objectives.
 Parameters are assumed to be constants but in reality they may not be so.

3. Explain the procedure involved in the simplex method to determine the optimum
solution?
Ans: The Simplex method is an approach to solving linear programming models by hand
using slack variables, tableaus, and pivot variables as a means to finding the optimal
solution of an optimization problem. A linear program is a method of achieving the best
outcome given a maximum or minimum equation with linear constraints. Most linear
programs can be solved using an online solver such as MatLab, but the Simplex method
is a technique for solving linear programs by hand. To solve a linear programming model
using the Simplex method the following steps are necessary:

 Standard form
 Introducing slack variables
 Creating the tableau
 Pivot variables
 Creating a new tableau
 Checking for optimality
 Identify optimal values

Step 1: Standard Form

Standard form is the baseline format for all linear programs before solving for the
optimal solution and has three requirements: (1) must be a maximization problem, (2)
all linear constraints must be in a less-than-or-equal-to inequality, (3) all variables are
non-negative. These requirements can always be satisfied by transforming any given
linear program using basic algebra and substitution. Standard form is necessary because
it creates an ideal starting point for solving the Simplex method as efficiently as possible
as well as other methods of solving optimization problems.

Step 2: Determine Slack Variables

Slack variables are additional variables that are introduced into the linear constraints of
a linear program to transform them from inequality constraints to equality constraints.
If the model is in standard form, the slack variables will always have a +1 coefficient.
Slack variables are needed in the constraints to transform them into solvable equalities
with one definite answer.

Step 3: Setting up the Tableau

A Simplex tableau is used to perform row operations on the linear programming
model as well as to check a solution for optimality. The tableau consists of the
coefficient corresponding to the linear constraint variables and the coefficients of
the objective function. In the tableau below, the bolded top row of the tableau states
what each column represents. The following two rows represent the linear
constraint variable coefficients from the linear programming model, and the last row
represents the objective function variable coefficients.

Step 4: Check Optimality

The optimal solution of a maximization linear programming model are the values
assigned to the variables in the objective function to give the largest zeta value. The
optimal solution would exist on the corner points of the graph of the entire model.
To check optimality using the tableau, all values in the last row must contain values
greater than or equal to zero. If a value is less than zero, it means that variable has
not reached its optimal value. As seen in the previous tableau, three negative values
exists in the bottom row indicating that this solution is not optimal.

Step 5: Identify Pivot Variable

The pivot variable is used in row operations to identify which variable will become
the unit value and is a key factor in the conversion of the unit value. The pivot
variable can be identified by looking at the bottom row of the tableau and the
indicator. Assuming that the solution is not optimal, pick the smallest negative value
in the bottom row. One of the values lying in the column of this value will be the
pivot variable. To find the indicator, divide the beta values of the linear constraints
by their corresponding values from the column containing the possible pivot
variable.

Step 6: Create the New Tableau

The new tableau will be used to identify a new possible optimal solution. Now that the
pivot variable has been identified in Step 5, row operations can be performed to
optimize the pivot variable while keeping the rest of the tableau equivalent.

Step 7: Check Optimality

As explained in Step 4, the optimal solution of a maximization linear programming
model are the values assigned to the variables in the objective function to give the
largest zeta value. Optimality will need to be checked after each new tableau to see if a
new pivot variable needs to be identified. A solution is considered optimal if all values in
the bottom row are greater than or equal to zero.

Step 8: Identify New Pivot Variable

If the solution has been identified as not optimal, a new pivot variable will need to be
determined. The pivot variable was introduced in Step 5 and is used in row operations
to identify which variable will become the unit value and is a key factor in the conversion
of the unit value. The pivot variable can be identified by the intersection of the row with
the smallest non-negative indicator and the smallest negative value in the bottom row.

4. What are a basic variable and a non basic variable?

5. Discuss the role of sensitivity analysis in linear programming.

Ans: The term sensitivity analysis, sometimes also called post-optimality analysis,
refers to an analysis of the effect on the optimal solution of changes in the
parameters of problem on the current optimal solution:

 Sensitivity analysis serves as an integral part of solving linear programming

model & is normally carried out after the optimal solution is obtained.
 It determines how sensitive the optimal solution is to making changes in the
original model.
 Sensitivity analysis allows us to determine how “sensitive” the optimal
solution is to change in data values.
 Sensitivity analysis is important to the manager who must operate in a
dynamic environment with imprecise estimates of the coefficients.
 Sensitivity analysis allows him to ask certain what-if questions about the
problem.
 Sensitivity analysis is used to determine how the optimal solution is affected
by changes, within specified ranges, in:
a) The objective function coefficients
b) The right-hand (RHS) values.
The Role of Sensitive analysis of the Optimal Solution
 Is the optimal solution to change in input parameters?
 Possible reasons for asking questions:
o Parameter values used were only best estimates.
o Dynamic environment may cause changes.
o “What-if” analysis may provide economical and operational information.
Sensitivity analysis is important for several reasons:
 Values of LP parameters might change. If a parameter changes, sensitivity
analysis shows it is unnecessary to solve the problem again.
  For Example in the Giapetto problem, if the profit contribution of a solder
changes to $3.50, sensitivity analysis shows the current solution remains
optimal.
 Uncertainty about LP parameters.
 In Giapetto problem for example; if the weekly demand for soldiers is at
least 20, the optimal solution remains 20 soldiers and 60 trains. Thus,
even if demand for soldiers is uncertain, the company can be fairly
confident that is still optimal to produce 20 soldiers and 60trains.
6. What is the difference between a balanced transportation problem and an
unbalanced transportation problem?

7. What is an assignment problem? Give its areas of application?

An assignment problem is a particular case of transportation problem where the

objective is to assign a number of resources to an equal number of activities so as to
minimise total cost or maximize total profit of allocation.
The problem of assignment arises because available resources such as men,
machines etc. have varying degrees of efficiency for performing different activities,
therefore, cost, profit or loss of performing the different activities is different.
Thus, the problem is “How should the assignments be made so as to optimize the
given objective”. Some of the problem where the assignment technique may be
useful are assignment of workers to machines, salesman to different sales areas.
Definition of Assignment Problem:
Suppose there are n jobs to be performed and n persons are available for doing
these jobs. Assume that each person can do each job at a term, though with varying
degree of efficiency, let cij be the cost if the i-th person is assigned to the j-th job.
The problem is to find an assignment (which job should be assigned to which person
one on-one basis) So that the total cost of performing all jobs is minimum, problem
of this kind are known as assignment problem.

8. Explain the steps involved in solving an assignment problem.

Following steps are involved in solving an assignment problem:

Step 1: Develop the Cost Table from the given Problem:

If the no of rows are not equal to the no of columns and vice versa, a dummy row
or dummy column must be added. The assignment cost for dummy cells are
always zero.
Step 2:  Find the Opportunity Cost Table:
(a) Locate the smallest element in each row of the given cost table and then
subtract that from each element of that row, and
(b) In the reduced matrix obtained from 2 (a) locate the smallest element in each
column and then subtract that from each element. Each row and column now
have at least one zero value.

Step 3: Make Assignment in the Opportunity Cost Matrix:

The procedure of making assignment is as follows:
(a) Examine rows successively until a row with exactly one unmarked zero is
obtained. Make an assignment single zero by making a square around it.
(b) For each zero value that becomes assigned, eliminate (Strike off) all other
zeros in the same row and/ or column.
(c) Repeat step 3 (a) and 3 (b) for each column also with exactly single zero
value all that has not been assigned.
(d) If a row and/or column has two or more unmarked zeros and one cannot be
chosen by inspection, then choose the assigned zero cell arbitrarily.
(e) Continue this process until all zeros in row column are either enclosed
(Assigned) or struck off (x)
Step 4: Optimality Criterion:
If the member of assigned cells is equal to the numbers of rows column then it is
optimal solution. The total cost associated with this solution is obtained by adding
original cost figures in the occupied cells.
If a zero cell was chosen arbitrarily in step (3), there exists an alternative optimal
solution. But if no optimal solution is found, then go to step (5).
Step 5: Revise the Opportunity Cost Table:
Draw a set of horizontal and vertical lines to cover all the zeros in the
revised cost table obtained from step (3), by using the following procedure:
(a) For each row in which no assignment was made, mark a tick (√)
(b) Examine the marked rows. If any zero occurs in those columns, tick the
respective rows that contain those assigned zeros.
(c) Repeat this process until no more rows or columns can be marked.
(d) Draw a straight line through each marked column and each unmarked row.
If a no of lines drawn is equal to the no of (or columns) the current solution is the
optimal solution, otherwise go to step 6.
Step 6: Develop the New Revised Opportunity Cost Table:
(a) From among the cells not covered by any line, choose the smallest element,
call this value K
(b) Subtract K from every element in the cell not covered by line.
 (c) Add K to very element in the cell covered by the two lines, i.e., intersection of
two lines.
(d) Elements in cells covered by one line remain unchanged.

9. What is the difference between CPM and PERT?

Ans: PERT is that technique of project management which is used to manage
uncertain (i.e., time is not known) activities of any project. CPM is that technique of
project management which is used to manage only certain (i.e., time is known)
activities of any project
PERT and CPM are the two network-based project management techniques, which
exhibit the flow and sequence of the activities and events. Program (Project)
Management and Review Technique (PERT) is appropriate for the projects where the
time needed to complete different activities are not known.
On the other hand, the Critical Path Method (CPM) is apt for the projects which are
recurring in nature.

Meaning PERT is a project management CPM is a statistical technique of

technique, used to manage uncertain project management that manages
activities of a project. well defined activities of a project.

What is it? A technique of planning and control A method to control cost and time.
of time.
Orientation Event-oriented Activity-oriented
Evolution Evolved as Research & Evolved as Construction project
Development project
Model Probabilistic Model Deterministic Model
Focuses on Time Time-cost trade-off
Estimates Three times estimates One time estimate
Appropriate for High precision time estimate Reasonable time estimate
Management of Unpredictable Activities Predictable activities
Nature of jobs Non-repetitive nature Repetitive nature
Critical and Non-critical No differentiation Differentiated
activities
Suitable for Research and Development Project Non-research projects like civil
construction, ship building etc.

The most important differences between PERT and CPM are provided below:
1. PERT is a project management technique, whereby planning, scheduling,
organising, coordinating and controlling uncertain activities are done. CPM is a
statistical technique of project management in which planning, scheduling,
organising, coordination and control of well-defined activities take place.
2. PERT is a technique of planning and control of time. Unlike CPM, which is a
method to control costs and time.
 3. While PERT is evolved as a research and development project, CPM evolved as a
construction project.
4. PERT is set according to events while CPM is aligned towards activities.
5. A deterministic model is used in CPM. Conversely, PERT uses a probabilistic
model.
6. There are three times estimates in PERT, i.e. optimistic time (to), most likely time
™, pessimistic time (tp). On the other hand, there is only one estimate in CPM.
7. PERT technique is best suited for a high precision time estimate, whereas CPM is
appropriate for a reasonable time estimate.
8. PERT deals with unpredictable activities, but CPM deals with predictable
activities.
9. PERT is used where the nature of the job is non-repetitive. In contrast to, CPM
involves the job of repetitive nature.
10. There is a demarcation between critical and non-critical activities in CPM, which
is not in the case of PERT

10. What are the critical path activities and why are they considered important?

11. What is a sequencing problem?

12. What are the advantages of sequencing?

13. What is the replacement of items? Why is it important?

Ans: The Replacement Theory in Operations Research is used in the decision making
process of replacing a used equipment with a substitute; mostly a new equipment of
better usage. The Replacement might be necessary due to the deteriorating property
of failure or breakdown of particular equipment. The ‘Replacement Theory’ is used
in continue with them, or the items might have been destroyed either by accident or
otherwise. The above discussed situations can be solved mathematically and
categorized on some basis like:

 Items that deteriorate with time e.g. machine tools, vehicles, equipments etc.
 Items becoming out-of-date to new developments like ordinary weaving
looms by automatic, manual accounting by tally etc.

Causes of replacement:

1. Deterioration
2. Obsolescence
3. Inadequacy
 4. Working Condition

Factors to be considered:
 Sunk costs to be ignored
 Existing asset value need not be considered
 Income tax to be avoided
 The optimal replacement cycle is one which has lowest equivalent annual
cost
 The replacement decision will apply indefinitely.
 Economic life of the challenger and the defender should not consider

14. What is meant by a Fair Game?

15. What is S? Give a few areas of its application.