MATHS PROJECT

TOPIC: LINEAR PROGRAMMING

SHARATH RAJ URS

II PUC
ACADEMIC YEAR:2024-2025
Introduction to Linear Programming

Linear Programming (LP) is a mathematical method used to

determine the best outcome in a model with constraints,
represented by linear relationships. The goal of linear programming
is to find the optimal value (maximum or minimum) of a linear
objective function, subject to a set of linear constraints.
Linear programming is used in various fields, including economics,
business, and engineering, to solve optimization problems, where
resources are limited. The problem is typically modeled with decision
variables, objective functions, and constraints. The method to solve
these problems is commonly referred to as the Simplex method or
graphical methods (for problems with two variables).
The general form of a linear programming problem is:
 Maximize or Minimize: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
 Subject to: a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
…
x₁ ≥ 0, x₂ ≥ 0, ..., xₙ ≥ 0 (Non-negativity constraints)
Where:
 x₁, x₂, ..., xₙ are the decision variables
 c₁, c₂, ..., cₙ are the coefficients in the objective function
 a₁₁, a₁₂, ..., aₙₙ are the coefficients in the constraint equations
 b₁, b₂, ..., bₙ are the right-hand side constants for the
constraints
Applications of Linear Programming

1. Business and Economics:

o Profit Maximization: Companies use linear programming
to determine the optimal production levels for different
products, given resource constraints (e.g., labor, raw
materials, machine hours).
o Cost Minimization: In supply chain management, linear
programming helps minimize transportation or storage
costs while meeting customer demands.
2. Manufacturing:
o Production Planning: Linear programming can be used to
allocate resources efficiently across various production
lines to maximize output or minimize costs.
3. Diet Planning:
o Linear programming can help design the most cost-
effective diet plan that meets nutritional requirements.
The constraints involve meeting a minimum amount of
vitamins, minerals, and other nutrients, while minimizing
cost.
4. Transportation and Logistics:
o Optimization of Delivery Routes: LP models help
companies find the most cost-efficient way to transport
goods between various points, considering factors like
distance, time, and capacity.
5. Agriculture:
o Crop Planning: Linear programming is used in agriculture
to determine the best crop combination to maximize yield
or profit, given factors like land, water, and labor
constraints.
6. Energy Sector:
o Power Generation: Linear programming is applied in the
energy industry to decide the optimal mix of power
generation sources (e.g., coal, solar, wind) that meets
demand at the lowest cost.

DEFINITIONS OF LINEAR PROGRAMMING

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 conditions that the variables are non-negative
and satisfy a set of linear inequalities (called linear constraints).
The term linear implies that all the mathematical relations used in
the problem are linear relations while the term programming
refers to the method of determining a particular programme or plan
of action. Before we proceed further, we now formally define some
terms (which have been used above) which we shall be using in the
linear programming problems: Objective function Linear function
Z = ax + by, where a, b are constants, which has to be maximised or
minimized is called a linear objective function. In the above example,
Z = 250x + 75y is a linear objective function. Variables x and y are
called decision variables. Constraints The linear inequalities or
equations or restrictions on the variables of a linear programming
problem are called constraints. The conditions x ≥ 0, y ≥ 0 are called
non-negative restrictions. In the above example, the set of
inequalities (1) to (4) are constraints. Optimisation problem A
problem which seeks to maximise or minimise a linear function (say
of two variables x and y) subject to certain constraints as determined
by a set of linear inequalities is called an optimisation problem.
Linear programming problems are special type of optimisation
problems. The above problem of investing a Reprint 2024-25 LINEAR
PROGRAMMING 397 given sum by the dealer in purchasing chairs
and tables is an example of an optimisation problem as well as of a
linear programming problem. We will now discuss how to find
solutions to a linear programming problem. In this chapter, we will
be concerned only with the graphical method.
PROBLEMS BASED ON LPP
1)
Maximise Z = 3x + 4y

Subject to the constraints:

Solution:
The feasible region determined by the constraints, x + y ≤ 4, x
≥ 0, y ≥ 0, is given below.

O (0, 0), A (4, 0), and B (0, 4) are the corner points of the
feasible region. The values of Z at these points are given below.
Corner point Z = 3x +
4y

O (0, 0) 0
A (4, 0) 12
B (0, 4) 16 Maximum

Hence, the maximum value of Z is 16 at the point B (0, 4).

2) Minimise Z = −3x + 4y

