Introduction to Linear Programming

---

Optimization problems: Problems which seek to maximize or minimize a numerical function of a number of variables (or functions), with the variables (functions) subject to certain constraints, form a general class of problems which may be called Optimization Problems.
However, we shall be concerned with a special but very important class of programming problems known as Linear Programming Problems, theory of linear programming with numerical techniques for solving such problems.

Programming Problems: Problems that deal with determining optimal allocations of limited resources to meet given objectives (resources could be men, materials, machinery, etc.). There may be, however, certain restrictions, for example, on the total amount of each resource available, on quantity of each product made, on quality of each product. Even within these restrictions, there will exist many feasible allocations. But of all permissible allocations of resources, it is desired to find the one which maximizes or minimizes some numerical quantity, such as profit or cost.

• Linear programming deals with that class of programming problems for which all relations among the variables are linear.

• The relations must be linear both in constraints and in the function to be optimized.

Before formally defining a linear programming problem, we define the concepts of linear function and linear inequality.

• A function $f(x_1,x_2,\dots,x_n)$ of $x_1,x_2,\dots,x_n$ is a linear function if and only if for some set of constants $c_1,c_2,\dots,c_n$, $f(x_1,x_2,\dots,x_n)$ = $c_1x_1+c_2x_2+\dots+c_nx_n$
  For example, $f(x_1,x_2)$ = $2x_1+x_2$ is a linear function of $x_1$ and $x_2$ but $f(x_1,x_2)$ = $x^2_1x_2$ is not a linear function of $x_1$ and $x_2$.
• For any linear function $f(x_1,x_2,\dots,x_n)$ and any number b, the inequalities $f(x_1,x_2,\dots,x_n) \leq b$ and $f(x_1,x_2,\dots,x_n) \geq b$ are linear inequalities.
  Thus $2x_1+3x_2 \leq 3$ and $2x_1+x_2 \geq 3$ are linear inequalities but $x^2_1x_2 \geq 3$ is not a linear inequality.

Linear Programming

A General Linear Programming Problem can be described as follows:

Given a set of m linear inequalities or equations in r variables, we wish to find non-negative values of these variables which will satisfy the constraints and maximize or minimize some linear function of the variables.

Mathematically, this means we have m inequalities or equations in r variables (m can be greater than, less than or equal to r) of the form:

$$\begin{aligned}a_{i1}x_1+a_{i2}x_2+\dots+a_{ir}x_r (\leq,=,\geq) b_i, i = 1(1)m \end{aligned}$$ __(3)

where for each constraint one and only one of the signs $\leq, =, \geq$ holds, but the sign may vary from one constraint to another. We seek values of the variables $x_j$ satisfying equation 1 and $x_j \geq 0, j = 1(1)r$ __(2)

which maximize or minimize a linear function

$$\begin{aligned}Z=c_1x_1+c_2x_2+\dots+c_rx_r \end{aligned}$$ ___(3)

The $a_{ij}, b_i, c_j$ are assumed to be known constants. We have thus formulated the General LPP which can be represented by equation (1), (2) and (3).

• Linearity implies that products of the variables such as $x_1x_2$, power of variables such as $x^2_3$ and combination of variables such as $a_1x_1+a_2log x_2$ cannot be allowed.
• One important restriction that is inherent in a LPP is: It is assumed that the variables $x_j$ can take on any values allowed by the restrictions (1) and (2); in other words, we cannot require that the variables assume only integral values.
• If additional restriction is imposed that the variables must be integers then in general we do not have any longer a LPP.
• The answers must be rounded off to the nearest integers which satisfy the constraints if situation requires.
• The function to be optimised, i.e., equation (3) is called the objective function.
• Mathematically, the constraints (2) which require that the variables $x_j$ be non-negative do not differ from the constraints (1). However, while solving a LPP, the non-negativity constraints are handled differently from other constraints. For this reason, we shall refer to the non-negativity constraints as non-negativity restrictions while the term constraint will be used to denote constraints other than non-negativity restrictions.
• Thus, when we say that there are m constraints on the problem, we mean that there are m constraints of the form (1). In addition, there are non-negativity restrictions.
• Any set of $x_j$ which satisfies the constraints (1) will be called a solution to LPP.
• Any solution which satisfies the non-negativity restrictions is called a Feasible Solution.
• Any Feasible solution which optimizes the objective function is called an Optimal Feasible Solution.
• The task of solving a LPP consists in finding an optimal feasible solution.
• There can be an infinite number of feasible solutions to a LPP. Out of these solutions, we must find one which optimizes the objective function.

Standard Form of a Linear Programming Problem

A linear programming problem in its standard form can be written as:

$$\text{Maximize } \quad Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$$

Subject to:

$$\begin{aligned} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &\leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &\leq b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &\leq b_m \\ x_1, x_2, \dots, x_n &\geq 0 \end{aligned}$$

Where:

• $Z$ is the objective function to be maximized (or minimized).
• $x_1, x_2, \dots, x_n$ are the decision variables.
• $c_1, c_2, \dots, c_n$ are the coefficients of the objective function.
• $a_{ij}$ are the coefficients of the constraints.
• $b_1, b_2, \dots, b_m$ are the right-hand side constants of the constraints.

Key Characteristics

• Linear Objective Function: The function to be optimized is linear.
• Linear Constraints: All constraints are linear equations or inequalities.
• Decision Variables: The variables whose values are under our control and influence the performance of the system are called decision variables.
• Non-Negativity Restriction: Decision variables are usually required to be non-negative.

Assumptions on LPP

There are several assumptions on which the linear programming works, these are:

1. Proportionality:
   The basic assumption underlying the linear programming is that any change in the constraint inequalities will have the proportional change in the objective function. This means, if product contributes Rs. 20 towards the profit, then the total contribution would be equal to $20x_1$, where $x_1$ is the number of units of the product.
   For example, if there are 5 units of the product, then the contribution would be Rs 100 and in the case of 10 units, it would be Rs 200. Thus, if the output (sales) is doubled, the profit would also be doubled.

2. Additivity:
   The assumption of additivity asserts that the total profit of the objective function is determined by the sum of profit contributed by each product separately.
   Similarly, the total amount of resources used is determined by the sum of resources used by each product separately.
   This implies, there is no interaction between the decision variables.

3. Continuity/Divisibility:
   Another assumption of linear programming is that the decision variables are continuous. This means a combination of outputs can be used with the fractional values along with the integer values.

4. Certainty:
   Another underlying assumption of linear programming is a certainty, i.e. the parameters of objective function coefficients and the coefficients of constraint inequalities is known with certainty. Such as profit per unit of product, availability of material and labor per unit, requirement of material and labor per unit are known and is given in the linear programming problem.

5. Finite Choices:
   An optimal solution cannot be computed in the situation where there is infinite number of alternative activities and resources restriction. This assumption implies that the decision maker has certain choices, and the decision variables assume non-negative values.

Solution Methods

Common methods for solving linear programming problems include:

graph TD
    A[Linear Programming] --> B{Feasible Region}
    B -->|Bounded| C[Optimal Solution]
    B -->|Unbounded| D[Infinite Solutions]
    C --> E[Simplex Method]
    D --> F[Check Constraints]

• Graphical Method (for two-variable problems)
• Simplex Method
• Interior Point Method

Linear programming helps in making optimal decisions within given constraints, making it an essential tool in decision-making and resource allocation.