Linear Programming Problems - Optimize Fuel Consumption Example

  • Linear programming is a mathematical method to determine the best possible outcome or solution in a given mathematical model for a specific objective, subject to constraints.
  • One common application of linear programming is in optimizing fuel consumption.
  • Let’s consider an example to understand the concept better.
  • Suppose we have a delivery truck that needs to transport goods from one location to another.
  • The truck has a limited fuel capacity and we want to determine the most efficient way to distribute the goods while minimizing fuel consumption.
  • This can be formulated as a linear programming problem.

Objective

  • The objective of this problem is to minimize the fuel consumption.
  • We want to find the optimal solution that requires the least amount of fuel for the given delivery requirements.

Variables

  • Let’s define the following variables for our problem:
    • x1: Number of goods to be delivered to location 1.
    • x2: Number of goods to be delivered to location 2.
    • x3: Number of goods to be delivered to location 3.
    • x4: Number of goods to be delivered to location 4.

Constraints

  • We have the following constraints for our problem:
    1. x1 + x2 + x3 + x4 ≤ 100: Total number of goods cannot exceed 100.
    2. 2x1 + 3x2 + 4x3 + 5x4 ≤ 150: Total weight of goods cannot exceed 150 kg.
    3. 3x1 + 2x2 + 2x3 + 4x4 ≤ 120: Total volume of goods cannot exceed 120 cubic meters.
    4. x1, x2, x3, x4 ≥ 0: Each variable must be non-negative.

Formulation

  • The objective function can be formulated as: minimize 0.5x1 + x2 + 1.5x3 + 2x4
  • Subject to the constraints mentioned earlier.

Graphical Representation

  • Let’s graphically represent our problem to visualize the feasible region. Graphical representation

Feasible Region

  • The shaded area in the graph represents the feasible region.
  • The feasible region is the set of all points that satisfy all the constraints.
  • Any point outside the feasible region is infeasible.

Optimal Solution

  • The optimal solution is the point in the feasible region where the objective function is minimized.

Solving the Problem

  • There are various methods to solve linear programming problems, such as the graphical method, simplex method, etc.
  • In this example, let’s use the graphical method to find the optimal solution.

Graphical Method: Step 1

  • Step 1: Convert the inequality constraints into equations.
  • We will replace the inequality signs with equality signs and introduce non-negative slack variables.
  1. x1 + x2 + x3 + x4 + s1 = 100
  1. 2x1 + 3x2 + 4x3 + 5x4 + s2 = 150
  1. 3x1 + 2x2 + 2x3 + 4x4 + s3 = 120
  • Here, s1, s2, and s3 are the slack variables introduced.

Graphical Method: Step 2

  • Step 2: Graph the equations on the xy-plane.
  • Use different scales for each axis to make the graph clear. Graphical representation
  • The lines represent the equations from Step 1.
  • The feasible region is the intersection of the shaded area and the xy-plane.

Graphical Method: Step 3

  • Step 3: Locate the feasible region.
  • Find the feasible region by visually identifying the points within the shaded area.

Graphical Method: Step 4

  • Step 4: Identify the optimal solution.
  • The optimal solution will be the point in the feasible region where the objective function is minimized.
  1. Linear Programming Problems - Optimize Fuel Consumption Example
  • In our previous slides, we discussed the objective, variables, and constraints of our Linear Programming problem.
  • Now, let’s continue solving this problem by finding the optimal solution using the graphical method.
  1. Graphical Method: Step 5
  • Step 5: Plot the objective function.
  • To find the optimal solution, we need to plot the objective function on the graph.
  • The objective function is given as: minimize 0.5x1 + x2 + 1.5x3 + 2x4
  1. Graphical Method: Step 6
  • Step 6: Locate the optimal solution.
  • The optimal solution is the point where the objective function is minimized within the feasible region.
  • It can be found by drawing parallel lines to the objective function and observing the intersection with the feasible region.
  1. Example Calculation
  • Let’s solve the problem with some numerical values:
    • Suppose we have x1 = 20, x2 = 30, x3 = 50, and x4 = 0.
    • Plugging these values into the objective function, we get: 0.5(20) + (30) + 1.5(50) + 2(0) = 20 + 30 + 75 + 0 = 125.
  1. Example Calculation (Contd.)
  • Let’s consider another set of values: x1 = 10, x2 = 20, x3 = 30, and x4 = 40.
  • Plugging these values into the objective function, we get: 0.5(10) + (20) + 1.5(30) + 2(40) = 5 + 20 + 45 + 80 = 150.
  1. Example Calculation (Contd.)
  • Let’s try another set of values: x1 = 30, x2 = 0, x3 = 40, and x4 = 30.
  • Plugging these values into the objective function, we get: 0.5(30) + (0) + 1.5(40) + 2(30) = 15 + 0 + 60 + 60 = 135.
  1. Interpretation of Optimal Solution
  • From the previous calculations, we observe that the optimal solution occurs when x1 = 10, x2 = 20, x3 = 30, and x4 = 40.
  • This combination of values minimizes the fuel consumption, resulting in the least amount of fuel required to transport the goods.
  1. Sensitivity Analysis
  • Sensitivity analysis is used to determine how changes in the parameters affect the optimal solution.
  • For example, if we increase the fuel capacity from 100 to 120, how does the optimal solution change?
  • Sensitivity analysis helps in understanding the robustness of the solution.
  1. Conclusion
  • In this lecture, we discussed linear programming problems with an example of optimizing fuel consumption for a delivery truck.
  • We explored the objective, variables, and constraints of the problem.
  • We also learned about the graphical method to find the optimal solution.
  • Lastly, we performed an example calculation and discussed sensitivity analysis.
  1. References
  • Linear Programming by Robert J. Vanderbei
  • Introduction to Operations Research by Frederick S. Hillier and Gerald J. Lieberman
  • Operations Research: Applications and Algorithms by Wayne L. Winston
  1. Graphical Method: Step 7
  • Step 7: Perform sensitivity analysis.
  • Sensitivity analysis helps in understanding how changes in the objective function coefficients affect the optimal solution.
  • For example, if the coefficient of x1 in the objective function changes from 0.5 to 1, how does the optimal solution change?
  1. Example Calculation (Sensitivity Analysis)
  • Let’s consider the previous optimal solution with x1 = 10, x2 = 20, x3 = 30, and x4 = 40.
  • Now, if the coefficient of x1 changes to 1, the new objective function value will be: 1(10) + (20) + 1.5(30) + 2(40) = 110.
  1. Example Calculation (Sensitivity Analysis) (Contd.)
  • In the previous calculation, we observed that increasing the coefficient of x1 from 0.5 to 1 results in a new objective function value of 110.
  • This shows the sensitivity of the optimal solution to changes in the objective function coefficients.
  1. Applications of Linear Programming
  • Linear programming has various real-life applications in different fields, such as:
    • Supply chain management: Optimal allocation of resources, transportation, and production planning.
    • Finance: Portfolio optimization, asset-liability management.
    • Marketing: Media allocation, product mix optimization.
    • Agriculture: Farm planning, crop rotation.
    • Healthcare: Resource allocation, staff scheduling.
  1. Limitations of Linear Programming
  • Although linear programming is a powerful tool, it has certain limitations, such as:
    • Linearity assumption: Linear programming assumes that the relationships between the variables are linear, which may not always be the case in real-life scenarios.
    • Deterministic nature: Linear programming models assume that all inputs and parameters are known with certainty, which may not always be true.
    • Limited to specific problems: Linear programming is applicable only to linear problems and may not be suitable for non-linear or discrete optimization problems.
  1. Conclusion
  • In this lecture, we explored the graphical method for solving linear programming problems.
  • We learned about the steps involved in the graphical method, including converting constraints, locating the feasible region, and finding the optimal solution.
  • We also discussed the importance of sensitivity analysis and the limitations of linear programming.
  • Linear programming is a versatile tool used in various fields to optimize resource allocation and decision-making.
  1. References
  • Linear Programming and Network Flows by Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali
  • Operations Research: An Introduction by Hamdy A. Taha
  • Introduction to Mathematical Programming: Applications and Algorithms by Wayne L. Winston
  1. Additional Resources
  • If you’re interested in learning more about linear programming and its applications, consider referring to the following resources:
    • “Linear Programming: Theory and Extensions” by George Dantzig and Mukund N. Thapa
    • “Linear Programming and Its Applications” by James K. Strayer
    • Online courses and tutorials on linear programming available on platforms like Coursera, edX, and Khan Academy.
  1. Practice Problems
  • To reinforce your understanding of linear programming, try solving practice problems.
  • Consider different scenarios with varied constraints and objectives to gain a better understanding of the concept.
  • You can also refer to textbooks and online resources for a wide range of practice problems with solutions.
  1. Summary
  • In this lecture, we covered the topic of linear programming problems, with a focus on an example of optimizing fuel consumption for a delivery truck.
  • We discussed the objectives, variables, and constraints of the problem, and explored the graphical method for finding the optimal solution.
  • Additionally, we learned about sensitivity analysis, applications, limitations, and additional resources for further study.
  • Linear programming is a valuable mathematical technique used in various fields to optimize resource allocation and decision-making processes.