PROGRAMACIÓN LINEAL

INTRODUCCIÓN

Los problemas que plantean alcanzar un valor máximo o mínimo se

llaman problemas de optimización. Los problemas de optimización, basados en
el cálculo de expresiones algebraicas se resuelven por métodos clásicos de
optimización; sin embargo existen métodos no clásicos de optimización,
conocidos como programación matemática, la que incluye la Programación
lineal y la Programación no lineal.
La Programación Matemática aborda problemas de optimización en
los que figuran restricciones de desigualdad del tipo f x1, x2 ,...,xn b . o del

tipo f x1, x2 ,...,xn b .

Dentro de la programación matemática se estudia primero la
programación lineal, en la cual figuran la función objetivo y las restricciones
de desigualdad, ambas de carácter lineal.
La programación lineal es una técnica matemática de optimización;
optimizar es maximizar o minimizar un objetivo. Esta técnica matemática es un
subconjunto dentro del conjunto de procedimientos matemáticos de optimización
de la programación matemática.
Maximizar o Minimizar: para ello se deben tomar decisiones, que
deben ser óptimas, significa esto que en un problema de programación lineal
van a existir variables de decisión : x j y lo que vamos a optimizar es la

función objetivo, satisfaciendo un conjunto de condiciones restrictivas o

restricciones.
¿Qué es la función objetivo ?. Es la expresión matemática de la meta a
alcanzar formulada en función de las variables de decisión x j .

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
2
Y el conjunto de restricciones o desigualdades lineales ¿Qué nos indica?. Este
conjunto da a conocer las condiciones que deben satisfacerse cuando se
determinan los valores de las variables x j .

EJEMPLO 1:

(Utilidad máxima). Una compañía fabrica 2 productos, X e Y. Cada uno

de estos productos requiere cierto tiempo en la línea de ensamblado y otro
tiempo más en el dpto. de acabado. Cada artículo X necesita 5 hs. de
ensamblado y 2 hs. de acabado, mientras que cada artículo del tipo Y requiere 3
hs. en ensamblado y 4 hs. de acabado. En cualquier semana, la empresa
dispone de l05 hs. en la línea de ensamblado y 70 hs. en el dpto. de acabado.
La empresa puede vender todos los artículos que produce y obtener una utilidad
de $20 por cada artículo X y $16 por cada artículo Y. Calcule el número de
artículo de cada tipo que debe fabricarse en la semana con objeto de maximizar
la utilidad total.

Resumimos la información en la siguiente tabla:

Productos Ensamblado Acabado Utilidad

X 5 2 20
Y 3 4 16
Disponibilidad 105 70

Formulación del problema:

maximizar z 20 x 16 y función objetivo

5x 3y 105
sujeto a restricciones estructurales
2 x 4y 70

x; y 0 restricciones de no negatividad

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
3
Al querer maximizar las utilidades provenientes de la producción y venta de
productos, las restricciones pueden reflejar los recursos de materiales, de
materias primas, de maquinarias disponibles, de mano de obra, de demanda,
etc.. Las restricciones de un problema de P.L. pueden ser ecuaciones o
desigualdades del tipo: ; .

La función objetivo en el ejemplo anterior es maximizar las utilidades.

Nuevamente podemos observar la linealidad de la función objetivo y de las
restricciones.
Las restricciones que condicionan la función objetivo son de dos tipos;
restricciones estructurales y restricciones de no negatividad , una para
cada variable de decisión x j .

Las restricciones estructurales se refieren a la limitación de los recursos

o factores económicos, las de no negatividad garantizan que ninguna x j sea

negativa.

ALGUNAS APLICACIONES DE LA P.L.

La esencia, la finalidad y la utilidad de la P.L. pueden apreciarse en
ejemplos concretos, algunos de ellos apuntan a la maximización, otros a la
minimización. Los problemas referidos a la mezcla de productos, o a la mezcla
de alimentos en dietas balanceadas, o a modelos de transporte o a modelos de
elaboración de presupuestos constituyen un grupo importante de aplicaciones
para la técnica matemática que se conoce como P.L.
En los problemas de mezcla de productos se determina la cantidad de unidades
que debe producir y vender una empresa para optimizar las utilidades que
percibe y minimizar los costos de producción y venta. Las cantidades son las
variables de decisión x j e indican las unidades fabricadas y vendidas de los

distintos productos, entonces puede calcularse el aporte a la utilidad total

sumando las contribuciones de los productos, contribuciones que se obtienen al
multiplicar el margen de utilidad por unidad por el número de unidades
producidas y vendidas.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
4
 La función objetivo, que en adelante indicaremos con "z" indica la
aportación a los costos y utilidades totales, lo que se maximiza o minimiza es el
valor de z.

I) Decisiones de Producción

Ejemplo 2:

Una empresa fabrica 2 productos, los cuales deben procesarse en los

departamentos 1 y 2. En la tabla se resumen las necesidades de horas de
trabajo por unidad de cada producto en uno y otro dpto. También se incluyen las
capacidades de hs. de trabajo semanales en ambos dptos. y los márgenes
respectivos de utilidad que se obtienen con los dos productos.

El problema consiste en determinar el número de unidades que hay que

fabricar de cada producto, con objeto de maximizar la aportación total a los
costos fijos y a las utilidades.

Producto A Producto B Cap. de T. semanal

Dpto. 1 3 hs/u 2 hs/u 120 hs
Dpto. 2 4 hs/u 6 hs/u 260 hs
Margen utilidad $ 5/u $ 6/u

Formulación del problema:

z 5 x1 16 x2 función objetivo

x1 ; x2 variables de decisión

3 x1 2 x2 120
sujeto a restricciones estructurales
4 x1 6 x2 260

x1 ; x2 0 restricciones de no negatividad

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
5
II) En problemas de modelos de dietas balanceadas, se busca la combinación
de elementos que deberán incluirse en una comida para: 1) minimizar su costo y
2) cumplir con necesidades nutricionales.
Ejemplos 3:
En un comedor universitario, una dietista planea la cena en base a tres
alimentos principales, los que suministrarán a los estudiantes, con por lo menos
una ración mínima diaria de 3 vitaminas en la cena. En la tabla se brinda el
contenido vitamínico por gr. de cada tipo de alimento, el costo por gr. de cada
alimento y la ración mínima que por día debe consumirse de las 3 vitaminas.
Cualquier combinación de los 3 comestibles puede elegirse, a condición de que
la porción total sea de 260 gr. por lo menos.

Alimento Vitamina Costo en $

1 2 3
1 50 20 10 0,10
2 30 10 50 0,15
3 20 30 20 0,12
R.D.M. 290 200 210

Formulación del problema:

z 0,10 x1 0,15 x2 0,12 x3 función objetivo

50 x1 30 x2 20 x3 290
20 x1 10 x2 30 x3 200
sujeto a restricciones estructurales
10 x1 50 x2 20 x3 210
x1 x2 x3 260

x1 ; x2 ; x3 0 restricciones de no negatividad
III) Los problemas más comunes en P.L. son los referidos a modelos de
transporte; así en las industrias petroleras son innumerables las aplicaciones
prácticas; la características de estos problemas son el transporte de productos
homogéneos de m fuentes u orígenes a n demandas o destinos, de manera
tal que cualquier origen puede abastecer a cualquier fuente.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
6
Para cada combinación de origen-destino se especifica algún costo por envío
de cada unidad, o se monetiza el esfuerzo del envío en función a la distancia o
al tiempo que se tarda en llegar. Estos problemas también se conocen con el
nombre de costos de distribución.

Un ejemplo tradicional es el cálculo del mantenimiento de las carreteras,

la preservación necesaria para ciudades que quedan aisladas en épocas de
tormentas, inundaciones, etc.

Ejemplo 4:

El Secretario de Obras Públicas debe determinar el costo mínimo de

suministrar sal y arena a 4 zonas de una ciudad cuando sobrevienen tormentas
de nieve; la sal y la arena provienen de 2 fuentes situadas fuera de la ciudad,
por lo tanto los suministros deben realizarse antes de la época de tormentas.

En la tabla se sintetiza el costo de los envíos a las distintas zonas

expresados en $ por toneladas; se indica también las demandas de cada zona y
las capacidades de las fuentes de orígenes.

z o n a s Oferta
1 2 3 4
Fuente 1 $ 20 $ 30 $ 15 $ 25 900
Fuente 2 $ 40 $ 35 $ 25 $ 30 750
Demanda 300 450 500 350

x ij toneladas enviadas de la fuente i a la zona j

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
7
Formulación del problema:

min imizar
z 20 x11 30 x12 15 x13 25 x14 40 x21 35 x22 25 x23 30 x24 función objetivo

x11 x12 x13 x14 900

x21 x22 x23 x24 750
x11 x21 300
sujeto a restricciones estructurales
x12 x22 450
x13 x23 500
x14 x24 350

x11 ; x12 ; x13 ; x14; x21; x22; x23; x24 0 restricciones de no negatividad

IV) En los modelos de elaboración de presupuesto de capital, figuran los

problemas de inversiones, que son aquellos en los que se consideran distintas
oportunidades de inversión y se calculan para cada una de ellas los costos de
esa inversión y las utilidades que puede brindar; de esas alternativas se
selecciona la que maximice las utilidades globales, siendo en esta oportunidad
de mucho peso las restricciones presupuestarias y otras que afectan los
recursos de los proyectos elegidos.

Ejemplo 5:

Un accionista planea invertir $ 30.000 en acciones de 2 empresas A y B.

Cada acción de A está valuada en $ 165 y cada acción de B en $ 90. Si el
accionista compra x1 acciones de A y x2 acciones de B ¿ Cuántas
acciones de cada compañía comprará ?.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
8
 Si por cada acción de A se paga un dividendo de $ 6 y por cada acción
de B se paga $ 5 ¿ Cuántas acciones debe comprar de cada una para obtener
un beneficio de por lo menos $ 1.400 ?.

Formulación del problema:

165 x1 90 x2 30.000
6 x1 5 x2 1.400
x1 ; x2 0

