Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un

comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido,

la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido

a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la

realidad.

Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) o Modelos

Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son

conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un

subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos

introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas.

Supuestos Básicos de la Programación Lineal: Linealidad, Modelos Deterministas, Variables

reales, No Negatividad.

APLICACIONES

1. Problema de la Dieta: (Stigler, 1945). Consiste en determinar una dieta de manera eficiente, a

partir de un conjunto dado de alimentos, de modo de satisfacer requerimientos nutricionales. La

cantidad de alimentos a considerar, sus características nutricionales y los costos de éstos, permiten

obtener diferentes variantes de este tipo de modelos. Por ejemplo:

 Leche Legumbre Naranjas Requerimientos

(lt) (1 porción) (unidad) Nutricionales

Niacina 3,2 4,9 0,8 13

Tiamina 1,12 1,3 0,19 15

Vitamina C 32 0 93 45

Costo 2 0,2 0,25

Variables de Decisión:

 X1: Litros de Leche utilizados en la Dieta

 X2: Porciones de Legumbres utilizadas en la Dieta

 X3: Unidades de Naranjas utilizadas en la Dieta

Función Objetivo: (Minimizar los Costos de la Dieta) Min 2X1 + 0,2X2 + 0,25X3

Restricciones: Satisfacer los requerimientos nutricionales

 Niacina: 3,2X1 + 4,9X2 + 0,8X3 >= 13

 Tiamina: 1,12X1 + 1,3X2 + 0,19X3 >=15

 Vitamina C: 32X1 + 0X2 + 93X3 >= 45

 No Negatividad: X1>=0; X2>=0; X3>=0

Compruebe utilizando nuestro Módulo de Resolución que la solución Óptima es X1=0,

X2=11,4677, X3=0,483871, con Valor Óptimo V(P)=2,4145.

2. Problema de Dimensionamiento de Lotes: (Wagner y Whitin, 1958). Consiste en hallar

una polìtica óptima de producción para satisfacer demandas fluctuantes en el tiempo, de modo de

minimizar los costos de producción e inventario, considerando la disponibilidad de recursos escasos.

Considere que una fabrica puede elaborar hasta 150 unidades en cada uno de los 4 periodos en
que se ha subdividido el horizonte de planificación y se tiene adicionalmente la siguiente
información:
 Demandas Costo Prod. Costo de Inventario
Periodos
(unidades) (US$/unidad) (US$/unidad)

1 130 6 2

2 80 4 1

3 125 8 2.5

4 195 9 3

Adicionalmente considere que se dispone de un Inventario Inicial de 15 unidades y no se acepta

demanda pendiente o faltante, es decir, se debe satisfacer toda la demanda del período.

Variables de Decisión:

 Xt: Unidades elaboradas en el período t (Con t =1,2,3,4)

 It: Unidades en inventario al final del período t (Con t =1,2,3,4)

Función Objetivo: (Minimizar los Costos de Producción e Inventarios) Min 6X1 + 4X2 + 8X3 + 9X4

+ 2I1 + 1I2 + 2,5I3+ 3I4

Restricciones:

 Capacidad de Producción por Período: Xt <= 150 (Con t =1,2,3,4)

 Satisfacer Demanda Período 1: X1 + I0 - I1 = 130 (I0 = 15)

 Satisfacer Demanda Período 2: X2 + I1 - I2 = 80

 Satisfacer Demanda Período 3: X3 + I2 - I3 = 125

 Satisfacer Demanda Período 4: X4 + I3 - I4 = 195

 No Negatividad: Xt >=0, It >=0

Solución Óptima utilizando Solver de MS Excel (Para ver una aplicación de esta herramienta ingrese

AQUI): X1=115, X2=150, X3=100, X4=150, I1=0, I2=70, I3=45, I4=0. Valor Óptimo

V(P)=3.622,5

3. Problema de Transporte: (Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947).

 El análisis gráfico es una alternativa eficiente para enfrentar la resolución de modelos de Programación

Lineal en 2 variables, donde el dominio de puntos factibles (en caso de existir) se encontrará en el

primer cuadrante, como producto de la intersección de las distintas restricciones del problema lineal.

