- Linear programming (LP) is a mathematical technique used to find the best outcome in a model that includes linear relationships.
- Objective function: In LP, the objective function represents the quantity to be maximized or minimized.
- Constraints: Constraints are limitations or restrictions that must be satisfied in the linear programming model.
- Feasible region: The feasible region is the set of all feasible solutions to the linear programming problem.
- Optimization: Optimization refers to finding the best feasible solution that maximizes or minimizes the objective function.
Solving Linear Programming Problems - Graphical Method
- Graphical method: The graphical method is a visual approach to solving linear programming problems.
- Steps to solve using graphical method:
- Identify the feasible region by plotting all the constraints.
- Identify the corner points of the feasible region.
- Evaluate the objective function at each corner point.
- Determine the maximum or minimum value of the objective function.
- Find the values of the decision variables at the optimal solution.
- Corner points: The corner points of the feasible region are the vertices where the constraints intersect.
- Optimal solution: The optimal solution is the combination of decision variable values that results in the maximum or minimum objective function value.
Linear Programming Applications
- Production planning: Linear programming can be used to optimize production plans by maximizing profit or minimizing costs.
- Transportation problems: Linear programming can be used to optimize transportation routes and allocation of resources.
- Resource allocation: Linear programming can be used to allocate resources effectively and efficiently.
- Portfolio optimization: Linear programming can be used to optimize investment portfolios to maximize returns and minimize risks.
- Scheduling: Linear programming can be used to create optimal schedules for projects or tasks.
- Decision variables: Decision variables represent the unknown quantities to be determined.
- Objective function: The objective function represents the quantity to be maximized or minimized.
- Constraints: Constraints are limitations or restrictions that must be satisfied.
- Mathematical notation:
- Decision variables: x₁, x₂, x₃, …
- Objective function: Z = c₁x₁ + c₂x₂ + c₃x₃ + …
- Constraints: a₁x₁ + a₂x₂ + a₃x₃ + … ≤ b
Linear Programming - Maximization Example
- Problem statement: A company produces two products, A and B. The profit per unit of A is $10 and the profit per unit of B is $8. The company has limited resources, 200 units of raw material and 150 units of labor. Product A requires 2 units of raw material and 3 units of labor, while product B requires 4 units of raw material and 1 unit of labor. How many units of each product should the company produce to maximize profit?
- Decision variables:
- Let x₁ be the number of units of product A to produce
- Let x₂ be the number of units of product B to produce
- Objective function:
- Constraints:
- 2x₁ + 4x₂ ≤ 200
- 3x₁ + x₂ ≤ 150
- x₁, x₂ ≥ 0
Linear Programming - Minimization Example
- Problem statement: A farmer wants to plant crops to maximize profit. Two crops, maize and wheat, can be planted. The profit per acre for maize is $200 and for wheat is $300. The farmer has 120 acres of land available for planting. Each acre of maize requires 2 units of labor and each acre of wheat requires 3 units of labor. The farmer has 200 units of labor available. How many acres of each crop should the farmer plant to minimize cost?
- Decision variables:
- Let x₁ be the number of acres of maize to plant
- Let x₂ be the number of acres of wheat to plant
- Objective function:
- Minimize Z = 200x₁ + 300x₂
- Constraints:
- 2x₁ + 3x₂ ≤ 120
- x₁, x₂ ≥ 0
Linear Programming - Infeasible Solution
- Infeasible solution: An infeasible solution is a solution that does not satisfy all of the constraints in a linear programming problem.
- Reasons for infeasibility:
- Conflicting constraints
- Constraint violation due to limited resources
- Incorrectly formulated problem
- Infeasible solutions require reassessing the problem constraints and possibly modifying the objectives or constraints to make it feasible.
Linear Programming - Unbounded Solution
- Unbounded solution: An unbounded solution is a solution in which the objective function can be increased or decreased indefinitely without violating any constraints.
- If a feasible region does not have a feasible solution, it is an unbounded solution.
- Reasons for unbounded solutions:
- Missing or incorrect constraints
- Incorrectly formulated problem
- Unbounded solutions require reassessing the problem constraints and possibly modifying the objectives or constraints to make it bounded.
- Linear programming (LP) is a mathematical technique used to find the best outcome in a model that includes linear relationships.
- Objective function: In LP, the objective function represents the quantity to be maximized or minimized.
- Constraints: Constraints are limitations or restrictions that must be satisfied in the linear programming model.
- Feasible region: The feasible region is the set of all feasible solutions to the linear programming problem.
- Optimization: Optimization refers to finding the best feasible solution that maximizes or minimizes the objective function.
Solving Linear Programming Problems - Graphical Method
- Graphical method: The graphical method is a visual approach to solving linear programming problems.
- Steps to solve using graphical method:
- Identify the feasible region by plotting all the constraints.
- Identify the corner points of the feasible region.
- Evaluate the objective function at each corner point.
- Determine the maximum or minimum value of the objective function.
- Find the values of the decision variables at the optimal solution.
- Corner points: The corner points of the feasible region are the vertices where the constraints intersect.
- Optimal solution: The optimal solution is the combination of decision variable values that results in the maximum or minimum objective function value.
Linear Programming Applications
- Production planning: Linear programming can be used to optimize production plans by maximizing profit or minimizing costs.
- Transportation problems: Linear programming can be used to optimize transportation routes and allocation of resources.
- Resource allocation: Linear programming can be used to allocate resources effectively and efficiently.
- Portfolio optimization: Linear programming can be used to optimize investment portfolios to maximize returns and minimize risks.
- Scheduling: Linear programming can be used to create optimal schedules for projects or tasks.
- Decision variables: Decision variables represent the unknown quantities to be determined.
- Objective function: The objective function represents the quantity to be maximized or minimized.
- Constraints: Constraints are limitations or restrictions that must be satisfied.
- Mathematical notation:
- Decision variables: x₁, x₂, x₃, …
- Objective function: Z = c₁x₁ + c₂x₂ + c₃x₃ + …
- Constraints: a₁x₁ + a₂x₂ + a₃x₃ + … ≤ b
Linear Programming - Maximization Example
- Problem statement: A company produces two products, A and B. The profit per unit of A is $10 and the profit per unit of B is $8. The company has limited resources, 200 units of raw material and 150 units of labor. Product A requires 2 units of raw material and 3 units of labor, while product B requires 4 units of raw material and 1 unit of labor. How many units of each product should the company produce to maximize profit?
- Decision variables:
- Let x₁ be the number of units of product A to produce
- Let x₂ be the number of units of product B to produce
- Objective function:
- Constraints:
- 2x₁ + 4x₂ ≤ 200
- 3x₁ + x₂ ≤ 150
- x₁, x₂ ≥ 0
- Example:
- If x₁ = 20 and x₂ = 30, the objective function value is Z = 10(20) + 8(30) = 560
Linear Programming - Minimization Example
- Problem statement: A farmer wants to plant crops to maximize profit. Two crops, maize and wheat, can be planted. The profit per acre for maize is $200 and for wheat is $300. The farmer has 120 acres of land available for planting. Each acre of maize requires 2 units of labor and each acre of wheat requires 3 units of labor. The farmer has 200 units of labor available. How many acres of each crop should the farmer plant to minimize cost?
- Decision variables:
- Let x₁ be the number of acres of maize to plant
- Let x₂ be the number of acres of wheat to plant
- Objective function:
- Minimize Z = 200x₁ + 300x₂
- Constraints:
- 2x₁ + 3x₂ ≤ 120
- x₁, x₂ ≥ 0
- Example:
- If x₁ = 40 and x₂ = 20, the objective function value is Z = 200(40) + 300(20) = 14,000
Infeasible Solution
- Infeasible solution: An infeasible solution is a solution that does not satisfy all of the constraints in a linear programming problem.
- Reasons for infeasibility:
- Conflicting constraints
- Constraint violation due to limited resources
- Incorrectly formulated problem
-
| Infeasible solutions require reassessing the problem constraints and possibly modifying the objectives or constraints to make it feasible. |
Unbounded Solution
- Unbounded solution: An unbounded solution is a solution in which the objective function can be increased or decreased indefinitely without violating any constraints.
- If a feasible region does not have a feasible solution, it is an unbounded solution.
- Reasons for unbounded solutions:
- Missing or incorrect constraints
- Incorrectly formulated problem
-
| Unbounded solutions require reassessing the problem constraints and possibly modifying the objectives or constraints to make it bounded. |
Linear Programming - Maximization Example
- Problem statement: A company produces two products, A and B. The profit per unit of A is $10 and the profit per unit of B is $8. The company has limited resources, 200 units of raw material and 150 units of labor. Product A requires 2 units of raw material and 3 units of labor, while product B requires 4 units of raw material and 1 unit of labor. How many units of each product should the company produce to maximize profit?
- Decision variables:
- Let x₁ be the number of units of product A to produce
- Let x₂ be the number of units of product B to produce
- Objective function:
- Constraints:
- 2x₁ + 4x₂ ≤ 200
- 3x₁ + x₂ ≤ 150
- x₁, x₂ ≥ 0
- Example:
-
| If x₁ = 20 and x₂ = 30, the objective function value is Z = 10(20) + 8(30) = 560 |
Linear Programming - Minimization Example
- Problem statement: A farmer wants to plant crops to maximize profit. Two crops, maize and wheat, can be planted. The profit per acre for maize is $200 and for wheat is $300. The farmer has 120 acres of land available for planting. Each acre of maize requires 2 units of labor and each acre of wheat requires 3 units of labor. The farmer has 200 units of labor available. How many acres of each crop should the farmer plant to minimize cost?
- Decision variables:
- Let x₁ be the number of acres of maize to plant
- Let x₂ be the number of acres of wheat to plant
- Objective function:
- Minimize Z = 200x₁ + 300x₂
- Constraints:
- 2x₁ + 3x₂ ≤ 120
- x₁, x₂ ≥ 0
- Example:
-
| If x₁ = 40 and x₂ = 20, the objective function value is Z = 200(40) + 300(20) = 14,000 |
Linear Programming - Simplex Method
- Simplex method: The simplex method is an algebraic procedure for finding the optimal solution to a linear programming problem.
- It optimizes a linear objective function subject to linear equality and inequality constraints.
- The simplex method starts from an initial feasible solution and iteratively moves to adjacent feasible solutions until the optimal solution is reached.
-
| It relies on pivot operations to move from one basic feasible solution to the next. |
Linear Programming - Transportation Problem
- The transportation problem is a special case of linear programming where the objective is to minimize the cost of transporting goods from sources to destinations.
- Each source has a limited supply and each destination has a demand.
- Constraints ensure that the total supply matches the total demand.
-
| The transportation problem can be solved using the simplex method or specialized transportation algorithms. |
Linear Programming - Assignment Problem
- The assignment problem is a special case of linear programming where the objective is to assign a set of tasks to a set of resources with minimum cost or maximum benefit.
- Each task can be assigned to only one resource, and each resource can be assigned to only one task.
-
| The assignment problem can be solved using the Hungarian algorithm, which is based on the concept of augmenting paths. |
Linear Programming - Integer Programming
- Integer programming: Integer programming is a variation of linear programming where some or all of the decision variables are restricted to integer values.
- It is used when decision variables need to represent discrete quantities or choices.
- Integer programming problems are generally more challenging to solve than linear programming problems, as the feasible region becomes a discrete set.
-
| Specialized algorithms, such as branch and bound, are used to solve integer programming problems. |
Linear Programming - Sensitivity Analysis
- Sensitivity analysis: Sensitivity analysis is a technique used to determine how the optimal solution and objective function value will change with small changes in the problem data.
- It helps in understanding the impact of uncertainty or variability in the inputs on the outputs.
- Sensitivity analysis can be used to identify critical constraints, parameter values, or scenarios that affect the optimal solution.
-
| It provides valuable insights for decision-making and risk management. |
Linear Programming - Summary
- Linear programming is a mathematical technique used to find the best outcome in a model with linear relationships.
- It involves optimizing an objective function subject to linear constraints.
- The graphical method is a visual approach to solve linear programming problems.
- Feasible region, corner points, and optimal solutions are important concepts in linear programming.
- Linear programming has various applications, including production planning, resource allocation, and portfolio optimization.
- Sensitivity analysis helps in understanding the impact of changes in problem data on the optimal solution.