Unidad 01 Programación Matemática Lineal

Semana 04
23 – 03 - 22

FACULTAD DE INGENIERÍA DE SISTEMAS E INFORMÁTICA

CURSO INVESTIGACIÓN OPERATIVA

LENGUAJE DEL TABLERO SIMPLEX

En el tablero Símplex, encontramos los siguientes términos, los que podemos
utilizar, para completar un tablero Símplex, y obtener la solución Símplex óptima, a
partir de un vértice óptimo, etc.
1. z j = CB B-1 aj

2. Y j = B-1 a j
( )
3. xB = B-1 b

4. Z0 = CB xB

Tabla3

Descríbase los términos: B , xB , cB , Yj

1 B es una sub matriz de A , de dimensión m : Formada por vectores columna,

linealmente independiente de la matriz. Por tanto B es una matriz básica, luego existe

su inversa B-1 .

2 x es un vértice (Concepto geométrico) del conjunto solución S, o

equivalentemente x , es una solución básica factible del Programa (Concepto

Algebraico). Entonces x ; tiene la siguiente estructura:

 xB   B-1b 
x = = 
 xN   0 

3 cB =  c1 , c2 , . . , cm  , son los coeficientes en la función objetivo, de las

variables que están en el tablero Símplex actual.

Profesor Carlos Rubén Guerrero Moncada Página 79

Unidad 01 Resolución de un PML método Símplex

APLICACIONES DEL FORMULARIO

Ejemplo

1. Resuelva gráficamente el siguiente programa lineal

Máx 30 x1 + 50 x2
St x1  4
2 x2  12
3x1 + 2 x2  18
x1  0 x2  0
2. Seguidamente convierta la solución óptima de vértice en su correspondiente
Solución Básica Factible y óptima (S. B. F.O.).
3. Haciendo uso de la tabla (). Escriba el tablero Símplex óptimo asociado a la
presente S.B.F.O

Resolución
Primeramente, se estandarizará el presente programa
Máx Z= 30 x1 + 50 x 2 + 0x3 + 0x4 + 0x5

St x1 + x3 = 4

2 x2 + x4 = 12 (1)

3 x1 + 2 x 2 + x5 = 18

x1  0 x2  0 x3  0 x4  0 x5  0

Evalúese el vértice óptimo ( x 1* , x 2* ) = (2, 6)t en el sistema (1),

Siendo por tanto la solución Básica Factible y Óptima asociada al presente vértice

 x1*   2 
     x *4 
xB* =  x 2*  =  6  y x N* =  * 
x 
 *  2  5
 3  
x

 1 0 1 1 0  4
   
La matriz de coeficientes A = a1, a2, a3, a4, a5 = 0 2 0 0 1 , b =  12 
 
3 2 0 0 0  18 
 
c =  c1, c2, c3, c4, c5 =  30, 50, 0 , 0, 0

x   x *4   0 
x =  B  , siendo xN =  *  =  
 x  0
 xN   5

Correo [email protected] Página 80

Unidad 01 Programación Matemática Lineal

B: Es la sub matriz de A, de columnas: a1, a2 y a3, asociadas a las variables básicas

 x1* 
 
xB* =  x 2* 
 *
 x3 
 1 0 1 0 -1 / 3 1 / 3

Así B = a1, a2, a3 = 0 2 0 y
 -1
  B = 0 1/2 0
3 2 0  1 1 / 3 -1 / 3
También cB = c1, c2, c3 = 30, 50, 0 , cN = c4, c5 = 0, 0, siendo z* = 30(2) + 50(6) =
360
3. El tablero Símplex, asociado a la solución óptima, será

Z x1 x2 x3 x4 x5 RHS

Z 0 0 0 360

x 1* 0 0 0 -1/3 1/3 2

x 2* 0 0 0 1/ 2 0 6

x 3* 0 0 0 1/3 -1/3 2

Continúe completándolo

Profesor Carlos Rubén Guerrero Moncada Página 81

