System Engineering
System Engineering
System Engineering
Mrs. R. Vasanthi
R. Vasanthi
R. Visvanathan
R. Palaniswamy
S. R. Devadasan
WWW.AGRIMOON.COM
System Engineering
Mrs. R. Vasanthi
Asst. Professor (Mathematics)
Agricultural Engineering College and Research Institute, TNAU, Coimbatore
Dr. R. Visvanathan
Co-CCPI and Prof. and Head, Post Harvest Technology Centre
Agricultural Engineering College and Research Institute, TNAU, Coimbatore
-:Content Reviewed by :-
Dr. R. Palaniswamy
Professor, Physical Sciences
Agricultural College and Research Institute, TNAU, Madurai
Dr. S. R. Devadasan
Professor, Mechanical Engineering Department
PSG College of Technology, Coimbatore
Index
Lesson Page No
Module 1. Systems concept
Lesson 1. Systems concept: operations management 5-11
Lesson 2. Systems concept: managerial policy and decision making 12-20
Lesson 3. Systems concept : methodology and models 21-34
Module 2. Requirements for linear programming problems
Lesson 4. Origin and development of or 35-31
Lesson 5. Methodology- uses and limitations 32-34
Lesson 6. Linear programming – basic ideas 35-40
Module 3. Mathematical formulation of linear programming problems
and its graphical solution
Lesson 7. Mathematical formulation of the problem 41-44
Lesson 8. Graphical method i 45-48
Lesson 9. Graphical method ii - special cases 49-52
Module 5. Simplex method, degeneracy and duality in linear
programming
Lesson 10. Simplex method 53-64
Lesson 11. Simplex method problems 65-69
Lesson 12. Degeneracy 70-72
Lesson 13. Duality in linear programming 73-76
Lesson 14. Simplex method –problems 77-83
Module 6. Artificial variable techniques- big m method, two phase
methods
Lesson 15. Artificial variable techniques- big m method 84-87
Lesson 16. Big m method - problems 88-91
Lesson 17. Big m method- special case 92-95
Lesson 18. Artificial variable techniques- two phase method 96-101
Module 7.
Lesson 19. Introduction to models 102-105
Lesson 20. Growth models 106-111
Module 8.
Lesson 21. Introduction to agricultural system 112-114
Lesson 22. Linear growth model 115-120
Lesson 23. Logistic growth model 121-124
Lesson 24. Richard’s growth model 125-134
Module 9. Cost analysis
Lesson 25. Cost analysis: cost of operation / production 135-143
Lesson 26. Investment analysis 144-156
Lesson 27. Inventory control 157-167
Module 10. Transporatation problems
Lesson 28. Transportation problems 168-175
Lesson 29. Transportation problems 176-191
Lesson 30. Transportation problems 192-197
Module 11. Assignment problems
Lesson 31. Assignment problems – introduction 198-201
Lesson 32. Assignment problems - solutions of the assignment problems 202-205
Lesson 33. Assignment problems - assignment algorithm 206-216
Module 12. Waiting line problems
Lesson 34. Introduction to queuing theory 217-220
Lesson 35. Characteristics of queueing systems 221-223
Lesson 36. Classification of queuing models and their solutions 224-229
Lesson 37 solved examples 230-234
Module 13. Network scheduling by PERT / CPM
Lesson 38. Network analysis 235-237
Lesson 39. Construction 238-241
Lesson 40. Critical path method 242-246
Lesson 41. Programme evaluation review technique: (pert) 247-251
Lesson 42. Network problems 252-258
Module 14. Resource analysis in network scheduling
Lesson 43. Project cost and resource leveling 259-261
Lesson 44. Time-cost optimization 262-265
Lesson 45. Time cost optimization- problems 266-272
System Engineering
Systems concept - introduction - operations management - resources, material and equipment, human
resources, capital - systems concept - types of systems - components of systems - systems design -
systems control - transformation and value-added activities.
1. INTRODUCTION
‗Happiness is different things to different people‘ similarly ‗systems mean different things to different
people‘ and some relate systems to science. All living things in the earth are related to ‗system of
nature‘. The term system denotes plan, method, order and arrangement.
System is an assembly or combination of things or parts forming a complex or unitary as a whole. For
eg. 1. In the world around as there are mountain system, river system, solar system etc. 2. Human body
is a complex organism as a system comprises of many systems like skeletal system, circulatory system,
nervous system, etc.
As systems comprises of systems with in that & subsystems there are systems, systems of systems &
systems of universe is a system of heavenly bodies which includes many systems of stars called
galaxies. Within such galaxy in the solar system one of the many planetary systems.
If organizational units are designed and operated as a system, each segment or subsystem can be
viewed as a self contained unit and its relationship or contribution to the next level can be programmed
and measured.
2. OPERATION MANAGEMENT
Operations management is defined as that activity whereby resources, flowing within a defined
system, are combined and transformed in a controlled manner to add value in accordance with policies
communicated by management.
Whereas the term "production," in a narrow sense, is often associated with a quantity of goods, or with
an assembly or perhaps a chemical process, "production management" has always been concerned with
the productivity of the transformation process. In a very real sense the above definition of operations
management also encompasses production management. We shall recognize this understanding, using
the word "production" to connote the vital concepts of transformation and value added. But we shall
not necessarily restrict transformations to physical processes, nor assume that value added represents
only material values that can be expressed in monetary terms (as opposed to human and immaterial
values).
The production activity is dynamic and takes place in an uncertain economic and social environment
that changes over time. Management has the task of acting upon and reacting to the environment by
making decisions which direct productive efforts toward the achievement of organizational objectives,
Key elements in the definition of operations management are the concepts of (1) resources, (2) systems,
(3) transformation and value-adding activities, and (4) managerial policy.
5
www.AgriMoon.Com
System Engineering
2.1. Resources
An organization's resources are the material and nonmaterial assets available to achieve desired
objectives. Resource inputs to the production system may be conveniently classified into material and
equipment, human, and capital resources.
These are the physical facilities and equipment such as plant, inventories, and supplies. Included are
operating and control equipment like computers and the physical energies (for example, electrical,
mechanical) used in operations. In an accounting sense, the material and equipment usually constitute
the major assets of an organization.
The human input is both physical and intellectual. Early production efforts relied heavily upon human
physical labour, but as production technology and methodology advanced, a higher proportion of the
human input became devoted to planning, organizing, and controlling efforts. By using the intellectual
capabilities of people, labor inputs are magnified many times, resulting in increased productivity as
well as a much closer worker-machine interface. This closer integration of human and physical systems
has in turn presented new challenges in job design to achieve worker satisfaction.
The labour resource, although it is often the key asset of an organization, is typically not accounted for
in the balance sheet of the organization. It is the human resource, in the form of managerial talent,
engineering skill, employee cooperation, etc. that has provided the primary impetus for the growth and
development of the large-scale organizations that flourish today.
People bring human values into an organization, and some of these values are essentially
institutionalized into the resulting organizational society. They become traditions, standards, and
ethical guidelines, both for internal operations and for dealing with "the public." These values often
play a strong but difficult to define role in the organizational decision process.
2.4. Capital
Funds are essential to establish and regulate the amount of material and human inputs. In an aggregate
sense they help to determine the level of technology and the tradeoff between the use of labour versus
equipment. As more capital is allocated to a given phase of a production process, the level of
technology typically rises and through automation, equipment replaces human labour.
In free enterprise organizations, capital becomes available in the form of equity (stock) or debt (bonds)
funds and is replenished through profits. In nonprofit organizations, taxes or contributions are a
continuing source of funds to finance operations deemed to be in the group or public interest.
However, whether an organization is profit- or nonprofit-oriented, efficient and effective use of
resources rests heavily upon fundamental principles of operations management.
3. SYSTEM CONCEPT
6
www.AgriMoon.Com
System Engineering
system, for example, has doctors and physical facilities plus conceptual operating policies which
combine to ultimately provide patients with a specified level of medical care.
Our cultural environment includes a multitude of economic and social systems, many of which are
interrelated and function simultaneously for the benefit of society as a whole. For example, we have a
national monetary system which facilitates the exchange of goods and a transportation network which
can move these goods quickly and efficiently to any part of the country.
The individual business and government organizations are essentially subsystems of larger social
systems. They, in turn, are typically composed of their own subsystems, which theoretically function
for the good of their individual organizations. The production, marketing, and finance functions are
traditional subsystems of the formal organization of a firm. However, many firms are now
reorganizing their formal structure to better account for the interdependency of such subsystems. As a
result, business systems are emerging which are based more upon information flows and decision
responsibilities than upon strict functional lines.
A systems approach to operations management problems places strong emphasis upon the integrative
nature of management responsibilities, recognizing both the interdependence and the hierarchical
nature of subsystems. In essence, systems theory stresses the understanding and relationships of the
whole system, recognizing that a combined effect of components can be greater than the sum total of
individual effects, that is, can be synergistic. Problems must first be abstracted from the overall (macro)
environment, then they can be broken down into parts (micro), analyzed, and solutions proposed. But
ultimately the components must again be restructured or synthesized (macro) to discover and evaluate
the impact of new interrelationships that arise from proposed changes in the system.
The ability of any system to achieve its objectives depends upon fl) the design of the system and (2) the
control exercised by the system.
4. TYPES OF SYSTEMS
Man-made system: Transportation system, lighting system. Man-made system is designed and
operated by man. The man utilizes the inputs taken from the natural systems.
Flexible system: The system which is adjusting to maintain the balance or equilibrium between the
system and is changing environment. Example: most of the life forms, economic, political and social
systems.
Rigid system: which cannot be modified or will not adjust for modification. Example: highway. Even
the man tries to build some flexibility into every system designed or constructed. Example: Building.
7
www.AgriMoon.Com
System Engineering
Manual system: A production system completely man operated one. Example: Coir thread making.
5. COMPONENTS OF SYSTEM
If units are designed and operated as a system, each segment or subsystem can be viewed as a self
contained unit & its relationships or contribution to the next level can be performed and measured.
Inputs, transformation process and output are the components of any system. Input and output are
mere significant than the actual transformation process. ‗Black box‘ approach is used to demonstrate
the relationship let computes and systems. A component is a basic unit or black box which performs or
provides the facility for performing some part of the transformation process. A teacher – component in
education or university system, may be taken for medical illustration as a system with several sub
systems. The definition of what is a system, subsystem, components occurs when the objectives of
those systems are determined.
6. SYSTEM DESIGN
Most managers realize that the independent optimization of individual subsystems, such as marketing
or production functions, does not necessarily result in optimization of the objectives of the total system.
Production may favour a steady manufacturing rate and low inventories while marketing is anxious to
meet highly seasonal demands. If any form of total system optimization is to be achieved, the
subsystem objectives must be integrated and coordinated in light of overall system goals. It makes
sense to start with a clearly delineated set of overall system objectives and to develop a hierarchy of
subsystem goals which, when consistently pursued, will most effectively facilitate the overall
objectives.
8
www.AgriMoon.Com
System Engineering
One of the most vital inputs to systems design comes from the consumers or users. They embody the
service objectives of the organization and are also the ultimate source of funds for the operations. Since
the system functions to serve the consumers, their quantity and cost requirements, as well as quality
and other technological desires, should be incorporated into the production systems design. Business
history has vividly proved that orientation to the consumers is a key element in an organization's
success. This holds true for public and nonprofit organizations as well as profit-making firms.
The more structured the design is, the less planning and decision making will be involved in the
operation of the system. Similarly, a highly structured design, although suitable for high-volume
production of standardized products, is inherently less adaptable to meeting competitive pressures of
broader product lines in smaller volumes upon shorter notice from the customer. An increasingly
important consideration in modern systems design arises from the need for flexibility and adaptability,
of the system to meet new and unexpected demands. Fortunately, both physical equipment and human
components can be geared to accept change, especially if the system has been designed with this
inevitability in mind.
Production systems are often categorized as continuous or intermittent, although many systems are a
combination of the two. In continuous designs, the physical flow of products is continuous and
9
www.AgriMoon.Com
System Engineering
production is usually in high volumes accomplished through line-type operations. Plant layout is
arranged to accommodate the product, such as paper, and specialized equipment is used. In
intermittent designs, the physical flow of products is intermittent and production is on a batch or job-
order basis. Layout is arranged according to process, and general-purpose equipment is used.
Fig.2 shows a simplified theoretical model of a production system design. Note that the essential
elements are inputs, transformation activities, and outputs.
7. SYSTEMS CONTROL
Systems control consists of all actions necessary to ensure that activities conform to preconceived plans
or goals. Control involves measurement, feedback, comparison with standards, and corrective action.
Fig.3 adds a control mechanism to the production system shown in Fig.2. The measurement function
must be accomplished by some appropriately accurate sensory device. Data are then fed back for
comparison and correction, with the feedback activity depending heavily upon the physical or
organizational communication network. An effective information system having appropriate response
times is essential to the operation of an effective control system. Standards for comparison are based
upon historical or engineered criteria and may be in the form of physical measurements, control limits,
cost variances, etc. Finally, corrective action implies both an authority to change the system and the
ability to implement those changes.
The system described in Fig.3 is a closed-loop arrangement because it can automatically function on the
basis of data from within its own system to ensure that the outputs will continuously meet control
10
www.AgriMoon.Com
System Engineering
standards. Open-loop control systems do not have sufficient internal feedback with automatic control
to maintain desired standards for they are influenced by "outside" information. Any system that inter-
faces with the environment is open to the extent that it receives stimuli from outside its own control.
For example, a spaceship that depends upon navigational information from computers on earth would
be operating (at least partly) as an open system.
The objective of combining resources (that is, factors of production) under controlled conditions is to
transform them into goods or services having a higher (material or immaterial) value than the original
inputs. The effectiveness of the use of the factors of production to produce goods and services is
commonly referred to as productivity. Basically, productivity connotes a relationship of output to input
such that:
This concept of value added is in contrast to the notion of engineering efficiency where energy losses
within any physical system prohibit the ratio of output to input from being greater than one.
The values placed on goods or services differ with consumers. But as a large volume of output enters a
competitive market, monetary amounts typically emerge as indicators of value. However, many
outputs from a production system, such as employee satisfactions, social and environmental impacts,
and so forth, are unique, and are difficult to value on a monetary basis. In the past, such intangible
values and side effects of production decisions were often overlooked. Today we recognize the reality
of these outputs and managers are forced to deal with them in terms of different individual and group
value systems.
Measures of physical productivity serve as means of comparison for two or more individual units or
organizations, as well as for whole industries and even nations. The resource base, population growth,
ethic of the people, and existing level of technology all contribute to the economic growth rate of a
nation. The productivity of the employees depends on (i) the level of training and education of the
employees and (2) the substantially higher capital investment in automated production equipment.
Since organizations operate in a dynamic environment that charges over time, the inputs and outputs
are best described as flows of inputs and outputs. In the physical sense, production (as a noun) results
from maintaining the system flows. For a given level of inputs, improvements in the design or control
of the system will increase productivity and the value of the outputs will be greater.
Production operations managers are concerned with both the technology of the transformation process
and the methodology of managing the process. The technology is often unique to given industries, such
as steel or paper processing, and is not the central focus of this text. However, the methodology of
planning, organizing, directing, and controlling activities has a theoretical base which is common to
most, or perhaps all, production activities. The development and use of this type of analytical base is
the concern of this text.
11
www.AgriMoon.Com
System Engineering
1. MANAGERIAL POLICY
Modern management techniques have developed from a unique history of practical and theoretical
effort. When the machine-powered factory system became well established Frederick Taylor
suggested that the scientific method be applied to all management problems. More specifically, he
proposed (1) scientific selection and training of workers, (2) definition of each worker's tasks, and (3)
cooperation and division of work between labour and management. Taylor's ideas were known as
"scientific management systems" and he was known as the "father of scientific management." As
corporations grew, a larger financial base was required and stock ownership became more widespread.
Owners soon turned to professional managers to run their organizations. Several theories were
developed to explain the role of managers; the important approaches to management are discussed
below.
This widely held approach holds that management has traditionally been charged with the role of
planning, organizing, directing, and controlling the activities of an organization. This approach regard
management as a universal process which is readily understood in terms of these fundamental
functions which must be performed regardless of the type of organization.
This human relations approach recognizes that managers are people who work through other people to
lead the activities of an organization. In viewing the individual as a sociopsychological being, it
concentrates upon behavioral and motivational forces and stresses the art of interpersonal
relationships. The manager is a leader of individuals or groups and the human element of organization
receives paramount attention.
This approach views a manager basically as a decision maker within an operating system. Management
is concerned with the methodology and implementation of decisions that facilitate system goals. The
decisions may well relate to both functions (such as planning, organizing, directing, and controlling)
and to people, for these subgoals and resources both exist within a systems context. Furthermore,
scientific methods of modeling and systems analysis can be followed to reach decisions.
Whereas some management theorists would separate the decision-making and systems approaches, we
have chosen to emphasize decision making in a systems context because of its theoretical basis and
12
www.AgriMoon.Com
System Engineering
applied usefulness. Other approaches also exist, but we shall not explore them in any depth. For our
purposes, then, we shall refer to management as the process of making decisions and taking action
relative to functions and behaviour which direct the activities of people in organized systems toward
common objectives.
2. DECISION-MAKING FUNCTION
The decision-making-systems approach has particular scientific and analytical suitability, the concept
can be selected from other perspectives.
The idea of management as a science is founded upon several observations. First, the "principles and
methodology of management" form an organized body of knowledge. Moreover, much of the current
decision methodology has advanced to a logically rigorous state. Second, real-world data are available
for analysis. The business world is essentially a laboratory to the management scientist. Third, an
objective systematic analysis of the data can often be made. This analysis relies largely upon modern
mathematical and statistical techniques. Finally, another experimenter (decision maker) could use the
same data and arrive at consistent results.
The association of management with the scientific method involves drawing objective conclusions from
facts, and facts come from analysis of data. Therefore, the idea of quantification of data is an important
element in viewing management as a science. Computers and management information systems are
now providing such a data base for decisions. By means of mathematical modeling and simulation, this
decision-making process also allows for experimentation and for testing of hypotheses.
Viewing management from the standpoint of a science, one must conclude that the decision-making
methodology can be both taught and learned as can other sciences. People need not be "born managers"
to do the job. Education, training, and experience can improve managers' abilities to make optimal
decisions. They can learn ways of identifying relevant system parameters, collecting data, and
analyzing data that will lead to better courses of action. As decision making becomes more scientific,
the importance of clearly defined objectives and systematic analysis also becomes more apparent.
If managers were nothing more than mechanistic robots operating in a computerized laboratory, we
might uncompromisingly argue for the full-fledged classification of management as a science. But
management decisions are not always based upon an "objective systematic analysis of the data. The
same humanistic element of concern for others exists in the engineering, medical, and other professions
which we commonly associate with the scientific method. Professional decisions are not always value
free - the choice of an "appropriate action" often rests, at least partly, upon an individual or an
institutionalized value system.
The incorporation of values into business decisions does not necessarily brand the decision process as
nonscientific - nor the results as invalid or unpredictable - for several reasons. First, many business
decisions can legitimately be based upon facts that do not carry value-laden implications. This is
especially true for numerous routine decisions related to micro, or subsystem, operations. An example
of this would be the choice an operations manager must make between two similar pieces of capital
equipment with differing initial costs and lifetimes. The chances are that this decision can be made in a
fairly objective, systematic manner.
13
www.AgriMoon.Com
System Engineering
Second, existing legal or environmental controls may accurately reflect individual or organizational
ethics. For example, production cost auditors may believe that the intent of the tax laws accurately
reflects what their firms "should" pay in federal taxes. Thus they neither overlook legitimate cost
deductions nor attempt to capitalize on tax "loopholes." In this case, the applicable laws provide a
satisfactory guide to action.
Third, values can be made known and accepted as an underlying standard. Many organizations have
identified and adhere to sound values (such as codes of ethics) that are applied in a consistent and
predictable manner. In this sense, a broadly based value system acts much like an organized body of
knowledge and facilitates a scientific approach to decisions.
Of course, many (perhaps most) value-based decisions are complex. Problems arise when "the law" is
an inadequate guideline or when values are not commonly or consistently held. Individual decision
makers sometimes narrow organizational concerns to their own self-interests. Others have little sense
of distributive justice and their allegiance wavers among the conflicting interests of themselves,
employees, stockholders, consumers, society, etc. Decision making in such situations cannot be
construed as being truly "scientific." Nevertheless there is even hope for eventually moving these
situations a little closer towards a scientific basis through proper education and training of the decision
makers. As decision makers gain an improved awareness of the value systems of others, the reasons for
differences become explored, some differences are resolved, and others perhaps are more willingly
accommodated.
Recognizing that despite value differences a scientific framework for business decisions does have
wide applicability, we now go on to examine the analytical framework for decisions in greater detail.
As we proceed through the steps we shall note the areas where value system differences come into
play.
An analytical and scientific framework for decisions implies several systematic steps for the decision
maker. These steps are summarized as below.
5. Choose the course of action which most closely satisfies 'he criteria.
The systems approach to defining the problem (step 1) helps to ensure that the final decisions are as
nearly optimal as possible. A system defined broadly may include many tangential aspects of a
problem, making it extremely difficult to establish the complex relationships among the variables.
Similarly, a narrowly defined problem might omit relevant variables. The inclusion or exclusion of
variables depends upon the system goals; if variables have a significant effect on the goals, they should
be included as parameters of the system.
14
www.AgriMoon.Com
System Engineering
In some cases, skilled systems analysts can facilitate the solution of problems by providing the
operating manager with specific systems design and programming skills. However, the model user
must almost inevitably become actively involved in defining the problem and formulating the
relationships (that is, model building) if the solution is to be truly a useful user-oriented one. This
requires close communication and interchange of information between the systems analyst and the
decision maker.
The establishment of decision criteria (step 2) is of paramount importance for they stem directly from
objectives which give purpose and direction to work efforts of the organization. For many years, profits
served as a convenient and accepted goal for most free enterprise organizations. Perhaps this was
because early models of firm behavior were based almost wholly on economic theory. Today, empirical
re- search reveals that organizations have sets of goals rather than single goals and that profits are only
one of many possible objectives. Studies identified the following eight types of goals set by industries.
1. Organizational efficiency
2. High productivity
3. Profit maximization
4. Organizational stability
5. Employee welfare
6. Organizational growth
7. Industrial leadership
8. Social welfare
There is reason to suggest that social welfare goals have gained more importance as environ mental
concerns have become more prominent during the past few years. Social pressures are now strongly
limiting the exploitation of resources solely for economic gain and instead are focusing upon the
greatest good for the most people over the longest period. Nevertheless, for many organizations within
our free enterprise society, profits continue to be a key source of motivation, rewards, and
investment capital that underlies a good deal of our nation's economic progress.
Numerous ways exist for classifying objectives, such as economic, social, and political, or individual
and organizational. The above listed goals have been classified into: (1) general efficiency, which are
specific and largely quantifiable criteria and include organizational efficiency, high productivity, and
profit maximization; (2) associative status, which sometimes results as a by-product of action toward
general efficiency goals and includes organizational growth, industrial leadership and orgnaisational
stability; (3) employees welfare; and (4) social welfare classifications. The study referenced found
relatively strong correlations between associative goals and personal or organizational characteristics
suggesting that differenced in firm behaviour may be more due to associative status goals than to
general efficiency goals, and that actual goals of a business may be related more be related more closely
to personal characteristics of the managers than to broad characteristics of the business.
The decision criterion (or set of criteria) flows directly from organizational objectives and should be as
specific as possible. A criterion of ―maximizing profits‖ may be adequate as one (economic)
15
www.AgriMoon.Com
System Engineering
organizational goal, but too broad and inadequate for much decision making on an operational goal,
but too broad and inadequate for much decision making on an operational level. Fig. 4 depicts the
hierarchical structure of goals by comparing it to the familiar upside-down planning pyramid which
begins with broad objectives that are ultimately operationalized into specific rules. The figure
illustrates the necessity of specific directives such as ―Rotate workers among 3 jobs‖ in order to fulfill
broader objectives such as ―Increase profits‖. Note the subsystem criteria must be consistent with the
higher-level goals. If inconsistencies exist in the goal structure, some of the organization‘s resources are
probably being wasted by the pursuit of contradictory objectives. An example of this would be a power
company with vague profit and service objectives. If its marketing group were to promote the
distribution of air conditioners while the production capacity was inadequate, neither profit nor service
objectives would be achieved. In some cases system criteria, such as ―good customer service,‖ are so
difficult to quantify that substitute criteria, such as ―number of customer complaints,‖ must be used.
One should clearly recognize and label such measures as indicators or criteria. Otherwise, the
substitute criteria may be satisfied, even though the intent of the system criteria is not. For example, a
pressured office manager might ―reduce the number of customer complaints by 50 percent‖ by simply
adopting a tedious 10-page customer complaint form. Unfortunately, this is not likely to help achieve
the organizational objective of better customer service even though the office manager will have
satisfied the substitute criteria. Large bureaucracies are often faced with such problems of using
substitute criteria because system objectives become institutionalized in terms of formal policies and
impersonal regulations. For this reason decision criteria should be reviewed frequently to ensure the
surrogate criteria are being used in a manner consistent with total system criteria.
16
www.AgriMoon.Com
System Engineering
Source: Monks, J.G. 1977. Operatons Management – Theory and Problems. McGrawhill Book
Company, New York.
The formulation of a relationship, or model, for experimentation (step-3) lies at the heart of the
scientific decision-making process. Models may be verbal, pictorial, schematic decision-making
process. Models may be verbal, pictorial, schematic, physical, scale, numerical and statistical or
mathematical. In general, they attempt to describe the essence of a situation or activity by abstracting
from reality so the decision maker can study the relationship among relevant variables in isolation.
They do not attempt to duplicate reality in all respects, for models that do this reveal nothing. Instead,
they are limited approximation of reality. If, for example, the system boundaries were defined in a
wide and inclusive manner, the problem situation would perhaps be more realistic, but the problem
itself would remain just as difficult to solve. The key to model building lies in abstracting only the
relevant variables that affect the criteria and expressing the relationships in a testable form.
or symbolically
Obj = f(X,Y,Є)
A full description of any model should also include a statement of its assumptions and constraints. All
models need not have controllable X, uncontrollable Y, and error terms Є, but these are convenient
classifications. The error term often represents a statistical factor which accounts for our use of sample
rather than census data. Of course we attempt to keep the amount of error as small as possible.
Q = f(F,D,I)
Where,
Note that the forecast production rate F is a controllable variable, actual demand D is largely
uncontrollable, and current inventory level I has elements of both. By relating the parameters F,D, and
I, via appropriate equations and assigning values to these parameters, the model builder can arrive at
proposed values for Q.
Fig. 4 shows the mathematical modeling process in the form of a schematic model [1:72 (modified)].
Note that it is an abstraction which begins and ends with the real world. The validity of a model
should, of course, be judged relative to what it is supposed to do. If, for example, a forecasting model
accurately predicts real world demand, a manager would consider it to be a ―good‖ model. Techniques
are available to evaluate the validity of models, some of which we shall discuss later in the text.
17
www.AgriMoon.Com
System Engineering
One of the most difficult aspects of model building lies in incorporating experience, human values, and
subjective or less-tangible factors into the relationship in a mathematical or statistical manner.
Although this is certainly not a new problem, the renewed emphasis on human and social values has
generated increased efforts along these lines. Another difficult aspect of model building involves the
problems of accommodating multiple goals, as explained earlier. Whereas goal identification is still
largely a subjective undertaking, the quantitative approaches of utility theory and goal programming
offer some objective potential in this realm.
Any decision problem implies that alternatives exist. The relationships formulated between the
parameters and the decision criteria permit the generation of alternative solutions (step-4) by varying
the values of the parameters. Mathematical and statistical models, again, are particularly suitable for
generating alternatives because they are so easily modified. The model builder can ―experiment‖ with
the model by substituting different values for controllable variables (such as employment levels) as
well as uncontrollable variables (such as actual demand).
It is noted earlier that the goals and decision criteria had a strong value base. The generation of
alternatives also has important value connotations. Just as goals are an end, the alternatives are a
means to that end. Both individuals and institutions are sometimes faced with the question of whether
or not a given means is morally acceptable.
18
www.AgriMoon.Com
System Engineering
Our society generally upholds the conviction that the end does not justify the means. For example, the
courts have said that a legitimate goal of profits or market share does not justify price fixing or
collusion as a means of obtaining it. In some cases, legislation (such as antitrust laws) may constitute a
satisfactory behaviorual guide for managers. But laws do not anticipate every situation and managers
must generally rely upon their individual and institutional value systems. In these situations values
play an important role in the decision process by ruling out (as infeasible) any alternatives that are not
consistent with behavioral standards.
The final step in the decision process ( step 5) is to choose the best course of action, that is, the one that
best satisfies the criteria. Some models, such as linear programming, are inherently of an optimizing
nature and automatically seek out a maximizing or minimizing solution. If the system boundaries are
clearly defined, and all the model assumptions are satisfied, these methods will generate optimal
solutions to the specific situations. Other models are more suitable for use in situations that are so
complex, uncertain, or subjective that optimal solutions cannot be used to suggest the best course of
action, or at least a preferred course, on the basis of the information and resources available to make the
decision. The best course of action or solution to a problem determined through use of a model is just
that-a solution to the model! The true test of the decision process comes when the theoretical solution is
applied to the real-world situation. Decision-making processes should therefore incorporate follow-up
procedures to ensure that the action is appropriate in the real world. These procedures should include
an analysis and evaluation of the solution plus any recommendations for changes or adjustments.
Focus on the knowledge and information base that provides the data which are essential to the
scientific decision-making process is important. With better information, a decision maker can be
expected to make decisions that more effectively move an organization towards its goals. Fig. 5 depicts
the information environment of decisions as one ranging from a situation where the decision maker has
(or assumes he or she has) complete information about the decision variables to the other extreme
where he or she has no information about them. Operations management decisions are in fact made at
numerous points along this continuum from complete certainty to extreme uncertainty.
As can be seen, complete certainty requires census data on all elements in the population. Lacking this,
large samples lend more certainty than do small samples. Beyond this, subjective information is very
likely better than no data at all.
19
www.AgriMoon.Com
System Engineering
20
www.AgriMoon.Com
System Engineering
Models for operations analysis - economic break-even analysis - utility-based decisions - production
system schematic - classification of operations management decision areas.
1. METHODOLOGY OF DECISIONS
The kind and amount of information available about the decision criteria and variables help determine
which type of analytical methods are most appropriate for a given decision situation. Fig. 1 shows
some useful quantitative methods currently available to operations managers. These analytical
techniques often serve as the basis for formulating models to help reach decisions. Illustrative problems
make wide use of these and other quantitative methods. The text material is, however, application-
oriented, and organized according to subject matter rather than to quantitative method. Thus, in many
cases, more than one methodology may be suitable for a given problem. A brief description of some of
these analytical methods are discussed below.
A condition of certainty does not necessarily imply that decision making is easy, for a problem may be
ill-defined, decision criteria unclear, or there may be too many variables to accommodate economically,
even though the model is theoretically feasible. For many situations, however, the following methods
are useful.
Algebra: This basic mathematical logic is useful in both certainty and uncertainty analysis. Given valid
assumptions, algebra provides a deterministic solution in situations such as break-even and benefit-
cost analysis.
Calculus: This branch of mathematics provides a useful tool for determining optimal values (limits)
where functions are to be maximized or minimized, such as inventory costs.
Statistical analysis: Classical estimation and testing techniques methods have proven increasingly
valuable as means of better using operating information for decisions. Some of the widespread applica-
tions include the setting of labor standards, forecasting, inventory and production control and quality
control.
Queuing theory: Analysis of queues in terms of waiting-line length and mean waiting time is
particularly useful in analyzing maintenance activities.
21
www.AgriMoon.Com
System Engineering
Simulation: Simulations duplicate the essence of an activity or system without actually achieving
reality. Computer simulations are valuable tools for analysis of investment outcomes, production
processes, scheduling, and maintenance activities.
Heuristic methods: Heuristic methods are sets of rules which, though perhaps not optimal, do facilitate
solutions of scheduling, layout, and distribution problems when applied in a consistent manner.
Network analysis techniques: Network approaches include decision trees, CPM, and PERT methods.
They are particularly helpful in identifying alternative courses of action and controlling research,
investment, and a multitude of project activities.
Utility: theory Utility or preference theory allows decision makers to incorporate their own experience
and values into a relatively formalized decision structure.
Game theory: Game theory helps decision makers to choose courses of action when there is absolutely
no information about what state of the environment will occur.
Flip coin: In spite of the "unscientific" nature of nipping a coin, random measures such as this are
widely used in situations where the decision makers are wholly indifferent.
22
www.AgriMoon.Com
System Engineering
Some decision-making aids are illustrated by reviewing three models useful for operations analysis: (1)
economic break-even analysis, (2) utility-based decisions, and (3) a production system schematic.
This economic model has facilitated industrial development by providing organizations with a
simplified profit-oriented goal structure that favours innovation, efficiency and growth.
Profits, of course, arise from the excess of total revenues (TR) over total costs (TC). Recognizing that
total costs are composed of both fixed costs (FC) and total variable costs (TVC), the profit function can
be expressed as:
Profit = TR - TC
Major cost categories often include direct labour, direct material, and overhead (or indirect production
expenses). The direct labor and direct material, plus some other items such as factory supplies, are
usually classified as variable costs because they typically change with the volume of production.
Supervision, taxes, office salaries, building depreciation, etc., are usually of a more fixed or semi-
variable nature. Fixed costs are essentially constant over a given range of output, but admittedly do
change over the long run as plant expansions are made, taxes change, and the like.
A break-even chart is a convenient way of graphically describing the relationship between costs and
revenues for different volumes of output. Fig.2. depicts this relationship over a range of volume where
total revenue increases linearly with each unit sold, and total cost reflects both an unavoidable fixed
cost plus a per unit variable cost. The break-even point (BEP) is that volume of output where the fixed
and variablecosts are just covered, but no profit exists. Thus at the BEP, the total revenues equal the
total costs (TR = TC). Recognizing that revenues reflect the price P charged per item times the volume
V sold, we can restate the TR = TC expression as:
P(V) = FC + VC(V)
23
www.AgriMoon.Com
System Engineering
Break-even analysis is simple and easy to visualize, and it condenses decision information into a form
that is readily understandable by almost anyone. Also, it is concerned with a vital aspect of free
enterprise of organizations—profitability. However, it is a technique based wholly upon economic
factors. It assumes one has complete knowledge about all the economic parameters, for the price, cost,
and demand data must eitlier be known for certain or assumed. Furthermore, the relationship between
these variables is assumed to follow a simple linear function which may be acceptable over short
ranges but often is really not satisfactory for longer-range decisions. Extrapolation to high outputs
involves an increasing amount of risk, for the model fails to account for any effects of decreasing
returns to scale as facilities become overloaded or markets become saturated.
Utility is the measure of preference that individuals have for various choices available to them. The
utility value of a given alternative is unique to individual decision makers and unlike a simple
monetary amount, can incorporate intangible factors or subjective standards from their own value
systems. Utility functions typically describe the relative preference value (in utils) that individuals have
for a given amount of the criterion (such as money, goods).
Operations management is the activity whereby resources, flowing within a defined system, are
combined and transformed in a controlled manner to add value in accordance with policies
communicated by management. Having discussed the key concepts of resources, systems,
transformation activities, and managerial policy, as well as the concept of models, let us now visualize
this definition in terms of a schematic model.
24
www.AgriMoon.Com
System Engineering
Production operations also exert an impact upon the social, political, ecological, and technological
environment of the firm. The economic results which flow to the public are another direct reflection of
the production activities. In essence, the model depicts flows of human, material, and capital resources
from the environment, through the transformation activities, and back to the environment. All flows
are accompanied by data and information which is used internally for control purposes and externally
for describing and modifying the role of the firm in its environment.
It is convenient to classify the material and equipment, human, and capital resource decisions primarily
as planning and organization decisions. They relate largely to the design or modification of the design
of the production system. The process analysis, forecasting, inventory control, production control,
quality control, maintenance and cost control decisions all relate to the operation of the production
system. These decisions have been broadly classified as direction and control decisions. Finally, an
increasingly important decision area pertains to environmental factors. In most cases, a discussion of
theory is followed by solved problems which illustrate applications of the management decision-
making methodology that is suitable for given problem situations.
25
www.AgriMoon.Com
System Engineering
26
www.AgriMoon.Com
System Engineering
9. Scheduling and
10. Quality control 11. Maintenance and cost control
control
27
www.AgriMoon.Com
System Engineering
4. SUMMARY
Operations managers are decision makers responsible for using human, material, and capital resources
to create valuable goods and services. Their work can be greatly facilitated by adopting a decision-
making-systems approach to managerial activities. This approach requires (1) a clear definition of the
system, (2) the establishment of criteria, (3) a formulation of relationships, (4) the generation of
alternatives, and (5) the choosing of a course of action based upon the criteria.
The key element of a decision-making activity often involves formulation of a model so that the
alternative courses of action can best be analyzed and evaluated. The actual structure of the model, of
course, depends upon the kind of information available and the prevailing level of certainty in the real
world. Techniques for making decisions under the various certainty-uncertainty conditions will be
used as relevant topics arise within the text. Three analytical aids for operations analysis were
discussed in this module. Break-even analysis assumes certainty and is generally limited in scope to
economic factors, but it is widely used. Utility theory is a newer and promising technique for uncertain
situations, but it is not yet widely accepted. It is one of the more formalized methods of incorporating
human values into the decision process. The production system model described in this chapter is
essentially a schematic "visualization" of the definition of operations management.
28
www.AgriMoon.Com
System Engineering
1.1 INTRODUCTION
The term operations Research was first coined in 1940 by McClosky and Trefthen in a small town,
Bowdsey, of the United Kingdom. This new science came into existence in military context. During
world war II, military management called on scientists from various disciplines and organized them
into teams to assist in solving strategic and tactical problems (ie) to discuss, evolve and suggest ways
and means to improve the execution of various military projects. By their joint efforts, experience and
deliberations, they suggested certain approaches that showed remarkable progress. This new approach
to systematic and scientific study of the operations of the system was called the Operations Research or
Operational Research (abbreviated as O.R).
During the year 1950, O.R achieved recognition as a subject worthy of academic study in the
Universities. Since then, the subject has been gaining more and more importance for students of
Economics, Management, Public Administration, Behavioral Sciences, Social work, Mathematics,
Commerce and Engineerin
Operations Research Society of America was formed in 1950 and in 1957 the International Federation of
O.R Societies was established. In several Countries, International Scientific Journals in O.R began to
appear in different languages. The primary journals are Operations Research, Transportation Science,
Management Sciences, Operational Research Quarterly, Journal of the Canadian Operational Research
Society, Mathematics of Operational Research, International journal of Game Theory etc.
In India, Operational Research came into existence in 1949 with the opening of an Operational Research
Unit at the Regional Research Laboratory at Hyderabad. In 1953, an Operational Research Unit was
established in the Indian Statistical Institute, Calcutta for the application of Operational Research
methods in national planning & survey . Operational Research Society of India was formed in 1957. It
became a member of the International Federation of Operational Research Societies in 1959. The first
Conference of Operational Research Society of India was held in Delhi in 1959. Operational Research
Society of India started a journal ―Opsearch‖ in 1963. Other journals which deal with Operational
Research are : Journal of the National Productivity Council, Materials Management journal of India and
the Defence Science journal.
1.3 Definition
Because of the wide scope of applications of Operational Research, giving a precise definition is
difficult. However, a few definitions of Operational Research are as under :
1. ―Operational Research is the application of scientific methods, techniques and tools to problems
involving the Operations of a system so as to provide those in control of the system with
optimum solutions to the problem‖.
- C.W.Churchman, R.L.Ackoff & E.L.Arnoff
29
www.AgriMoon.Com
System Engineering
1. ―Operational Research is the art of giving bad answers to problems which otherwise have
worse answers‖.
- T.L.Saaty
Types of Models
There are many ways to classify models and therefore, the decision-maker must identify which
type of model best suits the decision problem.
Physical Models
These models provide a physical appearance of the real object under study either reduced in size or
scaled up physical models are useful only in design problems because they are easy to observe, build
and describe.
1. Iconic models:Iconic model retain some of the physical properties and characteristics of
the system they represent.
2. Analogue models : The models represent a system by the set of properties different
from that of the original system and does not resemble physically.
Symbolic Models
These models use letters, numbers and other symbols to represent the properties of the system.
These models simply describe some aspects of a situation, based on observation, survey, questionnaire
results or other available data of a situation and do not predict or recommend.
Predictive Models
These models are used to predict the outcomes due to a given set of alternatives for problem. These
models do not have an objective function as a part of the model to evaluate decision alternatives.
30
www.AgriMoon.Com
System Engineering
Optimization Models
These models provide the ‗best‘ or ‗optimal‘ solution to problems subject to certain limitations of
the use of resources.
Static Models
Static models present a system at some specified time and do not account for changes over time.
Dynamic Models
In a dynamic model, time is considered as one of the variables and admit the impact of changes
generated by time in the selection of the optimal courses of action.
Deterministic Models
If all the parameters, constants and functional relationships are assumed to be known with certainty
when the decision is made, then the model is said to be deterministic. For a specific set of input values,
there is a uniquely determined output which represents the solution of the model under conditions of
certainty.
Models in which atleast one parameter or decision variable is a random variable are called probabilistic
(or Stochastic) models. Since atleast one decision variable is random, therefore, an independent
variable which is the function of dependent variable(s) will also be random. This means consequences
or payoff due to certain changes in the independent variable cannot be predicted with certainty.
However, it is possible to predict a pattern of values of both the variable by their probability
distribution.
Analytical Models
These models have a specific mathematical structure and thus can be solved by known analytical or
mathematical techniques. Any optimization model ( which requires maximization or minimization of
an objective function) is an analytical model.
Simulation Models
These models also have a mathematical structure but are not solved by applying mathematical
structure but are not solved by applying mathematical techniques to get a solution. Instead, a
simulation model is essentially a computer assisted experimentation on a mathematical structure of a
real-life problem in order to describe and evaluate its behavior under certain assumptions over a
period of time.
31
www.AgriMoon.Com
System Engineering
It is essential to follow some steps that everybody agrees as being helpful in planning, organizing,
directing and controlling Operations Research activities within an organization. The steps are listed
below :
1. Formulation of the problem : It involves analysis of the physical system, setting-up of objectives,
determination of restriction constraints against which decision should be adopted, alternative courses
of action and measurement of effectiveness.
2. Construction of a Mathematical model : After formulation of the problem, the next step is to
express all the relevant variables (activities) of the problem into a mathematical model. A generalized
mathematical model might take the form :
E = f(xi, yj )
3. Deriving the solution from the model : Once the mathematical model is formulated, the next step is
to determine the values of decision variables that optimize the given objective function. This deals
with the mathematical calculations for obtaining the solution to the model.
4. Validity of the model : The model should be validated to measure its accuracy. A model is valid or
accurate if (a) it contains al the objectives, constraints, and decision variables relevant to the
problem,(b) the objectives, constraints, and decision variables included in the model are all relevant to,
or actually part of the problem, and (c) the functional relationships are valid.
5. Establishing control over the solution : After testing the model and its solution, the next step of the
study is to establish control over the solution, by proper feedback of the information on variables
which deviated significantly, the solution goes out of control. In such situation the model may
accordingly be modified.
32
www.AgriMoon.Com
System Engineering
6. Implementation of the final results : Finally, the tested results of the model are implemented to
work. This would basically involve a careful explanation of the solution to be adopted and its
relationship with the operating realities. This stage of Operations Research investigation is executed
primarily through the cooperation of both the operations Research experts and those who are
responsible for managing and operating the system.
Operations Research is mainly concerned with the techniques of applying scientific knowledge, besides
the development of science. It provides an understanding which gives the expert/manager new
insights and capabilities to determine better solutions in his decision-making problems, with great
speed, competence and confidence. In recent years, Operations Research has successfully entered
many different areas of research in Defence, Government, Service Organizations and Industry. We
briefly describe some applications of Operations Research in the functional areas of management:
1. Cash flow analysis, long range capital requirements, dividend policies, investment portfolios.
2. Credit policies, credit risks and delinquent account procedures.
3. Claim and complain procedure.
Marketing
33
www.AgriMoon.Com
System Engineering
Uses
1. Optimum use of production factors. Linear programming techniques indicate how a manager
can most effectively employ his production factors by more efficiently selecting and distributing
these elements.
2. Improved quality of decision. The computation table gives a clear picture of the happenings
within the basic restrictions and the possibilities of compound behavior of the elements
involved in the problem. The effect on the profitability due to changes in the production
pattern will be clearly indicated in the table, e.g., simplex table.
3. Preparation of future managers. These methods substitute a means for improving the
knowledge and skill of young managers.
4. Modification of mathematical solution. Operations Research presents a possible practical
solution when one exists, but it is always a responsibility of the manager to accept or modify the
solution before its use. The effect of these modifications may be evaluated from the
computational steps and tables.
5. Alternative solutions. Operations Research techniques will suggest all the alternative solutions
available for the same profit so that the management may decide on the basis of its strategies.
Limitations of Operations Research
Operations Research has certain limitations. However, these limitations are mostly related to the time
and money factors involved in its applications rather than its practical utility. These limitations are as
follows :
a) Magnitude of computation. Operations Research tries to find out the optimal solution taking all the
factors into account. In the modern society, these factors are numerous and expressing them in
quantity and establishing relationship among these, requires huge calculations. All these calculations
cannot be handled manually and require electronic computers which bear very heavy cost. Thus, the
use of Operations Research is limited only to very large organizations.
b) Absence of quantification. Operations Research provides solution only when all the elements related
to a problem can be quantified. The tangible factors such as price, product, etc., can be expressed in
terms of quantity, but intangible factors such as human relations etc, cannot be quantified. Thus, these
intangible elements of the problem are excluded from the study, though these might be equally or more
important than quantifiable intangible factors as far as possible.
c) Distance between managers and Operations Research. Operations Research, being specialists‘ job,
requires a mathematician or a statistician, who might not be aware of the business problems. Similarly,
a manager may fail to understand the complex working of Operations Research. Thus, there is a gap
between one who provides the solution and one who uses the solution.
34
www.AgriMoon.Com
System Engineering
The linear programming involving more than two variables may be expressed as follows :
................................
Note : Some of the constraints may be equalities, some others may be inequalities of (£) type or (³) type
or all of them are of same type.
Solution: A set of values x1, x2 ...xn which satisfies the constraints of the LPP is called its solution.
Feasible solution: Any solution to a LPP which satisfies the non-negativity restrictions of the LPP is
called its feasible solution.
Optimum Solution or Optimal Solution: Any feasible solution which optimizes (maximizes or
minimizes) the objective function of the LPP is called its optimum solution or optimal solution.
............(1)
then the non-negative variables si which are introduced to convert the inequalities (1) to the equalities
are called slack variables. The value of these variables can be interpreted as the amount of unused
resource.
35
www.AgriMoon.Com
System Engineering
............(2)
then the non-negative variables si which are introduced to convert the inequalities (1) to the equalities
are called surplus variables. The value of these variables can be interpreted as the amount over and
above the required level.
After the formulation of LPP, the next step is to obtain its solution. But before any method is used to
find its solution, the problem must be presented in a suitable from. Two forms are dealt with here, the
canonical form and the standard form.
The canonical form : The general linear programming problem can always be expressed in the
following form :
Maximize Z = c1 x1 + c2 x2 + c3 x3 + ... cn xn
.................................
Subject to AX ≤ b (constraints)
36
www.AgriMoon.Com
System Engineering
(ii) All constraints are of (≤) type, except for the non-negative restrictions.
An inequality of ―≥‖ type can be changed to an inequality of the type ―≤‖ type by multiplying both
sides of the inequality y -1.
is equivalent to
For example
is equivalent to
A variable which is unrestricted in sign is equivalent to the difference between two non-negative
variables. Thus if xj is unrestricted in sign, it can be replaced by (xjl- xjll), where xjland xjll are both non-
negative,
37
www.AgriMoon.Com
System Engineering
Maximize or Minimize
Z = c1 x1 + c2 x2 + …….. + cn xn
.....................................................................
Where, c = (c1,c2,…,cn),
1. All the constraints are expressed in the form of equations, except for the non-negative
restrictions.
The inequalities can be changed into equation by introducing a non-negative variable on the left hand
side of such constraint. It is to be added (slack variable) if the constraint is of ― ≤ ‖ type and subtracted
(surplus variable) if the constraint is of ― ≥ ‖ type.
38
www.AgriMoon.Com
System Engineering
Basic Solution.: Given a system of m simultaneous linear equations with n variables (m < n).
Ax=b, xT ε Rn
The m variables, which may be all different from zero, are called basic variables. The m x m non-
singular sub matrix B called a basis matrix with the columns of B as basis vectors. The (n-m) variables
which are put to zero are called as non-basic variables.
Example:
Obtain all the basic solutions to the following system of linear equation:
x1 + 2x2 + x3 = 4
2x1 + x2 + 5x3 = 5
Solution:
Ax=b
where,
since rank of A is 2, the maximum number of linearly independent columns of A is 2. Thus we can take
any of the following, 2x 2 sub-matrices as basis matrix B:
The variables not associated with the columns of B are x3, x2 and x1 respectively, in the three different
cases.
A basic solution to the given system is now obtained by setting x3 = 0, and solving the system
39
www.AgriMoon.Com
System Engineering
We observe that all the above three basic solutions are non-degenerate solution.
Degenerate Basic Solution: A basic solution is said to be a degenerate basic solution if one or more of
the basic variables are zero.
Basic Feasible Solution: A feasible solution to a LPP., which is also a basic solution to the problem is
called a basic feasible solution to the LPP.
40
www.AgriMoon.Com
System Engineering
MODULE 3. Mathematical formulation of Linear programming problems and its Graphical solution
1.1 INTRODUCTION
In fact, the most difficult problem in the application of management science is the formulation of a
model. Therefore, it is important to consider model formulation before launching into the details of
linear programming solution. Model formulation is the process of transforming a real word decision
problem into an operations research model. In the sections that follow, we give several Lilliputian
examples so that you can acquire some experience of formulating a model. All the examples that we
provide in the following sections are of static models, because they deal with decisions that occur only
within a single time period
1.2 ALGORITHM:
The procedure for mathematical formulation of linear programming problem consists of the following
major steps:
Step2: Formulate the objective function to be optimized (maximized or minimized) as a linear function
of the decision variables.
Step3: Formulate the other conditions of the problem such as resource limitations, market constraints
,inter-relation between variables etc. as linear equations or in equations in terms of the decision
variables.
Step4: Add the ‗Non-negativity‘ constraint from the consideration that negative values of the
decision variables do not have any valid physical interpretation
The objective function, the set of constraints and the non-negative constraint together form a Linear
Programming Problem.
Ex1:
(Production allocation problem). A manufacturer produces two types of models M 1 and M2.Each
M1 model requires 4 hours of grinding and 2 hours of polishing; whereas each M2 model requires 2
hours of grinding and 5 hours of polishing. The manufacturer has 2 grinders and 3 polishers. Each
grinder works for 40 hours a week and each polisher works for 60 hours a week. Profit on an
M1 model is Rs 3.00 and on an M2 model is Rs. 4.00. Whatever is produced in a week is sold in the
market. How should the manufacturer allocate his production a week is sold in the market. How
should the manufacturer allocate his production capacity to the two types of models so that he may
make the maximum profit in a week ?
41
www.AgriMoon.Com
System Engineering
Solution:
Here is a real situation from an industry. The manufacturer can, if he so chooses, produce only model
M2 , but then his grinders would be idle and his profits may be maximum. This is only a guess. To be
definite, we must tell how many M1 models and how many M2 models should be produced per week,
in order that his profits may be maximum.
Mathematical Formulation
Objective function: The objective of the manufacturer is to determine the number of M1 and
M2 models so as to maximize the total profit.
Z= 3x1 + 4x2
Constraints: For grindinding since each M1 model requires 4 hours and each M2 model requires 2 hours
the total number of grinding hours needed per week is given by 4x1 + 2x2.
Similarly for polishing, the total number of polishing hours needed per week is 2x1+5x2
Further, since the manufacturer does not have more than 2 x 40(=80) hours of grinding and 3x60(=180)
hours of polishing, the time constraints are
Non- negativity constraints: Since the production of negative number of models is meaningless, we
must have x1 ≥ 0 and x2 ≥ 0
Hence, the manufacturer‘s allocation problem can be put in the following mathematical form:
1. 4x1 + 2x2 ≤ 80
3. x1≥ 0 , x2 ≥ 0
Ex .2: Universal Corporation manufactures two products- P1 and P2. The profit per unit of the two
products is Rs. 50 and Rs. 60 respectively. Both the products require processing in three machines.
The following table indicates the available machine hours per week and the time required on each
42
www.AgriMoon.Com
System Engineering
machine for one unit of P1 and P2. Formulate this product mix problem in the linear programming
form.
Available Time
Product
(in machine hours per week)
Machine
P1 P2
1 2 1 300
2 3 4 509
3 4 7 812
Solution:
Let x1 and x2 be the amounts manufactured of products P1 and P2 respectively. The objective here is
to maximize the profit, which is given by the linear function
Since one unit of product P1 requires two hours of processing in machine 1, while the corresponding
requirement of P2 is one hour, the first constraint can be expressed as
2x1 + x2 ≤ 300
In addition, there cannot be any negative production that may be stated algebraically as
x1 ≥ 0, x2 ≥ 0
(A variable that is also allowed to assume negative values is said to be unrestricted in sign.)
The problem can now be stated in the standard linear programming form as
subject to
43
www.AgriMoon.Com
System Engineering
2x1 + x2 ≤ 300
3x1 + 4x2 ≤ 509
4x1 + 7x2 ≤ 812
x1≥ 0, x2 ≥ 0
Ex.3: The Best Stuffing Company manufactures two types of packing tins- round & flat. Major
production facilities involved are cutting and joining. The cutting department can process 200 round
tins or 400 flat tins per hour. The joining department can process 400 round tins or 200 flat tins per
hour. If the contribution towards profit for a round tin is the same as that of a flat tin, what is the
optimal production level?
Solution:
Let
Since the contribution towards profit is identical for both the products, the objective function can be
expressed as x1 + x2. Hence, the problem can be formulated as
Maximize Z = x1 + x2
subject to
(1/200)x1 + (1/400)x2 ≤ 1
(1/400)x1 + (1/200)x2 ≤ 1
x1≥ 0, x2 ≥ 0
x1 ≥ 0, x2 ≥ 0
44
www.AgriMoon.Com
System Engineering
2.1 INTRODUCTION
Linear programming problems with two decision variables can be easily solved by graphical method.
A problem of three dimensions can also be solved by this method, but their graphical solution becomes
complicated.
Thus, the collection of feasible solutions in a linear programming problem form a convex set
2. Treat inequalities as equalities and then draw the lines corresponding to each equation and non-
negativity restrictions.
45
www.AgriMoon.Com
System Engineering
4. Determine the value of the objective function corresponding to the end points determined in
step 3.
subject to
x1, x2 ≥ 0
x1, x2 ≥ 0
The remaining three constraints are not affecting the feasible region in any manner. Such constraints
are called redundant constraints.
46
www.AgriMoon.Com
System Engineering
Example 1.
Maximize z = 18x1 + 16x2
subject to
x1, x2 ≥ 0
Solution:
If only x1 and no x2 is produced, the maximum value of x1 is 375/15 = 25. If only x2 and no x1 is
produced, the maximum value of x2 is 375/25 = 15. A line drawn between these two points (25, 0) & (0,
15), represents the constraint factor 15x1 + 25x2≤ 375. Any point which lies on or below this line will
satisfy this inequality and the solution will be somewhere in the region bounded by it.
Similarly, the line for the second constraint 24x1 + 11x2≤ 264 can be drawn. The polygon oabc represents
the region of values for x1 & x2 that satisfy all the constraints. This polygon is called the solution set.
47
www.AgriMoon.Com
System Engineering
The end points (corner points) of the shaded area are (0,0), (11,0), (5.7, 11.58) and (0,15). The values of
the objective function at these points are 0, 198, 288 (approx.) and 240. Out of these four values, 288 is
maximum.
The optimal solution is at the extreme point b, where x1 = 5.7 & x2 = 11.58, and z = 288.
Example 2
Maximize z = 6x1 - 2x2
subject to
2x1 - x2 ≤ 2
x1 ≤ 3
x1, x2 ≥ 0
Solution.
First, we draw the line 2x1 - x2 ≤ 2, which passes through the points (1, 0) & (0, -2). Any point which lies
on or below this line will satisfy this inequality and the solution will be somewhere in the region
bounded by it.
Similarly, the line for the second constraint x1 ≤ 3 is drawn. Thus, the optimal solution lies at one of the
corner points of the dark shaded portion bounded by these straight lines.
48
www.AgriMoon.Com
System Engineering
The linear programming problems discussed in the previous section possessed unique solutions. This
was because the optimal value occurred at one of the extreme points (corner points). But situations may
arise, when the optimal solution obtained is not unique. This case may arise when the line representing
the objective function is parallel to one of the lines bounding the feasible region. The presence of
multiple solutions is illustrated through the following example.
Example:
Maximize z = x1 + 2x2
subject to
x1 ≤ 80
x2 ≤ 60
5x1 + 6x2 ≤ 600
x1 + 2x2 ≤ 160
x1, x2 ≥ 0.
In the above figure, there is no unique outer most corner cut by the objective function line. All points
from P to Q lying on line PQ represent optimal solutions and all these will give the same optimal value
(maximum profit) of Rs. 160. This is indicated by the fact that both the points P with co-ordinates (40,
60) and Q with co-ordinates (60, 50) are on the line x1 + 2x2 = 160. Thus, every point on the line PQ
maximizes the value of the objective function and the problem has multiple solutions.
49
www.AgriMoon.Com
System Engineering
In some cases, there is no feasible solution area, i.e., there are no points that satisfy all constraints of the
problem. An infeasible LP problem with two decision variables can be identified through its graph. For
example, let us consider the following linear programming problem.
subject to
x1, x2 ≥ 0
The region located on the right of PQR includes all solutions, which satisfy the first and the third
constraints. The region located on the left of ST includes all solutions, which satisfy the second
constraint. Thus, the problem is infeasible because there is no set of points that satisfy all the three
constraints.
It is a solution whose objective function is infinite. If the feasible region is unbounded then one or more
decision variables will increase indefinitely without violating feasibility, and the value of the objective
function can be made arbitrarily large. Consider the following model:
subject to
2x1+ x2 ≥ 70
x1 + x2 ≥ 40
x1 + 3x2 ≥ 90
x1, x2 ≥ 0
50
www.AgriMoon.Com
System Engineering
The point (x1, x2) must be somewhere in the solution space as shown in the figure by shaded portion.
The three extreme points (corner points) in the finite plane are:
P = (90, 0); Q = (24, 22) and R = (0, 70) The values of the objective function at these extreme points are:
Z(P) = 3600, Z(Q) = 2280 and Z(R) = 4200.
In this case, no maximum of the objective function exists because the region has no boundary for
increasing values of x1 and x2. Thus, it is not possible to maximize the objective function in this case and
the solution is unbounded.
Note:
Single objective: Linear programming takes into account a single objective only, i.e., profit
maximization or cost minimization. However, in today's dynamic business environment, there
is no single universal objective for all organizations.
Certainty: Linear Programming assumes that the values of co-efficient of decision variables are
known with certainty.
Due to this restrictive assumption, linear programming cannot be applied to a wide variety of
problems where values of the coefficients are probabilistic.
Divisibility: In linear programming, the decision variables are allowed to take non-negative
integer as well as fractional values. However, we quite often face situations where the planning
51
www.AgriMoon.Com
System Engineering
models contain integer valued variables. For instance, trucks in a fleet, generators in a
powerhouse, pieces of equipment, investment alternatives and there are a myriad of other
examples. Rounding off the solution to the nearest integer will not yield an optimal solution. In
such cases, linear programming techniques cannot be used.
Summary:
This chapter initiated your study of linear models. Linear programming is a fascinating topic in
operations research with wide applications in various problems of management, economics, finance,
marketing, transportation and decision making pertaining to the operations of virtually any private or
public organization. Unquestionably, linear programming techniques are among the most
commercially successful applications of operations research.
In this chapter, you learned how to formulate a linear programming problem, and then we discussed
the graphical method of solving an LPP with two decision variables.
52
www.AgriMoon.Com
System Engineering
1.1 Introduction
Simplex method was developed by George B. Datzing in 1947 is an iterative and an efficient method for
solving linear programming problems. It is an algebraic procedure that starts at a feasible extreme
point of the simplex(or convex), normally the origin, and systematically moves from one feasible
extreme point to another until an optimum(or optimal) extreme point is located. At each iteration, the
procedure tests the one extreme (corner) point for optimality, and if not optimum, chooses another
extreme point, of the convex set that is formed by the constraints and non-negativity conditions of the
linear programming problem. Since the number of extreme points (i.e., corners or vertices) of the
convex set of all feasible solutions is finite, the method leads to the optimum extreme point (i.e.,
optimum or optimal solution) in a finite number of steps or indicates that there exists an unbounded
solution.
Slack Variable:
It is a variable that is added to the left-hand side of a less than or equal to type constraint to convert the
constraint into an equality. In economic terms, slack variables represent left-over or unused capacity.
Specifically:
can be written as
ai1x1 + ai2x2 + ai3x3 + .........+ ainxn + si = bi
Where i = 1, 2, ..., m
Surplus variable:
It is a variable subtracted from the left-hand side of a greater than or equal to type constraint to convert
the constraint into equality. It is also known as negative slack variable. In economic terms, surplus
variables represent over fulfillment of the requirement.
Specifically:
ai1x1 + ai2x2 + ai3x3 + .........+ ainxn ≥ bi
can be written as
ai1x1 + ai2x2 + ai3x3 + .........+ ainxn - si = bi
Where i = 1, 2, ..., m
53
www.AgriMoon.Com
System Engineering
Artificial variable:
It is a non negative variable introduced to facilitate the computation of an initial basic feasible solution.
In other words, a variable added to the left-hand side of a greater than or equal to type constraint to
convert the constraint into equality is called an artificial variable.
The general formulation of L.P.P can always be put in the following form:
x1,x2,x3,....xn ≥ 0
by making use of some elementary transformations. This form of L.P.P. is called the canonical form of
L.P.P.
If we have the objective function as min z then change that as min z = -Max (-z ).
(ii) All the constraints are of the “≤ “type, except for the non-negative restriction
If we have an inequality of ―≥‖ type, multiply both sides by -1. if the constraints is an equation say
ai1x1 + ai2x2+………ainxn = bi
write it as
If a variable is unrestricted in sign ((i.e.) positive, negative or zero) then replace that variable by
difference between two non-negative variables. If xj is unrestricted in sign replace xj by xj = where both
and are both non-negative.
54
www.AgriMoon.Com
System Engineering
AX ≤ b, X ≥ 0 (Non-negative restrictions)
The general formulation of L.P.P can always be put in the following form:
x1,x2,x3,....xn ≥ 0
(ii) All the constraints are expressed in the form of equations except for the non-negative
constraints.
If the constraints are of ―≤‖ type add the slack variable to the left hand side and if the constraints are
of ―≥‖ type subtract surplus variable to the left hand side.
AX = b, X ≥ 0 (Non-negative restrictions)
55
www.AgriMoon.Com
System Engineering
Given a system of m linear equations with n variables (m < n). The solution obtained by setting (n – m)
variables equal to zero and solving for the remaining m variables is called a basic solution.
The m variables are called basic variables and they form the basic solution. The n-m variables which
are put to zero are called as non-basic variables.
A basic solution is said to be a degenerate basic solution if one or more of the basic variables are zero.
Assuming the existence of an initial basic feasible solution, an optimal solution to any L.P.P by simplex
method is found as follows:
Step 2: Check whether all bi‘s are positive. If any of the bi‘s is negative, multiply both sides of that
constraint by -1 so as to make its right hand side positive.
Step 3: By introducing slack / surplus variables, convert the inequality constraints into equations and
express the given L.P.P into its standard form.
Step 4: Find an initial basic feasible solution and express the above information conveniently in the
following simplex table.
56
www.AgriMoon.Com
System Engineering
Step 5: Compute the net evaluations Zj –Cj (j= 1,2,3…..n) by using the relation
Zj –Cj = CBaj- Cj
b) If atleast Zj –Cj < 0 then the current basic solution XB is not optimal, go to next step.
The entering variable is the non-basic variable corresponding to the most negative value Zj –Cj. Let it be
xr for some j = r. The entering variable column is known at the bottom. If more than one variable has
the same most negative Zj –Cj, any of these variables may be selected arbitrarily as the entering
variable.
57
www.AgriMoon.Com
System Engineering
(i.e) the ratio between the solution column and the entering variable column by considering only the
positive denominators.
b) If all air > 0, then the leaving variable is the basic variable corresponding to the minimum ratio θ. If,
then the basic variable xk leaves the basis. The leaving variable row is called the key row or pivot
row or pivot equation and the element at the intersection of the pivot column and pivot row is called
the pivot element or key element or leading element.
Step 8:
Drop the leaving variable and introduce the entering variable along with its associated value under
CB column. Convert the pivot element to unity by dividing the pivot equation by the pivot element and
all other elements in its column to zero by making use of
Step 9: Go to step 5 and repeat the procedure until either an optimum solution is obtained or there is an
indication of an unbounded solution.
Example:
Maximize z = 3x1 + 2x2
Subject to
-x1 + 2x2 ≤ 4
3x1 + 2x2 ≤ 14
x1 – x2 ≤ 3
x1, x2 ≥ 0
Solution:
First, convert every inequality constraints in the LPP into an equality constraint, so that the problem
can be written in a standard from. This can be accomplished by adding a slack variable to each
constraint. Slack variables are always added to the less than type constraints.
58
www.AgriMoon.Com
System Engineering
-x1 + 2x2 + x3 = 4
3x1 + 2x2 + x4 = 14
x1 – x2 + x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Since slack variables represent unused resources, their contribution in the objective function is zero.
Including these slack variables in the objective function, we get
When we are not producing anything, obviously we are left with unused capacity
x3 = 4, x4 = 14, x5 =
We note that the current solution has three variables (slack variables x3, x4 and x5) with non-zero
solution values and two variables (decision variables x1 and x2) with zero values. Variables with non-
zero values are called basic variables. Variables with zero values are called non-basic variables.
Iteration 1:
cj 3 2 0 0 0
Solution
Basic variables
cB x1 x2 x3 x4 x5 values
B
b (=XB)
0 x3 -1 2 1 0 0 4
0 x4 3 2 0 1 0 14
0 x5 1 -1 0 0 1 3
zj-cj -3 -2 0 0 0
59
www.AgriMoon.Com
System Engineering
z1 – c1 = (0 × (-1) + 0 × 3 + 0 × 1) - 3 = -3
z2 – c2 = (0 × 2 + 0 × 2 + 0 × (-1)) - 2 = -2
z3 – c3 = (0 × 1 + 0 × 0 + 0× 0) - 0 = 0
z4 – c4 = (0 × 0 + 0 × 1 + 0 × 0) - 0 = 0
z5 – c5 = (0 × 0 + 0×0 + 0×1) – 0 = 0
Choose the smallest negative value from zj – cj (i.e., – 3). So column under x1 is the key column.
Now find out the minimum positive value
Minimum (14/3, 3/1) = 3
So row x5 is the key row.
Here, the pivot (key) element = 1 (the value at the point of intersection).
Therefore, x5 departs and x1 enters.
We obtain the elements of the next table using the following rules:
1. If the values of zj – cj are positive, the inclusion of any basic variable will not increase the
value of the objective function. Hence, the present solution maximizes the objective
function. If there are more than one negative values, we choose the variable as a basic
variable corresponding to which the value of zj – cj is least (most negative) as this will
maximize the profit.
2. The numbers in the replacing row may be obtained by dividing the key row elements by
the pivot element and the numbers in the other two rows may be calculated by using the
formula:
x4 row
a21 = 3 – 1× (3/1) = 0
a22 = 2 – (-1) × (3/1) = 5
60
www.AgriMoon.Com
System Engineering
a23 = 0 – 0 × (3/1) = 0
a24 = 1 – 0 × (3/1) = 1
a25 = 0 – 1 × (3/1) = -3
b2 = 14 – 3 × (3/1) = 5
x1 row
a31 = 1/1 = 1
a32 = -1/1 = -1
a33 = 0/1 = 0
a34 = 0/1 = 0
a35 = 1/1 = 1
b3 = 3/1 = 3
Iteration 2:
cj 3 2 0 0 0
Solution
cB Basic variables B x1 x2 x3 x4 x5 values
b (= XB)
0 x3 0 1 1 0 1 7
0 x4 0 5 0 1 -3 5
3 x1 1 -1 0 0 1 3
zj-cj 0 -5 0 0 3
z1 – c1 = (0 × 0 + 0 × 0 + 3 × 1) - 3 = 0
z2 – c2 = (0 × 1 + 0 × 5 + 3 × (-1)) – 2 = -5
z3 – c3 = (0 × 1 + 0 × 0 + 3 × 0) - 0 = 0
z4 – c4 = (0 × 0 + 0 × 1 + 3 × 0) - 0 = 0
z5 – c5 = (0 × 1 + 0 × (-3) + 3 × 1) – 0 = 3
61
www.AgriMoon.Com
System Engineering
x3 row
a11 = 0 – 0× (1/5) = 0
a12 = 1 – 5 × (1/5) = 0
a13 = 1 – 0 × (1/5) = 1
a14 = 0 – 1× (1/5) = -1/5
a15 = 1 – (-3) × (1/5) = 8/5
b1 = 7 – 5 × (1/5) = 6
x2 row
a21 = 0/5 = 0
a22 = 5/5 = 1
a23 = 0/5 = 0
a24 = 1/5
a25 = -3/5
b2 = 5/5 = 1
x1 row
a31 = 1 – 0 × (-1/5) = 1
a32 = -1 – 5× (-1/5) = 0
a33 = 0 – 0 × (-1/5) = 0
a34 = 0 – 1 × (-1/5) = 1/5
a35 = 1 – (-3) × (-1/5) = 2/5
b3 = 3 – 5 × (-1/5) = 4
Note: Don't convert the fractions into decimals, because many fractions cancel out during the process
while the conversion into decimals will cause unnecessary complications.
Final iteration:
cj 3 2 0 0 0
Solution
Basic variables
cB x1 x2 x3 x4 x5 values
B
b (= XB)
0 x3 0 0 1 -1/5 8/5 6
2 x2 0 1 0 1/5 -3/5 1
62
www.AgriMoon.Com
System Engineering
3 x1 1 0 0 1/5 2/5 4
zj-cj 0 0 0 1 0
Result:
Since all the values of zj – cj are positive, this is the optimal solution.
x1 = 4, x2 = 1
Max z = 3 X 4 + 2 X 1 = 14.
The largest profit of Rs.14 is obtained, when 1 unit of x2 and 4 units of x1 are produced. The above
solution also indicates that 6 units are still unutilized, as shown by the slack variable x3 in the
XB column.
Minimization Case:
In the previous section, the simplex method was applied to linear programming problems where the
objective was to maximize the profit with less than or equal to type constraints. In many cases,
however, constraints may of type ≥ or = and the objective may be minimization (e.g., cost, time, etc.).
Thus, in such cases, simplex method must be modified to obtain an optimal policy.
subject to
Any linear minimization problem can be viewed as an equivalent linear maximization problem,
and vice versa.
It can be written as
63
www.AgriMoon.Com
System Engineering
….................................................................
am1x1 + am2x2 + am3x3 + .........+ amnxn - sm = bm
x1, x2,....., xn ≥ 0
s1, s2,....., sm ≥ 0
-s1 = b1 or s1 = -b1
-s2 = b2 or s2 = -b2
..............................
-sm = bm or sm = -bm
which is not feasible because it violates the non-negativity stipulation, (i.e., s1≥ 0). Therefore, we need
artificial variables.
x1, x2,....., xn ≥ 0
s1, s2,....., sm ≥ 0
A1, A2,....., Am ≥ 0
Now, an initial basic feasible solution can be obtained by setting all the decision and surplus variables
to zero. Thus, an initial basic feasible solution to LPP is
A1 = b1 , A2 = b2, ....., Am = bm
Now to obtain an optimal solution, we must drive out the artificial variables. The two methods to solve
linear programming problems in such cases are:
Big-M- method
Solution methods to LP problems with integer or Boolean variables are still far less efficient
than those which include continuous variables only.
64
www.AgriMoon.Com
System Engineering
Example:
Maximize z = 3x1 + 2x2
Subject to
-x1 + 2x2 ≤ 4
3x1 + 2x2 ≤ 14
x1 – x2 ≤ 3
x1, x2 ≥ 0
Solution:
First, convert every inequality constraints in the LPP into an equality constraint, so that the problem
can be written in a standard from. This can be accomplished by adding a slack variable to each
constraint. Slack variables are always added to the less than type constraints.
-x1 + 2x2 + x3 = 4
3x1 + 2x2 + x4 = 14
x1 – x2 + x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Since slack variables represent unused resources, their contribution in the objective function is zero.
Including these slack variables in the objective function, we get
Now we assume that nothing can be produced. Therefore, the values of the decision variables are zero.
x1 = 0, x2 = 0, z = 0
When we are not producing anything, obviously we are left with unused capacity
x3 = 4, x4 = 14, x5 = 3
We note that the current solution has three variables (slack variables x3, x4 and x5) with non-zero
solution values and two variables (decision variables x1 and x2) with zero values. Variables with non-
zero values are called basic variables. Variables with zero values are called non-basic variables.
65
www.AgriMoon.Com
System Engineering
Iteration 1:
cj 3 2 0 0 0
Basic Solution
cB variables x1 x2 x3 x4 x5 values
B b (=XB)
0 x3 -1 2 1 0 0 4
0 x4 3 2 0 1 0 14
0 x5 1 -1 0 0 1 3
zj-cj -3 -2 0 0 0
Choose the smallest negative value from zj – cj (i.e., – 3). So column under x1 is the key column.
Now find out the minimum positive value
We obtain the elements of the next table using the following rules:
1. If the values of zj – cj are positive, the inclusion of any basic variable will not increase the value
of the objective function. Hence, the present solution maximizes the objective function. If there
are more than one negative values, we choose the variable as a basic variable corresponding to
which the value of zj – cj is least (most negative) as this will maximize the profit.
66
www.AgriMoon.Com
System Engineering
2. The numbers in the replacing row may be obtained by dividing the key row elements by the
pivot element and the numbers in the other two rows may be calculated by using the formula:
x3 row
a11 = -1 – 1 x ((-1)/1) = 0
a12 = 2 – (-1) x ((-1)/1) = 1
a13 = 1 – 0 x ((-1)/1) = 1
a14 = 0 – 0 x ((-1)/1) = 0
a15 = 0 – 1 x ((-1)/1) = 1
b1 = 4 – 3 x ((-1)/1) = 7
x4 row
a21 = 3 – 1 x (3/1) = 0
a22 = 2 – (-1) x (3/1) = 5
a23 = 0 – 0 x (3/1) = 0
a24 = 1 – 0 x (3/1) = 1
a25 = 0 – 1 x (3/1) = -3
b2 = 14 – 3 x (3/1) = 5
x1 row
a31 = 1/1 = 1
a32 = -1/1 = -1
a33 = 0/1 = 0
a34 = 0/1 = 0
a35 = 1/1 = 1
b3 = 3/1 = 3
Iteration 2:
cj 3 2 0 0 0
Solution
cB Basic variables B x1 x2 x3 x4 x5 values
b (= XB)
0 x3 0 1 1 0 1 7
67
www.AgriMoon.Com
System Engineering
0 x4 0 5 0 1 -3 5
3 x1 1 -1 0 0 1 3
zj-cj 0 -5 0 0 3
x3 row
a11 = 0 – 0 x (1/5) = 0
a12 = 1 – 5 x (1/5) = 0
a13 = 1 – 0 x (1/5) = 1
a14 = 0 – 1 x (1/5) = -1/5
a15 = 1 – (-3) x (1/5) = 8/5
b1 = 7 – 5 x (1/5) = 6
x2 row
a21 = 0/5 = 0
a22 = 5/5 = 1
a23 = 0/5 = 0
a24 = 1/5
a25 = -3/5
b2 = 5/5 = 1
x1 row
a31 = 1 – 0 x (-1/5) = 1
a32 = -1 – 5 x (-1/5) = 0
68
www.AgriMoon.Com
System Engineering
a33 = 0 – 0 x (-1/5) = 0
a34 = 0 – 1 x (-1/5) = 1/5
a35 = 1 – (-3) x (-1/5) = 2/5
b3 = 3 – 5 x (-1/5) = 4
Note: Don't convert the fractions into decimals, because many fractions cancel out during the
process while the conversion into decimals will cause unnecessary complications.
Final iteration:
cj 3 2 0 0 0
Basic Solution
cB variables x1 x2 x3 x4 x5 values
B b (= XB)
0 x3 0 0 1 -1/5 8/5 6
2 x2 0 1 0 1/5 -3/5 1
3 x1 1 0 0 1/5 2/5 4
zj-cj 0 0 0 1 0
Result:
Since all the values of zj – cj are positive, this is the optimal solution.
x1 = 4, x2 = 1
Max z = 3 X 4 + 2 X 1 = 14.
The largest profit of Rs.14 is obtained, when 1 unit of x2 and 4 units of x1 are produced. The above
solution also indicates that 6 units are still unutilized, as shown by the slack variable x3 in the
XB column.
69
www.AgriMoon.Com
System Engineering
2.1 Introduction
The problem of obtaining a degenerate basic feasible solution in a Linear programming problem is
known as Degeneracy. Degeneracy in an L.P.P may arise
In case (i) at least one basic variable is zero in the initial basic feasible solution, whereas in case (ii) at
any iteration of the simplex method more than one vector is eligible to leave the basis, and hence the
next simplex iteration produces a degenerate solution in which at least one basic variable is zero. This
means that the subsequent iterations may not produce improvements in the value of the objective
function. As a result it is possible to repeat the same sequence of simplex iterations endlessly without
improving the solution. This concept is known as Cycling.
As you know, the simplex algorithm starts at a corner point and moves to an adjacent corner point by
increasing the value of a non-basic variable x‘s with a negative value in the z-row (objective function).
Typically, the entering variable x‘s does increase in value, and the objective value z improves. But it is
possible that that x‘s does not increase at all. It will happen when one of the RHS coefficients is 0.
In this case, the objective value and solution does not change, but there is an exiting variable. This
situation is called degeneracy.
Recall that the simplex algorithm tries to increase a non-basic variable x‘s. If there is no degeneracy,
then x‘s will be positive after the pivot, and the objective value will improve. Recall also that each
solution produced by the simplex algorithm‘s a basic feasible solution with m basic variables, where m
is the number of constraints. There are a finite number of ways of choosing the basic variables. (An
upper bound is n! / (n-m)! m! , which is the number of ways of selecting m basic variables out of n.) So,
the simplex algorithm moves from bfs to bfs. And it never repeats a bfs because the objective is
constantly improving. This shows that the simplex method is finite, so long as there is no degeneracy.
A computation procedure to avoid cycling at any stage consists of the following steps
Step 1:
70
www.AgriMoon.Com
System Engineering
Step 2:
Re arrange the column vectors of A, so that the starting initial basis B is chosen by selecting the first m
column vectors of A. Then
yj = B-1 aj = ej (j = 1,2…,m)
Step 3:
If this minimum is unique for some I = k, then the vector yk leaves the basis. Otherwise go to next step.
Step 4:
If this minimum is unique for some i = k, then the vector yk leaves the basis. Otherwise go to next step.
Step 5:
If this minimum is unique for some I = k, then the vector yk leaves the basis. Otherwise continue the
procedure until a unique minimum nonnegative replacement ratio is obtained.
Note:
The above procedure is applicable to any iteration. However we have to maintain the same ordering of
the column vectors in every iteration. Any artificial vector, if included, should also not be removed at
any stage.
71
www.AgriMoon.Com
System Engineering
The simplex method without degeneracy The simplex method without degeneracy
The solution changes after each pivot. The The solution may stay the same after a pivot. The
objective value strictly improves after a pivot. objective value may stay the same.
The Simplex method is guaranteed to be The Simplex method may cycle and be finite. But it
finite. becomes finite if we use the perturbation approach or
several other approaches.
Two different tableaus in canonical form give It is possible that there are two different sets of basic
two different solutions. variables that give the same solution.
Degeneracy is important because we want the simplex method to be finite, and the generic simplex
method is not finite if bases are permitted to be degenerate.
In principle, cycling can occur if there is degeneracy. In practice, cycling does not arise, but no one
really knows why not. Perhaps it does occur, but people assume that the simplex algorithm is just
taking too long for some other reason, and they never discover the cycling.
Researchers have developed several different approaches to ensure the finiteness of the simplex
method, even if the bases can be degenerate. One such method is called the perturbation approach. The
perturbation approach (in the form described here) is not practical, but it serves its purpose. It does
give a way of doing simplex pivoting that is guaranteed to be finite.
72
www.AgriMoon.Com
System Engineering
Associated with every L.P.P is always a corresponding L.P.P called the Dual problem of the given
L.P.P. The original (given) L.P.P is called the Primal problem. However if we state the dual problem as
the primal one, then the other can be considered to be the dual of this primal. The two problems can
thus be said to constitute a pair of dual problems. Moreover as will be seen very soon, the two
problems can be derived from each other and there is a unique dual (primal) problem associated with
the primal(dual) problem. It will turn out that while solving a L.P.P. by simplex method, we shall
simultaneously be solving its associated dual problem as well.
The following table gives the amounts of two vitamins v1 and v2 per unit , present in two different
foods f1 and f2 respectively.
Vitamin
f1 f2
v1 2 4 40
v2 3 2 50
cost 3 2.5
The last column of this table represents the number of units of the minimum daily requirements for the
two vitamins; whereas the last row represents the cost per for the two foods. The problem is to
determine the minimum quantities of the two foods f1 and f2 so that the minimum daily requirements of
the two vitamins are met and that at the same time, the cost of purchasing these quantities of f1 and f2 is
a minimum. To formulate the problem mathematically, let xj be the number of units of food fj,(j = 1,2) to
be purchased, then the above problem is to determine two real numbers x1 and x2 so as to
73
www.AgriMoon.Com
System Engineering
Here, of course, in the construction of constraints, we have assumed that any intake of more than the
minimum requirements is not harmful and that negative purchase levels are prohibited. We shall
consider this L.P.P. as the primal problem.
Now, let us consider a different problem, which is associated with above problem. Suppose there is a
whole sale dealer who sells the two vitamins v1 and v2 along with some other commodities. The local
shopkeepers purchase the vitamin from him and form the two foods f1 and f2 ( the details are same as in
the given table). The dealer knows very well that the foods f1 and f2 have their market values only
because of their vitamin contents. The problem of the dealer is to fix the maximum per unit selling
prices, for the two vitamins v1 and v2, in such a way that the resulting prices of foods f1 and f2 do not
exceed their existing market prices.
To formulate the problem mathematically, let the dealer decide to fix up the two prices at w 1 and
w2 per unit, respectively. Then, the dealer‘s problem can be started mathematically has to determine to
real numbers w1 and w2 so as to
Let us place the matrix formulation of this L.P.P. side by with that of the primal one :
74
www.AgriMoon.Com
System Engineering
The cost vector associated with the objective function of one is just the right hand side vector in
the other‘s set of constraints.
The constraint coefficient matrix associated with one problem is simply the transpose of the
constraint matrix associated with the other.
However the two problems differ in one respect, that one of the problem is a maximization problem
while the other is a minimization problem.
Theorem 1:
If the primal or the dual has the finite optimum solution, then the other problem also possesses a finite
optimum solution and the optimum values of the objective functions of the two problems are equal.
If either the primal or the dual problem has an unbounded objective function value, then the other
problem has no feasible solution.
The symmetrical relationship between the primal and dual problem is summarized below (assume
primal to be a minimization problem)
75
www.AgriMoon.Com
System Engineering
Primal Dual
Minimization Maximization
R.H.S constant for the ith constraint Objective function coefficient for ith variable
Objective function coefficient for jth variable R.H.S constant for the jth constarint
Coefficient (aij) for ith variable in jth constraint Coefficient (aij) for jth variable in ith constraint
Rules for Constructing the Dual from the Primal (or primal from the dual) are:
1. If the objective of one problem is to be maximized, the objective of the other is to be minimized.
2. The Maximization problem should have all constraints and the minimization problem has all
constraints
4. The elements of right hand side of the constraints in one problem are the respective coefficients
of the objective function in the other problem.
5. The matrix of constraints coefficients for one problem is the transpose of the matrix of constraint
coefficient for the other problem.
76
www.AgriMoon.Com
System Engineering
A farmer has 1,000 acres of land on which he can grow corn, wheat or soyabeans. Each acre of corn
costs Rs. 100 for preparation, requires 7 man-days of work and yields a profit of Rs. 30. An acre of
wheat costs Rs. 120 to prepare, requires 10 man-days of work and yields a profit of Rs. 40. An acre of
soyabeans costs Rs. 70 to prepare, requires 8 man-days of work and yields a profit of Rs. 20. The
farmer has Rs. 1,00,000 for preparation and 8,000 man-days of work. Set-up the linear programming
equation for the problem.
Subject to
10x+12y+7z ≤10000
x + y +z ≤1000
x,y,z ≥0
Step 1: Check up whether the objective function is of maximization type. Otherwise apply the equation
Min(Z)=-Max(-Z) to convert the objective function to maximization type.
Step 2: Convert all the inequalities(≤ type) into equalities by introducing slack Variables. Then the
problem becomes
Subject to
x + y +z +s3 =1000
x, y, z , s1, s2, s3 ≥ 0
Step 3: Identify a suitable initial feasible solution by putting x=y=z=0.Then s1=1000; s2=8000 and
s3=1000 and these are the basic variables and the original variables x,y,z are non-basic variables. p
77
www.AgriMoon.Com
System Engineering
30 40 20 0 0 0
CB YB XB Y1 Y2 Y3 Y4 Y5 Y6
0 Y4 10000 10 12 7 1 0 0
0 Y5 8000 7 10 8 0 1 0
0 Y6 1000 1 1 1 0 0 1
Step 5: Compute the value of the objection by using CBXB. Also compute all the ‗Net Evaluations‘ using
zj-cj = CBYj – cj
Step 6: If all the net evaluations are ≥ 0, the the optimal solution is reached. In the above example, the
net evaluations corresponding to x1,x2 and x3 are negative. So the current solution is not optimal.
Step 7: Identify the most negative net evaluation and the variable corresponding to it will enter the
basis. In the above problem, the most negative net evaluation is -40 and it corresponds to the variable
x2 (or Y2). So Y2 enters into the basis.
30 40 20 0 0 0
CB YB XB Y1 Y2 Y3 Y4 Y5 Y6
0 Y4 10000 10 12 7 1 0 0 10000/12=833…
0 Y5 8000 7 10 8 0 1 0 8000/10=800
0 Y6 1000 1 1 1 0 0 1 1000/1=1000
78
www.AgriMoon.Com
System Engineering
↑
←↓
Entering variable
leaving variable
Step 8: To find the ‗leaving variable‘, select the variable for which the ratio is a minimum (where j
refers to the entering variable). So in the above example we have to find the minimum of the ratios
(10000/12,8000/10,1000/1). The minimum ratio is 800 and it corresponds to the variable Y5. So
Y5 leaves the basis. The row corresponding to Y5 is called ‗pivot row‘ and the column corresponding to
Y2 is called ‗pivot column‘. The element at the intersection of ‗pivot row‘ and ‗pivot column‘ is known
as ‗pivot element‘ and in the above example the pivot element is 10.
Step9: Form the next simplex table. Dividing all the pivot row elements by the pivot element.
30 40 20 0 0 0
CB YB XB Y1 Y2 Y3 Y4 Y5 Y6
0 Y4 10000 10 12 7 1 0 0 10000/12=833…
40 Y2 8000 7 10 8 0 1 0 8000/10=800
0 Y6 1000 1 1 1 0 0 1 1000/1=1000
Step 10: Convert all the other elements in the pivot column to 0 as follows:
Row 1:
10000 10 12 7 1 0 0
79
www.AgriMoon.Com
System Engineering
Pivot Row X 12
(-)
Row 3:
1000 1 1 1 0 0 1
Pivot Row X 1
(-)
30 40 20 0 0 0
CB YB XB Y1 Y2 Y3 Y4 Y5 Y6
32000 -2 0 12 0 4 0
80
www.AgriMoon.Com
System Engineering
Entering variable
30 40 20 0 0 0
CB YB XB Y1 Y2 Y3 Y4 Y5 Y6
32000
Pivot Row:
Row: 2
(-)
Row 3:
81
www.AgriMoon.Com
System Engineering
(-)
30 40 20 0 0 0
CB YB XB Y1 Y2 Y3 Y4 Y5 Y6
82
www.AgriMoon.Com
System Engineering
Resource utilization
Crop
Resource Crop 2 Crop 3 Total Resource Used Total Resource available Slack
1
83
www.AgriMoon.Com
System Engineering
1.1 INTRODUTION
LPP in which constraints may also have ≥ and = signs after ensuring that at all b 0 i ≥ are considered in
this section. In such cases basis of matrix cannot be obtained as an identity matrix in the starting
simplex table, therefore we introduce a new type of variable called the artificial variable. These
variables are fictitious and cannot have any physical meaning. The artificial variable technique is a
device to get the starting basic feasible solution, so that simplex procedure may be adopted as usual
until the optimal solution is obtained. To solve such LPP there are two methods.
1.3 ALGORITHM
The big M-method or the method of penalties consists of the following basic steps :
Step 1:
Express the linear programming problem in the standard form by introducing slack and/or surplus
variables, if any.
Step 2:
Introduce non-negative variables to the left hand side of all the constraints of (> or = ) type. These
variables are called artificial variables. The purpose of introducing artificial variables is just to obtain an
initial basic feasible solution. However, addition of these artificial variables causes violation of the
corresponding constraints. Therefore we would like to get rid of these variables and would not allow
them to appear in the optimum simplex table. To achieve this, we assign a very large penalty ' — M ' to
these artificial variables in the objective function, for maximization objective function.
Step 3:
84
www.AgriMoon.Com
System Engineering
At any iteration of the usual simplex method there can arise any one of the following three cases :
(a) There is no vector corresponding to some artificial variable, in the basis yb.
(b) There is at least one vector corresponding to some artificial variable, in the basis yB, at the zero level.
That is, the corresponding entry in XB is zero. Also, the co-efficient of M in each net evaluation Zj- Cj(j
= 1, 2, .... n) is non- negative.
In such a case, the current basic feasible solution is a degenerate one. This is a case when an optimum
solution to the given L.P.P. includes an artificial basic variable and an optimum basic feasible solution
still exists.
(c) At least one artificial vector is in the basis yB, but not at the zero level. That is, the corresponding
entry in XB is non-zero. Also coefficient of M in each net evaluation Zj - Cj is non-negative,
In this case, the given L.P.P. does not possess any feasible solution.
Step 4:
Application of simplex method is continued until either an optimum basic feasible solution is obtained
or there is an indication of the existence of an unbounded solution to the given L.P.P.
Note. While applying simplex method, whenever a vector corresponding to some artificial variable
happens to leave the basis, we drop that vector and omit all the entries corresponding to its column
from the simplex table.
Example:
Maximize z = x1 + 5x2
Subject to
3x1 + 4x2 ≤ 6
x1 + 3x2 ≤ 2
x1, x2 ≥ 0
Solution:
Converting inequalities to equalities
By introducing surplus variables, slack variables and artificial variables, the standard form of LPP
becomes
Subject to
85
www.AgriMoon.Com
System Engineering
3x1 + 4x2 + x3 = 6
x1 + 3x2 – x4 + A1 = 2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, A1≥ 0
where,
x3 is a slack variable
x4 is a surplus variable
A1 is an artificial variable.
x1 = x2 = x4 = 0, A1 = 2, x3 = 6
Iteration 1:
cj 1 5 0 0 –M
Solution
cB Basic variables B x1 x2 x3 x4 A1 values
b (= XB)
0 x3 3 4 1 0 0 6
–M A1 1 3 0 –1 1 2
–3M–
zj–cj –M–1 0 M 0
5
z1 – c1 = 0 × 3 + (–M) × 1 – 1 = –M – 1
z2 – c2 = 0 × 4 + (–M) × 3 – 5 = –3M – 5
z3 – c3 = 0 × 1 + (–M) × 0 – 0 = 0
z4 – c4 = 0 × 0 + (–M) × (–1) – 0 = M
z5 – c5 = 0 × 0 + (–M) × 1 – (–M) = 0
As M is a large positive number, the coefficient of M in the zj–cj row would decide the incoming basic
variable.
As -3M < -M, x2 becomes a basic variable in the next iteration.
Key column = x2 column.
Minimum (6/4, 2/3) = 2/3
Key row = A1 row
86
www.AgriMoon.Com
System Engineering
Pivot element = 3.
A1 departs and x2 enters.
Note: The iteration just completed, artificial variable A1 was eliminated from the basis. The new
solution is shown in the following table.
Iteration 2:
cj 1 5 0 0
Iteration 3:
cj 1 5 0 0
Result:
87
www.AgriMoon.Com
System Engineering
You may recall that while introducing the slack and surplus variables, we had assigned a zero cost to
them in the objective function. Moreover, the slack variables readily provided the initial basic feasible
solution. There are, however, many linear programming problems where slack variables cannot
provide such a solution. To solve such linear programming problems, there are two (closely related)
methods, viz.,
SAMPLE PROBLEMS
x1 + x2 ≥ 6, x1 ≥ 0 and x2 ≥ 0.
Solution. Introducing surplus (negative slack) variables x3 ≥ 0, x5 ≥ 0 and slack variable x4 ≥ 0 in the
constraint inequations, the problem becomes
xl + x2 – x5 = 6, xj ≥ 0 Q(j = 1,2, 3, 4, 5)
Clearly, we do not have a ready basic feasible solution. The surplus variables carry negative
coefficients (-1). We introduce two new variables A1 ≥ 0 and A2 ≥ 0 in the first and third equations
respectively. These extraneous variables, commonly termed as artificial variables, play the same role as
that of slack variables in providing a starting basic feasible solution.
We assign a very high penalty cost (say -M, M ≥ 0) to these variables in the objective function so that
they may be driven to zero while reaching optimality.
88
www.AgriMoon.Com
System Engineering
Al = 10, x4 = 6 and A2 = 6
with B = (a6 , a4, a7) as the basis matrix. The cost matrix corresponding to basic feasible solution is cB = (
-M, 0, -M )
Now, corresponding to the basic variables A1, x4 and A2. the matrix Y = B-1A and the net evaluations
zj - cj (j = 1, 2, .... 7) are computed. The initial basic feasible solution is displayed in the following
simplex table :
We observe that the most negative zj - cj is 4 - 3M (= zl – c1). The corresponding column vector y1,
therefore, enters the basis. Further, since min. = 5; the element y11 (=2) becomes the leading element
for the first iteration
In the above table, we omitted all entries of column vector y6, because the artificial variables Al has left
the basis and we would not like it to re-enter in any subsequent iterations.
Now since the most negative (zj—cj) is z2-c2; the non-basic vector y2 enters the basis. Further, since min
is 2 which occurs for the element y32 ( = 1/2), the corresponding basis vector y7 leaves the basis and
the element y32 becomes the leading element for the next iteration.
89
www.AgriMoon.Com
System Engineering
It is clear from the table that all zj - cj are positive. Therefore an optimum basic feasible solution has
been attained which is given by
Solution:
2x1 + x2 + x3 = 2,
3x1 + 4x2 - x4 + A1 = 12
x3 = 2 and A1 = 12.
90
www.AgriMoon.Com
System Engineering
Here the coefficient of M in each zj - cj is non-negative and an artificial vector appears in the basis, not
at the zero level. Thus the given L.P.P. does not possess any feasible solution.
91
www.AgriMoon.Com
System Engineering
Sometimes decision variables are unrestricted in sign (positive, negative or zero). In all such cases, the
decision variables can be expressed as the difference between two non-negative variables. For example,
if x1 is unrestricted in sign, then Put x1 = x1' - x1''
Example:
Subject to
-x1 + 2x2≤ 4
x1 + x2 ≤ 6
x1 + 3x2 ≤ 9
Solution:
Since x1 and x2 are unrestricted in sign, we can replace them by non-negative variables x1' , x1'', x2' , x2'' .
Subject to
Subject to
92
www.AgriMoon.Com
System Engineering
Iteration 1:
cj 2 -2 3 -3 0 0 0
Basic Solution
cB variables x1 ' x1'' x2' x2'' x3 x4 x5 values
B b (=XB)
0 x3 -1 1 2 -2 1 0 0 4
0 x4 1 -1 1 -1 0 1 0 6
0 x5 1 -1 3 -3 0 0 1 9
zj-cj -2 2 -3 3 0 0 0
Iteration 2:
cj 2 -2 3 -3 0 0 0
Basic Solution
cB variables x1' x1'' x2' x2'' x3 x4 x5 values
B b (=XB)
93
www.AgriMoon.Com
System Engineering
Iteration 3:
cj 2 -2 3 -3 0 0 0
Solution
Basic variables
cB x1' x1'' x2' x2'' x3 x4 x5 values
B
b (=XB)
Iteration 4:
cj 2 -2 3 -3 0 0 0
Solution
Basic variables
cB x1' x1'' x2' x2'' x3 x4 x5 values
B
b (=XB)
94
www.AgriMoon.Com
System Engineering
Result:
95
www.AgriMoon.Com
System Engineering
4.1 Introduction:
In the first phase of this method, the sum of the artificial variables is minimized subject to the given
constraints (known as auxiliary L.P.P.) to get a basic feasible solution to the original L.P.P. Second
phase then optimizes the original objective function starting with the basic feasible solution obtained at
the end of Phase 1.
Step 1:
Write the given L.P.P into its standard form and check whether there exists a starting basic feasible
solution.
If there does not exist a ready starting basic feasible solution, go on to the next step.
PHASE 1
Step 2:
Add the artificial variable to the left side of the each equation that lacks the needed starting basic
variables. Construct an auxiliary objective function aimed at minimizing the sum of all artificial
variables
Maximize z* = - A1 - A2 - A3 -………..-An
Step 3:
Apply simplex algorithm to the specially constructed L.P.P. The following three cases arise at the least
interaction:
Max z* < 0 and at least one artificial variable is present in the basis with positive value. In such
case, the original L.P.P does not possess any feasible solution.
96
www.AgriMoon.Com
System Engineering
Max z* = 0 and at least artificial variable is present in the basis at zero value. In such a case, the
original L.P.P possess the feasible solution. In order to get basic feasible solution we may
proceed directly to Phase 2 or else eliminate the artificial basic variable and then proceed
to Phase 2.
Max z* = 0 and no artificial variable is present in the basis. In such a case, a basic feasible
solution to the original L.P.P has been found. Go to Phase 2.
PHASE 2
Step 4:
Consider the optimum basic feasible solution of Phase 1 as the starting basic feasible solution for the
original L.P.P. Assign actual coefficients to the variables in the objective function and a value zero to
the artificial variables that appear at zero value in the final simplex table of Phase 1.
Apply usual simplex algorithm to the modified simplex table to get the optimum solution of the
original problem.
Example:
Subject to
x1 + 3x2 + x3 ≤ 5
2x1 – x2 + x3 ≥2
4x1 + 3x2 - 2x3 = 5
x1, x2, x3 ≥ 0
Solution:
If the objective function is in minimization form, then convert it into maximization form
Changing the sense of the optimization
Any linear minimization problem can be viewed as an equivalent linear maximization problem, and
vice versa. Specifically:
Minimize = Maximize
If z is the optimal value of the left-hand expression, then -z is the optimal value of the right-hand
expression.
Subject to
x1 + 3x2 + x3 ≤ 5
2x1 – x2 + x3 ≥ 2
4x1 + 3x2 - 2x3 = 5
97
www.AgriMoon.Com
System Engineering
x1 + 3x2 + x3 + x4 = 5
2x1 – x2 + x3 – x5 = 2
4x1 + 3x2 - 2x3 = 5
x1 + 3x2 + x3 + x4 = 5
2x1 – x2 + x3 – x5 + A1 = 2
4x1 + 3x2 - 2x3 + A2 = 5
PHASE 1
In this phase, we remove the artificial variables and find an initial feasible solution of the original
problem. Now the objective function can be expressed as
subject to
x1 + 3x2 + x3 + x4 = 5
2x1 – x2 + x3 – x5 + A1 = 2
4x1 + 3x2 - 2x3 + A2 = 5
98
www.AgriMoon.Com
System Engineering
cj 0 0 0 0 0 -1 -1
0 x4 1 3 1 1 0 0 0 5
-1 A1 2 -1 1 0 -1 1 0 2
-1 A2 4 3 -2 0 0 0 1 5
zj–cj -6 -2 1 0 1 0 0
Iteration 2:
cj 0 0 0 0 0 -1
-1 A2 0 5 -4 0 2 1 1
zj-cj 0 -5 4 0 -2 0
99
www.AgriMoon.Com
System Engineering
PHASE 2
The basic feasible solution at the end of Phase 1 computation is used as the initial basic feasible solution
of the problem. The original objective function is introduced in Phase 2 computation and the usual
simplex procedure is used to solve the problem.
Iteration 3:
cj 3 -1 2 0 0
Iteration 4:
cj 3 -1 2 0 0
100
www.AgriMoon.Com
System Engineering
0 x5 0 5/2 -2 0 1 1/2
Iteration 5:
cj 3 -1 2 0 0
Result:
An optimal policy is x1 = 5/2, x2 = 0, x3 = 5/2. The associated optimal value of the objective
function is
101
www.AgriMoon.Com
System Engineering
MODULE 7.
A system can be represented by means of a model. A representation of the system is called model.
Models is broadly categorized into two types
1. Physical model
2. Abstract or mathematical model
Physical model:
Model of a dam, aircraft, table, graph, photograph, etc are called as physical model. showcase models
etc
The solution to the systems is obtained by solving the one or more equations. Any inference can be
drawn about the system from the solution of the equations. Before drawing valid inferences, the
validity of the model is to be tested.
Simulation:
Simulation is an art of creating a realistic situation of the system. Simulation can be defined as the art of
building models and the study of their properties with reference to those of the systems they represent.
Models can be classified into
1. Statistical models
2. Simulation models
102
www.AgriMoon.Com
System Engineering
1. Statistical models: If we develop an empirical relation between the variables ie Regression models
without having any realistic assumption of the system, then it is called statistical or analytical models.
These models can not be simulated or optimized. These are also useful, but there are some limitations.
2. Simulation models: If we make realistic assumption on the system and then we develop a suitable
model based on the system, the resulting model is called as a simulation model. This can be used for
drawing valid inferences on the system.
Types of models:
1. Exact model: In this model, the different components will be exhibited as it is. E.g. Farm
management exhibition, exhibiting crops or animals as it is.
2. Analog model: Representing one for the other is called analog model. In this case, the
specimens can not be exhibited as it is. Instead, some samples will be exhibited.
3. Stochastic model: The model which gives the chance of occurrence of the parameters of the
model is called as stochastic model. In stochastic models, it is also assumed to vary with time.
But, in deterministic models, which determine the exact values, i.e. the parameter is assumed to
be a constant for a shorter period.
4. Static model: The model for a point of time or for a shorter period is called static model. static
models contain the relation between crop yield and factors of yield,crop growth and respiration
.Such static models also regarded as a component of dynamic models.
5. Dynamic model: grows along with time. i.e. keeps on changing from one value to another.That
is the dynamic models changes in time where as static models represent the relations between
the variables which do not involve time.
As soon as a model is constructed, the validity of the model is to be tested before drawing any
inferences or simulating the model. If the model is developed which suits the present set of
observations, then only the inferences can be drawn. Before drawing any inference from estimated
model, one should be careful with the location, season and assumptions of construction of model.
Keeping all these limitations, if the present experiment exist in the similar situation then the inference
can be drawn. For example, in the multiple linear regression model Y=a0+a1N+a2P+a3K+…, we cannot
optimize the nutrient levels, because the assumption in this model is that crop yield increases with
increase in the nutrient levels. But in reality, this holds good only upto the optimum level, beyond
which the will yield decrease.
One must also examine the sign and size of the co-efficient in the models. For example, consider the
response model Y= 1200 + 3 N-0.03 N2. Normally for any response model, sign of the square term must
be negative. Similarly, the size of the co-efficient will be small for annual crops. It will not be very high
value. If so, we will have to examine the model.
We have to test the estimated co-efficient of r or R2 for its significance. We can use to test the validity
model for chi-square goodness of fit ,
103
www.AgriMoon.Com
System Engineering
It follows the chi-square distribution with n-1 degrees of freedom. If the calculated chi-square value is
less than the table value then the test is non-significant. i.e. the observed values are in line with the
expected values. It can be inferred that the model is good. If the calculated chi-square value is more
than the table value then test is significant. i.e. the observed values are significantly different from the
expected values. It can be concluded that the models does not fit for the data.
Leaf area refers to the area of leaf (photosynthetic area) expressed in sq. cm. plant-1. Leaf area can be
accurately measured using leaf area meter of various models. In the absence of leaf area meter, the leaf
area can be measured using simulation models. Before drawing any inferences, the models should be
evaluated for their validity.
2. Keep the leaf, whose area is to be measured, on the XY quadrate and mark through the edges of
the leaf.
4. Draw a rectangle inscribing the leaf area. Let l and b be the length and breadth of rectangle,
respectively.
6. Let m be the total number of points inside the leaf area and n be the total number of points in
the rectangle. Leave the points outside the rectangle.
Let LAm be the leaf area estimated be leaf area meter. Then the error is calculated as Error = LAm - LAs
104
www.AgriMoon.Com
System Engineering
The percentage error should be lower for accepting the model. The error will be lower if we consider
more number of points.
W = f (t)
t = time in days
In growth models, for annual crops the growth is measured in g plant-1 and time is measured in days.
As soon as we collect the observation for model building, we have to go through the data very carefully
and identify extremities in observation. Mark these extreme observations and find out the reason for
the extremities. If the reason is not proper, we have to remove the extremities form the set of
observations. For construction of growth model, we have to measure the DMP in g plant-1 only and the
growth period is measured in days for annual crops.
The observations should be collected throughout the period or complete period of study. For example,
if wee want to construct a crop growth model, the observation should be collected throughout the crop
growth. Similarly for response functions, observations should be collected beyond the optimum level.
The observation should be collected in the equal period. No replication is needed for model
construction. The observation must be distributed throughout the period of study. More number of
observation will increase the precision in the model construction. The data should not be crowded
during one period and thin in other periods. The precision must be maintained in data collection. The
size of observation should be taken care of. Suppose, we collect observation at a time on a day, we
have to maintain the time of observation throughout the study.
105
www.AgriMoon.Com
System Engineering
Definition
Model
1. linear model
2. Quadratic model
3. Exponential model
4. Logistic model
Models are useful in drawing inferences. When a scientist looks at a growth model, he will be able to
draw the following inferences.
5. The turning point in the growth can be estimated by so many methods. A model can be
estimated by so many methods. But the best way of estimating a model is by the method of
least squares.
106
www.AgriMoon.Com
System Engineering
1. Linear model
The general form of a linear model is y=a+bx. Here both the variables x and y are of degree 1. In a
linear growth model, the dependent variable is always the total dry weight which is noted by w and
the independent variable is the time denoted by t. Hence the linear growth model is given by w = a+bt.
Here a and b are the parameters (or) constants of the model. Let (x1 , y1) (x2 , y2)…………. (xn , yn) be n
pairs of observations. By plotting these points on an ordinary graph sheet, we get a collection of dots
which is called a scatter diagram.
In a linear model, these points lie close to a straight line. Suppose y = a+bx is a linear model to be fitted
to the given data, the expected values of y corresponding to x1, x2…xn are given by (a+bx1) ,
(a+bx2),………………… (a+bxn). The corresponding obserbed values of y are y1 y2……yn. The
difference between the observed value and the expected value is called a residual. The Principles of
least squares states that the constants occurring in the curve of best fit should be chosen such that the
sum of the squares of the residuals must be a minimum. Using this for a linear model we get the
following 2 simultaneous equations in a and b, given by
where n is the no. of observations. Equations 1 and 2 are called normal equations. Given the
values of x and y, we can find ∑x, ∑y, ∑xy, ∑x2. Substituting in equations (1) and (2) we get two
simultaneous equations in the constants a and b solving which we get the values of a and b
x y x2 xy
∑x ∑y ∑x2 ∑xy
Note :If the linear equation is w=a+bt then the corresponding normal equations become
107
www.AgriMoon.Com
System Engineering
‗a‘ stands for the constant term which is the intercept made by the line on the w axis. When t=0, w=a ie
‗a‘ gives the initial DMP ie. Seed weight) ; ‗b‘ stands for the slope of the line which gives the growth
rate.
Exponential model
This model is of the form w=aebt where a and b are constants to be determined
108
www.AgriMoon.Com
System Engineering
Here RGR = b which is also known as intensive growth rate or Malthusian parameter.
Note
Population increases in geometric progression, whereas the food production increases in arithmetic
progression. In an exponential model the value of ‗a‘ is always positive whereas ‗b‘ can be positive or
negative. The graph of an exponential model is given below.
To find the parameters ‗a‘ and ‗b‘ in the above model first we convert it into a linear form by suitable
transformation.
logew = loge(aebt)
log w = logea + bt
Y = A + bt -------------------------(2)
Where Y = log w
A = logea
109
www.AgriMoon.Com
System Engineering
Here equation(2) is linear in the variables Y and t and hence we can find the constants ‗A‘ and ‗b‘ using
the normal equations.
∑Y = nA + b∑t
Note
The above model is also known as a semilog model.When the values of t and w are plotted on a
semilog graph sheet we will get a straight line. On the other hand if we plot the points t and w on an
ordinary graph sheet we will get an exponential curve.
The equation of this model is given by \[w={a \over {1 + c{e^{ - kt}}}}\] -------------------- (1)
Where a, c and k are constants. The above model can be reduced to a linear form as follows :
110
www.AgriMoon.Com
System Engineering
Now the equation (1) is reduced to the linear form given by equation (2) using this we can determine
the constants A and B from which we can get the value of the constants c and k.
Note : I
Here‘ a ‗ is called the carrying capacity. Either the value of ‗a‘ is given or we assume the value of ‗a‘
suitably. The other two constants ‗c‘ and ‗k‘ can be obtained by solving the linear model 2. The normal
equations of the model 2 are :
∑Y = nA + B∑t
Solving these two equations we get the values of the constant A and B.
111
www.AgriMoon.Com
System Engineering
MODULE 8.
Introduction:
Agriculture is at the mercy of the factors like temperature, RH, monsoon rains nutrients, occurrence of
pest and disease etc., which are again unreliable and uneven in distribution throughout the year.
Moreover it is essential to increase the food production and productivity with increase in food demand
due to increase in population. Due to the existence of the varied climatic scenarios, the crop growth,
food production is constrained by various natural and artificial factors like increase in water scarcity,
problems due to insects, pest and disease.
The phase and pattern of distribution of rainfall, temperature, occurrence of pest and disease problems
are coupled with the change in farm activities. Some of these behaviors are cyclic. If the past pattern
and the exact impact of crop associated resources are known, one can foretell the likely occurrences of
certain crop related attributes in advances, so that the farmer can plan early to tide over the controllable
attributes, which may likely to have serious impact on crop growth and yield. Because of the
uncertainty and risk involved in crop production it is better for the farm scientists to familiarize with
the advanced crop production techniques and tools, which are mainly associated with the application
of Crop simulation Models. The simulation models approach in crop research is very essential for
accurate planning. Using the crop growth functions one can easily estimate crop growth rate, relative
growth rate (RGR) at various stages of the crop. More the growth performance of different varieties of
the same crop, different nutrient treatments and irrigation treatments can also be studied more
effectively within the help of response functions, physical optimum, economic optimum and
constrained optimum can also be obtained which save time, energy, money etc. Using the optimum
concept, one can use the resources more efficiently and get maximum yield. The crop simulation
models are very popular in recent crop research studies. The crop simulation models like, crop growth
models, weed models, irrigation models, spacing models, response models and pest simulation models
etc., are all require the knowledge of mathematics for proper estimation, interpretation and to assess
the suitability of the model. Moreover simulation models very much essential for agricultural
Economics such as price models, production functions econometric models etc. In the case of
Agriculture the factors that influence crop yield may be divided as follows, factors that limit crop
yields such as the availability of water and nutrients, factors that determine potential yields such as
light, temperature etc and factors that reduce yields such as weeds, pests and diseases. Crop yields
throughout India are often severely restricted by the lack of fertilizer. In some cases, too much fertilizer
or organic manure is applied and when this happens both yields and crop quality are severely
depressed. But at the same time, application of less fertilizer causes reduction in yield as demand for
food production is ever increasing with rapid population explosion. Hence the optimal use of scarce
resources without further degradation, intensification, sustainability, climate changes and productivity
are the key issues. It is therefore, required most efficient crop management techniques and tools to
increase food production with optimum fertilizer use.
The word system is derived from a Greek word system with meaning an assemblage of objects united
in some form of regular interactions or interdependence. All the components are united to form a
112
www.AgriMoon.Com
System Engineering
system. System analysis is an intellectual tool used in the entire field to solve the complex problems.
That is any phenomenon; either structural or functional having at least two separable components and
some interactions between these components may be considered a system. e.g. farming system. All the
activities of farming will be included in the farming system. e.g. manuring, irrigation, weeding, etc. In
agriculture the systems are mainly classified as Cropping systems, farming systems, pathosystems and
agro ecosystems. Pathosystems may include hosts and parasite populations and their mutual
integrations. Similarly cropping system included the type of or sequence of crops during the particular
period. Each component of the system can be regarded as a system. For example, manuring in the
farming system involves time of manuring, quantity of manuring, method of manuring etc. Thus, any
system can also be considered as collection of systems. As time changes, the components of the system
also change. A system is always identified by the function while performance.
Types of system:
Open system:
If a system receives message from outside, it is called open system. e.g. soil system, plant growth
system, etc. The plant growth system receives message from outside environment like temperature,
rainfall, etc the effect of the environment on the system and their values must be closely monitored.
Closed system:
If a system does not receive anything from outside, it is called closed system. e.g. glass house
experiment In the closed system the effect of the driving variable on the environment on the systems at
its boundaries are in control. Hence the interactions between the state variables can be effectively
studied in the closed system.
Static system:
If a system does not vary with time, then it is called a static system. e.g. soil texture in a short period,
farming system for a short period. Generally any system is complex in nature and most of the systems
are time varying configuration. To analyze and get a valid information from these systems and to avoid
complications it can be treated as static system for a shorter period.
Dynamic system:
If a system varies with time, then it is called dynamic system. e.g. soil system, agricultural technology,
Farming systems and cropping systems. In cropping systems we repeat the crop experiments in
different seasons to study the seasonal influence on the Crop sequence.
1. Le Chatlier‘s Principle
3. Lenz‘s Law
113
www.AgriMoon.Com
System Engineering
2. Newton‘s third law : For every action, there will be an equal and opposite reaction‖.
3. Lenz‘s law : Any system will receive message initially. When it acquires sufficiently, then it opposes.
As soon as a system is introduced, it grows slowly till it attains maturity. As soon as it attains maturity,
it starts declining. At the time of decaying, if we revamp the system, it will survive. Otherwise the
original system will die and a new system will come into existence. For example consider a new
technology. As soon as it is introduced, it is popularized. After some time, this technology becomes
out-modeled. If a revamping is done at this stage, it will survive, otherwise it will die and a new
technology will be in use.
Then K= O/I is called as system ratio. Any system will receive input and send output.
Suppose K = 1,
then O/I = 1
i.e. O = I.
Suppose K < 1,
i.e. O < I.
In this case, the output is less than the input. The system is called as a normal system.
Suppose K > 1,
i.e. O > I.
In this case, the output is more than the input. The system is called as an abnormal system.
114
www.AgriMoon.Com
System Engineering
The model:
t = time (days)
Let ∆W be the change in growth during the interval of time ∆t. Therefore, at time t+∆t, the crop
growth is W+∆W.
In linear growth model, we make the assumption on crop growth system that the crop will grow
during the crop period i.e. as the day‘s increase the crop will grow.
i.e. ∆W ∆t.
∆W ∆t
∆W/ ∆t = b
Lt ∆t → 0 ∆W/ ∆t = b
i.e. dW/dt = b
dW = b. dt
115
www.AgriMoon.Com
System Engineering
This is the linear growth model. This is constructed based on the only assumption that ∆W ∆t.
The Curve:
In case of linear crop growth model, the parameter ‗a‘ indicates the average seed weight and the
parameter ‗b‘ indicates the crop growth rate (CGR)
The linear growth model is used only if the curve has the tendency of giving linear trend during the
period of investigation or study. For example, even in response model, for a short period before the
optimum point, the curve will be linear. Similarly, in the crop growth model, suppose we are
interested in one particular stage, we can assume that the trend is linear.
We have to plot the observed data in a graph. If the graph appears to be liner, then we have to estimate
the linear model. For example, in the case of growth model, eventhough entire growth period is
sigmoidal, the growth in a growth stage or short period can be assumed to be linear. Under these
circumstances, we can use linear models.
The linear regression between the dry matter production and time is estimated.
116
www.AgriMoon.Com
System Engineering
The co-efficients of the linear regression directly give the values of the parameters ‗a‘ and ‗b‘.
Ex.1. The following observation gives the DMP of IR 20 rice (g plant-1) at different stages. Estimate
the linear growth model for both the treatments and compare the results.
Time (days) 5 15 25 35 45
Solution:
The linear growth model is estimated. The estimated model parameters are
Parameter T1 T2
a -48.9055 -48.2675
b 3.4555 3.4127
r 0.778 0.776
The estimated linear growth models for the treatments T1 and T2 are:
The Model:
t = time (days)
117
www.AgriMoon.Com
System Engineering
In the linear growth model, the only assumption is that the crop will grow during its growth period
(i.e. we make the assumption ΔW Δt). But, we know that the growth of any crop in a particular
period (say 15 day) depends on its growth upto that period (growth upto15th day). That is, any
th
change in crop growth is also directly proportional to the growth upto the period. If we include this
assumption also, the resulting model is known as exponential growth model.
∆W W. ∆t
∆W/ ∆t = b.W
Lt ∆t → 0 ∆W/ ∆t = b.W
dw/W = b. dt
elog W = ebt + c
W = ebt. Ec
W = a ebt
118
www.AgriMoon.Com
System Engineering
The Curve:
W0 = a eb x 0
= a e0
=a
The parameter ‗a‘ gives the growth when t=0. i.e. the average seed weight is given by the parameter ‗a‘.
dW/dt = a . ebt . b
= W.b
b = (dW/dt) . (1/W)
i.e. b = RGR
As soon as we collect the observation, we should plot the data in a graph. If the graph is of the type
shown in Fig. 2, then we can use exponential growth model. Moreover, if we know that the crop or
situation previously and if the observation collected suits the two assumptions of the model, then we
can use the model. Also, if we are interested only for a period with these two assumptions alone, then
also we can decide that the model is exponential growth model.
119
www.AgriMoon.Com
System Engineering
W = a ebt
log W = log a + bt
Y=A+Bt
where Y = log W
A = log a or a = eA
B=b or b=B
Ex. 2. The following observation gives the DMP of IR 20 paddy during its growth period. By
estimating exponential growth model estimate RGR and growth rate on 30th day.
Time (days) 5 15 25 35 45
Solution:
The exponential growth model is estimated by estimating the liner regression between log W and t.
The estimated model parameters are
Ŵ= 0.0188 e0.2017 t
120
www.AgriMoon.Com
System Engineering
The Model:
t = time (days)
In exponential growth model we have assumed on the growth system that the changes in growth is
directly proportional to
If we consider the complete growth period of any species, these two assumptions will not be sufficient
since these two assumptions are true only upto a particular period and there is a restriction. That is,
this will be true only upto the maximum growth. If we include this assumption also i.e. the changes in
growth is also directly proportional to Wm-W, where Wm is the maximum possible growth, then the
resulting model is known as logistic growth model.
3. Also, the crop will grow upto the maximum growth only i.e. ΔW Wm-W.
∆W ∆t. W. (Wm-W)
121
www.AgriMoon.Com
System Engineering
dw/(W ( Wm-W)) = k. dt
The Curve:
122
www.AgriMoon.Com
System Engineering
e-bt = e0 = 1
W0 = Wm / (1+c)
1+c = Wm / W0
c= (Wm / W0) – 1
c is the ratio of maximum possible growth to the initial seed weight minus 1.
e-bt = eµ = 0
W = Wm / 1+0 = Wm
Logistic growth model is used when the complete growth period is considered.
W = Wm / (1+ c.e-bt)
W = Wm / (1+ c.e-bt)
W / Wm = 1+ c.e-bt
(W/Wm)-1 = c.e-bt
123
www.AgriMoon.Com
System Engineering
= log c – bt
Y = A+ Bx
A = log c or c = eA
B = -b or b = -B
Ex.3. Estimate logistic growth model and obtain its growth rate on 50th day for the following
observation in TMV 7 groundnut.
It is observed that the maximum growth in the replicated plot is 48.5 g pl-1.
Solution:
The linear regression between log {(W/ Wm)-1} and t is estimated. The estimated co-efficients are
c = eA = e3.7200 = 41.2631
b = -B = 0.0633
124
www.AgriMoon.Com
System Engineering
The model:
Richard had developed a logistic growth model for predicting the crop growth. The general form of
Richard‘s growth models is
W=A[1±e (t)]-1/n
If n is positive, we will choose 1 + e (t) and if n is negative we will choose 1 – e (t). For crop growth,
we choose the sign of ‗n‘ as positive and polynomial (t) = β - kt. Therefore, Richard‘s growth model
is of the form
If n =1, Richard‘s growth model reduces to logistic growth model. Normally for annual crops, the
value of ‗n‘ will be in and around one. The mean relative growth rate is given by the formula R = k /
(n+1)
Richard‘s growth model follows sigmoidal curve. If the value of n is 1, then the curve will be almost at
45 degrees to X axis.
If the value of n is more than 1, the curve tends to fall down wards and if the value of n is less than 1,
the curve becomes more upright.
125
www.AgriMoon.Com
System Engineering
W = A [1 + eβ - kt]-1/n
W/A = [1 + eβ - kt]-1/n
(W/A)-n = 1 + eβ - kt
(A/W)n = 1 + eβ - kt
(A/W)n – 1 = eβ - kt
= β – kt = β + (- k) t
A=β or β=A
B = -k or k = -B
We get the values of b and k by estimation. To estimate the above form, we have to assume the value
of n. By estimating the value of R2 and χ2, we have to choose the most accurate value of n. We should
choose ‗n‘ such that χ2 value is minimum.
Ex.4. The following data gives the growth of LRA cotton grown during 1997 at TNAU in two
nutrient treatments. Estimate Richards growth models for both the treatments and test their
validity.
126
www.AgriMoon.Com
System Engineering
T1(g pl-1) 0.256 0.921 2.640 7.691 38.821 75.943 118.464 158.840
T2(g pl-1) 0.360 0.943 2.060 7.621 32.453 65.673 105.460 140.480
The maximum growth in T1 is 160 g pl-1 and in T2 145 g pl-1. Choose the value of n for T1 as 1.26 and
T2 as 1.14.
Solution:
The linear regression between log {(A/W)n –1} and t is estimated and the estimated co-efficients are
T1 T2
Time
(Days)
W1 Ŵ1 W2 Ŵ2
127
www.AgriMoon.Com
System Engineering
χ2 7.628 2.607
Since the calculated χ2 values are lower than the table χ2 value, there is no significant differences
between the predicted and observed values. i.e. the models predict the crop growth satisfactorily and
hence can be accepted.
The model :
W = A / exp[exp(a+bt)]
The curve:
128
www.AgriMoon.Com
System Engineering
In Gompertz‘s growth model, the relative growth (RGR) and growth rate (GR) can be estimated as
below
(a + bt)
W = A / ee
(a + bt)
= log A – ea+bt
The co-efficients directly give the values of the parameters ‗a‘ and ‗b‘.
129
www.AgriMoon.Com
System Engineering
Ex.5. The following observation gives maize growth in two treatments. T1 is herbicide spray and T2
is hand weeding. Using Gompertz’s growth model, discuss which of the weed management practice
is better, by estimating the RGR and GR on 20,40 and 60th day.
The maximum growth was found to be 200 g plant-1 for both treatments.
Solution:
The linearity between log [log (A/W)] and t were estimated. The estimated model parameters are
T1 T2
Time
(Days)
W1 Ŵ1 W2 Ŵ2
130
www.AgriMoon.Com
System Engineering
χ2 2554.63 1809.28
The estimated RGR and GR at 20th, 40th and 60th days are
T1 T2
Time
(Days)
RGR GR RGR GR
Inference
Since the calculated χ2 values are greater than the table χ2 value at 8 d.f., there exists significant
difference between the predicted and observed values. i.e. the model do not estimate the crop growth
correctly. Therefore, the models can not be used for this data.
Herbicide spray (T1) registered high RGR than Hand weeding (T2) at 20. 40 and 60 days.
Therefore T1 is better than T2.
131
www.AgriMoon.Com
System Engineering
Hand weeding (T2) registered higher GR at 20 and 40 days than herbicide spray (T2) probably
due to better control of weeds. However at 60 days, there is no difference in GR between
treatments.
The Model:
W = A [1 – exp(a+bt2)]
= - 2 Abt . exp(a+bt2)
W = A [1 – exp(a+bt2)]
W/A = 1 – exp(a+bt2)
1-W/A = exp(a+bt2)
i.e. Y = a + b X
Ex.6. The following observation gives the growth of maize in two seasons under the same
treatment. Test whether there is a change in growth rate between the seasons in maize growth or
test whether the season has any influence on maize growth.
132
www.AgriMoon.Com
System Engineering
Solution:
The linearity between log (1-W/A) and t2 was estimated. The estimated model parameters are
Season 1 Season 2
Time
(Days)
W1 Ŵ1 W2 Ŵ2
133
www.AgriMoon.Com
System Engineering
GRW1 2.10 3.78 4.76 4.97 4.53 3.70 1.85 0.66 0.17
GRW2 0.66 1.26 1.74 2.08 2.25 2.26 1.93 1.35 0.80
Inference
The growth rates are higher in season 1 at all stage of growth than in season 2. Therefore, it can be
concluded that season has an influence on growth rate of maize. The estimated growth at 10, 20 and 30
days are negative. Since, in biological systems, the growth can not be negative, the models do not
estimate the growth properly. Therefore, the models can not be accepted for predicting maize growth.
134
www.AgriMoon.Com
System Engineering
Cost analysis - introduction - capital and sources - interest and present value concepts - cost of
operation / production - fixed cost – interest, taxes and insurance, depreciation - variable costs –
methods of determination of depreciation - straight line method, declining balance method, sum-of-
years digits and straight line method.
1. Introduction
Engineers are often required to make cost analysis and make decisions on use of capital in their
operations. These analyses and decisions are concerned with how best to allocate the limited funds
available to facilities and equipment so as to achieve the objectives.
In some cases, the capital allocation decisions involve the trade-off between labourers and equipment.
Labour costs are usually regarded as operating costs of a variable nature, whereas facilities and
equipment are classified as ―fixed.‖ In these sense, the capital allocation decisions have an extended
impact on the organization, for the fixed costs are charged off against income over several years in the
future.
Capital is a resource of funds owned or used by an organization. Owing to its limited availability, the
use of funds is usually carefully planned and controlled. A financial plan which shows the sources and
allocations of funds for a given period in the future is called a capital budget. An organization may
obtain funds from either or both of two major sources.
Equity and debt are considered as the important external sources. Equity capital comes from the funds
paid in for capital stock ownership. Debt capital constitutes the funds borrowed through bonds, notes
and other liabilities. Internally, an organization may increase its available funds by retaining earnings
from profits generated in the past. In profit-making organizations, some profits are typically
distributed to stockholders, but those retained earnings not paid out as dividends become available for
capital budgeting.
Interest is the cost of money, or the rental rate for funds. This cost is determined by the availability of
capital funds in the economy, the alternative opportunities investors enjoy to use those funds, and the
risk of loss the lenders must take. Funds used in very safe investments involve little risk of loss and can
usually be obtained at a more moderate cost. Funds used in more speculative ventures typically offer a
greater potential earning power, but the borrower must compensate the lender for the greater risk of
loss by paying a higher rate of interest. Thus the risk, along with economic conditions in general, helps
establish a basic interest rate.
135
www.AgriMoon.Com
System Engineering
Given the interest rate, the total amount of interest charged to a borrower is then proportional to the
principal amount borrowed and the length of time until repayment.
I=pin
where,
I = interest, Rs.
The total amount due at the end of a time period consists of the principal amount borrowed plus the
interest on that principal.
Let,
F1 = P + P (i) = P(1 + i)
The total amount due at the end of two time periods consists of the amount due at the end of the first
period, P(1 + i), plus interest on that amount for the second period:
F2 = P(1+i)2
F3 = P(1+i)3
F = P(1+i)n
136
www.AgriMoon.Com
System Engineering
The total cost of operation or cost of production is the sum of fixed cost and variable cost. The fixed cost
includes those costs which are incurred irrespective of the duration of operation and capacity of
production. The following are the expenditures include under the fixed cost.
2. Interest on the capital invested for land, building, shelter, plant and machinery
The costs or expenditure incurred that varies with the duration of operation or production level is
called the variable cost. Commonly they include,
1. Interest: The actual interest paid for the borrowed capital, capital invested for land, building,
shelter, plant and machinery and working capital or the prevailing rate of interest is taken for
the calculation purposes.
2. Taxes and insurance: The various taxes paid to the local bodies, like wealth tax, water tax, road
tax, employment tax and various deposits remitted are taken on actual basis.
3. Depreciation on the assets : Depreciation is a charge that reflects the decrease in value of an
asset over time. Since most fixed assets have a limited useful life, their cost should be charged
off gradually against the income they help produce during that useful life. No cash flows out of
the organization when this accounting entry is made, but the use of any given asset must be
reflected as an expense of doing business
4.2. Depreciation
Depreciation is an expense that must be deduced from the gross operating income of an organization.
Depreciation is sometimes referred to as a source of funds, but it is actually no more of a source than
are any other funds in the organization.
137
www.AgriMoon.Com
System Engineering
c. Sum-of-years digits
Under straight-line depreciation the book value of an asset decreases at a constant rate over the life of
the asset. If P represents the original investment value, S represents salvage, and n is the number of
years of life, the depreciation is:
Straight-line depreciation,
= (P –S) / n
Under declining-balance depreciation a fixed percentage of the book value of the asset is deducted each
period (for example, each year) and the book value decreases at a decreasing rate. This accelerated
depreciation method results in a most rapid decline in value in the early stages of an asset‘s life. The
percentage of depreciation allowed varies from 5 to 25%.
Under the sum-of-years digits depreciation, the digits representing each year of life of the asset are
summed and this total serves as the denominator of a fraction which is multiplied by the value. The
numerator varies each period, beginning with the largest-year digit down to the smallest. Thus for the
first year:
The sum-of-years digits is an accelerated depreciation method and the asset value decreases at a
decreasing rate. It does not yield as rapid a depreciation schedule as the declining-balance method,
however.
4.3. Example
1. Determine the cost of operation of a 35 hp tractor and cost of ploughing a hectare using a 3 bottom
plough of 30 cm width, for the following details.
138
www.AgriMoon.Com
System Engineering
Solution:
Assumptions:
4. Depreciation, D = 10%
No. of bottoms, n = 3
A1. Depreciation:
139
www.AgriMoon.Com
System Engineering
A2. Interest:
A= A1+A2+A3+A4
= 40.5+ 54 + 45 + 22.5
140
www.AgriMoon.Com
System Engineering
B. Variable Cost
Total Variable cost, B = B1 + B2 + B3 = 364 + 36.4 + 62.5 = Rs. 462.9 per hour
2. Cost of Ploughing:
A. Fixed Cost
A1.Depreciation:
141
www.AgriMoon.Com
System Engineering
A2. Interest:
= 0.22 + 6 + 5 +2.5
142
www.AgriMoon.Com
System Engineering
B. Variable Cost
Since the plough is operated along with the tractor, the variable cost for the tractor will be applicable
for the tractor and plough.
143
www.AgriMoon.Com
System Engineering
Cost analysis - investment analysis - methods of investment analysis - break – even analysis, pay back
period method, average rate of return method, discounted cash flow methods, net present value
method, internal rate of return method, discounted payback period method
1. Introduction
Investment decisions are important for the firm as they affect its wealth, influence its size, set the pace
and direction of its growth and determine its business risk. Thus investment decisions involve the most
efficient investment of the funds in long term activities in anticipation of the expected flow of future
benefits over a period of number of years. The future benefits are measured in terms of cash flows. In
the investment decisions it is the flow of cash – out flow and inflow – and not the accrued earnings
which is important. If the investment proposals are profitable, the firms wealth will increase, otherwise
it will decrease. Every firm would, therefore, like to undertake investment analysis which involves the
consideration of investment proposals, estimation of cash flows for the proposals, evaluation of cash
flows, selection of projects based on some criterion and finally the continuous revaluation of these
projects.
2. Break–Even Analysis
The break-even analysis is also known as cost-volume profit (CVP) analysis. The break-even analysis
provides a relationship between revenues and costs with respect to volume (quantity) of sales or
production. It represents the level of sales at which costs and revenues are in equilibrium; the
equilibrium point being known as the break-even point (BEP). At the break-even point, total revenue is
equal to the total costs, indicating no-profit or no-loss point.
1. The total cost can be separated into fixed and variable costs.
144
www.AgriMoon.Com
System Engineering
2. The total fixed cost remains unchanged with changes in sales volume.
3. The variable cost per unit is constant and the total variable cost is proportional to the
sales volume.
4. The selling price per unit is constant i.e., it does not change with volume.
5. The orgnaisation manufactures only one product or if there are multiple products, the
sales mix does not change.
Two following two methods are used to determine the break-even point:
1. Formula method
The break-even point can be computed based on units, or in terms of money value of sales
volume and as percentage of estimated capacity.
For an organisation with single-product, the break-even point in terms of units will be reached when
the total earned revenue becomes equal to the total costs.
Let,
Then
QB .s = F + QB .v .......... (3)
Or
QB = F/(s-v) ............(4)
Or
145
www.AgriMoon.Com
System Engineering
Fixed Costs
The break-even point for a single-product organisation can also be expressesed based on rupee value
of sales volume. If both sides of equation (4) are multiplied by the unit selling price, s we get the break-
even point, RB in terms of rupees. Thus
or
As both the variable costs and sales revenue vary in direct proportion to sales volume, the above
equation (6) can also be used for a multi-product organisation. For such organisatios,
Fixed costs
The break-even point as a percentage of capacity is obtained by dividing the break-even sales by the
total estimated sales or capacity sales. Thus
The break-even chart (Fig.1) represents a pictorial view of the relationships among costs, volume and
profit. In this chart the break-even point is the point at which the total cost line and the total sales line
intersect. The break-even chart is constructed as given below.
1. Represent the sales revenue along the horizontal axis. The sales revenue may be
expressed in terms of units, rupees or as a percentage of capacity.
2. Represent the revenue, fixed and variable costs along the vertical axis. A similar vertical
line may be drawn on the right of the chart to complete the square.
146
www.AgriMoon.Com
System Engineering
3. Draw the fixed cost line parallel to the horizontal axis through the fixed cost point.
4. Draw the total sales line and the total cost line. The point at which they intersect is the
break-even point. The angle between these lines is called the angle of incidence. Larger
this angle, lower the break-even point and vice-versa. The area to the left of this point is
the loss area and represents the unrecovered fixed costs, while the area to its right is the
profit area.
The excess of actual or budgeted sales over the break-even sales is called margin of safety. The margin
of safety ratio is expressed as,
Margin of safety ratio= (Budgeted sales – Break even sales) / Budgeted sales
The margin of safety indicates the extent to which sales may fall before a firm suffers a loss. Larger the
margin of safety, safer the firm.
Break-even analysis is the most useful technique of profit planning and control. It is a device to explain
the relationship between cost, volume and profits. The utility of the break-even analysis lies in the
following advantages it has:
147
www.AgriMoon.Com
System Engineering
alternative but also the probability of reaching the break-even point is higher should be
preferred.
2.5. Limitations of break-even analysis
2. The total fixed cost may not remain unchanged over the entire volume range.
3. The unit selling price and unit variable cost may not remain constant.
6. It is a static tool and shows the relationship among costs, volume and profits of an organisation
at a given point of time only.
Payback period is the most popular method of evaluating investment proposals. It is defined as the
number of years required to recover the cash invested in a project. If the annual cash inflows are same,
the payback period is computed by dividing cash invested by the annual cash inflow; if unequal, it is
calculated by adding up the cash inflows until the total is equal to the initial cash invested.
If the payback period calculated for a project is less than the maximum payback period set by the
management, the project is accepted; if not, it is rejected. By ranking method it gives the highest
ranking to the project that has the shortest payback period and lowest ranking to the project with the
highest payback period.
3. The cash inflows that accrue after the payback period is not accounted.
The accounting rate of return (ARR) is found by dividing the average annual net income (after taxes
and depreciation) by the average cash outlay i.e., average book value after depreciation. The
accounting rate of return is thus an average rate and can be determined by the following equation:
Average income
ARR = ----------------------------------
Average investment
148
www.AgriMoon.Com
System Engineering
A variation of ARR method is to divide the average earnings after taxes by the original cost of
the project instead of average cost.
This method accepts all those projects whose ARR value is higher than the minimum rate established
by the management and rejects those whose ARR value is lower. It also ranks the project as number
one if it has highest ARR and lowest rank would be assigned to the project with lowest ARR.
1. It uses accounting profits and not cash flows in comparing the projects.
2. It ignores the time value of money. Profits accruing in different periods are valued equally.
3. It does not allow for the fact the profits can be reinvested.
The above methods discussed suffer from drawback that they fail to recognize the time value of money
in evaluating the investment worth of the projects.
Methods that fully recognise the time value of money are called time-adjusted or discounted cash flow
or present value methods. They are
This method fully recognises the time value of money. It correctly postulates that cash flows arising at
different time periods differ in values and are comparable only when their equivalents-present values-
are found out. It involves the following steps.
1. Select an appropriate rate of interest to discount cash flows. Generally this rate is the firm‘s cost
of capital which equals the minimum rate of return expected by the investor.
2. Compute present value of cash inflows and outflows using the cost of capital as the discount
rate. If all cash outflows are made in the initial year, then their present value will be equal to the
cash actually spent.
3. Find out the present value by subtracting the present value of cash outflows from the present
value of cash inflows.
149
www.AgriMoon.Com
System Engineering
4. Accept the investment project if its net present value is positive or zero and reject it if its net
present value is negative.
The equation for NPV, assuming that all cash outflows are made in the initial year to can be written as
n At
= Σ ------------ - C (8)
t =1 (1 + k)1
where A1, A2, ........ An represent the cash inflows, k is the firm‘s cost of capital, C is the outlay and n is
the expected life of the proposal.
2. It considers all cash flows over the entire life of the project.
1. It is difficult to use.
2. It assumes that the discount rate – which is usually the firm‘s cost of capital – is known;
but the cost of capital is difficult to understand and measure.
3. It may not give satisfactory answer when projects involving different amount of
investment are compared. The project with higher NPV may not be desirable if it also
requires a large investment.
The internal rate of return is the rate that equals the present value of cash inflows with the present
value of cash outflows of an investment. Thus it is the rate at which the net present value of the
investment is zero. It can be determined from the following equation:
A1 A2 An n At
150
www.AgriMoon.Com
System Engineering
n At
or Σ --------- - C = 0 (10)
t =1 (1 + r)t
It may be seen that the IRR formula is the same as used for the NPV method with the difference that in
the NPV method the required rate of interest (cost of capital), k is known and the NPV is to be found
out, while in the IRR method the value of r is to be determined at which the NPV is zero. The value of r
in the IRR method the value of r is to be determined by trial and error method. Some value of the rate
of return is chosen and NPV of cash inflows is calculated. If this value is lower than the present value
of cash outflows, a lower rate is tried; if this value is higher than the present value of cash outflows, a
higher rate is tried. The process is repeated until the net present value becomes zero.
According to IRR method, a project is accepted if its internal rate of return is higher than or equal to the
minimum required rate of return (i.e., r ≥ k); and the project is to be rejected if r < k.
Merits:
Demerits:
2. It may yield results inconsistent with the NPV method if the projects differ in their
expected lives or cash outlays or timing of cash flows.
The payback period is defined as the number of years required to recover the original cash investment
in a project. In case of the discounted payback period, we consider the discounted present values of
future cash inflows and determine the number of years required to recover the initial investment. If
discounted payback period is less than the desired payback period, the project is accepted, otherwise it
is rejected.
7. Investment Decisions
Investment decisions are taken on the time value of money and principles of equivalence. The money
inflows and outflows at various points should not be added as such but should be reduced to a
151
www.AgriMoon.Com
System Engineering
common point and added. For performing certain operations may be many methods available and are
considered as equivalent methods. Among these methods, it is decided to choose based on the time
value of money. It may be an equipment/ machinery for doing the given job. When number of such
equipment or machinery are available the suitable one is selected based on the analysis of time value of
money. The following steps are involved in making the investment decision.
i. identification of alternative
iii. taking the decision based on the time value of money following any of the following methods
b. present worth
Let P be the present worth of an investment and over a period of n it yields to F, further worth, if it is
the compound interest. For the given P or F, the equivalent considerable worth is A. These
terms, A, F and P are connected through the following relations for taking investment decisions.
F = P (1+i)n (11)
P = F (1/1+i)n (12)
If A is the amount paid every year for a period of n years @ i, at the end of n years, the value will be,
where the amount paid during 0,1,2,…periods will earn interest for n, n-1, n-2,… years.
(14) – (13),
152
www.AgriMoon.Com
System Engineering
-F + iF + F = A [-1 + (1+i)n]
F = A [(1+i)n-1/i] (15)
A = F [i/(1+i)n-1] (16)
A = P(1+i)n [i/(1+i)n-1]
A packaging operation in a food industry was performed using manual labour which involves
Rs.50,000 per year as wages. The same can be performed by employing a packaging machine which
costs Rs.1,00,000/- and requires one labour only. The expenditure towards electricity and spares
repaired and labour charges are Rs.5000, Rs.10,000 and Rs.10,000 respectively. Suggest the industry
whether to go for packaging machine. The life of the machine is 10 years and the scrap value is 10% of
interest rate is 12%.
153
www.AgriMoon.Com
System Engineering
154
www.AgriMoon.Com
System Engineering
= Rs. 43,213
Plan A
Present worth of the annual cost, P = Rs. 50,000 (P/A, 12%, 10)
= 50000 [5.6502]
= Rs.2,82,510
Plan B
155
www.AgriMoon.Com
System Engineering
= 25000 [5.6502]
= Rs.1,41,255
= 9000[0.322]
= Rs. 2,898
= Rs.2,44,153
156
www.AgriMoon.Com
System Engineering
Cost analysis - inventory control - causes of poor inventory control - types of inventories - direct and
indirect - inventory costs - purchase costs, carrying cost, setup costs and shortage costs - inventory
model - economic order quantity (EOQ) - inventory control systems - fixed-order quantity system and
fixed-order interval system.
1. Introduction
An inventory consists of usable but idle resources such as men, machines, materials or money. When
the resources involved is a material, the inventory is called ―stock‖. Though inventory of materials is
an idle resource (since the material lie idle and are not to be used immediately), almost every
organisation must maintain it for efficient and smooth running of its operations. Without this no
business activity can be performed, whether it is a service organisation like a hospital or a bank or it is a
manufacturing or trading organisation. If an enterprise has no inventory of materials at all, on
receiving a sales order it will have to place order for purchase of raw materials, wait of their receipt and
then start production. This makes the customer to wait for the delivery of the goods and may turn to
other suppliers. resulting in loss of business for the enterprise. Most organisations have 20 to 25% of
their total funds devoted to inventory. It may even increase to 70% in cause of pharmaceutical,
chemical and paints industries.
1. It helps in smooth and efficient running of an enterprise by ensuring the availability of the
required raw materials and spares.
2. It facilitates to provide service to the customer at a short notice. Timely deliveries / services
will fetch more goodwill and orders, besides reputation.
3. In the absence of inventory, the enterprise may have to pay high prices during the purchases
made on emergency.
5. It reduces production cost since there is an added advantage of batching and long,
uninterrupted production runs.
6. It acts as a buffer stock when raw materials are received late and shop rejections are too many.
7. Process and movement inventories (also called pipeline stocks) are quite necessary in big
enterprises where significant amounts of times are required to tranship items from one location
to another.
8. Bulk purchases will entail less order and, therefore, less administrative costs. This applies to
goods produced within the organisation as well. Less order, as a result of larger lots, will entail
lesser machine setups and other associated costs.
157
www.AgriMoon.Com
System Engineering
9. An organisation may have to deal with several customers and vendors who are not necessarily
near it. Inventories, therefore, have to be built to meet the demand at least during the transit
time.
10. It helps in maintaining economy by absorbing some of the fluctuations when the demand for an
item fluctuates or is seasonal.
However, too often inventories are wrongly used as a substitute for management. Also maintenance of
inventory costs additional money to be spent on personnel, equipment, insurance, etc. thus excess
inventories are not desirable. This necessitates controlling the inventories in the most useful way.
1. Overbuying without regard to the forecast or proper estimate of demand to take advantage of
favourable market.
2. Over production or production of goods much before the customer requires them.
3. Overstocking due to bulk production to reduce production costs will also result in large
inventories.
4. Cancellation of orders and minimum quantity stipulations by the suppliers may also give rise to
large inventories.
4. Types of Inventories
They include items that are directly used for production and are classified as:
3. Finished Goods Inventory: This includes the final products ready for dispatch to
consumers or distributors.
4. Maintenance, repair and operating (MRO) Inventory: Maintenance, repair and operating
items such as spare parts and consumable stores that do not go into the final product but
are consumed during the production process.
5. Miscellaneous Inventory: All other items such as scrap, obsolete and unsalable products,
stationery and other items used in office, factory and sales department, etc.
158
www.AgriMoon.Com
System Engineering
Indirect inventories are those directly or indirectly used in the production. They may be in transit,
stored for future use, etc. They may be classified as:
1. Transit or Pipeline Inventories: Also called movement inventories, they consist of items
that are currently under transportation e.g., coal being transported from coalfields to a
thermal plant.
2. Buffer Inventories: They are required as protection against the uncertainties of supply
and demand. A company may well know the average demand of an item that it needs;
average value. Similarly, the average delivery period (lead time) may be known but due
to some unforeseen reasons, the actual delivery period could be much more. Such
situations require extra stock in excess of the average demand during the lead time is
called buffer stock (or safety stock or custom stock).
3. Decoupling Inventories: They are required to decouple or disengage the different parts
of the production system. For an item that requires processing on a series of different
machines with different processing times, it is a must to have decoupling inventories of
the item in between the various machines for smooth and continuous production. The
decoupling inventories act as shock absorbers in case of varying work-rates, machines
breakdowns or failures, etc.
4. Seasonal Inventories: Some items have seasonal demands e.g., demand of woolen
textiles in winter, coolers and air conditioners in summer, raincoats in rainy season, etc.
inventories for such items have to be maintained to meet their high seasonal demand.
Lot size or cycle inventories are, therefore, held by purchasing items in lots rather than their exact
quantities required. For example, a textile industry may buy cotton in bulk during cotton season rather
than buying it everyday.
6. Anticipation Inventories: They are held to meet the anticipated demand. Purchasing of crackers well
before Diwali, fans before the approaching summer, piling up of raw material in the face of imminent
transporters strike are examples of anticipation inventories.
5. Inventory Costs
1. Purchase costs
159
www.AgriMoon.Com
System Engineering
It is the price that is paid for purchasing / producing an item. It may be constant per unit or may vary
with the quantity purchased / produced. If the cost per unit is constant, it does not affect the inventory
control decision. However, the purchase cost is definitely considered when it varies as in quantity
discount situations.
5.2. Inventory carrying costs (or stock holding costs or holding costs or storage costs)
They arise on account of maintaining the stocks and the interest paid on the capital tied up with the
stocks. They vary directly with the size of the inventory as well as the time for which the item is held in
stock. Various components of the stockholding cost are:
1. Cost of money or capital tied up in inventories: This is, by far, the most important component.
Money borrowed from the banks may cost interest of about 12%. But usually the problem is viewed in
a slightly different way i.e., how much the organisation would have earned, had the capital been
invested in an alternative project such as developing new product, etc. it is generally taken somewhere
around 15% to 20% of the value of the inventories.
2. Cost of storage space: This consists of rent for space. Besides space expenses, this will also include
heating, lighting and other atmospheric control expenses. Typical values may vary from 1 to 3%.
3. Depreciation and deterioration costs: They are especially important for fashion items or items
undergoing chemical changes during storage. Fragile items such as crockery are liable to damage,
breakage, etc. 0.2% to 1% of the stock value may be lost due to damage and deterioration.
4. Pilferage cost: It depends upon the nature of the item. Valuables such as gun metal bushes and
expensive tools may be more tempting, while there is hardly any possibility of heavy casting for
forging being stolen. While the former must be kept under lock and key, the latter may be simply
dumped in the stockyard. Pilferage cost may be taken as 1% of the stock value.
5. Obsolescence cost: It depends upon the nature of the item in stock. Electronic and computer
components are likely to be fast outdated. Changes in design also lead to obsolescence. It may be
possible to quantify the percentage loss due to obsolescence and it may be taken as 5% of the stock
value.
6. Handling costs: These include all costs associated with movement of stock, such as cost of labour,
overhead cranes and other machinery used for this purpose.
7. Record – keeping and administrative cost: There is no use of keeping stocks unless one can easily
know whether or not the required item is in stock. This signifies the need of keeping funds for record-
keeping and necessary administration.
8. Taxes and Insurance. Most organisations have insurance cover against possible loss from theft, fire,
etc. and this may cost 1% to 2% of the invested capital.
Inventory carrying cost C1 is expressed either as per cent of the value or per unit time (e.g., 20% of the
value of the stock per year) or in terms of monetary value/unit/unit time (e.g., Rs. 5/unit/year).
Example: If the average stock during a year is of value Rs. 20,000, the inventory carrying costs, being,
say, equal to 20%, amount to Rs. 20,000 x (20/100) = Rs. 4,000.
160
www.AgriMoon.Com
System Engineering
These include the fixed cost associated with placing of an order or setting up a machinery before
starting production. They include costs of purchase, requisition, follow up, receiving the goods, quality
control, cost of mailing, telephone calls and other follow up actions, salaries of persons for accounting
and auditing, etc. also called ordering costs or replenishment costs, they are assumed to be
independent of the quantity ordered or produced but directly proportional to the number or orders
placed. At times, however, these costs may not bear any simple relationship to the number of orders.
More than one stock item may be ordered on one set of the documents; the clerical staff is not divisible
and without the existing staff increasing or decreasing, there may be considerable scope for changing
the number of orders. In such a case, the acquisition cost relationship may be quadratic or stepped
instead of a straight line. They are expressed in terms of Rs. per order or Rs. per set-up.
These costs are associated with either a delay in meeting demands or the inability to meet it at all.
Therefore, shortage costs are usually interpreted in two ways. In case the unfilled demand can be filled
at a later stage (backlog case), these costs are proportional to quantity that is short as well as the delay
time and are expressed as Rs. per unit back ordered per unit time (e.g. Rs.7/unit/year). They represent
loss of goodwill and cost of idle equipment. In case the unfilled demand is lost (no backlog case), these
costs become proportional to only the quantity that is short. This results in cancelled orders, lost sales,
profit and even the business itself.
It follows from the above discussion that if the purchase cost is constant and independent of the
quantity purchased, it is not considered in formulating the inventory control policy. The total variable
inventory cost in this case is given by
Total variable inventory cost = Carrying cost + Ordering cost + Shortage cost.
However, if the unit cost depends upon the quantity purchased i.e., price discounts are available, the
purchase cost is definitely considered in formulating the inventory control policy. The total variable
inventory cost in this case is then given by
Total variable inventory cost = Purchase cost + Carrying cost + Ordering cost + Shortage cost.
The total cost of the inventory is the sum of carrying cost, ordering cost and purchase cost.
Let,
Cc carrying cost per unit for the given period or a percentage of the unit cost
161
www.AgriMoon.Com
System Engineering
Q/2 the average inventory over a given period, when the inventory varies from 0 to Q
Differentiating with respect to the order quantity Q, yields the slope of the total cost curve, and
equating to O to minimize ‗T‘.
Eq.(3) is known as the Economic Order Quantity (EOQ) or Economic Lot Size (ELS) equation. Fig.
describes the relationship between the relevant ordering and carrying costs. Note also that the total cost
curve is relatively flat in the area of the EOQ, so small changes in the amount ordered do not have a
significant effect on total costs.
Once the economic order quantity Q is determined, the minimum inventory cost can be computed by
substituting this Q value into the total cost equation.
If the manufacturer or supplier offers any discount for a minimum purchase order, the total cost will
be calculated and the unit cost will be compared in both cases.
162
www.AgriMoon.Com
System Engineering
In some cases the manufacturer / supplier will extend a discount on the unit cost when a prescribed
minimum quantity is purchased or ordered. If Q1 is the minimum of units to be ordered and P1 is the
unit cost with discount, total cost as per minimum order,
Lead time is known and replenishment is instantaneous at the expiration of the lead
time.
Ordering and carrying costs include all the relevant costs and are constant.
Several other types of control systems have been in use for some time to achieve the various purposes
of inventory. ABC method of determining which inventory items deserve most attention, and then at
three traditional inventory control systems: (1) fixed-order quantity or fixed quantity – Q system, (2)
fixed-order interval (fixed period) – P system, and (3) base stock (as and when exhausted to be
163
www.AgriMoon.Com
System Engineering
ordered). These systems, by themselves, are essentially only. ―Order launching‖ techniques for they
basically only get an order issued but offer little in the way of follow-up control. They also tend to look
back at historical average usage rather than ahead to a forecast of material requirements.
The time and recordkeeping activities required to control inventories cost organization money. Some
items do not warrant as close and exacting control as others, for a small percentage of items usually
accounts for a large percentage of an inventory investment. This widely recognized fact has led many
firms to classify inventories into three groups designated A, B, and C:
1. items include the 10-20 percent of items that typically account for 70-80 percent of the
total value of inventory.
2. items include about 30-40 percent of items that account for about 15-20 percent of the
total value of inventory.
3. items include about 40-50 percent of items that account for about 5-10 percent of the
total value of inventory.
This classification system reveals that for most inventories the bulk of items typically account for only
5-10 percent of value and suggests that the firm have plenty of these low-value items on hand but
concentrate the more costly control efforts on the high-value items. Class A and B items are sufficiently
valuable or vital to warrant a close control under some type of perpetual or periodic monitoring
system. Class C items are sometimes managed on a two-bin system basis.
The fixed-order quantity inventory control system is a perpetual system which keeps a current record
of the amount of inventory in stock. A fixed quantity Q is ordered when the order point is reached (that
is, when the amount on hand, without using the safety stock, will just meet the average demand during
the lead time). This type of system, illustrated in figure, lends itself to the use of EOQ purchasing
methods. The system requires continuous monitoring of inventory levels, which can easily be done if
the system is computerized. Because of this, it is often used for inventories that have large, unexpected
fluctuations in demand.
In the fixed-order interval system the amount of inventory in stock is reviewed at periodic intervals,
such as weekly or monthly. A variable quantity Q is then ordered on a regular basis. The order
quantity is adjusted to bring the inventory on hand and on order up to a specified level. Since the safety
stock must provide protection over the entire cycle it is typically larger than would be required under
a fixed-order quantity system, where the safety stock must protect over the lead time only. This system
does not, however, require continuous monitoring, and is especially useful for processes that call for a
consistent use of material. It also lends itself to conditions where a single review period can identify
several items which can then be ordered at one time, with a possible savings in the ordering cost.
164
www.AgriMoon.Com
System Engineering
The base stock system is one of many combinations of inventory systems and has elements of both the
fixed-order interval systems. In this system, inventory levels are reviewed periodically, but orders are
placed only when the stock is below some specified level. The system thus provides some of the control
aspects of periodic review systems but would typically result in the placement of fewer orders, and
orders of a more economic lot size.
Example 1: A tractor manufacturer purchases the rear wheel tyres from a leading tyre manufacturer.
The annual requirement of tyres is 3000 numbers which spreads over uniformly. The cost of each tyre is
Rs.9,800. The ordering cost is Rs.2500 per order and the carrying cost is 2% of the cost of the year
during the stock period. Determine the economic order quantity and the unit cost of the tyre on site.
Given,
Carrying cost, CC = 2% of P
= Rs. 2,94,54,221/-
165
www.AgriMoon.Com
System Engineering
Example 2: A food processing industry buys tin cans for packaging their food product. The processing
capacity of the industry is 5 tonnes per day and produces 10,00,000 cans annually. The cans are bought
from a leading manufacturer. The expenditure involved in placing the order is Rs.5,000/- per order and
the carrying cost is 2% of the unit cost. The industry propose to purchase the cans based on the
economic order quantity. However the can supplier offers a discount of 2% on the unit cost of Rs.8/-.
Advise the food processing industry whether to avail the discount, if the carrying cost and ordering
cost remains same.
Given:
Discount offered = 2%
= Rs.7,08,900/-
166
www.AgriMoon.Com
System Engineering
= Rs.8,55,980/-
Based on the unit cost of the cans, with and without discount, the industry may be advised to avail the
discount which saves Rs.0.36 per can.
167
www.AgriMoon.Com
System Engineering
1. Introduction
Industries require to transport their products available at several sources or production centres to a
number of destinations or markets. In the process of distributing to various destinations, high
transportation costs are involved. Minimizing the transportation cost will benefit the organisation by
increasing the profit. To analyze and minimize the cost of transportation, transportation model is used.
The name ―transportation model‖ is, however, misleading. This model can be used for a wide variety
of situations such as scheduling, personnel assignment, product mix problems and many others, so that
the model is really not confined to transportation or distribution only.
The origin of transportation models dates back to 1941 when F.L. Hitchcock presented a study entitled
‗The Distribution of a Product from Several Sources to Numerous Localities‘. The presentation is
regarded as the first important contribution to the solution of transportation problems. In 1947, T.C.
Koopmans presented a study called ‗Optimum Utilization of the Transportation System‘. These two
contributions are mainly responsible for the development of transportation models which involve a
number of production centres / sources and a number of destinations / markets. Each shipping source
has a certain capacity and each destination has a certain requirement associated with a certain cost of
transportation from the sources to the destinations. The objective is to minimize the cost of
transportation while meeting the requirements at the destinations. Transportation problems may also
involve movement of a product from plants to warehouses, warehouses to wholesalers, wholesalers to
retailers, retailers to customers, etc.
1. Total quantity of the items available at different sources/ supply is equal to the total
requirement/ demand at different destinations / markets.
3. The unit transportation cost of the item from all sources to destinations is known.
4. The transportation cost on a given route is directly proportional to the number of units shipped
on that route.
5. The objective is to minimize the total transportation cost for the organization as a whole and not
for individual supply and distribution centres.
168
www.AgriMoon.Com
System Engineering
Suppose that there are m sources and n destinations. Let ai be the number of supply units available at
source i(i = 1,2,3,….., m) and let bj be the number of demand units required at destination j(j = 1,2,3,…..,
n). Let cij represent the unit transportation cost for transporting the units from source i to destination j.
The objective is to determine the number of units to be transported from source i to destination j so that
the total transportation cost is minimum. In addition, the supply limits at the sources and the demand
requirements at the destinations must be satisfied exactly.
If xij (xij ≥ 0) is the number of units shipped from source i to destination j, then the equivalent linear
programming model will be
minimize
m n
z= Σ Σ cij xij ,
i =1 j = 1
subject to
j=1
and
Σ x ij = bj , j = 1,2,3, …….. , n ,
i= 1
where x ij ≥ 0
The two sets of constraints will be consistent i.e., the system will be in balance if
m n
Σ ai = Σ bj .
i =1 j=1
Equality sign of the constraints causes one of the constraints to be redundant (and hence it can be
deleted) so that the problem will have (m + n - 1) constraints and (m x n ) unknowns.
169
www.AgriMoon.Com
System Engineering
Note that a transportation problem will have a feasible solution only if the above restriction is
satisfied. Thus,
m n
i =1 j=1
transportation problem to have a feasible solution. Problems that satisfy this condition are called
balanced transportation problems. Techniques have been developed for solving balanced or standard
transportation problems only. It follows that any non – standard problem in which the supplies and
demands do not balance, must be converted to a standard transportation problem before it can be
solved. This conversion can be achieved by the use of a dummy source/destination.
The above information can be put in the form of a general matrix shown below:
In table , cij , i = 1,2, ….., m ; j = 1,2, …… , n , is the unit shipping cost from the ith oringin to jth
destination, xij is the quantity shipped from the ith origin to jth destination, ai is the supply available at
origin i and bj is the demand at destination j.
Definitions:
A few terms used in connection with transportation models are defined below.
170
www.AgriMoon.Com
System Engineering
3. Optimal solution: A feasible solution (not necessarily basic) that minimizes (maximizes)
the transportation cost (profit) is called an optimal solution.
The matrix used in the transportation models consists of squares called ‗cells‘, which when stacked
form ‗columns‘ vertically and ‗rows‘ horizontally.
The cell located at the intersection of a row and column is designated by its row and column headings.
Thus the cell located at the intersection of row A and column 3 is called cell (A, 3). Unit costs are placed
in each cell.
In case of simplex algorithm, the basic feasible solution may become degenerate at the initial stage or at
some intermediate stage of computation. In a transportation problem with m origins and n destinations
if a basic feasible solution has less than m + n – 1 allocations (occupied cells), the problem is said to be a
degenerate transportation problem.
171
www.AgriMoon.Com
System Engineering
While in the simplex method degeneracy does not cause any serious difficulty, it can cause
computational problem in transportation technique. In stepping – stone method it will not be possible
to make close paths (loops) for each and every vacant cell and hence evaluations of all the vacant cells
cannot be calculated. If modified distribution method is applied, it will not be possible to find all the
dual variables ui and vj since the number of allocated cells and their cij values is not enough. It is thus
necessary to identify a degenerate transportation problem and take appropriate steps to avoid
computational difficulty. Degeneracy can occur in the initial solution or during some subsequent
iteration.
Normally, while finding the initial solution (by any of the methods), any allocation made either
satisfies supply or demand, but not both. If, however, both supply and demand are satisfied
simultaneously, a row as well as column are cancelled simultaneously and the number of allocations
become two less than m + n – 1 and so on. This degeneracy is resolved or the above degenerate
solution is made non-degenerate in the following manner:
First of all the requisite number of vacant cells with least unit costs are chosen so that (incase of tie
choose arbitrarily):
2. these m + n – 1 cells are in independent positions i.e., no closed path (loop) can be
formed among them. If a loop is formed the cells / cells with next lower cost is/are
chosen so that no loop is formed among them. This can always be done if the solution
we start with contains allocated cells in independent positions.
Now allocate an infinitesimally small but positive value ε (Greek letter epsilon) to each of the chosen
cells. Subscripts are used when more than one such letter is required (e.g., ε1, ε2, etc.) these ε‘s are then
treated like any other positive basic variable and are kept in the transportation array (matrix) until
temporary degeneracy is removed or until the optimal solution is reached, whichever occurs first. At
that point we set each ε = 0. Notice that ε is infinitesimally small and hence its effect can be neglected
when it is added to or subtracted from a positive value (e.g. 10 + ε = 10, 5 – ε = 5, ε + ε = 2 ε , ε - ε = 0).
Consequently, they do not appreciably alter the physical nature of the original set of allocations but do
help in carrying our further computations such as optimality test.
Sometimes even if the starting feasible solution is non-degenerate, degeneracy may develop later at
some subsequent iteration. This happens when the selection of the entering variable (least value in the
closed path that has been assigned a negative sign), causes two or more current basic variables
(allocated cell values) to become zero. In thils case we allocate ε to recently vacated cell with least cost
that there are exactly m + n – 1 allocated cells in independent positions and the procedure can then be
continued in the usual manner.
6. Transportation Algorithm
Transportation algorithm for a minimization problem as discussed earlier can be summarized in the
following steps:
172
www.AgriMoon.Com
System Engineering
1. Construct the transportation matrix. For this enter the supply ai from the origins, demand bj at
the destinations and the unit costs cij in the various cells.
2. Find initial basic feasible solution by Vogel‘s approximation method or any of the other given
methods.
3. Perform optimally test using modified distribution method. For this, find dual variables ui and
vj such that ui + vj = cij for occupied cells. Starting with say, vi = 0, all other variables can be
evaluated.
4. Compute the cell evaluations = cij – (ui + vj) for vacant cells. If all cell evaluations are positive or
zero, the current basic feasible solution is optimal. In case any cell evaluation in negative, the
current solution is not optimal.
5. Select the vacant cell with the most negative evaluation. This is called identified cell.
6. Make as much allocation in the identified cell as possible so that it becomes basic i.e., Reallocate
the maximum possible number of units to these cells, keeping in mind the rim conditions. This
will make allocation in one basic cell zero and in other basic cells the allocations will remain
non-negative ( ≥ 0). The basic cell whose allocation becomes zero will leave the basis.
2. Maximization problem.
5. Overtime production.
In the problems discussed so far, the total availability from all the origins was equal to the total
demand at all the destinations i.e.,
m n
i =1 j=1
In many real life situations, however, the total availability may not be equal to the total demand. i.e.,
m n
173
www.AgriMoon.Com
System Engineering
i =1 j=1
In these problems either some available resources will remain unused or some requirements will
remain unfilled.
Since a feasible solution exists only for a balanced problem, it is necessary that the total availability be
made equal to the total demand. If total capacity or availability is more than the demand and if there
are no costs associated with the failure to use the excess capacity, we add a dummy (fictitious)
destination to take up the excess capacity and the costs of shipping to this destination are set equal to
zero. The zero cost cells are treated the same way as real cost cells and the problem is solved as a
balanced problem. If there is, however, a cost associated with unused capacity (e.g., maintenance cost)
and it is linear, it too can be easily treated.
In case the total demand is more than the availability, we add a dummy origin (source) to ―fill‖ the
balance requirement and the shipping costs are again set to equal to zero. However, in real life, the cost
of unfilled demand is seldom zero since it may involve lost sales, lesser profits, possibility of losing the
customer or even business or the use of a more costly substitute. Solution of the problem under such
situations may be more involved.
The transportation problem may involve maximization of profit rather than minimization of cost. Such
a problem may be solved in one of the following ways:
2. It may be converted into a minimization problem, by subtracting all the profits from the
highest profit in the matrix. The problem can then be solved by the usual methods.
3. It may be solved as a maximization problem itself. However, while finding the initial
basic feasible solution, allocations are to be made in highest profit cells, rather than in
lowest cost cells. Also solution will be optimal when all cell evaluations are non-positive
(≤ 0).
In some industries a particular product may be manufactured and transported from different
production locations. The production cost could be different in different units due to various reasons,
like higher labour cost, higher cost of transportation of raw materials, higher overhead charges, etc.
Under this situation the production cost is added to the transportation cost while finding the optimal
solution. While solving the transportation problems, if the variable production costs and the fixed
costs are given for various production plants, no consideration is given for the fixed cost.
174
www.AgriMoon.Com
System Engineering
In the transportation of goods from sources to the destinations, some routes may be banned, blocked,
affected by flood, etc. To avoid allocations in a particular cell/ cells, a heavy penalty cost is assigned to
the cells/ cell and the problem is solved in the usual manner.
In the production units, overtime production is taken up to increase the production. This will add the
cost of production due to the higher wages paid to the employees involved in overtime. Such wages
paid also included in the transportation cost.
175
www.AgriMoon.Com
System Engineering
There are some transportation problems where the objective is to minimize time rather than
transportation cost. Such problems are usually encountered in hospital management, military services,
fire services, etc. where the speed of delivery or time of supply is more important than the
transportation cost.
Now, while solving problems where the objective is to minimize time for each route, the cost per unit is
replaced by the time required to ship the quantity xij from origin i to destination j, where i=1,2,3, …..
,m and j= 1,2,3, ….. ,n. The corresponding transportation matrix is given below.
m n
and Σ ai = Σ b j
i =1 j=1
176
www.AgriMoon.Com
System Engineering
Note that the time of shipment is independent of the number of units shipped. Also since shipments
from origins to destinations can be done at the same time on different routes, the shipment time of the
total plan is not the sum total of the times of the individual routes. In fact, the shipment of a feasible
plan will be complete. Such problems, therefore, require a different solution procedure.
Let, Tk be the largest time associated with kth feasible plan. Our objective is, therefore, to find out a
plan for which Tk is minimum of all values of k. The procedure for getting minimum Tk consists of the
following steps:
Step I: Find an initial basic feasible solution. This is obtained by using the same method as for the
normal transportation technique.
Step II: Find Tk corresponding to the current feasible solution and cross out all the non-basic cells for
which tij ≥Tk.
Step III: Draw a closed path (as in the normal transportation technique) for the basic variable associated
with Tk such that when the values at the corner elements are shifted around, this basic variable reduces
to zero and no variable becomes negative. This procedure ends if no such closed path can be traced out,
otherwise repeat step II.
The transportation models studied above will normally be valid for a limited period only. In actual
practice, the resource capacities and/or destination requirements may vary with time. Likewise, there
may be some changes in the transportation cost. Such changes may affect the optimal allocation and the
associated transportation cost. One way to study the effect of these changes is to solve the problem a
new. Many a times, however, it may not be necessary to do so and the new optimal solution may be
obtained by simply incorporating the changes in the current optimal solution, seeing the effects of these
changes and carrying out iterations if required.
An increase in the costs of empty cells will not change the current optimal solutions as the current cost
itself is too high, that is why there have been no allocations in these cells.
However, a reduction in costs of empty cells or an increase in costs of allocated cells is likely to change
the transportation schedule. In this case the problem is re-considered with the current optimal solution.
New values of ui and vj numbers are computed and evaluations of the empty cells are determined. If
they are all non-negative, the current solution still remains optimal. If not, a new solution is obtained
which is then tested for optimality.
The transportation problem assumes that direct routes exist from each source to each destination.
However, there are situations in which units may be shipped from one source to another or to other
destinations before reaching their final destination. This is called a trans-shipment problem. For
example, movement of material involving two different modes of transport – road and railways or
between stations connected by broad gauge to metre gauge lines will necessarily require
transshipment. For the purpose of transshipment the distinction between a source and destination is
dropped so that a transportation problem with m sources n destinations gives rise to a transshipment
177
www.AgriMoon.Com
System Engineering
problem will involve [(m+n)+(m+n)–1] or [2m+2n–1] basic variables and if we omit the variables
appearing in the (m+n) diagonal cells, we are left with [m+n–1] basic variables.
In the trans-shipment problem, as each source or destination is a potential point of supply as well as
demand, the total supply, say of N units, is added to the actual supply of each source, as well as to the
actual demand at each destination. Also the ‗demand‘ at each source and ‗supply‘ at each destination
are set equal to N.
Therefore, we may assume the supply and demand of each location to be fictitious one. These qualities
(N) may be regarded as buffer stocks and each of these buffer stocks should at least be equal to the total
supply/demand in the given problem.
The given trans-shipment problem can, therefore, be regarded as the extended transportation problem
and can hence be solved by the transportation technique. In the final solution, units transported from a
point to itself i.e., in diagonal cells are ignored as they do not have any physical meanings as there is no
transportation involved.
We know any linear programming problem has its dual. Since the transportation problem is a special
type of linear programming problem, it also has its dual with usual interpretations and applications. To
illustrate let us consider example along with the transportation cost table. The mathematical model
(Primal) for this problem is rewritten below:
Minimize, Z = 2x11 + 3x12 + 11x13 + 7x14 + x21 + 0x22 + 2x11 + 6x23 + x24 + 5x31 + 8x32 + 15x33 + 9x34 ,
Subject to constraints
maximize
Subject to
178
www.AgriMoon.Com
System Engineering
u1+v1≤ 2,
u1+v2≤3,
u1+v3≤11,
u1+v4≤ 7,
u2+v1≤ 1,
u2+v2≤ 0,
u2+v3≤ 6,
u2+v4≤ 1,
u3+v1≤ 5,
u3+v2≤ 8,
u3+v3≤15,
u3+v4≤9,
i =1,2,3 ; j=1,2,3,4.
1. The dual variables ui and vj are the row numbers and column numbers respectively in
table, used in solving the problem by the modified distribution method. In dual, ui may
be interpreted as the value of the product, free on board, at the ith origin and, therefore,
may be called location rent and vj can be interpreted as its value (delivered) at the jth
destination and, therefore, may be termed market prize. Hence Z‘ which represents the
sum of these two factors is to be maximized. The constraints of the dual indicate that to
allocate in a cell, the transportation cost in that cell should not be more than the sum of
these two factors for that cell.
2. We know that in case of linear programming, the final (optimal) simplex table also
represents the optimal solution of the dual without actually solving it. Likewise, the
optimal (final) transportation table of the primal represents the optimal solution of the
associated dual. For the problem under consideration, the optimal dual solution as given
by table.
u1=1, u2=- 4, u3=5, v1= 0, v2=2, v3=10, v4=4 .
value of
Z‘max = Rs. 100 [ 6 x 1 – 1 x 4 + 10 x 5 + 7 x 0 +5 x 2 + 3 x 10 + 2 x 4 ]
= Rs. 100 [ 6 – 4 + 50 + 0 + 10 + 30 + 8 ]
= Rs. 10,000 , which is same as Z‘ min .
179
www.AgriMoon.Com
System Engineering
If the problem can be formulated (modeled) as one of minimizing some given cost, such as
transportation expense, the methods of distribution linear programming are useful techniques for
minimizing the cost function subject to supply and demand constraints.
Distribution linear programming methods are widely used for minimizing transportation costs and are
indeed useful in numerous other maximization or minimization situations, such as maximizing
revenue available from various alternative locations, minimizing unit production costs, and
minimizing materials handling costs. The demand requirements and supply availabilities (demand-
supply constraints) are typically formulated in a rectangular arrangement (matrix) with the transported
amounts (cell loadings) being governed by the cost or profit for the particular supply- demand route.
Several methods of obtaining initial and final solutions have been developed, some of which include
the following.
I. Initial solutions
The following example will illustrate the use of an initial allocation via the North West corner method
and a final solution via the stepping- stone method. These are not usually the most expedient methods
to follow when the problem has any degree of complexity, but they have intuitive value and quickly
convey the basic methodology. An optional problem in the solved problem section at the end of this
chapter illustrates the use of the minimum cost method.
The solution procedure necessitates that only unused transportation paths (vacant cells) be evaluated,
and there is only one available pattern of moves to evaluate each vacant cell. This is because moves are
restricted to occupied cells. Every time a vacant cell is filled, one previously occupied cell must become
vacant. The initial (and continuing) number of entries is always maintained at R+C-1, that is, number of
rows plus number of columns minus one. When a move happens to cause fewer entries (for example,
when two cells become vacant at the same time but only one is filled), a ―zero‖ entry must be retained
in one of the cells to avoid what is termed a ―degeneracy‖ situation. The zero entry should be assigned
to an independent cell, that is, to one that cannot be reached by a closed path involving only filled cells.
The cell with the zero entry is then considered to be an occupied and potentially usable cell.
A second potentially troublesome situation may arise when supply and demand are unequal. In this
situation a ―dummy‖ supply plant or absorption location can be created either to produce the
additional needed supply or to absorb the excess supply.
180
www.AgriMoon.Com
System Engineering
If demand > supply: create a dummy supply and assign zero transportation cost to it so excess demand
is satisfied.
If supply> demand: create a dummy demand and assign zero transportation cost to it so excess supply
is absorbed.
This corresponds to a fundamental linear programming rule which holds that the number of
variables in solution must equal the number of constraints that are binding.
Problem No.1:
Obtain an initial basic feasible solution to the following distribution of products to various destinations
from the sources.
a1 a2 a3 a4
b1 11 13 17 14 250
b2 16 18 14 10 300
b3 21 24 13 10 400
Solution : Since, Sai=Sbj=950, there exists a feasible solution to the transportation problem. The initial
feasible solution can be obtained as given below.
Step 1: Starting with the cell at the upper left (north-west) corner of the transportation matrix, allocate
as much as possible so that either the capacity of the first row is exhausted or the destination
requirement of the first column is satisfied. i.e x11=min(a1,b1).
Step 2: If b1> a1, the move down vertically to the second row and make the second allocation of
magnitude x12 = min (a2,b1- x11) in the cell (2,1).
If b1<a1, then move right horizontally to the second column and make the second allocation of
magnitude x12 = min (a1 - x11,b2) in the cell (1,2).
If, b1=a1, there is a tie for the second allocation of magnitude x12 = min (a1 - a1 ,b1) = 0 in the cell (1,2), or
x21=min(a2,b1- b1 ) = 0 in the cell (2,1).
181
www.AgriMoon.Com
System Engineering
Step 3: Repeat steps 1 and 2 moving down towards the lower right corner of the transportation table
until all the rim requirements are satisfied.
The transportation table of the given problem has 12 cells. Following north-west corner rule, the first
allocation is made to the cell (1, 1), the magnitude being x11 = min. (250, 200) = 200. The second
allocation is made to the cell (1, 2) and the magnitude of the allocation is given by,
The third allocation is made in the cell (2, 2), the magnitude being x22= min. (300, 225-50)=175. In the
cell (2, 3) is given by x23=min. (300 – 175, 275) = 125. The fifth allocation is made in the cell (3, 3), the
magnitude being x34 = min. (400-150, 250)=250. Hence an initial basic feasible solution to the given
transportation problem is obtained and given below.
Table – 1
= Rs.12,200.
Step 1 : Determine the smallest cost in the cost matrix of the transportation table. Let it be Cij. Allocate
xij = min (ai, bj) in the cell (i,j).
Step 2 : If, xj = ai, cross off the ith row of the transportation table and decrease bj by ai. Go to step3.
If xij = bj, cross off the jth column of the transportation table and decrease ai by bj. Go to step3.
182
www.AgriMoon.Com
System Engineering
If xj = ai = bj, cross off either the ith row or jth column but not both.
Step 3 : Repeat steps1 and 2 for the resulting reduced transportation table until all the rim requirements
are satisfied. Whenever the minimum cost is not unique, make an arbitrary choice among the minima.
Problem: Obtain an initial basic feasible solution to the following distribution of products to various
destinations from the sources as given in Problem No.1.
a1 a2 a3 a4
b1 11 13 17 14 250
b2 16 18 14 10 300
b3 21 24 13 10 400
Solution : Since, Sai=Sbj=950, there exists a feasible solution to the transportation problem. The initial
feasible solution can be obtained as given below following Least-Cost Method.
Following the least cost method, the first allocation is made in the cell (3,4), the magnitude being x 34 =
min. (400, 250)=250. This satisfies the requirement at a4 and thus we cross off the fourth column from
the table. The second allocation is made in the cell (1, 1) of magnitude x11 = min. (250, 200) = 200 which
satisfied the required at a1 and therefore, we cross off the first column from the table. This yields table
2.
Table – 1
183
www.AgriMoon.Com
System Engineering
Table – 2
Now there is a tie for third allocation. We choose arbitrarily the cell (1, 2) and allocate x12= min. (50,
225) = 50. Cross off the first row. Fourth allocation is made in the cell (3, 3) with magnitude x33=
min.(150, 275)=150. After crossing off the third row, it results in table 3.
Table – 3
Table – 4
Fifth allocation is made to the cell (2, 3) of magnitude x23=min. (300, 125) = 125 and the sixth allocation
is given by x22=min (175, 175) = 175.
184
www.AgriMoon.Com
System Engineering
Table - 5
Thus we get the initial basic feasible solution as displayed in table 5. The transportation cost according
to the above route is given by,
Step 1 : The smallest cost in the first row of the transportation table is determined. Let it be Cij. Allocate
the maximum feasible xij=min (a1,bj) in the cell (1,j).
Step 2: If x1j=a1, cross off the 1st row of the transportation table and move down to the second row.
If x1j=bj, cross off the jth column of the transportation table and reconsider the first row with the
remaining availability.
If x1j=a1=bj, cross off the 1st column and make the second allocation x1k=0 in the cell (1,k)
with C1k being the new minimum cost in the first row. Cross of the first row and move down to the
second row.
Step 3: Repeat steps1 and 2 for the resulting reduced transportation table until all the rim requirements
are satisfied.
Problem:
Determine an initial basic feasible solution to the following transportation problem following row
minima method.
A B C
I 50 30 220 1
185
www.AgriMoon.Com
System Engineering
II 90 45 170 3
Requirements 4 2 2
Solution:
Step 1: Determine the smallest cost in the first column of the transportation table. Let it be Ci1. Allocate
the maximum feasible units to xi1=min(ai,b1) in the cell (i,1).
Step 2: If xi1=ai, cross off the ith row of the transportation table and reconsider the first column with the
remaining availability.
If, xi1=b1, cross off the ith column and move towards right to the second column.
186
www.AgriMoon.Com
System Engineering
If, xi1=ai=b1, cross off the ith row and make the second allocation xk1=0 in the cell (k,1) with Ck1 being
the new minimum cost in the first column. Cross of the first column and move down to the second
column.
Step 3: Repeat steps1 and 2 for the resulting reduced transportation table until all the rim requirements
are satisfied.
Problem:
Determine an initial basic feasible solution to the following transportation problem using column
minima method.
A B C
I 16 19 12 14
II 22 13 19 16
III 14 28 8 12
Requirements 10 15 17
Solution :
187
www.AgriMoon.Com
System Engineering
Step 1: Calculate the penalties by taking differences between the minimum and next to minimum unit
transportation costs in each row and each column.
Step 2: Circle the largest row difference or column difference. In the event of a tie, choose either.
Step 3: Allocate as much as possible in the lowest cost cell of the row(or column) having a circled row
(or column) difference.
Step 4: In case the allocation is made fully to a row (or column) , ignore that row(or column) for
further consideration, by crossing it.
Step 5: Revise the differences again and cross out the earlier figures. Go to step2.
Step 6: Continue the procedure until all rows and columns have been crossed out, i.e distribution is
complete.
Problem
188
www.AgriMoon.Com
System Engineering
a1 a2 a3 a4
b1 11 13 17 14 250
b2 16 18 14 10 300
b3 21 24 13 10 400
Solution: Since, Sai=Sbj=950, there exists a feasible solution to the transportation problem. The initial
feasible solution can be obtained as given below.
Following the Vogels approximation method, the differences between the smallest and next to smallest
costs in each row and each column are computed and displayed inside the parenthesis against the
respective rows and columns. The largest of these differences is (5) and is associated with the first
column of the transportation table.
Since the minimum cost in the first column is c11= 11, allocate x11=min. (250, 200)=200 in the cell (1,1).
This exhausts the requirement of the first column and, therefore, cross off the first column. The row
and column differences are now computed for the resulting reduced transportation table 1, the largest
of these is (5) which is associated with the second column. Since c12 (=13) is the minimum cost,
allocate x12 = min. (50, 225) = 50.
Table – 1
189
www.AgriMoon.Com
System Engineering
Table – 2
Thus exhausts the availability of first row and, therefore, we cross off the first row. Continuing in this
manner, the subsequent reduced transportation tables and the differences for the surviving rows and
columns are shown in table:
Eventually, the basic feasible solution obtained is shown in the following table:
190
www.AgriMoon.Com
System Engineering
191
www.AgriMoon.Com
System Engineering
Solving transportation problems using - north west corner rule (NWC) , least cost or matrix minima
method, row minima method, column minima method, Vogels approximation method (VAM or
penalty method), transportation algorithm (modified distribution method - MODI method),
unbalanced transportation problem.
Consider the matrix giving the initial feasible solution for the problem under consideration. Let us start
with any arbitrary empty cell (a cell without allocation), say (3, 2) and allocate + 1 unit to this cell.
As already discussed, in order to keep up the column 2 restriction, -1 must be allocated to cell (1, 2) and
to keep up the row 1 restriction, +1 must be allocated to cell (1,1) and consequently -1 must be allocated
to cell (3, 1); this is shown in the matrix below.
Table
The net change in transportation cost as a result of this perturbation is called the evaluation of the
empty cell in question.
Therefore,
= Rs. (0 x 100)
= Rs.0.
Thus the total transportation cost increases by Rs.0 for each unit allocated to cell (3,2). Likewise, the net
evaluation (also called opportunity cost) is calculated for every empty cell. For this the following
simple procedure may be adopted.
192
www.AgriMoon.Com
System Engineering
Starting from the chosen empty cell, trace a path in the matrix consisting of a series of alternate
horizontal and vertical lines. The path begins and terminals in the chosen cell. All other corners of the
path lie in the cells for which allocations have been made. The path may skip over any number of
occupied or vacant cells. Mark the corner of the path in the chosen vacant cell as positive and other
corners of the path alternatively –ve, +ve, -ve and so on. Allocate I unit to the chosen cell; subtract and
add 1 unit from the cells at the corners of the path, maintaining the row and column requirements. The
net change in the total cost resulting from this adjustment is called the evaluation of the chosen empty
cell. Evaluation of the various empty cells (in hundreds of rupees) are:
If any cell evaluation is negative, the cost can be reduced so that the solution under consideration can
be improved i.e., it is not optimal. On the other hand, if all cell evaluations are positive or zero, the
solution in question will be optimal. Since evaluations of cells (1, 3) and (2, 3) are –ve, initial basic
feasible solution given in table 3.15 is not optimal.
Now in a transportation problem involving m rows and n columns, the total number of empty cells will
be,
Therefore, there are (m-1) (n-1) such cell evaluations which must be calculated and for large problems,
the method can be quite inefficient. This method is named ‗stepping-stone‘ since only occupied cells or
‗stepping stones‘ are used in the evaluation of vacant cells.
Various steps involved in solving any transportation problem may be summarized in the following
iterative procedure:
Step1: Find the initial basic feasible solution by using any of three methods discussed above.
Step2: Check the number of occupied cells. If there are less than m+n-1, there exists degeneracy and it
is possible to introduce a very small positive assignment of Î(»0) in suitable independent positions, so
that the number of occupied cells is exactly equal to m+n+1.
Step 3: For each occupied cell in the current solution, solve the system of equations
ui+vj=cij.
193
www.AgriMoon.Com
System Engineering
Starting initially with some ui=0 or vj=0 and entering the successively the values of ui and vj in the
transportation table margins.
Step 4: Compute the net evaluation zij-cij=ui+vj-cij for all unoccupied basic cells and enter them in the
upper right corners of the corresponding cells.
Step 5: Examine the sign of each zij-cij. If all zij-cij £ 0 , then the current basic feasible solution is an
optimum one. If atleast one zij-cij > 0, select the unoccupied cells, having the largest positive net
evaluation to enter the basis.
Step 6: Let the unoccupied cell (r,s) enter the basis. Allocate an unknown quantity, say q, to the cell
(r,s). Identify a loop that starts and ends at the cell (r,s) and connects some of the basic cells. Add and
subtract interchangeably, q to and from the transition cells of the loop in such a way that the rim
requirements remain satisfied.
Step 7: Assign a maximum value to q in such a way that the value of one basic variable becomes zero
and the other basic variables remain non-negative. The basic cell whose allocation has been reduced to
Zero, leaves the basis.
Step8: Return to step 3 and repeat the process until an optimum basic feasible solution has been
obtained.
For a feasible solution to exist in a transportation problem, it is necessary that the total supply must
equal demand. That is, . But a situation may arise when the total available supply is not equal to the
total requirement. Such type of transportation problem is called unbalanced transportation problem.
Problem:
Find the starting solution in the following transportation problem by any one of the methods (North-
west Corner Method, Least–Cost Method, Vogel‘s Approximation Method, Row minima method or
column minima method). Also obtain the optimum solution by using the best starting solution:
D1 D2 D3 D4
S1 3 7 6 4 5
S2 2 4 3 2 2
S3 4 3 8 5 3
194
www.AgriMoon.Com
System Engineering
Demand 3 3 2 2
Step 1: In this problem we find the basic feasible solution by using Vogel‘s approximation method.
By Vogel‘s Approximation Method, the differences between the two successive lowest costs for each
row and each column are computed. These are written besides the corresponding rows or columns
under the heading ‗row difference‘ or ‗column difference‖:
The largest row difference or column difference is 3 which corresponds to third column. Allocating as
much as possible to the lowest cost cell in the third column give x23 = 2. This satisfies the supply at
S2 and the requirement at D3. So arbitrarily we cross off the third column and consider e1 (0) as the
small quantity to be supplied form S2. The row and column differences are now recomputed for the
reduced cost matrix, and choose the largest of these, i.e., 2 which corresponds to fourth column.
Therefore allocate x24 = e1 and second row is now eliminated. Again, compute the row and column
differences for the reduced 2x3 transportation table and choose the largest of these, i.e., 4
corresponding to the second column. Thus allocate x32 = 3 and eliminate second column while
consider e2 (0) being the negligible positive quantity to be supplied form S3. Again, computing the
column and row differences in the reduced 2x2 cost matrix, we assign x11 = 3 and thus eliminate first
column. This leaves now only fourth column, which can be filled by inspection and thus we assign
x14 = 2 and x34e2.
195
www.AgriMoon.Com
System Engineering
Step 2: From the initial basic feasible solution obtained in step 1, it is observed that the best starting
solution is obtained using Vogel‘s approximation method having the least transportation cost of 32.
Also, observe that unknown quantities e1, e2 (> 0) have been allocated in the unoccupied cells (2,4) and
(3,4) respectively to overcome the danger of degeneracy.
Step 3: Now compute the numbers ui (i = 1,2,3) and vj (j = 1,2,3,4) using successively the equations ui +
vj = cij for all the occupied cells. For this it may be arbitrarily assigned as, v4 = 0. Thus we have
u1 + v4 = c14 u1 + 0 = 4 u1 = 4
u2 + v4 = c24 u2 + 0 = 2 u2 = 2
u3 + v4 = c34 u3 + 0 = 5 u3 = 5
Given u1,u2 and u3, values of v1,v2 and v3 can be calculated as shown below :
u1 + v1 = c11 4 + v1 = 3 v1 = -1
u2 + v2 = c23 2 + v3 = 3 u3 = 1
u3 + v3 = c32 5 + v2 = 3 v2 = -2
The net evaluations for each of the unoccupied cells are now determined:
It is possible to present a more compact form for computing the unknown ut‘s and vj‘s and then
evaluate the net evaluations for each of the unoccupied cells in a more convenient way by working in
the transportation table margins:
196
www.AgriMoon.Com
System Engineering
The transportation cost associated with the optimum schedule is given by:
= 32 + 2 1 +5 2
197
www.AgriMoon.Com
System Engineering
1. Introduction
The assignment problem is defined as assigning each facility to one and only one job so as to optimize
the given measures of effectiveness, when n facilities and n jobs are available and given the
effectiveness of each facility for each job.
Let there be n facilities (machines) to be assigned to n jobs. Let cij is cost of assigning ith facility to jth job
and xij represents the assignment of ith facility to jth job. If ith facility can be assigned to jth job, xij=1,
otherwise zero. The objective is to make assignments that minimize the total assignment cost or
maximize the total associated gain.
Thus an assignment problem can be represented by n x n matrix which continues n! possible ways of
making assignments. One obvious way to find the optimal solution is to write all the n! possible
arrangements, evaluate the cost of each and select the one involving the minimum cost.
198
www.AgriMoon.Com
System Engineering
However, this enumeration method is extremely slow and time consuming even for small values of n.
For example, for n = 10, a common situation, the number of possible arrangements is 10! = 3,628,800.
Evaluation of so large a number of arrangements will take a probability large time. This confirms the
need for an efficient computational technique for solving such problems.
subject to constraints
If the last condition is replaced by xij ≥0, this will be a transportation model with all requirements and
available resources equal to 1.
An assignment model may be regarded as a special case of the transportation model. Here, facilities
represent the ‗sources‘ and jobs represent the ‗destinations‘. Number of sources is equal to the number
of destinations, supply at each source is unity (ai = 1 for all i) and demand at each destination is also
unity (bj = 1, for all j). The cost of ‗transporting‘ (assigning) facility i to job j is cij and the number of
units allocated to a cell can be either one or zero. i.e., they are non-negative quantities.
199
www.AgriMoon.Com
System Engineering
However the transportation algorithm is not very useful to solve this model, when an assignment is
made, the row as well as column requirements are satisfied simultaneously (rim conditions being
always unity) resulting in degeneracy. Thus the assignment problem is a completely degenerate form
of the transportation problem. In n x n problem, there will be n assignments instead of n+n–1 or 2n–1–
n = n–1 epsilons which will make the computations quite cumbersome. However, the special structure
of the assignment model allows a more convenient and simple method of solution.
(a) Supply at any source may be any Supply at any source (machine) will be 1
positive quantity ai i.e., ai =1.
(b) Demand at any destination may be Demand at any destination (job) will be
any positive quantity bj 1 i.e., bj = 1.
4. Theorems
The technique used for solving assignment model makes use of the following two theorems:
4.1. Theorem I
It states that in an assignment problem, if we add or subtract a constant to every element of a row (or
column) in the cost matrix, then an assignment which minimizes the total cost on one matrix also
minimizes the total cost on the other matrix‖.
Let, cij represent the original cost elements of the matrix. If constants ui and vj are subtracted from
the ith row jth column respectively, the new cost elements will be
200
www.AgriMoon.Com
System Engineering
and
Likewise, if in an assignment problem some cost elements are negative, we may convent them into an
equivalent assignment problem where all the cost elements are non-negative by adding a suitably large
constant to the elements of the relevant row.
4.2. Theorem II
It states ―If all cij ≥ 0 and we can find a set xij=x’ij, such that
The result follows automatically since as neither of cij is negative, the value of
201
www.AgriMoon.Com
System Engineering
cannot be negative.
The above two theorems indicate that if one can create a new cij' matrix with zero entries, and if these
zero elements, or a subset thereof, constitute feasible solution, then this feasible solution is the optimal
solution.
Thus the method of solution consists of adding and subtracting constant from rows and columns until
sufficient number of cij's become zero to yield a solution with a value of zero.
The cost of any action consists of opportunities that are sacrificed in taking that action. Consider the
following table which contains the cost in rupees of processing each of jobs, A, B and C on
machines X,Y and Z.
If job A is assigned to machine X, the cost of this assignment is Rs. 25. Since machine Y can also
process job A for Rs. 15, clearly assigning job A to machine X is not the best decision. Therefore, when
job A is arbitrarily assigned to machine X, it is done by sacrificing the opportunity to save Rs. 10 (Rs. 25
– Rs. 15). This sacrifice is referred to as an opportunity cost. The decision to process job A on
machine X precludes the assignment of this job to machine Y, given the constraint that one and only
one job can be assigned to a machine. Thus opportunity cost of assigning job A to machine X is Rs.10
with respect to the lowest cost assignment for job A. Likewise, a decision to assign job A to
machine Z would involve an opportunity cost of Rs. 7 (Rs. 22 – Rs. 15). Theassignment of job A to
machine Y is the best assignment as the opportunity cost of this assignment is zer (Rs.15-Rs.15). This is
called the machine – opportunity costs with regard to job A. Similarly, if the lowest cost of row B is
202
www.AgriMoon.Com
System Engineering
subtracted from all the costs in this row, the machine-opportunity costs for job B can be obtained. By
following the same step, the machine opportunity cost for job C can be obtained . This is given in the
following table.
In addition to these machine-opportunity costs, there are job-opportunity costs also. Job A, B and C, for
instance, could be assigned to machine X. The assignment of job B to machine X involves a cost of Rs.
31, while the assignment of job A to machine X costs only Rs. 25. Therefore, the opportunity costs of
assigning job B to machine X is Rs. 6 (Rs. 31 – Rs. 25). Similarly, the opportunity cost is involved in
the assignment of job A to machine X is Rs. 10 (Rs. 35 – Rs. 25). A zero opportunity cost is involved in
the assignment of job A to machine X, since this is the best assignment for machine X (column X).
Hence job-opportunity costs for each column (each machine) are obtained by subtracting the lowest
cost entry in each column from all cost entries in that column, if the lowest entry in each column of
table is subtracted from all the cost entries of that column, the resulting table is called total opportunity
cost table.
Machines
The objective is to assign the jobs to the machines to manimize total costs. With the total opportunity
cost table this objective will be achieved if the jobs are assigned to the machines in such a way as to
obtain a total opportunity cost of zero. Four cells in the total opportunity cost table contains zeros,
203
www.AgriMoon.Com
System Engineering
indicating a zero opportunity cost for these cells (assignment). Hence job A could be assigned to
machine X or Y and job B to machine Z, all assignments having zero opportunity costs. This way job C,
however, could not be assigned to any machine with a zero opportunity cost since assignment of
job B to machine Z precludes the assignment of job C to this machine. Clearly, to make an optimal
assignment of the three jobs to the three machines, there must be three zero cells in the table such that a
complete assignment to these cells can be made with a total opportunity cost of zero.
Drawing minimum number of lines covering all zero cells in the total opportunity cost table with
minimum number of lines equals the number of rows (or columns) in the table is a convenient method
for determining whether an optimal assignment is made If, however, the minimum number of lines is
less than the number of rows (or columns), an optimal assignment cannot be made. In this case there is
need to develop a new total opportunity cost table. In the present example, since it requires only two
lines to cross (cover) all zeros, and there are three rows, an optimal assignment is not possible. Clearly,
there is a need to modify the total opportunity cost table by including some assignment not in the rows
and columns covered by the lines. Of course, the assignment chosen should have the least opportunity
cost. In the present case it is the assignment of job B to machine Y with an opportunity cost of 1. In
other words, we would like to change the opportunity cost for this assignment from 1 to zero.
Machines
To accomplish this (a) choose the smallest elements in the table not covered by a straight line and
subtract this element from all other elements not having a line through them (b) add this smallest
element to all elements lying at the intersection of any two lines. The revised total opportunity cost
table is shown below.
Machines
204
www.AgriMoon.Com
System Engineering
The test for optimal assignment described above is applied again to the revised opportunity cost table.
As the minimum number of lines covering all zeros is three and there are three rows (or columns), an
optimal assignment can be made. The optimal assignments are A to X, B to Y and C to Z.
In larger problems there is need for more systematic procedure, as the assignments may not be readily
apparent.
205
www.AgriMoon.Com
System Engineering
First check whether the number of rows is equal to the number of columns, If it is so, the assignment
problem is said to be balanced. Then proceed to step 1. If it is not balanced, then it should be balanced
before applying the algorithm.
Step 1: Subtract the smallest cost element of each row from all the elements in the row of the given cost
matrix. See that each row contains atleast one zero.
Step 2: Subtract the smallest cost element of each column from all the elements in the column of the
resulting cost matrix obtained by step 1.
(a) Examine the rows successively until a row with exactly one unmarked zero is found. Make an
assignment to this single unmarked zero by encircling it. Cross all other zeros in the column of this
encircled zero, as these will not be considered for any future assignment. Continue in this way until all
the rows have been examined.
(b) Examine the columns successively until a column with exactly one unmarked zero is found. Make
an assignment to this single unmarked zero by encircling it and cross any other zero in its row.
Continue until all the columns have been examined.
(a) If each row and each column contain exactly one encircled zero, then the current assignment is
optimal.
(b) If atleast one row/column is without an assignment (i.e., if there is atleast one row/column is
without one encircled zero), then the current assignment is not optimal. Go to step 5.
Step 5: Cover all the zeros by drawing a minimum number of straight lines as follows.
(b) Mark (√) the columns (not already marked) that have zeros in marked rows.
(c) Mark (√) the rows (not already marked) that have assignments in marked columns.
(e) Draw lines through all unmarked rows and marked columns. If the number of these lines is equal
to the order of the matrix then it is an optimum solution otherwise not.
206
www.AgriMoon.Com
System Engineering
Step 6: Determine the smallest cost element not covered by the straight lines. Subtract this smallest
cost element from all the uncovered elements and add this to all those elements which are lying in the
intersection of these straight lines and do not change the remaining elements which lie on the straight
lines.
Problem:
A works manager has to allocate four different jobs to four workmen. Depending on the efficiency and
the capacity of the individual the times taken by each differ as shown in the Table 1. How should the
tasks be assigned one job to a worker so as to minimize the total man-hours?
Table 1
Solution:
STEP 1
Consider each row. Select the minimum element in each row. Subtract this smallest element form all
the elements in that row. This results in the table 2.
Table 2
207
www.AgriMoon.Com
System Engineering
STEP 2
Subtract the minimum element in each column from all the elements in its column. This will result in
Table 3.
Table 3
STEP 3
In this way we make sure that in the matrix each row and each column has atleast one zero element.
Having obtained atleast one zero in each row and each column, we assign starting from first row. In
the first row, we have a zero in (1,A). Hence we assign job 1 to the worker A. This assignment is
indicated by a square. All other zeros in the column are crossed (X) to show that the other jobs cannot
be assigned to worker A, who has already been assigned. In the above problem we do not have other
zeros in column A.
Proceed to the second row where there is a zero in (2,C) . Hence the job 2 can be assigned to
worker C, indicating by a square. Any other zero in this column is crossed (X).
Proceed to the third row. Here we have two zeros corresponding to (3,B) and (3, D). Since there is a tie
for the job 3, go to the next row deferring the decision for the present. Proceeding to the fourth row,
there IS only one Zero in (4, D). Hence assign job 4 to worker D. Now the column D has a zero in the
third row and cross (3, D). All the assignments made in this way are as shown in Table 4.
208
www.AgriMoon.Com
System Engineering
Table 4
STEP 4
Now having assigned certain jobs to certain workers we proceed to the column 1. Since there is an
assignment in this column, we proceed to the second column. There is only one zero in the cell (3, B);
We assign the jobs 3 to worker B. Thus all the four jobs have been assigned to four workers. Thus we
obtain the solution to the problem as shown in the Table 5
Table 5
209
www.AgriMoon.Com
System Engineering
1. Subtract the minimum element in each row from all the elements in its row to make sure
that at least there is one zero in that row.
2. Subtract the minimum element in each column from all the elements in its column in the
above reduced matrix, to make sure that atleast one zero exists in each column.
3. Having obtained atleast one zero in each row and atleast one zero in each column,
examine rows successively until a row with exactly one unmarked zero is found and
mark (X) this zero, indicating that assignment in made there. Mark (X) all other zeros in
the same column, to show that they cannot be used to make other assignments. Proceed
in this way until all rows have been examined. If there is a tie among zeros defer the
decision.
4. Next consider columns, for single unmarked zero, mark them ( ) and mark (X) any
other unmarked zero in their rows.
5. Repeat (c) and (d) successively until one of the two occurs
(2) The remaining unmarked zeros lie atleast two in each row and column. i.e., they occupy corners
of a square.
If the outcome is (1), we have a maximal assignment. In the outcome (2) we use arbitrary assignments.
This process may yield multiple solutions.
Problem:
A 48 48 50 44
B 56 60 60 68
Solution: C 96 94 90 85
STEP 1:
D 42 44 54 46
210
www.AgriMoon.Com
System Engineering
A 4 4 6 0
B 0 4 4 12
C 11 9 5 0
Table 6
D 0 2 12 4
STEP 2:
Choose the least element from each column in Table 6 and subtract the same form all the elements in
that column to ensure that there is atleast one zero in each column. This results in the following table
(Table 7)
Table 7
STEP 3:
Make the assignment in each row and column as explained previously. This results in table 8
211
www.AgriMoon.Com
System Engineering
Table 8
Here there are only three assignments, but four assignments are required. With this maximal
assignment, minimum number of lines to cover all the zeros are needed to draw. This is carried out as
explained in steps 4 to 9. Refer Table 9
Table 9
STEP 4:
STEP 5:
Against the marked column 4, look for any (X) element and mark that column (column 4).
212
www.AgriMoon.Com
System Engineering
STEP 6:
Against the marked column 4, look for any assignment and mark that row (row A.)
STEP 7:
STEP 8:
Draw lines through all unmarked rows (row B and Row D) and through all marked columns
(column 4). (Check: There should be only three lines to cover all the zeros).
STEP 9:
Select the minimum from the elements that do not have a line through them. In this example we have 1
as the minimum element, subtract the same from all the elements that do not have a line through them
and add this smallest element at the intersection of two lines. Thus we have the matrix shown in Table
10
Table 10
STEP 10:
Go ahead with the assignment with the usual procedure. This is carried out in the Table 10.
Thus we have four assignments.
213
www.AgriMoon.Com
System Engineering
Example 2
There are five machines and five jobs are to be assigned and the associated cost matrix is as follows.
Find the proper assignment.
Solution:
In order to find the proper assignment, we apply the Hungarian method as follows:
214
www.AgriMoon.Com
System Engineering
From the last table we see that all the zeros are either assigned or crossed out, but the total number of
assignment,i.e., 4<5 (number of jobs to be assigned to machines). Therefore, we have to follow step 4
and onwards as follows:
Step 4:
Step 5:
(i) Subtract 2 from all those elements which are not covered.
215
www.AgriMoon.Com
System Engineering
(ii) Add 2 to those entries which are at the junction of two lines.
Note:
If we are given a maximization problem then convert it into minimization problem, simply,
multiplying by -1 to each entry in the effectiveness matrix and then solve it in the usual manner.
216
www.AgriMoon.Com
System Engineering
INTRODUCTION
Waiting lines are the most frequently encountered problems in everyday life. For example, queue at a
cafeteria, library, bank, etc. Common to all of these cases are the arrivals of objects requiring service
and the attendant delays when the service mechanism is busy. Waiting lines cannot be eliminated
completely, but suitable techniques can be used to reduce the waiting time of an object in the system. A
long waiting line may result in loss of customers to an organization. Waiting time can be reduced by
providing additional service facilities, but it may result in an increase in the idle time of the service
mechanism.
QUEUEING THEORY is based on mathematical theories and deals with the problems arising due to
flow of customers towards the service facility.
The waiting line models help the management in balancing between the cost associated with waiting
and the cost of providing service. Thus, queuing or waiting line models can be applied in such
situations where decisions have to be taken to minimize the waiting time with minimum investment
cost.A flow of customers from in infinite/finite population towards the service facility forms. a queue
(waiting line) on account of lack of capability to serve them all at a time. The queues may be of persons
waiting at a doctor's clinic or at railway booking-office; these may be of machines waiting to be
repaired or of ships in the harbor waiting to be unloaded or of letters arriving at a typist's desk. In the
absence of a perfect balance between the service facilities and the customers, waiting is required either
of the service facilities or for the customer's' arrival.
By the term 'customer' we mean the arriving unit that requires some service to be performed. The
customer may be of persons, machines, vehicles, parts etc. Queues (waiting line) stand for a number of
customers waiting to be serviced. The queue does not include the customer being serviced. The process
or system that performs the services to the customer is termed by service channel or service facility.
QUEUEING SYSTEM
The mechanism of a queuing process is very simple. Customers arrive at service counter and are
attended by one or more of the servers. As soon as a customer is served, he departs from the system.
Thus a queuing system can be described as composed of customers arriving for service, waiting for
service if it is not immediate, and if having waited for service, leaving the system after being served.
The detailed character station of a queuing system is defined by its characteristics discussed in the
following section.
Queuing Model
It is a suitable model used to represent a service oriented problem, where customers arrive randomly to
receive some service, the service time being also a random variable.
217
www.AgriMoon.Com
System Engineering
Arrival
The statistical pattern of the arrival can be indicated through the probability distribution of the number
of the arrivals in an interval.
Service Time
The time taken by a server to complete service is known as service time.
Server
It is a mechanism through which service is offered.
Queue Discipline
It is the order in which the members of the queue are offered service.
Poisson Process
is the rate of arrival.t, where It is a probabilistic phenomenon where the number of arrivals in an
interval of length t follows a Poisson distribution with parameter
Queue
A group of items waiting to receive service, including those receiving the service, is known as queue.
Queue length
Number of persons in the system at any time.
FIFO
It is the first in first out queue discipline.
Bulk Arrivals
If more than one customer enter the system at an arrival event, it is known as bulk arrivals.
1. Input Source: The input source generates customers for the service mechanism. The most
important characteristic of the input source is its size. It may be either finite or infinite. Please
note that the calculations are far easier for the infinite case, therefore, this assumption is often
218
www.AgriMoon.Com
System Engineering
made even when the actual size is relatively large. If the population size is finite, then the
analysis of queuing model becomes more involved.
The statistical pattern by which calling units are generated over time must also be specified. It
may be Poisson or Exponential probability distribution. Usually the source population is
considered as unlimited.
2. Queue: It is characterized by the maximum permissible number of units that it can contain.
Queues may be infinite or finite.
3. Service Discipline: It refers to the order in which members of the queue are selected for service.
Frequently, the discipline is first come, first served.
Priority System
Customer's Behaviour
1. Balking. A customer may not like to join the queue due to long waiting line.
2. Reneging. A customer may leave the queue after waiting for sometime due to impatience.
3. Collusion. Several customers may cooperate and only one of them may stand in the queue.
4. Jockeying. When there are a number of queues, a customer may move from one queue to
another in hope of receiving the service quickly.
Server's Behaviour
Changing service rates. A server may speed up or slow down, depending on the number of
customers in the queue. For example, when the queue is long, a server may speed up in
response to the pressure. On the contrary, it may slow down if the queue is very small.
219
www.AgriMoon.Com
System Engineering
Assumptions:
The inter-arrival time has an exponential probability distribution with a mean arrival rate of l
customer arrivals per unit time.
The service time has an exponential probability distribution with a mean service rate of m
service completions per unit time.
The mean arrival rate is less than the mean service rate, i.e., l < m.
220
www.AgriMoon.Com
System Engineering
The Input Process. It expresses the mode of arrival of customers at the service facility governed by
some probability law. The number of customers emanate from finite or infinite sources. Also, the
customers may arrive at the service facility in batches of fixed size or of variable size or one by one. In
the case when more than one arrival is allowed to enter the system simultaneously, (entering the
system does not necessarily mean entering into service), the input is said to occur in bulk or batches.
It is also necessary to know the reaction of a customer upon entering the system. A customer may
decide to wait no matter how long the queue becomes, or if the queue is too long to suit him, may
decide not to enter it. If a customer decides not to enter the queue because of its huge length, he is said
to have balked. On the other hand, a customer may enter the queue, but after some time loses patience
and decides to leave. In this case he is said to have reneged. In the case when there are two or more
parallel queues, the customer may move from one queue to another for his personal economic gains,
that is jockey for position.
The final factor to be considered regarding the input process is the manner in which the arrival pattern
changes with time. The input process which does not change with time is called a stationary input
process. If it is time dependent then the process is termed as transient.
The Queue Disline. cipIt is a rule according to which customers are selected for service when a queue
has been formed. The most common discipline is the "first come, first served" (FCFS), or "first in, first
out" (FIFO) rule under which the customers are serviced in the strict order of their arrivals. Other
queue disciplines include: "last in, first out" (LIFO) rule according to which the last arrival in the
system is serviced first, "selection for service in random order" (SIRO) rule according to which the
arrivals as serviced randomly irrespective of their arrivals in the system; and a variety of priority
schemes-according to which a customer's service is done in preference over some other customer's
service.
Under priority discipline, the service is of two types. In the first, which is called pre-emptive, the
customers of high priority are given service over the low priority customer. In the second type, called
the non-pre-emptive, a customer of low priority is serviced before a customer of high priority is
entertained for service.
In the case of parallel channels "fastest server rule" (FSR) is adopted. For its discussion we suppose that
the customers arrive before parallel service channels. If only one service channel is free, then incoming
customer is assigned to free service channel. But it will be more efficient to assume that an incoming
customer is to be assigned a server of largest service rate among the free ones.
The Service Mechanism. This means the arrangement of server-s facility to serve the customers. If
there are infinite numbers of servers then all the customers are served instantaneously on arrival and
there will be no queue.
If the number of servers is finite, then the customers are served according to a specific order. Further,
the customers may be served in batches of fixed size or of variable size rather than individually by the
221
www.AgriMoon.Com
System Engineering
same server, such as a computer with parallel processing or people boarding a bus. The service system
in this case is termed as bulk service system.
Sometimes, the service rate may also depend on the number of customers, waiting for service. For
example, when the queue becomes longer, a server may work faster or, conversely, may become less
efficient. The situation in which service depends upon the number of waiting customers is referred to
as state dependent-system.
The Capacity of the System. Some of the queueing processes admit the physical limitation to the
amount of waiting room, so that when the waiting line reaches a certain length, no further customers
are allowed to enter until space becomes available by a service completion. Such types of situation are
referred to as finite source queues, that is, there is a finite limit to the maximum queue size. The queue
can also be viewed as one with forced balking
Where a customer is forced to balk if he arrives at a time when queue size is at its limit. .
Service Channels: When there are several service channels available to provide service, much depends
upon their arrangements. They may be arranged in parallel or in series or a more complex combination
of both, depending on the design of the system's service mechanism.
By parallel channels we mean a number of channels providing identical service facilities so that several
customers may be serviced simultaneously. Further, customers may wait in a single queue until one of
the service channels is ready to serve, as in a barber shop where many chairs are considered as different
service channels; or customers may form separate queues in front of each service channel as in the case
of super markets.
For series channels, a customer must pass successively through all the ordered channels before service
is completed. The situations may be seen in public offices where parts of the service are done at
different service counters.
A queueing system is called a one-server model when the system has one server only, and a multiple-
server model when the system has a number of parallel channels each with one server.
The following symbols and notations will be used in connection with the queuing systems:
λ / µ = Ρ = traffic intensity.
E(n) = average number of customers in the system. Both waiting and in service.
222
www.AgriMoon.Com
System Engineering
E(v) = average waiting time of a customer in the system, both waiting and in service.
Pn(t) = Probability that there are n customers in the system at any time t, both waiting and in service.
Pn = time independent Probability that there are n customers in the system at any time, both waiting
and in service.
223
www.AgriMoon.Com
System Engineering
Different models in queuing theory are classified by using special (or standard) notations described
initially by D.G.Kendall in 1953 in the form (a/b/c). Later A.M.Lee in 1966 added the symbols d and c
to the Kendall notation. Now in the literature of queuing theory the standard format used to describe
the main characteristics of parallel queues is as follows:
{(a/b/c) : (d/c)}
Where
a = arrivals distribution
d = max. number of customers allowed in the system (in queue plus in service)
Certain descriptive notations are used for the arrival and service time distribution (i.e. to replace
notation a and b) as following:
G = service time (departures) distribution of general type, i.e. no assumption is made about the type of
distribution.
GI = Inter-arrival time (arrivals) having a general probability distribution such as as normal, uniform or
any empirical distribution.
For example, a queuing system in which the number of arrivals is described by a Poisson probability
distribution, the service time is described by an exponential distribution, and there is a single server,
would be designed by M/M/I.
224
www.AgriMoon.Com
System Engineering
The Kendall notation now will be used to define the class to which a queuing model belongs. The
usefulness of a model for a particular situation is limited by its assumptions.
The derivation of this model is based on certain assumptions about the queuing system:
or reneging.
3. Queue discipline is ‗first-come, first-serve
4. Single serve with exponential distribution of service time
Performance characteristics
1.Expected (or average) number of customer in the system (customers in the line plus the customer
being served)
2.Expected (or average) queue length or expected number of customers waiting in the queue
225
www.AgriMoon.Com
System Engineering
4.Expected (or average) waiting time of a customer in the system (waiting and service)
5.Expected (or average) waiting time in the queue for busy system
Var (n) =
---------------------------------------------------------------
SOLVED EXAMPLES
226
www.AgriMoon.Com
System Engineering
Example1 A television repairman finds that the time spent on his jobs has an exponential distribution
with mean of 30 minutes. If he repairs sets in the order in which they came in, and if the arrival of sets
follows a Poisson distribution approximately with an average rate of 10 per 8-hour day, what is the
repairman‘s expected idle time each day? How many jobs are ahead of the average set just brought in?
λ = 10/8 = 5/4 sets per hour; and µ= (1/30) 60 = 2 sets per hour
(a) Expected idle time of repairman each day = Number of hours for which the repairman remains
busy in an 8-hour day (traffic intensity) is given by
Hence, the idle time for a repairman in an 8-hour day will be: (8 – 5) = 3 hours.
(approx.) TV sets
Example2 On an average 96 patients per 24-hour day require the service of an emergency clinic. Also
on an average, a patient requires 10 minutes of active attention. Assume that the facility can handle
only one emergency at a time. Suppose that it costs the clinic Rs 100 per patient treated to obtain an
average servicing time of 10 minutes, and that each minutes of decrease in this average time would cost
Rs. 10 per patient treated. How much would have to be budgeted by the clinic to decrease the average
size of the queue from one and one-third patients to half patient.
227
www.AgriMoon.Com
System Engineering
3.When the average queue size is decreased from 4/3 patient, the new service rate is determined as:
Average rate of treatment required is: = 7.5 minutes, i.e. a decrease in the average rate of
treatment is 2.5(= 10 – 7.5) minutes.
Example 3 Customers arrive at a one-window drive according to a Poisson distribution with mean of
10 minutes and service time per customer is exponential with mean of 6 minutes. The space in front of
the window can accommodate only three vehicles including the serviced one. Other vehicles have to
wait outside this space. Calculate:
(a) Probability that an arriving customer can drive directly to the space in front of the window.
(b) Probability that an arriving customer will have to wait outside the directed space.
(c) How long an arriving customer is expected to wait before getting the service?
Solution From the data of the Problem, we have λ=6 customers per hour; µ= 10 customers per hour
(a) Probability that an arriving customer can drive directly to the space in front of the window:
(b) Probability that an arriving customer will have to wait outside the directed space:
228
www.AgriMoon.Com
System Engineering
(c) Expected waiting time of a customer before getting the service is:
hr. or 9 minutes.
229
www.AgriMoon.Com
System Engineering
Example1 A television repairman finds that the time spent on his jobs has an exponential distribution
with mean of 30 minutes. If he repairs sets in the order in which they came in, and if the arrival of sets
follows a Poisson distribution approximately with an average rate of 10 per 8-hour day, what is the
repairman‘s expected idle time each day? How many jobs are ahead of the average set just brought in?
Solution
λ = 10/8 = 5/4 sets per hour; and μ = (1/30) 60 = 2 sets per hour
(a) Expected idle time of repairman each day = Number of hours for which the repairman remains
busy in an 8-hour day (traffic intensity) is given by
Hence, the idle time for a repairman in an 8-hour day will be: (8 – 5) = 3 hours.
Example2 On an average 96 patients per 24-hour day require the service of an emergency clinic. Also
on an average, a patient requires 10 minutes of active attention. Assume that the facility can handle
only one emergency at a time. Suppose that it costs the clinic Rs 100 per patient treated to obtain an
average servicing time of 10 minutes, and that each minutes of decrease in this average time would cost
Rs. 10 per patient treated. How much would have to be budgeted by the clinic to decrease the average
size of the queue from one and one-third patients to half patient.
230
www.AgriMoon.Com
System Engineering
(iii)When the average queue size is decreased from 4/3 patient, the new service rate μ is determined as:
Average rate of treatment required is: minutes, i.e. a decrease in the average rate of
treatment is 2.5(= 10 – 7.5) minutes.
Example 3 Customers arrive at a one-window drive according to a Poisson distribution with mean of
10 minutes and service time per customer is exponential with mean of 6 minutes. The space in front of
the window can accommodate only three vehicles including the serviced one. Other vehicles have to
wait outside this space. Calculate:
(a) Probability that an arriving customer can drive directly to the space in front of the window.
(b) Probability that an arriving customer will have to wait outside the directed space.
(c) How long an arriving customer is expected to wait before getting the service?
Solution From the data of the Problem, we have =6 customers per hour; = 10 customers per hour
(a) Probability that an arriving customer can drive directly to the space in front of the window:
231
www.AgriMoon.Com
System Engineering
(b) Probability that an arriving customer will have to wait outside the directed space:
(c) Expected waiting time of a customer before getting the service is:
Example 4: Students arrive at the head office according to a Poisson input process with a mean rate of
40 per hour. The time required to serve a student has an exponential distribution with a mean of 50 per
hour. Assume that the students are served by a single individual, find the average waiting time of a
student.
Solution.
= 4.8 minutes
232
www.AgriMoon.Com
System Engineering
Example 5: New Delhi Railway Station has a single ticket counter. During the rush hours, customers
arrive at the rate of 10 per hour. The average number of customers that can be served is 12 per hour.
Find out the following:
Given
λ = 10/hour, μ= 12/hour
10
Probability that the counter is free = 1- ----- = 1/6
12
(10)2
Average number of customers in the queue (Lq ) = -------- = 25/6
12 (12 - 10)
Example 6: Universal Bank is considering opening a drive in window for customer service.
Management estimates that customers will arrive at the rate of 15 per hour. The teller whom it is
considering to staff the window can service customers at the rate of one every three minutes.
(15)2
Average number in the waiting line = ---------- = 2.25 customers
20(20 - 15)
233
www.AgriMoon.Com
System Engineering
15
Average number in the system = ---------- = 3 customers
20 - 15
15
Average waiting time in line = ------------ = 0.15 hours
20(20 - 15)
1
Average waiting time in the system = --------- = 0.20 hours
20 - 15
234
www.AgriMoon.Com
System Engineering
Network analysis is one of the most popular techniques used for planning, scheduling, monitoring and
coordinating large and complex projects comprising a number of activities. It involves the development
of a network to indicate logical sequence of work content elements of a complex situation. It involves
three basic steps:
Network analysis is concerned with minimizing some measure of performance of the system such as
the total completion time for the project, overall cost and so on. By preparing a network of the system, a
decision maker can identify,
Network analysis is specially suited to project which are not routine or repetitive and which will be
conducted only once or a few times.
Objectives:
1. Minimization of total time: Network analysis is useful in completing a project in the minimum
possible time. A good example of this objective is the maintenance of production line machinery
in a factory. If the cost of down time is very high, it is economically desirable to minimize time
despite high resource costs.
2. Minimization of total cost: Where the cost of delay in the completion of the project exceeds cost
of extra effort, it is desirable to complete the project in time so as to minimize total cost.
3. Minimization of time for a given cost: When fixed sum is available to cover costs, it may be
preferable to arrange the existing resources so as to reduce the total time for the project instead
of reducing total cost.
4. Minimization of cost for a given total time: When no particular benefit will be gained from
completing the project early, it may be desirable to arrange resources in such a way as to give
the minimum cost for the project in the set time.
235
www.AgriMoon.Com
System Engineering
5. Minimization of idle resources: The schedule should be devised to minimize large fluctuations
in the use of limited resources. The cost of having men/machines idle should be compared with
the cost of hiring resources on a temporary basis.
6. Network analysis can also be employed to minimize production delays, interruptions and
conflicts.
Managerial Applications :
Network analysis can be applied to very wide range of situations involving the use of time, labour and
physical resources. Some of the more common applications of network analysis in project scheduling
are as follows:
5. Maintenance and overhauling complicated equipment in chemical or power plants, steel and
petroleum industries, etc.
A network is a graphic representation of a project‘s operations and is composed of activities and events
(or nodes) that must be completed to reach the end objective of a project, showing the planning
sequence of their accomplishments, their dependence and inter relationships.
Basic Components
236
www.AgriMoon.Com
System Engineering
Events (node)
A specific point in time at which an activity begins and ends is called a node. It is recognizable as a
particular instant in time and does not consume time or resource. An event is generally represented on
the network by a circle, rectangle, hexagon or some other geometric shape.
Activity
An activity is a task, or item of work to be done, that consumes time, effort, money or other resources.
It lies between two events, called the ‗Preceding‘ and ‗Succeeding‘ ones. An activity is represented on
the network by an arrow with its head indicating the sequence in which the events are to occur.
Predecessor Activity:
An activity which must be completed before one or more other activities start is known as Predecessor
activity.
Successor Activity:
An activity which started immediately after one or more of other activities are completed is known as
Successor activity.
Dummy Activity:
Certain activities which neither consume time nor resources but are used simply to represent a
connection between events are known as dummies. A dummy activity is depicted by dotted line in the
network diagram.
A dummy activity in the network is added only to represent the given precedence relationships among
activities of the project and is needed when (a) two or more parallel activities in a project have same
head and tail events, or (b) two or more activities have some (but not all) of their immediate
predecessor activities in common.
237
www.AgriMoon.Com
System Engineering
There are three types of errors which are most common in network drawing, viz.,
(a) Formation of a loop: If an activity were represented as going back in time, a closed loop would
occur. This is show in fig which is simply the structure of Fig (b) with activity B reversed in direction.
Cycling in a network can result through a simple error or when while developing the activity plans,
one tries to show the repetition of an activity before beginning the next activity.
A closed loop would produce an endless cycle in computer programmes without a built-in routine for
detection or i4-entification of the cycle; Thus one property of a correctly constructed network diagram
is that it is "non-cyclic".
(a) Dangling: No activity should end without being joined to the end event. If it is not so, a dummy
activity is introduced in order to maintain the continuity of the system. Such end-events other than the
end of the project as a whole are called dangling events.
In the above network, activity D leads to dangling. A dummy activity is therefore introduced to avoid
this dangling.
238
www.AgriMoon.Com
System Engineering
(c) Redundancy: If a dummy activity is the only activity emanating from an event, it can be eliminated.
For example, in the network show in Fig the dummy activity is redundant and can be eliminated, and
the network redrawn.
1. Each activity is represented by one & only one arrow so that no single activity can be
represented twice in the network.
2. Time follows from left to right. Arrows pointing in opposite directions must be avoided.
5. Every node must have at least one activity preceding it and at least one activity following it,
except that the beginning node has no activities before it and the ending node has no activities
following it.
6. Only one activity may connect any two nodes. This rule is necessary so that an activity can be
specified by giving the numbers of its beginning and ending nodes.
After the network is drawn in a logical sequence, every event is assigned a number. The number
sequence must be such so as to reflect the flow of the network. In event numbering, the following rules
should be observed:
2. Event numbering should be carried out an a sequential basis from left to right.
3. The initial event which has all outgoing arrows with no incoming arrow is numbered 0 or 1.
4. The head of an arrow should always bear a number higher than the one assigned at the tail of
the arrow.
239
www.AgriMoon.Com
System Engineering
5. Gaps should be left in the sequence of event numbering to accommodate subsequent inclusion
of activities, if necessary.
Example:
A television is manufactured in six steps, labeled A through F. Because of its size and Complexity, the
television is produced one at a time. The production control manager thinks that network scheduling
techniques might be useful in planning future production. He recorded the following information:
C precedes D and E
F follows E
D is successor of F
(ii) On checking with the records, the production manager corrects his last note to read, ―D is a
predecessor of F‖. Draw a revised diagram of this network incorporating this new change.
Solution:
(a)
C precedes D and E
240
www.AgriMoon.Com
System Engineering
Now since B follows D and precedes E, the complete network diagram is shown below.
241
www.AgriMoon.Com
System Engineering
For each activity an estimate must be made of time that will be spent in the actual accomplishment of
that activity. Estimates may be expressed in hours, days, weeks or any other convenient unit of time.
The time estimate is usually written in the network immediately above the arrow. The next step after
making the time estimates is the calculation of earliest times and latest times for each mode. These
calculations are done in the following way.
a) Let zero be the starting time for the project. Then for each activity there is an earliest starting time
(ES) relative to the project starting time. The earliest finishing time is denoted by
Where Esj denotes the earliest start time of all the activities emanating from node i and t ij is the
estimated duration of the activity i-j.
Example:
In the above example the activity is from i-j, the duration of time is 5 hours. Here start time is ESj= max
{ESi + tij}
Initially the starting time will be 0 The finishing time for the i th event is 5.Staring time for the jth event is
5.
b) Let us suppose that we have a target time for completing the project. Then this time is called the
latest finish time (LF) for the final activity. The latest start time (LS) is the latest time at which an
activity can start if the target is to be maintained. It means that for the final activity, its LS is simply LF
– activity time.
Critical Path:
Certain activities in a network diagram of a project are called critical activities because delay in their
execution will cause further delay in the project completion time. Thus, all activities having zero total
float value are identified as critical activities.
242
www.AgriMoon.Com
System Engineering
The critical path is the continuous chain of critical activities in a network diagram. It is the longest path
starting from first to the last event and is shown by a thick line or double lines in a network.
The length of the critical path is the sum of the individual times of all the critical activities lying on it
and defines the minimum time required to complete the project.
(a) ES i = LFi
(b) ES j = LFj
Step 1: List all the jobs and then draw a network diagram. Each job is indicated by an arrow with the
direction of the arrow showing the sequence of jobs. The length of the arrows has no significance.
Place the jobs on the diagram one by one keeping in mind what precedes and follows each job as well
as what job can be done simultaneously.
Step 2: Consider the job‘s times to be deterministic. Indicate them above the arrow representing the
task.
Step 3: Calculate the earliest start time (EST) and earliest finish time (EFT) for each event and write
them in the box marked Calculate the latest start time (LST) and latest finish time (LFT)
Step 4: Tabulate various times, i.e., activity normal times, earliest times and latest times, and mark EST
and LFT on the arrow diagram.
Step 5: Determine the total float for each activity by taking differences between EST and LFT.
Step 6: Identify the critical activities and connect them with the beginning node and the ending node
in the network diagram by double line arrows. This gives the critical path.
The float (Slack) or free time is the length of time to which a non-critical activity and the time between
its ES & LF is longer than its actual duration or an event can be delayed or extended without delaying
the total project completion time.(ie) the difference between the latest finish and earliest start time.
243
www.AgriMoon.Com
System Engineering
a) Total float
b) Free float
c) Independent float
d) Interference float
a) Total float
Difference between the latest finish and earliest finish time for the activity
b) Free float
It is defined by assuming that all the activities start as early as possible. The free float for the activity
(i, j) is the excess available time over its duration.
c) Interference float
d) Independent float
The time by which an activity can be rescheduled without affecting the preceding or the succeeding
activities is known as independent float.
1. CPM was developed for conventional projects like construction project which consists of well
know routine tasks whose resource requirement and duration were known with certainty.
2. CPM is suited to establish a trade off for optimum balancing between schedule time and cost of
the project.
3. CPM is used for projects involving well know activities of repetitive in nature.
Problem
CPM
The following table gives the activities of a construction project and duration.
244
www.AgriMoon.Com
System Engineering
Duration
20 25 10 12 6 10
(days)
(iii) Find the total, free and independent floats each activity.
Solution:
The first step is to draw the network and fix early start and early finish schedule and then late
start-late finish schedule as in figure 1 and figure 2.
Fig.-2
245
www.AgriMoon.Com
System Engineering
1-2 0 0 0
1-3 5 5 5
2-3 0 0 0
2-4 4 4 4
3-4 0 0 0
4-5 0 0 0
To find the critical path, connect activities with ) total slack and we get 1-2-3-4-5 as the critical path.
1-2-4-5 = 42
1-2-3-4-5 = 46*
1-3-4-5 = 41
246
www.AgriMoon.Com
System Engineering
4.1 Introduction:
This technique, unlike CPM, takes into account the uncertainty of project durations into account.
Deterministic network methods assume that the expected time is the actual time taken. Probabilistic
methods, on the other hand, assume the reverse, more realistic situation, where activity times are
represented by a probability distribution. This probability distribution of activity time is based upon
three different time estimate made for each activity. There are as follows .
Optimistic (least) time estimate : (t0 or a) is the duration of any activity when everything goes on very
well during the project. i.e., laborers are available and come in time, machines are working properly,
money is available whenever needed, there is no scarcity of raw materials needed etc.
Pessimistic (greatest) time estimate: (tp or b) is the duration of any activity when almost every thing
goes against our will and a lot of difficulties is faced while doing a project.
Most likely time estimate: (tm or m) is the duration of any activity when sometimes things go on very
well, sometimes things go on very bad while doing the project.
2. Compute the expected duration of each activity te = \[{1 \over 6}\left[ {4{t_m} + {t_0} + {t_p}} \right]\]
3. Compute the expected variance σ \[^2={\left( {{{{t_p} - {t_0}} \over 6}} \right)^2}\] of each
activity.
4. Compute the earliest start, earliest finish, latest start, latest finish time for each activity.
6. Compute the expected variance of the Project length (also called the variance of the critical path)
σ2 which is the sum of the variances of all the critical activities.
7. Compute the expected standard deviation of the project length and calculate the standard
normal derivate \[{{\rm{Z}}_{\rm{0}}}={{{\rm{duedate}} - {\rm{expected date of completion}}}
\over {\sqrt {{\rm{project variance}}} }}\]
8. Using (7) one can estimate the probability of completing the project within a specified time,
using the normal curve (Area) tables.
247
www.AgriMoon.Com
System Engineering
PERT
1. PERT was developed in a brand new R and D Project it had to consider and deal with the
uncertainties associated with such projects. Thus the project duration is regarded as random
variable and therefore probabilities are calculated so as to characterize it.
2. Emphasis is given to important stages of completion of task rather than the activities required to
be performed to reach a particular event or task in the analysis of network. i.e., PERT network is
essentially an event- oriented network.
3. PERT is usually used for projects in which time estimates are uncertain. Example : R&D
activities which are usually non-repetitive.
4. PERT helps in identifying critical areas in a project so that suitable necessary adjustments may
be made to meet the scheduled completion date of the project.
1. CPM was developed for conventional projects like construction project which consists of well
know routine tasks whose resource requirement and duration were known with certainty.
2. CPM is suited to establish a trade off for optimum balancing between schedule time and cost of
the project.
3. CPM is used for projects involving well know activities of repetitive in nature.
Example:
PERT
The following table lists the jobs of a network with their time estimates.
Duration (days)
Job I-j
Optimistic Most Likely Pessimistic
1 2 3 6 15
1 6 2 5 14
2 3 6 12 30
248
www.AgriMoon.Com
System Engineering
2 4 2 5 8
3 5 5 11 17
4 5 3 6 15
6 7 3 9 27
5 8 1 4 7
7 8 4 19 28
(c) What the is approximate probability that the jobs on the critical path will be completed by the due
date of 42 days?
(d) What due date has about 90% chance of being met?
Solution:
Before proceeding to draw the project network, let us calculate the expected time of activity te, standard
deviation and variance of the expected time of activity using
1-2 7 2 4
1-6 6 2 4
2-3 14 4 16
249
www.AgriMoon.Com
System Engineering
2-4 5 1 1
3-5 11 2 4
4-5 7 2 4
6-7 11 4 16
5-8 4 1 1
7-8 18 4 16
1-2-3-5-8 = 36 days
1-2-4-5-8 = 23 days
1-6-7-8 = 35 days
Expected length of the critical path is 36 days. The variance for 1-2, 2-3, 3-5 and 5-8 are 4, 16,4 and 1
respectively and variance of the projection duration is 25 and hence
250
www.AgriMoon.Com
System Engineering
= 0.5000 + 0.3849
= 0.8849
= 88.49%
251
www.AgriMoon.Com
System Engineering
SOLVED PROBLEMS
Problem 1. Draw a network for the simple project of erection of steel works for a shed. The various
elements of project are as under:
Solution:
Problem 2. Construct the network diagram comprising activities B, C, .... Q and N such that the
following constraints are satisfied:
252
www.AgriMoon.Com
System Engineering
The notation X < Y means that the activity X must be finished before Y can begin.
Solution. The resulting network is shown in Fig. 27.6. The dummy activities D1, D2 and D3 are used to
establish the correct precedence relationships. D4 is used to identify the activities I and J with unique
end nodes. The nodes of the project are numbered such that their ascending order indicates the
direction of progress in the project:
Problem 3. Construct the arrow diagram comprising activities A, B, … and L such that the following
relationships are satisfied:
(i) A, B, and C, the first activities of the project, can start simultaneously,
(ii) A and B precede D, (iii) B precedes E, F and H, (iv) F and C precede G,
(v) E and H precede I and J, (vi) C, D, F and J precede K, (vii) K precedes L,
Solution. The resulting network is shown in Fig. 27.7 below. The dummy activities are used to identify
the activities A and B; E and H; C and F with a unique end node:
253
www.AgriMoon.Com
System Engineering
Problem 4. Draw a network for the following project and number the events according to Fulkerson's
rules:
(1) A is the start event and K is the end event. (2) J is the successor event to F.
(3) C and D are successor events to B. (4) D is the preceding event to G.
(5) E and F occur after event C. (6) E precedes J
Solution. The resulting network is shown in the figure given below. The dummy activity is used to
identify the activities E and F with unique end node:
The nodes of the network are numbered to indicate the direction of progress in the network
J. Inspection.
K. Trial run.
254
www.AgriMoon.Com
System Engineering
Assuming that the work is assigned to the boiler engineer who has one boiler mechanic and one
boiler attendant at his disposal, draw a network showing the precedence relationships.
Solution. Looking at the list of activities, we note that activity A (inspection of boiler) is to be followed
by dismantling of defective parts (D) and only after that it can be decided which parts can be repaired
and which will have to be replaced. Now the repairing and purchasing can go side by side. But the
instructions for repairs may be prepared after sending the letters for quotations. Note that it becomes a
partial constraint, also started after activity D. Now we assume that repairing will take less time than
purchasing. But the installation of repaired parts can be started only when the cleaning is completed.
This results in the use of a dummy activity. After the installation of repaired parts, installation of
purchased parts can be taken up. This will be followed by inspection and trial run.
The dummy activities are used to identify the activities C, H and E, G with unique end nodes.
Problem 6. A television is manufactured in six steps, labelled A through F. The television is produced
one at a time. The manager thinks that network scheduling will improve the position. It is noted that A
is the first step and A < B. A < C, C < D, C < E, B > D, B < E, F > E, D is a successor of F.
Solution, (a) Using given constraints, the activity node diagram (network) is shown in Fig. 27.70. The
dummy activities are introduced to establish the correct precedence relationships:
255
www.AgriMoon.Com
System Engineering
The nodes are numbered in such a way that their ascending order indicates the direction of progress in
the manufacturing process. Among the various activities involved, obviously we have the following
cycle: B→ E→ F→D→B.
c) To determine the minimum time of completion of the project, we compute ESi and LFj for each
activity of the project (TV set). The critical path calculations as applied to Fig. 27.11 are:
i = 2, 6
i = 6, 7
256
www.AgriMoon.Com
System Engineering
For determining the critical nodes, calculations are displayed in the following table:
(1. 2) 1 0 1 0 1 0
(2, 4) 0 1 1 4 4 3
(2,3) 2 I 3 I 3 0
(3,6) 1 3 4 3 4 0
(6, 4) 0 4 4 4 4 0
(4, 5) 3 4 7 4 7 0
(3, 5) 0 3 3 7 7 4
(5,7) 3 7 10 7 10 0
(7, 8) 0 10 10 10 10 0
(6, 8) 0 4 4 10 10 6
(8, 9) 2 10 12 10 12 0
257
www.AgriMoon.Com
System Engineering
It is apparent from the table that the critical nodes are for the activities (1, 2), (2, 3), (3, 6), (6, 4), (4,
5), {5, 7), (7, 8) and (8, 9).
The critical path, therefore, comprises the activities A, C, D, B, E and F, which is shown below
The minimum time required to complete the television set is 1+2+1+3+3+2 = 12 hours.
258
www.AgriMoon.Com
System Engineering
INTRODUCTION
In this chapter, we shall consider the question of resource requirements for different activities, the
availability of resources, their allocation to activities and some other problems. A feature common to all
these problems is that the limitations on resources needed for carrying out various activities of a project
can affect the scheduling of a project either because of their limited availability or by some other
restrictions. We assume that the resources required for each activity of a project and the resource
restrictions are known.
PROJECT COST
In order to include the cost aspects in project scheduling, we must first define the cost-duration
relationships for various activities in the project. The total project cost comprises direct and indirect
costs. The direct costs are associated with the individual activities such as manpower loading,
equipment utilized, materials consumed directly, etc., in respect of various activities. The indirect costs
are those expenditures which cannot be allocated to individual activities of the project. These may
include administration or supervision costs. loss of revenue, fixed overheads, depreciation, insurance,
and so on. While indirect cost allocated to a project goes up with the increase in project duration, direct
costs go high as the time for individual activity is reduced. Such deliberate reduction of activity times
by putting an extra effort is called crashing the activity.
It may be noted that for technical reasons, the duration of an activity cannot be reduced indefinitely.
The crash time represents the fully expedited or the minimum activity duration time that is possible,
and any attempts to further 'crash' would only raise the activity direct costs without reducing the time.
The activity cost corresponding to the crash time is called the crash cost which equals the minimum
direct cost required to achieve the crash performance time. These are in contrast to the normal time and
the normal cost of the activity. The normal cost is equal to the absolute minimum of the direct costs
required to perform an activity. The corresponding activity duration is known as the normal time.
259
www.AgriMoon.Com
System Engineering
The point A in denotes the normal time for completion of an activity whereas point B denotes the crash
time which indicates the least duration in which the particular activity can be completed. The cost
curve is non-linear and asymptotic but for the sake of simplicity it can be approximated by a straight
line with its slope given by
The cost slope represents the rate of increase in the cost of performing the activity per unit decrease in
time and is called cost/time trade off. It varies from activity to activity. Having assessed the direct and
indirect project cost the total costs can be found out. The total project cost is the sum total of the project
direct and indirect costs.
Shows both the direct and the indirect project cost. As these two curves have been plotted against the
same time scale, at each ordinate, the project direct and indirect costs can be added to obtain the
various points on the graph, indicating the total project cost corresponding to the various project
durations. If these total time-cost points are joined to form a curve, the curve so obtained will be total
project cost curve. If this curve is examined carefully, it may be seen that for different project durations,
there will be corresponding project costs. However, compared to all other points on this curve, there
will be one point which is at the lowest, indicating the least cost and the minimum time for the project.
It may again be observed that any point on the right hand side of this lowest point, the cost of the
project increases and project duration also increases. On the other hand, if the point~ on the left hand
side of the lowest point of this curve is considered, it may be seen that though there is reduction in
project duration time, the cost of the project, however, increases. So much so, any point either on the
right hand side or left hand side of the lowest point of this total projects. cost curve, it is not
advantageous to the project manager to choose any of the points for the implementation of the project
Obviously, it is the lowest point which indicates the lowest overall cost against the minimum time
required for the completion of the project. This point may therefore be called as the optimum time-cost
point of the curve which the project manager can choose for the implementation of the project
RESOURCE LEVELLING
In PERT and CPM techniques there is an implied assumption that required resources are always
available. When resources are limited, two alternative courses of action are available. In the first
alternative, the activities are critically sequenced and the minimum period of project is redetermined.
This process is called Resource Levelling. The problem here is to manipulate the activity slacks,
schedules and resource requirements throughout the duration of the project.
1. Levelling resource demands with constraint on the total project duration time.
2. Minimization of the project duration time with a constraint on the total availability of certain key
resources.
The first problem arises when resources are adequate but they are desired to be used at a relatively
constant rate during the life of the project. The second problem occurs when the resources cannot be
increased and the object is to minimize project duration with available resources.
260
www.AgriMoon.Com
System Engineering
Thus, resource levelling or load levelling is required when the demands on specified resources are
required not to exclude the specified level and the duration of the project is not invariant.
Remark. In order to stabilize the use of existing level of resources the total float of non-critical activities
is used. By shifting a non-critical activity between its earliest start time and latest allowable time,
project manager may be able to lower the maximum resource requirements. The following two general
rules are normally used in scheduling non-critical activities.
1. If the total float of a non-critical activity is equal to its free float, then it can he schedule any where
between its earliest start and latest completion times.
2. If the total float is a non-critical activity is more than its free float, then its starting time can be
delayed relative to its earliest start time by no more than the amount of its free float without affecting
the scheduling of its immediately succeeding activities.
261
www.AgriMoon.Com
System Engineering
ALGORITHM
The process of shortening a project is called crashing and is usually achieved by adding extra resources
to an activity. Project crashing involves following steps:
Step 1: Critical path. Find the normal critical path and identify the critical activities.
Step 2: Cost slope. Calculate the cost slope for the different activities by using the formula:
Step 3: Ranking. Rank the activities in the ascending order of cost slope.
Step 4: Crashing. Crash the activities in the critical path as per the ranking, i.e., activity having lower
cost slope would be crashed first to the maximum extent possible. Calculate the new direct cost by
cumulative adding the cost of crashing to the normal cost.
Step 5: Parallel crashing. As the critical path duration is reduced by the crashing in Step 3, other paths
also become critical, i.e., we get parallel critical paths. This means that project duration can be reduced
duly by simultaneous crashing of activities in the parallel critical paths.
Step 6: Optimal duration. Crashing as per step 3 and step 4, optimal project duration is determined. It
would be the time duration corresponding to which the total cost (i.e., direct cost plus indirect cost) is a
minimum.
SAMPLE PROBLEMS
The following table gives the activities in a construction project and other, relevant information:
262
www.AgriMoon.Com
System Engineering
(b) Find the total float and free float for each activity
(c) Using the above information crash the activity step by step until all paths are critical.
Solution: (a) using the normal time duration the network is given below:
(b) Considering the normal time of the project, the earliest times and latest times as well as the total
floats and free floats in respect of the node points is obtained in the following table:
(i-j) (days)
Start Finish Start Finish Total Free
1-2 20 0 20 0 20 0 0
1-3 25 0 25 5 30 5 5
2-3 10 20 30 20 30 0 0
2-4 12 20 32 23 35 3 3
263
www.AgriMoon.Com
System Engineering
3-4 5 30 35 30 35 0 0
4-5 10 35 45 35 45 0 0
4-6 5 35 40 42 47 7 7
5-7 10 45 55 45 55 0 0
6-7 8 40 48 47 55 7 7
1→2→3→4→5→7
and duration of the project is 55 days with total cost as Rs. 3600
(c)The cost slopes of the activities of the above network are computed as follows:
Crashing of Activities
Since the activities lying on the critical path control the project duration, we crash the activities lying on
the critical path.
264
www.AgriMoon.Com
System Engineering
First crashing. First of all we crash that activity of critical path which involves the minimum cost slope.
Since the activities (1, 2) and (3, 4) give the minimum cost slope, we compress the duration of activity
(3, 4) from 5 to 2 days with an additional cost Rs. 3 x 40, i.e., Rs. 120.
Second crashing. Now, Since there are two parallel critical paths, we choose the minimum cost slope of
the activity which lies on any of the two critical paths. As the minimum cost slope is for the activity (1,
2) we compress this activity from 20 to 17 days with an additional cost of Rs. 40 x 3 i.e. Rs. 120.
Third crashing. Minimum cost slope now is for the activities (4, 5), (5, 7), and (6, 7). Therefore crashing
the activities (4, 5) and (5, 7) by 5 days each and activity (6, 7) by 3 days at an extra cost of Rs. 60 per
day, we have
Fourth crashing. Finally, crashing the activities (2, 3) and (2, 4) by two days each, we find that all the
activities are lying on the critical path. Thus, we have
Since all the activities are now on critical paths, the process of crashing is completed.
265
www.AgriMoon.Com
System Engineering
Examples
The following table gives data on normal time, and cost and crash time and cost for a project.
Normal Crash
Activity
Time (Weeks) Cost (Rs) Time (Weeks) Cost (Rs)
2-3 3 30 3 30
4-5 0 0 0 0
(a) Draw the network and identify the critical path with double line.
(b) What are the normal project duration and associated cost?
266
www.AgriMoon.Com
System Engineering
(c) Find out the total float associated with each activity.
(d) Crash the relevant activities systematically and determine the optimal project completion time and
cost
Solution:
(a) The network for normal activity times indicates a project completion time of 32 weeks with the
critical path: 1 – 2 – 5 – 6 – 7 – 8, as shown in Fig. 24.
(b) Normal project duration is 32 weeks and the associated cost is as follows:
= 4,220 + 50 x 32 = Rs 5,820
(c) Calculations for total float associated with each activity are shown in Table 10
267
www.AgriMoon.Com
System Engineering
Table 10
Total Float
Activity
(Li – Ei) – tij
1-2 (3 – 0) – 3 = 0
2–3 (7 – 3) – 7 = 1
2–4 (12 – 3) – 7 = 2
2–5 (12 – 3) – 9 = 0
3–5 (12 – 6) – 5 = 1
(d) For Critical activities, crash cost-slope is given in Table 11. The minimum value of crash cost per
week is for activity 2-5 and 5-6. Hence, Crashing activity 2-5 by 2 days from 9 weeks to 7 weeks. But the
time should be reduced by 1 week only otherwise another path 1-2-3-5-6-7-8 becomes a paralled path.
Network as shown Fig. 25 is developed when it is observed that new project time is 31 weeks and the
critical paths are 1 – 2 – 5 – 6 – 7 – 8 and 1 – 2 – 3 – 5 – 6 – 7 – 8.
268
www.AgriMoon.Com
System Engineering
Table 11
With crashing of activity 2 – 5, the new total cost involved can be calculated as follows:
New total cost = Total direct normal + Increased direct cost due to crashing of activity
Now with respect to network given in Fig. 25, the new possibilities for crashing in the critical paths are
listed in Table 12.
269
www.AgriMoon.Com
System Engineering
Table 12
1–2 100
2–5 x (Crashed)
3–5 50
5–6 45
6–7 70
7–8 200
The minimum value of crashed cost slope is for activity 5 – 6. Hence, crashing it by 2 weeks from 6
weeks to 4 weeks. The new network diagram will now look like as show in Fig. 26
It may be noted in Fig.26, that both critical paths shown in Fig.25 remain unchanged because activity 5
– 6 is common between critical paths shown in Fig. 25. But with this crashing of activity 5 – 6 by 2
weeks, the new cost involved is:
270
www.AgriMoon.Com
System Engineering
New total cost = Total direct normal + Increased direct cost due to crashing of
With respect to network given in Fig 26, the new possibilities for crashing in the critical paths are listed
in Table 13.
Table 13
1–2 100
2–5 x (Crashed))
5–6 x (Crashed)
6–7 70
7–8 200
The further crashing of 6 – 7 activity time from 4 weeks to 3 weeks will result in increased direct cost
than the gain due to reduction in project time. Hence, here we must stop further crashing. The optimal
project duration is 29 weeks with associated cost of Rs 5,805 as shown in Table 14.
271
www.AgriMoon.Com
System Engineering
32 x 50 =
32 -- 4,220 -- 4,220 5,820
1,600
31 x 50 =
31 2 – 5(1) 4,220 1 x 45 = 45 4,265 5,815
1,550
45 + 2 x 45 = 29 x 50 =
29 5 – 6(2) 4,220 4,355 5,805
135 1,450
135 + 1 x 70 = 28 x 50 =
28 6 – 7(1) 4,220 4,425 5,825
205 1,400
272
www.AgriMoon.Com
****** ☺******
This Book Download From e-course of ICAR
Visit for Other Agriculture books, News,
Recruitment, Information, and Events at
www.agrimoon.com
Give FeedBack & Suggestion at [email protected]
The information on this website does not warrant or assume any legal
liability or responsibility for the accuracy, completeness or usefulness of the
courseware contents.
The contents are provided free for noncommercial purpose such as teaching,
training, research, extension and self learning.
******☺******
Connect With Us: