LINEAR PROGRAMMING

Linear Programming

Definition Of Linear Programming

Linear Programming is the process of finding the extreme values (maximum and minimum values) of a function for a region defined by inequalities.

Example of Linear Programming

Consider the function D = 5x + 4y.
Let us find the minimum value of this function in the region defined by the inequalities
x ≥ 0, y ≥ 0, x + 2y ≤ 4, and x + y ≤ 3.
The feasible region determined by the given constraints is shown.

Video Examples: Linear Programming

example of Linear Programming

The vertices are (0,0), (3, 0), (2, 1), and (0, 2).
To find the minimum and maximum value of D, we evaluate the value of D = 5x + 4y at each of the four vertices and we find that the minimum value of the function subject to the constraints is 0.
The process that we adopted in the example above is called Linear Programming.

Solved Example on Linear Programming

Ques: Find the maximum value of the function C = 6x + y subject to the constrains
x ≥ 0, y ≥ 0 , 5x + 3y ≤ 15.

Choices:

A. 18
B. 8
C. 5
D. 19
Correct Answer: A

Solution:

Step 1: Objective function is C = 6x + y
Step 2: Constraints are x ≥ 0, y ≥ 0 5x + 3y ≤ 15
Step 3: [Draw the graph.]
The feasible region determined by the given constraints is shown.
example of Linear Programming
Step 4: From the graph, the three vertices are (0, 0), (3, 0), and (0, 5).
Step 5: To evaluate the minimum, maximum values of C, we evaluate C = 2x + y at each of the vertices.
Step 6: [Substitute the values.]
At (0, 0) , C = 6(0) + (0) = 0
Step 7: [Substitute the values.]
At (3, 0) , C = 6(3) + (0) = 18
Step 8: [Substitute the values.]
At (0, 5) , C = 6(0) + (5) = 5
Step 9: So, the maximum value of C is 18.

Quick Summary

Linear programming involves optimizing a linear objective function subject to linear constraints.
The feasible region is the set of all points that satisfy the constraints.
Optimal solutions occur at the vertices of the feasible region.

\[ Maximize/Minimize: c^T x subject to: Ax ≤ b, x ≥ 0 \]

🍎 Teacher Insights

Emphasize the graphical method for solving linear programming problems initially. Use real-world examples to illustrate the applications of linear programming. Encourage students to check their solutions by graphing the feasible region and verifying that the optimal solution lies within it.

🎓 Prerequisites

Algebra
Graphing Linear Equations
Solving Inequalities

Check Your Knowledge

Q1: What is the first step in solving a linear programming problem?

Graph the constraints Identify the objective function Find the vertices Evaluate the objective function

Q2: The optimal solution to a linear programming problem always occurs at:

The origin A vertex of the feasible region The midpoint of the feasible region Any point within the feasible region

Frequently Asked Questions

Q: What is the objective function?
A: The objective function is the linear function that you are trying to maximize or minimize.

Q: What are constraints?
A: Constraints are the inequalities that define the feasible region.

Q: How do I find the optimal solution?
A: Evaluate the objective function at each vertex of the feasible region. The vertex that yields the maximum (or minimum) value is the optimal solution.