Linear Programming

[a] Hyperplane, Convex Set, and Convexity of the LP Feasible Region

Hyperplane

A hyperplane in $\mathbb{R}^n$ is a set of the form

$$H=\{x\in\mathbb{R}^n : a^T x=b\},$$

where $a\in\mathbb{R}^n$ is a nonzero vector and $b\in\mathbb{R}$ is a scalar.
Geometrically, a hyperplane is an $(n-1)$-dimensional flat surface. For example, in $\mathbb{R}^2$ a hyperplane is a straight line, and in $\mathbb{R}^3$ it is a plane.

Convex Set

A set $S\subseteq\mathbb{R}^n$ is called a convex set if for every pair of points $x,y\in S$ and every scalar $\lambda$ with $0\le \lambda\le 1$,

$$\lambda x+(1-\lambda)y\in S.$$

That is, the line segment joining any two points of $S$ lies completely inside $S$.

---

Feasible Set of an LP is Convex

Consider a linear programming problem in the form

$$\begin{aligned} \text{Maximize } & z=c^T x\\ \text{subject to } & Ax\le b,\\ & x\ge 0. \end{aligned}$$

Its feasible set is

$$F=\{x\in\mathbb{R}^n : Ax\le b,\ x\ge 0\}.$$

Let $x,y\in F$ and let $\lambda\in[0,1]$. For each constraint row $i$,

$$a_i^T x\le b_i,\qquad a_i^T y\le b_i.$$

Then

$$\begin{aligned} a_i^T(\lambda x+(1-\lambda)y) &=\lambda a_i^T x+(1-\lambda)a_i^T y\\ &\le \lambda b_i+(1-\lambda)b_i\\ &=b_i. \end{aligned}$$

Also, since $x_j\ge 0$ and $y_j\ge 0$,

$$\lambda x_j+(1-\lambda)y_j\ge 0.$$

Hence $\lambda x+(1-\lambda)y$ satisfies all constraints, so

$$\lambda x+(1-\lambda)y\in F.$$

Therefore the feasible set $F$ is convex.

Equivalently, each inequality $a_i^T x\le b_i$ defines a closed half-space, and each nonnegativity condition $x_j\ge 0$ also defines a half-space. Since every half-space is convex and the intersection of convex sets is convex, the feasible region of an LP is convex. If the LP has equality constraints $Ax=b$, then for $x,y\in F$,

$$A(\lambda x+(1-\lambda)y)=\lambda b+(1-\lambda)b=b,$$

so the same conclusion holds.

---

[b] Convexity of $\alpha P+\beta Q$ and $P-Q$

Let $P,Q\subseteq\mathbb{R}^n$ be convex sets, and let $\alpha,\beta$ be any scalars. Define

$$\alpha P+\beta Q=\{\alpha p+\beta q : p\in P,\ q\in Q\}.$$

Take any two points $u,v\in \alpha P+\beta Q$. Then for some $p_1,p_2\in P$ and $q_1,q_2\in Q$,

$$u=\alpha p_1+\beta q_1,\qquad v=\alpha p_2+\beta q_2.$$

Let $\lambda\in[0,1]$. Then

$$\begin{aligned} \lambda u+(1-\lambda)v &=\lambda(\alpha p_1+\beta q_1)+(1-\lambda)(\alpha p_2+\beta q_2)\\ &=\alpha\bigl(\lambda p_1+(1-\lambda)p_2\bigr) +\beta\bigl(\lambda q_1+(1-\lambda)q_2\bigr). \end{aligned}$$

Since $P$ is convex,

$$p=\lambda p_1+(1-\lambda)p_2\in P.$$

Since $Q$ is convex,

$$q=\lambda q_1+(1-\lambda)q_2\in Q.$$

Thus

$$\lambda u+(1-\lambda)v=\alpha p+\beta q\in \alpha P+\beta Q.$$

Hence $\alpha P+\beta Q$ is a convex set.

Now take $\alpha=1$ and $\beta=-1$. Then

$$\alpha P+\beta Q=1P+(-1)Q=P-Q.$$

Since $P$ and $Q$ are convex, by the result just proved, $P-Q$ is also convex. Therefore,

$$\boxed{P-Q \text{ is a convex set.}}$$

[a] Rewriting the LP problem

Given LP problem:

Maximize $Z = 12x_1 + 5x_2$

Subject to: $6x_1 + 3x_2 \ge 5$ $7x_1 + 2x_2 \le 14$ $x_1, x_2 \ge 0$

1. Standard form

Introduce surplus and slack variables: $6x_1 + 3x_2 - S_1 = 5, \quad S_1 \ge 0$ $7x_1 + 2x_2 + S_2 = 14, \quad S_2 \ge 0$

Standard form:

Maximize $Z = 12x_1 + 5x_2 + 0S_1 + 0S_2$

Subject to: $6x_1 + 3x_2 - S_1 = 5$ $7x_1 + 2x_2 + S_2 = 14$ $x_1, x_2, S_1, S_2 \ge 0$

2. Canonical form

The canonical form requires each constraint equation to contain a basic variable (coefficient $+1$, appearing in no other equation) and non-negative RHS. The second equation already has basic variable $S_2$. The first equation has $-S_1$, so an artificial variable $A_1 \ge 0$ is introduced:

$6x_1 + 3x_2 - S_1 + A_1 = 5$ $7x_1 + 2x_2 + S_2 = 14$

Canonical form:

Maximize $Z^* = 12x_1 + 5x_2 + 0S_1 + 0S_2 - M A_1$ (Big-M method)

Subject to: $6x_1 + 3x_2 - S_1 + A_1 = 5$ $7x_1 + 2x_2 + S_2 = 14$ $x_1, x_2, S_1, S_2, A_1 \ge 0$

3. Conversion into minimization problem

Minimize $Z' = -Z = -12x_1 - 5x_2$

Subject to the same constraints: $6x_1 + 3x_2 - S_1 + A_1 = 5$ $7x_1 + 2x_2 + S_2 = 14$ $x_1, x_2, S_1, S_2, A_1 \ge 0$

with $\min Z' = -\max Z$.

---

[b] Equivalence of the three forms of LP problem

The three forms are:

1. General form — objective may be max or min; constraints may be $\le$, $\ge$, or $=$; variables non-negative.
2. Standard form — objective is maximization; all constraints are equations; all variables non-negative; RHS constants non-negative.
3. Canonical form — objective is maximization; all constraints are equations; all variables non-negative; RHS constants non-negative; each equation has a basic variable with coefficient $+1$ appearing in no other equation.

Equivalence proof:

(i) General → Standard form

• Replace $\min Z$ by $\max(-Z)$; then $\min Z = -\max(-Z)$.
• For $\le$ constraint, add slack variable; for $\ge$ constraint, subtract surplus variable.
• If RHS is negative, multiply the equation by $-1$ (reversing the inequality sign first).
• If a variable is unrestricted, write $x = x' - x''$ with $x', x'' \ge 0$.

These operations do not change the feasible region in terms of original variables, nor the objective value at any feasible point.

(ii) Standard → Canonical form

If a standard-form equation lacks a basic variable (e.g., it contains a surplus variable with coefficient $-1$), an artificial variable is added to serve as the initial basic variable. Using the Big-M or two-phase method, the artificial variable is forced to zero at optimum. Hence the optimal solution of the canonical form coincides with that of the standard form.

(iii) Canonical → General form

Dropping the slack, surplus, and artificial variables and rewriting each equation as an inequality recovers the general form. Since these added variables have zero coefficients in the objective (or are driven to zero), the optimal objective value is unchanged.

Conclusion

Each transformation preserves the feasible region (in terms of the original decision variables) and the objective value at every feasible point. Therefore the optimal solution of one form is also optimal for the other forms, and the three forms are equivalent.

(a) Basic feasible solution

For a system of $m$ equations in $n$ variables ($n > m$), a basic solution is obtained by setting $n-m$ variables (non-basic) to zero and solving for the remaining $m$ (basic) variables. If all basic variables are also $\ge 0$, it is a basic feasible solution (BFS); it corresponds to a corner point of the feasible region.

A BFS is non-degenerate if all $m$ basic variables are strictly positive. It is degenerate if at least one basic variable is zero (in the simplex table, a tie in the minimum-ratio test produces this).

(b) Steps of the simplex method

