[go: up one dir, main page]
Scribd
Upload
6 views5 pages

Linear Programming Sem 4 Vansh Utreja

ok

Uploaded by

Vela CRI
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
6 views5 pages

Linear Programming Sem 4 Vansh Utreja

ok

Uploaded by

Vela CRI
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/ 5

Linear Programming

Introduction: linear programming is a method of optimising operations with


some constraints. The main objective of linear programming is to maximize or
minimize the numerical value. It consists of linear functions which are subjected
to the constraints in the form of linear equations or in the form of inequalities.

Meaning: linear programming is considered as an optimization method to


maximize or minimize the objective function of the given mathematical model
with the set of some requirements which are represented in the linear
relationship. The main aim of the linear programming problem is to find the
optimal solution.

Characteristics:

The following are the five characteristics of the linear programming


problem:

Constraints – The limitations should be expressed in the mathematical


form, regarding the resource.

Objective Function – In a problem, the objective function should be


specified in a quantitative way.

Linearity – The relationship between two or more variables in the function


must be linear. It means that the degree of the variable is one.

Finiteness – There should be finite and infinite input and output numbers.
In case, if the function has infinite factors, the optimal solution is not
feasible.

Non-negativity – The variable value should be positive or zero. It should


not be a negative value.

Decision Variables – The decision variable will decide the output. It gives
the ultimate solution of the problem. For any problem, the first step is to
identify the decision variables.
Linear Programming Simplex Method
The simplex method is one of the most popular methods to solve linear
programming problems. It is an iterative process to get the feasible
optimal solution. In this method, the value of the basic variable keeps
transforming to obtain the maximum value for the objective function. The
algorithm for linear programming simplex method is provided below:

Step 1: Establish a given problem. (i.e.,) write the inequality constraints


and objective function.

Step 2: Convert the given inequalities to equations by adding the slack


variable to each inequality expression.

Step 3: Create the initial simplex tableau. Write the objective function at
the bottom row. Here, each inequality constraint appears in its own row.
Now, we can represent the problem in the form of an augmented matrix,
which is called the initial simplex tableau.

Step 4: Identify the greatest negative entry in the bottom row, which
helps to identify the pivot column. The greatest negative entry in the
bottom row defines the largest coefficient in the objective function, which
will help us to increase the value of the objective function as fastest as
possible.

Step 5: Compute the quotients. To calculate the quotient, we need to


divide the entries in the far-right column by the entries in the first column,
excluding the bottom row. The smallest quotient identifies the row. The
row identified in this step and the element identified in the step will be
taken as the pivot element.

Step 6: Carry out pivoting to make all other entries in column is zero.

Step 7: If there are no negative entries in the bottom row, end the
process. Otherwise, start from step 4.

Step 8: Finally, determine the solution associated with the final simplex
tableau.
Graphical Method
The graphical method is used to optimize the two-variable linear
programming. If the problem has two decision variables, a graphical
method is the best method to find the optimal solution. In this method,
the set of inequalities are subjected to constraints. Then the inequalities
are plotted in the XY plane. Once, all the inequalities are plotted in the XY
graph, the intersecting region will help to decide the feasible region. The
feasible region will provide the optimal solution as well as explains what
all values our model can take. Let us see an example here and understand
the concept of linear programming in a better way.

Example:

Calculate the maximal and minimal value of z = 5x + 3y for the following


constraints.

x + 2y ≤ 14

3x – y ≥ 0

x–y≤2

Solution:

The three inequalities indicate the constraints. The area of the plane that
will be marked is the feasible region.

The optimisation equation (z) = 5x + 3y. You have to find the (x,y) corner
points that give the largest and smallest values of z.

To begin with, first solve each inequality.

x + 2y ≤ 14 ⇒ y ≤ -(1/2)x + 7

3x – y ≥ 0 ⇒ y ≤ 3x

x–y≤2⇒y≥x–2

Here is the graph for the above equations.


Now pair the lines to form a system of linear equations to find the corner
points.

y = -(½) x + 7

y = 3x

Solving the above equations, we get the corner points as (2, 6)

y = -1/2 x + 7

y=x–2

Solving the above equations, we get the corner points as (6, 4)

y = 3x

y=x–2

Solving the above equations, we get the corner points as (-1, -3)

For linear systems, the maximum and minimum values of the optimisation
equation lie on the corners of the feasibility region. Therefore, to find the
optimum solution, you only need to plug these three points in z = 3x + 4y
(2, 6) :

z = 5(2) + 3(6) = 10 + 18 = 28

(6, 4):

z = 5(6) + 3(4) = 30 + 12 = 42

(–1, –3):

z = 5(-1) + 3(-3) = -5 -9 = -14

Hence, the maximum of z = 42 lies at (6, 4) and the minimum of z = -14


lies at (-1, -3).

You might also like