Ex: Find the Minimum of an Objective Function Given Constraints Using Linear Programming (unbounded)

Linear Programming: Finding Minimum Values

Introduction to Linear Programming

• The objective is to minimize the function c = 4x + 3y under specific constraints, which are represented by four inequalities.

• The first step involves identifying the feasible region by solving the system of inequalities. This will help in determining the coordinates of the vertices for further analysis.

Graphing Inequalities

• First Inequality: Graph y geq 0 as a horizontal line (the x-axis), shading above it since we want values greater than or equal to zero. Arrows indicate the shaded area.

• Second Inequality: Graph x geq 0 as a vertical line (the y-axis), shading to the right, indicating that we are only considering positive values in the first quadrant.

Analyzing Further Constraints

• Third Inequality: For 2x + 3y geq 12 , graph the line 2x + 3y = 12 . Find intercepts:

• Y-intercept at (0,4) and X-intercept at (6,0). Plot these points and draw a solid line through them. Use a test point (origin) to determine shading direction; since it yields false, shade above this line instead.

• Fourth Inequality: For x + y geq 5 , graph x + y = 5 . Intercepts found are both at (5,0) and (0,5). Again use a test point; since it yields false when substituting into inequality, shade above this line too.

Identifying Feasible Region

• The feasible region is where all shaded areas overlap—specifically where it's shaded four times—bounded by axes and lines from previous inequalities. Careful observation reveals its borders along specific lines and axes within the first quadrant.

Determining Vertices of Feasible Region

• Three key vertices identified:

• Point A: Y-intercept of x+y=5 at (0,5).

• Point B: X-intercept of 2x+3y=12 at (6,0).

• Point C: Intersection point of both lines calculated algebraically as (3,2). This intersection can be confirmed using substitution or elimination methods for accuracy in finding coordinates.

Solving for Variables and Objective Function Evaluation

Substituting Values to Solve for y

• The equation presented is 10 - 2y + 3y = 12. Distributing and combining like terms leads to the simplified form of y = 2.

• After finding y, the value of x is calculated using the equation x = 5 - y, resulting in x = 3.

• The coordinates derived from these calculations are (3, 2), which represent a point on the graph.

Evaluating Objective Function at Corner Points

• The first corner point evaluated is (0, 5). Substituting these values into the objective function gives C(0, 5) = 4(0) + 3(5) = 15.

• Next, the point (3, 2) will be used to evaluate the objective function further. This step continues to assess potential minimum values.