Back to Operations Research

Study notes

LearnExams

Qwestrum Engineering360 · Industrial & Production · Operations Research

Linear Programming

Linear programming optimizes a linear objective under linear constraints and non-negativity limits.
Exam tip: keep SI units consistent end-to-end, write the governing relation symbolically before substituting, and sanity-check magnitude and sign.

Key formulas & points

Skim these first — then read the full notes below.

  • Feasible region convex polygon/polyhedron
  • Shadow price from dual optimal
  • Sensitivity analysis on RHS and objective coeffs

Topic details

Introduction

In industrial decision-making, LP supports product mix, blending, manpower allocation, and transport planning. Chase and Buffa discuss LP as a core quantitative planning tool.

Key relations & formulas

Formulas (Indian textbook notation)

  • maxZ=cTxs.t.Ax≤b,x≥0max Z = cᵀx s.t. Ax \le b, x \ge 0

Formulas (Indian textbook notation)

  • simplex:movetoadjacentverteximprovingZsimplex: move to adjacent vertex improving Z

Formulas (Indian textbook notation)

  • dual:minbTys.t.ATy≥cdual: min bᵀy s.t. Aᵀy \ge c

Notation and sign conventions

Relation 1 —
maxZ=cTxs.t.Ax≤b,x≥0max Z = cᵀx s.t. Ax \le b, x \ge 0

Formulas (Indian textbook notation)

  • maxZ=cTxs.t.Ax≤b,x≥0max Z = cᵀx s.t. Ax \le b, x \ge 0
Write this relation with symbols exactly as in Operations Research — Hamdy Taha before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.
Relation 2 —
simplex:movetoadjacentverteximprovingZsimplex: move to adjacent vertex improving Z

Formulas (Indian textbook notation)

  • simplex:movetoadjacentverteximprovingZsimplex: move to adjacent vertex improving Z
Write this relation with symbols exactly as in Operations Research — Hamdy Taha before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.
Relation 3 —
dual:minbTys.t.ATy≥cdual: min bᵀy s.t. Aᵀy \ge c

Formulas (Indian textbook notation)

  • dual:minbTys.t.ATy≥cdual: min bᵀy s.t. Aᵀy \ge c
Write this relation with symbols exactly as in Operations Research — Hamdy Taha before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.

Concept in depth

Graphical method is useful for two-variable intuition, while simplex scales to larger systems. Dual values provide economic interpretation such as resource marginal worth (shadow prices). Groover-style manufacturing examples often map machine-hour constraints to LP structure clearly.

Assumptions and validity limits

State assumptions explicitly before using any relation for linear programming — steady state, uniform properties, linear elastic material, ideal gas, incompressible flow, etc., as applicable.
Wrong assumptions invalidate the entire solution even when the formula is correct. In Operations Research viva and GATE descriptive questions, listing valid assumptions often earns separate marks.

Step-by-step problem approach

1. Read the question and list given data with SI units (common in Operations Research papers).
2. Draw a neat labelled diagram where applicable — examiners in Indian universities award diagram marks even when arithmetic slips.
3. Identify which relation from this topic applies to linear programming.
4. Use equation 1:
maxZ=cTxs.t.Ax≤b,x≥0max Z = cᵀx s.t. Ax \le b, x \ge 0
.
5. Use equation 2:
simplex:movetoadjacentverteximprovingZsimplex: move to adjacent vertex improving Z
.
6. Substitute values, compute, and verify units and sign (direction).
7. State conclusion in one line — e.g. safe/unsafe, stable/unstable, feasible/infeasible.

Applications & exam relevance

Linear Programming appears in logistics and planning. In Indian industrial curricula this topic is tested because it connects theory to mathematical decision models.
GATE and semester exams often combine linear programming with earlier units — revise prerequisites before attempting mixed problems.
Industry interview panels sometimes ask: "Where did you use linear programming?" — answer with a lab, mini-project, or plant visit example if possible.

Common mistakes in exams

Students frequently miss non-negativity constraints or misread max/min conversion in dual formulation. Graphical solutions also lose marks when corner points are not tested.

Quick revision checklist

Before attempting linear programming problems, confirm you can:
1. Feasible region convex polygon/polyhedron
2. Shadow price from dual optimal
3. Sensitivity analysis on RHS and objective coeffs
Revise the solved examples in Operations Research — Hamdy Taha and one previous-year GATE or university paper for this unit.

Worked examples

Try the problem first — open the solution when you are ready to check.

Two-variable LP corner test

Problem

Maximize Z = 3x + 2y subject to x + y <= 4, x <= 2, y <= 3, x,y >= 0. Find optimum by corner method.

Solution

Feasible corners: (0,0), (2,0), (2,2), (1,3), (0,3). Z values: 0,6,10,9,6. Maximum Z = 10 at (2,2).

Conceptual check — Linear Programming

Problem

In a Operations Research semester or GATE paper you are asked: "State the main assumption, the governing relation, and one practical consequence of linear programming." What should a complete answer include?

📖 Standard books (India)

  • Operations Research — Hamdy Taha

    Read: Syllabus unit

    LP, transportation, and simulation

Explore related topics

See real industrial & production careers

After exams and interviews, see how engineers actually built careers — milestones and decisions from people in the field.

Browse Industrial & Production journeysPlan your path