Go back to UGC NET COMUPTER SCIENCE

UGC NET Computer Science Application – OPTIMIZATION 

(Linear Programming · Simplex · Dual Simplex · Sensitivity · Integer Programming · Transportation · Assignment · PERT · CPM · Resource Levelling · Cost Considerations)

---

1. LINEAR PROGRAMMING (LP)

Definition: Linear Programming

Linear programming is a mathematical technique for optimizing (maximizing or minimizing) a linear objective function, subject to a set of linear constraints.

General structure:

• Objective function

  $$Z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$$

• Subject to constraints:

  $$a_{i1}{x}_1+a_{i2}{x}_2+\cdots +a_{in}{x}_n\le ,=,\ge b_i$$

• with non-negativity constraints:

  $$x_j\ge 0$$

Explanation

LP is used where resources (labor, materials, machines) are limited and must be allocated optimally.

Simple Example

Maximize

$$Z=3x+2y$$

Subject to:

$$x+y\le 4,x,y\ge 0$$

---

2. MATHEMATICAL MODEL (FORMULATION)

Definition

Formulation is the process of expressing a real-world optimization problem as an LPP using:

• Decision variables

• Objective function

• Constraints

Explanation

This converts a word problem into equations.

Example

A factory makes chairs (x) and tables (y).
Profit = 50x + 80y
Wood constraint → 3x + 5y ≤ 30
Labor constraint → 2x + y ≤ 10

---

3. GRAPHICAL SOLUTION METHOD

Definition

A method to solve LPPs with two variables by drawing constraints on a 2D graph and identifying the feasible region.

Explanation

1. Convert inequalities into lines.

2. Shade feasible region.

3. Compute objective value at each vertex.

4. Best value gives the optimum.

Example

Line x + y = 4 divides the plane; feasible region lies below it.

---

4. SIMPLEX METHOD

Definition

The Simplex Method is an iterative algebraic method to solve LPPs with two or more variables.

Explanation

• Converts inequalities to equalities by adding slack, surplus, artificial variables

• Builds a tableau

• Performs pivoting to improve the solution

• Stops when no negative indicators remain in the objective row

Key Terms

• Basic variables: variables with non-zero values

• Non-basic variables: set to zero

• Pivot element: used for row operations

---

5. DUAL SIMPLEX METHOD

Definition

A modification of simplex used when:

• The objective row is feasible

• The basic solution is infeasible (negative RHS)

Explanation

Dual Simplex works by making the RHS feasible through pivoting until all RHS ≥ 0.

---

6. SENSITIVITY ANALYSIS

Definition

Sensitivity analysis studies how changes in:

• Coefficients of objective function

• RHS of constraints

• Constraint coefficients
  affect the optimal solution.

Key Terms

• Shadow price: change in optimal Z when RHS of a constraint increases by 1 unit.

• Reduced cost: amount by which objective coefficient must improve before variable enters basis.

• Allowable range: how much parameters can vary without altering the optimal solution.

---

7. INTEGER PROGRAMMING (IP)

Definition

An optimization model where some or all decision variables must be integers.

Types

1. Pure Integer Programming – all variables integer

2. Mixed Integer Programming – some integer

3. 0–1 (Binary) Programming – variables can be 0 or 1

Explanation

Used where fractional decisions are impossible (e.g., number of machines can’t be 2.5).

Methods

• Branch & Bound

• Cutting Plane

• Dynamic Programming

---

8. TRANSPORTATION PROBLEM

Definition

A special LPP that deals with transporting commodities from multiple sources to multiple destinations at minimum cost.

Explanation

• Rows: sources

• Columns: destinations

• Each cell: cost of transporting one unit

Balance condition:
Total supply = Total demand

Initial Solution Methods

• North-West Corner

• Least Cost Method

• Vogel’s Approximation Method (VAM)

Optimal Solution Methods

• MODI (u – v method)

• Stepping-Stone Method

---

9. ASSIGNMENT PROBLEM

Definition

A special case of transportation where:

• Supply = demand = 1

• One person does one task only

Goal: Minimize cost or maximize efficiency.

Explanation

Square cost matrix (NxN).
Solved by Hungarian Method.

Steps

1. Row reduction

2. Column reduction

3. Covering zeros

4. Optimal assignment

---

10. PERT (PROGRAM EVALUATION REVIEW TECHNIQUE)

Definition

PERT is a project management tool using probabilistic time estimates to compute expected project duration.

Explanation

Each activity has three time estimates:

• $a$ = optimistic time

• $m$ = most likely time

• $b$ = pessimistic time

Expected Time

$$t_e=\frac{a+4m+b}{6}$$

Variance

$${\sigma }^2={\left(\frac{b-a}{6}\right)}^2$$

Used when time is uncertain.

---

11. CPM (CRITICAL PATH METHOD)

Definition

A deterministic technique to determine the longest duration path (critical path) through a project network.

Explanation

• Activities have certain times

• Critical Path = longest path

• Activities on this path have zero float

Float Types

1. Total Float (TF)

2. Free Float (FF)

3. Independent Float (IF)

Critical Path Formula

Critical path = sequence of activities with

$$\text{Slack}=0$$

---

12. CRITICAL PATH CALCULATIONS

Steps

1. Forward Pass (Earliest Times)

• Compute Earliest Start (ES)

• Compute Earliest Finish (EF = ES + duration)

2. Backward Pass (Latest Times)

• Compute Latest Finish (LF)

• Compute Latest Start (LS = LF – duration)

3. Slack Calculation

$$\text{Slack}=LS-ES$$

Activities with Slack = 0 → critical.

---

13. RESOURCE LEVELLING

Definition

Resource levelling adjusts activity start times to smooth out resource usage over time.

Explanation

Prevents:

• sudden peaks in manpower

• idle resources

• overburdening specific days

Used for optimizing:

• labor

• machines

• budgets

---

14. COST CONSIDERATION IN PROJECT SCHEDULING

Definition

Scheduling must consider both direct and indirect costs to obtain the lowest total project cost.

Direct Costs

Cost of performing activity itself.

Indirect Costs

Administrative, supervision, overhead.

Crash Cost

Additional cost for reducing activity duration.

Explanation

Project duration vs cost curve is U-shaped.
Goal → Find minimum total cost.

---

COMPLETE CHAPTER SUMMARY (Exam Sheet)