UPIICSA – IPN – ACADEMIA DE I.O.

INVESTIGACIÓN DE
OPERACIONES 1

MÉTODO SIMPLEX
Formas equivalentes de un Modelo de Programación Lineal.

Después de la formulación de un problema de programación lineal, las siguientes etapas

a considerar en el método para la obtención de la solución son, modificar el modelo y adaptarse
a la forma canónica o bien a la forma estándar. La primera es esencialmente útil para la teoría
de la dualidad, y la segunda es para desarrollar el procedimiento general para solución de
cualquier problema de programación lineal.

I) Forma canónica.
Max Z = cx
s.a : Ax �b
x �0

Características:

1)La función objetivo es para maximizar.

2)Todas las restricciones son del tipo 
3)Todas las variables de decisión son no-negativas.
4)El modelo se puede expresar matricialmente.
NOTA: Si al menos una no se cumple no es forma canónica.

II) Forma estándar.

Max Z ó Min Z = cx
s.a : Ax = b
x �0

Características:
1) La función objetivo puede ser para maximizar o bien para minimizar.
2) Todas las restricciones son igualdades.
3) El lado derecho de las restricciones son cantidades no negativas.
4) Las variables de decisión son no negativas.
5) El modelo se puede expresar matricialmente.

La forma estándar es especialmente útil para la presentación de la información del

problema de P.L. y como preparación de la tabla para obtener la solución.

Para resolver el problema por el método simplex, el modelo primero se lleva a la forma
canónica y luego a la forma estándar. Es necesario para transformar el modelo a las formas
mencionadas, conocer las siguientes reglas algebraicas, llamadas reglas de equivalencia:

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 1

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Reglas de Equivalencia (algebraicas):

1. Toda función objetivo de un modelo de programación lineal, cumple:

Max Z = - Min ( - Z ) o bien Min Z = - Max ( - Z )

Ejemplo:
Sea Z = {-8, 0, 3, 11} ; (-Z) = {-11, -3, 0, 8,}
Entonces el Max Z = 11 = - Min (- Z) = - (-11) = 11
Min Z = -8 = - Max (- Z) = - Max (8) = -8

2. Toda desigualdad invierte su sentido si se multiplica por (- 1).

sea: aX  b  - aX  - b ; ó aX  b  - aX  - b

Ejemplo: 4 < 10  -4 > -10

3. Toda ecuación puede expresarse como un sistema de 2 desigualdades en sentido opuesto;

esto es:
Si aX = b  aX  b y aX  b ó aX  b y - aX ≤ - b (reemplaza a la primera)

Ejemplo: Considere la ecuación 3X - 2 = 7, cuyas solución es X = 3; por lo tanto, si se

descompone en dos desigualdades la solución del sistema es igual a la solución de la ecuación.

3X - 2 = 7  3X - 2  7 y 3X - 2  7
X=3  X  3 y X  3
X  (- , 3]  [3, ) = 3

4. Toda restricción  puede expresarse como una igualdad sumando una variable no negativa,
al lado izquierdo de la restricción llamada variable de holgura.

Si: aX  b  aX + H = b ; H  0

Toda restricción del tipo  puede expresarse como una igualdad restando del lado izquierdo
una variable no negativa llamada variable superflua o de superávit, esto es:

Si: aX  b  aX - S = b ; S  0

5. Una variable libre (o no restringida en su valor) se puede expresar como la diferencia de dos
variables no negativas.

Si X es libre  X [- ,  ]

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 2

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

La variable libre se puede expresar como:

X=Y-Z ; Y0 , Z0

Por lo tanto:

Si X < 0  (Y - Z) < 0  Y<Z

Si X = 0  (Y - Z) = 0  Y=Z
Si X > 0  (Y - Z) > 0  Y>Z

EJEMPLO 1:

Dado el siguiente modelo, determinar su forma canónica y su forma estándar.

Min Z = - x1  2 x2  x3
s. a : x1  x2 - x3  6
- 2 x1  3 x2 =8
- 4 x 2  3 x3  - 1
x1  0, x2 libre , x3  0

a) Forma canónica:

- Miax (- Z ) = x1 - 2 x2 - x3
s. a : x1  x2 - x3  6
Sea : Y1 = x1
- 2 x1  3 x2 8
Y2 - Y3 = x2
2 x1 - 3 x2  -8
Y4 = - x3
4 x2 - 3 x3  1
x1  0, x2 libre , x3  0

Haciendo el cambio de variables propuesto y escribiendo el modelo matricialmente:

�Y1 �
�Y�
- Miax ( - Z ) = ( 1, - 2, 2, 1) �2 �
�Y3 �
- Miax (-Z ) = Y1 - 2Y2  2Y3  Y4 ��
�Y4 �
s. a : Y1  Y2 - Y3  Y4 �6
�1 1 - 1 1 �� Y1 � � 6 �
- 2Y1  3Y2 - 3Y3 �8 �
- 2 3 - 3 0
��
Y2 � � �
s. a : � �� ��� 8 �
2Y1 - 3Y2  3Y3 �-8 � 2 - 3 3 0 �� Y3 � � - 8�
� �� � � �
� 0 4 - 4 3 ��4 � � 1 �
Y
4Y2 - 4Y3  3Y3 �1
�Y1 � ��0
Y1 �0, Y2 �0, Y3 �0, Y4 �0 �Y � ��
0
�2 ����
�Y3 � ��0
� � ��
Y
�4 � �� 0

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 3

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

b) Forma estándar:
La función objetivo queda igual, sin hacer el cambio de variables pertinente, transformaremos
las desigualdades en igualdades
Min Z = - x1  2 x2  x3
s. a : x1  x2 - x3  6
- 2 x1  3 x2 =8
- 4 x2  3 x3  - 1
x1  0, x2 libre , x3  0

Explicación:

Se convierte el lado derecho de la desigualdad en un valor no-negativo antes de convertir las

restricciones en igualdad.

 La primera restricción es del tipo ( ≤ ), lo que implica por la regla cuatro de equivalencia
agregar una variable de holgura para convertirla en una igualdad (note que el lado
derecho de la restricción es no-negativo)
 La segunda restricción ya es una igualdad con el lado derecho no-negativo, por lo que
queda igual.
 La tercera restricción es del tipo ( ≥ ) pero el lado derecho es negativo, lo que nos obliga
antes de convertirla en igualddad multiplicarla por ( - 1), esto hace que el tipo de
desigualdad cambie a ( ≤ ). Es entonces una variable de holgura la que se debe de
agregar.

Min Z = - x1  2 x2  x3
s. a : x1  x2 - x3  H1 = 6
- 2 x1  3 x2 =8
4 x2 - 3 x3  H2 = 1
x1 �0, x2 libre, x3 �0 H 1 �0, H 2 �0
(en x2 se aplica regla 5)
Proponemos el mismo cambio de variables que se propuso para la forma canónica
Donde : Y1 = x1 Y2 - Y3 = x2 ; - Y4 = x3

