Métodos matemáticos de organización y planificación … · problemas de este género, debemos...

Programación Lineal para la Ingeniería Técnica

1

En los siglos XVII y XVIII matemáticos como Newton, Leibniz, Bernouilli y sobre todo Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones. Posteriormente, el matemático francés Jean Batiste-Joseph Fourier fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos Programación Lineal. Si exceptuamos al matemático Gaspar Monge, quien en 1776 se interesó por problemas de este género, debemos remontarnos al año 1939 para encontrar nuevos estudios relacionados con los métodos de la actual Programación Lineal. En este año, el matemático ruso Leonidas Vitalyevich Kantorovitch publica una extensa monografía titulada “Métodos matemáticos de organización y planificación de la producción”, en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada, hoy en día, Programación Lineal. En 1941, se formula por primera vez el problema del transporte, estudiado independientemente por Kopmans y por Kantorovitch, razón por la cual se le suele conocer con el nombre de Kopmans-Kantorovitch. Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de “régimen alimenticio opcional”. En estos años posteriores a la II Guerra Mundial, en E.E.U.U. se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaban necesariamente por los modelos de optimización que resuelve la Programación Lineal.


2

En 1947, G. B. Dantzig formula, en términos matemáticos, el enunciado estándar al que cabe reducir todo problema de Programación Lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo que dio en denominarse Scoop, siendo una de las primeras aplicaciones de los estudios del grupo el puente aéreo de Berlín. Posteriormente, se constituyen en E.E.U.U. distintos grupos de estudio para ir desarrollando las diferentes ramificaciones de la Programación Lineal. Respecto al método del Simplex, señalar que su estudio comenzó en 1951 y fue desarrollado por Dantzig. Este algoritmo es básico en la resolución de los problemas de Programación Lineal, fundamentales en economía general, economía de empresas y planificación, aunque en principio sus aplicaciones fueron militares. De forma general, los problemas de optimización lineal tienen la siguiente estructura:

• Existe un cierto objetivo a alcanzar, un beneficio máximo, un coste mínimo o mínimo período de tiempo del sistema que se estudia.

• Generalmente, hay un gran número de variables que deben manejarse

simultáneamente y de diferentes tipos.

• Existen muchas interacciones entre las variables.

• A veces, existen objetivos contradictorios con el objetivo principal del problema.

Dicho de otro modo, un problema de Programación Lineal se caracteriza, como su propio nombre indica, por funciones lineales de las variables que involucra; el objetivo es lineal en las variables, y las restricciones son también ecuaciones o inecuaciones lineales en las variables de decisión. Los campos de aplicación de la Programación Lineal son muy numerosos. Entre otros, se pueden citar:

mm

mm

mm


3

• El campo de las aplicaciones militares.

• El campo de las Matemáticas Puras y Aplicadas.

• El campo de la Economía y, especialmente, de la Economía de la Empresa. Aquí, las aplicaciones se tienen en numerosos sectores: la industria química y del petróleo, las industrias alimenticias, la metalurgia, la producción y distribución de energía eléctrica, la minería, los transportes, la agricultura y ganadería, etc.

También los tipos de problemas son muy variados, entre ellos están:

• Las mezclas (industria del petróleo, nutrición de animales, etc.).

• La afectación del personal (problemas de asignación de tareas).

• La distribución y el transporte.

• El almacenaje.

• Los planes de producción.

• Los problemas compuestos de inversión, producción, almacenaje y distribución.

• Los estudios de circulación.

• El problema del viajante de comercio.

Para la Teoría Económica, en general, la aportación que ha hecho la Programación Lineal es muy valiosa, ya que muchas interrelaciones que en principio podían estar explicadas de forma vaga, están en la actualidad cuantificadas y perfectamente definidas. El atractivo que la Programación Lineal ofrece en cualquier otro tipo de disciplinas, hay que buscarlo en la sencillez de las técnicas matemáticas que utiliza,


4

la riqueza o posibilidades que ofrece su teoría, y la facilidad computacional que se tiene para los problemas lineales en contraposición con los no lineales. Al mismo tiempo, nos permite organizar la información cuantitativa en un modelo de expresión matemática accesible para expertos en otras profesiones. Otra razón de la popularidad de la formulación lineal, tanto para el objetivo como para las restricciones, es que es a menudo la menos difícil de definir, lo cual lleva en múltiples ocasiones a linealizar objetivos no lineales, con la consiguiente aproximación de su óptimo. Por simplicidad en los cálculos y claridad en la exposición, el estudio no se concretará en una aplicación particular. Los ejemplos que utilizaremos para describir la técnica puramente formal son de pequeñas dimensiones y económicamente irreales.