ENFOQUE GEOMETRICO - SOLUCION GRAFICA

Sobre un problema típico de P.L. analizaremos la utilidad de la solución

gráfica del mismo, para ello nuestro ejemplo será sencillo y sólo en 2 variables
de elección o variables de decisión.
Retomemos el ejemplo nº 1 de utilidad máxima.

Productos Ensamblado Acabado Utilidad

X 5 2 20
Y 3 4 16
Disponibilidad 105 70

Formulación del problema:

maxim izar z 20 x 16 y función objetivo

5x 3y 105 restricción de ensam blado

sujeto a
2 x 4y 70 restricción de acabado

x; y 0 restricciones de no negatividad

Aclaración: $ 20; $ 16, son ingresos netos, (netos de costos) o

beneficio bruto.
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
9
 Si bien las restricciones son del tipo y no podemos exceder la
capacidad de la empresa, si podemos dejar parte de esa capacidad ociosa.

Por las condiciones de no negatividad trabajamos en el cuadrante no

negativo, y dibujamos en él las llamadas fronteras restrictivas; las fronteras
restrictivas son las rectas que gráficamente representan las restricciones cuando
éstas están dadas como ecuaciones. En el ejemplo trazamos la frontera de
ensamblado y la de acabado. El conjunto de pares x; y que satisfacen las
desigualdades aparecen en la región sombreada o sobre las fronteras.
Un punto puede satisfacer a una restricción, pero no a la otra, ese punto
no es factible en nuestro P.L..
Todos los puntos ubicados en el área sombreada del gráfico satisfacen
simultáneamente a las 2 restricciones, ese conjunto de puntos recibe el nombre
de región o zona factible. Cada punto perteneciente a la zona factible se
llama solución factible. La región factible también incluye a los puntos de
la frontera que la acota.
Sobre el eje horizontal tenemos el conjunto de puntos
x: y / x 21; y 0 , sobre el eje vertical el conjunto es
x: y / x 0; y 17,5 , estos conjuntos de puntos forman parte de la
región factible.
La región factible es un conjunto cerrado que incluye a todos los puntos
de sus fronteras.

Area o zona de soluciones factibles: Es el conjunto solución del

sistema de restricciones. Este conjunto solución incluye todas las
combinaciones de las variables de decisión que satisfacen las restricciones
estructurales y de no negatividad. Esas combinaciones se consideran
candidatas de ser la solución óptima.
El punto (12 ; 14) no pertenece al área factible, ya que si bien satisface
la restricción de ensamblado no satisface la de acabado.
(12) 5 + (14) 3 = 102 y 102 105
(12) 2 + (14) 4 = 80 y 80 70 (excede la capacidad de la empresa para el
acabado).
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
10
La frontera del área factible está formada por las fronteras de ensamblado,
acabado y las de no negatividad.

Puntos extremos: Son los que aparecen en la intersección de 2 líneas

de frontera o en la intersección de una línea de frontera y un eje.

Si previamente establecemos el nivel de utilidades se identificarán las

combinaciones de los 2 productos que permitan alcanzar ese nivel.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
11
 Si z = 400 ==> 20 x + 16 y = 400 línea recta que corta al je x en (20 ;
0) y al eje y en (0 ; 25) y que atraviesa parte de la región factible, lo que
significa que es posible para la empresa alcanzar ese nivel de utilidad.
Si z = 600 ==> 20 x + 16 y = 600 línea recta que corta al eje x en (30 ;
0) y al eje y en (0 ; 37,5) y que no atraviesa la zona factible, lo que implica que
es imposible para la empresa lograr ese nivel de utilidad.

La utilidad máxima que puede alcanzarse debemos buscarla entre

$ 400 y $ 600.
La línea recta 20 x + 16 y = z recibe el nombre de línea de utilidad
constante o isobeneficio y así , para cada valor dado a z tendremos un
isobeneficio.

Debemos seleccionar la línea de utilidad más alta posible y que se

apoye en la región factible. Esa selección de isobeneficio nos conduce a la
búsqueda de un punto extremo llamado solución factible óptima o solución
óptima.

Una vez identificado el punto óptimo hallamos la solución óptima exacta

( x ; y ) resolviendo el sistema de ecuaciones que representan las 2 rectas que
se interceptan en él.

En la búsqueda de la solución óptima, vemos que a medida que z crece,

la línea de isobeneficio se aleja del punto (0 ; 0) y aumenta la ordenada al origen
20 5
ya que se trazan líneas paralelas de pendiente m
16 4
Cuando la línea de isobeneficio toque el extremo (15;10) que pertenece
al área factible habremos obtenido la máxima utilidad o beneficio bruto.
El valor z = (20) 15 + (16) 10 = 460 Luego, la utilidad máxima: $ 460

Frente a un problema de minimización procederemos de igual manera,

pero buscaremos el punto extremo que se convierta en solución óptima al
minimizar la función objetivo.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
12
 Si en particular hablamos de reducir costos, las líneas paralelas
representarán líneas de igual costo o isocoste y tendrá importancia aquella que
apoyándose en la región factible sea la curva de isocoste más baja posible.

Ejemplo 6:

Una compañía está diseñando una nueva planta, en la que se

producirán 2 productos químicos P1 y P2 . Esa planta debe producir al menos
100 unidades de P1 y 420 unidades de P2.

En esa planta deben incluirse cámaras de reacción básica para la

producción de esos productos. Existen 2 tipos de cámaras: tipo A y tipo B. La
cámara tipo A cuesta $ 600 y tiene una capacidad de producción de 10 unidades
de P1 por día y 20 unidades de P2 por día; la cámara tipo B es más barata,
tiene un costo de $ 300 y produce 4 unidades de P 1 por día y 30 de P2 por día.
Por los costos de operación es necesario tener por lo menos 4 cámaras de cada
tipo en la planta ¿ Cuántas cámaras de cada tipo se deben incluir a fin de
minimizar el costo de construcción y cumplir el plan de producción ?

Se sintetiza la información en la siguiente tabla:

P1 P2 Costo

Cámara A 10 20 600
Cámara B 4 30 300
Requerimientos 100 420

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
13
Formulación del problema:

33,33

25 Y
22

14
( 6,10)

0 4 10 11 16,66 21 X

Si z = 10.000 ==> 100 = 6 x + 3 y

Si z = 6.600 ==> 66 = 6 x + 3 y
Esta recta es tangente al área factible en el punto de contacto (6;10) que
es el óptimo buscado.
z = $ 6.600 ; ( x ; y ) = (6 ; 10) , significa 6 cámaras del tipo A y 10 del tipo B
Al considerar un problema de P.L. con dos variables x e y , la región
factible formada por todas las combinaciones que satisfacen a todas las
restricciones tendrá forma de un polígono en el plano " x y " y la función objetivo
será representada por una linea recta (isocuanta). Intuitivamente afirmamos que
el valor extremo de la función objetivo z , dentro de la región factible se obtiene
cuando la linea recta pasa por un vértice del polígono de factibilidad, ya que el
último punto de contacto ocurre en uno de esos vértices.
Esto hace nacer la idea de una técnica con la cual lo único que
debemos hacer es calcular el valor de z en cada uno de los vértices o puntos
extremos del área factible. El más grande de esos valores da el máximo de la

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
14
función objetivo y el más pequeño su mínimo. Esta técnica recibe el nombre de
método de punto en la esquina.
Este método, al igual que el método gráfico es aplicable cuando nuestro
problema tiene dos variables, a lo sumo tres, pero ninguno de estos dos
métodos es válido si estamos en presencia de más de tres variables.
El polígono que representa el área factible es un conjunto convexo (si u
y v son puntos que pertenecen al polígono, toda combinación convexa de u y v
está también en el conjunto) o (si dos puntos de ese conjunto se conectan
mediante una recta, todos los elementos de esa recta son miembros del
conjunto).

Método de punto en la esquina o método de puntos extremos.

I- Graficar el área factible.

II- Determinar las coordenadas de cada punto extremo.
III- Sustituir las coordenadas de los puntos extremos en la función
objetivo y determinar el valor de. z
IV- Seleccionar el valor más alto (bajo) de z , ésa es la solución óptima
en un problema de maximización (minimización).

Ejemplo 7:
minim izar z 3 x1 6 x2 función objetivo

4 x1 x2 20
sujeto a x1 x2 20
x1 x2 10

x1 0 ; x2 0

Puntos en las esquinas x1; x2

10 20
A ; z = 50
3 3
B 0 ; 20 z = 120
C ( 20 ; 0 ) z = 60
D ( 10 ; 0 ) z = 30
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
15
z = 30 x1 = 10 x2 = 0 Punto óptimo ( 10 ; 0 )

En los ejemplos dados, nuestras restricciones estructurales eran del tipo

o todas, pero no siempre es así. Ambos tipos de restricciones pueden
coexistir, ya lo hemos visto en los problemas anteriores al hablar de
restricciones de capacidad del tipo y las restricciones de no negatividad.

AUSENCIA DE SOLUCIÓN FACTIBLE

Al estar presentes los dos tipos de restricciones puede ocurrir que

exista incompatibilidad entre ellas y estaremos en presencia de casos sin
solución, ya que el polígono factible no existirá.

x2

O x1

Si en el problema se incluyen igualdades (ecuaciones) junto a

desigualdades, el conjunto de soluciones factibles se acota con la ecuación,
pero se aplica el mismo método de solución.

x2

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
16
 0 x1

SOLUCIONES OPTIMAS ALTERNATIVAS

Existen cuando se presenta más de una solución óptima en los

problemas de P.L.
Gráficamente la función objetivo es paralela a una restricción que
constituye una frontera del área factible. Esa restricción es en este caso una
restricción limitante, porque impide un mejoramiento de z .
Cuando utilizamos el método de punto extremo o punto en la esquina,
estamos en presencia de soluciones óptimas alternativas si hay empate del
valor óptimo de la función objetivo. Ese valor solución va a repetirse a lo largo
de todo el segmento de línea que une los dos puntos.

