Foundations of Linear Programming

Foundations of Linear Programming: Core Concepts

Chapter Overview

This section lays the fundamental mathematical groundwork for understanding Linear Programming Problems (LPPs). It introduces key concepts from convex analysis, which are crucial for comprehending the structure of LPPs, their feasible regions, and the nature of their optimal solutions. A strong grasp of convex sets, convex functions, hyperplanes, and extreme points is essential for solving and interpreting LPPs.

Key Concepts with Explanations

Sets in $\mathbf{R}^n$

* A set $S$ in $n$-dimensional Euclidean space $\mathbf{R}^n$ is a collection of points $x = (x_1, x_2, \dots, x_n)$.
* A line segment connecting two points $x_1, x_2 \in \mathbf{R}^n$ is the set of all points $x$ such that:

Convex Sets

* Definition: A set $S \subseteq \mathbf{R}^n$ is called a convex set if for any two points $x_1, x_2 \in S$, the entire line segment connecting $x_1$ and $x_2$ is also contained in $S$.
* Mathematically, for all $x_1, x_2 \in S$ and for all $\lambda \in [0, 1]$, the point $\lambda x_1 + (1-\lambda) x_2$ must also be in $S$.
* Properties:
* The intersection of any number of convex sets is a convex set.
* The union of convex sets is not necessarily convex.
* A single point is a convex set. The empty set is a convex set.
* Examples of Convex Sets:
* $\mathbf{R}^n$ itself.
* Any line, line segment, or ray.
* Half-spaces (e.g., $a^T x \le b$).
* Hyperplanes (e.g., $a^T x = b$).
* Polyhedra (intersection of finite number of half-spaces).
* Balls (circles, spheres, ellipses, ellipsoids): e.g., $S = \{(x, y) | x^2 + y^2 \le r^2\}$.
* Parabolic regions like $S = \{(x, y) | y^2 \le 4x, x \ge 0, y \ge 0\}$.
* Examples of Non-Convex Sets:
* $S = \{(x, y) | xy \le 1\}$ (unless restricted to a single quadrant, e.g., $x,y \ge 0$).
* $S = \{(x, y) | x^2 + 4y^2 \ge 12\}$ (exterior of an ellipse).
* A star shape.

Convex Hull

* Definition: The convex hull of a set $S$, denoted $\operatorname{conv}(S)$, is the smallest convex set containing $S$. It is the intersection of all convex sets containing $S$.
* For a finite set of points $\{x_1, \dots, x_k\}$, their convex hull is the set of all convex combinations:

Extreme Points (Vertices)

* Definition: A point $x$ in a convex set $S$ is an extreme point (or vertex) if it cannot be expressed as a convex combination of two distinct points in $S$. That is, if $x = \lambda x_1 + (1-\lambda) x_2$ for $x_1, x_2 \in S$ and $\lambda \in (0, 1)$, then it must be that $x_1 = x_2 = x$.
* Importance in LPP: If an LPP has an optimal solution, at least one optimal solution occurs at an extreme point of the feasible region.
* Examples:
* For a polygon, its vertices are its extreme points.
* For a closed disk (e.g., $x^2+y^2 \le 1$), every point on its boundary (circumference) is an extreme point.
* For a line segment, its two endpoints are the extreme points.
* An open half-space or an entire $\mathbf{R}^n$ has no extreme points.

Hyperplanes and Half-spaces

* Hyperplane: A hyperplane in $\mathbf{R}^n$ is a set of points $x$ satisfying a linear equation:

where $a \in \mathbf{R}^n$ is a non-zero vector (normal vector) and $b \in \mathbf{R}$ is a scalar.
* In $\mathbf{R}^2$, a hyperplane is a line. In $\mathbf{R}^3$, it's a plane.
* Hyperplanes are convex sets.
* Half-space: A hyperplane divides $\mathbf{R}^n$ into two half-spaces.
* Closed half-spaces:


* Open half-spaces:


* Half-spaces are convex sets.
* Checking if a point lies in a half-space: Substitute the coordinates of the point into the inequality.
* Example: For hyperplane $2x_1 + 3x_2 + 4x_3 + 5x_4 = 6$, check point $(-1, 2, 7, 6)$.
$2(-1) + 3(2) + 4(7) + 5(6) = -2 + 6 + 28 + 30 = 62$.
Since $62 > 6$, the point lies in the half-space $2x_1 + 3x_2 + 4x_3 + 5x_4 > 6$.

Convex Functions and Concave Functions

* Definition (Convex Function): A function $f: S \to \mathbf{R}$ is convex if its domain $S$ is a convex set and for any $x_1, x_2 \in S$ and $\lambda \in [0, 1]$:

Geometrically, the line segment connecting any two points on the graph of a convex function lies above or on the graph.
* Definition (Concave Function): A function $f: S \to \mathbf{R}$ is concave if its domain $S$ is a convex set and for any $x_1, x_2 \in S$ and $\lambda \in [0, 1]$:

Equivalently, $f$ is concave if and only if $-f$ is convex. Geometrically, the line segment connecting any two points on the graph of a concave function lies below or on the graph.
* Properties:
* A function that is both convex and concave is a linear function.
* The sum of convex functions is convex.
* If $f$ is convex, its epigraph (set of points above its graph) is a convex set.
* If $f$ is concave, its hypograph (set of points below its graph) is a convex set.
* Second Derivative Test (for $C^2$ functions):
* A function $f$ is convex if its Hessian matrix $\nabla^2 f(x)$ is positive semi-definite for all $x$ in its domain.
* A function $f$ is concave if its Hessian matrix $\nabla^2 f(x)$ is negative semi-definite for all $x$ in its domain.
* Examples:
* Convex: $f(x) = x^2$, $f(x, y) = x^2 + y^2 - 1$, $f(x) = e^x$, $f(x) = |x|$.
* Concave: $f(x) = -x^2$, $f(x, y) = -x^2 - y$, $f(x) = \log x$.
* Both Convex and Concave: Linear functions, e.g., $f(x, y) = 2x + 3y$.
* Neither Convex nor Concave: $f(x, y) = xy - 1$. (Hessian is $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$, which is indefinite).

Linear Programming Problem (LPP)

* Definition: An LPP is an optimization problem where the objective function and all constraints are linear functions of the decision variables.
* General Form:

* Vector/Matrix Form (Standard Form):

where $c \in \mathbf{R}^n$, $x \in \mathbf{R}^n$, $A \in \mathbf{R}^{m \times n}$, $b \in \mathbf{R}^m$.
* Components:
* Objective Function: The linear function to be maximized or minimized (e.g., $2x_1 + 4x_2$).
* Decision Variables: The variables whose values are to be determined (e.g., $x_1, x_2$).
* Constraints: Linear inequalities or equalities that the decision variables must satisfy (e.g., $x_1 + x_2 \le 4$).
* Non-negativity Restrictions: Typically, decision variables are required to be non-negative (e.g., $x_1, x_2 \ge 0$).
* Characteristics of an LPP:
* All functions (objective and constraints) must be linear.
* No products of variables (e.g., $x_1x_2$).
* No powers other than 1 (e.g., $x_1^2$).
* No absolute values (e.g., $|x_1|$).

Feasible Region and Optimal Solutions of LPP

* Feasible Region (or Feasible Set): The set of all points $x$ that satisfy all the constraints (including non-negativity restrictions) of an LPP.
* Properties of the Feasible Region:
* The feasible region of an LPP is always a convex set. This is because each constraint defines a half-space, and the feasible region is the intersection of these half-spaces (and the non-negativity constraints define half-spaces like $x_i \ge 0$), and the intersection of convex sets is convex.
* The feasible region is a polyhedron (a set formed by the intersection of a finite number of half-spaces). If it is bounded, it is called a polytope.
* Properties of Optimal Solutions:
* If an LPP has an optimal solution, then at least one optimal solution occurs at an extreme point (vertex) of the feasible region.
* The set of all optimal solutions for an LPP (if multiple exist) is a convex set.
* If an LPP has two distinct optimal solutions, then every point on the line segment connecting these two solutions is also an optimal solution.
* Optimal solutions for an LPP do not always exist. An LPP can be:
* Infeasible: No points satisfy all constraints (empty feasible region).
* Unbounded: The objective function can be improved indefinitely without violating constraints.
* Unique Optimal Solution: A single point yields the best objective value.
* Multiple Optimal Solutions: An entire line segment or face of the feasible region yields the best objective value.
* An LPP does not necessarily admit a unique optimal solution.

Important Points/Tips for Exam Preparation

* Master Convexity: A deep understanding of convex sets and convex/concave functions is paramount. Practice identifying them from equations and graphs.
* Hessian Matrix: For $C^2$ functions, remember the Hessian test for convexity/concavity.
* LPP Definition: Be able to quickly identify if a given problem is an LPP. Look for non-linear terms (products, powers, absolute values).
Feasible Region Properties: Remember that the feasible region of an LPP is always* a convex set.
* Optimal Solution Properties:
* Optimal solutions, if they exist, occur at extreme points.
* The set of optimal solutions is convex.
* Optimal solutions are not always unique and do not always exist.
* Extreme Points Counting: Practice finding the number of extreme points for various convex sets, especially polygons defined by linear inequalities.
* Half-space Check: Know how to determine if a point lies in a specific half-space by substituting its coordinates.

---

Foundations of Linear Programming: Part 4 - Applications

Chapter Overview

This section focuses on the practical utility of Linear Programming (LP) by demonstrating how real-world problems can be formulated as Linear Programming Problems (LPPs). Understanding the formulation process is crucial for translating complex scenarios into a solvable mathematical model, which then allows for the application of various LP techniques to find optimal solutions. This also reinforces the fundamental properties of LPPs, such as linearity and convexity, which are frequently tested in examinations.

Key Concepts

Problem Formulation: The process of translating a real-world decision-making problem into a mathematical LPP model. This involves identifying:

* Decision Variables: Unknown quantities that need to be determined to achieve the objective. These are typically non-negative.
* Objective Function: A linear mathematical expression that represents the goal of the problem (e.g., maximizing profit, minimizing cost).
* Constraints: Linear inequalities or equalities that represent limitations or requirements (e.g., resource availability, production capacity, demand).

Linearity: A defining characteristic of LPPs. Both the objective function and all constraints must be linear functions of the decision variables. This implies:

* No products of variables (e.g., $x_1x_2$).
* No powers of variables other than one (e.g., $x_1^2$).
* No non-linear functions (e.g., $\sin(x)$, $\log(x)$, $|x|$ unless linearized).

Feasible Region (Solution Space): The set of all possible solutions that satisfy all the constraints, including non-negativity restrictions. For an LPP, the feasible region is always a convex set and a polyhedron (an intersection of half-spaces).

Optimal Solution: A feasible solution that yields the best possible value for the objective function (maximum for maximization problems, minimum for minimization problems).

* The set of all optimal solutions for an LPP, if it exists, is also a convex set.
* If an LPP has multiple optimal solutions, any convex combination (point on the line segment) of these optimal solutions is also an optimal solution.

Extreme Points (Corner Points): Vertices of the feasible region. For a bounded feasible region, an optimal solution to an LPP always occurs at one or more extreme points.

Important Formulas

The general structure of a Linear Programming Problem (LPP) can be expressed as:

Objective Function:

Subject to Constraints:

Non-negativity Restrictions:

In matrix notation, this can be written as:

where $\mathbf{c}$ is the vector of objective function coefficients, $\mathbf{x}$ is the vector of decision variables, $\mathbf{A}$ is the matrix of technological coefficients, and $\mathbf{b}$ is the vector of resource availabilities/requirements.

Examples (Problem Formulation)

#### Example 1: Production Problem

A company produces two types of toys, A and B. Toy A requires 2 hours of labor and 1 unit of raw material. Toy B requires 1 hour of labor and 2 units of raw material. The company has 100 hours of labor and 80 units of raw material available. The profit for Toy A is \3 per unit, and for Toy B is \2 per unit. Formulate an LPP to maximize the total profit.

Solution:

Decision Variables:

* Let $x_1$ be the number of units of Toy A produced.
* Let $x_2$ be the number of units of Toy B produced.

Objective Function (Maximize Profit):

* Profit from Toy A: $3x_1$
* Profit from Toy B: $2x_2$
* Total Profit $Z = 3x_1 + 2x_2$

Constraints:

* Labor Constraint: (2 hours for A) + (1 hour for B) $\le$ 100 hours available

* Raw Material Constraint: (1 unit for A) + (2 units for B) $\le$ 80 units available

Non-negativity Restrictions:

* The number of toys produced cannot be negative.

Complete LPP Formulation:

#### Example 2: Diet Problem

A person needs to consume at least 60 units of Vitamin C and 40 units of Vitamin D daily. Two types of food, F1 and F2, are available. Each unit of F1 contains 3 units of Vitamin C and 2 units of Vitamin D. Each unit of F2 contains 2 units of Vitamin C and 4 units of Vitamin D. The cost of F1 is \5 per unit, and F2 is \4 per unit. Formulate an LPP to minimize the total cost while meeting the nutritional requirements.

Solution:

Decision Variables:

* Let $x_1$ be the number of units of Food F1 consumed.
* Let $x_2$ be the number of units of Food F2 consumed.

Objective Function (Minimize Cost):

* Cost from F1: $5x_1$
* Cost from F2: $4x_2$
* Total Cost $Z = 5x_1 + 4x_2$

Constraints:

* Vitamin C Requirement: (3 units from F1) + (2 units from F2) $\ge$ 60 units required

* Vitamin D Requirement: (2 units from F1) + (4 units from F2) $\ge$ 40 units required

