U2 DE

INVESTIGACION
PROGRAMACIÓN
OPERATIVA
LINEAL
 El modelo de programación (como sinónimo de
planeación) matemática se transforma en uno de
programación lineal cuando la función de utilidad que
se desea optimizar es una función lineal y las
ecuaciones o inecuaciones que representan las
restricciones son todas de primer grado.
(PL) FO: Maximizar σ𝑛𝑗=1 𝑐𝑗. 𝑋𝑗 = 𝑍

Comencemos…. s.a.
σ𝑛𝑗=1 𝑎𝑖𝑗. 𝑋𝑗 ≤ 𝑏𝑖 𝑖 = 1, … , 𝑚
𝑋𝑗 ≥ 0 j = 1, … , 𝑛
donde 𝑎𝑖𝑗, 𝑏𝑖 𝑦 𝑐𝑗 son constantes reales, con 𝑖 = 1, … , 𝑚
y j = 1, … , 𝑛
 SUPOSICIONES DE PROPORCIONALIDAD Y
DE ADITIVIDAD
El hecho de que la F.O. deba ser una función lineal de las variables de decisión tiene 2 Suposición de
consecuencias: proporcionalid
1) La contribución de la FO para cada variable de decisión es proporcional al valor de esta. ad de la PL
Ej. Si hago 2 unidades y cada una aporta $5 => $10, si hago 5 unidades gano $25
2) La FO para cualquier variable es independiente de los valores de las otras variables de
decisión
De manera similar, el hecho de que cada restricción de PL debe ser una desigualdad lineal
o una ecuación lineal tiene 2 consecuencias: Suposición
1) La contribución de cada variable del 1er. Miembro de cada restricción es proporcional aditiva e la PL
al valor de la variable. Si necesito 2 unidades de MP para hacer una silla necesito 6 para
hacer 3 sillas.
2) La contribución de cada variable al primer miembro de cada restricción es
independiente de los valores de la variable
 Una vez planteado el problema como uno de PL, la
búsqueda de la solución óptima, si existe, se realiza
con un método de optimización.

Continuemos… Dependiendo del número de variables de decisión,

podemos usar el método gráfico (para dos variables) o
el método simplex (para más de dos variables).
 La compañía Giapetto fabrica 2 tipos de juguetes de madera:
soldados y trenes. Los precios de ventas son $27.00 y $21.00
respectivamente. Los costos de materiales (materia prima) son de
$10.00 y $9.00 respectivamente. Los costos de mano de obra y
otros variables de fabricación son $14.00 y $10.00
respectivamente. La elaboración de estos juguetes requiere de

Veamos un dos tipos de mano de obra especializada: carpintería y pintura.

Un soldado requiere de 1 hora de carpintería y 2 de pintura. Un
tren por su parte requiere 1 hora en cada departamento. Cada

ejemplo semana Giapetto puede obtener toda la materia prima que desee,
pero solo cuenta con 80 horas para carpintería y 120 horas para
pintura. La demanda semanal de trenes es prácticamente
ilimitada, sin embargo, la demanda semanal de soldados no es
mayor de 40 unidades. Giapetto desea maximizar su ganancia
semanal (Venta – Costo de lo vendido). Se pide formular un
modelo matemático para la situación de la compañía Giapetto
que puede ser usado para maximizar la ganancia semanal.
 Definir las variables
Definición de variables de decisión:
x = el número de soldados fabricados por semana
y= el número de trenes fabricados por semana

Formulación de la Función Objetivo:

Maximizar la función de Utilidad

Función de Utilidad = (Ventas semanales) – (costos por compra de materiales) – (otros costo variables).

Ventas semanales = 27*x + 21*y

Costos de materiales = 10*x + 9*y
Otros costos variables = 14*x + 10*y
Entonces la Función Objetivo es igual a: [27*x + 21*y] – [10*x + 9y] – [14*x + 10*y] = 3*x + 2*y

Atención con las unidades: Debe existir coherencia dimensional

$ 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠 $ $
Ejemplo 3 𝑠𝑜𝑙𝑑𝑎𝑑𝑜 * x = 𝑠𝑒𝑚𝑎𝑛𝑎 → la F.O dará un resultado expresado en 𝑠𝑒𝑚𝑎𝑛𝑎
𝑠𝑒𝑚𝑎𝑛𝑎
 Definir las restricciones
Definición de las restricciones
1. Restricciones de tiempo (capacidad por semana)
1. El tiempo disponible en carpintería está limitado a 80 horas por semana.
2. El tiempo disponible en pintura está limitado a 120 horas por semana.
2. Restricciones de mercado.
1. No tiene sentido producir más de 40 soldados por semana debido a la limitante de mercado.

Escribir las restricciones en término de las variables de decisión definidas

1*x + 1*y < 80
2*x + 1*y < 120
1*x < 40

Restricciones de No Negatividad
Las variables de decisión deben tomar valores no-negativos, puesto que no podemos producir un número de juguetes negativo
(salvo que se acepten ordenes sin inventario). Por tanto, cada variable tiene asignada una restricción de no-negatividad.
X≥0
Y≥0
 Modelo Final

Max 3 x + 2 y
st
x + y ≤ 80
2 x + y ≤ 120
x ≤ 40
x, y ≥ 0
Solución Gráfica
ASI SE DEFINE LA REGION
FACTIBLE
AHORA DESPLAZAMOS LA RECTA DE ISOUTILIDAD HASTA EL PUNTO MAS LEJANO
DEL POLIGONO FORMADO POR LAS RESTRICCIONES PARA ASI ENCONTRAR LA
SOLUCION OPTIMA

De acuerdo a la imagen la
solución óptima es el
Punto C o sea (40,40).
Fabricar 40 soldados y 40 trenes.
Si lo reemplazamos en la Función
Objetivo tendremos una ganancia
semanal de $ 200
Stratton Company produce dos tipos básicos
de tubo de plástico. Tres recursos son
fundamentales para la producción de esos Producto

tubos: las horas de extrusión, las horas de Disponibilidad de

embalaje y un aditivo especial para las Recurso Tipo1 Tipo2 recursos

materias primas del plástico. Extrusión 4hr 6hr 48 hr

Los siguientes datos representan la situación Embalaje 2hr 2hr 18 hr

correspondiente a la semana próxima. Todos Mezcla

aditiva 2lb 1lb 16 lb
los datos se expresan en unidades de 100
pies de tubo.
 EJEMPLO

Un fabricante de bombones entrega a sus productos en cajas de un Kg., en dos variantes, A y B. Las
dos variantes poseen tres tipos de bombón a saber, de licor, de nuez y de fruta. La caja tipo A,
contiene 300 grs. de bombones de licor, 500 grs. de bombones de nuez y 200 grs. de bombones de
fruta. La caja de tipo B contiene 400 grs., 200 grs. y 400 grs. de cada tipo de bombón
respectivamente. La utilidad por cada caja del tipo A es de $24 y para la caja del tipo B de $18. El
fabricante dispone de 100 Kg. de bombones de licor, 120 Kg. de bombones de nuez y 100 Kg. de
bombones de fruta. Determinar en forma gráfica y analítica la cantidad de cajas que se pueden armar
en esta situación, para que el beneficio sea óptimo. ¿Existen sobrantes?. ¿De qué tipo de Bombón?.
¿Cuántos grs. (puede expresarse en kg, dependiendo la unidad a utilizar en el problema)?
 MODELOS SIN SOLUCIÓN ÓPTIMA

1) Soluciones múltiples o alternativas: Cuando la función objetivo es paralela a una

restricción que se satisface en el sentido de la igualdad a través de la solución óptima, la
función objetivo tomará el mismo valor óptimo en más de un punto de la solución. Por esta
razón reciben el nombre de Múltiples alternativas óptimas.
2) No acotado: Ocurre cuando el objetivo puede crecer infinitamente (objetivo a maximizar).
3) No factible: Ocurre cuando en el modelo no hay ningún punto de factible.
 Un problema de minimización

Dorian Auto fabrica automóviles de lujo y camiones. La compañía opina que sus clientes más
idóneos son hombres y mujeres de altos ingresos. Para llegar a estos grupos, Dorian Auto ha
emprendido una ambiciosa campaña publicitaria por TV, y decidió comprar comerciales de un
minuto en dos tipos de programas de comedia y juegos de fútbol americano. Cada comercial en
programas de comedia lo ven 7 millones de mujeres de altos ingresos y 2 millones de hombres de
altos ingresos. 2 millones de mujeres de altos ingresos y 12 millones de hombres de altos ingresos ven
cada comercial en juegos de fútbol. Un anuncio de un minuto en los programas de comedia cuesta
50.000 dólares y un comercial de un minuto en el juego de fútbol cuesta 100.000 dólares. A Dorian
le gustaría que por lo menos 28 millones de mujeres de altos ingresos y 24 millones de hombres de
altos ingresos vieran sus comerciales.
Determine gráficamente que debería hacer Dorian Auto para alcanzar sus requerimientos
comerciales a un costo mínimo
El MODELO FINAL SERIA

Minimizar Z= 50 x + 100 y
Sujeto a
7 x + 2y ≥ 28
2 x + 12 y ≥ 24
x, y ≥ 0

Ahora desplacemos la recta de Isocostos

Región Factible Con esto la solución encontrada es el punto B
y le corresponden estos valores:
X= 3,6 e Y= 1,4
Con lo que los costos mínimos son de $ 320
 RESUMEN DE LOS PASOS DEL MÉTODO
GRÁFICO
El método se resume en los pasos siguientes:

Paso 1. Transformar las desigualdades de las restricciones en ecuaciones.

Paso 2. Representar en el primer cuadrante del plano cartesiano (debido a las restricciones de no negatividad) la
ecuaciones obtenidas en Paso 1.

Paso 3. Graficar las desigualdades que dieron origen a las ecuaciones en Paso 1. Las intersecciones de estas
regiones dan origen a la RF. En este paso se sabrá si el problema es o no factible, es decir, si F = ∅. Si hay
factibilidad, entonces se continúa en Paso 4. En caso contrario, F = ∅ y el problema es infactible y no existe
solución para el problema.

Paso 4. Graficar la ecuación que representa a la FO haciendo Z = 0. A continuación se deben trazar rectas
paralelas a Z = 0, desplazándose por las vértices (curvas de nivel) de la RF hasta encontrar el vértice más alejado
del origen (en un problema máximo) o más cercano al origen en un problema de mínimo.
 PRACTICAMOS
La corporación Electrocomp fabrica dos productos eléctricos: acondicionadores de aire y
ventiladores de gran tamaño. El proceso de ensamblado para cada uno es similar en
tanto que requieren una cierta cantidad de cableado y de perforación. Cada
acondicionador de aire tarda 3 horas de cableado y 2 horas de perforación. Cada
ventilador tiene que pasar por 2 horas de cableado y 1 hora de perforación. En el
siguiente periodo de producción, están disponibles 240 horas de tiempo de cableado y
hasta 140 horas de tiempo de perforación que se pueden utilizar. Cada aparato de
acondicionador de aire vendido genera una utilidad de $25. Cada ventilador ensamblado
se puede vender con una utilidad de $15. Formule y resuelva esta situación de la mezcla
producción de PL para encontrar la mejor combinación de acondicionadores de aire y
ventiladores que genera la mayor utilidad. Use el método gráfico
 EJEMPLOS 1
La gerencia de Electrocomp se da cuenta que olvidó incluir dos restricciones
fundamentales. En particular, la gerencia decide que debería haber un número mínimo
de equipos de acondicionador de aire producidos con la finalidad de cumplir un
contrato. Además, debido a un exceso de oferta de ventiladores en el periodo anterior,
se debería poner un límite en el número total de ventiladores producidos.
a) Si Electrocomp decide que se deberían fabricar por lo menos 20 acondicionadores
de aire, pero no más de 80 ventiladores, ¿cuál sería la solución óptima? ¿Cuánta
holgura hay para cada una de las cuatro restricciones?
b) Si Electrocomp decide que se deberían fabricar por lo menos 30 acondicionadores
de aire, pero no más de 50 ventiladores, ¿cuál sería la solución óptima? ¿Cuánta
holgura hay en cada una de las cuatro restricciones en la solución óptima?
El decano del Western College of Business debe planear la oferta de cursos de la
escuela para el semestre de otoño. Las demandas de los estudiantes hacen que sea
necesario ofrecer un mínimo de 30 cursos de licenciatura y 20 de posgrado durante el
semestre. Los contratos de los profesores también dictan que se ofrezcan al menos 60
cursos en total. Cada curso de licenciatura impartido cuesta a la universidad un
promedio de $2,500 en salarios de docentes, y cada curso de posgrado cuesta $3,000.
¿Cuántos cursos de licenciatura y posgrado se deberían impartir en otoño, de manera
que los salarios totales del profesorado se reduzcan al mínimo?
 EJEMPLO 2
El candidato a la alcaldía en un pequeño pueblo asignó $40,000 para propaganda de
último minuto en los días anteriores a la elección. Se utilizarán dos tipos de anuncios:
radio y televisión. Cada anuncio de radio cuesta $200 y llega a unas 3,000 personas.
Cada anuncio de televisión cuesta $500 y llega a un estimado de 7,000 personas. En
la planeación de la campaña de propaganda, la jefa de la campaña quiere llegar a
tantas personas como sea posible, aunque ha establecido que se deben utilizar al
menos 10 anuncios de cada tipo. Asimismo, el número de anuncios de radio debe ser
al menos tan grande como el número de anuncios de televisión. ¿Cuántos anuncios de
cada tipo se deberían utilizar? ¿A cuántas personas llegarán?
 EJEMPLO 3
La corporación MSA Computer fabrica dos modelos de minicomputadoras, Alpha 4 y
Beta 5. La empresa contrata a cinco técnicos, que trabajan 160 horas cada mes, en su
línea de ensamble. La gerencia insiste en que se mantenga pleno empleo (es decir, las
160 horas de tiempo) para cada trabajador durante las operaciones del siguiente mes.
Se requiere 20 horas de trabajo para ensamblar cada equipo Alpha 4 y 25 horas de
trabajo para ensamblar cada modelo Beta 5. MSA desea producir al menos 10 Alfa 4 y
por lo menos 15 Beta 5 durante el periodo de producción. Las Alfa 4 generan $1,200
de utilidad por unidad, y las Beta 5 producen $1,800 cada una. Determine el número
más rentable de cada modelo de minicomputadora que se debe producir durante el
próximo mes.
 RESOLVEMOS DISTINTOS TIPOS DE
PROBLEMAS DE PL
PROBLEMAS DE DIETA
PROBLEMAS DE HORARIO DE TRABAJO
PROBLEMAS DE MEZCLA
PROBLEMAS DE PRODUCCIÓN
PROBLEMAS DE INVENTARIO
PROBLEMAS DE TRANSPORTE
PROBLEMAS DE ASIGNACION
PROBLEMAS DE TRASBORDO
 EJEMPLO
Un fabricante de bombones entrega a sus productos en cajas de un Kg., en dos variantes, A y B. Las
dos variantes poseen tres tipos de bombón a saber, de licor, de nuez y de fruta. La caja tipo A,
contiene 300 grs. de bombones de licor, 500 grs. de bombones de nuez y 200 grs. de bombones de
fruta. La caja de tipo B contiene 400 grs., 200 grs. y 400 grs. de cada tipo de bombón
respectivamente. La utilidad por cada caja del tipo A es de $120 y para la caja del tipo B de $90. El
fabricante dispone de 100 Kg. de bombones de licor, 120 Kg. de bombones de nuez y 100 Kg. de
bombones de fruta. Determinar en forma gráfica y analítica la cantidad de cajas que se pueden armar
en esta situación, para que el beneficio sea óptimo. ¿Existen sobrantes?. ¿De qué tipo de Bombón?.
¿Cuántos grs. (puede expresarse en kg, dependiendo la unidad a utilizar en el problema)?

Max 120 x + 90 y
St
0.3 x+0.4 y <=100
0.5 x+0.2 y <=120
0.2 x+0.4 y <=100
 FORMAS DE FORMULAR UN MODELO DE PL
Max 80 x1 + 88 x2
FORMA NATURAL → Las restricciones son con ≤, = . st≥
x1 + 2 x2 <= 120
x1 + x2 = 90
FORMA CANÓNICA 3 x1 + x2 >= 50

Min 50 x + 80 y
Maximización: Todas las restricciones se expresan como ≤ Sujeto a
x + 2 y >= 120
Minimización: Todas las restricciones son de ≥ x + y >= 90

Max 50 x + 80 y
FORMA ESTÁNDAR st
Sabemos que tenemos variables de hogura (s1 y s2)
x + 2 y + s1 = 120
Y las variables de exceso (e3)
Todas las restricciones son de = x + y + s2 = 90
3 x + y – e3 = 50
FORMA CANÓNICA DE UNA MAXIMIZACIÓN

FORMA NATURAL FORMA CANÓNICA

Max 80 x1 + 88 x2 Max 80 x1 + 88 x2 Max 80 x1 + 88 x2
st
st st
x1 + 2 x2 <= 120
x1 + 2 x2 <= 120 - 3 x1 - x2 <= -50 x1 + 2 x2 <= 120
3 x1 + x2 >= 50 La igualdad es equivalente a decir que - 3 x1 - x2 <= -50
x1 + x2 <= 90
x1 + x2 = 90 x1 + x2 <= 90
x1 + x2 >= 90
A esta última debo cambiarla y queda - x1 - x2 <= -90
- x1 - x2 <= -90
 FORMA MATRICIAL
Forma Natural Forma Estándar

Max 80 x1 + 88 x2 Max 80 x1 + 88 x2+0s1+0s2 𝑥1

st st
x1 + 2 x2 <= 120 x1 + 2 x2 +s1= 120 1 2 1 0 𝑥2 120
x1 + x2 <= 90 x1 + x2 +s2= 90
× 𝑠 =
1 1 0 1 1 90
𝑠2

𝑚 = 𝑒𝑐𝑢𝑎𝑐𝑖𝑜𝑛𝑒𝑠 → 2 𝑦 𝑛 𝑖𝑛𝑐ó𝑔𝑛𝑖𝑡𝑎𝑠 = 4 𝑥1
𝑍 = 80 88 0 0 × 𝑥2
𝑠1
𝑠2
 Soluciones básicas factibles
Max 80 x + 88 y
st
x + 2 y <= 120 Max 80 x + 88 y Solución No factible
x + y <= 90 st
3 x + y >= 50 x + 2 y + s1 = 120
x + y + s2 = 90
3 x + y – e3 = 50

Solución factible

Es un sistema de ecuaciones lineales

Con 5 variables o incógnitas (n)
Con 3 restricciones o ecuaciones (m)
Como hay más incógnitas que ecuaciones tendremos infinitas soluciones factibles que son las que
forman parte del polígono que se muestra
Un modelo tiene n-m= 2 variables se anulan para ser una SBF
Los vértices de este
polígono son: Max 80 x + 88 y
(20,0), (0,50); (0,60); st
x + 2 y + s1 = 120
(60,30); (90,0)
x + y + s2 = 90
Donde n=5 y m= 3 S1
S2 3 x + y – e3 = 50
Llamaremos solución
básica para un problema
donde tenemos n variables SOLUCIONES
BÁSICAS FACTIBLES
y m restricciones a aquella
donde se anulan por lo
menos n-m variables,
(5 - 3 = 2)
A→ x=0; E3=0
E3
B→ x=0; S1=0
C→ s1=0; s2=0
D→ y=0; s2=0
E→ y=0; e3=0
 Soluciones básicas No factibles

El punto en el círculo amarillo S1 S2

tiene dos variables que se anulan SOLUCIONES
BÁSICAS NO
x y s2, es una solución básica FACTIBLES
pero no factible
Lo mismo sucedería con el punto E3
dentro del círculo azul
¿Qué variables se anulan?
 Max 20 x + 30 y
st
Encontremos una solución al siguiente modelo x + 2 y + s1 = 120 Hagamos x e y iguales a cero
x + y + s2 = 90
2x + 0,5 y + s3 = 60
𝑥 0
𝑦 0 Esta sería el origen de coordenadas donde no tendríamos
𝑠1 120 Ganancia, Z=0 pero es una SBF. Este es el primer punto que toma el algoritmo para
𝑠2 90 iniciar
𝑠3 60

30
0
90 Aquí Z= 20*30+30*0= 600 → SBF
60
0
 FORMULACIÓN SOLUCIÓN INTERPRETACIÓN

Modelado Método Simplex

El algoritmo simplex consiste en pasar de una solución básica factible (vértice) a otra adyacente (solo
difiere en una columna), de modo que el valor de la FO mejore hasta encontrar el óptimo si existe. El
algoritmo solo explora soluciones básicas factibles y para cada solución genera una tabla
Lo veremos a través de un ejemplo

Resolver este modelo mediante el método simplex

Max 50 x + 80 y

Sujeto a
x + 2 y <= 120
x + y <= 90
 Seguimos con el ejemplo
Max 120 x + 90 y
Forma Natural St
Forma Estándar 0.3 x+0.4 y <=100
0.5 x+0.2 y <=120
0.2 x+0.4 y <=100
 PASOS
Convertir el PL en PL Estándar:
Normalizar el signo de los términos independientes: Como los términos independientes de todas las restricciones son positivos no es
necesario hacer nada. En caso contrario habría que multiplicar por "-1" en ambos lados de la inecuación (teniendo en cuenta que esta
operación también afecta al tipo de restricción).
En nuestro ejemplo todos los lados derechos son positivos
Normalizar las restricciones: Se convierten las inecuaciones en ecuaciones agregando variables de holgura, exceso y artificiales según la
tabla siguiente:

Tipo de desigualdad Tipo de variable que aparece

Se resta una variable de exceso y se agrega una

≥
variable artificial
= Se agrega una variable artificial

≤ Se suma una variable de holgura

Para nuestro ejemplo: x + 2 y <= 120 → x + 2y + s1 = 120

x + y <= 90 → x + y + s2 = 90
Siendo s1 y s2 dos variables de holgura
Así el problema queda escrito en su forma estándar
Max Z= 50 x + 80 y + 0 s1 + 0 s2
Sujeto a
x + 2 y + s1 = 120
x + y + s2 = 90
Variables básicas son
- Igualar la Función Objetivo a cero que se denomina Renglón cero las que no se anulan
Z – 50 x – 80 y – 0 s1 – 0 s2= 0
Y completar cada renglón con una restricción
Variable Básica o
Renglón Z X Y S1 S2 LD variables que están en la
base.
0 1 -50 -80 0 0 0 z=0
1 0 1 2 1 0 120 s1 = 120
2 0 1 1 0 1 90 s2=90
Nota: Observamos que las variables básicas en la base son versores o vectores unitarios. Y los versores
típicamente tienen coeficiente cero en la FO. Ver s1 y s2
Recordar que para tener una base se requiere tener n-m variables nulas (4-2=2)
 2) Obtener una solución básica factible (sbf) si es posible a partir de la forma estándar.
Que si miramos como nos queda la tabla la solución sería:
Z=0 x=y=0 s1= 120 y s2= 90

Asi 𝑽𝑩 = 𝒔𝟏, 𝒔𝟐 𝑽𝑵𝑩 = 𝒙, 𝒚

3) Determinar si la sbf actual es óptima

Aquí si retomamos la FO Z= 50 x + 80 y vemos que incrementando x o y en una unidad
obtendremos un valor superior de Z, por lo tanto tomamos “y” como variable entrante porque es
la que incrementa más a Z. Visto desde el tablero es el coeficiente más negativo del Renglón 0.
(Porque es una maximización)

Variables No Básicas

Renglón Z X Y S1 S2 Resultado Variable Básica

Variables 0 z 1 -50 -80 0 0 0

z=0
Básicas
1 s1 0 1 2 1 0 120 S1 = 120
2 s2 0 1 1 0 1 90
s2=90
 Entonces este valor marca la columna pivote. Luego calculamos la prueba del cociente que es igual a Resultado/Columna
pivote , para decidir la variable básica que saldrá de la nueva solución.
Rengló
Z X Y S1 S2 Resultado
n
0 z 1 -50 -80 0 0 0
1 s1 0 1 2 1 0 120 120/2= 60
2 s2 0 1 1 0 1 90 90/1=90
Seleccionamos la de menor valor positivo, es decir, la variable que deberá salir es la que menos le aporta a la solución, o sea s1, y
así definimos la fila pivote. El cociente más pequeño es el valor más grande de la variable entrante que conservará todas las
𝑏
variables básicas actuales no negativas, es decir el cociente más pequeño no negativo. 𝜃 = 𝑚𝑖𝑛 𝑖 siendo bi = lados derechos y
𝐴𝑖
Ai la columna de la variable que ingresa

Renglón Z X s1 S1 S2 Resultado Cociente Ld/S1

0 z 1 -50 -80 0 0 0
1 y 0 1 2 1 0 120
2 s2 0 1 1 0 1 90
Entonces el elemento pivote es el 2.
Como sabemos el primer paso es convertir el 2 en 1 a través de operaciones elementales de renglón, para ello debemos
multiplicar toda la ecuación por ½.
Actualizamos 𝑉𝐵 = 𝑦, 𝑠2 𝑉𝑁𝐵 = 𝑥, 𝑠1
Recordamos el tablero original

Renglón Z X Y S1 S2 Resultado
0 z 1 -50 -80 0 0 0
1 s1 0 1 2 1 0 120 120/2= 60
2 s2 0 1 1 0 1 90 90/1=90

Operaciones Renglón Z X Y S1 S2 Resultado

0 z
½ * R1 1 y 0 ½ 1 ½ 0 60
2 s2
El siguiente paso será hacer nulos los demás elementos de la columna pivote, para ello continuamos con las
Operaciones Elementales
Operaciones Renglón Z X Y S1 S2 Resultado
(+80)*R1+R0 0 z 1 -10 0 40 0 4800
1 y 0 ½ 1 ½ 0 60
(-1)*R1+R2 2 s2 0 ½ 0 -½ 1 30

X= 0 Y=60 s2=30 Z=4800