5

El problema general de Programación Lineal consiste en la búsqueda del óptimo (máximo o mínimo) de una función lineal de n variables jx , j = 1, ..., n, ligadas por

relaciones lineales (ecuaciones o inecuaciones) llamadas restricciones. Entre las restricciones se distinguen:

1. Las del tipo 0≥jx , imponiendo a una parte o al conjunto de las

variables ser no negativas. Usualmente, son llamadas restricciones de no negatividad.

2. El resto de las restricciones, del tipo que sean, a las que a veces de les

denomina restricciones verdaderas. Exceptuando el caso de los problemas lineales en números enteros, las variables pueden tomar cualquier conjunto de valores reales que satisfagan las restricciones. Precisamente, se tratará de encontrar, de entre estos posibles valores, aquel que de un mejor valor a la función lineal antes mencionada. Las restricciones son normalmente inecuaciones o ecuaciones. Se puede suponer, siempre que sea necesario, que algunas inecuaciones se han multiplicado por – 1, para que todas las desigualdades tengan el mismo sentido, y que algunas variables se han sustituido por sus opuestas para que las únicas condiciones suplementarias impuestas a estas variables sean restricciones de no negatividad. 2.1. EJEMPLO Supongamos que un ganadero está especializado en la explotación de ganado vacuno y que en el mercado puede comprar cuatro tipos de pienso, A, B, C y D. La composición de los piensos por tonelada es la siguiente:

a a

volver a objetivo, variables, interacciones

mm

mm

Enunciado

mm

mm


6

• El pienso A contiene 200 unidades de un pienso nutritivo M y 300 unidades de otro N.

• El pienso B contiene 150 unidades de M y 270 unidades de N. • El pienso C contiene 100 unidades de M y 140 unidades de N. • El pienso D contiene 45 unidades de M y 90 unidades de N. Por otro lado, teniendo en cuenta el número de cabezas existente en la explotación, para la alimentación diaria se necesitan 5500 unidades del elemento M y 8700 de N. El coste por tonelada de cada uno de los piensos es de 90, 81, 40 y 24 unidades monetarias respectivamente para A, B, C y D. Se tratará de determinar el tipo y cantidad de piensos que se deben comprar de forma que, garantizando la alimentación del ganado, el coste sea mínimo. Solución:

La formulación matemática del problema sería: min 4321 24408190 xxxx +++ [1] s.a.: 550045100150200 4321 ≥+++ xxxx [2] 870090140270300 4321 ≥+++ xxxx [3] 0,0,0,0 4321 ≥≥≥≥ xxxx [4]

donde 1x : toneladas que se deberán comprar de A. 2x : toneladas que se deberán comprar de B. 3x : toneladas que se deberán comprar de C. 4x : toneladas que se deberán comprar de D. La función lineal que se optimiza es [1], las restricciones lineales o verdaderas son [2] y [3], y las restricciones de no negatividad son [4]. Obviamente, en este caso, el problema de optimización se concreta en uno de minimización, puesto que la función que se optimiza [1] representa el coste total de adquirir 1x toneladas de A, 2x de B, 3x de C y 4x de D al

precio de 90, 81, 40 y 24 unidades monetarias por tonelada respectivamente.

mm

mm

Datos del problema

mm

Introducción de las variables y formulación del problema


7

Cada una de las restricciones lineales [2] y [3] se formula como una inecuación del tipo “mayor o igual”, ya que representa la cantidad total de elemento nutritivo M y N, respectivamente, que contiene la ración formada por 1x toneladas de pienso A, 2x de B, 3x de C y 4x de D, y que debe ser al

menos 5500 unidades para M y al menos 8700 unidades para N, es decir, mayor o igual que 5500 y 8700 unidades respectivamente. Por último, es obvio que la cantidad (toneladas) que incluye la ración de los piensos A, B, C y D debe ser no negativa, es decir, mayor o igual que cero, con lo que quedan justificadas las restricciones de no negatividad [4].