Sustituyendo las variables y escribiendo matricialmente la forma estándar del modelo:

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 4

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Min Z = Y1  2(Y2 - Y3 ) - Y4
s.a : Y1  Y2 - Y3  Y4  H1 =6
- 2Y1  3Y2 - 3Y3 =8
4 Y2 - 4Y3  3Y4  H2 = 1
Y1  0, Y2  0, Y3  0, Y4  0, H2  0 H1  0,
Y1 �
�
�
Y2 �
� �
�
Y3 �
Min Z = ( -1, 2, - 2, - 1, 0, 0 ) � �
Y4 �
�
�
H �
�1�
H2 �
�
Y1 �
�
�
Y2 �
�1 1 - 1 1 1 0 � � � 6
��
� �
Y �
s.a : �-2 3 - 3 0 0 0 �
�
3
� � = ��
8
��
�0 4 - 4 3 0 1 � Y4 �
�
� � ��
1
��
�
H �
�1�
H2 �
�
Y1 � ��
� 0
� �
Y2 � 0��
� ��
�
Y3 � ��
0
� � ���
Y4 � ��
� 0
�
H � ��
0
� 1 � ��
0
H 2 � ��
�

PROCEDIMIENTO DEL MÉTODO SIMPLEX

Para aplicarlo, el modelo debe estar en forma canónica, y el lado derecho de las
restricciones deben de ser valores no-negativos.

EJEMPLO:

I.- Forma canónica.

Max Z = 20 x1  30 x2
s.a : 3 x1  x2 �24
x1  x2 �10
x1  2 x2 �16
x1 �0; x2 �0

II.- Estandarizando la forma canónica.

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 5

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Max Z = 20 x1  30 x2
s.a : 3x1  x2  H1 = 24
x1  x2  H2 = 10
x1  2 x2  H 3 = 16
x1 �0; x2 �0; H i �0
Considerar el sistema de ecuaciones lineales pasando todas las variables al lado
izquierdo (igualando a cero la unción objetio).

Z - 20 x1 - 30 x2 = 0
s.a : 3x1  x2  H1 = 24
III.-
x1  x2  H2 = 10
x1  2 x2  H 3 = 16

IV.- Con los coeficientes del sistema se forma la siguiente tabla ( la tabla muestra la solución
del problema = tabla inicial del método = solución trivial ).

Vb Z X1 X2 H1 H2 H3 Zo
1 - 20 -30 0 0 0 0
H1 0 3 1 1 0 0 24
H2 0 1 1 0 1 0 10
H3 0 1 *2 0 0 1 16
1 -5 0 0 0 15 240
H1 0 5/2 0 1 0 -½ 16
H2 0 *½ 0 0 1 -½ 2
X2 0 ½ 1 0 0 ½ 8
1 0 0 0 10 10 260
H1 0 0 1 1 -5 2 6
X1 0 1 0 0 2 -1 4
X2 0 0 0 0 -1 1 6

* Elemento pivote.

SOLUCIÓN OPTIMA: Z = 260

X1 = 4
X2 = 6

 Se van determinando valores para las variables que deben ser no negativas.
 Los valores negativos no se toman en cuenta.

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 6

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

 El elemento pivote determinará la variable que saldrá o dejará de ser básica, entonces esa
columna se transformará de tal manera que todos los elementos sean cero, excepto el
elemento pivote (que siempre será igual a 1).
 Cuando la tabla muestra en la función objetivo todos sus elementos en cero o no-negativos
será una solución óptima para Z, tal situación se define como criterio de optimalidad.

EJEMPLO: Determine la tabla inicial del método simplex del siguiente problema de P. L.

Min Z = - 3w1  2w2

s.a : - w1  w2 �- 6
w1 - 3w2 � 12
w1 �0; w2 �0

1) Forma canónica.

La segunda restricción se multiplica por ( -1 )

Min Z = - 3w1  2w2

s.a : w1 - w2 � 6
w1 - 3w2 � 12
w1 �0; w2 �0

Aplicando la primera regla de equivalencia a la función objetivo:

Min Z = -3W1 + 2W2 - Max (-Z) = 3W1 - 2W2

Se propone el siguiente cambio de variables:

W 1 = X 1 ; W2 = - X 2 y sustituyendo en el modelo los cambios:

- Max (- Z ) = 3x1  2 x2
s.a : x1  x2 � 6
x1  3 x2 � 12
x1 �0; x2 �0

Estandarizando la forma canónica:

El modelo tiene restricciones del tipo (  ), por lo tanto se agregaran variables de holgura

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 7

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

- Max (- Z ) = 3x1  2 x2
s.a : x1  x2  H1 = 6
x1  3x2  H 2 = 12
x1 �0; x2 �0; H i �0

Considerando solo el sistema de ecuaciones:

- Z - 3x1 - 2 x2 = 0
x1  x2  H1 = 6
x1  3x2  H 2 = 12
Vb Z X1 X2 H1 H2 Zo
-1 -3 -2 0 0 0
H1 0 1 1 1 0 6
H2 0 1 3 0 1 12

EJEMPLO: Detrmine la solución óptima del siguiente modelo

Max Z = 4X1 + X2 - X3
s.a. 2X1 + 3X3  8
3X2 + X3  20
5X1 + X2 + X3  16
Xj  0

Estandarizando la forma canónica:

Max Z = 4X1 + X2 - X3
2X1 + 3X3 + H1 = 8
3X2 + X3 + H2 = 20
5X1 + X2 + X3 + H3 = 16
Xj  0 , H i  0

Z - 4 X 1 - X2 + X 3 = 0
2X1 + 3X3 + H1 = 8
3X2 + X3 + H2 = 20
5X1 + X2 + X3 + H3 = 16

Vb Z X1 X2 X3 H1 H2 H3 Zo
1 -4 -1 1 0 0 0 0
H1 0 2 0 3 1 0 0 8
H2 0 0 3 1 0 1 0 20
- H3 0 5 1 1 0 0 1 16
1 0 -1/5 9/5 0 0 4/5 64/5
H1 0 0 -2/5 13/5 1 0 -2/5 8/5
UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 8
GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

- H2 0 0 3 1 0 1 0 20
X1 0 1 1/5 1/5 0 0 1/5 16/5
1 0 0 28/15 0 1/15 4/5 212/15
H1 0 0 0 17/5 1 2/15 2/5 64/15
X2 0 0 1 1/3 0 1/3 0 20/3
X1 0 1 0 2/15 0 -1/3 1/5 28/15

Z* = 212/15 SOLUCIÓN OPTIMA

X1 = 28/15 ; X2 = 20/3

TÉCNICAS A VARIABLES ARTIFICIALES

Esta técnica consiste en agregar a las restricciones del tipo  o de igualdad, una nueva
variable llamada variable artificial, cuya característica fundamental es que su valor es cero.
Existen dos métodos que utilizan tal técnica, que son:

a) El método de la Doble Fase.

b) El método Penal o de la Gran M.

Cuando un problema no tiene solución se detecta mediante estos métodos, apareciendo

al menos una de las variables artificiales usadas deferentes de cero, esto es, que en la tabla
óptima aparece al menos una variable artificial.

MÉTODO DOBLE FASE

Este método consiste en dos fases.

PRIMERA FASE:
Consiste en resolver el siguiente problema:

Min  = w i ( wi var iable artificial)

Ax = b 
s. a : Mismas Re stricciones del problema original
x  0


Se pueden presentar las siguientes situaciones:

1. En la tabla óptima de este problema, al menos una de las variables artificiales se quedó en
la base, entonces se termina el proceso y se establece que el problema no tiene solución.
2. La tabla óptima no contiene variables artificiales (o sea todas las Wi son iguales con cero) el
problema tiene solución y se pasa a la segunda fase.

SEGUNDA FASE:

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 9

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Se considera la tabla óptima de la primera fase, se eliminan las columnas de las

variables artificiales y se reemplazan los coeficientes de la función objetivo original. Se itera de
acuerdo al tipo de optimización del problema original, la tabla óptima de esta segunda fase
muestra la solución del problema original.

EJEMPLO #1: Determine la solución óptima del sig. Modelo, utilizando el método doble fase.

Max Z = 2 x1  3 x 2 - x3
s.a : x1  x 2  x3 = 7
2 x1 - 5 x 2  x3  10
x1  0; x 2  0; x3  0

I. Primeramente se determina si el problema se puede resolver por el método simplex,

mediante la estandarización del modelo.
II. En este ejemplo se puede observar que las variables que restan al modelo no pueden
generar la base inicial.
III. Por lo tanto, para construir la tabla inicial se agregan las variables artificiales, a la forma
estándar.
Max Z = 2 x1  3 x 2 - x3
s.a : x1  x 2  x3  w1 = 7
2 x1 - 5 x 2  x3 - S  w2 = 10
x1  0; x 2  0; x3  0; S  0; wi  0
Wi = son variables artificiales que mantenemos en la base.

PRIMERA FASE:
Min  = w1  w2
s.a : x1  x 2  x3  w1 = 7
2 x1 - 5 x 2  x3 - S  w2 = 10
x1  0; x 2  0; x3  0; S  0; wi  0

Se pasan las variables del lado izquierdo.

I. Con los coeficientes del sistema de ecuaciones se construye la tabla inicial.

II. Como se puede observar la tabla inicial presenta la anomalía de que las columnas de las
variables Artificiales no son elemental unitarias, por lo tanto antes de iterar para optimizar la
tabla, se recuperará lo elemental unitario de las columnas, mediante operaciones
III. elementales entre renglones.
IV. Se optimiza cuando ya no existen valores positivos o cero en el renglón de la función
objetivo.

PRIMERA FASE:

Vb Z X1 X2 X3 S W1 W2 Zo
1 0 0 0 0 -1 -1 0

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 10

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

W1 0 1 1 1 0 1 0 7
W2 0 2 -5 1 -1 0 1 10
1 3 -4 2 -1 0 0 17
W1 0 1 1 1 0 1 0 7
W2 0 2 -5 1 -1 0 1 10
1 0 7/2 1/2 1/2 0 -3/2 2
W1 0 0 7/2 1/2 1/2 1 -1/2 2
X1 0 1 -5/2 1/2 -1/2 0 1/2 5
1 0 0 0 0 -1 -1 0
X2 0 0 1 1/7 1/7 2/7 -1/7 4/7
X1 0 1 0 6/7 -1/7 5/7 1/7 45/7

Sí existe solución.
Se debe obtener lo siguiente en la segunda etapa:

 Las columnas de las variables básicas deben ser elementales unitarias.

 Selección del coeficiente más negativo ya que la función objetivo en el problema original es
para maximizar.
 Se optimiza cuando ya no existan valores positivos en el renglón de z j - cj o bien sean ceros.
 Se itera hasta alcanzar la tabla óptima, que mostrará la solución óptima del problema.

TABLA SEGUNDA FASE:

Vb Z X1 X2 X3 S Zo
1 -2 -3 1 0 0
X2 0 0 1 1/7 1/7 4/7
X1 0 1 0 6/7 -1/7 45/7
1 0 0 22/7 1/7 102/7
X2 0 0 1 1/7 1/7 4/7
X1 0 1 0 6/7 -1/7 45/7

Z* = 102/7 SOLUCIÓN OPTIMA ;

X1 = 45/7 ; X2 = 4/7 ; X3 = 0

EJEMPLO #2: Determinar la solución mediante un método no gráfico del siguiente modelo:
(Mediante el método doble fase)

Min Z = 24Y1 + 10Y2 + 16Y3

s.a. Y1 + Y2 + 2Y3  20
3Y1 + Y2 + Y3  30
Yj  0

Solución:

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 11

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Min Z = 24 Y1 + 10Y2 + 16Y3

s.a. Y1 + Y2 + 2Y3 - S1 + W1 = 20
3Y1 + Y2 + Y3 - S2 + W2 = 30
Yj  0

Min Z = W1 + W2
s.a. Y1 + Y2 + 2Y3 - S1 + W1 = 20
3Y1 + Y2 + Y3 -S2 + W2 = 30
Yj  0

PRIMERA FASE:

Vb Z Y1 Y 2 Y3 S1 S2 W1 W2 Zo
1 0 0 0 0 0 -1 -1 0
W1 0 1 1 2 -1 0 1 0 20
W2 0 3 1 1 0 -1 0 1 30
1 4 2 3 -1 -1 0 0 50
W1 0 1 1 2 -1 0 1 0 20
W2 0 3 1 1 0 -1 0 1 30
1 0 2/3 5/3 -1 1/3 0 -4/3 10
W1 0 0 2/3 5/3 -1 1/3 1 -1/3 10
Y1 0 1 1/3 1/3 0 -1/3 0 1/3 10
1 0 0 0 0 0 -1 -1
Y3 0 0 2/3 1 -3/5 1/4 3/5 -1/5 6
Y1 0 1 1/5 0 1/5 -2/5 -1/5 2/5 8

SEGUNDA FASE:

Vb Z Y1 Y2 Y3 S1 S2 Zo
1 -24 -10 -16 0 0 0
Y3 0 0 2/5 1 -3/5 1/5 6
Y1 0 1 1/5 0 1/5 -2/5 8
1 0 6/5 0 -24/5 -32/5 288
Y3 0 0 2/5 1 -3/5 1/5 6
Y1 0 1 1/5 0 1/5 -2/5 8
1 0 0 -3 -3 -7 270*
Y2 0 0 1 5/2 -15/10 -1/2 15
UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 12
GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Y1 0 1 0 -1/2 5/10 -1/2 5

Solución:

Z* = 270 ; X1 = 5 ; X2 = 15 ; X3 = 0