Non-negativity Restrictions:

* The amount of food consumed cannot be negative.

Complete LPP Formulation:

Important Points/Tips for Exam Preparation

Identify LPPs Correctly: An LPP must have a linear objective function and all linear constraints. Any non-linear term (e.g., $x_1x_2$, $x_1^2$, $|x_1|$ if not linearized) makes it not an LPP.

PYQ Context*: Questions often ask to identify which option is an LPP. Look for strict linearity.
* Example: $\max x_1^2$ or $\max x_1x_2$ are NOT LPPs. $\max |x_1|$ is not an LPP unless transformed.

Convexity of Feasible Region: The set of all feasible solutions for any LPP is always a convex set. This is a fundamental property derived from the fact that each linear inequality defines a half-space, and the intersection of half-spaces is always convex.

PYQ Context*: Many questions test the understanding of convex sets, often asking to identify convex sets or properties related to the feasible region of an LPP.
* Example: A set defined by $x^2+y^2 \le R^2$ (a disk) is convex. A set defined by $xy \le 1$ is generally not convex.

Convexity of Optimal Solution Set: If an LPP has multiple optimal solutions, the set of all optimal solutions is also a convex set. This means if $X_1^$X1∗​ and $X_2^$ are two optimal solutions, then any point on the line segment connecting them, $\lambda X_1^$ + (1-\lambda) X_2^ for $0 \le \lambda \le 1$, is also an optimal solution.

PYQ Context*: Questions often state "The set of all optimal solutions for LPP does not need to be convex" (which is false) or "Every point on the line segment connecting two optimal solutions in an LPP is also an optimal solution" (which is true).

Existence of Optimal Solutions: Optimal solutions for an LPP do not always exist.

* An LPP can be infeasible (no solution satisfies all constraints, i.e., the feasible region is empty).
* An LPP can be unbounded (the objective function can be increased indefinitely for maximization problems, or decreased indefinitely for minimization problems, within the feasible region).
PYQ Context*: Questions like "Optimal solutions for LPP always exist" are false.

Extreme Points and Optimality: If an optimal solution exists for an LPP and the feasible region is bounded, at least one optimal solution will occur at an extreme point (vertex) of the feasible region.

PYQ Context*: Questions might relate to the number of extreme points for a given feasible region or the property that optimal solutions lie at extreme points.

Half-spaces: Each linear inequality constraint in an LPP defines a half-space. The feasible region is the intersection of these half-spaces and the non-negativity constraints.

PYQ Context*: Questions might ask whether a given point lies in a specific half-space defined by a hyperplane. To check, substitute the coordinates of the point into the inequality.

Convex/Concave Functions:

* A linear function $f(x) = \mathbf{c}^T \mathbf{x}$ is both convex and concave.
* A function like $f(x,y) = x^2+y^2-1$ is convex.
* A function like $f(x,y) = -x^2-y$ is concave.
* A function like $f(x,y) = xy-1$ is neither convex nor concave.
PYQ Context*: Questions often ask to classify functions as convex, concave, both, or neither. Recall the definitions or use the Hessian matrix test for twice-differentiable functions.

---

Foundations of Linear Programming - Part 5: Summary

Chapter Overview:

This chapter introduces the fundamental concepts underpinning Linear Programming Problems (LPPs). It defines what constitutes an LPP, emphasizing the critical role of linearity. Key mathematical concepts like convex sets, convex/concave functions, hyperplanes, and half-spaces are established as the building blocks for understanding the structure and properties of LPPs and their solutions. This summary consolidates these core ideas, highlighting their relevance for exam preparation.

Key Concepts:

Linear Programming Problem (LPP):

* An LPP involves optimizing (maximizing or minimizing) a linear objective function subject to a set of linear constraints (equalities or inequalities) and non-negativity restrictions on variables.
* General Form:







* Crucial Requirement: All functions (objective and constraints) must be strictly linear. Non-linear terms like $x_1^2$, $x_1x_2$, $|x_1|$ disqualify a problem from being an LPP.

Convex Sets:

* A set $S$ in $\mathbf{R}^n$ is convex if for any two points $x_1, x_2 \in S$, the entire line segment connecting $x_1$ and $x_2$ is also contained in $S$.
* Mathematical Definition: For any $x_1, x_2 \in S$ and any scalar $\lambda \in [0, 1]$, the point $\lambda x_1 + (1-\lambda) x_2$ must also be in $S$.
* Examples of Convex Sets:
* Half-spaces: $a^T x \le b$ or $a^T x \ge b$.
* Hyperplanes: $a^T x = b$.
* Polyhedra (intersections of half-spaces).
* Disks, ellipses, squares, triangles, parabolas of the form $y^2 \le kx$ (for $x \ge 0, y \ge 0$).
* Examples of Non-Convex Sets:
* Exterior of a disk/ellipse: $x^2 + y^2 \ge R^2$.
* Regions defined by $xy \le k$ (e.g., $xy \le 1$).
* Regions defined by $x^2 - y^2 \le k$.

