Minor Research Project for b.sc 6th semester

I, NAME Student of BSc. VI Semester 2024, hereby declare that the Minor Research Project entitled “PROJECT TITLE” “which is submitted to the Dr. Shyama Prasad Mukherjee Govt. Degree College, Bhadohi, Affiliated to Mahatma Gandhi Kashi Vidyapeeth University, Varanasi, is a record of an original work done by me under the guidance of Dr. Bhawna Singh and this Minor Research Project work is submitted in partial fulfillment of the requirement for the Degree of Bachelor of Science.”

1. 1



“ Linear programming and optimization techniques ”



A Minor Research Project submitted to Mahatma Gandhi Kashi Vidyapeeth
University, Varanasi in partial fulfilment of the requirement for the Degree of
Bachelor of Science







Submitted By:
VARSHA YADAV

Roll No: 30222870163
Enrollment No: KA2K22/302870163
Session: 2023-2024
Under The Supervision of
Dr. Bhawna Singh
Department of Mathematics
Dr. Syama Prasad Mukharjee Govt. Degree College, Bhadohi
221401

2. 2




DECLARATION



I, VARSHA YADAV Student of BSc. VI Semester 2024, hereby declare that
the Minor Research Project entitled “Linear programming and
optimization techniques” “which is submitted to the Dr. Shyama Prasad
Mukherjee Govt. Degree College, Bhadohi, Affiliated to Mahatma Gandhi Kashi
Vidyapeeth University, Varanasi, is a record of an original work done by me under the
guidance of Dr. Bhawna Singh and this Minor Research Project work is submitted in partial
fulfillment of the requirement for the Degree of Bachelor of Science.”









Place: Bhadohi
Date:………... Signature of the student
……………….
VARSHA YADAV

3. 1



CERTIFICATE




On the basis of declaration submitted by VARSHA YADAV , student B.Sc. VI Semester
2024, Mathematics, I hereby certify that the Minor research project entitled “Linear
programming and optimization technique s” submitted to the Dr.
Shyama Prasad Mukharjee Govt. Degree College, Bhadohi, Affiliated to Mahatma Gandhi
Kashi Vidyapeeth University, Varanasi, in partial fulfillment of the requirement for the
award of the degree of Bachelor of Science under my guidance and supervision.








Dr. Bhawna Singh
(Supervisor)
Assistant Professor, Maths
Dr. Shyama Prasad Mukharjee Govt.College
Bhadohi, 221401

4. 2




ACKNOWLEDGEMENTS


I would like to express my special thanks of gratitude to my teacher Dr. Bhawna Singh
as well as our principal Prof. (Dr) Shahid Parwez who gave me the golden opportunity to do this wonderful
project on the topic Linear programming and optimization techniques, which also helped me Like in
doing a lot of Research and i came to know about so many new things I am really thankful to them
Secondly i would also like to thank my parents and friends who helped me a lot in finalizing this project
within the limited time Frame .




VARSHA YADAV
B.Sc. VI Semester
Roll No: 30222870163
Dr. Bhawna Singh
Department of Mathematics
Dr. Syama Prasad Mukharjee Govt. Degree College, Bhadohi
221401

5. 3


CONTENTS
Name Page No.

 ABSTRACT 04

 KEY WORDS 04

 INTRODUCTION 05

 APPLICATION 08

 SOLUTION METHODS 12

 ADVANCED PROCEDURES 17

 CONCLUSION 26

 FUTURE PROPECTIVE 27

 REFERENCES 33

6. 4

ABSTRACT

Linear programming is a mathematical tool for optimizing an outcome through a
mathematical model. In recent times different mathematical models are extensively
used in the planning of different real-life applications such as agriculture,
management, business, industry, transportation, telecommunication, engineering,
and so on. It is mainly used to make the real-life situation easier, more comfortable,
and more economic, and to get optimum achievement from the limited resources.
This paper has tried to shed light on the basic information about linear programming
problems and some real-life applications. It presents the general introduction of the
linear programming problem, historical overview, meaning and definition of a linear
programming problem, assumptions of a linear programming problem, component of
a linear programming problem, and characteristics of a linear programming problem,
and some highlights of some real-life applications.

Key word

Some of the basic terminologies used in Linear Programming Problems are:
 Objective Function
 Constraints
 Feasible Solution
 Decision Variable
 Optimal Solution

 Objective function
The objective function must be linear, and it should be stated quantitatively.
 Constraints
These limitations are usually inequalities that define a region in the solution space where all
constraints are satisfied. This region is known as the feasible region.
 Variables
Decision variables represent things like production levels and transportation levels that are under the
control of the decision maker.
 Non-negativity
The value of the variable should be positive or zero, and not negative.
 Duality
Duality is used to solve linear programming problems when the initial solution is infeasible. It can
also be used to find the upper or lower bound of the objective function within its constraints.

7. 5

INTRODUCTION
 A is the queen of science. In our daily life, planning is required on various
occasion, especially when the resources are limited. Any planning is meant for
attaining certain objective. The best strategy is one that gives a maximum
output from a minimum input. The objective which is in the form of output
may be to get the maximum profit , minimum cost of production or
minimum inventory cost with a limited input of raw material, manpower and
machine capacity .such problems are referred to as the problems of
constrained optimization. Linear programming is a technique for
determining an optimum schedule of interdependent activities in view of the
available resources. Programming is just another word for ‘planning and
refers to the process of determining a particular plan of action from
amongst several alternative .
 Linear programming is a major innovation science world war in the field of
business decision making, particularly under condition of certainty . The
word ‘linear’ means the relationship handled are those represented by
straight lines, the relationship are of the form y=a+bx and the word
‘programming’ means taking decision systematically . Thus, Linear
programming is a decision making technique under given constraints on
the assumption that the relationship amongst the variables representing
different phenomenon happen to be Linear.
 Linear programming applies to optimization models in which objective
and constraints function are strictly Linear . The technique is used in a
wide range of application, including agriculture, industry, transportation,
economic, health system, behavioral and social science and the military . It
also boasts efficient computational algorithms for problems with
thousands of constraints and variables. Indeed, because of its
tremendous computational efficiency , linear programming from the
backbone of the solution algorithms for other operative research
models, including integer , stochastic and non -linear programming . The
graphical solution provides insight into the development of the general
algebraic simplex method . It also gives concrete ideas for the
development and interpretation of sensitivity analysis in linear
programming .
 A linear programming problems consist of three parts. First, there objective
function which is to be either maximized or minimized. Second there is a set
of linear constraints which contains three technical specifications of the
problems in relation to the given resources or requirements. Third, there
is a set of non-negativity constraints- since negative production has no
physical counterpart.

8. 6

 Linear programming is a mathematical concept that is used to find the
optimal solution of the linear function . This method uses simple
assumption for optimization the given function. Linear programming has
a huge real -world application and it is used to solve various types of
problems.
 The term “linear programming” consists of two words linear and
programming , the word linear tells the relation between various types
of variables of degree one used in a problem and the word programming
tells us the step by step procedure to solve these problems.
 Linear programming (LP) is a tool for solving optimization problems. I 1947,
George Danzig developed an efficient method, the simplex algorithm, for
solving linear programming problems (also called LP) . Since the
development of the simplex algorithm , LP has been used to solve
optimization problems in industries as diverse as banking, education,
forestry, petroleum, and trucking . In survey of fortune 500 firms 85%of the
responded said they had used linear programming as a measure of the
importance of linear programming in operation research approximately
70% of these book will be devoted to linear programming and related
optimization technique .
 We begin our study of linear programming by describing the general
characteristics shared by all linear programming problems . We learn how to
solve graphically those linear programming problems that involve only
two variables. Solving these simple LPs will give us full insight for solving
more complex LPs . The remainder of the chapter explains how to
formulate linear programming models of real -life situation.
 Linea programming is a sophisticated mathematical approach for
optimizing solution to a wide range of real -world situation. It entail
maximizing or minimizing a linear objective function while keeping linear
limitations in mind. Application span form industrial resources allocation to
logistical planning. The method employs graphical and algebraic
methodologies to select the best viable solution from a set of options,
offering useful insight for decision-making processes.
 It is an optimization method applicable for the solution of optimization
problem where objective function and the constraints are linear.
 It was first applied in 1930 by economist, mainly in solving resources
allocation problems during world war the us air force sought more
effective procedure for allocation of resources George B. Danzig, a
member of the us air force formulated general linear problems for solving
the resources allocation problem.

9. 7

 “A linear programming problem is one that is concerned with finding the
optimal value (maximum or minimum value) of a linear function (called
objective function ) of several variables (say x and y) , subject to the
condition that the variables are non-negative and satisfy a set of linear
inequalities ( called linear constraints). The term linear implies that all the
mathematical relation used in the problem are linear relation while the
term programming refers to the method of determining a particular
programmer or plan of action.
 The term operation research (OR) was first coined by MC Klosky and
treatment in 1940 in a small town Bowdre UK. The mine origin of OR was
during the second word war – The military commands of UK and USA
engaged several inter- disciplinary teams of scientists to undertake scientific
research in to strategic and tactical military operation. Their mission was to
formulate specific proposals and to arrive at the decision on optimal
utilization of scarce military resources and also to implement the decision
effectively. In simple words, it was to un cover the methods that can yield
greatest results with little efforts. Thus it had gained popularity and was
called “ An art of winning the war without actually fighting I” the name
Operation Research OR was invented because the team was dealing with
research on military. The encouraging result obtained by British OR team
motivated US military management to start with similar activities . The
work of OR team was given various names in US:
 Operational analysis, operation evaluation, operation research, system
analysis, system research, system allocation and so on. The first method in
this direction simplex method of linear programming developed in 1947
by G.B Danzig USA . Since then new techniques and application have been
developed to yield high profit from last costs.
 Now OR activities has become universally applicable to any area such as
transportation, hospital management, agriculture, libraries, city planning,
institution, construction management and so forth. In India many of the
industries like Delhi cloth mills, Indian Airlines, India Railway, etc are making
use of OR techniques

10. 8

2. Application. Linear programming (LP) is a branch or subset of mathematical
programming. LP is the quantitative analysis technique for deciding to achieve
the desired goal. It is a simple optimization technique. It is considered to be
the most important method of optimization in different fields.

 It is used to obtain the most optimal solution to the problem within some
constraints. It comprises of an objective function; linear inequalities subject to
some constraints may be in the form of linear equations or in the form of
inequalities. This method is used to maximize or minimize the objective
function of the given mathematical model comprising the set of linear
inequalities depending upon some constraints represented in the linear
relationship. LP is concerned with the maximization or minimization of a linear
objective function in many variables subject to linear equality and inequality
constraints
 . It deals with the optimization of linear functions subject to linear constraints.
Particularly, LP helps to allocate the resources efficiently to profit
maximization, loss minimization, or to utilize the production capacity to the
maximum extent
 LP always helps formulate the real-life problems into a fixed mathematical
model. Thus, it is also defined as a mathematical technique for solving
different real-life problems to determine the optimal solution or for
calculating the best value within the context or situation
 It is used to find the optimum utilization of the resources at the minimum
cost. In another words, it deals with the allocation of resources with some
restrictions such as costs and availability. It uses some assumptions while
determining the optimal value. The linear inequalities or restrictions known as
constraints of LP problems are always articulated in quantitative terms. The
objective function says the linear function Z = ax + by, where a, b are
constants and the constraints i.e. x ³ 0, y ³ 0 should always be linear and the
linear function is to be optimized. LP is extensively used in mathematics and
other different fields of social and physical sciences. For instance it is used to
make the decision on business planning, industrial engineering, economics,
telecommunication, energy, transportation and routing, fields of manufacture,
various types of scheduling, etc. It is the simplest and most extensively used
method of problem optimization [3]. In a real-life situation, the multi-sector
optimization problem usually occurs such as the planning of regional
development, development of water or electricity systems, urban planning,
and preservation of the natural environment
 This article mainly discusses on the historical overview, meaning, and
definition of the LP problem, some assumptions, major components,
characteristics of LP, and some real-life applications.

11. 9

 Historical Overview - The development of the solving LP problem does not
have so long history. It is considered to be a revolutionary development in the
sense of making optimal decisions in complex situations

 The firs start-up for solving optimization problems with simple equality
