Scribd
Upload
64 views

Chapter # 7 Linear prog

Chapter 7 discusses linear programming, focusing on linear inequalities, objective functions, and optimal solutions. It outlines the procedure for optimizing constraints, identifying feasible regions, and distinguishing between bounded and unbounded feasible regions. The chapter also covers concepts such as redundant constraints and multiple solutions in the context of maximizing or minimizing an objective function.

Uploaded by

mian.haris010
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
64 views

Chapter # 7 Linear prog

Chapter 7 discusses linear programming, focusing on linear inequalities, objective functions, and optimal solutions. It outlines the procedure for optimizing constraints, identifying feasible regions, and distinguishing between bounded and unbounded feasible regions. The chapter also covers concepts such as redundant constraints and multiple solutions in the context of maximizing or minimizing an objective function.

Uploaded by

mian.haris010
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Chapter# 7

LINEAR PROGRAMMING
1. LINEAR INEQUALITIES
An equation defines a relationship where two expressions are equal to each other. An
equation solves to give a value of a variable.
The variables used in linear inequalities are real numbers.

An inequality defines a relationship where one expression is greater than or less than
another.
 x > y Means that x is greater than y
 x ≥ y Means that x is greater than or equal to y, or x is not less than y
 x < y Means that x is less than y
 x ≤ y Means that x is less than or equal to y, or x is not more than y

A linear inequality can be solved in a way similar to that used to solve equations. An
inequality solves to give a value of a variable at the boundary of the inequality. A
value could be one side of this variable but not the other.

Not more then 5 ≤5

Not less than 5 or at least 5 ≥ 5

2. Objective function:
A function which is to be maximized or minimized is called objective function

Revenue maximization
Profit maximization
Production maximization
Cost minimization

3. Optimal solution:
The feasible solution which maximize or minimizes the objective function is called optimal
solution.

4. Rules of manipulating inequalities


 Adding or subtracting a term to both sides of an inequality does not alter the
inequality sign.
 Multiplying or dividing both sides of an inequality by a positive number does not
alter the inequality sign.
 Multiplying or dividing both sides of an inequality by a negative number changes
the inequality sign.

5. Linear programming
o Optimal allocation of scarce competing resources.
o Linear programming is a mathematical method for determining a way to
achieve the best outcome (such as maximum profit or lowest cost) subject to
a number of limiting factors (constraints).
o A linear programming problem involves maximizing or minimizing a linear
function (the objective function) subject to linear constraints.
 Profit maximization
 Cost minimization
 Resource allocation

Complied by: Mian M Zeeshan


Page 1 of 3
Chapter# 7

o It is the process of taking various linear inequalities relating to some situation,


and finding the "best" value obtainable under those conditions.

o What constitutes the best outcome depends on the objective. The equation
constructed to represent the best outcome is known as the objective function.

6. Procedure to optimize constraints


Step 1: Define variables.
Step 2: Construct inequalities to represent the constraints.
The constraints in a linear programming problem can be drawn as straight
lines on a graph
Two points are needed to draw a straight line on a graph. The easiest
approach to finding the points is to set x to zero and calculate a value for y
and then set y to zero and calculate a value for x.
A separate constraint must be identified for each item that might put a
limitation
on the objective function.

Step 3: Plot the constraints on a graph


Step 4: Identify the feasible region. This is an area that represents the combinations
of x and y that are possible in the light of the constraints.
Step 5: Construct an objective function
Step 6: Identify the values of x and y that lead to the optimum value of the objective
function. This might be a maximum or minimum value depending on the objective.
There are different methods available of finding this combination of values of x and y.

7. Graph to express inequality

8. Feasible region
The feasible area for a solution to the problem is shown as the shaded area ABCD.
There are unlimited/infinite solutions in feasible region.

Combinations of values for x and y within this area can be achieved within the limits of the
constraints. Combinations of values of x and y outside this area are not possible, given the
constraints that exist.

To solve the linear programming problem, we now need to identify the feasible combination
of values for x and y (the combination of x and y within the feasible area) that maximises the
objective function

8.1Bounded feasible regions


The feasible region identified had boundaries on all sides (it is described as a
polygonal area). This is a bounded feasible region. A bounded feasible region
may be enclosed in a circle and will have a both a maximum value and a
minimum value.

8.2 Unbounded feasible regions


An unbounded feasible region does not have boundaries on all sides. It is not a
polygonal shape and cannot be enclosed in a circle.
If the coefficients on the objective function are all positive, then an unbounded
feasible region will have a minimum but no maximum.

Complied by: Mian M Zeeshan


Page 2 of 3
Chapter# 7

To conver unbounded feasible region to bounded region, draw a rectangle


large enough so that original corner points are inside the rectangle, now we
have new bounded region.

8.3 Infeasible solution


Sometimes system of constraints cannot be satisfied simultaneously, the
model is said to have no feasible solution. It happens when the model is not
formulated correctly.
No common region which satisfies all the three constraints.

9. Maximizing (or minimizing) the objective function


The optimal combination of values of x and y can be found using:
o corner point theorem; or
o slope of the objective function.

10. Redundant Constraint


This is a constraint which plays no part in the optimal solution because it lies outside the
feasibility region.
That does not affect the feasible solution space/region.
It can be ignored as unnecessary.

11. Multiple solution


If more than one solution gives the optimal solution, it is said to be multiple solution.

Complied by: Mian M Zeeshan


Page 3 of 3

You might also like