z máx .

z mín..

SOLUCIONES NO ACOTADAS

x2

A
O A x1

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
17
 Si en nuestro ejemplo tenemos dos restricciones del tipo y el espacio
solución se extiende hacia afuera indefinidamente, este espacio solución no
tiene limite y se llama espacio solución no acotada.
Si en nuestro problema lo que se busca es minimizar la función objetivo,
la dirección del mejoramiento de z es hacia el origen y entonces existe z en el
punto de esquina A. Pero si lo que buscamos es maximizar z , la función
objetivo es llevada en el espacio solución hacia afuera una distancia infinita y el
problema tiene solución no acotada.

FORMULACION GENERAL DE LOS PROBLEMAS LINEALES

Para formular un modelo de P.L. deben seguirse los siguientes pasos:

1- Leer cuidadosamente el problema.
2- Determinar las variables de decisión (elección), x j , para ello es

necesario establecer los efectos que tienen esas variables sobre el objetivo a
alcanzar. Luego de determinar las x j j, se las debe enumerar, identificando el

significado de cada una.

Ejemplo:
x1 : número de unidades del producto 1 producidas y vendidas en el
primer mes.
3- Definir el objetivo y escribir la función objetivo.
Ejemplo:
Maximizar la utilidad mensual obtenida de producir y vender los
productos 1 y 2 en un mes (o minimizar el costo de producción de esos
productos).
4- Establecer cuáles son las condiciones que deben satisfacerse al
asignarle valores a las x j , esto es dar las restricciones estructurales. Significa

escribirlas.
5- Escribir las restricciones de no negatividad.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
18
 En un problema de P.L. en el que existan n variables y m restricciones,
podemos optar por escribirlo de las siguiente forma:

Forma completa

Un caso de maximización:

maxim izar z c1x1 c2 x2 ... c j x j ... cn xn función objetivo

a11x1 a12 x2 .... a1 j x j .... a1n xn b1

a21x1 a22 x2 ... a2 j x j .... a2n xn b2
.......................................................................
sujeto a
ai1x1 ai 2 x2 ... aij x j .... ain xn bi
.......................................................................
am1x1 am 2 x2 ... amj x j .... amn xn bm

x1, x2 , .., x j ,....,xn 0 o xj 0 con j 1,2,..n

z será el maximando, en este caso z es una función beneficio.

x j indica las variables de decisión o variables de elección.

c j son los coeficientes constantes de la función objetivo.

bi son las constantes que figuran en el miembro derecho de las

restricciones.
aij son los coeficientes de las variables de elección.

i 1, 2, ..., m , j 1, 2,..., n , m n o m n

Al haber escrito desigualdades del tipo no queremos significar que no

puedan existir restricciones del tipo en el problema, no olvidemos que cabe
la opción de transformarlas en otras del tipo con solo multiplicarlas por (-1).

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
19
 Para un caso de minimización, escribimos:

maxim izar z c1x1 c2 x2 ... c j x j ... cn xn función objetivo

a11x1 a12 x2 .... a1 j x j .... a1n xn b1

a21x1 a22 x2 ... a2 j x j .... a2n xn b2
.......................................................................
sujeto a
ai1x1 ai 2 x2 ... aij x j .... ain xn bi
.......................................................................
am1x1 am 2 x2 ... amj x j .... amn xn bm

x1, x2 , .., x j ,....,xn 0 o xj 0 con j 1,2,..n

z es un minimando cuando la función objetivo nos habla de minimizar costos

r significa ahora requerimientos en lugar de restricciones.
Es necesario aclarar que según el contexto el maximando (minimando)
puede no responder a una función beneficio (función de costo), esto significa
que si bien el objetivo es maximizar (minimizar) no se trata de utilidades o de
costos.

NOTACION
Para un problema de maximización:

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
20
 n
maxim izar z cj xj
j 1

n
sujeto a aij x j bi i 1, 2,..., m
j 1

xj 0 j 1, 2,..., n

Para un problema de minimización:

n
minim izar z cj xj
j 1

n
sujeto a aij x j bi i 1, 2,..., m
j 1

xj 0 j 1, 2,..., n

NOTACIÓN MATRICIAL

Sean las matrices :

A aij , B bi mx1 , X xi mx1 y C cj , que pueden

mxn 1x n

escribirse:

a11 a12 ... a1 j ... a1n b1

a 21 a 22 ... a 2 j ... a 2n b2
. . . . . . .
A , A K mx n , B , B K mx 1
ai1 ai 2 ... aij . ... ain . bi
. . . . . . .
a m1 a m2 ... a mj ... a mn bm

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
21
 x1
x2
.
C c1 c2 ... c j ... cn , C K1x n X , X K nx1
xi
.
xn

luego, el modelo de programación lineal se escribe:

maxim izar z CX minim izar z CX

sujeto a AX B o sujeto a AX B

xj 0 xj 0

METODO DE RESOLUCION

Cuando en un programa lineal es n=2, la solución gráfica nos conduce

sin dificultad a la solución óptima. No nos interesa el número de restricciones, ya
que un mayor número de ellas , lo único que hace es incrementar el número de
puntos extremos. Cuando es n=3, el método gráfico es poco manejable., es
necesario tener habilidades en el manejo de gráficos tridimensionales. El
método gráfico es inaplicable cuando el número de variables es mayor que 3;
(n 3 ), para el caso de n variables el espacio es n-dimensional y cada punto
extremo sería la n-upla x1, x2 , ..., xn o un n-vector.
En el espacio de dos dimensiones, hemos visto que valiéndonos de la
función objetivo podríamos localizar un punto x1, x2 que pertenece al
espacio solución y que puede convertirse en solución óptima. Lo mismo
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
22
sucede para n-variables, donde cada punto extremo es la n-upla ordenada
x1, x2 , ..., xn , sólo debemos encontrar a través de un método distinto del

gráfico, cuál es la solución óptima x1, x2 , ..., xn . Esto es posible porque

prescindiendo del número de variables , la región factible de un programa lineal

es siempre un conjunto convexo cerrado.
Si en un conjunto convexo, tomamos dos puntos del mismo, u y v,
entonces cualquier combinación convexa de u y v pertenece al mismo
conjunto.

Llamemos H a ese conjunto.

u H
w H siendo w u 1 v con (0 1)
v H

En un espacio bidimensional z c1x1 c2 x2 es una recta.

En un espacio tridimensional, z c1x1 c2 x2 c3x3 es un plano.

En un espacio n-dimensional, z c1x1 c2 x2 ... c j x j ... cn xn es

un hiperplano.
La recta, el plano y el hiperplano son conjuntos convexos.
Tomemos el hiperplano H definido por:
z c1x1 c2 x2 ... c j x j ... cn xn

Si elegimos dos puntos pertenecientes a H,

u ( u1, u2 ,...,un ) y v (v1,u2 ,...un ) , respectivamente, entonces u y v satisfacen la

ecuación z C X y es válido escribir:

z c1u1 c2u2 ... c ju j ... cnun ; z Cu

z c1v1 c2 xv2 ... c j v j ... cnvn ; z Cv

Cw C u 1 v C u C1 v Cu 1 Cv z 1 z 1 z z

Entonces la combinación convexa w H; por lo tanto H es convexo.

En el plano, espacio de dos dimensiones, tendremos que z es una recta

que lo divide en dos semiplanos, en el espacio n-dimensional el hiperplano
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
23
determina dos semiespacios n-dimensionales., según que el hiperplano divisor
se considere o no una porción del semiespacio en cuestión tendremos un
semiespacio abierto o cerrado.
Si escribimos las desigualdades:
1) C X > s, indica todos los puntos situados a un lado del hiperplano.
Se trata de un semiespacio abierto.
2) C X s indica todos los puntos situados a un lado del hiperplano
como así también los que están sobre el mismo. Se trata de un
semiespacio cerrado.
Cada restricción estructural define un semiespacio cerrado, lo mismo
que cada restricción de no negatividad.
La región factible de un P.L. satisface m+n desigualdades lineales ( m
de las restricciones estructurales y n de las restricciones de no negatividad), por
lo tanto es un elemento de los m+n espacios cerrados; es decir todo punto de la
región factible está ubicado en la intersección de m+n conjuntos convexos
cerrados.

Conclusión: para cualquier valor de z , la función objetivo de un P.L. de

n variables define un hiperplano, el que es un conjunto cerrado, y por ser la
región factible la intersección de m+n semiespacios cerrados, también es un
conjunto convexo cerrado, llamado F.

Podemos distinguir entonces puntos interiores, puntos de frontera y

puntos extremos. Los puntos frontera son los situados sobre los lados del
polígono que representa el área factible y los no situados sobre los lados pero sí
en el polígono son puntos interiores.

b es punto de frontera E b; por pequeño que sea puntos

del entorno que no pertenecen la área factible.

i es punto interior E i; por pequeño que sea no puntos que

no pertenecen al área factible.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
24
PUNTO EXTREMO:

Es un punto de frontera no situado sobre el segmento que une

cualquier par de puntos del conjunto cerrado convexo. Este punto no puede
expresarse como combinación convexa de cualquier par de puntos del conjunto.

El conjunto de todos los puntos extremos es un subconjunto del

conjunto de los puntos de frontera.
El conjunto de los puntos de frontera es disjunto del conjunto de puntos
interiores
a, b, c, d, o puntos extremos
i punto interior
contorno del polígono = {puntos de frontera}.

a b
F
c
i

i
0 d

Al optimizar o al minimizar el hiperplano objetivo alcanza la posición más

elevada posible pero permanece en F.
En el maximando o minimando el hiperplano óptimo H , no puede
contener puntos interiores.

H  F = {puntos de frontera}.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
25
 En la solución óptima, el hiperplano objetivo que representa la curva de
isobeneficio o isocoste óptima, es un hiperplano soporte.

Hiperplano soporte H, es aquel que tiene uno o más puntos en común

con el conjunto convexo F, H debe estar situado de manera tal que F se
encuentra exclusivamente a un lado de H .

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
26
 Sobre cada una de estas rectas aparecen puntos de frontera de F y