Convex and Concave Functions:

* A function $f: S \to \mathbf{R}$ (where $S$ is a convex set) is convex if for any $x_1, x_2 \in S$ and $\lambda \in [0, 1]$:

* A function $f: S \to \mathbf{R}$ (where $S$ is a convex set) is concave if for any $x_1, x_2 \in S$ and $\lambda \in [0, 1]$:

* Properties:
* Linear functions ($f(x) = c^T x + d$) are both convex and concave.
* For a twice-differentiable function $f$:
* If its Hessian matrix $\nabla^2 f(x)$ is positive semi-definite for all $x \in S$, then $f$ is convex.
* If its Hessian matrix $\nabla^2 f(x)$ is negative semi-definite for all $x \in S$, then $f$ is concave.
* Examples:
* $f(x, y) = 2x + 3y$ (linear) is both convex and concave.
* $f(x, y) = x^2 + y^2 - 1$ is convex.
* $f(x, y) = -x^2 - y$ is concave.
* $f(x, y) = xy - 1$ is neither convex nor concave.

Feasible Region (Feasible Solution Set):

* The set of all points that satisfy all the constraints of an LPP is called the feasible region or feasible solution set.
* Key Property: The feasible region of an LPP is always a convex set. Specifically, it is a convex polyhedron (the intersection of a finite number of half-spaces).
* If the feasible region is empty, the LPP is said to be infeasible.

Optimal Solutions:

* An optimal solution is a feasible solution that optimizes (maximizes or minimizes) the objective function.
* Properties:
* The set of all optimal solutions (if it exists) for an LPP is always a convex set.
* If an LPP has multiple optimal solutions, then any point on the line segment connecting any two optimal solutions is also an optimal solution.
* Optimal solutions do not always exist:
* An LPP can be infeasible (empty feasible region).
* An LPP can be unbounded (objective function can be improved indefinitely over the feasible region).
* An LPP does not necessarily have a unique optimal solution; it can have infinitely many optimal solutions (e.g., along an edge of the feasible region).

Extreme Points (Vertices):

* An extreme point (or vertex) of a convex set is a point that cannot be expressed as a convex combination of two other distinct points in the set.
* For a convex polyhedron (the feasible region of an LPP), the number of extreme points is finite.
* Fundamental Theorem of LPP: If an LPP has an optimal solution, then at least one optimal solution occurs at an extreme point of the feasible region.

Half-spaces and Hyperplanes:

* A hyperplane in $\mathbf{R}^n$ is a set of points $x$ satisfying $a^T x = b$, where $a \in \mathbf{R}^n, a \ne 0$, and $b \in \mathbf{R}$.
* A hyperplane divides $\mathbf{R}^n$ into two half-spaces: $a^T x \le b$ and $a^T x \ge b$.
* All constraints in an LPP define half-spaces, and their intersection forms the feasible region.
* To determine which half-space a point $P$ lies in relative to a hyperplane $a^T x = b$, substitute $P$'s coordinates into $a^T x$. If $a^T P < b$, it's in the 'less than' half-space; if $a^T P > b$, it's in the 'greater than' half-space.

Important Points/Tips for Exam Preparation:

* Master Convexity: Understand the definition of a convex set thoroughly and be able to identify convex vs. non-convex sets from equations or graphical representations. This is a frequently tested concept.
* Function Classification: Be able to classify functions as convex, concave, both, or neither, especially linear and simple quadratic forms. Remember linear functions are always both.
* LPP Characteristics: Clearly distinguish LPPs from non-LPPs based on the linearity of objective and constraints.
* Properties of Feasible and Optimal Sets: Remember that both the feasible region and the set of optimal solutions (if non-empty) are always convex sets.
* Existence and Uniqueness of Solutions: Understand that optimal solutions are not guaranteed to exist (infeasible or unbounded LPPs) and are not necessarily unique.
* Extreme Points: Recognize the significance of extreme points in LPP theory – optimal solutions, if they exist, are found at these points. Be able to count extreme points for simple polyhedral sets.
* Half-space Evaluation: Practice checking if a given point lies in a specific half-space.
* PYQ Analysis: Pay close attention to the types of questions asked in PYQs, especially those related to definitions, properties, and identification of convex sets/functions.