1. Formulate the problem; convert to maximization and make all RHS values non-negative.
2. Convert inequalities to equations by adding slack variables ($\le$), subtracting surplus variables ($\ge$) and adding artificial variables where there is no starting basic variable ($\ge$ or $=$).
3. Find an initial BFS (slack variables as the basis) and construct the initial simplex table with $c_j$, $z_j$ and $c_j - z_j$ rows.
4. Optimality test: if all $c_j - z_j \le 0$ (for maximization), the solution is optimal; stop.
5. Otherwise, choose the entering variable: the column with the largest positive $c_j - z_j$ (key column).
6. Choose the leaving variable: the minimum non-negative ratio $\dfrac{\text{RHS}}{\text{key column entry}}$ (only for positive entries); this gives the key row. If no entry is positive, the solution is unbounded.
7. Divide the key row by the key element to get the new pivot row; make the other entries of the key column zero by row operations.
8. Recompute $z_j$ and $c_j - z_j$, and repeat from step 4 until optimal.

OR: Two-phase solution

Max $Z = 10x_1 + 8x_2$ subject to $x_1 + x_2 \le 6$, $2x_1 + x_2 \ge 8$, $x_1, x_2 \ge 0$.

Standard form: $x_1 + x_2 + s_1 = 6$, $2x_1 + x_2 - s_2 + A_1 = 8$.

Phase I: Minimize $A_1$ (equivalently maximize $-A_1$). Starting basis $(s_1, A_1)$.

$x_1$ enters, $A_1$ leaves. After the iteration:

All $c_j - z_j \le 0$ for the Phase I objective and $A_1 = 0$, so a feasible solution exists. Drop $A_1$.

Phase II: Use the original objective $c = (10, 8, 0, 0)$. Initial table, basis $(s_1, x_1)$:

$s_2$ enters, $s_1$ leaves (multiply the $s_1$ row by 2, then add half of it to the $x_1$ row):

All $c_j - z_j \le 0$, so the solution is optimal:

$x_1 = 6,\quad x_2 = 0,\quad Z_{\max} = 10(6) + 8(0) = 60.$

[a] Dual of the given LP

The primal is

$$\begin{aligned} \text{Min } Z &= 2x_1+5x_2+0x_3\\ \text{s.t. } & x_1+x_2 \ge 2\\ & 2x_1+x_2+6x_3 \le 6\\ & x_1-x_2+3x_3 = 4\\ & x_1,x_2,x_3 \ge 0 \end{aligned}$$

Let the dual variables be $y_1,y_2,y_3$ corresponding to the three constraints.

Rules used:

• Primal is minimization, so dual is maximization.
• Primal $\ge$ constraint gives dual variable $y_1 \ge 0$.
• Primal $\le$ constraint gives dual variable $y_2 \le 0$.
• Primal equality constraint gives dual variable $y_3$ unrestricted.
• Primal variables $x_1,x_2,x_3 \ge 0$ give dual constraints of type $\le$.

Hence the dual is

$$\boxed{ \begin{aligned} \text{Max } W &= 2y_1+6y_2+4y_3\\ \text{s.t. } & y_1+2y_2+y_3 \le 2\\ & y_1+y_2-y_3 \le 5\\ & 6y_2+3y_3 \le 0\\ & y_1 \ge 0,\quad y_2 \le 0,\quad y_3 \text{ unrestricted} \end{aligned} }$$

If the intended objective was $Z=2x_1+5x_2+6x_3$, then the third dual constraint becomes

$$6y_2+3y_3 \le 6.$$

---

[b] Proof: Equality constraint gives unrestricted dual variable

Consider the $i$-th primal constraint as an equality:

$$a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n=b_i.$$

This equality can be written as two inequalities:

$$a_{i1}x_1+\cdots+a_{in}x_n \ge b_i$$

and

$$a_{i1}x_1+\cdots+a_{in}x_n \le b_i.$$

Let the dual variable for the $\ge$ part be $y_i^+ \ge 0$, and for the $\le$ part be $y_i^- \le 0$.

In the dual objective, these two constraints contribute

$$b_i y_i^+ + b_i y_i^- = b_i(y_i^+ + y_i^-).$$

In each dual constraint, they contribute

$$a_{ij}y_i^+ + a_{ij}y_i^- = a_{ij}(y_i^+ + y_i^-).$$

Now define

$$y_i = y_i^+ + y_i^-.$$

Since $y_i^+ \ge 0$ and $y_i^- \le 0$, the value of $y_i$ may be positive, negative, or zero. Therefore $y_i$ has no sign restriction.

Conversely, any unrestricted $y_i$ can be split as

$$y_i^+ = \max(y_i,0), \qquad y_i^- = \min(y_i,0),$$

so the two inequality dual variables together are equivalent to one unrestricted dual variable.

