Linear Programming Problems

Introduction to Linear Programming Problems:

Linear Programming is the process to find the extreme values (maximum and minimum values) of a function for a region defined by inequalities. Linear programming (LP) is a mathematical method to determine 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.

The problem of maximizing or minimizing linear constraints from linear function subject is defined as the linear programming problem. These linear constraints are mayor may not be equalities. That is it may either equality or non equality.

Uses of Linear Programming:

More formally, uses of linear programming are the technique, in which the optimization of a linear objective functions, subject to linear equality and linear inequality constraints. Given a polytope and the 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.

Uses of Linear programming may be applied to various fields of study, which is a major uses of linear programming. It is used most extensively in business and economics studies, but can also be utilized for some engineering problems. An industry that uses linear programming models are transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse type of problems in planning, routing, scheduling, assignment, and design. Linear programming is a considerable field for uses of optimization for several reasons. Many practical problems in operations research may be expressed as linear programming problems.

Cases of Linear Programming:

Certain special cases of linear programming are network flow problems and multi commodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A certain number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming had 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 under microeconomics and company management, such as planning, production, transportation, technology and other issues.

Though the modern management issues are ever changing, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues may boil down to linear programming problems.

How to Solve Linear Programming Problem:

Structure of linear programming problem:

The linear programming problem generally consists of three components:

  •  Activities of variables and their relationships.
  •  Objective functions
  •  The constraints.

Solving a Linear programming Problem:      

How to find the solution set is called the feasible region for a set of linear inequalities. These concepts will be used for solving Linear programming Problem.

A programming problem consists of Business problem where one faces several limitations causing restrictions. One has to remain within the frame work of these restrictions and optimize his goals. The strategies of doing so successfully, is called solving a programming problem.

If the restrictions, when expressed mathematically are in the form of linear inequalities, the programming problem is called  a Linear programming Problem. These restrictions are also called constraints.

If the constraints do not have more than two variables the L.P.P Can be solved graphically.

The goals when written mathematically are called   Objective functions.

Solving a Linear programming problem using Graphical method:

This is done in two stages:

1. Find the solution set.

2. Get the optimum solution from this set.

Solve linear programming problem Step 1:

Write the restrictions or the constraints mathematically and find their solution set.

All possible solutions of the problem represent the solution set. The Feasible region is defined as the graphical representations of the constraints. This method is known as the Graphical representations of the constraints. Then the objective function is to optimize. It means to find that solution from the solution set that gives the optimum value of the objective function.

The optimum value of the objective function will be the unique, but there can be many solutions which optimize the objective function.

Solve linear programming problem Step 2:

Find the optimum solution. That is find the value/ values of the variables which optimize the objective function.

The optimum solution is found by using a theorem known as the  Convex polygon Theorem.

Applications of Linear programming problem:

  • The Diet problem
  • Portfolio optimization
  • Crew scheduling
  • Manufacturing and transportation
  • Telecommunication
  • Travelling sales man problem

Problems:

Example Problem 1: Do the calculation to find graphically the

Minimum value of the objective function. Z = – 50x + 20y — (1)

Subject to the constraints:

2x – y ? – 5 —  (2)

3x + y ? 3 —— (3)

2x – 3y ? 12 — (4)

x ? 0, y ? 0 —- (5)

Solution:

First we have to draw the graph for the given data. The feasible region (shaded) is shown in the figure. Now we can calculate Z at the corner points.

From the above figure we can see that – 300 is the smallest value of Z at the corner point (6, 0). Therefore minimum value of Z is – 300

Minimum value of Z is – 300.

Example problem 2 : Solve the following linear programming problem graphically:

Maximize Z = 4x + y —– (1)

Subject to the constraints:

x + y ? 50 — (2)

3x + y ? 90 — (3)

x ? 0, y ? 0 — (4)

Solution:

The shaded region in figure is the feasible region determined by the system of constraints (2) to (4). We observe that the feasible region OABC is bounded. So, we now use Corner Point Method to determine the maximum value of Z. The coordinates of the corner points O, A, B and C are (0, 0), (30, 0), (20, 30) and (0, 50) respectively. Now we evaluate Z at each corner point.

Hence, maximum value of Z is 120 at the point (30, 0).

Maximum value of Z is 120 at the point (30, 0).

Practice Problem 1: Solve the following linear programming problem graphically: Minimize Z = 200 x + 500 y —- (1)

Subject to the constraints:

x + 2y ? 10 —— (2)

3x + 4y ? 24 —– (3)

x ? 0, y ? 0 —– (4)

Answer: The minimum value of Z is 2300 attained at the point (4, 3)

Practice Problem 2: Solve the following problem graphically: Minimize and Maximize Z = 3x + 9y —- (1)

Subject to the constraints: x + 3y ? 60 … (2)

x + y ? 10 —– (3)

x ? y —– (4)

x ? 0, y ? 0 —– (5)

Answer: The maximum value of Z on the feasible region occurs at the two corner points C (15, 15) and D (0, 20) and it is 180 in each case.

Practice problem 3: A dietitians wishes to mix two types of foods in such a way that vitamin contents of the mixture contain at least 8 units of vitamin A and 10 units of vitamin C. Food ‘I’ contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C. Food ‘II’ contains 1 unit/kg of vitamin A and 2 units/kg of vitamin C. It costs dollars 50 per kg to purchase Food ‘I’ and dollars 70 per kg to purchase Food ‘II’. Can you minimize the cost of such a mixture?

Answer: Dollars 380.

Practice problem 4: A cooperative society of farmers has 50 hectare of land to grow two crops X and Y. The profit from crops X and Y per hectare are estimated as dollars 10,500 and dollars 9,000 respectively. To control weeds, a liquid herbicide has to be used for crops X and Y at rates of 20 liters and 10 liters per hectare. Further, no more than 800 liters of herbicide should be used in order to protect fish and wild life using a pond which collects drainage from this land. Can you find that how much land should be allocated to each crop so as to maximize the total profit of the society?

Answer: Dollars 4, 95,000