---
2. Objective Function
Represents the goal.
Example:
Maximize
Z = 50x + 40y

---
3. Constraints
Restrictions on resources.
Example:
2x + y ≤ 100
x + 3y ≤ 120

---
4. Non-Negativity Constraints
Decision variables cannot be negative.
x ≥ 0
y ≥ 0

---
Assumptions of Linear Programming
1. Linearity

2. Additivity

3. Divisibility

4. Certainty

5. Non-negativity



---
Steps to Formulate an LP Problem
Step 1
Identify decision variables.

---
Step 2
Write the objective function.

---
Step 3
Write all constraints.

---
Step 4
Apply non-negativity constraints.

---
Example of LP Formulation
A factory manufactures two products A and B.
Profit:
Product A = ₹40
Product B = ₹30

Decision Variables:
x = Units of Product A
y = Units of Product B
Objective Function:
Maximize
Z = 40x + 30y
Constraints:
2x + y ≤ 100
x + y ≤ 60
x ≥ 0
y ≥ 0

---
Graphical Solution Method
The Graphical Method is used when there are only two decision variables.
Steps:
1. Draw x-axis and y-axis.

2. Plot all constraint equations.

3. Find the feasible region.

4. Determine all corner points.

5. Calculate the objective function at each corner.

6. Choose the best value.



---
Feasible Region
The region satisfying all constraints is called the Feasible Region.
Characteristics:
Contains all possible solutions.
Every point satisfies the constraints.


---
Optimal Solution
The point in the feasible region where the objective function has the maximum or minimum value is called the Optimal Solution.

---
Types of Solutions
1. Unique Optimal Solution
Only one best solution exists.

---
2. Multiple (Alternative) Optimal Solutions
More than one solution gives the same optimal value.

---
3. Unbounded Solution
Objective function increases indefinitely.
Reason:
Constraints do not sufficiently restrict the solution.


---
4. Infeasible Solution
No feasible region exists.
Reason:
Constraints contradict each other.


---
Simplex Method
The Simplex Method is an algebraic method used to solve LP problems involving more than two variables.
Developed by: George Dantzig
Advantages:
Handles many variables.
Faster than graphical method for large problems.
Widely used in optimization software.


---
Steps of the Simplex Method
1. Convert inequalities into equations using slack variables.

2. Construct the initial simplex table.

3. Select the entering variable.

4. Select the leaving variable.

5. Perform pivot operations.

6. Repeat until the optimal solution is reached.



---
Slack Variables
Slack variables convert ≤ constraints into equations.
Example:
Constraint:
2x + y ≤ 100
After adding slack variable:
2x + y + s₁ = 100
Where:
s₁ = Slack Variable

---
Big-M Method
The Big-M Method is used when LP problems contain:
Equality (=)
Greater-than-or-equal-to (≥) constraints

It introduces:
Artificial Variables
Large penalty value M

Purpose:
Remove artificial variables from the final solution.


---
Example
Constraint:
x + y ≥ 20
Converted into:
x + y − s₁ + A₁ = 20
Where:
s₁ = Surplus Variable
A₁ = Artificial Variable


---
Two-Phase Method
An alternative to the Big-M Method.
Phase 1
Find a feasible solution by removing artificial variables.
Phase 2
Solve the original LP problem using the feasible solution.
Advantages:
More systematic.
Avoids choosing a very large value of M.


---
Duality in Linear Programming
Every LP problem (called the Primal Problem) has another associated LP problem called the Dual Problem.
Characteristics:
Every primal has a dual.
Solving the dual often helps solve the primal.
Useful for sensitivity analysis.


---
Example
Primal:
Maximize
Z = 5x + 4y
Dual:
Minimize
W = ...
(The dual objective function and constraints are derived from the primal.)

---
Integer Linear Programming (ILP)
In ILP, decision variables must be integers.
Example:
Workers = 10
Machines = 5
Not Allowed:
Workers = 10.5
Applications:
Employee scheduling
Vehicle routing
Production planning


---
Applications of Linear Programming
Production planning
Transportation
Supply chain management
Marketing
Finance
Agriculture
Manufacturing


---
Advantages of Linear Programming
Maximizes profit.
Minimizes cost.
Improves resource utilization.
Supports decision-making.
Easy to implement using software.


---
Limitations of Linear Programming
Assumes linear relationships.
Requires accurate data.
Cannot directly handle uncertainty.
Not suitable for highly non-linear problems.


---
Important Exam Questions
Short Questions
1. Define Linear Programming.

2. What are Decision Variables?

3. Define Objective Function.

4. What is a Feasible Region?

5. What is the Simplex Method?

6. What is a Slack Variable?

7. Explain the Big-M Method.

8. What is Integer Linear Programming?



---
Long Questions
1. Explain the formulation of a Linear Programming Problem.

2. Describe the Graphical Method for solving LP problems.

3. Explain the Simplex Method with steps.

4. Discuss the Big-M Method and the Two-Phase Method.

5. Explain Duality in Linear Programming.

6. Discuss the applications, advantages, and limitations of Linear Programming.



---
Quick Revision Notes
Linear Programming (LP) = Optimization technique using linear equations.
Objective Function = Maximize profit or minimize cost.
Decision Variables = Unknown values to determine.
Constraints = Resource limitations.
Feasible Region = Region satisfying all constraints.
Graphical Method = Used for two variables.
Simplex Method = Used for multiple variables.
Slack Variable = Converts ≤ to =.
Big-M Method = Handles ≥ and = constraints.
Two-Phase Method = Alternative to Big-M.
Duality = Every primal LP has a corresponding dual LP.
Integer LP = Decision variables must be whole numbers.


---
Next Blog: Optimization Techniques (MCA555) – Unit 3: Transportation Problem, MODI Method, Assignment Problem (Hungarian Method), Game Theory, Two-Person Zero-Sum Games, and Dominance Principle.
x