constraints was done by Lagrange in 1762 Similarly, Gauss solved linear
equations in 1820
 A French mathematician Jean-Baptiste Joseph Fourier (1768-1830) is known as
the first man to publish a book of method for solving systems of linear
inequalities in 1827
 This was the first attempt at the solution of an optimization problem. Similarly,
the Russian mathematician Leonid V. Kantorovich (1912-1986) gave linear
optimization formulations of resource allocation problems in 1939 that were
used in World War II to reduce the costs and increase the efficiency of the army
on the battlefield. In the meantime, the American economist Tjalling C.
Koopmans (1910-1985) also contributed to formulating the linear optimization
problem. Similarly, Frank Hitchcock formulated the transportation problem in
1941 and George Stigler formulated the diet problem in 1945 [9]. The real
practice of the optimization problem was implemented During World War II by
the U.S. Army to allocate the resources effectively in the leadership of George B.
Danzig in 1947

 As a result, both Kantorovich and Koopmans were awarded The Nobel Prize in
economic sciences for their work in 1975. Danzig also developed the linear
programming model for solving military logistics problems. After the
development of the digital computer in 1945, the American mathematician,
George Danzig developed the Simplex method for solving LP problems in 195
 For this achievement, George Danzig was awarded the National Medal of
Science by President Gerald Ford considered as the inventor of LP problems in
1976. The Simplex method was considered as a simplified form to solve the
linear programming problems. However, when more variables were attempted,
the number of necessary operations expanded exponentially and the
computation becomes more complicated. Thus, in 1979, Leonid Hachiman, the
Russian mathematician, discovered a polynomial-time algorithm called the
ellipsoid method. This process is considered slower than the Simplex method
when practically applied. Likewise, Narendra Carmaker, an Indian
mathematician discovered another polynomial-time algorithm in 1984 called
the interior point method

12. 10

 This method was proved as competitive with the Simplex method. In 1968,
Fiasco and McCormick introduced the Interior Point Method in 1968. Similarly,
in 1984, Carmaker applied the Interior Method to solve linear programming
problems

 Gradually, progress was made to a large extent in the theoretical development
and the practical applications of the LP problem. John von Neumann recognized
the significance of the concept of duality and later Kuhn and Tucker contributed
to the theoretical development of the duality theory that is considered as the
most important impact on the development of LP problems [9]. Similarly, the
works of Charnels and Cooper have also had a major impact on the industrial
applications of the LP problem. Similarly, as time passed, other several methods
for solving LP problems have been developed. At this time, the method
developed by Carmaker in 1984 was faster in comparison to the simplex
algorithm of Danzig
 Thus, the development of different techniques for calculating LP problems
helped to solve the decision-making process effectively and efficiently. On the
other hand, the actual techniques for solving LP problems have been
successfully applied in different sectors such as educational, industrial, and civil.
The development of computers also helps to make it possible to develop for
solving the LP problem, called the simplex algorithm at a faster rate. This also
helps to develop linear optimization problems rapidly in both theory and its
application. Nowadays, with the development of computer software, linear
optimization problems having several variables and constraints can be solved in
a few minutes. In the present time, linear optimization problems are almost
used in academic, industrial, and civil services for quantitative decision-making.

13. 11

 Meaning and Definition of Linear Programming Problem- Linear
programming is considered to be extremely significant tool due to its
application in modeling real-world problems and its use in mathematical
theory. Linear programming problem is the specified linear function that is
considered as an objective function that may contain several variables subject to
the conditions satisfying a set of linear inequalities known as linear constraints
and it is concerned with finding the optimal value of the given linear function. A
linear function or the objective function has the form: a0 + a1 x1 + a2 x2 + a3
x3 + . . . + an xn = 0, whereas, a's are called the coefficients or sometimes called
parameters of the equation and x's are called the variables of the equation. The
optimal value can either be a minimum or maximum. The LP problem is used to
find the best answer for a range of circumstances, together with manufacturing
issues, transportation issues, diet issues, allocation issues, etc. Different areas of
applied mathematics were developed in the late 1940s to solve the allocation
problems of the number of resources. An LP problem can be defined as the
problem of maximization or minimization of the linear function subject to the
linear constraints. The constraints may be equalities or inequalities. It is a
special and extremely important type of optimization problem due to its wide
applicability in different sectors
 The term 'linear programming' comprises of two words. The first word 'linear'
describes the relationship between multiple variables with degree one or
describes the linear relationship among variables in a specific model [11]. Such
a relationship always exists a proportional change to one another variable. This
means that the change of one variable always affects the other variable. The
second word 'programming' denotes the mathematical modeling to solve the
problem using limited resources to achieve the desired objectives

 Similarly, programming describes the process of getting the best solution from a
variety of alternatives. The term "programming" is also used as a synonym for
optimization
 Similarly, it is a mathematical technique useful for allocation of ‘scarce’ or
‘limited’ resources, to several competing activities on the basis of a given
criterion of optimality
 According to linear programming is a planning technique that permits some
objective functions to be minimized or maximized within the framework of given
situational restrictions. LP is a powerful technique of mathematical
programming extensively used in business planning, transportation, engineering
design, airline scheduling, and many other applications

14. 12

 According to linear programming can be defined as a mathematical technique
for solving management problems. While solving LP problems, at first the real-
life problems should be modeled in the form of a linear programming model
consisting of a certain number of resources into linear equations or inequalities
that permit us to appropriately identify and structure the constraints satisfied by
the variables of the model. Then, we can calculate the mathematical optimum
value using specific linear programming techniques.
3. Solution Methods
 Linear programming is a method of optimization that helps find optimal solutions
to problems by maximizing or minimizing them. Here are some methods for
solving linear programming problems.

A linear programming issue includes choice parameters, a nonlinear objective,
constraints, and nonnegative limitations. The outcome of the LP model is
determined by the choice variables x and y, which also reflect the ultimate answer.
 Z is the function that must be optimized (maximized or minimized) to arrive at
an answer. The constrictions are the limits placed on the variables to limit their
values. According to the non-negative limitations, the variables must always
possess a non-negative value.