Una de las propiedades básicas de un modelo de Programación Lineal que admite solución,

es que ésta se encontrará en el vértice o frontera (tramo) del dominio de puntos factibles.

Es decir, si luego de gráficar el dominio y evaluar los distintos vértices de modo de elegir "el mejor"

candidato según sea nuestro caso (el valor de la función objetivo será la que nos permitirá discriminar

cual es el mejor candidato dependiendo si estamos maximizando o minimizando).

Consideremos un Ejemplo Introductorio en 2 variables:

 D) MIN 8X + 6Y

 S.A. 2X + Y >= 10

 ...... .2X + 2Y >= 16

 ..... ..X>= 0, Y>= 0

Comentario: Nótese que corresponde al Problema Dual de P) cuya resolución se presenta en

nuestro sitio como ejemplo introductorio en la utilización de Solver de MS Excel. Para ver el detalle de

la resolución gráfica de P) se recomienda al usuario ingresar AQUI.

Para resolver el problema D) graficamos el dominio de puntos factibles y las curvas de nivel asociadas

a la función objetivo:
El área achurada en color verde representa el dominio de puntos factibles del problema D), es decir,

son las distintas combinaciones de valores que pueden adoptar las variables de decisión que

satisfacen las restricciones del problema. Cabe destacar que esto corresponde a un dominio no

acotado, lo que no implica que el problema no tenga solución.

Por otra parte sabemos que el óptimo de un problema lineal se encuentra en un vértice o frontera del

dominio de puntos factibles. En este caso tenemos 3 vértices candidatos al óptimo los cuales se

señalan con flecha blanca y azul. El vértice (X,Y)= (0,10) con V(P)=60; (X,Y)=(2,6) con V(P)=52 y

(X,Y)=(8,0) con V(P)=64. El mínimo valor para la función objetivo se alcanza en (X,Y)=(2,6) con

V(P)=52, el cual resulta ser la Solución Óptima de D). Sin embargo, una forma más eficiente para

obtener el óptimo que no implique evaluar cada vértice en la función objetivo, es desplazando las

curvas de nivel de la función objetivo en la dirección del máximo decrecimiento (en el caso de un

problema de minimización). Para un problema de minimización, el mayor decrecimiento se alcanza en

la dirección del vector " - Gradiente F(X,Y)", en nuestro caso el vector con dirección (-8,-6)

(dirección representada por flecha roja). Luego, el óptimo se alcanza en el último punto donde las

curvas de nivel intersectan al dominio de puntos factibles en la dirección del máximo decrecimiento,

cuya solución obviamente corresponde a (X,Y)=(2,6) con V(P)=52.

ANÁLISIS DE SENSIBILIDAD GRÁFICO PARA 2 RESTRICCIONES

Una vez resuelto un modelo de Programación Lineal resulta útil hacer un análisis de sensibilidad que

permita identificar cómo afecta en los resultados del problema variaciaciones en los parametros de
éste, sin que esto pase por resolver el problema nuevamente. Nuestro sitio considera una sección

aparte llamada "Sensibilidad" cuyos resultados principales se pueden consultar AQUI.

1. Variación en los Coeficientes de la Función Objetivo: La pregunta que buscamos responder es

cuál es el intervalo de variación para los coeficientes de la función objetivo (cada coeficiente se analiza

por separado) que mantiene la actual Solución Óptima.

Un primer acercamiento es considerar las pendientes de las restricciones activas en el óptimo, es

decir, aquellas restricciones que se cumplen en igualdad (en nuestro caso restricción 1 y 2). La

restricción 1 (2X + Y >=10) tiene pendiente -2. La restricción 2 (2X + 2Y >=16) tiene pendiente -1.

Por otra parte la pendiente de la función objetivo dado C1=8 y C2=6 es -4/3.

En consecuencia, se mantiene la actual Solución Óptima si la pendiente de la función objetivo (curvas

de nivel) varían en el intervalo de las pendientes de las actuales restricciones activas. Esto es:

-2 <= -C1/C2 <= -1 (Multiplicamos por -1)

2 >= C1/C2 >= 1