cada recta soporte contiene al menos un punto extremo.
En los procedimientos de P.L., a diferencia de los problemas de
optimización clásica, cualquier solución obtenida nos da no sólo el óptimo local o
relativo, sino también el global o absoluto.

METODOS SIMPLEX O BUSQUEDA DE PUNTOS EXTREMOS

La solución óptima de un p.l. se encuentra en un punto extremo; cuando

F puede ser dibujada, la tarea es sencilla, el problema radica cuando existen n
variables. Este tipo de problemas se resuelve a través del METODO SIMPLEX.
Para explicar el método que desarrollaremos, retomamos el problema
dado como Ejemplo 1, y lo consideraremos como:

Ejemplo 8:

Productos Ensamblado Acabado Utilidad

X 5 2 20
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
27
 Y 3 4 16
Disponibilidad 105 70

Formulación del problema:

maxim izar z 20 x 16 y función objetivo

5x 3y 105 restricción de ensam blado

sujeto a
2 x 4y 70 restricción de acabado

x; y 0 restricciones de no negatividad

Representemos el área factible.

y

17,5
(15;10)

0 x

El punto 15 ; 10 aparece como intersección de dos fronteras

restrictivas. Este punto satisface a ambas [Link] puntos (0;17,5) y (21;0)
surgen como intersección de una frontera restrictiva y un eje.
Por último tenemos el punto (0 ; 0) que no satisface ninguna de las
restricciones estructurales. Este punto sólo aparece en los problemas de
maximización, en los de minimización se lo excluye.
Si un punto no verifica la igualdad para alguna de las restricciones, es
decir hay cumplimiento inexacto de esa restricción por parte de ese punto, es
porque existe una subutilización de la capacidad y entonces aparecerá una
holgura si es un problema de maximización.
Veamos otro ejemplo de producción.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
28
Ejemplo 9:

[Link] trabajo de elaboración Capacidad diaria

por [Link] prod. en horas
Departamentos I II
Cortado 1 8
0
2
Montaje 0 1 8
Embalaje 1 2 8
3 3

Beneficio/tn. $ 40 $ 30

Formulación del problema:

maxim izar z 40x1 30x2 función objetivo
1
x1 8
2
sujeto a x2 8
1 2
x1 x2 8
3 3

x1; x2 0

También puede expresarse:

maxim izar z 40x1 30x2 función objetivo

x1 16
sujeto a x2 8
x1 x2 24

x1; x2 0

x2
12
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
29
 (8;8)

(16;4)
0 x1

El punto (16;4) satisface las restricciones de cortado y embalado, pero

no la de montaje, ya que está debajo de la frontera correspondiente. Acá
aparece una holgura en la utilización de la capacidad de montaje.
El punto (8;8) sólo cumple las restricciones de montaje y embalado, no
la de cortado con respecto a la cual hay una holgura.
Los puntos (0;8) y (16;0) sólo cumplen una restricción, existe holgura
respecto a las demás.
En este ejemplo m = 3 (tres restricciones) y n = 2 (variables de
elección). Cada uno de los puntos extremos implica una holgura en al menos
una restricción.
En la solución óptima x1 ; x2 , no solamente damos los valores
óptimos sino los valores de las holguras óptimas.

Con Si demostraremos la holgura correspondiente a la i-ésima

restricción, podemos entonces escribir el programa lineal de la siguiente forma:

maxim izar z 40x1 30x2 0S1 0S2 0S3 función objetivo

x1 S1 16
sujeto a x2 S2 8
x1 2 x2 S3 24

x1; x2 ; S1; S2 ; S3 0

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
30
 x1
1 0 1 0 0 x2 16
matricialmente: 0 1 0 1 0 S1 8
1 2 0 0 1 S2 24
S3

Existen ahora 5 variables; 2 de elección y 3 de holgura

Número de variables: n+m=p
 Si > 0 indica que existe holgura en la i-ésima restricción,
 Si= 0 indica que la i-ésima restricción se cumple exactamente.
 Si nunca es negativa.
En la función objetivo, los coeficientes de Si son ceros, porque las
holguras no contribuyen al beneficio.
Las Si reciben el nombre de variables ficticias.
Estamos ya en condiciones de plantear la siguiente tabla.

Punto extremo Espacio solución

(x1 ; x2) (x1;x2;S1;S2;S3)

(0 ; 0) (0;0;16;8;24)
(16 ; 0) (16;0;0;8;8)
(16 ; 4) (16;4;0;4;0)
(8 ; 8) (8;8;8;0;0)
(0 ; 8) (0;8;16;0;8)
En esta tabla damos el valor cero a dos de las variables, siendo tres de
ellas distintas de cero, no figuran acá las soluciones no factibles.
En un sistema compatible de m ecuaciones y p variables, existe solución
determinada cuando m = p
En el ejemplo considerado es m=3, n=2, p=m+n=5 en consecuencia, de
las 5 variables, sólo tres pueden tener un valor distinto de cero.

1 0 1 0 0 16
En 0 x1 + 1 x2 + 0 S1 + 1 S2 + 0 S3 = 8
1 2 0 0 1 24

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
31
 Si igualamos dos valores a cero, obtenemos un sistema de tres
ecuaciones y tres variables, sistema de solución única puesto que los vectores
de coeficientes que se conservan en el miembro izquierdo son linealmente
independientes.
¿ Que sucede si x1 = S3 = 0 ? ==> la penta-upla será (0;12;16;-4;0),
esta solución viola la restricción de no negatividad, es por lo tanto no factible y
debe rechazarse. En el gráfico es el punto (0;12) que está fuera de la región
factible y debe rechazarse.

Solución factible básica (S F B). Se llama así a una solución factible y

básica; factible porque está en F y satisface las restricciones estructurales y de
no negatividad; básica porque la validez de la solución depende de m vectores
linealmente independientes, que en conjunto forman la base del espacio m-
dimensional. La dimensión de este espacio es el número de restricciones m.

1 0 0 16
si x1 = x2 = 0 ==> 0 S1 + 1 S2 + 0 S3 = 8
0 0 1 24
o
100 S1 16
010 S2 = 8
001 S3 24

Si igualamos a cero otras dos variables obtenemos un nuevo sistema, si en él

los vectores de coeficientes son nuevamente linealmente independientes,

tendremos una nueva base y una nueva S.F.B. la que nos sitúa en otro
punto extremo.
Por lo tanto, desplazarse de un punto extremo a otro en F significa
esencialmente tomar una nueva base para el espacio de requerimientos.
Para determinar una S.F.B. usamos un método algebraico y no
geométrico, así en un programa lineal de m restricciones y n variables de
elección el espacio solución tendrá dimensión n+m y el espacio de
requerimientos será m-dimensional.
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
32
 Localizar un punto extremo es hallar una S.F.B., una vez halladas todas
las S.F.B. calculamos los valores correspondientes del maximando y elegimos
de todos ellos el óptimo. En nuestro ejemplo z = 40 (16) + 30 (4) = 760 .
Cuando se trabaja con muchas variables y muchas restricciones se
recurre al método simplex.

Resumiendo:

Solución Factible: S.F. es cualquier conjunto de valores de P variables

que satisfacen tanto las restricciones estructurales como las de no negatividad.

Solución Básica: S.B. es cualquier solución que se obtiene al hacer

igual a cero (P - m) variables y al resolver el sistema de ecuaciones para los
valores de las m variables restantes. Esas m variables resueltas se llaman
variables básicas y constituyen una base.
Las P - m variables restantes se llaman variables no básicas.
Solución Factible Básica S.F.B. es una solución básica que además
cumple con las restricciones de no negatividad.

En un ejemplo de minimización, con el incumplimiento inexacto de

alguna restricción se presenta un consumo de algún elemento por sobre el
requerimiento mínimo del mismo o dicho de otra forma existe un excedente en el
uso de las capacidades, podemos decir una sobreutilización de la capacidad.
Esos excedentes se representan con el símbolo E i. Ei significa
variable de demasía o excedente de la i-ésima restricción. Estas variables
también reciben el nombre de variables ficticias.

Al considerar los excedentes podemos transformar una desigualdad en

una igualdad estricta. Estas variables de demasía, que cumplen la misma
función que las variables de holgura (conservar el equilibrio en ambos
miembros de la ecuación), se sustraen en el primer miembro de cada
restricción del tipo .
Las variables de demasía son no negativas.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
33
 En cada restricción del tipo y en cada restricción de igualdad ,se
añade en el primer miembro otra variable no negativa llamada variable
artificial. Esta variable artificial carece de significado real en el problema, su
única función es servir como punto de partida o solución inicial para el método
simplex.
Conclusión: En las restricciones del tipo se suma la variable
artificial y se resta una variable de demasía. En lo demás se procede igual
que en los casos de maximización.
A continuación mostramos la transformación necesaria para hallar la
solución en un problema de minimización cuando todas las restricciones son
desigualdedes del tipo .

Ejemplo 10:
min im izar z x1 6 x2 2 x3

x1 2 x2 2
sujeto a x1 x2 3 x3 2

x1; x2 ; x3 0
Para transformar este p.l. tendremos que: a las variables artificiales en
la función objetivo se le asignan coeficientes muy grandes (grandes en relación
a los coeficientes de las variables de elección) y a las variables de demasía se
les asigna coeficientes cero como a las de holgura.
Para plantear el problema como un sistema de ecuaciones y respetando
las pautas dadas, transformamos de la siguiente manera:

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
34
 min imizar z x1 6 x2 2 x3 0 E1 0 E 2 M A1 M A 2

x1 2 x2 - E1 A1 2
sujeto a x1 x2 3 x3 - E2 A2 2

x1; x2 ; x3 ; E1; E 2 ; A1 ; A 2 0

Todo lo dicho ante riormente puede resumirse en este ejemplo:

z 5 x1 10 x2 función objetivo

x1 x2 100
sujeto a 2 x1 3 x2 40 restricci ones estructurales
x1 2 x2 25

