In mathematics, a deterministic system is a system in which no randomness is involved in the

development of future states of the system. Deterministic models thus produce the same output
for a given starting condition.A deterministic system is a conceptual model of the philosophical
doctrine of determinism applied to a system for understanding everything that has and will occur
in the system, based on the physical outcomes of causality. In a deterministic system, every
action, or cause, produces a reaction, or effect, and every reaction, in turn, becomes the cause of
subsequent reactions. The totality of these cascading events can theoretically show exactly how
the system will exist at any moment in time.

To understand this concept, start with a fairly small everyday system. Visualize a set of three
dominoes lined up in a row with each domino less than a domino's length away from its
neighbors, impervious to external environment influences. Once the first domino has toppled, the
third domino will topple because the second will topple upon being contacted by the first
domino. This could feasibly be shown by a scientist using a computer model front-loaded with
the ability to correctly apply physics.

A mathematical model uses mathematical language to describe a system. The process of

developing a mathematical model is termed mathematical modeling (also modeling).
Mathematical models are used not only in the natural sciences (such as physics, biology, earth
science, meteorology) and engineering disciplines, but also in the social sciences (such as
economics, psychology, sociology and political science); physicists, engineers, computer
scientists, and economists use mathematical models most extensively.

Classifying mathematical models

Many mathematical models can be classified in some of the following ways:

1. Linear vs. nonlinear: Mathematical models are usually composed by variables, which
are abstractions of quantities of interest in the described systems, and operators that act
on these variables, which can be algebraic operators, functions, differential operators, etc.
If all the operators in a mathematical model exhibit linearity, the resulting mathematical
model is defined as linear. A model is considered to be nonlinear otherwise. If one or
more of the objective functions or constraints are represented with a nonlinear equation,
then the model is known as a nonlinear model. Here, it was possible to say many things,
but since it is not our concern, let us skip to the next.
2. Deterministic vs. probabilistic (stochastic): A deterministic model is one in which
every set of variable states is uniquely determined by parameters in the model and by sets
of previous states of these variables. Therefore, deterministic models perform the same
way for a given set of initial conditions. Conversely, in a stochastic model, randomness is
present, and variable states are not described by unique values, but rather by probability

distributions.

1
 Deterministic Models

Definition

 There are various types of deterministic models in operation research like:-

 Linear programming
 Sensitivity analysis
 Transportation and assignment problems
 Integer linear programming and
 Goal programming but for a better convenience let us see only linear
programming.

Linear programming

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

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

Linear programs are problems that can be expressed in canonical form:

Maximize: cTx
Subject to: Ax ≤ b

where x represents the vector of variables (to be determined), c and b are vectors of (known)
coefficients and A is a (known) matrix of coefficients. The expression to be maximized or
minimized is called the objective function (cTx in this case). The equations Ax ≤ b are the
constraints which specify a convex polytope over which the objective function is to be
optimized. (In this context, two vectors are comparable when every entry in one is less-than or
equal-to the corresponding entry in the other. Otherwise, they are incomparable.)

2
  Linear programming can be applied to various fields of study. It is used most extensively
in business and economics, but can also be utilized for some engineering problems.
Industries that use linear programming models include transportation, energy,
telecommunications, and manufacturing. It has proved useful in modeling diverse types of
problems in planning, routing, scheduling, assignment, and design.

History of linear programming

The problem of solving a system of linear inequalities dates back at least as far as
Fourier, after whom the method of Fourier-Motzkin elimination is named. Linear programming
arose as a mathematical model developed during the second world war to plan expenditures and
returns in order to reduce costs to the army and increase losses to the enemy. It was kept secret
until 1947. Postwar, many industries found its use in their daily planning.

The founders of the subject are Leonid Kantorovich, a Russian mathematician who developed
linear programming problems in 1939, George B. Dantzig, who published the simplex method in
1947, and John von Neumann, who developed the theory of the duality in the same year. The
linear programming problem was first shown to be solvable in polynomial time by Leonid
Khachiyan in 1979, but a larger theoretical and practical breakthrough in the field came in 1984
when Narendra Karmarkar introduced a new interior point method for solving linear
programming problems.

Dantzig's original example of finding the best assignment of 70 people to 70 jobs exemplifies the
usefulness of linear programming. The computing power required to test all the permutations to
select the best assignment is vast; the number of possible configurations exceeds the number of
particles in the universe. However, it takes only a moment to find the optimum solution by
posing the problem as a linear program and applying the Simplex algorithm. The theory behind
linear programming drastically reduces the number of possible optimal solutions that must be
checked.

Uses

Linear programming is a considerable field of optimization for several reasons. Many practical
problems in operations research can be expressed as linear programming problems. Certain
special cases of linear programming, such as network flow problems and multicommodity flow
problems are considered important enough to have generated much research on specialized
algorithms for their solution. A number of algorithms for other types of optimization problems
work by solving LP problems as sub-problems. Historically, ideas from linear programming have
inspired many of the central concepts of optimization theory, such as duality, decomposition, and
the importance of convexity and its generalizations. Likewise, linear programming is heavily
used in microeconomics and company management, such as planning, production, transportation,
technology and other issues. Although the modern management issues are ever-changing, most
companies would like to maximize profits or minimize costs with limited resources. Therefore,
many issues can boil down to linear programming problems.
3
Standard form

Standard form is the usual and most intuitive form of describing a linear programming problem.
It consists of the following three parts:

 A linear function to be maximized

e.g., Maximize: c1x1 + c2x2

 Problem constraints of the following form

