Linear Programming Problems

Linear programming problems involve optimizing (maximizing or minimizing) a linear objective function subject to a set of linear inequality constraints with non-negative variables. The general form is to find values of decision variables \(x, y\) that maximize or minimize \(Z = ax + by\) subject to constraints such as \(c_1x + d_1y \leq e_1\), \(c_2x + d_2y \leq e_2\), and \(x, y \geq 0\).

Concept Explanation

The objective function \(Z = ax + by\) represents the quantity to be optimized. The variables \(x\) and \(y\) are decision variables whose values are to be determined. Constraints are linear inequalities that restrict the values of \(x\) and \(y\). The feasible region is the set of all points \((x,y)\) satisfying all constraints including non-negativity.

Formula Derivation

The objective function is given as \(Z = ax + by\). Constraints are inequalities of the form \(c_ix + d_iy \leq e_i\) or \(\geq\) depending on the problem. The feasible region is the intersection of half-planes defined by these inequalities.

Worked Illustration

Consider the problem: Maximize \(Z = 4x + y\) subject to \(x + y \leq 50\), \(3x + y \leq 90\), and \(x, y \geq 0\). The feasible region is the polygon bounded by these constraints.

Solved Example

Find the maximum value of \(Z = 4x + y\) given the constraints above.

1. Identify corner points by solving the system of equations:
2. \(x + y = 50\) and \(3x + y = 90\) intersect at \(x=20, y=30\).
3. Other corner points are \((0,0), (30,0), (0,50)\).
4. Evaluate \(Z\) at each corner point:
• At \((0,0)\), \(Z=0\)
• At \((30,0)\), \(Z=4\times30 + 0 = 120\)
• At \((20,30)\), \(Z=4\times20 + 30 = 110\)
• At \((0,50)\), \(Z=0 + 50 = 50\)
5. Maximum \(Z=120\) at \((30,0)\).

Practice Set

• Level 1 – Easy: Maximize \(Z = 3x + 2y\) subject to \(x + y \leq 10\), \(x, y \geq 0\).
• Level 2 – Moderate: Maximize \(Z = 5x + 4y\) subject to \(2x + y \leq 20\), \(x + 3y \leq 30\), \(x, y \geq 0\).
• Level 3 – Challenging: Maximize \(Z = 7x + 3y\) subject to \(3x + 2y \leq 18\), \(x + 4y \leq 16\), \(x, y \geq 0\).

Answer Key

• Level 1: Maximum \(Z=30\) at \((10,0)\) or \((0,10)\).
• Level 2: Maximum \(Z=70\) at \((10,0)\).
• Level 3: Maximum \(Z=42\) at \((4,2)\).

Quick Reference

• Objective function: \(Z = ax + by\)
• Constraints: Linear inequalities
• Feasible region: Intersection of constraints
• Optimal solution at corner points

Glossary

• Objective function: Function to be maximized or minimized.
• Decision variables: Variables whose values are to be determined.
• Constraints: Restrictions in the form of inequalities.
• Feasible region: Set of all points satisfying constraints.
• Corner points: Vertices of the feasible region polygon.

Theorems in Linear Programming

Two fundamental theorems guide the solution of linear programming problems.

Concept Explanation

The theorems state that the optimal value of the objective function occurs at a corner point of the feasible region, and if the feasible region is bounded, both maximum and minimum values exist at corner points.

Formula Derivation

Let \(R\) be the feasible region and \(Z = ax + by\) the objective function.

• Theorem 1: If \(Z\) has an optimal value, it occurs at a vertex of \(R\).
• Theorem 2: If \(R\) is bounded, \(Z\) attains both maximum and minimum at vertices of \(R\).

Worked Illustration

For the feasible region defined by \(x + y \leq 50\), \(3x + y \leq 90\), and \(x,y \geq 0\), the corner points are \((0,0), (30,0), (20,30), (0,50)\). The maximum and minimum values of \(Z\) occur at these points.

Solved Example

Refer to the previous example where \(Z=4x + y\) is maximized. The maximum occurs at \((30,0)\), a corner point, confirming Theorem 1.

Practice Set

• Level 1: Identify corner points for \(x + 2y \leq 8\), \(3x + y \leq 9\), \(x,y \geq 0\).
• Level 2: Prove that the maximum of \(Z=2x + 3y\) occurs at a vertex for the feasible region defined by \(x + y \leq 5\), \(x,y \geq 0\).
• Level 3: Show that if the feasible region is unbounded, the objective function may not have a maximum.

Answer Key

• Level 1: Corner points at \((0,0), (0,4), (3,0)\).
• Level 2: Maximum at \((0,5)\) or \((5,0)\).
• Level 3: Example: \(Z = x + y\) with \(x,y \geq 0\) and no upper bound.

Quick Reference

• Optimal values occur at vertices of feasible region.
• Bounded feasible region guarantees max and min.
• Unbounded region may lack max or min.

Glossary

• Feasible region: Set of all points satisfying constraints.
• Vertex (corner point): Intersection point of constraints.
• Bounded region: Closed and limited feasible region.
• Unbounded region: Feasible region extending infinitely.

Graphical Method for Linear Programming