subject to .
Solution:
The feasible region determined by the system of constraints,
is given below.

O (0, 0), A (4, 0), B (2, 3) and C (0, 4) are the corner points of
the feasible region.
The values of Z at these corner points are given below.

Corner point Z = – 3x + 4y

O (0, 0) 0

A (4, 0) -12 Minimum

B (2, 3) 6

C (0, 4) 16

Hence, the minimum value of Z is – 12 at the point (4, 0).

3. Maximise Z = 5x + 3y
subject to .
Solution:
The feasible region determined by the system of constraints,
3x + 5y ≤ 15, 5x + 2y ≤ 10, x ≥ 0, and y ≥ 0, is given below.

O (0, 0), A (2, 0), B (0, 3) and C (20 / 19, 45 / 19) are the corner
points of the feasible region. The values of Z at these corner
points are given below.

Corner point Z = 5x + 3y

O (0, 0) 0

A (2, 0) 10

B (0, 3) 9

C (20 / 19, 45 / 19) 235 / 19 Maximum

Hence, the maximum value of Z is 235 / 19 at the point (20 /

19, 45 / 19).
4. Minimise Z = 3x + 5y , such that .
Solution: The feasible region determined by the system of
constraints, x + 3y ≥ 3, x + y ≥ 2, and x, y ≥ 0, is given below.

It can be seen that the feasible region is unbounded.

The corner points of the feasible region are A (3, 0), B (3 / 2, 1 /
2) and C (0, 2).
The values of Z at these corner points are given below.

Corner point Z = 3x + 5y

A (3, 0) 9

B (3 / 2, 1 / 2) 7 Smallest

C (0, 2) 10

7 may or may not be the minimum value of Z because the feasible region
is unbounded.
For this purpose, we draw the graph of the inequality, 3x + 5y < 7 and
check whether the resulting half-plane has common points with the
feasible region or not.
Hence, it can be seen that the feasible region has no common point with
3x + 5y < 7.
Thus, the minimum value of Z is 7 at point B (3 / 2, 1 / 2).

5. Maximise Z = 3x + 2y

subject to .
Solution:
The feasible region determined by the constraints, x + 2y ≤ 10,
3x + y ≤ 15, x ≥ 0, and y ≥ 0, is given below.

A (5, 0), B (4, 3), C (0, 5) and D (0, 0) are the corner points of
the feasible region.
The values of Z at these corner points are given below.

Corner point Z = 3x + 2y

A (5, 0) 15

B (4, 3) 18 Maximum

C (0, 5) 10

Hence, the maximum value of Z is 18 at points (4, 3).

6. Minimise Z = x + 2y
subject to
.
Solution:
The feasible region determined by the constraints, 2x + y ≥
3, x + 2y ≥ 6, x ≥ 0, and y ≥ 0, is given below.

A (6, 0) and B (0, 3) are the corner points of the feasible region.
The values of Z at the corner points are given below.

Corner point Z = x + 2y

A (6, 0) 6

B (0, 3) 6

Here, the values of Z at points A and B are same. If we take any

other point, such as (2, 2) on line x + 2y = 6, then Z = 6.
Hence, the minimum value of Z occurs for more than 2 points.
Therefore, the value of Z is minimum at every point on the line
x + 2y = 6.
Conclusion

Linear Programming (LP) is a powerful and versatile

mathematical technique used to solve optimization problems
that involve a set of linear constraints and a linear objective
function. Its applications span across numerous industries,
including business, economics, manufacturing, transportation,
agriculture, and energy, helping organizations make informed
decisions while maximizing profits or minimizing costs.
The ability of linear programming to model real-world problems,
where resources are limited, makes it an invaluable tool for
decision-makers. By considering constraints such as resource
availability, demand, and capacity, LP provides solutions that
enable businesses and individuals to operate more efficiently
and effectively.
Through methods like the Simplex algorithm or graphical
methods, linear programming helps in achieving optimal
solutions that balance competing objectives while adhering to
necessary constraints. The study and application of LP
techniques continue to grow, and they play a crucial role in
advancing the efficiency and competitiveness of industries
worldwide.
In conclusion, Linear Programming serves as a cornerstone in
modern optimization theory, enabling practical solutions to
complex problems in diverse fields, ensuring resource
efficiency, and driving progress in real-world applications. As
industries continue to evolve, LP remains a fundamental tool for
tackling complex decision-making challenges in an increasingly
constrained world.