e.g.,
a1,1x1 + a1,2x2 ≤ b1
a2,1x1 + a2,2x2 ≤ b2
a3,1x1 + a3,2x2 ≤ b3
 Non-negative variables

e.g.,
x1 ≥ 0
x2 ≥ 0.

The problem is usually expressed in matrix form, and then becomes:

Maximize: cTx
Subject to: Ax ≤ b, x ≥ 0.

Other forms, such as minimization problems, problems with constraints on alternative forms, as
well as problems involving negative variables can always be rewritten into an equivalent
problem in standard form.

Example

Suppose that a farmer has a piece of farm land, say A square kilometres large, to be planted with
either wheat or barley or some combination of the two. The farmer has a limited permissible
amount F of fertilizer and P of insecticide which can be used, each of which is required in
different amounts per unit area for wheat (F1, P1) and barley (F2, P2). Let S1 be the selling price
of wheat, and S2 the price of barley. If we denote the area planted with wheat and barley by x1
and x2 respectively, then the optimal number of square kilometres to plant with wheat vs barley
can be expressed as a linear programming problem:

Maximize: S1x1 + S2x2 (maximize the revenue — revenue is the "objective function")

4
Subject to: x1 + x2 ≤ A (limit on total area)
F1x1 + F2x2 ≤ F (limit on fertilizer)
P1x1 + P2x2 ≤ P (limit on insecticide)
x1 ≥ 0, x2 ≥ 0 (Cannot plant a negative area).

Which in matrix form becomes?

Maximize

Subject to

Introducing slack variables (augmented form)

Example

The example above is converted into the following augmented form:

Maximize: S1x1 + S2x2 (objective function)

Subject to: x1 + x2 + x3 = A (augmented constraint)
F1x1 + F2x2 + x4 = F (augmented constraint)
P1x1 + P2x2 + x5 = P (augmented constraint)
X1, x2, x3, x4, x5 ≥ 0.

where x3, x4, x5 are (non-negative) slack variables, representing in this example the unused area,
the amount of unused fertilizer, and the amount of unused insecticide.

In matrix form this becomes:

Maximize Z:

5
Duality
Every linear programming problem, referred to as a primal problem, can be converted into a dual
problem, which provides an upper bound to the optimal value of the primal problem. In matrix
form, we can express the primal problem as:

Maximize cTx subject to Ax ≤ b, x ≥ 0;

with the corresponding symmetric dual problem,
Minimize bTy subject to ATy ≥ c, y ≥ 0.

An alternative primal formulation is:

Maximize cTx subject to Ax ≤ b;

with the corresponding asymmetric dual problem,
Minimize bTy subject to ATy = c, y ≥ 0.

There are two ideas fundamental to duality theory. One is the fact that (for the symmetric dual)
the dual of a dual linear program is the original primal linear program. Additionally, every
feasible solution for a linear program gives a bound on the optimal value of the objective
function of its dual. The weak duality theorem states that the objective function value of the dual
at any feasible solution is always greater than or equal to the objective function value of the
primal at any feasible solution. The strong duality theorem states that if the primal has an optimal
solution, x*, then the dual also has an optimal solution, y*, such that cTx*=bTy*.

A linear program can also be unbounded or infeasible. Duality theory tells us that if the primal is
unbounded then the dual is infeasible by the weak duality theorem. Likewise, if the dual is
unbounded, then the primal must be infeasible. However, it is possible for both the dual and the
primal to be infeasible

Existence of optimal solutions

Geometrically, the linear constraints define a convex polytope, which is called the feasible
region. A linear function is a convex function, which implies that every local minimum is a
global minimum; similarly, a linear function is a concave function, which implies that every
local maximum is a global maximum.

Optimal solution need not exist, for two reasons. First, if two constraints are inconsistent, then no
feasible solution exists: For instance, the constraints x ≥ 2 and x ≤ 1) cannot be satisfied jointly;
in this case, we say that the LP is infeasible. Second, when the polytope is unbounded in the
6
direction of the gradient of the objective function (where the gradient of the objective function is
the vector of the coeffients of the objective function), then no optimal value is attained.

Optimal vertices (and rays) of polyhedra

Otherwise, if a feasible solution exists and if the (linear) objective function is bounded, then the
optimum value is always attained on the boundary of optimal level-set, by the maximum
principle for convex functions (alternatively, by the minimum principle for concave functions):
Recall that linear functions are both convex and concave. However, some problems have distinct
optimal solutions: For example, the problem of finding a feasible solution to a system of linear
inequalities is a linear programming problem in which the objective function is the zero function
(that is, the the constant function taking the value zero everywhere): For this feasibility problem
with the zero-function for its objective-function, if there are two distinct solutions, then every
convex combination of the solutions is a solution.

The vertices of the polytope are also called basic feasible solutions. The reason for this choice of
name is as follows. Let d denote the number of variables. Then the fundamental theorem of
linear inequalities implies (for feasible problems) that for every vertex x* of the LP feasible
region, there exists a set of d (or fewer) inequality constraints from the LP such that, when we
treat those d constraints as equalities, the unique solution is x*. Thereby we can study these
vertices by means of looking at certain subsets of the set of all constraints (a discrete set), rather
than the continuum of LP solutions. This principle underlies the simplex algorithm for solving
linear programs.

Algorithms

A series of linear constraints on two variables produces a region of possible values for those
variables. Solvable problems will have a feasible region in the shape of a simple polygon.

7
Source: - Internet and text books

8
9