Step-by-Step Guide to Graphing Linear Programming Problems • SLM (Self Learning Material) for MBA

#LinearProgramming #Optimization #OperationsResearch #GraphicalMethod

Have you ever wondered how companies decide the perfect mix of products to manufacture, or how airlines determine the most profitable flight schedules? The answer often lies in linear programming, a powerful mathematical technique that helps solve optimization problems. At the heart of this method is the graphical approach – a visual way to find the best solution by literally drawing your way to success. Let’s explore how to master the art of graphing linear programming problems step by step.

Setting the foundation: Formulating your linear programming problem

Before you can draw anything meaningful, you need to translate your real-world problem into mathematical language. Think of this as creating a recipe – you need to identify your ingredients (variables) and your cooking instructions (constraints and objectives).

Let’s work with a practical example. Imagine you own a small bakery that makes two types of cookies: chocolate chip and oatmeal raisin. You have limited flour, sugar, and time, but you want to maximize your profit. Here’s how we convert this scenario into mathematical terms:

Step 1: Define your decision variables. Let x represent the number of dozens of chocolate chip cookies, and y represent the number of dozens of oatmeal raisin cookies you’ll make.

Step 2: Write your objective function. If chocolate chip cookies give you $3 profit per dozen and oatmeal raisin gives $2 profit per dozen, your objective function becomes: Maximize Z = 3x + 2y

Step 3: Establish your constraints. Perhaps you have 100 pounds of flour, and chocolate chip cookies need 2 pounds per dozen while oatmeal raisin needs 1 pound per dozen. This gives you the constraint: 2x + y ≤ 100. Similarly, you might have time constraints, sugar limitations, and the obvious non-negativity constraints (x ≥ 0, y ≥ 0).

The key is being systematic and ensuring every limitation in your real-world scenario becomes a mathematical inequality. Remember, linear programming works only when all relationships are linear – no squares, cubes, or other complex mathematical operations.

Bringing mathematics to life: Plotting constraints on your graph

Now comes the exciting part – transforming those mathematical expressions into visual representations. Think of your graph as a map where each constraint draws a boundary, and together they create a territory where your solution must live.

Setting up your coordinate system

Choose appropriate scales. Look at your constraint values to determine reasonable scales for your x and y axes. If your constraints involve numbers in the hundreds, don’t make each grid square represent 1 unit – you’ll run out of paper! Instead, let each square represent 5 or 10 units.

Label your axes clearly. Your x-axis represents your first decision variable, and your y-axis represents your second. In our bakery example, the x-axis shows dozens of chocolate chip cookies, and the y-axis shows dozens of oatmeal raisin cookies.

Converting constraints into boundary lines

Each constraint inequality becomes a straight line on your graph. Here’s the process:

Convert inequality to equality. Take your constraint 2x + y ≤ 100 and temporarily make it 2x + y = 100. This line represents the boundary of your constraint.

Find two points on the line. The easiest approach is to find where the line crosses each axis. When x = 0, then y = 100. When y = 0, then 2x = 100, so x = 50. Plot these points (0, 100) and (50, 0) and draw a straight line connecting them.

Determine which side satisfies the inequality. Pick any point not on the line – (0, 0) is usually convenient. Substitute into your original inequality: 2(0) + 0 ≤ 100? Yes, 0 ≤ 100 is true. This means the area containing (0, 0) satisfies the constraint. Shade this region lightly or mark it with arrows.

Repeat this process for every constraint. Don’t forget your non-negativity constraints (x ≥ 0, y ≥ 0) – these simply mean you only consider the first quadrant of your graph.

Identifying the feasible region

The magic happens when you look at where all your shaded regions overlap. This intersection – called the feasible region – represents all possible solutions that satisfy every constraint simultaneously. It’s like finding the sweet spot where all your limitations are respected.

The feasible region in linear programming problems typically forms a polygon. Sometimes it might be unbounded (extending infinitely in one direction), and occasionally, if your constraints are contradictory, there might be no feasible region at all.

The moment of truth: Finding your optimal solution

Here’s where linear programming reveals its elegant simplicity. The optimal solution – the point that maximizes or minimizes your objective function – always occurs at a corner point (vertex) of your feasible region. This isn’t coincidence; it’s a mathematical certainty known as the fundamental theorem of linear programming.

Locating corner points

Visual identification. Look at your feasible region and identify every corner. These occur where two constraint lines intersect, where a constraint line meets an axis, or where two axes meet (the origin).

Mathematical calculation. For precision, calculate the exact coordinates of each corner point by solving the system of equations formed by the intersecting lines. For instance, if lines 2x + y = 100 and x + 2y = 80 intersect, solve this system simultaneously.

From 2x + y = 100, we get y = 100 – 2x. Substituting into the second equation: x + 2(100 – 2x) = 80, which simplifies to x + 200 – 4x = 80, giving us -3x = -120, so x = 40. Therefore, y = 100 – 2(40) = 20. The intersection point is (40, 20).

Evaluating the objective function

Now test your objective function at each corner point:

Calculate systematically. If your objective function is Z = 3x + 2y, substitute each corner point’s coordinates. For point (40, 20): Z = 3(40) + 2(20) = 120 + 40 = 160.

Compare all values. The corner point that gives the highest value (for maximization problems) or lowest value (for minimization problems) is your optimal solution.

Interpret your results. Don’t just state numbers – translate back to your original problem. If (40, 20) is optimal with Z = 160, this means making 40 dozen chocolate chip cookies and 20 dozen oatmeal raisin cookies will give you the maximum profit of $160.

Special cases to watch for

Sometimes you might encounter unique situations. If two adjacent corner points give the same optimal value, you have multiple optimal solutions – any point on the line segment between them is also optimal. If your feasible region is unbounded in the direction that improves your objective function, the problem has no finite optimal solution.

The graphical method brilliantly transforms abstract mathematical optimization into a concrete, visual process. By following these systematic steps – formulating equations, plotting constraints, and evaluating corner points – you can solve complex resource allocation problems with nothing more than graph paper and careful calculation.

What do you think? Can you imagine applying this graphical approach to optimize your own daily decisions, like balancing study time between different subjects? How might businesses use this method to make strategic decisions about product mixes or resource allocation?

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

PDF

Comments

Operations Research

1 Operations Research-An Overview

2 Linear Programming- Formulation and Graphical Method

3 Linear Programming-Simplex Method

4 Transportation Problem

5 Assignment Problem

6 Application of Excel Solver to Solve LPP

7 Goal Programming

8 Integer Programming

9 Dynamic Programming

10 Non-Linear Programming

11 Introduction to game theory and its Applications

12 Monte Carlo Simulation

13 Queueing Models