15. 13

 The linear programming formula may be regarded as follows:
 The function of the formula: ax + by = Z
 The formula’s operating limitations: cx + dy ≤ e and fx + gy ≤ h
 Other, non-negative restrictions: x ≥ 0, y ≥ 0
 You need to know a few terms to understand the meaning of linear programming.
First come the decision variables. These elements fight for limited resources,
including products, services, etc. They are referred to as decision variables if they
are connected with a linear connection capable of determining the most optimal
option.
 The next component would be the objective function. The challenge must have
had a quantitatively measurable aim, such as maximizing profit, reducing costs,
etc. These constraints also apply to the available resources, such as limited
equipment, people, materials, etc. Some constraints are observably existent but
do not hamper the process of the studied issue; they are referred to as redundant
constraints.
 A viable solution is the collection of all potential solutions that fulfill the constants
in the format of variables. In addition, an optimum value is the best possible
solution that effectively supports the problem’s aim.
 The most crucial step in addressing a linear programming issue is formulating it
using the provided data. The following are the steps for solving linear
programming problems
Multiple Optimal Solutions

Example 1. A company purchasing scrap material has two types of scarp materials available.

16. 14

The first type has 30% of material X, 20% of material Y and 50% of material Z by weight. The
second type has 40% of material X, 10% of material Y and 30% of material Z. The costs of the
two scraps are Rs.120 and Rs.160 per kg respectively. The company requires at least 240 kg of
material X, 100 kg of material Y and 290 kg of material Z. Find the optimum quantities of the
two scraps to be purchased so that the company requirements of the three materials are
satisfied at a minimum cost.
Solution. First we have to formulate the linear programming model. Let us introduce the
decision variables x1 and x2 denoting the amount of scrap material to be purchased. Here the
objective is to minimize the purchasing cost. So, the objective function here is
Minimize
120x1 + 160x2
Subject to:
0.3x1 + 0.4x2 ≥ 240
0.2x1 + 0.1x2 ≥ 100
0.5x1 + 0.3x2 ≥ 290
x1 ≥ 0; x2 ≥ 0
Multiply by 10 both sides of the inequalities, then the problem becomes
Minimize
120x1 + 160x2
Subject to:
3x1 + 4x2 ≥ 2400
2x1 + x2 ≥ 1000
5x1 + 3x2 ≥ 2900

17. 15

x1 ≥ 0; x2 ≥ 0


Let us introduce parameter M in the objective function i.e. 120x1 + 160x2 = M. Then we have
to determine the different values for M, which is shown in the following Table

Shows the calculation of Minimum objective function value
Note that there are two minimum value for the objective function (M=96000). The feasible
region and the multiple solutions are indicated in the following Graph

18. 16

Graphical Method

Example 2. Solve linear equations x+y=2 and 2x+3y=4 using Graphical Method

19. 17



4. Advanced Procedures
The model formulation is crucial in decision-making because it captures the core of
the business choice problem. The process of transforming verbal descriptions and
numerical data into mathematical formulations that accurately reflect the relationships
between decision-making elements, objectives, and resource-use constraints is known
as formulation. Linear programming (L.P.) is a specific kind of technique used for
economically allocating "scarce" or "limited" resources, like labour, material, machine,
time, warehouse space, capital, energy, etc., to several competing activities, like goods,
services, jobs, new equipment, projects, etc. based on a given optimality criterion.
Resources that are limited in availability throughout the planning stage are referred to
as scarce resources.
The decision-maker must know all these assumptions and attributes before using
linear programming to solve a real-world choice issue. "linear" refers to a model's
variables' linear relationships. As a result, every change in one variable will always result
in a proportionate change in the other. For instance, double the investment in a certain

20. 18

project will be twice the return rate. Programming is the mathematical modelling and
solution of problems involving the economic allocation of scarce resources by
selecting a particular course of action or strategy from a range of possible options to
reach the desired goal.
In a decision-making embroilment, model formulation is important because it represents the
essence of business decision problem. The term formulation is used to mean the process of
converting the verbal description and numerical data into mathematical expressions which
represents the relevant relationship among decision factors, objectives and restrictions on the
use of resources. Linear Programming (LP) is a particular type of technique used for economic
allocation of ‘scarce’ or ‘limited’ resources, such as labor, material, machine, time, warehouse
space, capital, energy, etc. to several competing activities, such as products, services, jobs, new
equipment, projects, etc. on the basis of a given criterion of optimally. The phrase scarce
resources mean resources that are not in unlimited in availability during the planning period.
The criterion of optimality generally is either performance, return on investment, profit, cost,
utility, time, distance, etc..
The word linear refers to linear relationship among variables in a model. Thus, a given change
in one variable will always cause a resulting proportional change in another variable. For
example, doubling the investment on a certain project will exactly double the rate of the return.
The word programming refers to modelling and solving a problem mathematically that
involves the economic allocation of limited resources by choosing a particular course of action
or strategy among various alternative strategies to achieve the desired objective.
5. ASSUMPTIONS OF LINEAR PROGRAMMING PROBLEM
Assumptions are the acceptance without any proof or acceptance without proof.
In the LP problem, some assumptions are made to model the complex real-
world problem into a simple form that can be solved or analyzed more freely.
According to the major assumptions of the LP problem are stated as

A. Certainty The assumption of LP, certainty denotes the availability of all the
parameters such as the parameters of objective function coefficients and the
coefficients of constraint inequalities. In other words, the availability of all
parameters for instance: availability of resources, contribution per unit of
decision variable, and consumption of resources per unit of decision variable
must be known and must be constant.
B. Additivity is the value of the objective function and the total amount of each
resource used or supplied, must be equal to the sum of the respective
individual contribution (profit or cost) of the decision variables. In another
word, the sum of all activities quails the sum of each individual activity.
C. . Linearity or Proportionality It is the amount of each resource used and its
role to the profit or cost in objective function must be proportional to
the value of each decision variable. In other words, any change in the

21. 19

constraint inequalities also makes the proportional change in the objective
function is the proportionality or linearity.
D. . Divisibility or continuity The assumption divisibility or continuity denotes the
state of continuous decision variables. It means a combination of outputs can
be used with the fractional values along with the integer values. It means that
the solution needs to be in whole numbers (integers). Instead, they are
divisible and may take any fractional value, if the product cannot be produced
in fraction, and integer programming problem exists.