Si fijamos C2=6.

2 >= C1/6 >= 1

12 >= C1 >= 6 (Garantiza la actual Solución Óptima con C2 fijo)

Si fijamos C1=8.

2 >= 8/C2 >= 1

8 >= C2 >= 4 (Garantiza la actual Solución Óptima con C1 fijo)

Nótese que en los extremos de los intervalos además de incluir la actual Solución Óptima se

consideran nuevas combinaciones del dominio que mantienen el Valor Óptimo y también son Solución

Óptima de D). Esta situación determina que el problema tiene infinitas soluciones óptimas.

2. Variación en los lados derechos de las restricciones (cálculo del "precio sombra") :

Una pregunta común en el análisis de sensibilidad resulta ver el impacto que tiene en el valor óptimo
una variación marginal del lado derecho de alguna de sus restricciones (tanto aumento o

decrecimiento). El impacto en el valor óptimo por unidad de variación del lado derecho de una

restricción (manteniendo el resto constante) es el precio sombra asociado a dicha restricción. En

nuestro ejemplo, considere que el lado derecho de la restricción 1 (actualmente b1=10) corresponde

a un recurso escaso (ejemplo: horas hombre, dinero, tiempo, etc). Si sabemos que el actual valor

óptimo V(P)=52, quisieramos saber por ejemplo, cuánto aumentaría el valor óptimo se dispusiéramos

de una unidad adicional del recurso escaso (es decir, pasando a b1*=11). En forma equivalente

frecuentemente se plantea esta inquietud como ¿Cuánto es lo máximo que se estaría dispuesto a

pagar por unidad adicional del recurso asociado a la primera restricción?. Este valor corresponde al

precio sombra.

Precio Sombra Restricción 1: Primero se considera el desplazamiento paralelo de la Restricción 1

(tanto en el sentido de crecimiento o decrecimiento del lado derecho), de modo que la Solución

Óptima se siga encontrando con las actuales restricciones activas (en nuestro caso R1 y R2). Por

ejemplo, desplazando R1 en la dirección de su decrecimiento, el último punto donde se intersecta R1

con R2 sería en el par ordenado (X,Y)=(0,8). Se propone al usuario el cálculo de la máxima variación

para R1 que se produce en (X,Y)=(8,0).

En consecuencia, el Precio Sombra asociado a la Restricción 1 queda dado por:

Un Precio Sombra igual a 2 indica por ejemplo que si el lado derecho aumenta en 1 unidad, el

beneficio adicional (incremento en el Valor Óptimo) es de 2 unidades. Adicionalmente, una pregunta

frecuente resulta en identificar el intervalo de variación donde el precio sombra calculado es

válido. El máximo valor al que puede adoptar el lado derecho de R1 es b1*, de modo que la nueva

solución se siga encontrando con R1 y R2 activas. El valor de b1* se obtiene al evaluar (X,Y)=(8,0) en

la Restricción 1: 2*(8) + 1*(0)=16. Siguiendo similar razonamiento el mínimo valor que puede

alcanzar el lado derecho de R1 es b1, que evaluado en (X,Y)=(0,8) en R1 se obtiene: 2*(0) +

1*(8)=8.

Se recomienda al usuario hacer el cálculo del Precio Sombra para la Restricción 2, el cual corresponde

a 2. Si desea consultar un nuevo ejemplo ingrese a Resolución Gráfica en Programación Lineal.

(Sitio: Investigación Operativa)

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que

secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación

Lineal en caso de existir esta última.

La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71

variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1,

implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.

El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de

Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último

en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación

progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método

Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar

el cual definiremos a continuación.

FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL

Consideremos un modelo de Programación Lineal en su forma estandar, que denotaremos en lo que

sigue por:
 Min c1x1 + c2x2 + ... + cnxn

 sa a11x1 + a12x2 + ... + a1nxn = b1

 a21x1 + a22x2 + ... + a2nxn = b2

 ... ... ...

 am1x1 + am2x2 + ... + amnxn = bm

 xi >= 0, i = 1, 2, ..., n y m <= n

Matricialmente escrito como:

Min cTx

s.a Ax = b