x1; x2 0

La transformaciones en los casos de maximización y minimización son;

max imizar z 5 x1 10 x2 0S1 0E 2 MA 2 MA 3

x1 x2 S1 100
sujeto a 2 x1 3 x2 - E2 A2 40
x1 2 x2 A3 25

x1; x2 ; S1; E 2 ; A 2 ; A3 0

min imizar z 5 x1 10 x2 0S1 0E 2 MA 2 MA 3

x1 x2 S1 100
sujeto a 2 x1 3 x2 - E2 A2 40
x1 2 x2 A3 25

x1; x2 ; S1; E 2 ; A 2 ; A3 0

METODO SIMPLEX

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
35
 BUSQUEDA DEL PUNTO EXTREMO OPTIMO

Localizar un punto extremo es hallar una S.F.B., esto ya lo hemos dicho,

pero elegir la solución óptima cuando se trabaja con muchas variables y
restricciones no es sencillo, se debe buscar entre todas las S.F.B.
Existe un método llamado SIMPLEX que soluciona el problema. La idea
de este método es comenzar con un punto extremo inicial, calcular el valor de la
función objetivo y ver si se lo puede mejorar desplazándonos a un punto
extremo adyacente.
Este método es iterativo; se repite hasta que el valor de z no admite
más mejoras, en este caso, el último valor encontrado será el óptimo.
Este método iterativo, que consiste en desplazarse de un vértice a otro
de la región factible, se ve apoyado por la computación, ya que existen
programas de cálculo para determinar los óptimos.
El método simplex es el procedimiento no gráfico de mayor uso. Es
una técnica algebraica para resolver los sistemas de ecuaciones en que ha de
optimizarse la función objetivo.
MÉTODO SIMPLEX: proceso iterativo que parte de una solución
factible inicial, busca luego mejorar esa solución mejorando el valor de z, y
si lo consigue, continúa la búsqueda. Para cada solución sucesiva
resuelve un sistema de ecuaciones lineales. La búsqueda termina cuando
la función objetivo no admite mejoramiento.

Requisitos:

1- Todas las restricciones deben formularse como ecuaciones.

2- El miembro derecho de una restricción no puede ser negativo.
3- Todas las variables están restringidas a valores no negativos

¿Cuál es el álgebra del método simplex ?. Este método se basa en

una aritmética conocida, y es la eliminación gaussiana ya explicada en el tema
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
36
de ecuaciones. La eliminación gaussiana se sirve de operaciones de renglón
para transformar un sistema de ecuaciones en otro equivalente.
El sistema de ecuaciones estará formado por la función objetivo y las
restricciones, así z será una variable más en el sistema. La función objetivo será
la ecuación número cero que se colocará en el renglón cero y las restricciones
serán las ecuaciones 1, 2, ... m que figurarán en los renglones 1, 2, ... m .

TABLA DEL SIMPLEX

El método simplex se aplica esquematizado en una tabla denominada
tabla del simplex, la que contiene columnas y filas, detalladas así:

Columnas:
1ra c.: indicativa de las variables básicas.
2da c.: indicativa de la función objetivo.
3ra c, 4ta, c, .: etc.: indicativas de cada una de las variables de elección.

* - columnas indicativas de las variables de holgura o de demasía.

* - columnas indicativas de las variables artificiales.
*.- columnas indicativas de los bi o términos independientes que figuran en
el segundo miembro de las igualdades.
* - la última columna corresponde al número de renglón.

Filas:
1ra f.: se coloca en ella los nombres de las variables y demás nombres
de columnas.
2da f., 3ra f. ... m+1 f. : en la segunda fila se colocan los datos del renglón
cero que son los coeficientes de la función objetivo, y en las restantes filas se
colocan los coeficientes que aparecen en las ecuaciones transformadas, es
decir los coeficientes de las distintas variables en las respectivas ecuaciones.

Volviendo a nuestro ejemplo de maximización anterior:

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
37
 maxim izar z 40x1 30x2 función objetivo

x1 16
sujeto a x2 8
x1 x2 24

x1; x2 0

Transformando el modelo, éste se escribirá:

maxim izar z 40x1 30x2 0S1 0S2 0S3 función objetivo

x1 S1 16
sujeto a x2 S2 8
x1 2 x2 S3 24

x1; x2 ; S1; S2 ; S3 0

La tabla que corresponde, según lo descripto es:

variables z x1 x2 S1 S2 S3 bi Nº de renglón
básicas

1 -40 -30 0 0 0 0 0
S1 0 1 0 1 0 0 16 1

S2 0 0 1 0 1 0 8 2

S3 0 1 2 0 0 1 24 3

Al hallar una S.F.B. encontramos una base particular para el espacio

tridimensional de requerimientos. Omitiendo la fila cero, de las otras tres
podemos tomar tres vectores columnas linealmente independientes.
En un problema de maximización que tenga todas sus restricciones del
tipo , la solución inicial tiene un conjunto de variables básicas integrado por las
variables de holgura.
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
38
 En nuestro ejemplo si x1 = x2 = 0 ==> S1 = 16 ; S2 = 8; S3 = 24
Luego el método simplex compara las variables no básicas con las
básicas y si ocurre que: 1) la función objetivo puede mejorarse y 2) es factible
una nueva solución, entonces el método simplex sustituye una variable básica
por una no básica.
Nuestra solución (0;0;16;8;24) que es una S.F.B. nos dice que no hay
producción, el beneficio es cero (z = 0) como se observa en el renglón cero.
Recalcamos: sólo para iniciar se adoptó una S.F.B. que incluye valores
de holgura, los que tienen como vector de coeficientes a vectores unidad
linealmente independientes.
El valor de z puede leerse en la tabla, junto con los valores de las
variables que forman la base del espacio de requerimientos.
Podemos considerar la matriz identidad: I m 1 x m 1 y escribir:

0001 z 0
=
1000 x S1 = 16

0100 S2 8

0010 S3 24

Si intentamos mejorar nuestro beneficio, nos trasladamos a una nueva

S.F.B. ¿ Cómo?.
El proceso de cambio de base se llama pivoteo y consiste en
reemplazar un vector columna de la base actual por otro que no está en ella.
Esto significa sustituir una variable de holgura por una de elección actualmente
excluída. Es decir que existen vectores (variables) salientes y entrantes.
Como lo que queremos es mejorar z, buscamos orientación en la función
objetivo. Los coeficientes de renglón cero (0) de todas las variables (salvo z)
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
39
representan el cambio en el valor actual de z si la variable (en esa columna)
aumenta de valor en una unidad. El signo de esos coeficientes es el contrario
de la dirección real del cambio. Un coeficiente negativo indica un crecimiento
de z y un coeficiente positivo denota un decrecimiento de z.
Así en z la tasa marginal de beneficio de x1 es de $ 40 y la de x2 es de
$ 30. Elegimos entonces x1 como variable de entrada, ya que eleva el beneficio
en mayor proporción.
En un problema de maximización la variable no básica que sustituye a
una variable básica es la que tiene el coeficiente más negativo en el renglón
cero. Los empates se definen de modo arbitrario, pudiéndose así tomar el que
está más a la izquierda en la tabla. A la columna de la nueva variable básica la
llamamos columna pivote. (x1 es la variable entrante y su columna la columna
pivote).
Ahora falta decidir qué variable será sustituida, es decir qué columna
será eliminada y comprobar que la nueva columna de la base es un vector
linealmente independiente ( l.i.).
Esto se resuelve simultáneamente, transformando la columna pivote en
un vector unidad compuesto por 1 en una de las filas inferiores a la fila cero y
por ceros en las demás filas (operaciones de renglón). Queda por decidir la
ubicación exacta de 1, éste elemento 1 de la columna pivote se llamará
elemento pivote. Se procede entonces de la siguiente manera:
Para cualquier columna los valores aij, (i=1...m) se llaman tasas
marginales de sustitución e indican los cambios requeridos en cada una de
las variables básicas actuales si la variable (en la columna pivote) aumenta en
una unidad. El signo de estas tasas marginales de sustitución es el contrario de
la dirección real del cambio. Un valor positivo de a ij denota una disminución de
la i-ésima variable básica y un valor negativo de a ij indica un aumento de esa
variable.
En nuestra columna pivote z aumenta en cuarenta (40) unidades por
cada unidad que crece x1, pero S1 decrecerá una unidad lo mismo que S3.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
40
 Tomemos aquellos aij > 0 de la columna pivote (con excepción del de la
fila cero) y dividamos cada elemento de la columna de las constantes, bi por el
correspondiente aij.
bi
A esos cocientes los denominamos cocientes de desplazamientos;
aij

una vez hallados los comparamos y elegimos como fila pivote aquella cuyo
cociente sea el menor. El elemento que está en la intersección de la fila y la
columna pivote es el elemento pivote.
bi
¿Por qué se elige el menor ? Para asegurarnos que el incremento
aij

de producción de x1 es lo suficientemente pequeño como para poder

permanecer dentro de los límites de las restricciones estructurales y para que
cada variable respete la restricción de no negatividad.
Variable básica de salida: es la que se sustituirá. Es la que se obtiene
determinado el renglón asociado a:
bi
valor mínimo de: para i = 1 ... m / aij > 0
aij

16 24
En nuestro ejemplo, solo hay dos cocientes: y , como 16 < 24
1 1
==> la fila pivote será la fila o renglón (1) y la variable de salida S 1. La nueva
tabla será:
variables z x1 x2 S1 S2 S3 bi Nº de renglón
básicas

1 0 -30 40 0 0 640 0
x1 0 1 0 1 0 0 16 1

S2 0 0 1 0 1 0 8 2

S3 0 0 2 -1 0 1 8 3

La segunda S.F.B. es (16;0;0;8;8) z = 640

La nueva base la forman (x1 ; S2 ; S3) y se excluyen x2 y S1, que no
contienen vectores unitarios. El valor de z ha crecido hasta un beneficio de $
640.
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
41
 Aun existe una tasa marginal de beneficio positiva, pues aún figura en
la tabla el valor (-30) en el renglón cero; iteramos lo hecho y obtenemos
entonces la siguiente tabla:
Columna pivote: la de x2 (existe allí (-30)).

bi 8 8
Fila pivote: = y son los cocientes de desplazamiento de los
aij 1 2

renglones 2 y 3; como 4 < 8, la fila pivote es la fila 3 y S3 la variable salida.

variables z x1 x2 S1 S2 S3 bi Nº de renglón
básicas

1 0 0 25 0 15 760 0
x1 0 1 0 1 0 0 16 1
S2 0 1 1 4 2
0 0 1
2 2

S3 0 1 1 4 3
0 1 0
2 2

S.F.B. (16;4;0;4;0) z = 760 S1 = S3 = 0

No podemos proseguir, en la fila cero no xisten más valores negativos,
lo que indica que no tendremos ningún beneficio adicional.
Por lo tanto esta S.F.B. es la óptima y 760 es el máximo beneficio a
obtener.
En un problema de maximización se habrá encontrado la solución
óptima si todos los coeficiente en el renglón cero de las variables son
mayores o iguales que cero. Si estos coeficientes son menores que cero
(negativos) para las variables no básicas puede obtenerse una mejor solución
asignándoles una cantidad positiva.

RESUMEN DEL METODO SIMPLEX PARA EL CASO EN

QUE TODAS LAS RESTRICCIONES SEAN DEL TIPO :

1- Definimos las variables de holgura Si y las sumamos a las restricciones ri

para transformarlas en ecuaciones.
Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
42
2- Construimos la tabla simplex colocando en ella los coeficientes de las
variables y las constantes del segundo miembro.

3- Se identifica la solución inicial en la que las variables básicas son las Si Se

determina si la solución actual es la óptima considerando los coeficientes del
renglón cero (0). Si todos ellos son 0 se interrumpe el proceso y ésa es la
solución óptima, caso contrario se continúa.

5 Se determina la variable no básica que se convertirá en básica,

considerando el coeficiente más negativo en el renglón (0). Esta será la
variable de entrada.

6- Se identifica la variable básica a sustituir o variable de salida calculando la

bi
razón mínima donde aij > 0. El cociente más pequeño determina la
aij

variable de salida.

7- Se aplican las operaciones de eliminación gaussiana para llegar a la nueva

solución. Acá regresamos nuevamente al paso 4.
Para problemas de maximización con restricciones mixtas del tipo ( ;
; =) el método simplex no varía, sólo tendremos que agregar las variables
correspondientes al transformar las restricciones en ecuaciones.
Para cada restricción del tipo se sustrae una variable de demasía y al
lado de ella se suma una variable artificial. En cada restricción del tipo = se
suma una variable artificial en el primer miembro. A la tabla simplex le
agregamos una columna más por cada variable complementaria.
En la función objetivo basta con colocar coeficientes apropiados, ceros
para las variables de excedencia y valores muy altos para las variables
artificiales. A esos valores muy altos de variables artificiales los llamamos (-M) y
debemos aclarar que son altos en relación con los coeficientes aij.
En cualquier problema de p.l., las variables básicas serán todas las
variables de holgura y todas las variables artificiales que aparezcan en el
problema.

PROBLEMAS DE MINIMIZACION

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
43
 En estos problemas la región factible no incluye el punto de origen, por
ello no conviene comenzar desde dicho punto, además las variables de demasía
se sustraen, de allí que las últimas columnas dan una matriz identidad negativa.

Si consideramos como solución inicial la del punto origen x1 = x2 = ... =

xn = 0, entonces los valores de E1 ; E2 ; ... ; Em serán negativos.

Una solución es ampliar el programa incorporando variables artificiales

no negativas a las restricciones, estas variables tienen coeficientes muy grandes
en la función objetivo (grandes comparados con los aij). Los coeficientes
grandes o elevados en la función objetivo hacen que esos productos o artículos
artificiales sean muy caros y nadie los tendrá en cuenta. En la función objetivo
en un caso de minimización los coeficientes de las variables artificiales se
indican con M.
Una vez reformulado el sistema de ecuación se aplica el método simplex
en la forma ya explicada, pero primero debemos sumar la expresión: M.(fila 1 +
... + fila i) a la fila cero a fin de que desaparezcan los coeficientes (-M) de las
variables artificiales.

En este tipo de problemas la variable no básica que sustituirá a una

variable básica es la que tiene el mayor coeficiente positivo en el renglón (0).

En un problema de minimización, la solución óptima se obtiene

cuando en el renglón (0) todos los coeficientes de las variables son 0. Si
los coeficientes son positivos para las variables no básicas, puede obtenerse
mejor solución.

Ejemplo 11:

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
44
 min im izar z 5 x1 6 x2 función objetivo

x1 x2 10
sujeto a
2 x1 4 x2 24

x1; x2 0
se transforma en :

min im izar z 5 x1 6 x2 0E1 0E2 MA1 MA 2 función objetivo

x1 x2 E1 A1 10
sujeto a
2 x1 4 x2 - E2 A2 24

x1; x2 ; E1; E 2 ; A1; A 2 0

La tabla correspondiente del simplex es:

variables Nº de renglón
z x1 x2 E1 E2 A1 A2 bi
básicas

1 -5 -6 0 0 -M -M 0 0
A1 0 1 1 -1 0 1 0 10 1

A2 0 2 4 0 -1 0 1 24 2

variables Nº de renglón
z x1 x2 E1 E2 A1 A2 bi
básicas

1 -5+3M -6+5M -M -M 0 0 34M 0

A1 0 1 1 -1 0 1 0 10 1

A2 0 2 4 0 -1 0 1 24 2

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
45
 variables Nº de
z x1 x2 E1 E2 A1 A2 bi
básicas renglón

1 M 3 M 3 5M 36+4M 0
2 0 -M 0
2 2 4 2 4
A1 0 1 1 1 4 1
0 -1 1
2 4 4

x2 0 1 1 1 6 2
1 0 - 0
2 4 4

se continúa porque x1 y E2 son positivos

variables Nº de
z x1 x2 E1 E2 A1 A2 bi
básicas renglón

1 1 1 52 0
0 0 -4 4-M M
2 2
x1 0 1 1 8 1
1 0 -2 2
2 2

x2 0 1 1 1 2 2
1 1 - -1
2 2 2

Los resultados que arroja la tabla son:

z 52; x1 8; x2 2

Hemos obtenido así la solución óptim, ya que todos los coeficientes en

el renglón cero (0) son 0 para las variables básicas y las no básicas.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
46
CASOS DE DEGENERACION

En el caso simplex se considera degeneración a la aparición de

cocientes de desplazamiento "ligados", cuando dos o más de ellos son los
menores y entonces ocurrirá que existen dos o más filas candidatas a ser filas
pivotes.
Un criterio para romper la ligadura es considerar fila pivote la que
corresponde a la variable ligada que se encuentre más a la izquierda en la tabla
simplex. Luego se procede como en los restantes casos.
Otro caso de degeneración ocurre cuando al pivotear no obtenemos una
mejora en el beneficio o una reducción en el costo. A veces varios pasos de
pivote dan una mejora nula antes de que el proceso iterativo rompa ese círculo
vicioso.
Además de estos dos casos: el de ligadura y el de mejora nula, la
aplicación del método simplex no encuentra otros casos de degeneración.

FENOMENOS ESPECIALES

Ya hemos explicado tres fenómenos especiales cuando se resuelven

problemas de p.l., ellos son: soluciones óptimas alternativas; solución no factible
y soluciones no acotadas. ¿ Cómo se presentan esos fenómenos al resolver un
problema por el método simplex?.

SOLUCIONES OPTIMAS ALTERNATIVAS

En el gráfico existen soluciones óptimas alternativas cuando la función

objetivo es paralela a una restricción que impone la dirección de la optimización;
con el método de puntos en la esquina se produce un empate en los puntos
óptimos, pero si se aplica el método simplex ocurre que:
 Se ha identificado una solución óptima y
 El coeficiente en el renglón (0) para una variable no básica es (0).

Por haberse identificado solución óptima no existe otra mejor, pero al

figurar un (0) en el renglón cero para una variable no básica nos esta indicando
que esta se puede convertir en variable básica y llegar a ser positiva, sin
embargo el valor de z no varía.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
47
Ejemplo 12:

maxim izar z 6 x1 4 x2 función objetivo

x1 x2 5
sujeto a
3 x1 2 x2 12

x1; x2 0

variables Nº de renglón
z X1 X2 S1 S2 bi
básicas

1 -6 -4 0 0 0 0
S1 0 1 1 1 0 5 1
S2 0 3 2 0 1 12 2

Indica solución óptima alternativa

variables Nº de renglón
z x1 x2 S1 S2 bi
básicas

1 0 0 0 2 24 0
S1 0 1 1 1 1
0 1 -
3 3
x1 0 2 1 4 2
1 0
3 3

variables Nº de renglón
z x1 x2 S1 S2 bi
básicas

1 0 0 0 2 24 0
x2 0 0 1 3 -1 3 1
x1 0 1 0 -2 1 2 2

z = 24 no varió

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
48
AUSENCIA DE SOLUCIÓN FACTIBLE

La condición de ausencia de solución factible se manifiesta en el método

simplex cuando una variable artificial aparece con carácter óptimo en un nivel
positivo.

Ejemplo 13:

maxim izar z 10 x1 20 x2 función objetivo

x1 x2 5
sujeto a
x1 x2 20

x1; x2 0

se transforma en :

maxim izar z 10x1 20x2 0S1 0E2 - MA 2 función objetivo

x1 x2 S1 5
sujeto a
x1 x2 - E2 A2 20

x1; x2 ; S1; E2; A 2 0

La tabla correspondiente es:

variables x1 x2 S1 E2 A2 bi
z Nº de renglón
básicas

1 -10 -20 0 0 M 0 0
S1 0 1 1 1 0 0 5 1
A2 0 1 1 0 -1 1 20 2

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
49
 variables x1 x2 S1 E2 A2 bi