Unidad 01 Resolución de un PML método Símplex

CASO N°1 Resolver cada uno de los siguientes programas gráficamente y luego

elabore el tablero Símplex óptimo, haciendo uso de la tabla ()

i. Máx 3 x1 + 9 x2 ii Mín - x1 - 3 x2
St x1 + 4 x2  8 St x1 - 2 x2  6
x1 + 2 x2  6 2x1 + x2  8
x1  0 x2  0 x1  0 x2  0

iii. Máx Z = 3x1 + 5x2 iv. Máx 2 x1 + x2

St 2x1 + 3x2  9 ST 2 x1 + x2  300
-2x1 + 3x2  6 x0 x1  100
x1  2 x2  180
x0 x0

CASO N°2 Para el sistema lineal

x1 + 2 x2 + 3 x3 + x4 = 10

x1 + x2 + x5 =5

x1 + x6 =1
I. Para el presente sistema, la matriz de coeficientes A; tiene rango igual 3
a. Luego el número máximo de soluciones básicas es de ___
b El número máximo de soluciones básicas factibles es de ___
II. A continuación tiene una serie se soluciones del presente sistema:

a. ( x 1 , x 2 , x 3 ) t = (1, 4, 1
3 )t b. ( x 3 , x5 , x6 )t = ( 10 3 , 5,1)t

c. ( x 1 , x 2 , x6 ) t = (0, 5, 1)t d. ( x 1 , x 2 , x5 ) t = (1, 9

2 , 0)t

e. ( x 1 , x 2 , x 3 ) t = ( 12 , 9
2 , 1
6 )t

Respecto a las soluciones anteriores, seguidamente se tiene una serie de

afirmaciones. Analícelas y responda (V), en caso de ser verdaderas, escriba (F) en otro
caso
i. Sólo (a) es solución básica
ii. Sólo (a) y (b) son soluciones básicas factibles

Correo [email protected] Página 82

 Unidad 01 Programación Matemática Lineal

iii. (e) es factible; pero no básica

iv. (d) es básica; pero no factible
v. (c) y (d) son factibles, además de ser básicas
vi. El presente sistema, tiene más soluciones factibles que soluciones básicas
vii. El presente sistema, tiene más soluciones no básicas que soluciones básicas
factibles
i. ii. iii. iv. v. vi. vii.

CASO N°3 Una compañía dispone de $35 millones para distribuirlos el próximo año

entre sus tres sucursales. Debido a compromisos de la estabilidad, el nivel de

empleados y por otras razones, la compañía ha establecido un nivel mínimo de fondos
para cada sucursal. Estos fondos mínimos son de $8, $10 y $15 millones,
respectivamente. Debido a la naturaleza de su operación, la sucursal 2 no puede
utilizar más de $20 millones.
Cada sucursal tiene la oportunidad de dirigir distintos proyectos con los fondos que
recibe. Para cada proyecto se ha establecido una tasa de ganancia (como un % de la
inversión). Por otra parte, algunos de los proyectos permiten sólo una inversión
limitada. A continuación, se dan los datos para cada proyecto.

Sucursal Proyecto Tasa de utilidad Inversión máxima

1 8% 16’

1 2 6% 5’

3 7% 9’

1 5% 7’

2 2 8% 10’

3 9% 4’

1 10% 6’

3 2 6% 12’

3 15% 6’
¿Cuál debe ser el plan de inversiones? Que maximice el capital
actual
Modelamiento:
a. Definamos las siguientes variables de decisión.

Profesor Carlos Rubén Guerrero Moncada Página 83

Unidad 01 Resolución de un PML método Símplex

Sea pij el capital invertido, por la sucursal - i, en el proyecto – j (i =1, 2, 3 y j = 1, 2, 3 )

