Geometry Of Linear Programming PDF

Preview

Summary

The fundamental theorem of linear programming says that if there is a solution to a linear programming problem then it will occur at one or more corner points or the boundary between two corner points. In other words, the solution is going to be on the edge of the region, not in the middle....

Description

Geometry Of Linear Programming BASIC CONCEPTS ABOUT LINEAR PROGRAMMING:        

 

Linear programming is a method of dealing with decision problems that can be expressed as constrained linear models. The primary objectives of all Linear Programming are certainly of the parameters and linearly of the objective function and all constraints. A mathematical technique for finding the best uses of an organization's resources. It is initially referred to as "programming in a linear structure". It was renamed "linear programming in 1948 as suggested by Tjalling Koopsmans. Programming means producing a plan or procedure that determines the solution to a problem. Graphical Solution Method is a two-dimensional geometric analysis of linear programming problems with two decision variables. Linear programming is a result of the Air Force research project concerned with computing the most efficient and economical way to distribute men, weapons, and supplies from different fronts during World War II. Linear Graphical Solution is limited in a two dimensional set of axes. Graphing software applications can be used in three variables corresponding to planes in a coordinate space ( three dimensional).

SOLVING LINEAR PROGRAMMING (LP) PROBLEM GRAPHICALLY:  

A linear programming problem in two unknowns x and y in which we are to determine the maximum and minimum values of linear expressions. It needs an objective function which can be a minimum and a maximum in the form:

Objective Function - is an expression that shows the relationship between the variables in the problem and the firm's goal. Two Types of Constraints: 1. Structural Constraint - it is a limit on the availability of resources and it is also known as an explicit constraint. 2. Non - negativity Constraint - it is the constraint that restricts all the variables to zero and positive solution and it is also known as an implicit constraint. Linear Programming Model:

OPTIMAL SOLUTION OF LP MODEL: 

Optimal Solution -is a combination of decision variable amounts that yield the best possible value of the objective function and satisfy all the constraints.

 



Optimal Value - it is the highest ( for maximization problem ) or lowest value ( for minimization problem ) of the objective function. Feasible Region - it is the set of combinations of values for the decision variables that satisfy the non-negativity conditions and all the constraints simultaneously that is the allowable decisions. Extreme Points - are the corner of the feasible region, these are the location of the maximum and minimum point of the feasible region.

Fundamental Theorem of LP Problem: There are two things we need to consider in solving the LP problem such as:  

If a Linear Programming( LP ) problem has an optimal solution, there is always at least one extreme point ( corner point ) solution of the feasible region. A Linear programming ( LP ) problem with bounded, non-empty feasible regions always contains an optimal solution.

Example: A local boutique produced two designs of gowns A and B have the following materials available: 18 square meters of cotton, 20 square meters of silk, and 5 square meters of wool. Design A requires the following; 2 square meters of cotton, 2 square meters of silk, and 1 square meter of wool. Design B requires the following: 2 square meters of cotton, 4 square meters of silk. If design A sells for Php 1,200 and design B for Php 1,600, how many of each garment should the boutique produce to obtain the maximum amount of money? Solution: Step 1: Represent the unknown in the problem. Let x be the number of Design A y be the number of Design B Step 2: Tabulate the data about the facts ( if necessary ).

Step 3: Formulate the objective function and constraints by restating the information in mathematical form ( LP model) Objective function: amount)

P =1,200x + 1,600y

(Maximize since asking for maximum

Note: P will denote that the LP model is maximization problem and C for minimization problem. Step 4: Plot the constraints of the LP problem on a graph, with design A ( x ) shown on the horizontal axis and Design B ( y ) on the vertical axis, using the intercept rule. Using the constraint for the cotton:

Using the constraint for Silk:

Step 5: From the graph on step 4 identify the feasible region. The feasible region is the shaded part which is the dark green in color. The extreme points are the points solved in step 4, which are points 1, 2, 3, 4, and 5. These points will be used to solve for the unknown coordinates. Step 6: Solve the intersection of the lines, which satisfies the feasible solution simultaneously using the elimination method.

Step 8: Formulate the decision. Since the coordinate ( 4, 3 ) will give the highest value of Php 9,600. The decision will be to create 4 Design A and 3 Design B of gowns in order to maximize the sales....