Thus, the dual variable corresponding to an equality constraint of the primal is unrestricted in sign. $\blacksquare$

[a] LP Model for a Transportation Problem

Formulation

Let there be $m$ sources (supply points) and $n$ destinations (demand points).

Parameters:

• $a_i$ = amount available (supply) at source $i$, $i = 1, 2, \dots, m$
• $b_j$ = amount required (demand) at destination $j$, $j = 1, 2, \dots, n$
• $c_{ij}$ = cost of transporting one unit from source $i$ to destination $j$

Decision variables: $x_{ij} = \text{quantity transported from source } i \text{ to destination } j \quad (x_{ij} \ge 0)$

Objective function: Minimize total transportation cost $\text{Minimize } Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}\, x_{ij}$

Constraints:

Supply constraints (each source cannot ship more than it has): $\sum_{j=1}^{n} x_{ij} \le a_i \quad \text{for } i = 1, 2, \dots, m$

Demand constraints (each destination must receive what it needs): $\sum_{i=1}^{m} x_{ij} \ge b_j \quad \text{for } j = 1, 2, \dots, n$

Non-negativity: $x_{ij} \ge 0 \quad \text{for all } i, j$

For a balanced problem, $\sum a_i = \sum b_j$, and the supply and demand constraints become equalities.

Real-life Application

A brewery in Nepal has bottling plants in Kathmandu, Pokhara and Biratnagar, and must supply its product to warehouses in Chitwan, Butwal and Dharan. The company knows the production capacity of each plant, the demand of each warehouse and the per-truck transport cost on each route. The transportation model finds the shipping plan that meets all warehouse demands at minimum total cost.

---

[b] LP Model for a Diet Problem

Formulation

Let there be $n$ food items and $m$ nutrients.

Parameters:

• $c_j$ = cost per unit of food $j$
• $a_{ij}$ = amount of nutrient $i$ present in one unit of food $j$
• $b_i$ = minimum required amount of nutrient $i$

Decision variables: $x_j = \text{quantity of food } j \text{ to be included in the diet} \quad (x_j \ge 0)$

Objective function: Minimize the total cost of the diet $\text{Minimize } Z = \sum_{j=1}^{n} c_j x_j$

Constraints:

Nutrient requirements (each nutrient must reach its minimum level): $\sum_{j=1}^{n} a_{ij} x_j \ge b_i \quad \text{for } i = 1, 2, \dots, m$

Non-negativity: $x_j \ge 0 \quad \text{for } j = 1, 2, \dots, n$

Real-life Application

A hospital dietician must prepare a daily meal plan for patients from foods such as rice, lentils, milk, vegetables and eggs. Each food has a known price and a known content of calories, protein, calcium and iron. The diet model determines the cheapest combination of foods that still satisfies the patients' minimum daily nutritional requirements.

---

OR — LP Model for the Maximum Flow Problem

General LP Model

Let $G = (V, E)$ be a directed network with source $s$ and sink $t$. Each arc $(i, j) \in E$ has capacity $u_{ij}$.

Decision variables: $x_{ij} = \text{flow on arc } (i, j) \quad (x_{ij} \ge 0)$

Objective function: Maximize the total flow from source to sink $\text{Maximize } Z = \sum_{j:(s,j)\in E} x_{sj}$

Constraints:

Capacity constraints: $x_{ij} \le u_{ij} \quad \text{for every arc } (i, j) \in E$

Flow conservation at every intermediate node $k$ (flow in = flow out): $\sum_{i:(i,k)\in E} x_{ik} - \sum_{j:(k,j)\in E} x_{kj} = 0 \quad \text{for all } k \ne s, t$

Non-negativity: $x_{ij} \ge 0 \quad \text{for every arc } (i, j) \in E$

Why the Model is Linear

Every term in the objective function and in every constraint is of the form $x_{ij}$ multiplied by a constant (here, the constant is 1). No variable is raised to a power, no two variables are multiplied together, and no variable appears in a denominator. Hence both the objective function and all constraints are linear functions of the decision variables, so the model is a linear programming model.

Two Applications

1. Telecommunication networks: Determining the maximum volume of data (calls or internet traffic) that can be sent from one exchange to another through cables of limited capacity.
2. Water supply and pipeline systems: Finding the maximum quantity of water that can be delivered from a reservoir to a city through a network of pipes of fixed diameters.
3. Road and railway traffic: Computing the maximum number of vehicles per hour that can pass from one point of a city to another, used for traffic planning.