Por ejemplo:
- p11 es el capital invertido por la sucursal - 1, en el proyecto - 1
- p13 es el capital invertido por la sucursal - 1, en el proyecto - 3
- p23 es el capital invertido por la sucursal - 2, en el proyecto - 3
b. Elaboración de restricciones.
b-1. De inversión total:
P11 + P12 + P13 + P21 + P22 + P23 + P31 + P32 + P33  35
b-2. De inversión mínima de cada sucursal.
P11 + P12 + P13  8
P21 + P22 + P23  10
P31 + P32 + P33  15
b-3. De disponibilidad, máxima para inversión en la sucursal - 2
P21 + P22 + P23  20
Agregando las restricciones, de disponibilidad máxima de recursos por cada
proyecto, tendremos el siguiente programa, por resolver:

Max .08P11+ .06P12+ .07P13+ .05P21+ .08P22+ .09P23+ .10P31+ .06P32+ .15P33

St
2) P11 + P12 + P13  8
3) P21 + P22 + P23  10
4) P31 + P32 + P33  15
5) P21 + P22 + P23  20
6) P11 + P12 + P13 + P21 + P22 + P23 + P31 + P32 + P33  35
7) P11  16
8) P12  5
9) P13  9
10) P21  7
11) P22  10
12) P23  4
13) P31  6
14) P32  12
15) P33  6
End
Seguidamente tenemos la solución óptima.

Correo [email protected] Página 84

Unidad 01 Programación Matemática Lineal

RESPONDER EL SIGUIENTE CUESTIONARIO

I. Esta mezcla de inversiones, produce una utilidad máxima de _____ millones de

dólares
II. Completar la información faltante. El programa sugiere que lo mejor que se puede
hacer es invertir:
a. ____ en el proyecto 1, de la sucursal 1 b. ____ en el proyecto 3, de la sucursal 2

c. ____ en el proyecto 2, de la sucursal 1 d. ____ en el proyecto 1, de la sucursal 3

e. ____ en la sucursal 1 f. ____ en la sucursal 2

g. en la sucursal 3

III. La utilidad producida por cada sucursal es:

a. Sucursal – 1: _____ b. Sucursal – 2: _____ c. Sucursal – 3: _____

IV. Seguidamente tiene una serie de preguntas: Analícelas y su respuesta colóquela en

la tabla que está al final del cuestionario
1. El porcentaje de su disponibilidad máxima que utiliza el P 2 3 .es:
2. Los proyectos, que no utilizan sus recursos al 100%, suman

4. Si la disponibilidad máxima de recursos del P 31 , se disminuye 1'. El nuevo valor del

programa será

5. Si la disponibilidad máxima de recursos del P 32 , se aumenta en 1'. El nuevo valor del

programa será

6. Si la disponibilidad máxima de recursos del P 32 , se aumenta 2'. El nuevo valor del

programa será

7. Si la disponibilidad máxima de recursos de P 31 , se disminuye 2'. El valor objetivo actual.

a. Empeorará b) Mejorará c) No se modificará d) Falta información

8. Si la disponibilidad máxima de recursos de P 11 se aumenta 1'. El valor objetivo
actual.
a. Empeorará b) Mejorará c) No se modificará d) Falta información
9. Si la disponibilidad máxima de recursos de P 2 3 , se disminuye 2'. El valor

objetivo actual.
a) Empeorará b) Mejorará c) No se modificará
10. Si el recurso mínimo asignado a la sucursal 1, se disminuye en $2. El
valor actual del programa
a) Se modifica. b) No se puede predecir c) Falta información
11. El porcentaje de su recurso máximo que es utilizado por el proyecto P32 es:

Profesor Carlos Rubén Guerrero Moncada Página 85

Unidad 01 Resolución de un PML método Símplex

12. Si la disponibilidad máxima de recursos de P11 , se disminuye 1'. El valor

objetivo:
a. Empeorará b. Mejorará c. No se modificará d. falta información
13. Si existe la opción de ampliar en 1’. la inversión en: P 32 o P23 . Sería más

rentable invertir en:

14. Si al recurso mínimo de la sucursal 2, se añade $2. El valor del programa:

a.1) Aumenta a.2) Disminuye a.3) No se modifica. a.4) Falta

información
15. Si la sucursal - 3 ampliara su recurso máximo en $2. El valor actual del
programa:

a.1) Aumenta a.2) Disminuye a.3) No se modifica. a.4) Falta

información
16. Lo mínimo que debe aumentar la utilidad del P 2 1 , para que se vuelva
rentables es:

17. Lo mínimo que debe aumentar la utilidad del P 1 2 , para que se vuelva
rentables es:
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12)

13) 14) 15) 16) 17

18. En cada uno de los siguientes casos: Cuál será el nuevo valor del
programa. Si considera que falta información; escriba F
a. Si se disminuye un millón al proyecto 3 de la sucursal 2 y este se asigna al proyecto
3 de la sucursal 3
b. Si se disminuye dos millones al proyecto 1 de la sucursal 1 y estos se
asignan: Uno al proyecto 3 de la sucursal 2 y el otro al proyecto 1 de la
sucursal 3
c. Si se disminuye dos millones al proyecto 3 de la sucursal 2 y estos se
asignan al proyecto 3 de la sucursal 3
d. Si se disminuye 0.02 la utilidad del proyecto 1 de la sucursal 3 y se añade
0.01 a la utilidad del proyecto2 de la sucursal 3.
e. Si se disminuye tres millones al proyecto 2 de la sucursal 2 y estos se
asignan: Uno al proyecto 3 de la sucursal 1 y los otros al proyecto 3 de la
sucursal 3

Correo [email protected] Página 86

Unidad 01 Programación Matemática Lineal

a. b. c. d. e.

CASO N°4

El gobierno peruano, planea un programa de desarrollo educacional, para los

próximos siete años; mediante el cual los profesores, serán enviados a la sierra,
para enseñar en las escuelas primarias de dicha región. Los profesores pueden ser
contratados por: 1, 2, 3 ó 4 años. A continuación, se tienen los siguientes costos (en
dólares) asociados, al número de años, que dura el contrato.

Años 1 2 3 4
Costo 600 1080 1440 1800
Tabla-a

El número mínimo de profesores requeridos cada año, es el siguiente:

Años 1 2 3 4 5 6 7
Mínimo requerido 800 1600 2700 3100 3500 3700 3900

Tabla-b
Se supone que este programa de reclutamiento de profesores, sólo será necesario,
durante los próximos siete años.
El mercado no ofrece más de 1000 profesores cada año.
Determine la política de contrataciones, para los próximos siete años, que haga
mínimo el costo del plan.

MODELAMIENTO
a. Identifiquemos las siguientes variables de decisión:
Llamemos: x i j al número de profesores, contratados el año i y que trabajarán

durante j años (i = 1, . . ,7 y j = 1, . ,4)

Por ejemplo:
x 2 4 : Es el número de profesores contratados el 2do año y que trabajarán 4 años.

x11 : Es el número de profesores contratados el primer año y que trabajarán durante

un año.
x1 2 : Es el número de profesores contratados el primer año y que trabajarán dos

años, etc.
b. Se tendrá dos tipos de restricciones:
• De oferta máxima cada año. (no más de 1 000)

Profesor Carlos Rubén Guerrero Moncada Página 87

Unidad 01 Resolución de un PML método Símplex

• De demanda mínima para cada año (según Tabla- b)

Luego el programa por resolver será:

Mín 600 x 11 + 1080 x 1 2 +1440 x 1 3 +1800 x 1 4 + 600 x 2 1

+1080 x 2 2 + 1440 x 2 3 +1800 x 2 4 + 600 x 3 1 +1080 x 3 2

+1440 x 3 3 + 1800 x 3 4 + 600 x 4 1 +1080 x 4 2 +1440 x 4 3

+1800 x 4 4 + 600 x 5 1 +1080 x 5 2 +1440 x 5 3 + 600 x 6 1

+1080 x 6 2 + 600 x 7 1