2.1. MODELIZACIÓN DEL PROBLEMA La traducción algebraica que podemos hacer para la formulación del objetivo, tratará de optimizar (minimizar o maximizar) la función lineal:

( ) ∑=

=n

jjjn xcxxf

11 ,,…

siendo constantes los coeficientes jc .

Del mismo modo, para la formulación del sistema de restricciones:

i

n

jjij bxa ≥∑

=1, i = 1, ..., p

i

n

jjij bxa =∑

=1

, i = p + 1, ..., m

0≥jx , j = 1, ..., q jx cualquiera j = q + 1, ..., n

Un significado apropiado para cada una de las cantidades que intervienen sería el siguiente:

a a

volver a problema general

mm

mm


8

jx : nivel de actividad j-ésima. Por tanto, n denotará el número de

actividades. jc : margen de beneficio o coste que supone producir una unidad de la

actividad j-ésima. ija : cantidad del i-ésimo recurso requerido para producir una unidad de la

j-ésima avtividad. Por tanto, m denotará el número de recursos. ib : cantidad disponible del i-ésimo recurso o su requerimiento.

Toda la teoría que vamos a desarrollar se establece bajo la condición fundamental de no negatividad de las variables, condición que se impone a priori en casi todos los problemas económicos, y que puede adoptarse siempre en cualquier problema. Consideremos tres formulaciones equivalentes del problema, todas ellas equivalentes a su vez a la forma general, y todas con variables no negativas:

1. Forma canónica: útil para el desarrollo de la teoría de la dualidad.

max cc xcz = s.a.: ccc bxA ≥ 0≥cx

2. Forma estándar: para desarrollar los métodos de cálculo.

max dd xcz = s.a.: ddd bxA = 0≥dx

3. Forma mixta: comprende a las dos anteriores.

max tt xcz = s.a.: itti bxa ≥ , i = 1, ..., p itti bxa = , i = p + 1, ..., m 0≥tx

mm


9

Todo problema de Programación Lineal puede reducirse a la forma estándar, con el siguiente enunciado:

Hallar ( ) nnxxX ℜ∈= ,,1 … que maximice la forma lineal:

( ) nnxcxcXfZ ++== …11

sujeto a las siguientes restricciones: 11111 bxaxa nn =++…

mnmnm bxaxa =++…11

0≥jx , j = 1, ..., n, 0≥ib , i = 1, ..., m (m < n)

En notación matricial:

max Z = CX s.a.: AX = B

0≥X donde:

( )nccC ,,1 …= ,

=

nx

xX

1

,

=

mnm

n

aa

aaA

…

…

1

111

,

=

mb

bB

1

, m < n

0≥X , denota que sus componentes son todas mayor o igual que cero.

Llamaremos ( )nmi

i

i PPAa

aP ,,1

1

…=⇒

= .

Para llegar a la forma estándar realizaremos, en caso de ser necesario, alguna de las siguientes operaciones:

mm

volver a forma éstandar


10

Operación I: maximizar f (X) equivale a minimizar – f (X). De este modo, siempre el problema se puede transformar en uno de maximización. Operación II: una variable de cualquier signo jx , siempre se puede sustituir

por dos no negativas de la forma que sigue:

−+ −= jjj xxx , con ( ) 0,0 ≥=+jj xmaxx , ( ) 0,0 ≥−=−

jj xmaxx .

Obsérvese que así, el número de variables aumenta en una por cada una a la que le apliquemos esta transformación. Si no se desea aumentar el número de variables podemos utilizar otro método: supongamos que 1x no está restringida en signo, entonces podemos eliminarla utilizando alguna de las restricciones en la que el coeficiente de 1x sea distinto de cero. Por ejemplo, si inini bxaxa =++…11 es tal que 01 ≠ia , entonces:

( )niniiii

xaxaba

x −−−= …221

11

y sustituimos esta expresión en todas las restricciones restantes, así como en la función objetivo. El problema quedará expresado en términos de una variable y una restricción menos que el problema original. Obviamente, una vez obtenido el óptimo para este nuevo problema con n – 1 variables y m – 1 restricciones, se encuentra el óptimo para el problema original fácilmente. Operación III: si para algún i se tiene 0≤ib , entonces se multiplica esa

restricción por – 1, obteniendo:

i

n

