Nacional Abierta

Vicerrectorado Académico
Área de Ingeniería
Carrera Ingeniería de Sistemas

Trabajo práctico sustitutivo

Asignatura: Investigación de Operaciones I Código: 315

Fecha de devolución: A más tardar el 29-03-2021 Nombre del

Estudiante: Giovanny García M.

Cédula de Identidad: 11.959.958

Centro Local / Unidad de Apoyo: Mérida

Correo electrónico:yovannygarciamendez@gmail.com

Teléfono celular: 0416-1183597

Carrera: 281 TSU en higiene y seguridad industrial

Número de originales:

Lapso: 2021-1

Resultados de Corrección

OBJ N° 1 2 3 4 7 8
0:N 1:
L L

-
ESPECIFICACIONES DEL TRABAJO PRÁCTICO SUSTITUTIVO

M: 1, U: 1, O: 1 C/D: 1/1
1) Considere planificar el envío de los artículos necesarios desde los almacenes donde se
fabrican y almacenan a los centros de distribución donde se necesitan, como se muestra
en la introducción. Hay tres almacenes en diferentes ciudades: Valera, Cabimas y el Tigre.
Tienen 250, 130 y 235 toneladas de papel en consecuencia. Hay cuatro publicadores en
San Felipe, San Carlos, La Victoria y Los Teques. Ordenaron 75, 230, 240 y 70 toneladas
de papel para publicar nuevos libros.

Existen los siguientes costos en UM (Unidad Monetaria) de transporte de una tonelada de

papel:
San San La Los
Feli Carlos victoria Teques
pe
Valera 15 20 16 21
Cabimas 25 13 5 11
El Tigre 15 15 7 17

La gerencia quiere que minimice los costos de envío mientras satisface la demanda.
Determine:
i) Variables de Decisión.
ii) Función Objetivo.
iii) Restricciones.
iv) El modelo matemático de Programación Lineal.

i. Variables de decisión

Sea Xij la cantidad de material a enviar (toneladas de papel) a enviar de los tres almacenes
(Caracas, Valencia y Barquisimeto) i (i=1, 2.3. 4) a las cuatro editoriales en Coro,
Maracaibo, Porlamar y Cumana, j (j=1,2. 3. 4)

ii. Función objetivo

Z= 15X11 + 25 X12 + 15 X13 + 20 X21 + 13X22 + 15X23 + 10 X31 + 5X32 + 7X33 + 21X41 +11X42 +
7X43

iii. Restricciones

X11 + X12 + X13 =250

X21 + X22 + X23 = 130

X31 + X32 + X33 = 235

X11 + X12 + X13 =75

X21 + X22 + X23 = 230

X31 + X32 + X33 = 240

X41 + X42 + X43 = 70

Xij ≥0

iv. El modelo matemático de programación lineal

Minimizar

Z= 15X11 + 25 X12 + 15 X13 + 20 X21 + 13X22 + 15X23 + 10 X31 + 5X32 + 7X33 + 21X41 +11X42 +
7X43

Sujeto a

X11 + X12 + X13 =250

X21 + X22 + X23 = 130

X31 + X32 + X33 = 235

X11 + X12 + X13 =75

X21 + X22 + X23 = 230

X31 + X32 + X33 = 240

X41 + X42 + X43 = 70

Xij ≥0

M: 1, U: 2, O: 2 C/D: 1/1

La empresa XYZ fabrica tres tipos diferentes de embarcaciones. Todo se puede

obtener de manera rentable en esta empresa, pero la producción mensual de la
empresa está limitada por la cantidad limitada de mano de obra, tornillos y madera
disponibles cada mes. El director elegirá la combinación de barcos que maximice los
ingresos a la vista de la información que se proporciona en la siguiente tabla:
 Insumos bote de cano kay disponibilidad
remos a ak mensual
mano de 12 7 9 1260 horas
obra
madera 22 1 16 19008 m3
8
tornillería 2 4 3 396 Kg
precio (UM) 4000 2000 500
0

a) Formule el problema anterior como un problema de programación lineal. b)

Resuelva por el método simplex y encuentre la solución óptima

a)

Z= 4000 X1 + 2000 X2 + 5000 X3

s. a:

12 X1 + 7 X2 + 9 X3 ≤ 1260

22 X1 + 18 X2 + 16X3 ≤ 19008

2 X1 + 4 X2 + 3 X3 ≤ 396

X1, X2, X3 ≥0

Solución a las preguntas a, b y c.

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).

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

≥ -exceso + artificial
= + artificial
≤ + holgura

Se escribe la tabla inicial del método simplex:

La tabla inicial del método Simplex está compuesta por todos los coeficientes de las variables
de decisión del problema original y las de holgura, exceso y artificiales agregadas en el paso 2
(en las columnas, siendo P0 el término independiente y el resto de variables P i coinciden con
Xi), y las restricciones (en las filas). La columna C b contiene los coeficientes de las variables
que se encuentran en la base.

La primera fila está formada por los coeficientes de la función objetivo, mientras que la
última fila contiene el valor la función objetivo y los costes reducidos Zj - Cj.

La última fila se calcula como sigue: Z j = Σ(Cbi·Pj) para i = 1..m, donde si j = 0, P 0 = bi y C0

= 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera tabla del método Simplex y
ser todos los Cb nulos se puede simplificar el cálculo, y por esta vez disponer Zj = -Cj.

Condición de parada:

Si el objetivo es la maximización, cuando en la última fila (fila indicadora) no existe ningún

valor negativo entre los costes reducidos (columnas P1 en adelante) se alcanza la condición
de parada.

• En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de
Z (columna P0) es la solución óptima del problema.

• Otro caso posible es que en la columna de la variable entrante a la base todos los valores son
negativos o nulos. Esto indica que el problema no se encuentra acotado y su solución siempre
resultará mejorable. Ante esta situación no es necesario continuar iterando indefinidamente y
también se puede dar por finalizado el algoritmo.

De no ser así, se ejecutan los siguientes pasos de forma iterativa.

ELECCIÓN DE LA VARIABLE ENTRANTE Y SALIENTE DE LA BASE.

Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna
cuyo valor en la fila Z sea el menor de entre todos los negativos. En este caso sería la variable
X1 (P1) de coeficiente -3.

• Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de
empate), entonces se optará por aquella variable que sea básica.

• La columna de la variable que entra en la base se llama columna pivote.

Una vez obtenida la variable que entra en la base, se procede a determina cual será la variable
que sale de la misma. La decisión se toma en base a un sencillo cálculo: dividir cada término
independiente (columna P0) entre el elemento correspondiente de la columna pivote, siempre
que ambos elementos sean estrictamente positivos (mayores que cero). Se escoge la fila cuyo
resultado haya resultado mínimo.

• Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente. En caso de que
todos los elementos de la columna pivote fueran de ésta condición se habría cumplido la
condición de parada y el problema tendría una solución no acotada.

• El término de la columna pivote que en la división anterior dio lugar al menor cociente
positivo indica la fila de la variable de holgura que sale de la base. Si al calcular los cocientes,
dos o más resultados cumplen la condición para elegir el elemento saliente de la base (caso de
empate), se escoge aquella que no sea variable básica (siempre que sea es posible).

• La intersección de la fila pivote y columna pivote marca el elemento pivote, en este caso el 3

Actualizar la tabla:

Los nuevos coeficientes de la tabla se calculan de la siguiente manera:

• En la fila del elemento pivote cada nuevo elemento se calcula como:

• Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote

• En el resto de las filas cada elemento se calcula:

• Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna
Pivote * Nuevo Elemento Fila Pivote)

• Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de
elementos de la columna pivote se anulan (análogo al método de Gauss-Jordán).
La tabla correspondiente a la segunda iteración será:

Al comprobar la condición de parada se observa que no se cumple ya que entre los elementos
de la última fila hay uno negativo, -1. Se continúa iterando nuevamente los pasos 6 y 7.

• La variable que entra en la base es X 2 (P2), por ser la variable que corresponde a la columna
donde se encuentra el coeficiente -1.

• Para calcular la variable que sale, se dividen los términos de la columna P0 entre los
términos correspondientes de la nueva columna pivote. Actualizando nuevamente los valores
de la tabla se obtiene:
Solución óptima: Z= 668000

El método simplex es un algoritmo eficiente y confiable para resolver problemas de

programación lineal. También proporciona la base para llevar a cabo, en forma muy eficiente,
las distintas etapas del análisis pos óptimo. Aunque tiene una interpretación geométrica útil, el
método simplex es un procedimiento algebraico. En cada iteración se mueve de la solución
básica factible actual a una adyacente mejor eligiendo tanto la variable básica entrante como
la que sale y después usando la eliminación de Gauss para resolver el sistema de ecuaciones
lineales. Cuando la solución actual no tiene una solución básica factible adyacente que sea
mejor, la solución actual es óptima y el algoritmo se detiene.
 M: 2, U: 3, O: 3 C/D: 1/1
3.- Sea el siguiente problema de programación lineal

Max, Z=X1+2X2
s.a: -X1 + X2 ≤ 2
X1 + 2X2 ≤ 6
2X1+ X2 ≤ 6
X1, X2≥0