St
2) x11 + x12 + x13 + x14  1000

3) x21 + x22 + x23 + x24  1000

4) x31 + x32 + x33 + x34  1000

5) x 41 + x 42 + x 43 + x 44  1000

6) x51 + x52 + x53  1000

7) x61 + x62  1000

8) x71  1000

9) x11 + x12 + x13 + x14  800

10) x12 + x13 + x14 + x21 + x22 + x23 + x24  1600

11) x13 + x14 + x22 + x23 + x24 + x31 + x32 + x33 + x34  2700

12) x14 + x23 + x24 + x32 + x33 + x34 + x 41 + x 42 + x 43 + x 44  3100

13) x24 + x33 + x34 + x 42 + x 43 + x 44 + x51 + x52 + x53  3500

14) x34 + x 43 + x 44 + x52 + x53 + x61 + x62  3700

15) x 44 + x53 + x62 + x71  3900

End
Seguidamente tenemos la solución óptima

Correo [email protected] Página 88

Unidad 01 Programación Matemática Lineal

DESARROLLAR EL SIGUIENTE CUESTIONARIO

1. El costo óptimo del proyecto será: _________

2. Conviene contratarse profesores por tres años: los años:
3. Conviene contratar profesores por un año; en los años:
4) El segundo año, se debe trabajar con ____ profesores
5. El 5to año, se debe trabajar, con ___ profesores, contratados el 3er año
6. Conviene contratar ____ profesores, el quinto año
7. Se debe planificar un gasto de ____ por todos los profesores, que fueron
contratados por un año.
8) Se debe planificar un gasto de ____ por todos los profesores, que trabajarán el
segundo un año.
9. Actualmente no conviene contratar profesores el primer año por un año ( x 1* 1 = 0).

Si hubiera obligación de contratar por lo menos uno. ¿Cuánto debería disminuir,

su costo actual?
10. El costo actual de contratar un profesor, el primer año por 3 años es $1440. Si
este disminuyera $100. ¿Cuál sería el nuevo valor del programa?
11. ¿El número de profesores ofrecidos por el mercado, para el quinto año, que no
conviene contratar, suman?
12. Si la oferta de profesores para el tercer año, se ampliara de 1000 a 1050. ¿El
nuevo valor del programa sería?
13. Si el mercado ofreciera 50 profesores adicionales, para el cuarto año. ¿Cuál
sería el nuevo valor del programa? ¿Sería provechosa para el proyecto esta
ampliación?
14. Si el mercado ofrece 50 profesores adicionales, para el tercer o cuarto año. En
qué año sería más provechoso tomarlos
15. Si hubiera la opción de disminuir la demanda de un profesor, durante el sexto
año. ¿Cuál sería el nuevo valor del programa?¿Sería provechosa para el proyecto
esta ampliación?
16. Si hubiera la opción de disminuir la demanda de un profesor, durante el
séptimo año. ¿Cuál sería el nuevo valor del programa? ¿Sería provechosa para el
proyecto esta ampliación?
17. Si existiera la opción de disminuir la demanda de profesores, en los años sexto
o séptimo. ¿Cuál sería más provechoso?

Profesor Carlos Rubén Guerrero Moncada Página 89

Unidad 01 Resolución de un PML método Símplex

18. Si existiera el mercado pudiera ampliar la oferta de profesores, para el tercer

año de 1 000 a 1 200. ¿Esta modificación mejoraría el valor actual del proyecto?
19. Si el proyecto, demandara para el sexto año; no menos de 3 950 profesores.
¿Esta modificación afectara el valor actual del proyecto?
20. ¿Cuál sería el nuevo valor del programa, si la oferta de profesores, en el cuarto
año; disminuye en 100?
21. Si la oferta del primer año, disminuyera en 100. ¿El nuevo valor del programa
será?
22. Si la oferta del 2do año, se redujera a 900. ¿El nuevo valor del programa será?

Correo [email protected] Página 90