4) Si la solución básica factible (sbf) actual no es óptima, entonces se determina cuál variable no básica se debe
transformar en variable básica y cual variable básica se debe transformar en no básica con el objeto de hallar una
nueva sbf con un mejor valor de la función objetivo.
Asimismo la condición de parada si el objetivo es la maximización, cuando en el R0 no existe ningún valor
negativo, se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z es la solución óptima del
problema.
Esta es la nueva matriz y los coeficientes de la variable de decisión son -10 y 0 en consecuencia hay que continuar
hasta que ellos sean 0 o mayores a cero
 Volvemos a elegir el coeficiente más negativo o sea -10 y esa será la nueva columna pivote. Ahora x es la
variable entrante o sea básica
Operaciones Renglón Z X Y S1 S2 Resultado
0 z 1 -10 0 40 0 4800
1 y 0 ½ 1 ½ 0 60
2 s2 0 ½ 0 -½ 1 30

Calculamos R/columna pivote y seleccionamos la de menor valor, es decir 60 que le corresponde a s2.

Operaciones Renglón Z X Y S1 S2 Resultado

0 z 1 -10 0 40 0 4800
60/(1/2)=120 1 y 0 ½ 1 ½ 0 60
30/(1/2)= 60 2 x 0 ½ 0 -½ 1 30

Actualizamos 𝑽𝑩 = 𝒙, 𝒚 𝑽𝑵𝑩 = 𝒔𝟏, 𝒔𝟐

5) Aplicar OER para encontrar la nueva sfb con el mejor valor de la función objetivo. Regresar
el punto 3.
 Operaciones Renglón Z X Y S1 S2 Resultado
0 z 1 -10 0 40 0 4800
1 y 0 ½ 1 ½ 0 60
2*R2 2 x 0 1 0 -1 2 60

Operaciones Renglón Z X Y S1 S2 Resultado

+10*R2+R0 0 z 1 0 0 30 20 5400
-1/2*R2+R1 1 Y 0 0 1 1 -1 30
2*R2 2 X 0 1 0 -1 2 60

Como vemos ahora todos los coeficientes de la función objetivo son no negativos, en consecuencia,
termina el algoritmo
 ¿Como leemos la solución encontrada?

Renglón Z X Y S1 S2 Resultado

0 z 1 0 0 30 20 5400

1 Y 0 0 1 1 -1 30

2 x 0 1 0 -1 2 60

Z= 5400 Y= 30 X = 60
PRACTICAMOS…. El caso de giapetto

Modelo

Max 3 S + 2 T
st
2 S + T ≤ 100
S + T ≤ 80
S ≤ 40
S,T ≥ 0
 Forma Estandar

Z-3S-2T=0

2 S + T + s1 = 100
S + T + s2 = 80
S + s3 = 40
Tablero inicial
RESULTAD
Renglon Z S T S1 S2 S3 O
R0 1 -3 -2 0 0 0 0
R1 0 2 1 1 0 0 100
R2 0 1 1 0 1 0 80
R3 0 1 0 0 0 1 40
THE TABLEAU

ROW (BASIS) S T SLK 2 SLK 3 SLK 4

1 ART -3.000 -2.000 0.000 0.000 0.000 0.000
2 SLK 2 2.000 1.000 1.000 0.000 0.000 100.000
3 SLK 3 1.000 1.000 0.000 1.000 0.000 80.000
4 SLK 4 1.000 0.000 0.000 0.000 1.000 40.000
ART ART -3.000 -2.000 0.000 0.000 0.000 0.000
 PRACTICAMOS

2.- Dakota Fortune Company fabrica escritorios, mesas y sillas. La manufactura de cada tipo de mueble requiere
madera y dos tipos de trabajo especializado: acabado y carpintería. La cantidad que se necesita de cada recurso
para fabricar cada tipo de mueble es la siguiente:

Recurso Escritorio Mesa Silla

Madera 8 pies tabla 6 pies tabla 1 pie tabla
Horas de acabado 4 horas 2 horas 1.5 horas
Horas de carpintería 2 horas 1.5 horas 0.5 horas

Por ahora, se disponen de 48 pies tabla de madera, de 20 horas de acabado y 8 horas de carpintería. Se vende un
escritorio a 60 dólares, una mesa a 30 dólares y una silla a 20 dólares. Dakota opina que la demanda de escritorios
y sillas es ilimitada,, pero cuanto mucho se puede vender 5 mesas. Puesto que los recursos ya se compraron,
Dakota quiere maximizar el ingreso total.
 MODELO

Variables
x1 = escritorios x2 = mesas x3 = sillas

Max 60x1 + 30x2 + 20x3

s.a.:
8x1 + 6x2 + x3 ≤ 48 (Restricción de la madera)
4x1 + 2x2 + 1,5x3 ≤ 20 (Restricción del acabado)
2x1 + 1,5x2 + 0,5x3 ≤ 8 (Restricción de la carpintería)
x2 ≤ 5 (Restricción de la demanda de mesas)
x1, x2, x3 ≥ 0
 OBTENEMOS LAS TABLAS DEL SIMPLEX EN
EL LINDO

1) Cargamos el modelo como siempre

2) Antes de resolver hacemos Alt+7 para
visualizar el tablero inicial
3) Elegimos el pivote con Ctrl+N
4) Ejecutamos y volvemos a hacer Alt+7
para ver el segundo tablero.

Si en cambio resolvemos primero el

modelo y luego pedimos visualizar el
tablero nos muestra solo la ultima tabla
del Simplex
LP OPTIMUM FOUND AT STEP 2

OBJECTIVE FUNCTION VALUE

1) 280.0000

VARIABLE VALUE REDUCED COST

X1 2.000000 0.000000
X2 0.000000 5.000000
X3 8.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 24.000000 0.000000
3) 0.000000 10.000000
4) 0.000000 10.000000
5) 5.000000 0.000000

NO. ITERATIONS= 2
 Una minimización
2 OPCIONES:
1) Transformar un problema de Minimización en uno de Maximización, para ello multiplicamos la FO del
problema de Minimización por -1 y resolvemos como uno de Max. Con una FO – Z. La solución óptima para
el problema de Max nos dará una solución óptima para el problema de Min.
RECORDAR: El valor z óptimo para el problema de Min = -(valor z óptimo para el problema de Max).

Min z = 3 x1 + 8 x2 + 3 x3 + 8 x4 Max - z = - 3 x1 - 8 x2 - 3 x3 - 8 x4
St St
3 x1 + 2 x2 + x3 >=50 3 x1 + 2 x2 + x3 >=50
2 x2 + 3 x3 + 4 x4 >=60 2 x2 + 3 x3 + 4 x4 >=60
2) Realizamos un cambio simple en el algoritmo para poder resolver directamente:
Modificamos el paso 3 asi:
- Si todas las variables no básicas del renglón 0 tienen coeficientes no positivos, entonces la sbf actual es óptima.
- Si cualquier variable no básica en el renglón 0 tiene coeficiente positivo, seleccione la variable con el coeficiente
“más positivo” en el renglón 0 para que entre a la base.
- La condición de parada será que todos los valores del Renglón 0 sean negativos. Asi obtenemos una solución
óptima.

Esta modificación funciona porque al incrementar una variable no básica con un coeficiente positivo en el renglón
0 disminuirá Z
 Veamos un ejemplo
Supongamos este modelo

Min z = 2 x1 - 3 x2 Max - z = -2 x1 + 3 x2
st st
x1 + x2 <= 4
Es equivalente a
x1 + x2 <= 4
X1 - x2 <=6 x1 - x2 <=6

- z + 2 x1 - 3 x2=0
1) Verificamos que los lados derechos sean positivos
2) Pasamos el modelo a su forma estándar: restricciones y F.O st
x1 + x2 + s1 = 4
x1 - x2 + s2 =6
 Resolución con el método I
R Variable "-Z" x1 x2 s1 s2 Resultado
R0 "-Z" 1 2 -3 0 0 0
R1 s1 0 1 1 1 0 4
R2 s2 0 1 -1 0 1 6
Buscamos el valor de Z más negativo para saber que variable ingresa
Hacemos la prueba del cociente para saber que variable sale
R Variable "-Z" x1 x2 s1 s2 Resultado
R0 "-Z" 1 2 -3 0 0 0
R1 s1 0 1 1 1 0 4
R2 s2 0 1 -1 0 1 6
Como el pivote ya es 1, solo resta hacer ceros toda la columna

R Variable "-Z" x1 x2 s1 s2 Resultado

R0 "-Z" 1 5 0 3 0 12
R1 x2 0 1 1 1 0 4
R2 s2 0 2 0 1 1 10

Como todos los valores del renglón 0 son positivos el algoritmo para con esta solución optima
-z = 12 x2= 4 s2 = 10 x1 = s1 =0
Por el cambio realizado, la verdadera solución es : z= -12 x2=4 s2= 10 x1=s1=0
 Resolución con el método II
