Linear Programming and Optimization

[a] Hyperplane, convex set and convexity of 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$, $a\neq 0$, and $b\in \mathbb{R}$. It is an affine set of dimension $n-1$.

Convex set. A set $S\subseteq \mathbb{R}^n$ is called convex if for every $x,y\in S$ and every $\lambda\in[0,1]$,

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

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

---

LP feasible set is convex. Consider a general LP in the form

$$\begin{aligned} \text{Maximize } & c^T x\\ \text{subject to } & a_i^T x \le b_i,\quad i=1,2,\dots,m,\\ & x\ge 0. \end{aligned}$$

The feasible set is

$$F=\{x\in \mathbb{R}^n : a_i^T x\le b_i,\ i=1,\dots,m,\ x\ge 0\}.$$

For each inequality $a_i^T x\le b_i$, define the halfspace

$$H_i=\{x\in \mathbb{R}^n : a_i^T x\le b_i\}.$$

We show $H_i$ is convex. Let $x,y\in H_i$ and $\lambda\in[0,1]$. Then

$$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.$$

Hence $\lambda x+(1-\lambda)y\in H_i$, so $H_i$ is convex.

Similarly, each nonnegativity condition $x_j\ge 0$ defines a halfspace and is convex. Therefore the feasible set $F$ is the intersection of finitely many convex sets:

$$F=\left(\bigcap_{i=1}^m H_i\right)\cap \{x:x\ge 0\}.$$

The intersection of convex sets is convex. Hence the set of all feasible solutions of an LP problem is a convex set.
If the LP has equality constraints $Ax=b$, then each equality is a hyperplane, which is also convex, so the same conclusion holds.

---

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

Let $P,Q\subseteq \mathbb{R}^n$ be convex sets and let $\alpha,\beta\in\mathbb{R}$. 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 there exist $p_1,p_2\in P$ and $q_1,q_2\in Q$ such that

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

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

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

Since $P$ is convex,

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

Since $Q$ is convex,

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

Therefore

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

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

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

$$P-Q=P+(-1)Q=\{p-q : p\in P,\ q\in Q\}.$$

By the result just proved, $P-Q$ is a convex set. Hence $P-Q$ is convex.

(a) Given: Max $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$.

Standard form (all constraints are equations, all variables non-negative): subtract a surplus variable $s_1$ from the $\ge$ constraint and add a slack variable $s_2$ to the $\le$ constraint.

$\text{Max } Z = 12x_1 + 5x_2 + 0s_1 + 0s_2$ $6x_1 + 3x_2 - s_1 = 5,\qquad 7x_1 + 2x_2 + s_2 = 14,\qquad x_1,x_2,s_1,s_2 \ge 0$

Canonical form (for a maximization problem every constraint is of the $\le$ type, variables $\ge 0$): multiply the $\ge$ constraint by $-1$.

$\text{Max } Z = 12x_1 + 5x_2$ $-6x_1 - 3x_2 \le -5,\qquad 7x_1 + 2x_2 \le 14,\qquad x_1,x_2 \ge 0$

Minimization form: since $\text{Max } Z = -\text{Min}(-Z)$, put $Z' = -Z$:

$\text{Min } Z' = -12x_1 - 5x_2$ subject to the same constraints, $6x_1+3x_2 \ge 5$, $7x_1+2x_2 \le 14$, $x_1,x_2\ge 0$. (In its own canonical form, a minimization problem has all constraints of the $\ge$ type, so the second constraint becomes $-7x_1-2x_2 \ge -14$.) The optimal $x_1,x_2$ are the same, and $Z_{\max} = -Z'_{\min}$.

(b) The three forms are the general form (constraints $\le,\ge,=$ mixed; variables may be unrestricted), the canonical form (all constraints $\le$ for Max, or all $\ge$ for Min; variables $\ge 0$) and the standard form (all constraints equations; variables $\ge 0$). They are equivalent because any one can be converted into another without changing the set of optimal solutions:

1. Max to Min: $\text{Max } Z = \sum c_jx_j \iff \text{Min } (-Z)$, with $Z_{\max} = -Z'_{\min}$ at the same solution.
2. Inequality direction: $\sum a_{ij}x_j \ge b_i \iff -\sum a_{ij}x_j \le -b_i$.
3. Equation to inequalities: $\sum a_{ij}x_j = b_i \iff \sum a_{ij}x_j \le b_i$ and $\sum a_{ij}x_j \ge b_i$ (so the general form becomes canonical).
4. Inequality to equation: $\sum a_{ij}x_j \le b_i \iff \sum a_{ij}x_j + s_i = b_i,\ s_i\ge 0$ (slack); $\sum a_{ij}x_j \ge b_i \iff \sum a_{ij}x_j - s_i = b_i,\ s_i\ge 0$ (surplus). Slack and surplus variables carry zero cost, so $Z$ is unchanged and any feasible $x$ gives a feasible $(x,s)$ and conversely (so canonical becomes standard).
5. Unrestricted variable: if $x_j$ is unrestricted in sign, write $x_j = x_j' - x_j''$ with $x_j',x_j''\ge 0$ (so the general form's variables become non-negative).
6. Variable with $x_j \le 0$: substitute $x_j = -x_j'$, $x_j' \ge 0$.

Since each step maps feasible solutions one-to-one onto feasible solutions with the same objective value, the general, canonical and standard forms of an LP problem have the same optimal solution, so the three forms are equivalent.

(a) For a system $AX=b$ 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. A basic feasible solution (BFS) is a basic solution in which all variables are non-negative ($X\ge 0$); it corresponds to a corner (extreme) point of the feasible region.

A BFS is non-degenerate if all $m$ basic variables are strictly positive, and degenerate if at least one basic variable is zero.

(b) Steps of the simplex method

1. Formulate the problem and convert it to standard form: make the objective Max, make all RHS $b_i\ge 0$, add slack variables for $\le$ constraints, subtract surplus variables and add artificial variables for $\ge$ constraints, add artificial variables for $=$ constraints.
2. Find an initial BFS (slack/artificial variables form the starting basis) and write the initial simplex table with $C_j$, $C_B$, $X_B$ and the body matrix.
3. Compute $Z_j=\sum C_B a_{ij}$ and the net evaluations $C_j - Z_j$ for every column.
4. Optimality test: if all $C_j - Z_j \le 0$ (Max problem), the current solution is optimal; stop. Otherwise go on.
5. Entering variable: choose the column with the largest positive $C_j-Z_j$ (key column).
6. Leaving variable: compute the ratio $\theta = X_B/(\text{key column entry})$ for positive entries only; the row with the minimum ratio is the key row. If no entry is positive, the problem is unbounded.
7. The element at the intersection is the pivot. Divide the key row by the pivot, and make the other entries of the key column zero by row operations to obtain the new table.
8. Repeat steps 3 to 7 until all $C_j-Z_j\le 0$. The optimal values are the $X_B$ column and $Z=\sum C_BX_B$.

OR (Two-phase method)

Max $Z=10x_1+8x_2$ s.t. $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: Min $w=a_1$ (i.e. Max $-a_1$). Starting basis $(s_1,a_1)$.

$x_1$ enters and $a_1$ leaves. New row: $x_1 + \tfrac12x_2 - \tfrac12s_2 = 4$ and $s_1$ row: $\tfrac12x_2+s_1+\tfrac12s_2=2$. Now $w=0$ and no artificial variable remains in the basis, so a feasible solution exists. Drop the $a_1$ column.

Phase II: original objective, basis $(s_1,x_1)$.

$s_2$ enters, $s_1$ leaves. After the pivot:

All $C_j-Z_j\le 0$, so the solution is optimal:

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

(Check: corner points $(4,0),(6,0),(2,4)$ give $Z=40,60,52$.)

(a) The primal is a minimization problem with $x_1,x_2,x_3\ge 0$. Write $x_3$ with zero cost in the objective and bring all constraints to the same $\ge$ form, one dual variable per constraint:

• Constraint 1 ($\ge$): $x_1+x_2\ge 2$, dual variable $y_1\ge 0$.
• Constraint 2 ($\le$): multiply by $-1$ to get $-2x_1-x_2-6x_3\ge -6$, so the dual variable is $y_2'\ge 0$; with $y_2=-y_2'$ this is a variable $y_2\le 0$ for the original $\le$ constraint.
• Constraint 3 ($=$): $y_3$ unrestricted in sign.

Primal: Min $Z = 2x_1+5x_2+0x_3$.

Dual:

$\text{Max } W = 2y_1 + 6y_2 + 4y_3$ subject to $y_1 + 2y_2 + y_3 \le 2 \quad (x_1)$ $y_1 + y_2 - y_3 \le 5 \quad (x_2)$ $6y_2 + 3y_3 \le 0 \quad (x_3)$ $y_1\ge 0,\quad y_2\le 0,\quad y_3 \text{ unrestricted in sign}$

(Equivalently, with $y_2'=-y_2\ge 0$: Max $W=2y_1-6y_2'+4y_3$ with the corresponding signs changed.)

(b) Let the primal be Min $Z=cx$ with a set of constraints, of which the $i$-th is an equality:

$\sum_j a_{ij}x_j = b_i$

An equality is equivalent to two inequalities:

$\sum_j a_{ij}x_j \ge b_i \qquad\text{and}\qquad -\sum_j a_{ij}x_j \ge -b_i$

(the second is the $\le$ constraint multiplied by $-1$, so that all constraints are of the $\ge$ type). Assign the dual variables $y_i'\ge 0$ to the first and $y_i''\ge 0$ to the second. In the dual, the column of the $i$-th constraint contributes

$a_{ij}y_i' + (-a_{ij})y_i'' = a_{ij}(y_i'-y_i'')$

to the $j$-th dual constraint, and $b_iy_i'+(-b_i)y_i'' = b_i(y_i'-y_i'')$ to the dual objective. So the dual depends on $y_i'$ and $y_i''$ only through their difference. Define

$y_i = y_i' - y_i''$

Since $y_i'$ and $y_i''$ are both non-negative, their difference can be positive, negative or zero, so $y_i$ takes any real value. Replacing the pair by the single variable $y_i$ gives a dual with the $i$-th variable unrestricted in sign. Hence if the $i$-th primal constraint is an equality, the $i$-th dual variable is unrestricted in sign. $\blacksquare$

[a] LP Model for a Transportation Problem

Statement of the problem. A commodity is to be shipped from $m$ sources (supply points) to $n$ destinations (demand points). Source $i$ has a supply of $a_i$ units, destination $j$ requires $b_j$ units, and the cost of shipping one unit from source $i$ to destination $j$ is $c_{ij}$. The aim is to decide the shipment quantities so that total transportation cost is minimum.

Decision variables. Let

$x_{ij} = \text{number of units shipped from source } i \text{ to destination } j, \qquad i = 1,2,\dots,m; \; j = 1,2,\dots,n$

with $x_{ij} \ge 0$ for all $i,j$.

Objective function. Minimize total transportation cost:

$\text{Minimize } Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}\, x_{ij}$

Constraints.

1. Supply (capacity) constraints — the total shipped out of each source cannot exceed its supply:

$\sum_{j=1}^{n} x_{ij} \le a_i, \qquad i = 1,2,\dots,m$

2. Demand (requirement) constraints — each destination must receive at least its requirement:

$\sum_{i=1}^{m} x_{ij} \ge b_j, \qquad j = 1,2,\dots,n$

3. Non-negativity constraints: $x_{ij} \ge 0$ for all $i,j$.

Balanced case. If total supply equals total demand, $\sum_i a_i = \sum_j b_j$, the problem is balanced and the inequalities become equalities:

$\sum_{j=1}^{n} x_{ij} = a_i, \qquad \sum_{i=1}^{m} x_{ij} = b_j$

If supply exceeds demand, a dummy destination is added with demand $\sum_i a_i - \sum_j b_j$ and zero cost; if demand exceeds supply, a dummy source is added similarly. This makes the model balanced and feasible.

Real-life application. A cement company in Nepal (for example, Hetauda Cement) has plants at Hetauda and Bhairahawa and depots at Kathmandu, Pokhara, Biratnagar and Nepalgunj. Given the production capacity of each plant, the demand at each depot and the per-bag freight rate on each route, the LP model above determines how many bags to send on each route so that total freight cost is minimum. The same model is used for distributing petroleum products from depots, fertilizers from warehouses to districts, and goods from factories to retail outlets.

---

[b] LP Model for a Diet Problem

Statement of the problem. A person must choose quantities of $n$ available foods so that the diet supplies at least the required amounts of $m$ nutrients at minimum cost. Food $j$ costs $c_j$ per unit and contains $a_{ij}$ units of nutrient $i$ per unit of food. The minimum daily requirement of nutrient $i$ is $b_i$.

Decision variables. Let

$x_j = \text{quantity of food } j \text{ included in the diet}, \qquad j = 1,2,\dots,n$

with $x_j \ge 0$ for all $j$.

Objective function. Minimize the total cost of the diet:

$\text{Minimize } Z = \sum_{j=1}^{n} c_j x_j$

Constraints.

1. Nutritional requirement constraints — the diet must supply at least the required amount of each nutrient:

$\sum_{j=1}^{n} a_{ij} x_j \ge b_i, \qquad i = 1,2,\dots,m$

2. Non-negativity constraints: $x_j \ge 0$ for all $j$.

Remarks. If a food can be taken only in limited quantity (taste, availability), upper bounds $x_j \le u_j$ are added. If the requirement is an exact amount, the constraint becomes an equality. The model is a minimization LP with "greater than or equal to" constraints, so it is solved by the simplex method after adding surplus and artificial variables (Big-M or two-phase method).

Real-life application. Hospital and hostel messes, army and police canteens, and school feeding programmes use this model to prepare a daily menu that meets calorie, protein, fat, vitamin and mineral requirements at the lowest possible cost. In Nepal, the Mid-Day Meal programme and Nepal Food Corporation ration planning are typical examples. It is also used in planning cattle and poultry feed mixtures and in blending problems in industry.

---

OR — LP Model for the Maximum Flow Problem

Statement of the problem. A directed network has nodes $1,2,\dots,N$ with node 1 as the source and node $N$ as the sink. Each arc $(i,j)$ has capacity $u_{ij} \ge 0$. The aim is to send the maximum possible amount of flow from source to sink without exceeding any arc capacity, and with flow conserved at every intermediate node.

Decision variables. Let

$x_{ij} = \text{amount of flow on arc } (i,j), \qquad x_{ij} \ge 0$

Objective function. Maximize the total flow leaving the source:

$\text{Maximize } Z = \sum_{j} x_{1j}$

Constraints.

1. Capacity constraints: $x_{ij} \le u_{ij}$ for every arc $(i,j)$.
2. Flow conservation at intermediate nodes $k = 2,3,\dots,N-1$:

$\sum_{i} x_{ik} - \sum_{j} x_{kj} = 0$

3. Non-negativity: $x_{ij} \ge 0$ for all arcs.

Why the model is linear. Every term in the objective function and in every constraint is of the form $1 \cdot x_{ij}$ — each variable appears with power one and is multiplied only by a constant (capacity $u_{ij}$ or coefficient 1). There are no products or powers of variables, no variables in denominators, and no other non-linear terms. Hence both the objective function and the constraint set are linear functions of the decision variables, so the model is a linear programming problem. Moreover, the flow conservation equations are linear "balance" equations, exactly of the LP form $Ax = b$.

Applications.

1. Communication and computer networks. The model finds the maximum data rate that can be sent from a server to a client through routers and links of limited bandwidth, and identifies the bottleneck links.
2. Transportation and pipeline systems. It determines the maximum volume of water, gas or petroleum that can be pumped from a supply point to a demand point through a pipeline network of fixed pipe capacities; similarly, it gives the maximum number of vehicles or goods that a road network can carry between two cities.