6. Types of variables


A variable is a characteristic that can be measured and that can assume different values.
Height, age, income, province or country of birth, grades obtained at school and type of
housing are all examples of variables. Variables may be classified into two main
categories: categorical and numeric. Each category is then classified in two subcategories:
nominal or ordinal for categorical variables, discrete or continuous for numeric variables.
These types are briefly outlined in this section.
 Categorical variables
A categorical variable (also called qualitative variable) refers to a characteristic that can’t
be quantifiable. Categorical variables can be either nominal or ordinal.
 Nominal variable
A nominal variable is one that describes a name, label or category without natural order. Sex
and type of dwelling are examples of nominal variables. In Table 4.2.1, the variable “mode of
transportation for travel to work” is also nominal.

22. 20


It is important to note that even if categorical variables are not quantifiable, they can
appear as numbers in a data set. Correspondence between these numbers and the
categories is established during data coding. To be able to identify the type of
variable, it is important to have access to the metadata (the data about the data)
that should include the code set used for each categorical variable. For instance,
categories used in Table 4.2.2 could appear as a number from 1 to 5: 1 for “very bad,”
2 for “bad,” 3 for “good,” 4 for “very good” and 5 for “excellent.

 Numeric variables
A numeric variable (also called quantitative variable) is a quantifiable characteristic
whose values are numbers (except numbers which are codes standing up for
categories). Numeric variables may be either continuous or discrete.
 Continuous variables
A variable is said to be continuous if it can assume an infinite number of real values
within a given interval. For instance, consider the height of a student. The height
can’t take any values. It can’t be negative and it can’t be higher than three meters.
But between 0 and 3, the number of possible values is theoretically infinite. A student
may be 1.6321748755 … meters tall. In practice, the methods used and the accuracy
of the measurement instrument will restrict the precision of the variable. The
reported height would be rounded to the nearest centimeter, so it would be
1.63 meters. The age is another example of a continuous variable that is typically
rounded down.
 Discrete variables
As opposed to a continuous variable, a discrete variable can assume only a finite
number of real values within a given interval. An example of a discrete variable would
be the score given by a judge to a gymnast in competition: the range is 0 to 10 and
the score is always given to one decimal (e.g. a score of 8.5). You can enumerate all
possible values (0, 0.1, 0.2…) and see that the number of possible values is finite: it is

23. 21

101! Another example of a discrete variable is the number of people in a household
for a household of size 20 or less. The number of possible values is 20, because it’s
not possible for a household to include a number of people that would be a fraction
of an integer like 2.27 for instance.

7.Artificial Variable Technique
When George Danzig originally put forward the simplex method, it was limited only to
LP problems having a known feasible solution, commonly called the initial basic
feasible solution. When the traditional simplex method is applied to larger LP
problems, the number of variables and number of iterations is increased
considerably and with this, also the complexity.
Because simplex method is possibly the best and most universally applied pivot
algorithm for solving LP problems, it became important to develop more general
methods to solve LP problems, where an arbitrary initial basic solution (which was
not necessarily a feasible solution) may be used to begin the pivoting process.
Danzig (1955) and Wagner (1956) highlighted that for LPs without an initial basic
feasible solution, almost all the current variants of the simplex method are applicable
in two phases. In Phase I, a basic feasible solution is generated by adding variables
known as artificial variables to the problem with a specially constructed auxiliary
objective, aiming to minimize the sum of all the artificial variables while maintaining
feasibility.
When all the artificial variables reach a value of zero, it means all the infeasibilities have
been eliminated and we can continue with the normal simplex method in Phase II. If
not, the problem does not have a feasible solution. Artificial variables are also used
in another simplex method that predates the two-phase method and is known as
the Big M method.
The Big M method allows the simplex algorithm to be applied to problems that contain
a greater-than type of constraints by introducing a large negative constant M which
would not be part of the final optimal solution if there is any.
In this article, readers will gain an insight into artificial variables and the two methods
that use them to extend the simplex method to solve LP problems.
the previou article you studied problems where slack and surplus variables readily provided
an initial basic feasible solution. You assign zero cost to these variables in the objective
function. A problem may arise when slack variables do not provide an initial basic feasible
solution and it becomes difficult to start and proceed with the initial simplex tableau. This
happens when the slack variables have negative values. For example, let us consider a
constraint:
x + 3y ≥ 175

To replace this inequality with an equation, you need to subtract a slack variable so
that you have:
x + 3y – S = 175
Now, if x and y are non-basic variables in the problem, then S is taken as the starting
basic variable. But this means that the value of S = –175 which is infeasible. You

24. 22

cannot continue any more iterations of the simplex method with an infeasible basic
solution. To generate an initial solution, you need to use the artificial variable
technique so that you can proceed with the simplex method until the optimal
solution is reached.
Artificial variables are added to constraints with greater than or equal to sign to
generate an initial solution to an LP problem. In a physical sense, artificial variables
have no meaning, they are purely a means for getting an initial solution to an LP
problem and are eliminated later.

In some LP problems, the slack variables cannot give the initial basic feasible solution.
In these types of LP problems, a minimum of one constraint is of ≥ type. Since a
basis matrix cannot be obtained as an identity matrix in the initial simplex tableau,
you use a new type of variable called the artificial variable to generate the initial
basic solution.
You can extend the simplex method to solve such LP problems with artificial variables
using either of the two methods:
If in the basis, no vector corresponding to the artificial variable appears and the
optimality conditions are met, the current solution is said to be the optimal basic
feasible solution.
If there is at least one vector corresponding to the artificial variable at zero level in the
basis and the conditions of optimality are met, then the current basic solution is the
optimal albeit degenerate solution.
If there is at least one vector corresponding to the artificial variable at a positive level
in the basis and the conditions of optimality are met, then there is no feasible
solution to the original problem. The penalty, in this case, is very large, while the
solution satisfies the constraints it does not optimize the objective function.
A slack variable is added to less than or equal to type of constraints to convert them
to equalities. A surplus variable is added to greater than or equal to type of
constraints to convert them to equalities.
For a binding constraint, the corresponding slack or surplus value will equal zero.
Artificial variable is introduced in the LP model to obtain the initial basic feasible
solution. It is used for the equality constraints and for the greater than or equal to
type of inequality constraints.
Let us now see where the variables are inserted in the Big M method:
In Step 1 of the Big M method, the constraints of the given LP problem are expressed
in the equation form by including slack variables for constraint of the type ≤ or
surplus variables for constraint of the type ≥.
Now, the basic solution for the problem, an infeasible one can be determined as the
basic variable is negative for constraints of the type ≥.
In Step 2 of the Big M method, non-negative artificial variables are added to the left-
hand side of each of the equations corresponding to the constraints of the types >
and = to generate a starting basic feasible solution