jjiji

n

jjij bxabxa −=−⇔= ∑∑

== 11

donde ahora 0≥− ib .

Operación IV: toda ecuación puede sustituirse por dos inecuaciones:


11

−≥−

≥⇔=

∑

∑∑

=

=

=i

n

jjij

i

n

jjij

i

n

jjij

bxa

bxabxa

1

1

1

Operación V: toda inecuación puede sustituirse por una ecuación, agregando al primer término una variable, llamada de compensación o de holgura, 0≥iy .

ii

n

jjiji

n

jjij byxabxa =−⇔≥ ∑∑

== 11

ii

n

jjiji

n

jjij byxabxa =+⇔≤ ∑∑

== 11

Esta variable está afectada de un coeficiente nulo en la función objetivo a optimizar. El problema quedaría: min YCXZ 0+= s.a.: BIYAX =− 0,0 ≥≥ YX

donde: ( )0,,00 …= ,

=

my

yY

1

,

=

100

010001

…

……

I

Si hacemos el cambio de notación: sns xy += , ms ≤≤1 , entonces:

( )0,* CC = ,

=YX

X * , ( ) ⇒−= IAA ,* max *** XCZ =

BXA =** 0* ≥X


12

A partir del planteamiento del problema de Programación Lineal expresado en su formulación estándar, vamos a estudiar las principales definiciones y resultados que soportan el aspecto teórico del procedimiento de solución que veremos posteriormente.

max Z = CX A: matriz de coeficientes tecnológicos. s.a.: AX = B B: vector de disponibilidad de recursos.

0≥X C: vector de precios o costes unitarios. 3.1. DEFINICIONES Algunos conceptos que utilizaremos en lo sucesivo son: Función objetivo: la función a optimizar f(X). Sistema de restricciones lineales: conjunto de todas las restricciones. Solución factible: ( )nxxX ,,1 …= que satisfaga el conjunto de restricciones

lineales. Solución factible básica: la que tiene a lo sumo m variables no nulas. Solución factible básica no degenerada: la que tiene exactamente m variables no

nulas. Solución óptima: la mejor entre las factibles. Región de factibilidad (F): conjunto de todas las soluciones posibles o factibles.

a a

volver a significado apropiado


13

Punto n-dimensional en el espacio IRn: es la n-tupla ( )nxxX ,,1 …= , y está

caracterizado por ser un conjunto ordenado de n valores o coordenadas llamadas también componentes de X.

A continuación, procedemos a formular otras definiciones de interés. Definición: Un conjunto C de IRn es convexo si para dos puntos cualesquiera del conjunto, el segmento que los une también está contenido en el conjunto. Esto es,

CvvCvv ∈β+α⇒∈∀ 2121, , con 0, ≥βα y 1=β+α . En dos dimensiones podemos ver algunos ejemplos:

CONVEXOS

NO CONVEXOS Definición:

Una combinación lineal convexa es una combinación de la forma ∑=

αn

iii x

1

, con

11

=α∑=

n

ii , nii ,,1,0 …=∀≥α . En particular, si n = 2, queda ( ) 21 1 xx λ−+λ ,

10 ≤λ≤ . También se le llama segmento lineal n-dimensional.

a a

concepto relacionado con convexo

a a

papel de la combinación lineal convexa


14

Definición: En un espacio n-dimensional, el subconjunto de puntos cuyas coordenadas satisfacen bxaxa nn =++…11 se llama hiperplano. Un hiperplano tiene dimensión

n – 1 en un espacio n-dimensional. Al conjunto de puntos cuyas coordenadas satisfacen bxaxa nn ≤++…11 se le llama semiespacio cerrado.

Definición: Un conjunto convexo se llama poliedro si es la intersección de un número finito de semiespacios cerrados. Definición: Un punto extremo de la región de factibilidad F es un punto que no puede ser expresado como combinación lineal convexa de otros puntos del conjunto, pero cualquier otro punto del conjunto puede expresarse como combinación lineal convexa de puntos extremos. Si el número de extremos es finito, a C se le llama poliedro convexo. 3.2. PROPOSICIONES BÁSICAS Dado el problema de Programación Lineal expresado en forma estándar, se tienen los siguientes resultados.

max Z = CX s.a.: AX = B