MÉTODO PENAL

Este método consiste en penalizar las variables artificiales sobre la función objetivo
mediante un coeficiente muy grande  M, en donde, M  , (+M si el problema es para
minimizar y - M si el problema es para maximizar).

Se complementa la estandarización. Se hace con las variables artificiales en las

restricciones del tipo  o bien de igualdad. Si el problema es de maximizar: se restan todas las
variables artificiales. Se itera hasta alcanzar la tabla óptima. Si aparece al menos una variable
artificial en la base en la tabla óptima, entonces se dice que el problema no tiene solución. En
otro caso, la solución que muestra la tabla óptima es la solución óptima del problema dado.

NOTA: Este método sirve para problemas donde necesariamente son indispensables las
variables artificiales.

EJEMPLO #1: Resolver el siguiente problema de P. L.

Min Z = 2 x1  4 x2  x3
s.a.: x1  2 x2 - x3 �5
2 x1 - x2  2 x3 = 2
- x1  2 x2  2 x3 �1
x1 �0; x2 �0; x3 �0
1) Estandarizar el modelo:

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 13

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Min Z = 2 x1  4 x2  x3
s.a.: x1  2 x2 - x3  H = 5
2 x1 - x2  2 x3 =2
- x1  2 x2  2 x3 - S =1
x1 �0; x2 �0; x3 �0; H �0; S �0
2) Agregando las variables artificiales:

Min Z = 2 x1  4 x2  x3
s.a.: x1  2 x2 - x3  H = 5
2 x1 - x2  2 x3  w1 =2
- x1  2 x2  2 x3 -S  w2 = 1
x1 �0; x2 �0; x3 �0; H �0; S �0; wi �0
3) Haciendo aparecer las variables artificiales en la función objetivo multiplicadas por (+M):

Min Z = 2 x1  4 x2  x3  Mw1  Mw2

s.a.: x1  2 x2 - x3  H = 5
2 x1 - x2  2 x3  w1 =2
- x1  2 x2  2 x3 -S  w2 = 1
x1 �0; x2 �0; x3 �0; H �0; S �0; wi �0

4) Considerando solamente el sistema de ecuaciones e igualando a cero la función objetivo:

Z - 2 x1 - 4 x2 - x3 - Mw1 - Mw2 = 0
s.a.: x1  2 x2 - x3  H = 5
2 x1 - x2  2 x3  w1 =2
- x1  2 x2  2 x3 - S  w2 = 1
5) Formando la tabla inicial, con los coeficientes de las variables del sistema de ecuaciones

Vb Z X1 X2 X3 H W1 S W2 Zo
1 -2 -4 -1 0 -M 0 -M 0
H 0 1 2 -1 1 0 0 0 5
W1 0 2 -1 2 0 1 0 0 2
W2 0 -1 2 2 0 0 -1 1 1
1 M-2 M-4 4M-1 0 0 -M 0 3M
H 0 1 2 -1 1 0 0 0 5
W1 0 2 -1 2 0 1 0 0 2
W2 0 -1 2 2 0 0 -1 1 1
1 3M-5/2 -3M-3 0 0 0 -1/2 -2M+1/2 M+1/2
H 0 1/2 3 0 1 0 -1/2 1/2 11/2
UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 14
GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

W1 0 3 -3 0 0 1 1 -1 1
X3 0 -1/2 1 1 0 0 -1/2 1/2 1/2
1 0 -11/2 0 0 -M+5/6 1/3 -M-1/3 4/3
H 0 0 7/2 0 1 -1/6 -2/3 2/3 16/3
X1 0 1 -1 0 0 1/3 1/3 -1/3 1/3
X3 0 0 1/2 1 0 1/6 -1/3 1/3 2/3
1 -1 -9/2 0 0 -M+1/2 0 -M 1
H 0 2 3/2 0 1 1/2 0 0 6
S 0 3 -3 0 0 1 1 -1 1
X3 0 1 -1/2 1 0 1/2 0 0 1

La última tabla (tabla óptima) muestra la solución óptima del problema:

Z* = 1, para X1 = X2 = 0; X3 = 1

EJEMPLO #2: Resolver el siguiente problema de P. L.

Min Z = 24 y1  10 y2  16 y3
s.a : y1  y2  2 y3 �20
3 y1  y2  y3 �30
y1 �0; y2 �0; y3 �0

Vb Z y1 y2 y3 S1 S2 W1 W2 Zo
1 - 24 - 10 - 16 0 0 -M -M 0
W1 0 1 1 2 -1 0 1 0 20
W2 0 3 -1 1 0 -1 0 1 30
1 4M-24 2M-10 3M-16 -M -M 0 0 50M
W1 0 1 1 2 -1 0 1 0 20
W2 0 3 1 1 0 -1 0 1 30
1 0 2/3M-2 4/3M-8 -M 1/3M-8 0 - 4/3M+8 10M+240

W1 0 0 2/3 5/3 -1 1/3 1 - 1/3 10

y1 0 1 1/3 1/3 0 - 1/3 0 1/3 10
1 0 6/5 0 - 24/5 - 32/5 - M+24/5 -M+32/5 288
y3 0 0 2/5 1 - 3/5 1/5 3/5 - 1/5 6

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 15

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

y1 0 1 1/5 0 1/5 - 2/5 - 1/5 2/5 8

1 0 0 -3 -3 -7 - M+3 - M+7 270
y2 0 0 1 5/2 - 3/2 1/2 3/2 - 1/2 15
y1 0 1 0 - 1/2 1/2 - 1/2 - 1/2 1/2 5

EJERCICIOS DEL MÉTODO PENAL, DOBLE FASE

1.- Escriba 3 métodos diferentes y sus modelos, para resolver el siguiente problema:

Min Y = 6 y1  7 y2  3 y3  5 y4
S . A. 5 y1  6 y2  3 y3  4 y4 �12
y2  5 y3 - 6 y4 �10
2 y1  5 y2  y3  y4 �8
y j �0

2.- Encuentre la solución óptima del siguiente modelo de programación lineal.

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 16

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Min Z =5 x1 -6 x 2 -7 x3
S . A. 2 x1 10 x 2 -6 x3  30
5
x1 -3 x 2 5 x3  10
2
2 x1  2 x 2  2 x3 = 5
x1 , x 2 , x3 0

3.- Resuelva por el método penal (ó doble fase) el siguiente problema:

Min Z = 5 x1 - 6 x2 - 7 x3 a) Determine el modelo dual en

s.a.: 2 x1  10 x2 - 6 x3 �30 forma directa y a través de la
5 forma canónica, haga coincidir
x1 - 3 x2  5 x3 �10 ambos modelos duales.
2
2 x1  2 x2 - 2 x3 = 5
x1 �0; x2 �0; x3 �0

4.- Aplicando cualquier método (menos el gráfico), determine la solución de:

Min P = 5 p1  6 p2
s.a.: 2 p1  3 p2 �18
2 p1  p2 �12
3 p1  3 p2 � 24
p1 �0; p2 �0

5.- Determine la solución del siguiente problema.

Max Z = 4 x1  4 x2  3x3
s.a.: 4 x1  2 x2 �5
x1  2 x3 = 2
x2 �3
x1 �0; x2 �0; x3 �0

6.- Resuelva por el método penal ( ó doble fase) el siguiente problema:

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 17

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Max Z = 2 x1  3 x2 - 5 x3
s.a.: 2 x1  2 x2  2 x3 = 14
- 2 x1  5 x2  x3 �10
x1 �0; x2 �0; x3 �0

7.- Usando el método analítico, determine la solución óptima del siguiente Modelo de P.L.

Max Z = - 2 x1  3x2
s.a.: - x1 - x2 �- 2
x1 - x2 � 1
x1 �1
x1 �0; x2 �0
8.- Resuelva el siguiente problema de P.L. y conteste correctamente:

Min Z = 10 x1  3x2  4 x3
s.a.: 3 x1  x2 �8
2 x1  x3 �6
x1 �0; x2 �0; x3 �0

( ) El método adecuado para resolver el problema es:

a) El penal
b) Simples
c) El gráfico
d) Doble fase
e) El dual-simplex

( ) El número de variables en total que se necesitan para resolver el

Problema (incluyendo las originales) son:

a) 5 b) 3 c) 6 d) 7 e) Ninguna de las Anteriores

( ) La tabla inicial muestra una anomalía que es:

a) No se encuentran las variables superfluas en la base
b) Las columnas de las variables artificiales no son elementales
c) Contiene la base puras variables artificiales
d) La tabla no contiene variables de holgura
e) El valor de las variables originales son cero

( ) El valor de Z óptimo es:

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 18

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

a) 2/3
b) 88/3
c) 440/3
d) 60
e) 120

( ) Las variables básicas óptimas son:

a) x1 , w2
b) x1 , x 2
c) x1 , x 2 , x3
d) x1 , x3
e) x 2 , x3

( ) El valor de las variables básicas óptimas es:

a) 8/3, 2/3
b) 8, 6
c) 8/3, 0, 2/3
d) 40, -2/3
e) 30, 25, 0

9.- A partir del programa lineal

a) Plantear la forma estándar y la tabla inicial
Min Z = 4 x1  8 x2 para cada uno de los métodos: penal, doble
s.a.: 4 x1  4 x2 �16 fase y dual simplex.

x1 �2 b) Indique para cada una, la variable entrante y

2 x1  4 x2 �8 la variable saliente. No los resuelva.
x1 �0; x2 �0
c) Escriba la forma dual del programa lineal
original.

d) Identifique el caso especial

11.- Encuentre la solución óptima del siguiente modelo de P.L. utilizando la técnica de las
variables artificiales.

Min Z = - 3 x1  5 x2
s.a.: x2 �6
x1 �4
3x1  2 x2 �18
x1 �0; x2 �0
12.- Resuelva el siguiente problema por las técnicas de las variables artificiales

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 19

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Min Z = - 4 x1  5 x2  5 x3
s.a.: - x2  x3 �- 2 x2
- x1  x2  x3 �1
- x3 �-1
x1 �0; x2 �0; x3 �0

( ) La solución óptima es una solución:

a) Degenerada
b) Infactible
c) Inexistente
d) No acotada
e) Óptimas múltiples

( ) El número de variables artificiales necesarias para resolver el problema:

a) Cero
b) Una
c) Dos
d) Tres
e) Cuatro.

( ) El número total de variables (de todo tipo, excluyendo la Z), que tiene la tabla simplex es:
a) Tres
b) Cinco
c) Siete
d) Nueve
e) Ninguna de las anteriores.

( ) La característica fundamental que tiene la tabla óptima es:

a) Variables básicas iguales a cero
b) Variables básicas artificiales
c) Variables básicas negativas
d) No tiene variables básicas
e) Ninguna de las anteriores.

( ) Al utilizar la técnica de variables artificiales, el método más adecuado es:

a) Gráfico
b) Simples
c) Penal
d) Dual- Simplex
e) Algoritmo de transporte.

13.- En un problema de programación lineal. Resolviendo por el método de dos fases se llegó a
la siguiente tabla.
UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 20
GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

Z X1 X2 S1 R 1 R2 S3 Z0
v.b. 1 0 -1 -1 0
X1 0 1/5 3/5 - 1/5 3/5
X2 0 - 3/5 - 4/5 3/5 6/5
S3 0 1 1 -1 0

Si la F.O. fue Min Z = 4x1 + x2 encuentre la sol. ,óptima si ésta existe.

14.- Utilizando variables artificiales resuelva el siguiente problema de P.L. y conteste cada una
de las preguntas.

Max Z = x1  2 x2
s.a.: - x1  x2 �8
x1  x2 �10
x1 �0; x2 �0
( ) En la tabla inicial, el número de variables (excluyendo a Z) son:
a) dos
b) tres
c) cuatro
d) cinco
e) seis

( ) Las variables básicas iniciales, respectivamente son:

a) Superflua (Holgura Negativa) y Artificial
b) Artificial
c) Superflua y Holgura
d) Artificial y Holgura ( Holgura Positiva)
e) Ninguna de las anteriores

( ) La primera variable entrante a la base, en la tabla inicial es:

a) X 1
b) X 2
c) Superflua
d) Holgura
e) Artificial

( ) Las variables básicas optimas respectivamente son:

a) Artificial y X 1
b) X 1 y X 2
c) X 2 y Holgura
d) X 1 y Superflua
e) X 2 y Superflua

( ) El valor de las variables básicas optimas son respectivamente:

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 21
GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

a) (9, 1) T
b) (10, 2) T
c) ( 8,10 ) T
d) ( 2, 9 ) T
e) Ninguna de las anteriores

15.- Solucione el siguiente modelo de programación lineal, por la técnica de las variables
artificiales.

Max Z = x1  5 x2  3x3
s.a.: x1  2 x2  x3 = 3
2 x1 - x2 = 4
x1 �0; x2 �0; x3 �0

CASOS ESPECIALES
En la Programación Lineal se identifican algunos problemas como casos especiales del
método simplex, por las características de sus soluciones, dichos problemas pueden ser
identificados a partir de las tablas del Método Simplex.

Los casos especiales a considerar son:

a) Degeneración.
b) Solución óptima no acotada.
c) Solución óptima múltiple.
d) Solución óptima inexistente.

A) DEGENERACIÓN

Se presenta cuando al menos una de las variables básicas es igual a cero. Esto es fácil
de identificar en la tabla del método simplex. No necesariamente la degeneración temporal
implica una degeneración de la solución óptima.

EJEMPLO:

1.- CASO DE DEGENERACIÓN ÓPTIMA

