Miscellaneous:METHODS OF INTEGER PROGRAMMING SOLUTION

<< Miscellaneous:SEQUENCING, PROCESSING n JOBS THROUGH TWO MACHINES

Operations Research (MTH601)

273

METHODS OF INTEGER PROGRAMMING SOLUTION

The two methods employed to solve the integer programming problems are:

(i) Cutting Methods

(ii) Search Methods

Cutting methods, which are developed, for integer linear problem, start with continuous

optimum. Here the principle is systematically adding special constraints namely 'secondary

constraints' which provide the necessary conditions for integrality.

The continuous solution space is gradually changed until its continuous optimum extreme

point satisfies the integer conditions. The added secondary constraints effectively eliminate certain

parts of the solution space that do not contain feasible integer points. R.E. Gomory has developed the

cutting methods. They include the "fractional algorithm" which applies to the pure integer problem and

the "mixed algorithm" for mixed integer problem.

Search method is an enumeration technique in which all feasible integer points are

enumerated. The most prominent search method is the "branch and bound" technique. It also starts

with the continuous optimum, but systematically partitions the solution space into sub problems that

eliminate parts that contain no feasible integer points. A.H. Land A.G. Doig originally developed the

branch and bound algorithm. But R.J. Dakin's modification provides the computational case. The third

algorithm is due to E.Balas, which is known, as 'additive algorithm', which is applied to pure zero-one

problem.

GAME THEORY

Many conflicting situations are found in everyday life, in economic, social, political, military, battles,

advertising and marketing campaign by competing business firms. In these situations two or more individuals

have to take decisions that involve conflicting interests

A basic feature in many of these situations is that the final result depends primarily on the

combination of strategies selected by the persons involved, called adversaries. Game theory

handles such situations. Von Neumann, originally developed the Game Theory.

The following properties hold good for a competitive game.

There are finite number of competitors

Each of the competitors has a finite list of of possible courses of actions

known as strategy. The number of strategies need not be the same for each

competitor.

A play of the game results when each of the competitors chooses a single

course of action from the list of strategies available to him. The choices are

273

Operations Research (MTH601)

274

assumed to be made simultaneously so that no competitor knows his

opponent's choices until he is already committed to his own.

The outcome of a play depends on the strategies undertaken by the

competitors. Each outcome determines the set of payments to be made to each

competitor.

An objective of the game theory is to develop a rational criterion for selecting a strategy. This

is done under the assumption that both players are rational and each will uncompromisingly

attempt to do as well as possible, relative to his opponent. Game theory assumes that both

players are actively trying to improve their own welfare in opposition to that of opponent.

There are different types of games and they may be classified indifferent ways. Some of them are,

·Two-Person Zero-sum game

·Games with mixed strategies

·Games with Dominance, and so on.

SIMULATION

Simulation deals with the study of (dynamic) systems over time. There are three types of simulations

·Analogue

·Continuous

·Discrete

In analogue models, the physical (original) system is replaced by a model using analogy,

which is easier for manipulation.

Continuous models represent the system undergoing smooth changes in the characteristic

over a certain time period.

If the system is simulated with a model and observed it only at selected points in time, we

have discrete model. These time points coincide with the occurrence of certain events, which

play an important role to effect the changes in the performance of a system

Monte Carlo Simulation is the code name given by Von Neumann to the technique of solving

problems too expensive for experimental solutions and too complicated for analytical

treatment. If the model involves random sampling from a known probability distribution, the

procedure is called Monte Carlo Simulation.

274

Operations Research (MTH601)

275

MARKOV CHAIN

A Markov process is mathematical model that describes, in probabilistic terms, the dynamic

behavior of certain type of systems over time. A Markov chain is a type of Markov process.

A stochastic process is said to have the Markovian property that the conditional probability of

any future event, given any past event and the present state, is independent of the past event

and depends only on the present state of the process. This is called first-order Markov chain.

If the outcome depends on other than the prior results it is called a higher order chain. For

example a second order chain describes a process in which an outcome depends on the two

previous outcomes.

DECISION ANALYSIS

In recent years, statisticians, engineers, economists and students of management have placed

increasing emphasis on decision-making under conditions of uncertainty. Much of life, of

course, involves making choices under uncertainty, which is, choosing from some set of

alternative courses of action in situations where we are uncertain about the actual

consequences that will occur for each course of action being considered.

In today's fast-moving technological world, the need for sound, rational decision making by

business, industry and government is vividly apparent. Consider, for example, the area of

design and development of new improved products and equipment. Typically, development

from invention to commercialization is expensive and filled with uncertainty regarding both

technical and commercial success. In R&D, for example, decision makers might be faced

with the problem of choosing whether to pursue a parallel versus a sequential strategy ( i.e.

pursuing two or more designs simultaneously versus developing the most promising design,

and if it fails, going to next most promising design, etc). In production, they may have to

decide on a production method or process of manufacture; or choose whether to lease,

275

Operations Research (MTH601)

276

subcontract, or manufacture; or select a quality-control plan. In finance, they may have to

decide whether to invest in a new plant, equipment, research programs, marketing facilities,

and even risky orders. In marketing, they may have to determine the pricing scheme, whether

to do market research and what type and what type of it, the type of advertising campaign,

and so on.

Each of these decision problems is characteristically complex and can have a significant impact on

the health of a firm. It is almost impossible for any decision maker to intuitively take full account of all

the factors impinging on a decision simultaneously. It thus becomes useful to find some method of

separating such decision problems into parts in a way that would allow a decision maker to think

through the implications of each set of factors one at a time in a rational, consistent manner. Decision

analysis provides a rich set of concepts and techniques to aid the decision maker in dealing with

complex decision problems under uncertainty.

Decision-making can be broadly classified into three broad categories;

·Decision making under certainty

·Decision making under risk

·Decision making under uncertainty

Most of the decisions are made on the basis of some criterion. When there is certainty or the outcome

is sure, decision-making is simpler. When the outcome is not sure, then different criteria are used.

They are

For decision making under risk

·Expected value criterion

·Combined expected value and variance criterion

·Known aspiration level criterion

·Most likely occurrence criterion

For decision making under uncertainty

·Laplace criterion

·Minimax (Maximin) criterion

·Savage criterion

·Hurcwiz criterion

All the Operation Research Techniques discussed in this course are basically intended to help decision makers to take the

most optimal decision.

276

Operations Research (MTH601)

277

Best wishes for the decision

makers Good luck for the

students of this OR course:

MTH601

277

Table of Contents: