Mathematics

Linear programming

Algebraic formulation, objective function, constraints, feasible region, optimization by algebraic and graphical methods, transportation problems.

Linear programming is the algebraic formulation that aims to optimize (maximize or minimize) a linear function of several variables, called the objective function:

f(x,y)=ax+by+c

subject to constraints, formulated as linear inequalities:

\begin{cases} a_1 x + b_1 y \leq \geq c_1 \\ a_2 x + b_2 y \leq \geq c_2 \\ \quad \vdots \qquad \vdots \qquad \vdots \\ a_n x + b_n y \leq \geq c_n \end{cases}

The representation of the region that satisfies the inequalities is called the feasible region

Fundamental theorem of linear programming:
If there is a unique solution that optimizes the objective function, it is located at an extreme point (vertex) of the feasible region

Example: An industry produces cheese in 100 and 300 gram containers, with a profit per container of €0.50 and €1.40 respectively. Every day, 2400 kg of cheese is available for packaging, although no more than 15,000 small containers can be produced. In addition, the number of 100 g containers must be greater than or equal to the number of 300 g containers. Find the point of maximum profit.

1) We define the variables and the objective function:
x = number of 100 g containers (0.1 Kg)
y = number of 300 g containers (0.3 Kg)

Objective function:

B(x,y)=0.5x+1.4y

2) We organize the information in a data table

	Nº containers	Kg. of cheese	Profit
100 g containers	x	0.1 x	0.5 x
300 g containers	y	0.3 y	1.4 y
Constraints	x ≤ 15000 x ≥ y	≤ 2400

3) System of inequalities for the constraints

\begin{cases} 0.1x + 0.3y \leq 2400 \\ x \leq 15000 \\ x \geq y \end{cases}

4) Graph the feasible region

5) We find the vertex points

\begin{aligned} A &= \begin{cases} 0.1x + 0.3y = 2400 \\ x = y \end{cases} & A &= (6000, 6000) \\ B &= \begin{cases} 0.1x + 0.3y = 2400 \\ x = 15000 \end{cases} & B &= (15000, 3000) \\ C &= \begin{cases} x = 15000 \\ y = 0 \end{cases} & C &= (15000, 0) \end{aligned}

Resolution by the algebraic method

6) We apply each vertex point to the objective function to find the optimal value:

\begin{aligned} B(6000, 6000) &= 0.5 \cdot 6000 + 1.4 \cdot 6000 = 11400 \\ B(15000, 3000) &= 0.5 \cdot 15000 + 1.4 \cdot 3000 = 11700 \\ B(15000, 0) &= 0.5 \cdot 15000 + 1.4 \cdot 0 = 7500 \end{aligned}

Resolution by the graphical method

6) The level lines associated with the objective function are drawn

\displaystyle 0.5x+1.4y=k

Draw any line, for example

0.5x+1.4y=0

, and draw parallel lines until finding the optimal vertex. If we want to maximize, it will be the point that touches the line furthest to the right, and if we want to minimize, it will be the point that touches the line furthest to the left.

7) Expression of the result:
The optimal production point is 15,000 containers of 100 g and 3,000 containers of 300 g, with a profit of €11,700

A ham factory has two curing facilities A and B that produce 50 and 80 hams per month. They are distributed to three stores M, N and O whose demand is 35, 50 and 45 respectively, with transportation cost per ham according to the following table:

	M	N	O
Facility A	5	6	8
Facility B	7	4	2

Calculate the distribution so that the cost is minimum.

1) The constraints are interrelated, variables are defined arbitrarily. We will take:
x = hams to send from facility A to store M
y = hams to send from facility A to store N

2) We organize the information in a data table

	M	N	O
Demand	35	50	45
Facility A - 50	x	y	50 - x - y
Facility B - 80	35 - x	50 - y	45 - (50 - x - y)
Cost	5x + 7(35 - x)	6y + 4(50 - y)	8(50 - x - y) + 2(x + y - 5)

The objective function is the sum of all costs:

C(x,y) = 835 - 8x - 4y

3) The constraints are deduced by taking into account that all quantities are positive:

\begin{cases} x \geq 0 \\ y \geq 0 \\ 50 - x - y \geq 0 \\ 35 - x \geq 0 \\ 50 - y \geq 0 \\ x + y - 5 \geq 0 \end{cases}

Linear programming

Linear programming

Linear programming problem

Transportation problem. Setup