make detailed notes for this document.
do not
leave out any detail. make a well structured notes.
Here is a comprehensive and structured set of detailed notes for the document "MODULE 2
INTRODUCTION TO LINEAR PROGRAMMING & MODULE 3 SIMPLEX METHOD" from St.
Joseph's College of Commerce, touching on every key detail and example presented. [1]
MODULE 2: Introduction to Linear Programming
Meaning & Objective
Linear Programming (LP) is a mathematical technique used for selecting the optimal solution
from a set of feasible alternatives, utilizing available resources (machinery, labor, money,
time, raw materials) most effectively. [1]
Both the objective function and constraints in LP can be expressed as linear mathematical
functions.
The aim is to maximize or minimize goals like profit, cost, efficiency, or resource utilization.
Useful for managers to solve resource allocation and decision-making problems.
Key Terms and Definitions
Linearity: Proportional ("straight-line") relationships among variables.
Process and Level: Input combinations producing specific outputs.
Objective/Criterion Function: The function to maximize or minimize, e.g., profit (maximize)
or cost/time (minimize):
Decision Variables: Quantities to determine, typically .
Constraints: Resource limitations described by inequalities or equations.
Non-Negativity Restrictions: Decision variables cannot be negative.
Standard Form of Linear Programming Problem
Decision Variables: Let denote variables to determine.
Objective Function: Maximize or Minimize
Constraints: Expressed as
and similar forms for each resource.
Non-Negativity:
Advantages of LPP
Solves optimal allocation of scarce resources.
Provides practical, usable solutions.
Improves quality and effectiveness of organizational decision-making.
Limitations of LPP
Assumes linearity and certainty, which may not reflect reality.
Cannot handle time/uncertainty, or multiple objectives directly.
Model parameters are usually assumed constant.
Applications of Linear Programming
Product Mix
Diet Problem
Portfolio Selection
Media Selection
Blending Problem
Transportation Problem
Travelling Salesman Problem
Miscellaneous (e.g., airline routing, farm planning, etc.)
Formulating LPP: Example Problems
Maximization Type
A factory must decide how many products of type A and B to make, given time constraints
on machines/craftsmen and target to maximize profit.
A firm makes three products with given raw material constraints and profit rates—determine
optimal mix.
Minimization Type
Diet problems: Select foods to meet minimum nutritional requirements at minimum cost.
City hospital: Find the minimal number of nurses per period to ensure sufficient coverage.
General Cases
Investment allocation: Optimize returns subject to risk and liquidity constraints.
Advertisement allocation in magazines: Maximize buyer exposure within budget and
magazine limits.
Multiple product and machine constraints (see more in the document for full tables and
variable setups).
Solving an LPP: Graphical Method
Applicable when there's only two variables.
Key Terms:
Solution: Set of decision variable values satisfying all constraints.
Feasible Solution: Solution meeting all constraints and non-negativity.
Infeasible Problem: No solution satisfies all constraints.
Basic Solution: Some variables set to zero; the rest are solved.
Unbounded Problem: Objective function can increase/decrease without limit.
Redundancy: A constraint is unnecessary if it doesn't affect the feasible region.
Steps in the Graphical Method:
1. Formulate the LPP and rewrite inequalities as equations.
2. Plot each constraint line.
3. Identify and shade feasible region.
4. Find corner points.
5. Calculate the objective function value at each corner.
6. Choose the optimal (highest or lowest) value.
Special Cases in LPP:
Infeasibility
Unboundedness
Redundancy
Alternate optimal solutions (more than one optimal corner point)
Degeneracy (basic solutions with zero basic variables)
Multiple optimal solutions
MODULE 3: Simplex Method
Introduction & Need
The graphical method can't handle more than two variables; the simplex method generalizes
solution to problems with multiple variables and constraints.
Simplex iteratively improves the solution towards optimality.
Types of Variables in the Simplex Method:
Slack Variables: Added to ≤ constraints.
Surplus Variables: Subtracted from ≥ constraints.
Artificial Variables: Used in equations where surplus gives negative values; aids in setting
up initial solution.
Steps for Maximization Problems (Simplex)
1. Set up inequalities for constraints.
2. Convert them to equalities using slack, surplus, and artificial variables as needed.
3. Insert variables into the simplex tableau (identity matrix via slack variables).
4. Calculate and values.
If all , optimum reached; otherwise, continue.
5. Key column: choose maximum positive .
6. Minimum ratio test: choose key row.
7. Update tableau by entering new basic variable (pivot).
8. Continue until optimum.
Sample Problems in Document:
Maximize , subject to two constraints.
Maximize , subject to three constraints.
Several others, both maximization and minimization.
Big-M Method (for Mixed Constraints)
Artificial variables introduced to start with a feasible solution.
Assign for artificial variables in minimization, in maximization.
Artificial variables dropped from the table as soon as possible.
If artificial variable remains in final table, the original problem is infeasible.
Sample Problems
Minimize/Maximize with mixed-type constraints, as given in the document.
Duality in Linear Programming
Every LPP (primal) has a dual problem with interchanged roles of decision variables and
constraints.
If primal maximizes, dual minimizes, and vice versa.
Number of constraints in primal equals number of variables in dual.
Solutions for both are equivalent for optimal values.
Rules for constructing dual are detailed with illustrative examples.
Sample Problems
Set up duals for a range of maximization and minimization problems, with varied constraints.
All definitions, methodologies, steps, and worked sample problems are presented in exhaustive
detail, with emphasis on terminology, formulation practices, special cases, computational steps,
and practical applications of linear programming in diverse fields. [1]
⁂
1. [Link]