R Variable Z x1 x2 s1 s2 Resultado Prueba
R0 Z 1 -2 3 0 0 0
R1 s1 0 1 1 1 0 4
R2 s2 0 1 -1 0 1 6
Buscamos el valor de Z más "positivo" para saber que variable ingresa
Hacemos la prueba del cociente para saber que variable sale
R Variable Z x1 x2 s1 s2 Resultado Prueba
R0 Z 1 -2 3 0 0 0
R1 s1 0 1 1 1 0 4 4
R2 s2 0 1 -1 0 1 6 -6
Como el pivote ya es 1, solo resta hacer ceros toda la columna
R Variable Z x1 x2 s1 s2 Resultado Prueba
R0 Z 1 -5 0 -3 0 -12
R1 x2 0 1 1 1 0 4
R2 s2 0 2 0 1 1 10
Como todos los valores del renglón 0 son no positivos el algoritmo para con esta solución optima
z = -12 x2= 4 s2 = 10 x1 = s1 =0
 Ejemplos
Min 120 x + 90 y
St
0.3 x+0.4 y >=100
0.5 x+0.2 y >=120
0.2 x+0.4 y >=100

2) Una empresa produce concreto usando los ingredientes A y B. Cada kilo de ingrediente A cuesta $ 60 y
contiene 4 unidades de arena fina, 3 unidades de arena gruesa y 5 unidades de piedras. Cada kilo de
ingrediente B cuesta $ 100 y contiene 3 unidades de arena fina, 6 unidades de arena gruesa y 2 unidades de
piedras. Cada saco de concreto debe contener por lo menos 12 unidades de arena fina, 12 unidades de arena
gruesa y 10 unidades de piedras. Formule un modelo de programación lineal y resuélvalo gráficamente.
 Método de la gran M
Como ya vimos el simplex para comenzar necesita de una sbf, la que hasta el momento se
consigue utilizando las variables de holgura como si fueran básicas.
¿Qué pasa con las restricciones de >= o de igualdad?

Aquí no es fácil encontrar una sbf inicial por lo que deberemos utilizar el método de la gran M ó
el Simplex de Dos Fases.
El método de la gran M es una versión del algoritmo simplex que determina la primera sbf
mediante la suma de variables “artificiales”

Analicemos este problema extraído de Winston ( 2005)

BEVCO elabora una bebida gasificada sabor a naranja que se llama orange mediante la
combinación de agua gasificada de naranja y jugo de naranja. Cada onza de agua gasificada de
naranja contiende 0.5 onzas de azúcar y 1 mg de vitamina c, cada onza de jugo de naranja contiene
0.25 onzas de azúcar y 3 mg de vitamina C. Bevco gasta 2 centavos por producir 1 onza de agua
gasificada de naranja y 3 centavos por elaborar 1 onza de jugo de naranja. El departamento de
mercadotecnia de Bevco decidió que la botella de 10 onzas de orange debe contener por lo menos
20 mg de vitamina c y cuanto mucho 4 onzas de azúcar.
Variables
x1= cantidad de onzas de agua gasificada de naranja en una botella de Orange
x2 = cantidad de onzas de jugo de naranja en una botella de Orange

Modelo Modelo en forma estandar

Z – 2 x1 - 3 x2 = 0
Min 2 x1 + 3 x2 st
st ½ x1 + ¼ x2 + s1 = 4
x1 + 3 x2 –e2 = 20
½ x1 + ¼ x2 <= 4 (Rest azúcar) X1 + x2 = 10
x1 + 3 x2 >= 20 (Rest vitamina C) Todas las variables son no negativas
x1 + x2 = 10 (Rest cont botella)
En la representación
gráfica de este problema de
Minimización, el punto
(0,0) no puede
ser la primera base
Analizamos las restricciones en busca de la primera solución básica factible

Forma Estándar Primera sbf si hacemos x1 = x2 = 0

½ x1 + ¼ x2 + s1 = 4 S1 = 4

x1 + 3 x2 –e2 = 20 - e2 = 20 ó e2 = -20
esto viola la restricción de no negatividad

X1 + x2 = 10
No tendríamos variables no básicas

Para resolver esto “creamos” unas variables básicas factibles para cada restricción que lo necesite y
las llamaremos variables artificiales y la denominaremos ai de tal manera de conseguir una base
factible ficticia
 Modelo en forma estándar con variables artificiales
Z – 2 x1 - 3 x2 = 0
st Sbf es: Z=0 s1 =4 a2= 20 a3= 10
½ x1 + ¼ x2 + s1 = 4
x1 + 3 x2 –e2 + a2 = 20
X1 + x2 + a3 = 10
Todas las variables son no negativas ¿Esta solución es válida para el modelo original?
Por ejemplo ¿contiene vitamina c?
La respuesta es NO para que cumpla con la solución
las variables artificiales deben ser cero. ¿cómo?

a) En un problema de Minimización asegurar que las variables artificiales sean cero si sumamos un
término Mai a la F.O. por cada variables artificial ai
b) En un problema de Maximización asegurar que las variables artificiales sean cero si sumamos un
término – Mai a la F.O. por cada variables artificial ai
Siendo M un número positivo muy grande, asi será muy costoso poner esa variable artificial como
parte de la solución. El Renglón O = Z – 2 x1 - 3 x2 – Ma2 – Ma3 = 0
Si a pesar de esto alguna variable obtiene un valor positivo en la solución significa que ese PL no tiene
solución factible
 EL METODO DE LA GRAN “M” PASO A PASO
