Question 1

What is linear programming?

Accepted Answer

Linear programming (LP) optimizes a linear objective function subject to linear inequality and equality constraints. It is used for production planning (how many units of each product to make), transportation, resource allocation, and scheduling. In CAE it appears in structural optimization problems where weight or cost is minimized under stress and displacement constraints.

Question 2

What is the graphical method for LP?

Accepted Answer

For 2-variable problems, each constraint is a half-plane in the x₁-x₂ plane. Their intersection forms the feasible region (a convex polygon). The objective function c₁x₁+c₂x₂=Z is a family of parallel lines. As Z increases (maximization) the line sweeps across the feasible region; the optimal solution occurs at the vertex where the line last touches the region.

Question 3

What does sensitivity analysis (RHS ranging) tell us?

Accepted Answer

Sensitivity analysis shows how the optimal objective value changes as a constraint's right-hand side (a resource limit) varies. The shadow price (dual variable) λᵢ=∂Z*/∂bᵢ tells you how much Z* improves per unit increase in resource i. For example if machine hours have a shadow price of 5, acquiring one more machine hour improves profit by 5 (within the valid range).

Question 4

Is the LP optimal solution always at a vertex?

Accepted Answer

Yes. The feasible region of an LP is a convex polytope, and a linear objective function attains its extremum at a vertex (extreme point) of this polytope. This is the fundamental theorem of LP and the basis for the simplex method, which moves from vertex to vertex improving the objective until no further improvement is possible.

Linear Programming — Graphical Method

Standard Form