Max Z = 3x1  9 x2 Vb Z X1 X2 H1 H2 Zo
s.a.: x1  4 x2 �8 1 -3 -9 0 0 0
H1 0 1 4 1 0 8
x1  2 x2 � 4
H2 0 1 2 0 1 4
x1 �0; x2 �0 1 -3/4 0 9/4 0 18
UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 22
GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

X2 0 1/4 1 1/4 0 2
H2 0 1/2 0 -1/2 1 0* X2
1 0 0 3/2 3/2 18
X2 0 0 1 1/2 -1/2 2
X1 0 1 0 -1 2 0

 Degenerada.

GRAFICA DE LA DEGENERACIÓN
X1
NOTA.- No todo problema con degeneración temporal es un problema de degeneración
óptima. Mediante este ejemplo se muestra dicha situación:
2.- CASO DE DEGENERACIÓN TEMPORAL
EJEMPLO:

Max Z = 2 x1  x2
s.a.: 4 x1  3 x2 �12 Formando la tabla inicial, e iterando:
4 x1  x2 �8
Vb Z X1 X2 H1 H2 H3 Zo
4 x1 - x2 �8 1 -2 -1 0 0 0 0
x1 �0; x2 �0 H1 0 4 3 1 0 0 12
Estandarizando: H2 0 4 1 0 1 0 8
H3 0 4 -1 0 0 1 8
Max Z = 2 x1  x2 1 0 -1/2 0 1/2 0 4
H1 0 0 2 1 -1 0 4
s.a.: 4 x1  3 x2  h1 = 12
X1 0 1 1/4 0 1/2 0 2
4 x1  x2  h2 = 8 H3 0 0 -2 0 -1 1 0*
4 x1 - x2  h3 = 8 1 0 0 1/4 1/4 0 5
x1 �0; x2 �0; hi �0 X2 0 0 1 1/2 -1/2 0 2
X1 0 1 0 -1/5 3/8 0 3/2
H3 0 0 0 1 -2 1 4

Solución degenerada * temporal. Pero solución óptima no-degenerada.

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 23

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

B) SOLUCIÓN OPTIMA NO ACOTADA

Este caso está asociado siempre a una región como área de factibilidad abierta, lo
contrario no es válido. Se identifica en el método simplex cuando los elementos de la columna
de la variable entrante, todas son no positivos. Identificando el caso no es necesario seguir
iterando, puesto que su solución se va al infinito.

EJEMPLO:

T A B L A S
Max Z = x1  2 x2 Vb Z X1 X2 H1 H2 Zo
s.a.: x1 - x2 �10 1 -1 -2 0 0 0
2 x1 - x2 �40 H1 0 1 -1 1 0 10
H2 0 2 -1 0 1 40
x1 �0; x2 �0
1 0 -3 1 0 10
X1 0 1 -1 1 0 10
H2 0 0 1 -2 1 20
1 0 0 -5 3 70
X1 0 1 0 -1 1 30
X2 0 0 1 -2 1 20

30

20

10

0
10

18

20

22
12

14

16

24

26

28

30
0

-10

-20

-30

-40

-50

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 24

GALDEANO
 UPIICSA – IPN – ACADEMIA DE I.O. INVESTIGACIÓN DE
OPERACIONES 1

C) SOLUCIÓN OPTIMA MÚLTIPLE

Este caso se puede identificar en las tablas del método simplex, cuando al hacer (0) al
coeficiente de la variable entrante de la función objetivo se hace (0) en forma simultánea otro
coeficiente de una variable no básica de la misma función objetivo.

(Cuando el coeficiente de una de las restricciones sea proporcional a los coeficientes de

la función objetivo es un indicio para saber que es una solución múltiple).

EJEMPLO:

Max Z = 4 x1  14 x 2
s.a : 2 x1  7 x 2  21
7 x1  2 x 2  21
x1  0; x 2  0

Vb Z X1 X2 H1 H2 Zo
1 -4 -14 0 0 0
H1 0 2 7 1 0 21
H2 0 7 2 0 1 21
1 0 0 2 0 42
X2 0 2/7 1 1/7 0 3
H2 0 45/7 0 -2/7 1 15
1 0 0 2 0 42
X2 0 0 1 9/45 -2/45 7/3
X1 0 1 0 -2/45 9/45 7/3

UNIDAD 3 –PROGRAMACIÓN LINEAL Autor: ING. HUMBERTO OVIEDO 25

GALDEANO
GRAFICA

(0,21)
B
A

(0,3)

SOLUCIÓN OPTIMA
(3,0)

(21/2,0)
D) SOLUCIÓN OPTIMA INEXISTENTE
Cuando al menos una de las variables artificiales es diferente de cero.
(Variables artificiales  0).

EJEMPLO:

X1 + X 2  K

X1 + X 2  L EN DONDE K  L

EJEMPLO: Dado el siguiente modelo, compruebe que su solución es óptima inexistente.

Max Z = 4 x1  x2
s.a.: x1  x2 �6
5 x1  3x2 �15
x1 �0; x2 �0

Vb Z X1 X2 S H W Zo
1 -4 -1 0 0 M 0
W 0 1 1 -1 0 1 6
H 0 5 3 0 1 0 15
1 -M-4 -M-1 M 0 0 -6M
W 0 1 1 -1 0 1 6
H 0 5 3 0 1 0 15
1 2/3M - 7/5 0 M M/3+1/3 0 -M+5
W 0 - 2/3 0 - 1 -1/3 1 3
X2 0 5/3 1 0 1/3 0 3

En la base de la tabla óptima contiene la variable artificial por lo que el problema no tiene solución,
esto es, se considera que le problema tienen una solución óptima inexistente, lo que se reconoce
como un caso especial del método simplex.
EJERCICIOS DE CASOS ESPECIALES

1. Resuelva el siguiente modelo de P.L. e identifique algún caso especial, justificando con lo
observado en la tabla simplex.

Max Z = 8 x1  4 x2
s.a.: x1  2 x2 �8
4 x1  2 x2 �10
x1 �0; x2 �0

2. Resuelva el siguiente problema de P.L. por el método simplex e identifique algún caso especial
en la tabla simplex.

Max Z = 3x1  2 x2  3x3

s.a.: 2 x1  x2  x3 � 20
3 x1  4 x2  2 x3 �8
x1 �0; x2 �0; x3 �0
3. Considere el siguiente problema:

Min y0 = y1 - 5 y2  6 y3
s.a.: 2 y1  4 y3 �50
y1  2 y2 �30
y3 �10
x1 , x2 , x3 libres

a) Muestre que a la solución A, este problema es no acotada mostrando que el dual es

infactible y el primal factible.
b) Suponga que el problema primal no se verifica en cuanto a factibilidad, ¿sería posible llegar
a esta conclusión, ¿por qué?.

4. Usando el método simplex encuentre dos soluciones óptimas del siguiente modelo de P.L.

Max Z = x1  x2  x3  x4
s.a.: x1  x2 �2
x3 - x4 �5
x1 �0; x2 �0; x3 �0; x4 �0
5. Considere los siguientes modelos de P.L.

1) Max Z = 4 x1  x2  6 x3 2) Max Z = x1  3 x2
s.a.: 3x1 - 4 x3 �25 s.a.: 4 x1 - 2 x2 �12
2 x2 - x3 �60 2 x1  6 x2 � 20
x1  x2 �80 x1  x2 �15
x1 �0; x2 �0; x3 �0 x1 �0; x2 �0

( ) El modelo (1) se puede identificar como el caso especial:

a) Degeneración parcial
b) Soluciones óptimas múltiples
c) Solución óptima No- Acotada
d) Sol.,óptima inexistente
e) Solución óptima degenerada.

( ) El modelo (2) se puede identificar como el caso especial:

a) Solución óptima No- Acotada
b) Degeneración parcial.
c) Solución óptima Degenerada
d) Solución óptima inexistente.
e) Soluciones óptimas múltiples.

( ) La solución óptima para el problema (1) es:

a) Z = Infinito
b) Z = 10
c) Z = 100/3
d) Z = 250

( ) La solución óptima para el problema (2) es:

a) Z* = 100/3
b) Z* = 10/3
c) Z* = Infinito
d) Z = 20
e) Z* = 10.

( ) La variable que sale de la base en la primera tabla del prob. (1)

a) H1
b) Ninguna
c) X2
d) H3
e) H2
 ( ) Es también una base óptima x1 = 4; x2 = 2; H3 = 27/3, del problema
a) Uno
b) Tanto del uno como del dos
c) Dos
d) De ninguno.

( ) El valor de las variables básicas que optimizan el prob. (2) son:

a) 56/3, 10/3, 35/3
b) 12, 20, 15
c) 25, 31, 40
d) 4, 0, 100/3.

( ) El valor de las variables básicas que optimizan el prob. (1) son:

a) 0, 25, 40
b) 25, 60, 80
c) 2/3, 16/3, 13/3
d) 1, 5, 0
e) Ninguno de los anteriores.

7.- Considere los dos siguientes modelos de P.L. y conteste las preguntas:

1) Max Z = 10 x1  8 x2
s.a : 7 x1  4 x2 �35
3 x1  2 x2 �3
x1 �0; x2 �0

2) Max Z = 5 x1  2 x2
s.a : 6 x1  10 x2 �30
x1  0.4 x2 � 2
x1 �0; x2 �0
( ) El modelo (1) es un caso espacial del tipo:
a) Degenerado
b) Infactible
c) No- acotado
d) Inexistente
e) Óptimas múltiples

( ) El modelo (2) es un caso espacial del tipo:

a) Degenerado
b) Infactible
c) No- acotado
d) Inexistente
e) Óptimas múltiples.

( ) El valor óptimo de la función objetivo en el modelo (1) es:

a) 120
 b) 10
c) Infinito (no-acotada)
d) 96
e) Ninguna de las anteriores.

( ) El valor óptimo de la función objetivo en el modelo (2) es:

a) 10
b) Infinito ( no acotada)
c) 100
d) 32
e) Ninguna de las anteriores.

( ) La base óptima del modelo (2) es:

x3 x1 x3 x2
a) b) ; c) ; d) ; e) Ninguna de las anteriores.

x4 x4 x2 x3
8. Obtenga las soluciones óptimas de los dos modelos siguientes y diga cada caso que tipo de
solución óptima se obtiene.

Max Z = 3x1  x2 Max Z = - 2 x1  7 x2

s.a : 9 x1  3x2 �18 s.a : x1 - 3x2 �21
2 x1 �15 4 x1 �16
x1 �0; x2 �0 x1 �0; x2 �0
 TEORIA DE DUALIDAD
Todo modelo de programación lineal (llamado modelo primal) tiene asociado otro modelo
llamado “Modelo Dual” cuya característica fundamental es tener la misma solución óptima que la
del modelo primal (si la solución existe y es finita).

La estructura matricial del modelo dual es:

DU A L PRI M AL

Min G = bt y Max Z = cx
s. a : At y �c t s. a : Ax �b
y �0 x �0

CARACTERÍSTICAS DEL MODELO DUAL.

1. G óptima = Z óptima (G* = Z*)

2. El número de restricciones duales es igual al número de variables primales.
3. El número de variables duales es igual al número de restricciones primales.
4. El Dual de Maximizar es Minimizar.
5. El Dual de Minimizar es Maximizar.
6. Los costos duales son los recursos primales.
7. Los recursos duales son lo costos primales.
8. Los coeficientes tecnológicos duales son los coeficientes transpuestos primales.
9. El Dual del Dual es el primal mismo. Si denotamos con P el modelo primal y con D el modelo
dual, al aplicar esta regla equivaldría a manejar al dual como operador, esto es:

D ( D (P) ) = P

10. Por el teorema fundamental de dualidad , si el primal tiene una solución óptima no-acotada,
entonces, el modelo dual no tiene solución y si el primal no tiene solución, entonces, el dual
tiene una solución óptima no-acotada

Ejemplo: Dado el siguiente modelo, determine su modelo dual a partir de la forma canónica.

Min Z = 2 x1 - x2
s.a : x1  2 x2 �10
- x1 - x2 �-7
4 x1  x2 = 16
x1 libre; x2 �0
Solución:

a) Obtención de la forma canónica

- Max (- Z ) = - 2 x1  x2
s.a : - x1 - 2 x2 �- 10
- x1 - x2 �- 7
- 4 x1 - x2 �-16
4 x1  x2 �16
x1 libre; x2 �0

Se propone el cambio de variables siguiente: sea x 1 = t1 – t2 ; x2 = - t3 y sustituyendo.

- Max (- Z ) = - 2t1  2t2 - t3

s.a : - t1  t2  2t3 �- 10
- t1  t2  t3 � - 7
- 4t1  4t2  t3 �-16
4t1 - 4t2 - t3 � 16
t1 �0; t 2 �0; t3 �0

Matricialmente:
�t1 �
��
- Max Z = (-2, 2, - 1) �t2 �
�t3 �
� �
�-1 1 2 � �-10 �
� �� t1 � � �
-1 1 1 � � � �-7 �
s. a : � � t2 ��
�-4 4 1 � � �-16 �
�
� �
�� t3 �
� � �
� �
�4 - 4 1� �16 �
t1 � ��
� 0
� � ��
t2 ����
� 0
�
t3 � ��0
� � ��

De donde:
�-10�
�- 7 � -2 �
�
C = ( - 2, 2, - 1) ; b = � � ; C T = �2 �
� ; bT = ( -10, - 7, - 16, 16 )
�
�-16�
� � -1 �
�
� �
�16 �
 -1
� 1 2�
� -1 - 1 - 4 4 �
�
-1 1 1� �
A= � �
; A = �1
T
1 4 - 4��
-4
� 4 1�
� � �
�2 1 1 - 1��
�4 - 4 - 1�

Entonces tenemos que el Modelo Dual mediante la forma Canónica es:

� y1 �
� y2 �
- Min (-G ) = ( -10, - 7, - 16, 16 ) � �
� y3 �
��
� y4 �
�y1 �
�-1 - 1 - 4 4 �� � � -2 �
�1 y
1 4 -4� ��� �2
s.a.: � ��y ���2 �
�
�2 1 1 - 1� 3
�� � � -1 �
� �
y
�4 �
�y1 � �� 0
�y � ��
�2 ���� 0
�y3 � �� 0
� � ��
�y4 � �� 0

El modelo dual en forma extendida es:

- Min (-G ) = - 10 y1 - 7 y2 - 16 y3  16 y4
s. a : - y1 - y2 - 4 y3  4 y4 �-2
y1  y2  4 y3 - 4 y4 � 2
2 y1  y2  y3 - y4 �-1
y1 �0; y2 �0; y3 �0; y4 �0

REGLAS DE DUALIDAD
PRIMAL DUAL
(DUAL) ( PRIMAL)
1.- Max Z Min G
2.- Si Xj  0 La “j” es una restricción de tipo “  “
3.- Si Xj libre La “j” es una restricción de tipo “ = “
4.- Si Xj  0 La “j” es una restricción de tipo “  “
5.- Si la i-ésima restricción La i-ésima variable es “  0 ”
es de tipo 
6.- Si la i-ésima restricción La i-ésima es libre
es de tipo =
7.- Si la i-ésima restricción La i-ésima variable es “  “
-+ es de tipo 
Por otro lado si la solución óptima es la misma, entonces, se cumple:

Z = CX Z* = G*
G = bY CX = bY

NOTA:
Debe coincidir el modelo calculado mediante estas reglas (modelo dual directo), con el que se
calculó mediante la forma canónica.

EJEMPLO:
Determinar el modelo Dual del siguiente modelo mediante las reglas de dualidad
Min Z = 2 x1 - x2
s.a : x1  2 x2 �10
- x1 - x2 �-7
4 x1  x2 = 16
x1 libre; x2 �0
a) La forma canónica.
b) Las reglas de dualidad (dual directo).

b) Obtención del modelo dual directo:

EJERCICIO:

Max Z = 10 f1 - 7 f 2  16 f 3
s.a.: f1 - f 2  4 f 3 = 2
2 f1 - f 2  f3  - 1
f1  0; f 2  0; f 3 libre

Aplicando las reglas de equivalencia haga coincidir los incisos a y b.

PROBLEMAS PROPUESTOS PARA EL MODELO DUAL

1. Transforma el modelo en forma canónica.

Sea : Min Z = 2 x1 - 3 x2  5 x3 a) Escriba el modelo en forma canónica (usando

s.a.: x1 - x2 - x3  - 5 las reglas de equivalencia).
- 6 x1 - 7 x2 - 9 x3 = 15
b) Determine el modelo DUAL asociado, a partir
19 x1 - 7 x2 - 5 x3  15
de la forma canónica de (a).
x1  0; x2  0; x3 libre
c) Determine el DUAL pero en forma directa
(usando las reglas de dualidad), y
compruebe con las reglas de equivalencia
que es igual al modelo obtenido en (b).
2. Encuentre el modelo dual asociado del siguiente modelo primal.

a) Mediante la forma canónica

b) En forma directa.

Min G = 3w1  2w2 - w3

s.a.: w1  2w2 4
5w2  8w3 = 9
w1  w2  w3  5
w1  0; w2 libre; w3  0

3. Obtenga el modelo de P.L. dual a partir del siguiente primal e indique las unidades,
dimensiónales que le correspondan al dual, así como el significado de las variables duales.

PROBLEMA PRIMAL.- Objetivo minimizar el desperdicio en corte de rollos de papel.

Sea : X j = # de cortes tipo j = 1, 2, 3, 4, 5

pu lg
Min Z = 18 x1  3x2  22 x3  18 x4  7 x5 corte = pu lg
corte
rollos
s.a.: 3 x1  2 x2  x3  800 corte = rollos
corte
x2  2 x4  x5  500
x3  x5  100
x1  0; x2  0; x3  0; x4  0; x5  0

4. Dado el siguiente modelo determine el modelo dual, mediante:

a) La forma canónica
b) La forma directa (reglas de dualidad).
c) Haga coincidir los modelos de (a) y (b)

Min Z = -8 x1  x2
s.a.: x1 - x2  2 x3  0
- 3 x2  x3 = 12
x1  0; x2  0; x3 libre

5. Dado el siguiente modelo de P.L., Determine el modelo dual asociado mediante:

a) La forma canónica
b) La forma directa
 c) Haga coincidir los modelos (a) y (b)

Min Z = - x1  4 x2
s.a.: x1 - x2  3x3 = -12
- x2 - x3  0
x1  0; x2  0; x3 libre

6. Escriba en su forma dual el siguiente problema:

Min Z = 3x1 - 4 x2  x3 - 2 x4
s. a.: 2 x1  x2  2 x3  x4 = 10
x3  2 x4 �10
x1 - x2  x4 �- 5
2 x1  3 x2  x3  x4 �20
x1 �0; x2 �0; x3 �0; x4 �0

7. Considere el siguiente modelo de programación lineal como un modelo primal y determine:

a) Su forma canónica
b) Su modelo dual asociado

Min Z = 2 x1 - 3 x2  x3
s.a.: x1 - x2  x3 �1
x1  3x3 = 5
x1  2 x2 �6
x1 libre; x2 �0; x3 libre

8. Dado el siguiente modelo determine:

a) El modelo dual en forma directa

b) El modelo dual mediante la forma canónica
c) Haga coincidir los modelos obtenidos en a y en b

Min Z = 3x1 - x3
s.a.: - 4 x1  x2 - 2 x3 �-6
x1  2 x2  x3 = 0
x1 �0; x2 �0; x3 libre

9. Determine el modelo dual-asociado al siguiente problema primal en forma directa y a través de

la forma canónica.
 Min Z = 2 x1 - 3 x2  4 x3
s.a.: x1  x2  x3 �1
x1 - 2 x2 = 7
x1 �0; x2 �0; x3 libre

10. Dado el siguiente programa lineal determine:

a) Cuál es su programa dual asociado

b) Determine su forma canónica
c) Obtenga la solución óptima, considerando y  0 (use el método dual-simplex)

Min Z = 5 x  2 y
s.a.: x  2 y � 5
x - y �12
x  3y � 4
x �0; y libre

11. Sea:

Min Z = 2 x1 - 3x2  5 x3 a) Escriba el modelo en forma canónica.

(usando las reglas de equivalencia).
s.a.: x1 - x2 - x3 �- 5
- 6 x1 - 7 x2 - 9 x3 = 15
19 x1 - 7 x2 - 5 x3 �15 b) Determine el DUAL.
x1 �0; x2 �0; x3 libre