x >= 0

No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:

 EJEMPLO

 P) Max 9u + 2v + 5z

 sa 4u + 3v + 6z <= 50

 u + 2v - 3z >= 8

 2u - 4v + z = 5

 u,v >= 0

 z e IR

1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la

función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -

f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de -f(x)

2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una

(nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo.

 3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una

(nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.

4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no

negativas.

Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6

(exceso), el problema P) puede ser escrito en forma equivalente como:

 Min - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6

 sa: 4x1 + 3x2 + 6x3 - 6x4 + x5 = 50

 x1 + 2x2 - 3x3 + 3x4 - x6 = 8

 2x1 - 4x2 + x3 - x4 = 5

 xi >= 0, i=1,2,3,4,5,6.

EJEMPLO:

Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:

 Max 40*X1 + 60*X2

 s.a. 2*X1 + 1*X2 <= 70

 1*X1 + 1*X2 <= 40

 1*X1 + 3*X2 <= 90

 X1 >= 0 X2 >= 0

Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual

definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3.
De esta forma queda definida la tabla inicial del método de la siguiente forma:

X1 X2 X3 X4 X5

2 1 1 0 0 70

1 1 0 1 0 40
 1 3 0 0 1 90

-40 -60 0 0 0 0

En esta situación, las variables de holgura definen una solución básica factible inicial, condición

necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no

básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el

costo reducido "más negativo". En este caso, X2.

Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el

lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes

> 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30

asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja

la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con
rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al
cabo de una iteración:

X1 X2 X3 X4 X5

5/3 0 1 0 -1/3 40

2/3 0 0 1 -1/3 10

1/3 1 0 0 1/3 30

-20 0 0 0 20 1800

El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector

hacer una representación gráfica del problema y notar como las soluciones factibles del método

corresponden a vértices del dominio de puntos factibles.

La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable

no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el

criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3),

30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido
lo anterior se aplica una iteración del método:
 X1 X2 X3 X4 X5

0 0 1 -5/2 1/2 15

1 0 0 3/2 -1/2 15

0 1 0 -1/2 1/2 25

0 0 0 30 10 2100

Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos

asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia

de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con

"infinitas soluciones".

La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos

reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1,

2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método

gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para

el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.

MÉTODO SIMPLEX DE 2 FASES

Esta estrategia se utiliza cuando no es inmediata una solución básica factible inicial en las variables

originales del modelo.

FASE 1: Se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las

restricciones del problema, de modo de obtener una solución básica factible. Resolver por Simplex un

problema que considera como función objetivo la suma de las variables auxiliares. Si el valor óptimo

es cero, seguir a la Fase II, en caso contrario, no existe solución factible.

FASE 2: Resolver por Simplex el problema original a partir de la solución básica factible inicial hallada

en la Fase I.

 P) Max 2X1 + X2

 sa 10X1 + 10X2 <= 9

 10X1 + 5X2 >= 1

 X1, X2 >= 0

Se debe agregar X3 como variable de holgura de la restricción 1, X4 como variable de exceso de la

restricción 2 y X5 variable auxiliar para poder comenzar la Fase 1. (Nótese que solo agregando X3

como variable de holgura a la restricción 1 y X4 como variable de exceso a las segunda restricción no

se obtiene una solución básica factible inicial, en particular X4<0).

 F1) Min X5

sa ...............10X1 + 10X2 + X3 = 9

 10X1 + 5X2 - X4 + X5 = 1

 X1, X2, X3, X4, X5 >= 0

La tabla inicial asociada a la Fase I queda en consecuencia definida de la siguiente forma:

X1 X2 X3 X4 X5

10 10 1 0 0 9

10 5 0 -1 1 1

0 0 0 0 1 0

Luego, se debe hacer 0 el costo reducido de X5, obteniendo la siguiente tabla inicial para hacer el
uso de Simplex:

X1 X2 X3 X4 X5

10 10 1 0 0 9

10 5 0 -1 1 1

-10 -5 0 1 0 -1

Se escoge X1 como variable que entra a la base al tener el costo reducido más negativo.