0≥X Teorema: El conjunto de soluciones factibles en un problema de Programación Lineal, F, caso de no ser vacío, es un poliedro convexo que no contiene rectas.

mm

mm


15

Demostración:

Supongamos que ∅≠F . Sean FXX ∈21 , , y sean α, β cualquiera números reales tales que 0≥α ,

0≥β , 1=β+α . Entonces, por hipótesis, se tiene que 01 ≥X , BAX =1 , 02 ≥X , BAX =2 .

Se tiene que 021 ≥β+α XX y ( ) BBBAXAXXXA =β+α=β+α=β+α 2121 ; luego toda combinación lineal convexa de 1X y 2X pertenece a F. La imposibilidad de contener rectas es consecuencia directa de las restricciones de no negatividad de las variables en el problema.

Teorema Fundamental de la Programación Lineal: a) La función objetivo es máxima en un punto extremo (vértice) del conjunto

convexo F de las soluciones factibles. b) Si dos vértices son máximos para la función objetivo, entonces lo es toda

combinación lineal convexa de éstos. Demostración:

Supongamos que F es un poliedro convexo. a) Sean kXX ,,1 … los vértices de F y sea 0X un punto no extremo y

solución posible; por no ser extremo se tiene que ∑=

α=k

i

ii XX

1

0 , con

11

=α∑=

k

ii , 0≥αi , i = 1, ..., k. La función objetivo en 0X es ( ) 00 CXXf = ,

entonces:

( ) ( )∑∑∑===

α=α=α=k

i

ii

k

i

ii

k

i

ii XfCXXCXf

111

0

mm


16

Sea ( ){ }niXfmax i ,,1, …==λ ( ) λ=λα≤⇒ ∑=

k

iiXf

1

0 . Por tanto, 0X no es

un punto máximo de la función objetivo y el máximo se ha de alcanzar en los extremos.

b) Sean 21, XX dos extremos donde se alcanza el máximo de la función objetivo, es decir, ( ) ( ) λ== 21 XfXf , y sean 0≥α , 0≥β con 1=β+α . Por ser f lineal, se tiene:

( ) ( ) ( ) ( ) λ=λβ+α=βλ+αλ=β+α=β+α 2121 XfXfXXf

lo cual demuestra la segunda parte.

Teorema: Si existen k vectores iP linealmente independientes y existen kxx ,,1 … reales tales

que BPxk

iii =∑

=1

con todos los 0≥ix y k < n, entonces ( )0,,0,,,1 …… kxxX = es un

vértice de F. Demostración:

Supongamos, por reducción al absurdo, que X no es vértice de F. Entonces, existen ( )11

11 ,, nxxX …= , ( )22

12 ,, nxxX …= vértices distintos de F, y α, β

números reales ( 0≥α , 0≥β con 1=β+α ) tales que 21 XXX β+α= , esto es:

( ) ( ) ( )221

1111 ,,,,0,,0,,, nnk xxxxxx ………… β+α=

Podemos considerar que 0≠α y 0≠β , ya que: Si α = 0, entonces β = 1, y se tendría que 2XX = , llegando a contradicción. Si β = 0, entonces α = 1, y se tendría que 1XX = , llegando a contradicción. Por tanto: 022

111

1 ====== ++ nknk xxxx …… , y como FXX ∈21, , se tiene:


17

( ) ( ) 0211

21

1122

112

1111

1

=−++−⇒

=++⇒==++⇒=

kkkkk

kk PxxPxxBxPxPBAXBxPxPBAX

………

y como iP son linealmente independientes, se deduce que:

2121 ,,1, XXkixx ii =⇒== … , lo que de nuevo es una contradicción.

Así, por cualquiera de los caminos llegamos a contradicción con la hipótesis de partida, por lo tanto se concluye que X es un vértice de F.

Teorema. (recíproco del anterior) Si el punto ( )0,,0,,,1 …… kxxX = es un vértice del conjunto de restricciones,

entonces los vectores iP asociados mediante BPxn

iii =∑

=1

a los ix son linealmente

independientes. Demostración:

Sea ( )0,,0,,,1 …… kxxX = vértice de F con 0>ix para ki ≤≤1 , entonces

sus vectores asociados mediante BPxn

iii =∑

=1

son kPP ,,1 … , y supongamos

que son linealmente dependientes. Entonces, existen escalares kββ ,,1 … tales que 011 =β++β kk PP … con alguno de esos escalares distinto de cero.