Verificar que todos los LD sean positivos. (Recordemos que si multiplicamos por (-1) se invierte la
desigualdad e Identifique las restricciones de = o de >=
Escriba el modelo en su forma estándar es decir agregando una variable de holgura a las
desigualdades de <= ó reste una variable de excedente para cada restricción de >=.
Sume a las restricciones de >= ó = una variable artificial
Si el problema es de minimización sume por cada variable artificial un término Mai. Si el PL es de
maximización reste un término Mai por cada variable artificial a la función objetivo.
Verifique que en el Renglón cero tiene coeficientes nulos para las variables de holgura y M para
las variables artificiales, en donde M es un número extremadamente elevado para asegurar que las
variables artificiales se excluirán de la solución óptima.
Como cada variable artificial está en la base de inicio, todas las variables artificiales se tienen
que eliminar del Renglón 0 antes de empezar el simplex. De esta manera se asegura que se
empieza con una forma canónica. Al elegir la variable entrante, recordemos que M es un numero
positivo muy grande. Por ej, 4M -2 es más positivo que 3M + 900 y -6M-5 es más negativo que -
5M-40.
 Volvamos al ejemplo
PASO 4 (Agregamos Var artificiales a la FO)
PASO 2 (forma estándar)
Min Z = 2 x1 + 3 x2 + Ma2 + Ma3
Min Z = 2 x1 + 3 x2
Renglón 1 ½ x1 + ¼ x2 + s1 = 4
Renglón 1 ½ x1 + ¼ x2 + s1 = 4
Renglón 2 x1 + 3 x2 – e2 = 20
Renglón 2 x1 + 3 x2 – e2 + a2= 20
Renglón 3 x1 + x2 = 10
Renglón 3 x1 + x2 + a3 = 10
Todas las variables son no negativas

PASO 5 para eliminar las variables artificiales

PASO 3 (agregamos var artificiales)
del renglón 0, se reemplaza R0 por R0 + M
Min Z = 2 x1 + 3 x2 renglón 2 + M renglón 3
Renglón 1 ½ x1 + ¼ x2 + s1 = 4 Renglón 0 Z – 2 x1 - 3 x2 - Ma2 – Ma3 = 0
Renglón 2 x1 + 3 x2 – e2 + a2= 20
Renglón 3 x1 + x2 + a3 = 10 Renglón 2 Mx1 + 3 Mx2 – Me2 + Ma2= 20 M
Renglón 3 Mx1 + Mx2 + Ma3 = 10M
RENGLON 0

Z- 2 x1 - 3 x2 - Ma2 – Ma3 + Mx1 + 3 Mx2 – Me2 + Ma2 - 20 M + Mx1 + Mx2 + Ma3 - 10M = 0

Z + (-2+ M + M) X1 + (-3 + 3M + M) x2 – Me2 – 30 M = 0

Z + (-2+ 2 M) X1 + (-3 + 4M ) x2 – Me2 = 30 M En esta FO no hay variables artificiales

Tablero Inicial

R Variable Z x1 x2 s1 e2 a2 a3 Resultado
R0 Z 1 2 M-2 4M - 3 0 -M 0 0 30 M
R1 s1 0 1/2 1/4 1 0 0 0 4
R2 a2 0 1 3 0 -1 1 0 20
R3 a3 0 1 1 0 0 0 1 10

Buscamos el valor más positivo para la columna pivote → 4M -3 → ingresa x2

De la prueba del cociente gana 20/3 → sale a2
 Variabl Resultad
R e Z x1 x2 s1 e2 a2 a3 o Prueba
R0 Z 1 2 M-2 4M - 3 0 -M 0 0 30 M
R1 s1 0 1/2 1/4 1 0 0 0 4 16
R2 a2 0 1 3 0 -1 1 0 20 6,6667
R3 a3 0 1 1 0 0 0 1 10 10

Primer tablero
Variabl Prueb
R e Z x1 x2 s1 e2 a2 a3 Resultado a
R0 Z 1 (2 M-3)/3 0 0 (M-3)/3 (3-4M)/3 0 (60+10M)/3
R1 s1 0 5/12 0 1 1/12 -1/12 0 7/3 28/5
R2 x2 0 1/3 1 0 -1/3 1/3 0 20/3 20
R3 a3 0 2/3 0 0 1/3 -1/3 1 10/3 5
 Tablero Final y solución

R Variable Z x1 x2 s1 e2 a2 a3 Resultado
R0 Z 1 0 0 0 -1/2 (1-2M)/2 (3-2M)/2 25
R1 s1 0 0 0 1 -1/8 1/8 -5/8 1/4
R2 x2 0 0 1 0 -1/2 1/2 -1/2 5
R3 x1 0 1 0 0 1/2 -1/2 3/2 5
 TAREA
max 50 d1 + 30 d2 + 60 d3
st
30 d1 + 10 d2 + 20 d3 <= 1000
20 d1 + 40 d2 + 50 d3 <= 800
4 d1 + 3 d2 + 2 d3 <= 100

Pag 151 Winston ej 2

Min 4 x1 – x2
St
2 x1+ x2 <=8
X2<=5
X1-x2 <=4
 Método simplex de dos fases
Se utiliza cuando no es tan sencillo encontrar una sbf inicial.
Elimina el uso de la M
Utiliza la Fase I para encontrar la sbf.
Con la solución obtenida en la Fase I inicia la Fase II
 Método simplex de dos fases
FASE I FASE II
Utilice el algoritmo simplex para obtener la Utilice la solución óptima obtenida en la Fase I
minimización de la suma de las variables como solución de partida al problema 1 original,
artificiales, sujeta a las mismas restricciones reemplazando la función objetivo original Z por la
del problema original, independientemente de W. Como es usual, la función objetivo original
de si este problema original es de debe ser expresada en función de las variables no
maximización o minimización. básicas. Si al final de la Fase I las variables
Si la suma de las variables artificiales, W, es artificiales son no básicas, se eliminan de la Fase II.
mayor que cero, entonces no existe una Si alguna variable artificial es básica, pero a un
solución básica factible y se termina el nivel cero, esta variable se mantiene en el conjunto
proceso. Si W= 0, entonces inicie la Fase II de variables básicas, pero debe garantizarse que su
del algoritmo. valor nunca será mayor que cero durante la
ejecución de la Fase II.
 EJEMPLO caso 2 (Ej.6 pag.181 Winston)
MIN Z = 2 X1 + 3 X2
St
1/2 X1 + 1/4 X2 <= 4
X1 + 3 X2 >= 20
FASE I
X1 + X2 = 10
1) Introducimos las variables artificiales y las de exceso para llevar a su forma
X1, x2 >=0
estándar
Min W = a2 + a3
1/2 X1 + 1/4 X2 + s1 = 4
X1 + 3 X2 – e2 + a2 = 20
X1 + X2 + a3 = 10
Como en el método de la gran M, Z será igual a:W+R2+R3
-a2 – a3 + x1 + 3 X2 – e2 + a2- 20 + X1 + X2 + a3 – 10

w + 2 x1 + 4 x2 - e2 = 30
Asi obtenemos el nuevo tablero inicial
R Variable W x1 x2 S1 E2 A2 A3 Resultado
R0 W 1 2 4 0 -1 0 0 30
R1 S1 0 1/2 1/4 1 0 0 0 4
R2 A2 0 1 3 0 -1 1 0 20
R3 A3 0 1 1 0 0 0 1 10

Elegimos la columna y el renglón pivote --> el pivote

Prueba del
R Variable W x1 x2 S1 E2 A2 A3 Resultado cociente
R0 W 1 2 4 0 -1 0 0 30
R1 S1 0 1/2 1/4 1 0 0 0 4 16
R2 A2 0 1 3 0 -1 1 0 20 6,7
R3 a3 0 1 1 0 0 0 1 10 10
Iteramos
Prueba del
R Variable W x1 x2 S1 E2 A2 A3 Resultado cociente

R0 W 1 2/3 0 0 1/3 -1 1/3 0 3 1/3

R1 S1 0 5/12 0 1 1/12 - 1/12 0 2 1/3 5,60
R2 x2 0 1/3 1 0 - 1/3 1/3 0 6 2/3 20,00
R3 a3 0 2/3 0 0 1/3 - 1/3 1 3 1/3 5,00
 R Variable W x1 x2 S1 E2 A2 A3 Resultado Prueba del cociente
R0 W 1 2/3 0 0 1/3 -1 1/3 0 3 1/3
R1 S1 0 5/12 0 1 1/12 - 1/12 0 2 1/3 5,6
R2 x2 0 1/3 1 0 - 1/3 1/3 0 6 2/3 20
R3 a3 0 2/3 0 0 1/3 - 1/3 1 3 1/3 5

R Variable W x1 x2 S1 E2 A2 A3 Resultado
R0 W 1 0 0 0 0 -1 -1 0
R1 S1 0 0 0 1 - 1/8 1/8 - 5/8 1/4
R2 x2 0 0 1 0 - 1/2 1/2 - 1/2 5
R3 x1 0 1 0 0 1/2 - 1/2 1 1/2 5
La condición de parada es la misma que en el método Simplex normal.
 R Variable W x1 x2 S1 E2 A2 A3 Resultado
R0 W 1 0 0 0 0 -1 -1 0
R1 S1 0 0 0 1 - 1/8 1/8 - 5/8 1/4
R2 x2 0 0 1 0 - 1/2 1/2 - 1/2 5
R3 x1 0 1 0 0 1/2 - 1/2 1 1/2 5

La Solución encontrada es x1 = 5 x2 = 5 s1= ¼ W= 0

Ahora debe evaluarse la solución para saber si es posible pasar a la Fase II.

Si W=0 y las variables artificiales no están en la sbf el PL original tiene solución. En caso contrario indica
que se trata de un problema no factible y no tiene solución.

¿Como comenzamos la Fase II?

 FASE II
Se suprimen las columnas de las variables artificiales a2 y a3
Se reintroduce la FO original → Min Z= 2x1 + 3 x2
Como x1 y x2 están en la sbf debemos hacerlas desaparecer del R0. Para ello se suma 3 ( R2) +
2 (R3) del tablero de la Fase I

R Variable W x1 x2 S1 E2 Resultado Restricciones

R0 W 1 0 0 0 0 0
R1 S1 0 0 0 1 - 1/8 1/4 S1 – 1/8 e2 = 1/4
R2 x2 0 0 1 0 - 1/2 5 1 x2 – ½ e2 = 5
R3 x1 0 1 0 0 1/2 5 1 x1 + ½ e2 = 5

R0 = z – 2 x1 – 3 x2 + 3 x2 – 3/2 e2 – 15 + 2 x1 + e2 – 10 asi R0= z- 1/2 e2 = 25

 Min Z – ½ e2 = 25 Restricciones
s1 – 1/8 e2 = ¼
S1 – 1/8 e2 = 1/4
x2 – ½ e2 = 5
1 x2 – ½ e2 = 5
x1 + ½ e2 = 5 1 x1 + ½ e2 = 5

En este caso el tablero es ya un tablero óptimo, por lo que no hace falta pivotear

R Variable Z x1 x2 S1 E2 Resultado
R0 Z 1 0 0 0 - 1/2 25
R1 S1 0 0 0 1 - 1/8 1/4
R2 x2 0 0 1 0 - 1/2 5
R3 x1 0 1 0 0 1/2 5

Cuya solución es: z= 25, s1= ¼, x1= 5 y x2= 5

 LP OPTIMUM FOUND AT STEP 1

Max 4 x1 - 8 x2 + x3 OBJECTIVE FUNCTION VALUE

st
1) 28.00000
x1 + x2 + x3 = 7
2x1 - 5 x2 + x3 >= 10 VARIABLE VALUE
REDUCED COST
X1 7.000000 0.000000
X2 0.000000 12.000000
X3 0.000000 3.000000

ROW SLACK OR SURPLUS

DUAL PRICES
2) 0.000000 4.000000
3) 4.000000 0.000000

NO. ITERATIONS= 1
 fase 1

PRUEBA
DEL
Renglon VB Z X1 X2 x3 E2 A1 A2 RDO COCIENTE
0 z 1 3 -4 2 -1 0 0 17
1 A1 0 1 1 1 0 1 0 7 7
2 A2 0 2 -5 1 -1 0 1 10 5

