UPV



Resultados de la búsqueda By Etiquetas: programacion-lineal


La Programación Lineal. El método Simplex.

La programación lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones lineales, optimizando la función objetivo, también lineal. Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

Os dejo un vídeo tutorial donde se explica la programación lineal y se avanzan las ideas básicas del método Simplex.

Existen páginas web, como PHPSimplex, donde puedes solucionar on-line problemas sencillos. También puede resolverse este tipo de problemas con las herramientas de MATLAB: Optimization Toolbox.

A continuación os dejo un vídeo donde se explica cómo resolver un problema de Programación Lineal mediante MS Excel 2007. Es importante que aprendáis a utilizar el Solver. Espero que os guste el vídeo.

Tenéis que resolver con dicho programa los siguientes problemas:

  1. Una empresa produce hormigón usando los ingredientes A y B. Cada kilo de ingrediente A cuesta 60 unidades monetarias y contiene 4 unidades de arena fina, 3 unidades de arena gruesa y 5 unidades de grava. Cada kilo de ingrediente B cuesta 100 unidades monetarias y contiene 3 unidades de arena fina, 6 unidades de arena gruesa y 2 unidades de grava. Cada amasada debe contener, por lo menos, 12 unidades de arena fina, 12 unidades de arena gruesa y 10 unidades de grava. Formule un modelo de programación lineal y resuélvalo gráficamente.
  2. Una empresa especializada en la construcción de estructuras de edificios tiene patentes de tres tipos de forjados F1, F2 y F3. Los beneficios que consigue por metro cuadrado de forjado construido son 100, 90 y 120 unidades monetarias respectivamente. Por razones de almacenamiento y financiación, diariamente sólo se dispone de dos toneladas de acero, 200 m3 de hormigón y 8 m3 de madera para encofrados. Las cantidades de acero, hormigón y madera que se necesitan por m2 en cada uno de los forjados son:

Tipo de forjado

Materia prima

Cantidad

F1

Acero

0,2 kg/m2

Hormigón

80 dm3/m2

Madera

0,001 m3/m2

F2

Acero

0,25 kg/m2

Hormigón

37,5 dm3/m2

Madera

0,00125 m3/m2

F3

Acero

0,225 kg/m2

Hormigón

35 dm3/m2

Madera

0,0015 m3/m2

 

Maximizar el beneficio que se puede obtener.

El entregable tiene una bonificación de 0,15 puntos y deberá subirse a la carpeta Espacio Compartido de PoliformaT antes del 31 de octubre de 2017.

23 octubre, 2017
 
|   Etiquetas: ,  ,  ,  |  

Programación lineal con Matlab

Los problemas de programación lineal consisten en optimizar una ecuación lineal que está sujeta a una serie de restricciones conformadas por desigualdades lineales. Para resolverlos el toolbox de Matlab posee la función linprog, la cual posee tres algoritmos para su solución, el método de larga escala, el método simplex y el de Active Set.

La sintaxis para llamar esta función es la siguiente:

x = linprog (f ,A, b, Aeq, beq, lb, ub, x0, options)

Donde:

f: es el vector de coeficientes de la función objetivo, organizado según las variables (Matlab intentará minimizar siempre, por tanto multiplicaremos por -1 si queremos maximizar)

A, b: corresponden a las restricciones de desigualdad, siendo el primero la matriz y el segundo el vector del lado derecho del sistema de inecuaciones Ax<=b.

Aeq, beq: tienen el mismo tratamiento que A y b, respectivamente, teniendo en cuenta que los nuevos corresponden a un sistema de ecuaciones, en tanto que los antiguos constituían uno de inecuaciones.

lb, ub: son, respectivamente, los límites inferior y superior de la región donde se espera que se encuentre el punto óptimo.

x0: es el punto inicial para la iteración. Según el algoritmo usado, es posible, o no, omitir este último.

Ejercicio 1:

Un taller confecciona faldas, blusas, vestidos y abrigos para los que utiliza 2 horas, 3 horas y media, 4 horas y media y 5 horas de máquina de coser y 1, 2, 1 y 10 horas de cosido a mano para cada prenda, respectivamente. Si se dispone de 3000 horas de máquina y 2000 horas para coser a mano, y sabiendo que los beneficios obtenidos por unidad son de 6, 10, 13 y 30 u.m,  respectivamente, calcular el número de prendas de cada tipo que deben confeccionarse para obtener el máximo beneficio.

El planteamiento para el primer problema es:

Maximizar: 6×1 + 10×2 + 13×3 + 30×4
Sujeto a: 2×1 + 3,5×2 + 4,5×3 + 5×4 = 3000
x1 + 2×2 + x3 + 10×4 = 2000
x1, x2, x3, x4 ≥ 0

Para definir todas las variables del primer problema, en Matlab, se debe escribir:
>> f = [-6 -10 -13 -30];
>> A = -eye(4); % matriz identidad de tamaño 4×4
>> b = [0 0 0 0];
>> Aeq = [2 3.5 4.5 5 ; 1 2 1 10];
>> beq = [3000 2000];

Finalmente, se usa la sintaxis respectiva con las variables del primer problema, cargadas previamente, para obtener lo siguiente:

>> [x,fval] = linprog(f,A,b,Aeq,beq,lb,ub,x0)
Optimization Terminated.

x =
0.0000
0.0000
500.0000
150.0000
fval =
-1.1000e+004

Ejercicio 2:

Una empresa que se dedica a la producción de frascos de perfume, de agua de colonia y de champú utiliza tres factores productivos F1, F2 y F3 disponiendo de 240, 460 y 430 unidades, respectivamente. Las cantidades de dichos factores utilizados en la producción de un frasco por cada producto se detallan en la siguiente tabla:

Cuadro
La formulación el segundo problema es:Sabiendo que el precio unitario de venta del perfume es de 5 unidades monetarias, el del agua de colonia de 2 y el del champú de 3, y que se vende todo lo que se produce, calcular el beneficio máximo y el número de frascos de cada tipo que debe producir la empresa para obtenerlo.

Maximizar: 5×1 + 2×2 + 3×3
Sujeto a: F1 ≤ 240
F2 ≤ 460
F3 ≤ 430

La asignación de los valores de las variables, correspondientes al segundo problema, se realiza de la siguiente manera:

>> f = [-5 -2 -3];
>> A = [1 2 1 ; 2 0 3 ; 0 4 1];
>> b = [240 460 430];
>> x0 = [0 0 0];

>> [x,fval] = linprog(f,A,b,[],[],[0 0 0])
Optimization Terminated.
x =
230.0000
5.0000
0.0000
fval =
-1.1600e+003

 Referencia:

Cabezas, I.; Páez, J.D. (2010). Matlab. Toolbox de optimización. Aplicaciones en ciencias económicas. Unidad de Informática y Comunicaciones. Facultad de Ciencias Económicas. Universidad Nacional de Colombia, Bogotá D.C. (enlace).

 

18 febrero, 2015
 
|   Etiquetas: ,  |  

Universidad Politécnica de Valencia