a) Resuelva el problema por el método simplex y encuentre la solución óptima.

b) Grafique el problema anterior indicando la solución óptima factible.

Resolviendo el problema de forma gráfica tenemos:

La solución óptima es:

Z=X1+2X2=0,67 + 2.(2,67)=6,01

Igualar cada una de las restricciones a cero con lo cual tenemos,

-X1 + X2 =2 Ecuación 1
X1 + 2X2 =6 Ecuación 2
2X1+ X2 =6 Ecuación 3
Para la ecuación 1 tenemos cuando X1 = 0, X2=2: cuando X2=0, X1= -2

Para la ecuación 2 tenemos cuando X1= 0, X2= 3; cuando X2=0, X1=6

Para la ecuación 3 tenemos cuando X1= 0, X2= 6; cuando X2=0, X1=3

Grafico 2. Solución grafica para la función objetivo Z: X1 + 2X2

Se obtienen los valores óptimos X1=0,67 y X2=2.67 con lo cual se obtiene el valor de Z

Z=X1+2X2=0,67 + 2.(2,67)=6,01
De esta manera se comprueba que existe una solución óptima.

Por el método simplex tenemos:

Iteración 1 y 2:

Iteración 3:
La solución óptima es:

Z=X1+2X2=0,67 + 2.(2,67)=6,01

M: 2, U: 4, O: 4 C/D: 1/1
4.- Aplique el método dual-simplex del siguiente problema de programación lineal:

= 2 +
. :3 + ≥ 3
4 +3 ≥ 6
+ 2 ≥ 3
, ,≥0

Solución:

Consideremos el siguiente problema de programación lineal

Maximizar Z=cx (primal)

Sujeto a Ax≤b

x≥0

Hay otro problema de programación lineal que es

Minimizar Y= b`y

Sujeto a A`y≥c`

y≥0

Este segundo problema se llama el dual del problema anterior.

Se observa que el problema dual contiene las mismas constantes a ij de A, de bi y de cj del

problema original, sólo que arreglados en otro orden. Se observa además que en el dual hay
tantas variables como restricciones hay en el primal (excluyendo las de no negatividad de las
variables). Si la matriz A es sxr de tal manera que x es un vector con r componentes, entonces
A` es rxs, donde y es un vector con s componentes.

Las relaciones anteriores se pueden también escribir de la siguiente manera:

Maximizar (Y̽) = (-b`) y

Sujeto a A`y≤-c`
y≥0

y min(Y)=-max (Y̽)

Si ahora consideramos que el problema primal es el descrito por las relaciones anteriores, que
no es otra cosa sino que es equivalente al problema dual anteriormente planteado, y
escribimos el dual de este problema obtenemos:

Min (Z̽) =-cx

Sujeto a -A≥-b, x≥0

O bien

Max Z̽ =cx

Sujeto a x≤b, x≥0

Donde min Z̽= -max Z

Las relaciones anteriormente obtenidas no son más que el problema primal inicialmente
planteado es decir, se ha encontrado que el dual del duales el primal.

Las observaciones anteriores nos permiten obtener el dual de un problema de programación

lineal. En efecto, basta escribir el problema en una de las dos formas antes descrita.

Sea y1, y2, y3 las variables asociadas a la primera, segunda y tercera restricciones,
respectivamente.

El dual está dado por:

M Y=3y1 + 6y2 + 3y3

Sujeto a 3y1 + 4y2 + y3 ≤2

y1 + 3y2 + 2y3 ≤1

yi≥0, i=1, 2. 3

Observación: el dual del dual me daría el problema primal original, como se demostró
anteriormente.
M: 3, U: 7, O: 7 C/D: 1/1
5.- Dado el siguiente problema de programación lineal:

Max. Z=3X1 –X2 + 4X3

s.a: X1+ 3X2 + 4X3≤18
3X1+ X2+2X3≤10
0≤X1≤3
2≤X2≤3
0≤X3≤2
X1, X2, X3≥0
Resolver por el método simplex con variables acotadas superiormente.

Solución: en este caso al analizar las restricciones tenemos que el método simplex con
variables acotadas superiormente se aplica directamente al modelo de programación lineal
planteado en el enunciado de acuerdo a las cotas mostradas y por ello comenzamos a resolver
el problema de acuerdo al procedimiento del método simplex como se efectuó ya en el
ejercicio número 2

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

≥ -exceso + artificial
= + artificial
≤ + holgura

En este caso se introducen las variables de holgura en cada una de las restricciones del tipo ≤,
para convertirlas en igualdades (como se realizó en el ejercicio2) resultando el sistema de
ecuaciones lineales:

Y Se iguala la función objetivo a cero:

Z-3X1 +X2 -4X3=0

Se escribe la tabla inicial del método simplex:

La tabla inicial del método Simplex está compuesta por todos los coeficientes de las variables
de decisión del problema original y las de holgura, exceso y artificiales agregadas en el paso 2
(en las columnas, siendo P0 el término independiente y el resto de variables P i coinciden con
Xi), y las restricciones (en las filas). La columna C b contiene los coeficientes de las variables
que se encuentran en la base.

La primera fila está formada por los coeficientes de la función objetivo, mientras que la
última fila contiene el valor la función objetivo y los costes reducidos Zj - Cj.

La última fila se calcula como sigue: Z j = Σ(Cbi·Pj) para i = 1..m, donde si j = 0, P 0 = bi y C0

= 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera tabla del método Simplex y
ser todos los Cb nulos se puede simplificar el cálculo, y por esta vez disponer Zj = -Cj.

Iteración 1.
Iteración 2.
 It
eración 3.

Iteración 4.
De esta última tabla se desprende que la solución óptima es

Z=10

M: 3, U: 8, O: 8 C/D: 1/1
6.- Considere el siguiente problema de Programación Lineal:

Min Z=2 X1 +3 X2

s.a: X1 + 2X2 ≥ 4
3X1+ X2 ≥ 6
Xi, X2≥0

a) Transfórmela en un Problema Lineal Complementario (PLC).

Transformemos este problema en un PLC

La matriz M es:

M= 0 - AT
A 0
Por lo tanto:

A=1 2
3 1

El vector q es:

q= c`
b`

donde c`=(2,3), -b=(-4,-6)

Entonces, el problema lineal complementario (M,q) es:

0 0 -1 -3
M= 0 0 -2 -1 q= (2,3,-4,-6)`
1 3 0 0
2 1 0 0

M≥0, Z≥0, Mi.qi=0, para todo i.

Al resolver este problema obtenemos las soluciones del primal y del dual, puesto
que en el vector z están las correspondientes variables (X 1, X2, Y1, Y2)
.
b) Utilice el algoritmo del Pivote Complementario para resolver en caso de que sea
posible el PLC.

Expresemos el problema en forma tabular

w1 w2 w3 w4 z1 z2 z3 z4 q

1 0 0 0 0 0 1 3 2
0 1 0 0 0 0 2 1 3
0 0 1 0 -1 -3 0 0 -4
0 0 0 1 -2 -1 0 0 -6

Wi≥0, Zi≥0, Wi.Zi=0 para todo i

Introducimos la variable artificial Zo con su correspondiente vector columna -14.La tabla es:
 VB w1 w2 w3 w4 z1 z2 z3 z4 zo q

W1 1 0 0 0 0 0 1 3 -1 2
W2 0 1 0 0 0 0 2 1 -1 3
W3 0 0 1 0 -1 -3 0 0 -1 -4
W4 0 0 0 1 -2 -1 0 0 -1 -6

La variable que entra es zo y sale w4

VB w1 w2 w3 w4 z1 z2 z3 z4 zo q

W1 1 0 0 0 0 0 1 3 -1 2
W2 0 1 0 0 0 0 2 1 -1 3
W3 0 0 1 0 -1 -3 0 0 -1 -4
Z0 0 0 0 -1 2 1 0 0 1 6

La variable que entra es z4 y sale w3

VB w1 w2 w3 w4 z1 z2 z3 z4 zo q

W1 1 0 0 0 0 0 1 3 -1 2
W2 0 1 0 0 0 0 2 1 -1 3
Z4 0 0 -1 0 1 3 0 0 1 4
Z0 0 0 0 -1 2 1 0 0 1 6

La variable que entra es z3 y sale w1

VB w1 w2 w3 w4 z1 z2 z3 z4 zo q

Z3 -1 0 0 0 0 0 -1 -3 1 -2
W2 0 1 0 0 0 0 2 1 -1 3
Z4 0 0 -1 0 1 3 0 0 1 4
Z0 0 0 0 -1 2 1 0 0 1 6

La variable que entra es z1 y sale w2

 VB w1 w2 w3 w4 z1 z2 z3 z4 zo q

Z3 -1 0 0 0 0 0 -1 -3 1 -2
Z1 0 -1 0 0 0 0 -2 -1 1 -3
Z4 0 0 -1 0 1 3 0 0 1 4
Z0 0 0 0 -1 2 1 0 0 1 6

Se observa que la base actual no es una base complementaria factible.