z Nº de renglón
básicas

1 -10-M -20-M 0 M 0 -20M 0

S1 0 1 1 1 0 0 5 1
A2 0 1 1 0 -1 1 20 2

variables Nº de renglón
z x1 x2 S1 E2 A2 bi
básicas

1 10 0 M+20 M 0 -15M+100 0
x2 0 1 1 1 0 0 5 1
A2 0 0 0 -1 -1 1 15 2

La solución óptima es x 2 = 5 ; A2 = 15 y z = -15M + 100

Las variables artificiales carecen de significado en un problema de p.l. y
el hecho de que en el resultado figure A2=15 no es indicativo de que el
problema tenga solución.

SOLUCIONES NO ACOTADAS

Estas soluciones existen cuando:

 El espacio solución no está acotado.

 El mejoramiento de z es en dirección de la parte no acotada del
espacio solución.

Si en el método simplex, en uno de los pasos iterativos los valores de a ij

son ceros o negativos, para que la variable seleccionada se convierta en la
nueva variable básica, el problema de p.l. tiene una solución no acotada.
Los aij son las tasas marginales que indican los cambios que sufren los
valores de las actuales variables básicas por cada unidad de la nueva variable
básica.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
50
  Si aij > 0 ==> disminución en los valores de las variables básicas.
 Si aij < 0 ==> crecimiento en los valores de las variables básicas.
 Si aij = 0 ==> no cambios en los valores de las variables básicas.
 Si todos los aij 0 ninguna variable básica disminuye su valor y no
tendrá limite el número de unidades que pueden introducirse de la
nueva variable.

Ejemplo 14:

maxim izar z 2 x1 3 x2 función objetivo

x1 10
sujeto a
2 x1 x2 30

x1; x2 0

La correspondiente tabla es:

variables Nº de renglón
z x1 x2 S1 S2 bi
básicas

1 2 -3 0 0 0 0
S1 0 1 0 1 0 10 1
S2 0 2 -1 0 1 30 2

En el renglón cero se determina que la variable de entrada es x2, la que

ha de mejorar el valor de z. Sin embargo los valores a12 = 0 y a22 = -1 nos
dicen que por cada unidad que se introduzca de x2, S1 no cambiará y S2
aumentará en una unidad. No se llevará a cero a ninguna de estas variables
básicas.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
51
DUALIDAD

Los problemas de maximización y minimización si bien se tratan

individualmente, son factibles de ser considerados simultáneamente. Por cada
problema lineal de maximización existe uno de minimización y recíprocamente,
por cada programa lineal de minimización existe uno de maximización.

El programa original recibe el nombre de programa primario o primal

y su recíproco se conoce como programa dual o simplemente dual.
Si estamos por resolver un programa de minimización (minimizar z )
éste será el primal y el correspondiente recíproco de maximización (maximizar
z* ) será el dual.
Los valores óptimos de las funciones objetivo del primal y del dual son
idénticos, los que nos da la posibilidad de trabajar con el programa más sencillo
de los dos.

z z*

FORMULACIÓN DE UN PROBLEMA DUAL.

Dado el primal, recordemos la simbología utilizada

 función objetivo: z
 coeficientes de la función objetivo: cj
 variables de elección: xj
 coeficientes de las variables de elección en las restricciones: a ij
 restricciones: ri
 constantes que figuran en el 2do miembro de las restricciones: bi

Ejemplo de primal:
Supondremos que el problema original es de maximización, luego el
dual será de minimización.
Se expresa a continuación la simbología correspondiente a ambos
casos, en forma general, de sumatoria y matricial.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
52
 maxim izar z c1x1 c2 x2 ... c j x j ... cn xn función objetivo

a11x1 a12x2 .... a1 j x j .... a1n xn b1

a21x1 a22x2 ... a21 j x j .... a2n xn b2
sujeto a ........................................................................
ai1x1 ai 2 x2 ... aij x j .... ain xn bi
.......................................................................
am1x1 am 2 x2 ... amj x j .... amnxn bm

x1, x2 , .., x j ,....,xn 0 o xj 0 con j 1, 2,..n

n
maxim izar z cj xj
j 1

n
o sujeto a aij x j bi i 1, 2,..., m
j 1

xj 0 j 1, 2,..., n

maxim izar z CX función objetivo

sujeto a AX B restricciones estructurales

xj 0 con j 1, 2,..., n restricciones de no negatividad

Las matrices:

A aij , B bi mx1 , X xi mx1 y C cj , pueden escribirse:

mxn 1xn

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
53
 a11 a12 ... a1 j ... a1n b1
a 21 a 22 ... a 2 j ... a 2n b2
. . . . . . .
A , A K mxn , B , B K mx1
ai1 ai 2 ... aij . ... a in . bi
. . . . . . .
a m1 a m2 ... a mj ... a mn bm

x1
x2
.
C c1 c2 ... c j ... cn , C K1x n X , X K nx1
xi
.
xn
Para escribir el correspondiente dual, transformamos el programa de la
siguiente manera:

 Si el primal es de maximización su dual será de minimización. El

sentido de la optimización es siempre el opuesto en un primal y su
correspondiente dual.
 Los signos de las desigualdades del primal se invierten en el dual,
menos el signo de las condiciones de no negatividad.
 El número de las variables en el primal siempre es igual al número de
restricciones en el dual. El número de restricciones en el problema primario
siempre es igual al número de variables del dual.
 El coeficiente de la función objetivo del primal para la j- ésima
variable de elección es igual a la constante cj que figura en el segundo miembro
de la j-ésima restricción del dual. El vector fila de los cj del primal traspuesto es
el vector columna de las constantes de los segundos miembros de las
restricciones en el dual.
 La constante bi que figura en el segundo miembro de la i-esima
restricción del primal es el coeficiente de la i-esima variable de elección de la
función objetivo del dual. El vector columna de los b i del primal, traspuesto, es
el vector fila de los coeficientes de las variables de elección de la función
objetivo en el dual.
 Los coeficientes aij en el primal son los aji del dual, es decir los
coeficientes de fila del primal (en las restricciones) se convierten en los
coeficientes de columnas de las restricciones del dual. De otra manera, la matriz
de coeficientes del primal traspuesta es la matriz de coeficientes del dual.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
54
 Prosiguiendo con nuestro ejemplo el dual será:

min im izar z* b1 y1 b2 y2 ... bi yi ... bm ym función objetivo

a11y1 a21y2 .... ai1 yi .... am1 ym c1

a12 y1 a22 y2 ... ai 2 yi ... am 2 ym c2
sujeto a ........................................................................
a1 j y1 a2 j y2 ... aij yi .... amj ym c j
.......................................................................
a1n y1 a2n y2 ... ain yi .... amn ym cn

y1, y2 , .., yi ,...., ym 0 o yi 0 con i 1, 2,.., n

m
min im izar z bi yi
i 1

m
o sujeto a a ji yi cj j 1, 2,..., n
i 1

yi 0 i 1, 2,..., m

minim izar z* Bt Y función objetivo

sujeto a At Y Ct restricciones estructurales

yi 0 con i 1, 2,..., m restricciones de no negatividad

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
55
 Las matrices:

At a ji , Bt bi 1xm , Y yi mx1 y Ct cj , pueden escribirse:

nxm nx1

a11 a 21 ... a i1 ... a m1 c1

a12 a 22 ... a i 2 ... a m 2 c2
. . . . . . .
At , At K nxm , Ct , Ct K nx1
. . ... . ... . cj
. . . . . . .
a1n a 2n ... a in ... a mn cn

y1
y2
.
Bt b1 b2 ... bi ... bm , Bt K1x m Y , Y Km x 1
yi
.
ym

El dual de un programa dual es el primal siempre que las y se

conviertan en x y eliminemos el asterisco de la función objetivo.
Cuando empleamos el método simplex, tenemos la posibilidad de
elección entre el primal y el dual y escogemos aquel que tenga menos
restricciones, porque entonces es menor la dimensión de la base y también es
menor el número de variables ficticias que agregar.
Cuando en el primal y en el dual el número de restricciones sea el
mismo, escogemos el programa de maximización porque podemos partir de una
S.F.B. inicial ya dada y además no necesitamos incorporar variables artificiales.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
56
REGLAS PARA TRASFORMAR UN PRIMAL DE MAXIMIZACIÓN
EN UN DUAL DE MINIMIZACIÓN

P.L. DE MAXIMIZACIÓN P.L. DE MINIMIZACIÓN

1- número de restricciones 1- número de variables

2- restricción 2- variable no negativa

3- restricción 3- variable no positiva

4- restricción = 4- variable no restringida

5- número de variables 5- número de restricciones

6- variable no negativa 6- restricción

7- variable no positiva 7- restricción

8- variable no restringida 8- restricción =

9- cj [Link] z para xj 9- [Link] el 2do [Link] rj

10- bi cte. 2do miembro en 10- c) coeficiente en z para xi

la i-esima restricción
11- aji coeficiente en restricción i para la 11- aji coef. en restricción j para la
variable j variable i

Ejemplo 15:
maxim izar z 100 x1 140 x2 50x3 función objetivo

x1 2 x2 x3 10
sujeto a x1 4 x3 20
x1 x2 15
x1 3 x2 2 x3 12

x1 0
x2 0
x3 no restringida

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
57
 El dual es:

min im izar z* 10 y1 20 y2 15y3 12 y4 función objetivo

y1 y2 y3 y4 100
sujeto a 2 y1 - y3 3 y4 140
y1 4 y2 - 2 y4 50
y1 0
y2 no restringida
y3 0
y4 0

Ejemplo 16:
Problema Primal Problema Dual

maxim izar min im izar

z 2 x1 4 x2 z* 800y1 350y2 125y3

5 x1 4 x2 800
5 y1 3 y2 - 4 y3 2
sujeto a
sujeto a 3 x1 2 x2 350
4 y1 2 y2 3 y3 4
4 x1 3x2 125
y1; y2 y3 0
x1; x2 0

Este ejemplo puede escribirse en forma matricial:

maximizar z 2 x1 4 x2
sujeto a
5 4 x1 800
3 2 350
-4 3 x2 125

x1; x2 0

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
58
 minimizar z * 800y1 350y2 125y3
sujeto a
5 3 -4 y1 2
4 2 3 y2 4
y3

y1; y2 ; y3 0

PARA TENER EN CUENTA:

1- Si existen soluciones factibles óptimas, los valores óptimos de las

funciones objetivas del primal y del dual son idénticos.

z z*

2a- Si una variable de elección en el óptimo de un p.l. es distinta de

cero, entonces la correspondiente variable ficticia en el programa recíproco debe
ser cero en el óptimo.
xj variable de elección del primal
yi variable de elección del dual
Si i-esima variable ficticia del primal
Ej j-ésima variable ficticia del dual

Si
x j > 0 ==> E j = 0 y si y i > 0 ==> S i = 0

2b- Si una variable ficticia en la solución óptima de un programa lineal

es distinta de cero, entonces la correspondiente variable de elección en el
programa reciproco debe ser cero en el óptimo.

Si
E j > 0 ==> x j = 0 y si S i > 0 ==> y i = 0

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
59
SOLUCIÓN DE UN PROBLEMA PRIMARIO Y SU DUAL

Ejemplo 17:

Problema primal Problema dual

maxim izar minim izar
z 5 x1 6 x2 z* 120 y1 260y2

3x1 2 x2 120 3 y1 4 y2 5
sujeto a sujeto a
4 x1 6 x2 260 2 y1 6 y2 6

x1; x2 0 y1; y2 0

z 5 x1 6 x2 0S1 0S2 0S3 0

3 x1 2 x2 S1 120
4 x1 6 x2 S2 260
x1; x2 ; S1; S2 0

variables x1 x2 S1 S2 bi
z Nº de renglón
básicas
1 -5 -6 0 0 0 0
S1 0 3 2 1 0 120 1
S2 0 4 6 0 1 260 2

variables x1 x2 S1 S2 bi
z Nº de renglón
básicas
1 -1 0 0 1 0 0
S1 0 5 1 200 1
0 1 -
3 3 6
x2 0 2 1 260 2
1 0
3 6 6

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
60
 variables x1 x2 S1 S2 bi
z Nº de renglón
básicas
1 3 4 280 0
0 0
5 5
x1 0 3 1 20 1
1 0 - 1
5 5
x2 0 2 3 30 2
0 1
5 10

S1 S2 0; x1 20; x2 30; z 280

Si hubiéramos realizado el dual:

variables y1 y2 E1 E2 A1 A2 bi
z* Nº de renglón
básicas
1 -120 -260 0 0 -M -M 0 0
A1 0 3 4 -1 0 1 0 5 1
A2 0 2 6 0 -1 0 1 6 2

variables y1 y2 E1 E2 A1 A2 bi
z* Nº de renglón
básicas
1 -120+5M -260+10M -M -M 0 11M 0
0
A1 0 3 4 -1 0 1 0 5 1
A2 0 2 6 0 -1 0 1 6 2

variables z* y1 y2 E1 E2 A1 A2 bi Nº de renglón
básicas
1 - 100 5M 4M 260M 260 10M 260+M 0
0 -M 0
3 3 6 6 6 6
A1 0 5 2 2 1 1
0 -1 1 -
3 3 3
A2 0 1 1 1 1 2
1 0 - 0
3 6 6

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
61
 variables y1 y2 E1 E2 A1 A2 bi
z* Nº de renglón
básicas
1 0 0 -20 -30 20-M 30-M 280 0
y1 0 3 2 3 2 3 1
1 0 - -
2 5 5 5 5 5
y2 0 1 3 1 3 4 2
0 1 - -
5 10 5 10 5

3 4
E1 E2 0; y1 ; y2 ; z* 280
5 5

Los valores óptimos de las variables de decisión en un problema se

obtienen del renglón cero de la tabla de soluciones óptimas del otro problema.
3 4
Los valores óptimos y1 ; y2 pueden extraerse de la tabla 1 1
5 5
donde figuran como coeficientes en el renglón cero para las variables de holgura
S1 y S2 .
Los valores óptimos x1 20; x2 30 se pueden obtener de la
tabla 2 como los valores cambiados de signo de los coeficientes en el renglón
cero de las variables de demasía E1 y E2 . Estos valores también aparecen
bajo las variables A1 y A2 si se consideran los términos que no contienen a M.

E1 E2 0 x1 0; x2 0

S1 S2 0 y1 0; y2 0

INTERPRETACION ECONOMICA DE UN DUAL

Si bien en el cálculo de un programa lineal se puede sustituir éste por su

dual, el programa dual tiene un sentido económico diferente y con significado
particular.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
62
 Dado el primal:
maximizar z c1x1 c2x2

sujeto a

a11 a12 x1 b1

a21 a22 x2 b2

x1 ; x2 0

El dual será

minimizar z b1y1 b2y2

sujeto a

a11 a21 y1 c1

a12 a22 y2 c2

y1 ; y2 0

Si z esta en $, en $ debe estar z * , para ello (bi que es la cantidad del

recurso i de la que dispone la empresa) yi debe estar expresado en unidad de $
por unidad del i-ésimo recurso, sóo así biyi aparecerá en $. Esto significa que yi
es el valor del recurso considerado, ese valor es un valor imputado al recurso
en la contabilidad de la empresa, porque ésta ya lo posee, no sale a comprarlo
al mercado a ese precio. Ese valor yi se llama precio contable o precio
sombra y puede representar el costo de oportunidad de utilizar el i-ésimo
recurso.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
63
 La restricción de no negatividad yi 0 significa que al recurso no
podemos imputarle un valor negativo, el recurso siempre tiene valor positivo, si
el recurso no se utiliza en su totalidad el costo de oportunidad yi es nulo.

Por lo tanto yi > 0 significa plena utilización del i-ésimo recurso en la

solución óptima, entonces la variable de holgura es Si = 0.

La restricción a11y1 + a21y2 c1 ¿ Que indica?

Como aij es la cantidad del i-ésimo recurso empleada en producir una

unidad del j-ésimo producto, y c1 es el beneficio bruto por unidad del primer
producto, la expresión a11y1 + a21y2 c1 indica que el costo de oportunidad de
producir una unidad del primer producto sea imputado a un valor por lo menos
igual al del beneficio bruto del producto primero. Pero si el costo de oportunidad
de la producción excede al beneficio significa que la asignación del recurso no
es la óptima y conviene dejar de producir el primer producto, con lo cual se
liberan recursos para asignarlos a otros fines.
Al no producirse el primer producto x1 0 E1 0 .
Si se decide producir el primer producto es porque
a11y1 a12y2 c1 x1 0 E1 0 .

¿ Que ocurre con la función objetivo del dual?

Como b1 y b2 son las cantidades totales de recursos disponibles de la
empresa, z * b1y1 b2y2 evidencia el valor total imputado a esos recursos.
El dual persigue minimizar el valor de z * y también satisfacer las
restricciones.

Maximizar el beneficio hallando los niveles óptimos de producción

x1 y x2 (programa primal) es equivalente a minimizar el valor total
imputado a los recursos de la empresa o costo de oportunidad con la condición
de que el costo de oportunidad de cada producto no debe ser menor que el
beneficio bruto del mismo.
z z* significa que en el óptimo el beneficio bruto totales asignado
enteramente a los recursos de la empresa vía los precios sombra.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
64
 BIBLIOGRAFÍA

“INTRODUCCIÓN A LA INVESTIGACIÓN OPERATIVA”. HILLER, Frederick

S,-LIEBERMAN, J. , Editorial McGraw-Hill. Quinta Edición.
“INVESTIGACIÓN DE OPERACIONES”. Hamdy A. TAHA. Quinta Edición.
Alfaomega. México. 1995.
“INTRODUCCIÓN A LOS MODELOS CUANTITATIVOS PARA
ADMINISTRACIÓN”. ANDERSON, SWEENEY, WILLIIAMS. Editorial
Iberoamérica. México 1993.
“MÉTODOS Y MODELOS DE INVESTIGACIÓN DE OPERACIONES”.
Editorial Continental. México.1979.
“MODELOS CUANTITATIVOS PARA ADMINISTRACIÓN”. Grupo Editorial
Iberoamericana. México.1986.
“FUNDAMENTOS DE INVESTIGACIÓN DE OPERACIONES”. ACKOFF-
SASIENI. Editorial Limusa. 1991.
“INVITACIÓN A LA INVESTIGACIÓN DE OPERACIONES”.A. KAUFMANN
y R. FAURE. Editorial Continental.México.1964.
“INVESTIGACIÓN DE OPERACIONES”. Herbert MOSKOWITZ y Gordon
WRIGT. PRENTICE-HALL HISPANOAMERICANA. México. 1982.
“PROGRAMACIÓN LINEAL”. Isidoro MARIN, Víctor RODRIGUEZ y Oscar
PERINO. Ediciones MACCHI. 1981. Buenos Aires.
“LA PROGRAMACIÓN LINEAL EN EL PROCESO DE DECISIÓN”. MARIN-
PALMA-LARA. Editorial MACCHI. Segunda Edición. 1977. Buenos Aires.
“MATEMÁTICAS APLICADAS A LA ADMINISTRACIÓN Y A LA
ECONOMIA”. Jagdish ARYA y Robert LARDNER. Segunda Edición-PRENTICE-
HALL. México. 1985.
“METODOS FUNDAMENTALES DE ECONOMIA MATEMÁTICA “. Alpha C.
CHIANG. Tercera Edición. McGRAW-HILL. México, 1987.
“MATEMÁTICAS APLICADAS PARA ADMINISTRACIÓN, ECONOMIA Y
CIENCIAS SOCIALES. Frank S. BUDNICK. Tercera Edición. McGRAW-HILL.
México, 1990.

Carmen Rescala
Prof. en Matemática, Física y Cosmografía - Contadora Pública
Especialista en Ingeniería Gerencial
65