Posteriormente, mediante el criterio del mínimo cuociente se selecciona la variable que sale de la

base: Min {9/10; 1/10} = 1/10, X5 sale de la base:

X1 X2 X3 X4 X5
 0 5 1 1 -1 8

1 1/2 0 -1/10 1/10 1/10

0 0 0 0 1 0

Se obtiene la solución óptima de la Fase I, con valor óptimo cero. Luego iniciamos la Fase II del

método tomando X1 y X3 como variables básicas iniciales.

FASE 2: Resolver por Simplex el problema original a partir de la solución básica factible inicial
hallada en la Fase I.

X1 X2 X3 X4

0 5 1 1 8

1 1/2 0 -1/10 1/10

-2 -1 0 0 0

Hacemos cero los costos reducidos de las variables básicas:

X1 X2 X3 X4

0 5 1 1 8

1 1/2 0 -1/10 1/10

0 0 0 -1/5 1/5

X4 entra a la base. Por el criterio del mínimo cuociente, el pivote se encuentra en la fila 1, por tanto

X3 sale de la base:

X1 X2 X3 X4

0 5 1 1 8

1 1 1/10 0 9/10

0 1 1/5 0 9/5

Donde la solución óptima es: X1=9/10 X2=0 Con valor óptimo V(P) = 9/5.
 ¿Necesitas Aprobar tu Examen de
Programación Lineal y no tienes
ejercicios Resueltos?...
Descarga HOY el Libro de Apuntes de Programación Lineal!

RESUELVA AQUI SUS PROBLEMAS DE PROGRAMACIÓN LINEAL UTILIZANDO EL MÉTODO

SIMPLEX

La siguiente aplicación permite resolver modelos de Programación Lineal utilizando el Método Simplex.

Consideremos uno de los ejemplos de esta sección para ver su uso. Nótese que no es necesario

agregar las restricciones de no negatividad. De aquí se obtiene la solución óptima, valor óptimo y cada

una de las tablas del Método Simplex. Para una mejor visualización de las tablas se recomienda

seleccionar el modo "Fracción".

Principio del formulario

Escriba su problema lineal abajo. (Seleccione "Ejemplo" para ver como

 funciona)

Solución:

Redondeo: digitos significativos

Modo:

Las tablas del Metodo Simplex apareceran AQUI.

Aplicación usada con la autorización de ZweigMedia Inc. Los derechos de autor corresponde a

ZweigMedia.

¿Problemas usando la aplicación? Háganos llegar sus consultas. Ingrese a nuestro Formulario de

Contacto:
 NUESTROS REFERIDOS

A continuación se presenta un compendio de Links de Interés para el usuario.

Método Simplex

Investigación Operativa

ENLACES PATROCINADOS

Links patrocinados que pueden resultar de interés para el usuario.

MÉTODO SIMPLEX - CASOS ESPECIALES

Llevar un problema de Programación Lineal a su forma estándar no siempre es inmediato. Un error

frecuente es tratar de resolver por el Método Simplex un modelo que no cumple con el diseño que

exige el método. A continuación algunos ejemplos y casos especiales a tener en cuenta:

CAMBIO DE VARIABLES

Resuelva el siguiente problema de Programación Lineal utilizando el Método Simplex.

Max 2X1 + 2X2 + 4X3

S.A.

X2 + 2X3 <= 240 (R1)

X1 + X2 + X3 <= 400 (R2)

2X1 + X2 + X3 <= 360 (R3)

X1>=100 (R4) X2>=60 (R5) X3>=60 (R6)

Si quisiéramos resolver directamente este problema utilizando Simplex deberíamos agregar variables

de exceso para R4, R5 y R6 y luego variables artificiales para disponer de una solución básica factible

de modo de utilizar el Método Simplex de 2 Fases. Claramente esto es un trabajo tedioso por el gran

tamaño de la tabla resultante.

En consecuencia, lo más eficiente es hacer un cambio de variables de modo que todas las

restricciones queden del tipo "<=" y de esta forma se dispone de una solución básica factible inicial.

Sea Y1=X1-100>=0; Y2=X2-60>=0; Y3=X3-60>=0. Reemplazamos en el modelo anterior, el cual

