Linear Programming and Simplex Method

Linear Programming is indeed a mathematical optimization technique used to determine the best allocation of limited resources among competing activities. It maximizes or minimizes an objective function subject to constraints.

Linear programming is deterministic, not probabilistic. All parameters in an LPP (objective coefficients, constraint coefficients, RHS values) are assumed to be known with certainty. Stochastic programming handles probabilistic scenarios.

In an LPP, the number of decision variables and constraints are independent. You can have m constraints and n decision variables with no requirement that m = n. Simplex method works with m ≠ n.

In standard LPP formulation, all variables must be non-negative (x ≥ 0). Unrestricted variables (which can be negative) must be transformed using substitution x = x' - x'' where x', x'' ≥ 0 before solving.

The graphical method is specifically designed for LPPs with exactly two decision variables. It plots the feasible region and objective function on a 2D coordinate plane. For three+ variables, use simplex or other methods.

The objective function establishes the mathematical relationship between decision variables and the goal to be optimized. For example: Z = 3x₁ + 5x₂ shows how variables x₁, x₂ determine the objective value Z.

In a linear programming problem (LPP), the optimal solution can sometimes occur at a single extreme point (vertex) rather than along an entire edge connecting two vertices. Therefore, the claim that it always lies on at least two vertices is false.

When the objective function is parallel to a binding constraint edge, multiple optimal solutions exist. All points on that edge (including both endpoints) yield the same optimal objective value.

An unbounded solution occurs when the objective function can increase (maximization) or decrease (minimization) indefinitely within the feasible region. This typically means constraints don't bound the objective in that direction.

A feasible solution must satisfy ALL constraints simultaneously. The statement claims the opposite - that not satisfying constraints makes it feasible, which is incorrect. Infeasible solutions violate at least one constraint.

Standard form of LPP requires: (1) objective is maximization, (2) all constraints are equalities (=), (3) all variables non-negative, (4) RHS is non-negative. The statement describes ≤ constraints, which is canonical form, not standard.

Canonical form of LPP is characterized by: (1) maximization objective, (2) all constraints of ≤ type, (3) non-negative variables. This matches the statement exactly. Standard form converts ≤ to = using slack variables.

A redundant constraint does not bind at the optimal solution point. Since it lies outside the active feasible region boundary, removing it doesn't change the feasible region or affect the optimal solution value.

Slack variables represent unused resources in less-than-or-equal-to constraints. Adding them to the left-hand side converts inequality constraints (≤) into equality constraints, which is required for the simplex method.

Surplus variables represent excess over minimum requirements in greater-than-or-equal-to constraints. Subtracting them from the left-hand side converts inequality constraints (≥) into equality constraints for simplex method.

Artificial variables are necessary in both maximization and minimization LPP when constraints are of the ≥ or = type. They help find an initial basic feasible solution when one doesn't exist naturally.

The simplex method requires all decision variables to be non-negative. Unrestricted variables (which can be positive or negative) must be converted by expressing each as the difference of two non-negative variables: x = x' - x''.

A variable that leaves the basis can re-enter in a later simplex iteration. The simplex method explores adjacent extreme points, and a variable may become favorable to re-enter the basis if its reduced cost becomes attractive again during optimization.

In the standard form of linear programming problems, slack and surplus variables are mathematical constructs with no economic value or cost. Therefore, their coefficients in the objective function are always zero.

When all elements in the pivot (key) column are non-positive, there is no valid ratio test to determine a leaving variable. This means the entering variable can increase indefinitely without violating any constraint, indicating an unbounded solution.

Basic variables are part of the current basis (solution). By definition, their reduced cost (zj - cj) equals zero - this is a fundamental property of the simplex method and holds for any basic feasible solution, optimal or not.

The minimum ratio test (least non-negative ratio) determines which variable reaches zero first as the entering variable increases. This selection ensures that feasibility is maintained - the chosen departing variable becomes non-basic while all other basic variables remain non-negative.