0 z 1 0 3 1/2 1/2 1/2 0 -1 1/2 2

1 A1 0 0 3 1/2 1/2 1/2 1 - 1/2 2
2 x1 0 1 -2 1/2 1/2 - 1/2 0 1/2 5

0 z 1 0 0 0 0 -1 -1 0
1 x4 0 0 1 1/7 1/7 2/7 - 1/7 4/7
2 x1 0 1 0 6/7 - 1/7 5/7 1/7 6 3/7
fase 2
0 z 1 0 0 1 2/7 -1 5/7 21 1/7
1 x4 0 0 1 1/7 1/7 4/7 4
2 x1 0 1 0 6/7 - 1/7 6 3/7 -45

0 z 1 0 12 3 0 28
1 x4 0 0 7 1 1 4
2 x1 0 1 1 1 0 7
TIPOS DE SOLUCIONES DE UN PL
EN EL TABLERO SIMPLEX
 SOLUCIONES EN EL LINDO
TIPO DE SOLUCIONES EN EL LINDO

Infeasible = No factible Feasible = Factible

Optimum(Finite/Infinite) (Única
Podría ser un error Unbounded = No acotado
o Múltiple)

Podría ser un malentendido

acerca de lo que puede hacerse Claramente un Error
simultáneamente
 1) SOLUCIONES MÚLTIPLES – MÚLTIPLES
ALTERNATIVAS ÓPTIMAS

Cuando en los coeficientes de las variables no básicas en el renglón z de la tabla óptima existe una
variable con valor de cero, lo que indica que esa variable no básica puede entrar a la solución básica
sin alterar el valor de z , pero provoca un cambio en el valor de las variables.

EJEMPLO
Maximizar Z = 4x1+ 14x2
st
2x1 + 7x2 <= 21 Gráficamente se aprecia la
misma pendiente de la FO
7x1 + 2x2 <= 21 con una de las restricciones
 R Variable Z x1 x2 s1 s2 Resultado Prueba
R0 Z 1 -4 -14 0 0 0
R1 s1 0 2 7 1 0 21
R2 s2 0 7 2 0 1 21

Buscamos el valor de Z más "negativo" para saber que variable ingresa

Hacemos la prueba del cociente para saber que variable sale
R Variable Z x1 x2 s1 s2 Resultado Prueba
R0 Z 1 -4 -14 0 0 0
R1 s1 0 2 7 1 0 21 3
R2 s2 0 7 2 0 1 21 10,5
Hacemos el pivote igual a 1, y ceros el resto de la columna pivote

R Variable Z x1 x2 s1 s2 Resultado Prueba

R0 Z 1 0 0 2 0 42 VB { x2, s2}
R1 x2 0 0,29 1 0,14 0 3 VNB { x1, s1}
R2 s2 0 6,43 0 -0,29 1 15 Cuando en los
coeficientes de las
variables no básicas en el
renglón z de la tabla
Como todos los valores del renglón 0 son positivos el algoritmo para con esta solución optima
óptima existe una variable
z = 42 x2= 3 s2 = 15 x1 = s1 =0 con valor de cero
 2) Soluciones no acotadas

En algunos PL los valores de las variables pueden crecer indefinidamente sin violar ninguna
restricción lo que significa que el espacio solución es no acotado al menos en esa dirección.
En el simplex esta situación se reconoce cuando en el renglón 0 de la Z, de la tabla óptima
existe una variable no básica que puede entrar. pero al determinar la variable que sale nos
damos cuenta de que en su columna existen solo valores ceros o negativo, lo que indica que
esa variable puede hacer crecer a la F.O indefinidamente

EJEMPLO: Breadco elabora dos clases de pan: baguette y pan negro. Cada baguette se vende a 36 centavos y
cada hogaza de pan negro a 30 centavos. Para elaborar una baguette se requieren un paquete de levadura y 6
onzas de harina. Para el pan negro se requieren 1 paquete de levadura y 5 onzas de harina. Breadco tiene en la
actualidad 5 paquetes de levadura y 10 onzas de harina. Se pueden comprar más paquetes de levadura a 3
centavos cada uno y harina a 4 centavos la onza.
 2) Soluciones no acotadas

X1= número de baguettes horneadas

X2=número de hogazas de pan negro horneadas
Y1= número de paquetes de levadura compradas
Y2=número de onzas de harina compradas

Max 36 x1 + 30 x2 – 3 x3 – 4 x4 Max 36 x1 + 30 x2 – 3 x3 – 4 x4
St St
x1+x2 <= 5 + x3 x1+x2 – x3 <= 5
6x1 + 5 x2 <= 10 + x4 6x1 + 5 x2 – x4 <= 10

Para Lindo es Unbounded

 2) Soluciones no acotadas

PRUEBA
DEL
Renglon VB Z X1 X2 x3 x4 s1 s2 RDO COCIENTE
0 z 1 -36 -30 3 4 0 0 0
1 s1 0 1 1 -1 0 1 0 5 5
2 s2 0 6 5 0 -1 0 1 10 1 2/3

0 z 1 0 0 3 -2 0 6 60
1 s1 0 0 1/6 -1 1/6 1 - 1/6 3 1/3 20
2 x1 0 1 5/6 0 - 1/6 0 1/6 1 2/3 -10

0 z 1 0 2 -9 0 12 4 100
1 x4 0 0 1 -6 1 6 -1 20 -3 1/3
2 x1 0 1 1 -1 0 1 0 5 -5
 3) Solución no factible
EJEMPLO
Maximizar Z = 5x1+ 3x2
st
x1 + x2 <= 5
X1 >= 3
X2 >= 3
2x1 + 3x2 >= 3

Gráficamente no existe región factible en consecuencia no tiene solución.

En el tablero se observará que al menos una variable artificial será positiva
 DEGENERACIÓN
Una solución óptima es degenerada cuando posee una restricción redundante. En el simplex, al
momento de elegir la variable de salida hay empate. Si bien se resuelve arbitrariamente, en la
próxima iteración una variable básica será cero. La nueva solución es degenerada.

Ejemplo
max 2 x1 + x2 n=5 y m=3
st Cuando hay más de (n-m) variables nulas
3 x1+ x2 <=6 (azul) Punto D → (2,0)
x1-x2 <=2 (negra) x1=2
x2 <= 3 (verde) x2=0
s1=> s1=6-3x1-x2=6-6-0=0
s2 = 0
s3=3
 PRUEBA DEL
Renglon VB Z X1 X2 S1 S2 S3 RDO COCIENTE
0 z 1 -2 -1 0 0 0 0 z= 0
1 s1 0 3 1 1 0 0 6 2 VB= S1; S2;S3

Empate
2 s2 0 1 -1 0 1 0 2 2 VNB= X1, X2
3 s3 0 0 1 0 0 1 3 #¡DIV/0!

0 z 1 0 -3 0 2 0 4 z= 4
S1=0; X1=2;S3=3 --> La VB s1 es igual a
1 s1 0 0 4 1 -3 0 0 0 VB= cero
2 x1 0 1 -1 0 1 0 2 -2 VNB= S2, X2
3 s3 0 0 1 0 0 1 3 3

0 z 1 0 0 3/4 - 1/4 0 4 z= 4
x2=0; X1=2;S3=3 --> La VB x2 es igual a
1 x2 0 0 1 1/4 - 3/4 0 0 0 VB= cero
2 x1 0 1 0 1/4 1/4 0 2 8 VNB= S1, s2
3 s3 0 0 0 - 1/4 3/4 1 3 4

0 z 1 0 0 2/3 0 1/3 5 z= 5
1 x2 0 0 1 0 0 1 3 VB= x2=3; X1=1;S2=4
2 x1 0 1 0 1/3 0 - 1/3 1 VNB= S1, s3
3 s2 0 0 0 - 1/3 1 1 1/3 4
 Casos especiales en la aplicación del SIMPLEX:
Tipos de soluciones y su identificación en el método
simplex.
1. Degeneración:
La degeneración ocurre cuando en alguna iteración del método simplex existe un empate en la selección de la
variable que sale. Este empate se rompe arbitrariamente. Sin embargo, cuando suceda esto una o más veces de las
variables básicas, será necesariamente igual a cero en la siguiente iteración. En este caso decimos que la nueva
solución es degenerada.
Recordemos que el número de variables no básicas se encuentra al hacer la diferencia de n-m (n>m); donde: m
= número de ecuaciones n = número de incógnitas. (Una variable básica es cero)

2. Múltiples alternativas optimas:

Cuando la función objetivo es paralela a una restricción que se satisface en el sentido de la igualdad a través de la
solución óptima, la función objetivo tomará el mismo valor óptimo en más de un punto de la solución. Por esta
razón reciben el nombre de Múltiples alternativas óptimas.
¿ Cómo sabemos en las tablas que existen múltiples alternativas óptimas ?
Cuando en los coeficientes de las variables no básicas en el renglón z de la tabla óptima existe una variable con
valor de cero, lo que indica que esa variable no básica puede entrar a la solución básica sin alterar el valor de z ,
pero provoca un cambio en el valor de las variables.
 Casos especiales en la aplicación del SIMPLEX:
Tipos de soluciones y su identificación en el método
simplex.
3. Soluciones no acotadas:
En algunos modelos de programación lineal, los valores de las variables se pueden aumentar en forma indefinida sin
violar ninguna de las restricciones, lo que significa que el espacio de soluciones es no acotado cuando menos en una
dirección. Como resultado el valor de la función objetivo puede crecer (caso de la minimización) en forma indefinida.
¿ Cómo sabemos en las tablas que existen solución no acotada ?
Cuando en la tabla del simplex en el renglón de la z existe una variable no básica que puede entrar pero al determinar
la variable que sale nos damos cuenta que en la su columna existen solo valores de ceros negativos o negativos lo que
significa que esa variable puede hacer crecer en forma indefinida a z sin que se infrinja ninguna de las restricciones. Por
lo tanto concluimos sin hacer más cálculos que el problema no tiene solución acotada.
4. Solución Infactible:
Si las restricciones no se pueden satisfacer en forma simultánea, se dice que el modelo no tiene solución factible. Esta
situación nunca puede ocurrir si todas las restricciones son del tipo Menor igual (suponiendo valores positivos en el
segundo miembro) ya que las variables de holgura producen siempre una solución factible. Sin embargo, cuando
empleamos los otros tipos de restricciones, recurrimos al uso de variables artificiales, que por su mismo diseño no
ofrecen una solución factible al modelo original. Aunque se hacen provisiones ( a través del uso de penalizaciones)
para hacer que estas variables artificiales sean cero en el nivel óptimo, esto sólo puede ocurrir si el modelo tiene una
espacio factible. Si no lo tiene, cuando menos una variable artificial será positiva en la iteración óptima.
 INTERPRETACIÓN ECONÓMICA DE LA TABLA SIMPLEX
La empresa tiene como objetivo la maximización de las utilidades provenientes de la fabricación
de los cerámicos rústicos y esmaltados.
La contribución máxima a las utilidades que puede lograrse está sujeta a las disponibilidades de
los insumos.
Tanto las utilidades como el uso de los insumos son proporcionales a la cantidad que se fabrique
de los productos
No es posible fabricar cantidades negativas de los productos

Cerámico Cerámico Rústico Disponibilidad de

Esmaltado horas mensuales
Horas de mano de obra / m2 5 5 300
Horas de secado / m2 4 8 400
Horas de cocción / m2 6 4 320
Contribución a las utilidades/m2 8 6
 INTERPRETACIÓN ECONÓMICA DE LA
TABLA SIMPLEX
MODELO PL ESTANDAR
Max 8 x1 + 6 x2 Max Z= 8 x1 + 6 x2 + 0 s1 + 0 s2 + 0 s3
St St
5 x1 +5 x2 <= 300 5 x1 +5 x2 + s1 = 300
4 x1 +8 x2 <= 400 4 x1 +8 x2 + s2 = 400
6 x1 +4 x2 <= 320 6 x1 +4 x2 + s3 = 320

x1= metros de cerámicos esmaltados

x2= metros de cerámicos rústicos
 Armado del tablero

Renglo PRUEBA DEL

n VB Z X1 X2 S1 S2 S3 RDO COCIENTE
0 z 1 -8 -6 0 0 0 0
1 s1 0 5 5 1 0 0 300 60
2 s2 0 4 8 0 1 0 400 100
3 s3 0 6 4 0 0 1 320 53 1/3

0 z 1 0 - 2/3 0 0 1 1/3 426 2/3

1 s1 0 0 1 2/3 1 0 - 5/6 33 1/3 20
2 s2 0 0 5 1/3 0 1 - 2/3 186 2/3 35
3 x1 0 1 2/3 0 0 1/6 53 1/3 80

VB={X1, S1, S2} X2=0

VNB={X2, S3} S1= 100/3= 33,3
SOLUCION DE LA PRIMERA ITERACIÓN S2= 560/3= 186,6
Z= 1280/3=426,6 S3=0
X1= 160/3 = 53,3
 INTERPRETACIÓN ECONÓMICA DE LA
TABLA SIMPLEX
Hacemos 53,3 m2 de cerámico esmaltado
SOLUCION DE LA PRIMERA
ITERACION No hacemos cerámico rústico
Z= 1280/3=426,6 Ganamos $ 426,6
X1= 160/3 = 53,3 Usamos todas las horas de cocción →
Recurso limitante
X2=0
Sobran 33,3 hs de Mano de Obra
S1= 100/3= 33,3
Sobran 186,6 hs de Secado
S2= 560/3= 186,6
No es el óptimo porque todavía hay variables
S3=0
negativas en R0

PARA AGREGAR METROS DE CERÁMICO RUSTICO DEBO DEJAR DE PRODUCIR ALGO DE

CERAMICO ESMALTADO PARA LIBERAR HORAS DE COCCIÓN.
 INTERPRETACIÓN ECONÓMICA DE LA
TABLA SIMPLEX
OBSERVEMOS LA COLUMNA DE LOS CERAMICOS ESMALTADOS EN EL TABLERO

V Contribución que se pierde por m2

Renglón B Z X1 X2 S1 S2 S3 RDO que se fabrica de cerámico rústico
originado por la reducción de
0 z 1 0 - 2/3 0 0 1 1/3 1280/3 cerámico esmaltado. Como es (-) se
1 s1 0 0 5/3 1 0 - 5/6 100/3 aumentará Z
En cuanto se disminuye el cerámico
2 s2 0 0 16/3 0 1 - 2/3 560/3 esmaltado para poder producir 1 m2
3 x1 0 1 2/3 0 0 1/6 160/3 de cerámico rústico

TASAS DE SUSTITUCIÓN: Si es (+) el sacrificio que deberá hacerse la variable xj para incrementar en
una unidad la VB. Si es (-) el incremento que se producirá en la VB

5/3= Por cada m2 que se incremente x2, el cerámico rústico, el excedente de mano de obra se reducirá en 5/3
16/3= Por cada m2 que se incremente x2, el cerámico rústico, el excedente de hs de secado se reducirá en 16/3
2/3=Hacer 1 m2 de rústico implica dejar de fabricar 2/3 de m2 de cerámico esmaltado porque hacer 1 m2 de
rustico necesita 4 hs de cocción. Observemos la restricción de las hs de cocción
 INTERPRETACIÓN ECONÓMICA DE LA TABLA SIMPLEX

6 x1 +4 x2 + s3 = 320 HS de cocción
Entonces 6 * 2/3 = 12/3 = 4 → hacer 1 m2 de rústico necesita 4 hs.
ASI NOS CONVIENE FABRICAR CERÁMICO RUSTICO. ¿Cuánto? TAN GRANDE COMO SE PUEDA
Usamos la tasa de sustitución para responder
Cada x1 que agregue modifica las otras variables básicas incluso podría volverlas negativas
Valoremos el ingreso de x2 sin modificar las otras variables no básicas. Recordemos
VB={X1, S1, S2} VNB={X2, S3}
Si mantenemos s3=0 e incorporamos quedan
5/3 x2 + s1 = 100/3 Renglón VB Z X1 X2 S1 S2 S3 RDO
S1= 100/3-5/3x2 y como s1 debe ser >0
0 z 1 0 - 2/3 0 0 1 1/3 1280/3
100/3-5/3 x2 >=0 1 s1 0 0 5/3 1 0 - 5/6 100/3
X2= 100/3: 5/3 2 s2 0 0 16/3 0 1 - 2/3 560/3
X2= 20 3 x1 0 1 2/3 0 0 1/6 160/3
Ahora lo hacemos con las demás restricciones
 INTERPRETACIÓN ECONÓMICA DE LA
TABLA SIMPLEX
Asi LP OPTIMUM FOUND AT STEP 2
x2 <=20
X2 <= 80 OBJECTIVE FUNCTION VALUE
X2<= 35
1) 440.0000
El máximo valor de x2 será el Min {20,80,35} = 20
VARIABLE VALUE REDUCED
Z= 1280/3 + 20 (2/3) = 440 COST
X1 40.000000 0.000000
X2 20.000000 0.000000
R VB Z X1 X2 S1 S2 S3 RDO
0 z 1 0 0 2/5 0 1 440 ROW SLACK OR SURPLUS DUAL
1 x2 0 0 1 3/5 0 -½ 20 PRICES
2 s2 0 0 0 -16/5 1 2 80 2) 0.000000 0.400000
3 x1 0 1 0 - 2/5 0 1/2 40 3) 80.000000 0.000000
4) 0.000000 1.000000