queda de la siguiente forma:

Max 2Y1 + 2Y2 + 4Y3 + 560

S.A.

Y2 + 2Y3 <= 60 (R1)

Y1 + Y2 + Y3 <= 180 (R2)

2Y1 + Y2 + Y3 <= 40 (R3)

Y1>=0 (R4) Y2>=0 (R5) Y3>=0 (R6)

Nótese que se podría obviar la restricción 2 y obtener identicos resultados. De todos modos definimos

la tabla inicial asociada a este nuevo problema:

Y1 Y2 Y3 S1 S2 S3

0 1 2 1 0 0 60

1 1 1 0 1 0 180

2 1 1 0 0 1 40

-2 -2 -4 0 0 0 0

Compruebe que Y1=5 (X1=105), Y2=0 (X2=60), Y3=30 (X3=90) con V(P)=690.

PROBLEMA INFACTIBLE

Esta situación se detecta cuando el valor óptimo del problema de la fase 1 es distinto de cero.

Max 3x1 + 2x2

s.a: 2x1 + x2 <= 2

3x1 + 4x2 >= 12

x1,x2 >= 0
Llevamos el modelo a su forma estándar agregando X3 como variable de holgura de la restricción 1,

X4 como variable de exceso de la restricción 2 y X5 como variable artificial de la restricción 2 que nos

permita formar la base. De esta forma el modelo de la fase 1 queda definido por:

Min x5

s.a: 2x1 + x2 + x3 = 2

3x1 + 4x2 -x4 + x5= 12

x1,x2,x3,x4,x5 >= 0

Con tabla inicial:

X1 X2 X3 X4 X5

2 1 1 0 0 2

3 4 0 -1 1 12

0 0 0 0 1 0

Y tabla final de la fase 1:

X1 X2 X3 X4 X5

2 1 1 0 0 2

-5 0 -4 -1 1 4

5 0 4 0 0 -4

EJEMPLO PROBLEMA NO ACOTADO:

Esta situación se detecta cuando al realizar el cálculo de la variable que deja la base, todos los

elementos ykj de la columna j en la tabla, son negativos para j el índice de una variable no básica con

costo reducido negativo.

Max 2x1 + x2

s.a: x1 - x2 <= 10

2x1 <= 40

x1,x2 >= 0

Donde la tabla inicial del método simplex luego de agregar X3 y X4 como variables de holgura para las

restricciones 1 y 2 respectivamente es:

X1 X2 X3 X4

1 -1 1 0 10

2 0 0 1 40

-2 -1 0 0 0

Cabe destacar que en esta instancia ya se puede constatar que el problema es no acotado. X2 siendo

variable no básica los elementos de la respectiva columna son negativos o cero. Sin embargo, si el

usuario no se percata inmediatamente de esto, de todos modos llegará a la misma conclusión en la

iteración posterior, luego de hacer entrar X1 a la base como aquella variable no básica con costo

reducido más negativo.

MÚLTIPLES SOLUCIONES ÓPTIMAS

Esta situación se detecta cuando existen costos reducidos iguales a cero en una o más de las variables

no básicas óptimas.

Max 3x1 + 2x2

s.a: 5x1 + 2x2 <= 140

 3x1 + 2x2 <= 120

x1,x2 >= 0

Con tabla final del Método Simplex:

X1 X2 X3 X4

1 0 1/2 -1/2 10

0 1 -3/4 5/4 45

0 0 0 1 120

Nótese que se ha encontrado una de las infinitas soluciones óptimas para el problema (X1=10,

X2=45, V(P)=120). Esto debido a que la variable no básica X3 tiene costo reducido igual a cero en el

óptimo. ¿Cómo se puede obtener otro vértice con similar valor óptimo?. Se debe forzar la

entrada entonces de X3 a la base y sacar de la base una de las variables básicas actuales (si sigue el

cálculo notará que esta corresponde a X1). Finalmente, el nuevo vértice óptimo es X1=0, X2=60,

V(P)=120. El resto de las infinitas soluciones óptimas esta contenida en tramo que une los 2 vértices

tal como se muestra en la figura: