Linear programming in operations research

Introduction

Linear programming is a set of rational analysis and problem-solving techniques that aims to help decision-makers on matters involving a large number of variables.

The name of linear programming does not come from the creation of computer programs, but from a military term, programming, which means "making plans or time proposals for training, logistics or the deployment of combat units."

Although it appears that linear programming was used by G. Monge in 1776, LV Kantorovich is considered one of its creators. He presented it in his book Mathematical methods for organization and production (1939) and developed it in his work On the transfer of masses (1942). Kantorovich received the Nobel Prize in economics in 1975 for his contributions to the problem of optimal allocation of human resources.

Operations research in general and linear programming in particular got a big boost thanks to computers. One of the most important moments was the appearance of the simplex method.

goals

Know linear programming and its applications to everyday life. Set out and solve situations with linear programming. Steps for the construction of a model.

Type of Solutions

Linear programs with two variables are usually classified according to the type of solution they present. These might be:

Feasible: If there is a set of solutions or values that satisfy the restrictions. These in turn can be: with a single solution, multiple consolution (if there is more than one solution) and with an unbounded solution (when there is no limit for the objective function) Not feasible: When there is no set of solutions that meet the constraints, that is, when the constraints are inconsistent.

Solution methods

There are three methods of solving linear programming problems:

Graphic method: The level lines give the points of the plane where the objective function takes the same value. Analytical method: The following result, called the fundamental theorem of linear programming, allows us to know another method of solving a program with two variables: “In a linear program with two variables, if there is a unique solution that optimizes the objective function, it is found at an extreme point (vertex) of the bounded feasible region, never inside said region. If the objective function takes the same optimal value at two vertices, it also takes the same value at the points of the segment they determine. In the case that the feasible region is not bounded, the objective linear function does not necessarily reach a specific optimal value, but if it does, it is at one of the vertices of the region ”.Practical scheme: Linear programming problems can be presented in standard form, giving the function, objectives and restrictions, or they can be stated by means of a statement.

Basic structure:

Examples of linear programming taken from:

www.superprof.es/apuntes/escolar/matematicas/algebralineal/pl/ejembres-de-programacion-lineal.html

A department store orders pants and sports jackets from a manufacturer.

The manufacturer has 750 m of cotton fabric and 1000 m of polyester fabric to make. Each trouser requires 1 m of cotton and 2 m of polyester. For each jacket you need 1.5 m of cotton and 1 m of polyester.

The price of the pants is set at $ 50 and the jacket at $ 40.

What number of trousers and jackets must the manufacturer supply to the warehouses so that they register a maximum sale?

1. Choice of unknowns.

X = number of pants Y = number of jackets

2. Objective function

F (x, y) = 50x + 40y

3. Restrictions

To write the restrictions we are going to help ourselves with a table:

	Pants	Jackets	Available
Cotton	one	1.5	750
Polyester	two	one	1000

X + 1.5y <750 à 2x + 3y <1500 2x + y <1000

Since the number of pants and jackets are natural numbers, we will have two more restrictions:

X> 0Y> 0

4. Find the set of feasible solutions

We have to graph the constraints.

Since x> 0 and y> 0, we will work in the first quadrant.

We represent the lines, starting from their intersection points with the axes.

Linear programming

We graphically solve the inequality: 2x + 3y <1500, for this we take a point of the plane, for example (0,0).

Since 0 <1500 then the point (0,0) is in the half plane where the inequality is fulfilled.

Analogously solve 2x + y <1000.

Linear programming

The area of intersection of the solutions of the inequalities would be the solution to the system of inequalities, which constitutes the set of feasible solutions.

5. Calculate the coordinates of the vertices of the enclosure of the feasible solutions.

The optimal solution, if it is unique, is found in a corner of the enclosure. These are the solutions to the systems:

2x + 3y = 1500; x = 0 (0.500)

2x + y = 1000; y = 0 (500.0)

2x + 3y = 1500; 2x + y = 1000 (375, 250)