Important Questions Optimization Techniques BCA 4th Sem
 |
Important Questions Optimization Techniques BCA 4th Sem
1. Define a linear programming problem.
A Linear Programming Problem (LPP) is a mathematical technique used for optimization where the objective is to maximize or minimize a linear function subject to a set of linear constraints (inequalities or equations).
General Form:
Maximize or Minimize: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
Subject to:
a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
...
x₁, x₂, ..., xₙ ≥ 0
2. Explain the deterministic model of inventory.
In a deterministic inventory model, all variables and parameters such as demand, lead time, ordering cost, and holding cost are known and constant.
Example: Economic Order Quantity (EOQ) Model assumes:
Constant demand
Instantaneous replenishment
No stockouts
EOQ Formula:
Where D = demand, S = ordering cost, H = holding cost/unit/year
3. Define sequencing problem.
Sequencing problems deal with determining the order of tasks or jobs to be performed to optimize performance measures like total processing time or waiting time.
Example: Arranging jobs on a single machine to minimize completion time.
4. Explain queue length, waiting time and traffic intensity.
Queue Length: Average number of customers/items in the queue.
Waiting Time: Average time a customer spends waiting before service.
Traffic Intensity (ρ): The ratio of arrival rate (λ) to service rate (μ).
If ρ < 1, system is stable; if ρ ≥ 1, system becomes unstable.
5. What are the different types of job sequencing problems?
n Jobs on 1 Machine
2 Jobs on m Machines
n Jobs on 2 Machines (Johnson's Rule)
n Jobs on 3 Machines
Jobs with priority/rush orders
These are solved using heuristic or algorithmic approaches, depending on the configuration.
6. Simplex and dual simplex. (Numericals)
Not Available
7. Explain the Big-M method. (Numericals)
Not Available
8. Explain Assignment Problem and Transportation Method (with Numericals):
Assignment Problem: It involves assigning tasks to resources (e.g., jobs to workers) such that the total cost or time is minimized. It’s a special case of the transportation problem with a 1:1 allocation.
Solution Method: Hungarian Method.
Numerical Example (Assignment):
| | W1 | W2 | W3 |
|------|----|----|----|
| J1 | 9 | 2 | 7 |
| J2 | 6 | 4 | 3 |
| J3 | 5 | 8 | 1 |
After applying the Hungarian Method:
Minimum cost = 7 (J1-W2, J2-W3, J3-W1)
Transportation Problem: It deals with finding the least-cost way to transport goods from sources to destinations.
Methods Used:
Initial solution: North-West Corner, Least Cost, Vogel’s Approximation
Optimal: MODI Method
9. Explain the Basic Economic Order Quantity (EOQ) Model and its Assumptions:
EOQ Definition: EOQ is the order quantity that minimizes total inventory costs (ordering + holding cost).
EOQ Formula:
EOQ = \sqrt{\frac{2DS}{H}}
D = Demand/year, S = Setup cost/order, H = Holding cost/unit/year
Assumptions:
1. Constant demand and lead time
2. Instantaneous replenishment
3. No stockouts
4. Holding and ordering costs are constant
5. Only one product is involved
10. Describe the Graphical Method of Solving LPP (with Numericals):
Used for solving LPPs with 2 variables. Steps:
1. Convert constraints to equations
2. Plot them on graph
3. Identify feasible region
4. Locate corner points
5. Evaluate objective function at corners
6. Choose the optimum value
Example:
Max Z = 3x + 4y
s.t.
x + y ≤ 4
x ≤ 2
y ≤ 3
x, y ≥ 0
Corner points: (0,0), (0,3), (1,3), (2,2)
Max Z = 3(2) + 4(2) = 14 at (2,2)
11. Explain Sequencing and Types of Sequencing Problems (with Numericals):
Sequencing: It is the process of finding the best order to process a series of jobs through machines to minimize time or cost.
Types:
1. n jobs on 1 machine
2. 2 jobs on m machines
3. n jobs on 2 machines
4. n jobs on 3 machines
Example (n jobs on 2 machines):
| Job | A | B |
|-----|----|----|
| 1 | 3 | 2 |
| 2 | 5 | 1 |
| 3 | 2 | 4 |
Using Johnson’s Rule:
Optimal sequence: Job 3 → Job 1 → Job 2
Minimum total time = 12 units
Question 12
(a) Hungarian Assignment Method
The Hungarian method is an efficient algorithm to solve the Assignment Problem, which involves assigning n tasks to n agents such that the total cost is minimized (or profit maximized). It ensures a one-to-one assignment.
Steps of the Hungarian Method:
1. Row Reduction: Subtract the smallest element of each row from all elements in that row.
2. Column Reduction: Subtract the smallest element of each column from all elements in that column.
3. Draw Minimum Lines: Cover all zeros using the minimum number of horizontal or vertical lines.
4. Test for Optimality:
If the number of lines = n, the solution is optimal.
Else, modify the matrix: subtract the smallest uncovered element from all uncovered elements and add it to the elements covered twice. Repeat from Step 3.
5. Make Assignments: Choose independent zeros (no row/column repetition) to make the final assignment.
Applications: Job allocation, scheduling, and resource assignment.
(b) Johnson’s Algorithm for n Jobs and 2 Machines
Johnson's algorithm provides an optimal sequence to minimize the total time required for n jobs processed through 2 machines (say A and B) in the same order.
Assumptions:
Each job is processed first on machine A, then on machine B.
The order of jobs remains the same for both machines.
No job is processed on both machines at the same time.
Steps of Johnson’s Algorithm:
1. List the processing times for each job on both machines.
2. Find the smallest processing time among all jobs.
3. If it belongs to machine A, place the job as early as possible in the sequence.
4. If it belongs to machine B, place the job as late as possible in the sequence.
5. Repeat until all jobs are sequenced.
Example:
| Job | A (min) | B |
|-----|---------|---|
| 1 | 5 | 7 |
| 2 | 2 | 6 |
| 3 | 4 | 3 |
Using Johnson's Rule, the sequence = Job 2 → Job 3 → Job 1
Total makespan = minimized.
(c) Replacement Theory
Replacement theory deals with determining the optimal time to replace equipment or items to minimize costs (or maximize efficiency).
Types of Replacement Problems:
1. Individual Replacement: For items that fail completely (e.g., bulbs).
2. Group Replacement: When items are replaced in groups at fixed intervals even if they haven't failed (e.g., batteries).
3. Capital Equipment Replacement: Replacing machines when maintenance costs increase or performance degrades over time.
Objectives:
Minimize average cost per unit time
Maximize equipment efficiency
Avoid frequent breakdowns
Common Models:
Time-based Replacement (fixed life items)
Cost-based Replacement (when running cost > new item cost)
Applications: Industrial machinery, electronic components, fleet management, etc.
___________________________________________________________________________________
Important Note to Readers
Dear students and respected visitors,
We would like to inform you that some numerical problems may not be included in this blog post. We kindly request students and all our website visitors to practice those numericals independently, based on the methods and examples provided here.
If there are any errors or if the explanation of any question feels incomplete, we sincerely apologize. Due to time constraints, we have tried our best to deliver the most helpful content possible for your exam preparation.
We truly appreciate your support and request you to stay connected with us for more valuable content.
Warm regards,
Team Byomjitech