25. 23

The two-phase method is so named because the LP problem is solved in two phases.
Simplex method is applied to a specially constructed auxiliary LP problem in Phase
I, and the problem is solved by applying the simplex method which helps in
generating a basic feasible solution to the original problem.
The process of elimination of artificial variables is performed in Phase I of the solution
and Phase II is used to obtain an optimal solution using a simplex.
In Phase I, the artificial variables are introduced for making the vary- bales of the
original problem non-basic and set them to zero even though this might be
infeasible to the original problem. The resulting infeasibilities are taken on by the
artificial variables and they are basic at the beginning of Phase

The optimum basic feasible solution of phase I is used as the initial basic feasible
solution for the original LP problem. Assign actual coefficients to the variables in the
objective function and zero value to the artificial variables that show zero value in
the final simplex tableau of Phase I. Use the normal simplex algorithm on the
modified simplex tableau to obtain the optimum solution of the original problem.

The drawback to Big M method is related to how we choose the penalty M. If M is too
small, the final solution to the original problem may not even be feasible, let alone
optimal, since the penalty for infeasibility was not big enough.
On the other hand, if M is very large, the original problem can have numerical issues
and the final solution may not be optimal. Sometimes, no M value exists that can
prevent both these issues. Another limitation of the big M method over the two-
phase method is that in the former, feasibility is not known until optimality is
reached.

Big M Method Example: LPP
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
Maximize x1 + 5x2 + 0x3 + 0x4 – MA1

26. 24

27. 25

28. 26

8.Conclusion

Following completion of this free Open Learn course, Linear programming – the basic
ideas, you should find that your skills in finding a solution to a linear programming
problem and interpreting the result in terms of the original problem are improving.
You should now be able to:
Formulate a given simplified description of a suitable real-world problem as a linear
programming model in general, standard and canonical forms
Sketch a graphical representation of a two-dimensional linear programming model
given in general, standard or canonical form
classify a two-dimensional linear programming model by the type of its solution
solve a two-dimensional linear programming problem graphically
use the simplex method to solve small linear programming models by hand, given a
basic feasible point.

29. 27

Future Propective

While significant progress has been made in global optimization, there are clearly
still a number of major challenges that need to be addressed. First, existing methods
for global optimization of NLP and MINLP can still be computationally very expensive
to solve. Special reformulation strategies such as the ones that are outlined in Smith
and Pantelides (1999) in order to handle algebraic models in terms of basic
functional forms (bilinear, fractional, concave separable), need to be studied further
and implanted effectively. Also, computational strategies that are for instance
implemented in BARON (Sahinidis, 1996) or in alphaBB (Adjiman et al. 1996) need
to be further developed and investigated, as well as implemented in modern parallel
machines (see section IV). Second, the extension of global optimization to problems
of optimization under uncertainty (Ierapetritou et al., 1996; Floudas et al., 2001), or
to dynamic and mixed-integer dynamic problems (Singer and Barton, 2002), will
clearly require either radically new ideas, or a quantum improvement in
computational capabilities. On the other hand, it is important to recognize that
current capabilities for global optimization are already quite impressive, so there is
reason for optimism in the future of this area.

Linear programming is used in business and industry in production planning,
transportation and routing, and various types of scheduling. Airlines use linear
programs to schedule their flights, taking into account both scheduling aircraft and
scheduling staff. Delivery services use linear programs to schedule and route
shipments to minimize shipment time or minimize cost. Retailers use linear programs
to determine how to order products from manufacturers and organize deliveries with
their stores. Manufacturing companies use linear programming to plan and schedule
production. Financial institutions use linear programming to determine the mix of
financial products they offer, or to schedule payments transferring funds between
institutions. Health care institutions use linear programming to ensure the proper
supplies are available when needed. And as we’ll see below, linear programming has
also been used to organize and coordinate life saving health care procedures.
In some of the applications, the techniques used are related to linear programming
but are more sophisticated than the methods we study in this class. One such
technique is called integer programming. In these situations, answers must be
integers to make sense, and can not be fractions. Problems where solutions must be
integers are more difficult to solve than the linear programs we’ve worked with. In
fact, many of our problems have been very carefully constructed for learning
purposes so that the answers just happen to turn out to be integers, but in the real
world unless we specify that as a restriction, there is no guarantee that a linear
program will produce integer solutions. There are also related techniques that are
called non-linear programs, where the functions defining the objective function
and/or some or all of the constraints may be non-linear rather than straight lines.
Many large businesses that use linear programming and related methods have
analysts on their staff who can perform the analyses needed, including linear
programming and other mathematical techniques. Consulting firms specializing in

30. 28

use of such techniques also aid businesses who need to apply these methods to
their planning and scheduling processes.
When used in business, many different terms may be used to describe the use of
techniques such as linear programming as part of mathematical business models.
Optimization, operations research, business analytics, data science, industrial
engineering hand management science are among the terms used to describe
mathematical modelling techniques that may include linear programming and related
met
In the rest of this section we’ll explore six real world applications, and investigate
what they are trying to accomplish using optimization, as well as what their
constraints might represent.
Airline Scheduling
Airlines use techniques that include and are related to linear programming to
schedule their aircrafts to flights on various routes, and to schedule crews to the
flights. In addition, airlines also use linear programming to determine ticket pricing
for various types of seats and levels of service or amenities, as well as the timing at
which ticket prices change.
The process of scheduling aircraft and departure times on flight routes can be
expressed as a model that minimizes cost, of which the largest component is
generally fuel costs.
Constraints involve considerations such as:
 Each aircraft needs to complete a daily or weekly tour to return back to its
point of origin.
 Scheduling sufficient flights to meet demand on each route.
 Scheduling the right type and size of aircraft on each route to be appropriate
for the route and for the demand for number of passengers.
 Aircraft must be compatible with the airports it departs from and arrives at -
not all airports can handle all types of planes.
A model to accomplish this could contain thousands of variables and constraints.
Highly trained analysts determine ways to translate all the constraints into
mathematical inequalities or equations to put into the model.
After aircraft are scheduled, crews need to be assigned to flights. Each flight needs a
pilot, a co-pilot, and flight attendants. Each crew member needs to complete a daily
or weekly tour to return back to his or her home base. Additional constraints on
flight crew assignments take into account factors such as:
 Pilot and co-pilot qualifications to fly the particular type of aircraft they are
assigned to

31. 29

 Flight crew have restrictions on the maximum amount of flying time per day
and the length of mandatory rest periods between flights or per day that
must meet certain minimum rest time regulations.
 Numbers of crew members required for a particular type or size of aircraft.
When scheduling crews to flights, the objective function would seek to minimize
total flight crew costs, determined by the number of people on the crew and pay
rates of the crew members. However the cost for any particular route might not end
up being the lowest possible for that route, depending on tradeoffs to the total cost
of shifting different crews to different routes.
An airline can also use linear programming to revise schedules on short notice on an
emergency basis when there is a schedule disruption, such as due to weather. In
this case the considerations to be managed involve:
 Getting aircrafts and crews back on schedule as quickly as possible
 Moving aircraft from storm areas to areas with calm weather to keep the
aircraft safe from damage and ready to come back into service as quickly and
conveniently as possible
 Ensuring crews are available to operate the aircraft and that crews continue
to meet mandatory rest period requirements and regulations.
Kidney Donation Chain
For patients who have kidney disease, a transplant of a healthy kidney from a living
donor can often be a lifesaving procedure. Criteria for a kidney donation procedure
include the availability of a donor who is healthy enough to donate a kidney, as well
as a compatible match between the patient and donor for blood type and several
other characteristics. Ideally, if a patient needs a kidney donation, a close relative
may be a match and can be the kidney donor. However often there is not a relative
who is a close enough match to be the donor. Considering donations from unrelated
donor allows for a larger pool of potential donors. Kidney donations involving
unrelated donors can sometimes be arranged through a chain of donations that pair
patients with donors. For example a kidney donation chain with three donors might
operate as follows:
 Donor A donates a kidney to Patient B.
 Donor B, who is related to Patient B, donates a kidney to Patient C.
 Donor C, who is related to Patient C, donates a kidney to Patient A, who is
related to Donor A.
Linear programming is one of several mathematical tools that have been used to
help efficiently identify a kidney donation chain. In this type of model, patient/donor
pairs are assigned compatibility scores based on characteristics of patients and
potential donors.

32. 30

The objective is to maximize the total compatibility scores. Constraints ensure that
donors and patients are paired only if compatibility scores are sufficiently high to
indicate an acceptable match.
Advertisements in Online Marketing
Did you ever make a purchase online and then notice that as you browse websites,
search, or use social media, you now see more ads related the item you purchased?
Marketing organizations use a variety of mathematical techniques, including linear
programming, to determine individualized advertising placement purchases.
Instead of advertising randomly, online advertisers want to sell bundles of
advertisements related to a particular product to batches of users who are more
likely to purchase that product. Based on an individual’s previous browsing and
purchase selections, he or she is assigned a “propensity score” for making a
purchase if shown an ad for a certain product. The company placing the ad generally
does not know individual personal information based on the history of items viewed
and purchased, but instead has aggregated information for groups of individuals
based on what they view or purchase. However, the company may know more about
an individual’s history if he or she logged into a website making that information
identifiable, within the privacy provisions and terms of use of the site.
The company’s goal is to buy ads to present to specified size batches of people who
are browsing. The linear program would assign ads and batches of people to view
the ads using an objective function that seeks to maximize advertising response
modelled using the propensity scores. The constraints are to stay within the
restrictions of the advertising budget.
Loans
A car manufacturer sells its cars though dealers. Dealers can offer loan financing to
customers who need to take out loans to purchase a car. Here we will consider how
car manufacturers can use linear programming to determine the specific
characteristics of the loan they offer to a customer who purchases a car. In a future
chapter we will learn how to do the financial calculations related to loans.
A customer who applies for a car loan fills out an application. This provides the car
dealer with information about that customer. In addition, the car dealer can access a
credit bureau to obtain information about a customer’s credit score.
Based on this information obtained about the customer, the car dealer offers a loan
with certain characteristics, such as interest rate, loan amount, and length of loan
repayment period.
Linear programming can be used as part of the process to determine the
characteristics of the loan offer. The linear program seeks to maximize the
profitability of its portfolio of loans. The constraints limit the risk that the customer

33. 31

will default and will not repay the loan. The constraints also seek to minimize the
risk of losing the loan customer if the conditions of the loan are not favorable
enough; otherwise the customer may find another lender, such as a bank, which can
offer a more favorable loan.
Production Planning and Scheduling in Manufacturing
Consider the example of a company that produces yogurt. There are different
varieties of yogurt products in a variety of flavors. Yogurt products have a short
shelf life; it must be produced on a timely basis to meet demand, rather than
drawing upon a stockpile of inventory as can be done with a product that is not
perishable. Most ingredients in yogurt also have a short shelf life, so can not be
ordered and stored for long periods of time before use; ingredients must be
obtained in a timely manner to be available when needed but still be fresh. Linear
programming can be used in both production planning and scheduling.
To start the process, sales forecasts are developed to determine demand to know
how much of each type of product to make.
There are often various manufacturing plants at which the products may be
produced. The appropriate ingredients need to be at the production facility to
produce the products assigned to that facility. Transportation costs must be
considered, both for obtaining and delivering ingredients to the correct facilities, and
for transport of finished product to the sellers.
The linear program that monitors production planning and scheduling must be
updated frequently - daily or even twice each day - to take into account variations
from a master plan.
Bike Share Programs
Over 600 cities worldwide have bikeshare programs. Although bikeshare programs
have been around for a long time, they have proliferated in the past decade as
technology has developed new methods for tracking the bicycles.
Bikeshare programs vary in the details of how they work, but most typically people
pay a fee to join and then can borrow a bicycle from a bike share station and return
the bike to the same or a different bike share station. Over time the bikes tend to
migrate; there may be more people who want to pick up a bike at station A and
return it at station B than there are people who want to do the opposite. In chapter
9, we’ll investigate a technique that can be used to predict the distribution of bikes
among the stations.
Once other methods are used to predict the actual and desired distributions of bikes
among the stations, bikes may need to be transported between stations to even out
the distribution. Bikeshare programs in large cities have used methods related to
linear programming to help determine the best routes and methods for redistributing
bicycles to the desired stations once the desire distributions have been determined.

34. 32

The optimization model would seek to minimize transport costs and/or time subject
to constraints of having sufficient bicycles at the various stations to meet demand

35. 33

10.Reference

1. Dantzig G B, Thapa MN. Linear programming 1:Introduction. Springer-Verlag New York,
Inc, 1997.

2. Srinath LN. Linear Programming: Principles and applications. Second Edition.
Basingstoke, England: Palgrave Macmillan, 1983.

3. Bhattarai D. Linear programming problems: Determination of optimal value of real-
life practical problems. Nuta Journal. 2018; 5(1-2): 79-86.

4. Oliveira V, Paulo P. Evaluation in Urban Planning: Advances and Prospects. Journal of
Planning Literature. 2010; 24(4): 343–361.

5. Rao S. Engineering optimization: Theory and practice, Fifth Edition. John Wiley & Sons,
Inc, 2020.

6. Sahana SK, Khowas M, Sinha K. Budget optimization and allocation: An evolutionary
computing based model. Bentham Science Publishers, 2018.

7. Kanno Y. Exploiting lagrange duality for topology optimization with frictionless
unilateral contact. Japan Journal of Industrial and Applied Mathematics. 2020; 37: 25-
48.

8. Sierksma G, Zwols Y. Linear and integer optimization theory and practice. Third Edition.
Taylor & Francis Group, 2015.

9. Thie PR, Keough GE. An Introduction to linear programming and game theory. Third
Edition. John Wiley & Sons, 2008.

10. Stanimirovic I. Advances in optimization and linear programming. First Edition. Apple
Academic Press, Inc. 2022.

11. Sharma, J. Operations research theory and applications. Sixth Edition. Laxmi Publications
Pvt. Ltd, 2017.


12. Eiselt HA C-L Sandblom. Linear programming and its applications. New York, NY: Springer,
2010.

13. William PF, Fausto PG. Modeling and Linear Programming in Engineering Management.
Intech Open Access Publisher, 2013.

14. Yang X. Linear Programming. Optimization Techniques and Applications with Examples.
Hoboken, NJ, USA: John Wiley & Sons, Inc. 2018: 125–140.

15. Elhami A, Radi B. Optimizations and programming: linear, non-linear, dynamic, stochastic
and applications with Matlab. John Wiley & Sons, Inc, 2021.

16. Bixby, Robert E. Solving real-world linear programs: A decade and more of progress.
Operations research. 2002; 50(1): 3–1

36. 34


17. [BCT91] Bertsekas, D. P., Casta˜non, D. A., and Tsaknakis, H., 1991. “Reverse Auction and
the Solution of Inequality Constrained Assignment Problems, Unpublished Report.

18. [BGK77] Barr, R., Glover, F., and Klingman, D., 1977. “The Alternating Basis Algorithm for
Assignment Problems,” Math. Programming, Vol. 13, pp. 1-13.

19. [BGK78] Barr, R., Glover, F., and Klingman, D., 1978. “Generalized Alternating Path Algorith
Transportation Problems,” Euro. J. of Operations Research, Vol. 2, pp. 137-144.

20. [BGK79] Barr, R., Glover, F., and Klingman, D., 1979. “Enhancement of Spanning Tree
Labeling Procedures for Network Optimization,” INFOR, Vol 17, pp. 16-34.


21. [BHT87] Bertsekas, D. P., Hossein, P., and Tseng, P., 1987. “Relaxation Methods for Network
Flow Problems with Convex Arc Costs,” SIAM J. on Control and Optimization, Vol. 25, pp.
1219-1243.

22. [BJS90] Bazaraa, M. S., Jarvis, J. J., and Sherali, H. D., 1990. Linear Programming and
Network Flows (2nd edition), Wiley, N. Y.[BMP89] Balas, E., Miller, D., Pekny, J., and Toth,
P., 1989. “A Parallel

23. Shortest Path Algorithm for the Assignment Problem,” Management Science Report MSRR
552, Carnegie Mellon Univ., Pittsburgh, PA [BaF88] Bar-Shalom, Y., and Fortman, T. E.,
1988. Tracking and Data Association, Academic Press, N. Y.

24. [BaJ78] Bazaraa, M. S., and Jarvis, J. J., 1978. Linear Programming and Network Flows,
Wiley, N. Y. [Bal85] Balinski, M. L., 1985. “Signature Methods for the Assignment Problem,”
Operations Research, Vol. 33, pp. 527-537.

25. [Bal86] Balinski, M. L., 1986. “A Competitive (Dual) Simplex Method for the Assignment
Problem,” Math. Programming, Vol. 34, pp. 125-141. [BeC89a] Bertsekas, D. P., and
Casta˜non, D. A., 1989. “The Auction Algorithm for Transportation Problems,” Annals of
Operations Research, Vol. 20,pp. 67-96.

26. [BeC89b] Bertsekas, D. P., and Casta˜non, D. A., 1989. “The Auction Algorithm for the
Minimum Cost Network Flow Problem,” Laboratory for Information and Decision Systems
Report LIDS P-1925, M.I.T., Cambridge, MA.

27. [BeC89c] Bertsekas, D. P., and Casta˜non, D. A., 1989. “Parallel Synchronous and
Asynchronous Implementations of the Auction Algorithm,” Alphatech Report, Burlington,
MA, to appear in Parallel Computing.[BeC90a] Bertsekas, D. P., and Casta˜non, D. A., 1990.
“Parallel Asynchronous