U 3
U 3
U 3
Enrique España
Para obtener gráficamente la solución óptima del MPL, se pueden seguir los pasos
(del procedimiento) que se indican a continuación (secciones: 3.1.1 - 3.1.4).
Dada la inecuación: 3x1 + 5x2 ≤ 15, la ecuación asociada es: 3x1 + 5x2 = 15
Los semiejes positivos (rectas: x1 = 0 y x2 = 0) del sistema coordenado son los límites
de la condición de no negatividad del MPL. Dado esto, para determinar el semiplano
solución de las demás restricciones:
Así, dados dos puntos del plano: A y B; los diagramas apropiados serían:
A B
Línea recta
A B
Segmento de recta
Un segmentó está limitado por dos puntos: sus extremos, mientras que una recta
pasa por estos puntos: no tiene extremos. El segmento es un subconjunto de la
recta.
1. Igualar la función objetivo a cero (z = 0). Así, la recta pasa por el origen del
sistema (0, 0).
3. Ubicar los dos puntos: (0, 0) y (x1, x2), en el plano cartesiano, y trazar la recta
que pasa por estos puntos.
Solución única
Si el modelo tiene únicamente una solución, entonces queda definida una figura
convexa, cerrada y acotada; y el conjunto de puntos extremos es finito, igual al
número de vértices de la figura.
La mejor solución será uno de los vértices de la figura convexa. Se identifica como
primer (minimización) o último (maximización) punto extremo.
Considerando lo anterior:
2. Leer las coordenadas del punto extremo que implica la solución óptima. En
general, las componentes de la solución gráfica, no se pueden leer; a menos
que sean enteras. Empero, aunque sean fraccionarias, se pueden establecer
sus valores utilizando el modelo: resolución de sistemas de ecuaciones.
sistema formado por las ecuaciones asociadas a estas rectas, para determinar
el valor de las variables.
Varias soluciones
Para establecer si un MPL tiene varias soluciones, se siguen los mismos pasos del
procedimiento indicado para: Solución única.
Si al aplicar el punto uno (1), la recta de la función objetivo incluye dos vértices
adyacentes (un lado) de la figura convexa, entonces existen varias soluciones; pero
el valor óptimo (z) es el mismo.
Por lo tanto, la afirmación: "Un vértice de la figura convexa es la solución óptima del
modelo", es verdadera; aunque el MPL tenga varias soluciones.
Sin solución
2. El MPL tiene solución si las restricciones definen una figura convexa, cerrada
y acotada.
Ejemplo 3.1
Para el próximo mes, una empresa desea saber cuántas unidades debe producir y
vender de cada uno de sus dos productos principales (A y B). Los dos bienes se
producen en dos fases de proceso (I y II) con los siguientes coeficientes técnicos:
Investigación de Operaciones Msc. Enrique España
Ejemplo 3.2
La empresa "ABC" produce dos tipos de juguetes: Súper (S) y Normal (N). Dispone de
1.200 kilos de plástico especial y de 40 horas de producción semanal. La producción
total no puede ser mayor que 800 docenas y el número de docenas de S no puede
exceder al número de docenas de N por más de 450. Para producir una docena de S
se requieren dos kilos de plástico y tres minutos de producción por docena y N
requiere un kilo de plástico y cuatro minutos de producción por docena. La venta de
una docena de S implica una ganancia de $8 y N entrega $5 de utilidad por docena.
Determinar la utilidad máxima semanal que se puede obtener.
Ejemplo 3.3
Ejemplo 3.4
Una unidad educativa necesita comprar cierto tipo de equipos para el laboratorio de
química. Dos fábricas pueden proveérselos. Dada la siguiente información:
Concepto Fábrica 1 Fábrica 2
Cantidad de personal auxiliar simultáneo para la atención de
2 3
cada equipo.
Cantidad de alumnos que pueden trabajar simultáneamente
10 4
por equipo.
Cantidad de experimentos distintos que pueden realizarse
1 7
simultáneamente por equipo.
Costo de cada equipo en Bs 1000 1500
Decidir qué cantidad de equipos de cada fábrica le conviene adquirir para que el
costo total sea mínimo.
El método simplex fue creado en 1947 por el matemático George Dantzig. Este
algoritmo se utiliza para resolver problemas de programación lineal que implican
dos o más variables; es decir, sin importar el número de variables.
Entonces dada una restricción lineal, inecuación o ecuación (en su forma más
simple), se tiene:
LI LD
ax1 + bx2 ≤ c
Condiciones iniciales
Investigación de Operaciones Msc. Enrique España
Cuando en un MPL no se den las condiciones anteriores, habrá que hacer los
ajustes correspondientes.
Variables
básicas
z 0
Las columnas entre B y S se rotulan con todas las variables del problema, en orden:
con j = 1, 2,…, n variables.
3.1 La variable que entra a la base es la que tiene el coeficiente más negativo
en la última fila (z).
Investigación de Operaciones Msc. Enrique España
3.2 Para fijar la variable que debe salir de la base, se divide cada término de
la columna S por el término correspondiente de la cp, siempre que estos
últimos sean positivos.
Cada ccp pertenece a una fila, los elementos de esta fila se denominan
coeficientes de la fila correspondiente del ccp (cfccp).
4. Elaborar una tabla nueva y calcular los nuevos coeficientes para las
diferentes filas; de tal manera que el elemento pivote (p) sea 1 y los otros, ccp,
0. Es decir, la columna de la nueva tabla que corresponde a la cp de la tabla
antigua, sólo debe contener un uno (1) y ceros (0) como nuevos elementos.
4.1 La nueva tabla tiene los mismos rótulos de columnas y filas, excepto la
fila de la variable que sale de la base que es sustituida por la variable
que entra en la base. La nueva primer columna (B) es ahora el conjunto
de las variables básicas.
4.2 Los nuevos coeficientes de la variable (fila) que entra en la base (cve) se
obtienen dividiendo todos los coeficientes de la fila pivote (fp) entre el
pivote (p), que es el que hay que convertir en 1. Es decir,
[𝒇𝒑]
[𝒄𝒗𝒆] =
𝒑
5. Repetir los pasos tres y cuatro hasta que no queden números negativos en la
última fila (z), excluyendo la columna S.
Ejemplo 3.5
Para el próximo mes, una empresa desea saber cuántas unidades debe producir y
vender de cada uno de sus dos productos principales (A y B). Los dos bienes se
producen en dos fases de proceso (I y II) con los siguientes coeficientes técnicos:
Producto A B Cap. Máx.
Proceso I 15 h/u 25 h/u 75 h
Proceso II 20 h/u 12 h/u 60 h
Las dos relaciones conducen a la misma solución óptima. La razón es que, entre
más pequeña es z, más grande es –z, así que la solución que da el menor valor de z
dentro de la región factible también debe dar el mayor valor para –z en esta región.
Por lo tanto, en todas aquellas restricciones de igualdad que no tengan una variable
de holgura deben introducirse variables artificiales, con el fin de generar una
solución básica inicial.
Ejemplo 3.6
Una unidad educativa necesita comprar cierto tipo de equipos para el laboratorio de
química. Dos fábricas pueden proveérselos. Dada la siguiente información:
Concepto Fábrica 1 Fábrica 2
Cantidad de personal auxiliar simultáneo para la atención de
2 3
cada equipo.
Cantidad de alumnos que pueden trabajar simultáneamente
10 4
por equipo.
Cantidad de experimentos distintos que pueden realizarse
1 7
simultáneamente por equipo.
Costo de cada equipo en Bs 1000 1500
Investigación de Operaciones Msc. Enrique España
Decidir qué cantidad de equipos de cada fábrica le conviene adquirir para que el
costo total sea mínimo.
Siempre que existan variables artificiales como parte de la solución inicial, la última
fila de la tabla inicial del simplex contendrá M, a fin de evitar su presencia en las
tablas, se precisan los siguientes cambios:
3. Siempre que una variable artificial deja de ser básica (variable artificial que
sale de la base), se puede eliminar la columna que le corresponde.
4. La última fila puede eliminarse, siempre que todos sus elementos sean ceros.
Ejemplo 3.7
Ejemplo 3.8
Ejemplo 3.9
Una compañía aérea tiene dos aviones A y B para cubrir un determinado trayecto.
El avión A debe hacer igual o más veces el trayecto que el avión B pero no puede
sobrepasar 120 viajes. Entre los dos aviones deben hacer por lo menos 60 vuelos,
pero no más de 200. En cada vuelo A consume 900 litros de combustible y B 700
litros. ¿Cuántos vuelos deben hacer, para que el consumo de combustible sea
mínimo?
Ejemplo 3.10
¿Cuántas acciones de cada tipo tendría que comprar usted, con el fin de maximizar
el rendimiento anual total de esa cartera?
Investigación de Operaciones Msc. Enrique España
Problemas de Resolución
Trabaje los problemas 3.1 - 15, utilizando el método gráfico
3.1 La empresa GTC produce dos clases de herramientas: llaves inglesas y
alicates, para satisfacer la demanda del mercado (empresas y particulares). El
estudio, técnico y de mercado, ha estimado los parámetros que se indican en la
tabla que sigue. Dada esta información, calcular el número de llaves y alicates que
se debe fabricar parta obtener la mejor utilidad.
Datos técnicos y de mercado
Concepto Llaves Alicates Disponible
Acero 1,5 1,0 27.000 kilos
Máquina de moldeo 1,0 1,0 21.000 horas
Máquina de montaje 0,3 0,5 9.000 horas
Demanda 15.000 16.000
Beneficio unitario ($) 0,13 0,10
3.2 Una agropecuaria utiliza diariamente por lo menos 800 kilos (k) de alimento
especial para ganado. Este alimento es una mezcla de maíz y semilla de soya, con la
siguiente composición:
Los requerimientos dietéticos diarios del alimento especial estipulan por lo menos
un 30% de proteína y cuando mucho un 5% de fibra. Determinar el costo mínimo
diario de la mezcla de alimento.
3.7 Una persona ha desarrollado dos tipos de juego de salón para adultos, hechos a
mano, que vende a tiendas en todo el país. Aunque la demanda de estos juegos
excede su capacidad de producción, la persona continúa trabajando sola y limita su
trabajo semanal a 50 horas. El juego tipo 01 se produce en 3,5 horas y arroja una
ganancia de $28, mientras que el juego 02 toma 4 horas para su producción y da
una ganancia de $31. Cuántos juegos de cada tipo deberá producir semanalmente
esta persona, si su objetivo es maximizar la ganancia total?
3.9 Un agente económico tiene disponibles $6.000 para invertir. Tiene dos ofertas
de participar como socio de dos negocios diferentes. Oferta 1, invertir $5.000 y 400
horas de su tiempo, y la ganancia estimada (ignorando el valor del dinero en el
tiempo) sería de $4.500. Oferta 2, $4.000 de inversión y 500 horas, con una
ganancia estimada de $4.500. Sin embargo, ambas ofertas son flexibles y permiten
entrar al negocio con cualquier fracción de la sociedad; la participación en las
utilidades sería proporcional a esa fracción. Como de todas maneras, este agente
está buscando un trabajo interesante para el verano y dispondrá de 600 horas a lo
sumo, ha decidido participar en una o ambas ofertas, con la combinación que
maximice la ganancia total estimada. Determine esa ganancia total.
3.11 Resuelva el problema anterior, suponiendo que las ganancias netas por hora
deben superar los $3.000 para que se justifique la implementación de la producción
de los dos nuevos productos.
3.12 Resuelva el problema 2.8, suponiendo que la ganancia por Ventana es $120
(en vez de $300).
3.13 Resuelva el problema 2.8, ignorando las restricciones de las Plantas dos y
tres.
3.15 Una empresa planifica construir casas con tres (TD) y dos (DD) dormitorios,
para lo cual dispone de $5,5 millones. El costo de una casa TD es de $130.000 y
$80.000 para DD. El número de TD ha de ser, al menos, el 40 % del total y el de
DD, el 20 % por lo menos. Si cada casa TD se vende a $160.000 y en $90.000 cada
unidad del tipo DD, ¿cuál sería el beneficio máximo?
3.16 Usted dispone de $250.000 para invertir en los activos financieros: RV (renta
variable), BB (bonos del Banco Central)) y BT (bonos del Tesoro). Cada activo RV
cuesta $900 y el rendimiento esperado es 12 %; el precio del BB es $1.000 y genera
un beneficio del 6 %; el costo de cada BT es $1.000 y rinde el 8 %. La inversión en
los activos RV y BT no debe superar al 60 % del total invertido. Lo invertido en BB
tiene que ser superior a $20.000, y la inversión en BT no puede ser inferior a la
inversión en los activos RV. Determine el máximo rendimiento monetario anual.