The graphical method solves linear programming problems with two variables by graphing constraints and finding the feasible region.

Concept Explanation

Plot each constraint as a line on the coordinate plane. The feasible region is the intersection of the half-planes defined by the inequalities. The optimal solution lies at a corner point of this region.

Formula Derivation

Each constraint \(c_ix + d_iy \leq e_i\) is plotted as the line \(c_ix + d_iy = e_i\). The feasible side is determined by testing points.

Worked Illustration

For constraints \(x + y \leq 50\), \(3x + y \leq 90\), and \(x,y \geq 0\), plot lines and shade the feasible region.

Solved Example

Maximize \(Z=4x + y\) subject to above constraints. Evaluate \(Z\) at corner points \((0,0), (30,0), (20,30), (0,50)\) to find maximum \(Z=120\) at \((30,0)\).

Practice Set

• Level 1: Maximize \(Z=3x + 2y\) with \(x + y \leq 10\), \(x,y \geq 0\).
• Level 2: Minimize \(Z=5x + 4y\) with \(2x + y \leq 20\), \(x + 3y \leq 30\), \(x,y \geq 0\).
• Level 3: Maximize \(Z=7x + 3y\) with \(3x + 2y \leq 18\), \(x + 4y \leq 16\), \(x,y \geq 0\).

Answer Key

• Level 1: Maximum \(Z=30\) at \((10,0)\) or \((0,10)\).
• Level 2: Minimum \(Z=40\) at \((0,10)\).
• Level 3: Maximum \(Z=42\) at \((4,2)\).

Quick Reference

• Plot constraints as lines.
• Shade feasible region.
• Evaluate objective function at corner points.
• Choose max or min value.

Glossary

• Feasible region: Intersection of all constraints.
• Corner points: Vertices of feasible region polygon.
• Objective function: Function to optimize.

Corner Point Method

The corner point method finds the optimal solution by evaluating the objective function at each vertex of the feasible region.

Concept Explanation

Since the optimal value occurs at a corner point, calculate \(Z\) at each vertex and select the maximum or minimum.

Formula Derivation

Vertices are found by solving pairs of constraint equations. For each vertex \((x_i,y_i)\), compute \(Z_i = a x_i + b y_i\).

Worked Illustration

For the problem with constraints \(x + y \leq 50\), \(3x + y \leq 90\), vertices are \((0,0), (30,0), (20,30), (0,50)\). Compute \(Z\) at each.

Solved Example

Calculate \(Z=4x + y\) at each vertex:

• \(Z(0,0) = 0\)
• \(Z(30,0) = 120\)
• \(Z(20,30) = 110\)
• \(Z(0,50) = 50\)

Maximum is 120 at \((30,0)\).

Practice Set

• Level 1: Find corner points and evaluate \(Z=3x + 2y\) for \(x + y \leq 10\), \(x,y \geq 0\).
• Level 2: Evaluate \(Z=5x + 4y\) at vertices of \(2x + y \leq 20\), \(x + 3y \leq 30\), \(x,y \geq 0\).
• Level 3: For \(3x + 2y \leq 18\), \(x + 4y \leq 16\), \(x,y \geq 0\), find \(Z=7x + 3y\) at vertices.

Answer Key

• Level 1: Max \(Z=30\) at \((10,0)\) or \((0,10)\).
• Level 2: Max \(Z=70\) at \((10,0)\).
• Level 3: Max \(Z=42\) at \((4,2)\).

Quick Reference

• Find vertices by solving constraints.
• Calculate \(Z\) at each vertex.
• Select optimal value.

Glossary

• Vertex: Intersection point of constraints.
• Objective function value: Value of \(Z\) at a point.

Practical Examples of Linear Programming

Linear programming is widely used in economics, management, and planning to optimize resources.

Concept Explanation

Problems include maximizing profit, minimizing cost, or optimizing production under constraints.

Worked Illustration

Example: Maximize profit \(Z=250x + 75y\) subject to \(5x + y \leq 100\), \(x + y \leq 60\), \(x,y \geq 0\).

Solved Example

Graph constraints, find feasible region, evaluate \(Z\) at corner points to find maximum profit.

Practice Set

• Level 1: Maximize \(Z=10x + 15y\) with \(2x + y \leq 20\), \(x + 2y \leq 30\), \(x,y \geq 0\).
• Level 2: Minimize cost \(Z=5x + 8y\) with \(x + y \geq 10\), \(2x + 3y \leq 30\), \(x,y \geq 0\).
• Level 3: Maximize \(Z=7x + 9y\) with \(3x + 2y \leq 24\), \(x + 4y \leq 20\), \(x,y \geq 0\).

Answer Key

• Level 1: Max \(Z=250\) at \((10,0)\).
• Level 2: Min \(Z=50\) at \((0,10)\).
• Level 3: Max \(Z=135\) at \((4,3)\).

Quick Reference

• Use linear programming to optimize real-world problems.
• Formulate objective function and constraints.
• Graph and find feasible region.
• Evaluate objective function at vertices.

Glossary

• Profit: Revenue minus cost to be maximized.
• Cost: Expense to be minimized.
• Resource constraints: Limits on available resources.