Linear Programming (LP) deals with the optimization (maximization or minimization) of a linear objective function, subject to a set of linear equality and inequality constraints.
Example:
Maximize Z = 3x + 5y
Subject to:
x + 2y ≤ 200
3x + 2y ≤ 300
x ≥ 0, y ≥ 0
Important theorems include the Existence Theorem, Feasibility, and Boundedness. These theorems guarantee the existence of an optimal solution under certain conditions.
Example:
If a feasible region is non-empty and bounded, then the linear programming problem has at least one optimal solution.
The simplex method is an iterative procedure to solve LP problems by moving along the edges of the feasible region to find the optimal value.
Example:
Initial tableau formed → Pivot operations applied → Optimal solution obtained
While the primal simplex method starts from a basic feasible solution, the dual simplex method starts from a dual feasible solution and iterates toward optimality.
Example:
Primal LP: Max Z = 2x + 3y
Dual LP: Min W = 200a + 300b
Subject to constraints derived from the primal problem
Transportation problems deal with finding the least cost route for transporting goods. Assignment problems involve assigning resources to tasks at minimal cost or maximal profit.
Example (Transportation):
Warehouses W1, W2 to Stores S1, S2 with cost matrix
Example (Assignment):
Tasks A, B, C assigned to Workers 1, 2, 3 using Hungarian Method
A variant or small-scale version of transportation or assignment problem often used to illustrate basic principles.
Example:
3x3 cost matrix minimized using least-cost allocation technique
The graphical method is used for LP problems with two decision variables. The feasible region is plotted, and the optimal point is identified visually.
Example:
Plot constraints:
x + y ≤ 5
x ≥ 0, y ≥ 0
Identify feasible region and objective function line
A queuing system is a model used to describe the behavior of lines (queues). It includes the process of arriving, waiting in the queue, and getting served.
Example:
Bank queue system where customers arrive randomly and are served on a first-come, first-served basis.
Queuing models are classified based on the number of servers, arrival and service time distributions. The standard notation is A/S/c, where:
Example:
M/M/1 - A single server queue with exponential interarrival and service times.
M/M/c - Multi-server system with c servers.
This refers to systems with one server and one waiting line. Customers are served one at a time.
Example:
Doctor's clinic with one doctor and patients waiting in a line.
Steady state refers to the condition where the arrival rate (λ) and service rate (μ) remain constant over time. The system reaches equilibrium where the probabilities do not change.
Model I: Infinite queue capacity, exponential arrival/service
Performance metrics: Average number of customers in system (L), average wait time (W), etc.
Model II: Finite queue capacity
This refers to items that gradually wear out over time, such as machinery or vehicles. The replacement policy is based on the cost of maintenance versus the cost of replacement.
Example:
A machine costs ₹20,000 and its maintenance cost increases every year.
When the cumulative cost becomes higher than buying a new machine, replacement is recommended.
This category deals with items that suddenly fail without warning (e.g., light bulbs, electronic components). Probabilistic models are used to estimate their failure rates and replacement schedules.
Example:
If a bulb has a failure rate of 10% per month, we can plan bulk replacement to reduce costs and failure disruptions.
In individual replacement, items are replaced one by one upon failure. This method is simple but can be costly if failures are frequent.
Example:
Replacing each streetlight bulb only when it fails.
In group replacement, all items are replaced at fixed intervals, regardless of individual failures. This approach is more economical when failure rates increase with time.
Example:
All bulbs in a facility are replaced every 6 months, even if some still work, to reduce overall downtime and cost.
Inventory problems involve managing the stock of goods to minimize total costs. The main costs include:
Example:
Ordering cost = ₹50/order
Holding cost = ₹2/unit/month
Shortage cost = ₹10/unit lost sale
This model assumes known, constant demand. The goal is to determine the optimal order quantity that minimizes total inventory cost.
Example:
Annual demand = 1200 units
Ordering cost = ₹100
Holding cost = ₹5/unit/year
Economic Order Quantity (EOQ) = sqrt((2 × 1200 × 100)/5) = 219 units
This model determines the order quantity when shortages are not allowed. It uses EOQ to calculate the most economical batch size.
Formula:
EOQ = √(2DS/H)
Where D = demand, S = setup cost, H = holding cost
Here, shortages are allowed with a penalty. The model balances the costs of holding and shortages to determine optimal order size.
Example:
Use EOQ with penalty cost included to compute revised order quantity.
When items are produced rather than ordered, production rate influences the inventory model:
Example:
Production rate = 100 units/day
Demand rate = 50 units/day
Inventory builds at 100 - 50 = 50 units/day
Job sequencing problems aim to determine the optimal order of processing a set of jobs on one or more machines to minimize total elapsed time, idle time, or cost.
Example:
Given 4 jobs to be processed on 2 machines, find the sequence that minimizes the total processing time.
Johnson’s Rule is a method to find the optimal sequence of n jobs processed through two machines (Machine A and Machine B). The rule minimizes total elapsed time.
Example:
Job | M1 | M2
A | 3 | 8
B | 12 | 5
C | 4 | 7
D | 6 | 6
Apply Johnson’s Rule:
- Smallest time is A on M1 → A goes first
- Next smallest is B on M2 → B goes last
Continue until all are placed
Optimal sequence: A → C → D → B