Sea α > 0 01

=βα⇒ ∑=

k

iii P , luego se tiene:

( )

( )

=αβ−=βα−

=αβ+=βα+

∑∑∑

∑∑∑

===

===

BPxPPx

BPxPPxk

iiii

k

iii

k

iii

k

iiii

k

iii

k

iii

111

111

Construimos dos vectores de la forma:


18

( )0,,0,,,111 …… kkxxX αβ+αβ+=

( )0,,0,,,112 …… kkxxX αβ−αβ−=

Como todas las 0>ix siempre podemos elegir un α > 0 tal que todas las componentes iix αβ+ y iix αβ− sean estrictamente positivas. Según esto,

FXX ∈21, por el teorema anterior.

Pero XXXXX =+=+222

2121

, lo que entra en contradicción con el hecho

de ser X vértice de F, porque si X es punto medio del segmento definido por 1X y 2X en el convexo F, X no puede ser vértice de F.

Concluimos por tanto que kPP ,,1 … son linealmente independientes.

Propiedades: Dado el problema de Programación Lineal en forma estándar, se tienen las siguientes propiedades: 1. Si tiene solución factible, entonces tiene solución factible básica. 2. Si existe una solución factible óptima, entonces existe una solución factible

básica óptima. 3. Cualquier punto extremo de F también es solución factible básica. 4. Si F es distinto del vacío, al menos posee un punto extremo. 5. Si F es igual al vacío, no existe solución óptima. 6. F posee un número finito de puntos extremos. 7. Si la función objetivo está acotada superiormente en F distinto del vacío,

entonces existen soluciones óptimas, al menos una de las cuales es un punto extremo de F.

mm


19

8. Si F es no acotado, puede existir solución óptima no acotada. Consecuencia: Para encontrar las soluciones factibles básicas óptimas, bastará con investigar el valor que toma la función objetivo en los puntos extremos del poliedro convexo que constituye la región de factibilidad, representada por la intersección de las restricciones. Además, si dos de estos extremos son óptimos, también lo será cualquier punto del segmento o combinación lineal convexa que los une, con lo que tendríamos un número infinito de soluciones óptimas. Se estaría en esta situación cuando la función objetivo fuera paralela a una restricción.


20

Siempre que el problema incluya únicamente dos o tres variables de decisión, podemos representar gráficamente las restricciones para dibujar en su intersección el poliedro convexo que conforma la región de factibilidad F. Si el número de variables es dos, las restricciones, semiespacios cerrados, son semiplanos delimitados por la recta que corresponde a cada restricción. Si el número de variables es tres, los semiespacios en este caso están delimitados por planos. 4.1. REGLA DE LOS CINCO PASOS Para hallar, gráficamente, la solución de un problema de Programación Lineal con dos variables, procederemos del siguiente modo: Paso 1: representaremos todas las restricciones del problema para determinar la región de factibilidad F. Si ésta es vacía, el problema no tiene solución óptima, se dice que es inconsistente. En otro caso, ir al paso 2. Paso 2: identificar los extremos o vértices de F. Paso 3: dibujar una de las rectas que pertenece a la familia de rectas paralelas que representa la función objetivo, f(X) = k. Habitualmente, suele dibujarse f(X) = 0 por comodidad. Paso 4: desplazamos paralelamente a sí misma la recta que representa la función objetivo para determinar la dirección de mejora, que será aumento o disminución según si el objetivo del problema es la maximización o minimización de dicha función.

mm


21

Paso 5: el punto extremo de F al que corresponde el valor óptimo para la recta que representa la función objetivo es la solución óptima finita del problema. Nota: hay que tener en cuenta que pueden presentarse las situaciones estudiadas en el apartado anterior, cuando existe más de un punto extremo o la región de factibilidad es no acotada. 4.2. EJEMPLO (El problema de la ración) Supongamos que se quiere elaborar una ración que satisfaga unas condiciones mínimas de contenidos vitamínicos diarios, por ejemplo 2 mg de vitamina A, 60 mg de B y 40 mg de C. Para ello se van a mezclar dos clases de piensos, P y Q, cuyo precio por kilogramo es, respectivamente, de 40 y 60 pesetas, y cuyo contenido en las vitaminas citadas es:

A B C 1 kg de P 1 mg 20 mg 10 mg 1 kg de Q 0.5 mg 20 mg 20 mg

¿Cómo deben mezclarse los piensos para que satisfagan esas necesidades vitamínicas con el menor gasto posible?. Solución:

Denotamos: x = cantidad de P que se debe consumir diariamente. y = cantidad de Q que se debe consumir diariamente.

La función objetivo a minimizar en este caso consiste en el coste producido por la compra de los piensos P y Q, esto es:

f (x, y) = 40x + 60y

mm

mm

mm

Enunciado

mm

Definición de variables


22

Las restricciones lineales que aseguran que se satisfacen las necesidades mínimas en contenido de vitaminas quedan expresadas como:

x + 0.5y ≥ 2 (vitamina A) ≥ 602020x + y (vitamina B) ≥ 402010x + y (vitamina C)

Con todo ello, y las restricciones de no negatividad debido a la definición de las variables, el problema queda planteado como sigue:

min f(x, y) = 40x + 60y s.a.: 25.0 ≥+ yx 602020 ≥+ yx 402010 ≥+ yx 0≥x , 0≥y

Dibujamos la región de factibilidad:

4 3 2 1 0 1 2 3 4

El mínimo se alcanza en C(2,1), esto es, se necesitan 2 kilogramos de P y 1 kilogramo de Q, con un coste diario por animal de 140 pesetas.

40x + 60y = 0

D

C

B

A

20x + 20y = 60 10x + 20y = 40

x + 0.5y = 2

mm

mm

Formulación del problema

mm

Resolución gráfica. Método de los 5 pasos


23

Otra opción de resolver este tipo de problemas en dos dimensiones consiste en, una vez localizados los puntos extremos en el paso 2, sustituir los pasos 3, 4 y 5 del método de resolución gráfica por una simple sustitución de los vértices en la función objetivo para localizar visualmente en cuál se alcanza el óptimo buscado. En esta segunda opción, hay que tener en cuenta que si la región de factibilidad no está acotada como en el ejemplo, es necesario seleccionar, junto con los vértices, un punto en cada una de las restricciones por las que no se cierra la región factible, y una vez sustituidos en la función objetivo, realizar el límite a lo largo de la restricción correspondiente. Ilustramos esta operación con el ejemplo que estamos considerando. En este caso, los vértices son: A(0,4), B(1,2), C(2,1), D(4,0), y consideramos dos puntos de la forma E(x,0), F(0,y) que corresponden a las rectas que abren la región factible. Sustituimos estos seis puntos en la función objetivo a minimizar:

f(A) = f(0,4) = 240 f(B) = f(1,2) = 160 f(C) = f(2,1) = 140 f(D) = f(4,0) = 160 f(E) = f(x,0) = 40x +∞=

+∞→xlim

x40

f(F) = f(0,y) = 60y +∞=+∞→

ylimy

60

Como es obvio, el resultado es el mismo. Es de destacar en este ejemplo que la mismafunción con las mismas restricciones no posee máximo acotado.

4.3. OBSERVACIONES Observación 1: Si f(x, y) = ax + by, la dirección de “mejora” se obtiene geométricamente de la siguiente manera:

mm

mm

Alternativa de solución gráfica


24

• Si b > 0, el máximo se calculará trasladando paralelamente f(x, y) = k hasta que toque al último vértice, donde se encontrará el máximo. Para el caso de mínimo, se realizará lo mismo para el primer vértice.

• Si b < 0, se procede de manera contraria, esto es, para el máximo nos

fijaremos en el primer vértice, y para el mínimo en el último. Observación 2: En caso de duda, calcular el valor de f en los vértices, si la región de factibilidad está acotada. Si no lo está, mirar también en puntos “alejados” a ver que pasa (como ya hemos mencionado antes). Observación 3: Observemos, por último, que este mismo procedimiento puede seguirse en el caso de que el problema incluya tres variables, efectuando una representación espacial en IR 3. Lógicamente, si la dimensión del problema es mayor, la representación gráfica es imposible.


25

Supongamos que queremos resolver el problema lineal sin desarrollar una técnica específica. Un método de resolución que se podría pensar de forma casi intuitiva es el siguiente. El problema puede expresarse introduciendo, si hace falta, variables de holgura como: max nnxcxcZ ++= …11 s.a.: 111111 bxxaxa H

nnn =+++ +… 222121 bxxaxa H

nnn =+++ +…

m

Hmnnmnm bxxaxa =+++ +…11

0≥ix , ni ,,1…= 0≥+

Hjnx , mj ,,1…=

Este problema tiene m ecuaciones y n + m incógnitas. Para resolverlo podemos elegir m columnas linealmente independientes cualesquiera y resolver los subproblemas de esta forma obtenidos, analizando de entre las soluciones que se tengan, cuál es óptima para la función objetivo. Nótese que la submatriz formada por los m vectores columna correspondientes a las m variables de holgura es justamente la matriz identidad, y por tanto, no singular. Veámoslo con un ejemplo. Supongamos el siguiente problema a resolver: max ( ) 2121 23, xxxxf +−= s.a.: 22 21 ≤+− xx 32 21 ≤− xx 112 21 ≤+ xx 0, 21 ≥xx

mm

mm


26

Introduciendo las correspondientes variables de holgura, con coste cero en la función objetivo, el problema expresado en su formulación estándar queda como:

max ( ) HHH xxxxxxxf 5432121 00023, ++++−= s.a.: 22 321 =++− Hxxx 32 421 =+− Hxxx 112 521 =++ Hxxx 0,,,, 54321 ≥HHH xxxxx

La matriz de coeficientes tecnológicos del problema es:

−

−=

1002 1 01021 0011 2

A

Como cualesquiera tres vectores columna son linealmente independientes, tenemos 103

5 =C formas distintas de elegir tres columnas de la matriz de

coeficientes tecnológicos, es decir, tenemos 10 sistemas lineales a resolver como éste:

=

⇒

=

−

−

1427

1132

02 1 021 11 2

3

2

1

3

2

1

xxx

xxx

La siguiente tabla resume el resultado de plantear estos 10 sistemas. En ella se especifica, además del número asignado a cada sistena, los vectores columna elegidos para cada uno de ellos y la solución que proporcionan. Así mismo, si añadimos la condición de no negatividad de las variables, obtenemos cuales de las soluciones anteriores son factibles para el problema lineal. Finalmente, señalamos el valor que toma la función objetivo únicamente para las soluciones proporcionadas por los 10 sistemas que han sido factibles, eligiendo el máximo así obtenido para la función objetivo. Este resultado óptimo se señala en negrita dentro de esta tabla.

mm

mm

Forma estándar


27

Sistema nº

Vectores columna elegidos

Solución Solución factible con la

condición de no negatividad

Valor de la f.o.

1 1, 2, 3 (7, 2, 14, 0, 0) (7, 2, 14, 0, 0) -17

2 1, 2, 4 (7/5, 24/5, 0, 56/5, 0) (7/5, 24/5, 0, 56/5, 0) 27/5

3 1, 2, 5 (-7/3, -8/3, 0, 0, 56/3)

4 1, 3, 4 (11, 0, 24, -8, 0)

5 1, 3, 5 (3, 0, 8, 0, 8) (3, 0, 8, 0, 8) -9

6 1, 4, 5 (-1, 0, 0, 4, 12)

7 2, 3, 4 (0, 11/2, -7/2, 14, 0)

8 2, 3, 5 (0, -3/2, -7/2, 0, 14)

9 2, 4, 5 (0, 2, 0, 7, 7) (0, 2, 0, 7, 7) 4

10 3, 4, 5 (0, 0, 2, 3, 11) (0, 0, 2, 3, 11) 0

El valor óptimo para la función objetivo es ( )527, *

2*1

** == xxfZ , obtenido con los

valores de las variables 57*

1 =x , 524*

2 =x .

Este procedimiento da idea de cómo resolver en general problemas de Programación Lineal pero, como es obvio, presenta grandes inconvenientes para su uso práctico cuando las dimensiones del sistema son mayores, lo cual suele ser habitual en problemas reales. Nótese, que el número de sistemas lineales a

resolver será en general

+mnm

, por ello el método más utilizado es el del

Simplex de Dantzig que utiliza un número razonable de etapas.

mm

mm

Posibles soluciones

Métodos matemáticos de organización y planificación … · problemas de este género, debemos...

Documents

Transcript of Métodos matemáticos de organización y planificación … · problemas de este género, debemos...