Pemrograman Linier Formulasi Model Dan Solusi Grafis

𝕸𝖆𝖘 𝕬𝖓𝖉𝖞 𝕯𝖎𝖌𝖎𝖙𝖆𝖑 𝕸𝖊𝖉𝖎𝖆

4 min read

·

Apr 15, 2025

52

Share

Formulating and Solving Linear Programming Problems Graphically: A Complete Guide

Linear programming (LP) is a powerful mathematical technique used to optimize objectives subject to constraints. This guide provides a complete walkthrough of formulating linear programming models and solving them graphically. We'll cover the essential components, step-by-step solution methods, and considerations for real-world applications.

What is Linear Programming?

Linear programming deals with problems where the objective function and all constraints are linear. This means they can be expressed as equations or inequalities of the form: ax + by + cz + ... = k or ax + by + cz + ... ≤ k or ax + by + cz + ... ≥ k, where 'a', 'b', 'c', and 'k' are constants, and x, y, z... are decision variables. The goal is to either maximize or minimize the objective function (e.g., profit, cost) while adhering to a set of constraints (e.g., resource limitations, production capacity).

Steps to Formulating a Linear Programming Model

1. Define Decision Variables: Identify the key factors you can control to achieve your objective. These become your decision variables (often represented by x, y, z, etc.). Clearly define what each variable represents.

2. Formulate the Objective Function: Express your goal (maximizing profit or minimizing cost) as a linear function of the decision variables. This function should clearly show the relationship between the decision variables and the objective.

3. Identify Constraints: Determine all limitations or restrictions on the decision variables. These are expressed as linear inequalities or equations. Constraints often represent resource limitations, production capacities, or market demands.

4. Non-Negativity Constraints: Because you cannot produce negative quantities, add non-negativity constraints for each decision variable (e.g., x ≥ 0, y ≥ 0).

Example: Maximizing Profit

Let's consider a simple example of a company producing two products, A and B. Each product requires different amounts of raw materials and labor, and contributes differently to profit.

• Decision Variables:

  • Let x represent the number of units of product A produced.
  • Let y represent the number of units of product B produced.

• Objective Function: Assume product A contributes $10 profit per unit, and product B contributes $15 per unit. The objective is to maximize profit (Z):

  Z = 10x + 15y

• Constraints:

  • Raw Material Constraint: Product A requires 2 units of raw material, and product B requires 3 units. The company has a total of 12 units of raw material available: 2x + 3y ≤ 12
  • Labor Constraint: Product A requires 1 hour of labor, and product B requires 2 hours. The company has 8 hours of labor available: x + 2y ≤ 8
  • Non-negativity Constraints: x ≥ 0, y ≥ 0

Graphical Solution Method

The graphical method is suitable for linear programming problems with two decision variables. Here's how to solve it graphically:

1. Plot the Constraints: Graph each constraint as an inequality on a coordinate plane (x-axis representing product A, y-axis representing product B). Shade the feasible region, which satisfies all constraints.

2. Identify the Feasible Region: The feasible region is the area where all constraints are simultaneously satisfied. This is the area where all shaded regions overlap.

3. Plot the Objective Function: For various values of Z (profit), plot the corresponding objective function line. This line represents different profit levels. (Example: if Z=60, then 10x + 15y = 60)

4. Find the Optimal Solution: The optimal solution (maximizing or minimizing Z) will lie at one of the corner points (vertices) of the feasible region. Test each corner point in the objective function to determine which yields the maximum (or minimum) value.

Note: For problems with more than two variables, the simplex method or other algorithms are necessary, as graphical solutions are no longer practical.

Interpreting the Results

The optimal solution from the graphical method will provide the values of x and y that maximize (or minimize) the objective function while satisfying all constraints. This solution provides the optimal production levels for each product to maximize profit.

Conclusion

Linear programming is a versatile tool for optimization. By systematically defining decision variables, forming the objective function, and incorporating constraints, you can model and solve numerous real-world problems. The graphical method offers a visual and intuitive approach for problems with two variables, providing valuable insights into optimal solutions. Remember, for more complex problems, algorithmic methods are necessary.