PROBLEMA DE LA PROGRAMACIÓN LINEAL - Samuel Ferrara

Vista previa del material en texto

[UNIDAD 2]
INTRODUCCION a la PROGRAMACIÓN LINEAL 
 ¿QUÉ ES UN PROBLEMA DE PROGRAMACIÓN LINEAL?
Consiste en un problema analítico que permite encontrar entre un gran número de soluciones aquella política única que optimice la FO. Es decir encontrar la mejor de las soluciones factibles medida por la función objetivo.
La PL es un caso particular de un problema de optimización donde la FO y las restricciones son lineales en cada una de las variables de decisión involucradas utilizan un modelo matemático para describir el problema.
El problema general de PL consiste en encontrar un vector (x1,x2,…,xn) que optimice (maximice o minimice) la forma lineal (o sea la función objetivo) sujeta a restricciones lineales.
Es un método analítico que nos permite encontrar dentro de un gran número de soluciones aquella política que optimice el valor de la FO.
Es un caso particular de los métodos de optimización y se da cuando tanto la FO como las restricciones son lineales en cada una de las variables de decisión xi y estas son no negativas.
PROBLEMA DE LA PROGRAMACIÓN LINEAL
Un PL es un problema de optimización en el cual se realiza lo siguiente:
a) Se trata de MAX o MIN una función Lineal de variables de decisión que no es más que la FO. Aquí también se identifica las Variables de decisión y los coeficientes
b) Los valores de cada una de las variables de decisión deben respetar un conjunto de restricciones que están en forma de ecuación lineal o desigualdades lineales
c) Debe existir una restricción de Signo para cada variable de decisión. Puede ser una variable Xi → (Xi>0) o puede ser Xi SRS (sin restricción de signo)
CARACTERISTICAS de un PROBLEMA de PROGRAMACIÓN LINEAL:
· Variables de decisión REALES: Son cantidades numéricas a determinar que representan la solución del problema. Estos valores son controlables de manera que podemos cambiarlos para optimizar la solución, son reales porque se obtienen de situaciones reales. Se debe especificar que representan y en que unidades esta
· Variables de decisión FICTICIAS: son cantidades numéricas que se introducen al modelo con el objetivo de aplicar artificios matemáticos para llegar a la optima solución del problema. Pueden ser de EXCESO u OLGURA
· OBJETIVOS
FO C1x1 + C2x2 + … + Cixi + … + Cnxn
· RESTRICCIONES: son las limitaciones que restringen el rango de valores que pueden tomar las variables de decisión.
si:
{a11x1 + a12x2 + … + a1jxj + … + a1nxn ≤ b1
{a21x1 + a22x2 + … + a2jxj + … + a2nxn ≤ b2
{ … + … + … + … + … + …
{ai1x1 + ai2x2 + … + aijxj + … + ainxn ≤ bi
{ … + … + … + …. + … + …
{am1x1 + am2x2 + … + amjxj + … + amnxn ≤ bm
Donde las aij, bi y Cj son constantes y m < n
Siempre supondremos que las ecuaciones han sido multiplicadas por -1 cuando sea necesario para hacer bi >0
Si hay una igualdad en las restricciones, estas son OBLIGATORIAS.
	INTERPRETACION DE VARIABLES
aij Coeficientes tecnológicos, coeficientes de las variables de decisión. Se llaman así puesto que nos indican la cantidad de recursos utilizados para producir cada unidad de producto. 
bi Indican la cantidad de recursos de las que se dispone. 
Ci Es el coeficiente de beneficio (unidad económica) por unidad de producto. 
FO : Z = 4x1 + 3x2 (MAX)
Sa:
 
· Condición de No NEGATIVIDAD: En la mayoría de los casos las variables de decisión representan cantidades de material a producir, a almacenar o a transportar, por lo que no sería posible tener valores negativos.
RESOLUCION DE UN PROBLEMA DE PL
Primero: Identificar las variables de decisión (decisiones de la empresa) (id q representa y unidades)
Segundo: Identificar los datos del problema 
Tercero: Formular la FO a optimizar
Cuarto: Especificar las restricciones estructurales de recurso y las restricciones de signo
SUPOSICIONES:
SUPOSICIONES DE PROPORCIONALIDAD y de ADITIVIDAD
El hecho de que la FO de un PL tenga que ser una función lineal tiene 2 aplicaciones
1- La contribución de cada variable de decisión a la FO es proporcional al valor de dicha variable de decisión
2- La contribución a la FO por parte de cualquier variable de decisión es independiente de los valores de las otras variables de decisión.
De manera análoga, el hecho de que cada restricción deba ser una igualdad o desigualdad lineal, implica que.
1- La aportación de cada variable al lado izquierdo de la restricción es proporcional al valor de esa variable
2- La contribución de cada variable al lado izquierdo de la restricción es independiente de las otras variables.
Para que un PL sea una representación apropiada de un problema de la vida real, las variables de decisión deben satisfacer ambas suposiciones y además deben satisfacer las suposiciones de divisibilidad y certidumbre.
SUPOSICION DE DIVISIBILIDAD: Requiere que cada variable de decisión pueda tomar valores fraccionarios
SUPOSICION DE CERTIDUMBRE: Significa que tiene que conocerse con certidumbre cada parámetro. Si no tuviéramos la cantidad exacta de cada uno de ellos, entonces no se cumple la suposición.
SOLUCION GRAFICA DE PROBLEMAS BIDIMENSIONALES DE PL
Cuando un problema tiene 2 variables de decisión se lo puede resolver GRAFICAMENTE
ESPACIO DE PF: se determina por la intersección de los semiplanos determinados por el grafico de las restricciones.
PASOS A SEGUIR: 
1) Se dibujan los ejes cartesianos
2) Sobre este espacio se grafican las restricciones
3) Se dibuja el funcional (la FO) haciendo Z=0
4) Se busca el último punto de contacto entre la RPF y el funcional. Es decir, desplazamos la FO hasta el límite, donde tenga solo un punto de contacto con la RPF.
La diferencia entre los recursos disponibles y los consumidos, es el exceso o sobrante. Estas son las VARIABLES DE HOLGURA o de EXCESO. Estas se agregan en las restricciones al momento de realizar el grafico para poder representar los recursos no utilizados.
Por ejemplo: 
La línea de ISOUTILIDADES, es aquella donde el valor de Z es igual en todos los puntos. (por ejemplo, cuando hacemos Z=0, esa línea es de isoutilidades, donde el valor de Z es siempre igual a 0)
PUNTO EXTREMO: Para cualquier conjunto convexo S un punto P de S es un punto extremo si para cada segmento rectilíneo que se encuentra completamente en S y que pasa por el punto P, es un punto extremo del segmento rectilíneo.
VERTICE ADYACENTE: analíticamente se reconoce un vértice adyacente ya que al pasar de un vértice al siguiente las variables deben cambiar de estado (pasar de 0 a ≠ 0 y viceversa) de forma paralela.
Por ejemplo para los vértices B y C, las variables x3 y x4 intercambian su estado al pasar de un punto al otro: 
RESTRICCIÓNES REDUNDANTES: son aquellas que no forman parte de los límites del EPF y por lo tanto pueden ser ignoradas sin consecuencias.
IMPOSIBILIDAD: PROGRAMA LINEAL NO FACTIBLE: Ocurre cuando el EPF es NO CONVEXO
ILIMITABILIDAD: POLIGONO NO ACOTADO: Ocurre cuando las restricciones son insuficientes para poder plantear el problema, por lo tanto, si se intenta maximizar el funcional se obtendrá que 
Ahora, si se intenta minimizarlo, se puede obtener un resultado valido para el (en este caso = B)
PROGRAMA LINEAL con SOLUCIONES MULTIPLES
Esto puede ocurrir cuando el punto extremo, es decir, el punto donde el funcional adquiere su valor máximo, es todo punto en un segmento. En este caso el Punto Optimo será dicho segmento: Pop: 
Esto nos permite, al momento de tomar una decisión, de poder elegir qué recurso deseamos utilizar y cuál no, dado que ambos producirán el mismo valor Optimo de Z.
Por ejemplo, podemos observar esto en estos vectores con los valores de las variables en los puntos B y C. ISOUTILIDAD
Este mismo problema, en caso de que fuese una minimización, tendría una única solución.
PROBLEMA DE DEGENERACION: Se plantea cuando ocurre que en un punto se hacen 0 más de n-m variables, siento n el número de variables de decisión y m el número de restricciones.
PROBLEMA DE REGION FACTIBLE QUE NO TOCA EL ORIGEN: en este caso se puede complicar la resolución con el método simplex que comienza en (0,0) generalmente. Por lo quese deberá elegir un punto inicial que se encuentre en el convexo y a la vez re calcular los valores de las variables de la base
TIPOS DE RESTRICCIONES:
ACTIVAS (Obligatorias): Son aquellas donde se han consumido todos sus recursos, es decir, donde sus variables de holgura son = 0
INACTIVAS (No Obligatorias): Son aquellas donde las variables de holgura son ≠ 0
FORMAS
FORA CANONICA: en la forma canónica debe existir una FO (máx. o min.), restricciones y las condiciones de no negatividad. Además no deben existir variables de holgura
FORMA ESTANDAR: En esta forma se exige que la FO se encuentre MAX. Además las restricciones deben estar con la desigualdad <=. Por otra parte TODAS las variable incluidas la de holgura deben tener condición de no negatividad
FO: Z max = Cx
S.a.{ Ax ≤ b
 X ≥ 0}
Z = 
Cualquier forma distinta de esta es EQUIVALENTE y podemos llevarla siempre a la forma estandar.
REGLA 1:
· MAX Cx es equivalente a MIN – Cx
· MIN Cx es equivalente a MAX – Cx
REGLA 2:
· Ax ≤ b es equivalente a -Ax ≥ -b
· Ax ≥ b es equivalente a -Ax ≤ -b
REGLA 3: IGUALDAD EN UNA RESTRICCION
· Ax = b ≡ Ax ≤ b & Ax ≥ b
REGLA 4
· ADICION DE VARIABLE DE HOLGURA:
 Ax ≤ b Ax + y1 = b
· RESTA DE VARIABLE DE EXCESO o SUPERFLUA
Ax ≥ b Ax – y2 = b
REGLA 5:
- VARIABLE NO RESTRINGIDA
x1 no está restringida → x1 = x2 – x3
x1 No restringida (nrs); x2 ≥ 0 y x3 ≥ 0
- VARIABLE NEGATIVA
x1 <= 0 → x1 = - x2 
DEFINICIONES Y TEOREMAS:
VARIABLE NO BASICA: Cuando una variable en el punto analizado es = 0. Esta variable esta fuera de la solución.
CANTIDAD MAXIMA de PUNTOS a EVALUAR: La solución va a estar a lo sumo en un vértice y se tendrán que analizar:
 Cnm
SOLUCION BASICA: Representan vértices producto de la intersección de dos o más restricciones. Pueden ser factibles o no factibles
SOLUCION FACTIBLE: al problema de PL es un vector X = x1,x2,…,xN el cual satisface las ecuaciones de las restricciones y las condiciones de no negatividad
SOLUCION FACTIBLE BASICA para la ecuación es una solución obtenida al hacer n-m variables = 0 y resolver por las ni variables remanentes, siempre que el determinante de los coeficientes de estas m variables no sean cero. Las m variables se llaman VARIABLES BASICAS. Entonces la SFB es aquella donde el vector X tiene no más de m componentes positivas.
SOLUCION FACTIBLE BASICA NO DEGENERADA es una solución factible básica donde el vector X tiene exactamente m componentes positivas.
SOLUCIÓN FACTIBLE BASICA DEGENERADA: es una solución factible básica donde hay menos de m componentes positivas del vector X.
REGION DE FACTIBILIDAD: Es el conjunto de todas las soluciones factibles.
 Una SOLUCION FACTIBLE MAXIMA (PUNTO OPTIMO) es una solución posible que también MAXimiza la FO.
Una función f(x1,x2,…,xN) es una FUNCION LINEAL de (x1,x2,…,xN) si y solo si para algún conjunto de constantes (C1,C2,…,Cn), F(x1,x2,…,xN) = C1x1 + C2x2 + … + Cnxn
 Un problema de PL es un PROBLEMA DE OPTIMIZACION para el cual tratamos de MAX o MIN una función de variables de decisión.
1- La función que se pretende optimizar se llama FO
2- Los valores de las vD deben satisfacer un conjunto de restricciones lineales
3- Hay una restricción de signo para cada variable xi ≥ 0 con i =1,2,…,n
 Una RESTRICCION se considera OBLIGATORIA si el lado izquierdo es = al derecho de la restricción al sustituir los valores óptimos de las vD en la restricción.
Una RESTRICCION se llama NO OBLIGATORIA si el lado izquierdo NO es igual al lado derecho de la restricción al sustituir los valores óptimos de las vD en la restricción.
SOLUCION OPTIMA: Corresponde al conjunto de los valores de las variables de decisión que corresponden al punto optimo. Representan a las mejores decisiones a tomar para el problema
TEOREMAS BASICOS DE LA PROGRAMACIÓN LINEAL
[TEOREMA 1]: El conjunto de todas las soluciones posibles al problema de PL es un conjunto convexo.
[TEOREMA 2]: La FO alcanza un MAX o MIN en un punto extremo del conjunto convexo generado por el conjunto de soluciones posibles al problema de PL. Si alcanza este MIN o MAX en más de un punto extremo, entonces toma el mismo valor para toda combinación convexa de estos puntos particulares.
[TEOREMA 3]: Si puede encontrarse un conjunto de k < m vectores P1, P2, …, Pk que son linealmente independiente y tal que x1P1 + … + xkPk = P0 y todos los xi > 0 el punto x = (x1,x2,…,xk, 0, 0, …, 0) es un punto extremo del polígono convexo de soluciones posibles. En este caso, x es un vector n-dimensional cuyos últimos n-k elementos son 0.
[TEOREMA 4]: Si x=(x1, x2,…,xN) es un punto extremo del convexo, entonces los valores asociados con los xi positivos, forman un conjunto linealmente independiente. De esto surge que al menos m de los xi son positivos.
	{COROLARIO 1}: Con cada punto extremo del convexo se encuentra asociado un conjunto de m vectores linealmente independientes del junto dado p1, p2, …, pn
CONCLUSION: De acuerdo a los teoremas anteriormente nombrados, la solución optima en este método se encontrara sobre, por lo menos, un punto extremo del conjunto convexo, y este punto extremo tendrá un máximo de m variables no nulas.
SIMPLEX
El algoritmo Simplex fue creado por Gorge Datzing en 1947 se trata de un método algebraico, con conceptos geométricos fundamentales, para la resolución de problemas de PL. Consiste en la selección de una solución óptima mediante la generación iterativa de un número finito de soluciones factibles cada una de las cuales produce un nuevo valor de la FO estrictamente mejor que la anterior
Dada la FO: Z = C1x1+ C2x2
Y las restricciones:
a11 x1+ a12x2 + x3 = b1
a21x1 – a22x2 + x4 = b2
a31x1+ a32x2 + x5 = b3
Para empezar con este método, se representa matricialmente los valores de las variables en la primera solución básica factible. Esto es, cuando tanto Z como x1y x2 son = 0. 
Si estos son 0, entonces 
x3 = b1
x4 = b2
x5 = b3
Con esta matriz se puede empezar a trabajar en la tabla correspondiente, agregando las ecuaciones y el funcional
Esta solución estará integrada por las variables cuyos coeficientes integran la submatriz unidad
REGLAS DEL METODO SIMPLEX
1- Se transforma el PL en la forma estándar
2- Se obtiene una Solución básica factible a partir de la forma estándar, esto es, se hace n-m variables iguales a cero y se despejan las m variables que quedan. Esto supone que al hacer las n-m variables = 0, nos proporciona valores únicos para las m variables restantes o, equivalentemente, las columnas de las m variables restantes son linealmente independientes.
3- Se determina si esta solución es optima
4- Si no es optima, se determina qué variable NO básica se tiene que convertir en una variable básica y viceversa, para encontrar una nueva Solución básica factible con un mejor valor de la FO.
5- Se realizan OER de la tabla simplex para obtener la nueva solución básica factible con un mejor valor de la FO.
DEFINICION DE ADYACENCIA:
Para cualquier problema de PL con n variables de decisión genuinas, dos soluciones factibles son adyacentes si comparten n-1 fronteras de decisión.
Frontera de Decisión: Una frontera de decisión es una recta que marca el limite de lo qe permite y no permite la restricción correspondiente que representa. Los diferentes puntos de intersección entre fronteras de decisión representan vértices a evaluar.
Dos SBF son adyacentes si todas menos una de las variables básicas son las mismas 
INTERPRETACION TECNICA-ECONOMICA de TODOS los ELEMENTOS de la TABLA OPTIMA del SIMPLEX
Supongamos que la siguiente es la tabla óptima de un problema
	
	Cj (1)
	8
	6
	0
	0
	Ck (2)
	Xk (3)
	bk (4)
	X1 (5)
	X2
	X3
	X4
	8
	X1
	6
	1
	0
	1/3 
	-1/6
	6
	X2
	18
	0
	1
	-1/6
	1/3
	
	Zj (6)
	156
	8
	6
	5/3
	2/3
	
	
	Zj-cj (7)
	0
	0
	5/3
	2/3
(1) Esta fila nos indica el beneficio que nos otorga cada unidad de xj en el valor del funcional, es decir, cuanto impacta la cantidad de xj en la solución.
(2) Esta columna nos indica el beneficio que nos otorga cada unidad de xK que se encuentra enla solución básica.
(3) Esta columna nos indica qué variable de decisión se encuentre en la base.
(4) Esta columna representa la cantidad de cada variable de decisión que hay en la base.
(5) Estas columnas (x1-x4) nos indican las tasas de sustitución de las variables no básicas con respecto a las básicas. Por ejemplo, si deseo liberar una unidad de x3, deberé dejar de producir 1/3 de unidad de x1 y podre producir a su vez, 1/6 de unidad de x2. 
(6) Esta fila nos muestra el valor del funcional primero y luego nos muestra los costos de oportunidad que resulta de traer una variable a la solución. Esto significa, cuanto se reduce el valor de Z si incrementamos en una unidad esta variable. Como mencionamos en el punto 5) si traemos una unidad de x3 a la solución, se reduce 1/3 la cantidad de x1 producido, y eso significa una disminución de a13 x C1 = 1/3 x 8 = 8/3 y a su vez, un aumento en la producción de x2 que implica un aumento en el funcional de a23 x C2 = -1/6 x 6 = -1, por lo tanto, si incrementamos en una unidad x3, el valor de Z disminuiría en 5/3. A su vez, si se trata de una variable genuina no básica, el valor de Zj nos dará el costo reducido de la variable, es decir, el valor que debería tener el Cj de dicha variable para entrar en la solución.
(7) Esta fila contiene el beneficio o la pérdida neta que resulta de traer una unidad de esta variable a la solución. Si el valor es de la columna perteneciente a una variable de holgura, este valor nos indicara cuanto crecería el valor de Z si incorporásemos una unidad más de este recurso al sistema. (es decir, modificáramos el valor de bj en la restricción). Esto se puede observar por ejemplo, en el hecho de que si incrementásemos b1 en 1, entonces x3 podría incrementarse en uno también, permitiendo que se incremente la producción de x1 y se disminuya la de x2, trayendo un beneficio de 5/3. Este valor se conoce como PRECIO SOMBRA y nos dice también cuanto más se debe estar dispuesto a pagar por una unidad más del recurso en cuestión. Ya que si nos da un beneficio de 5/3, entonces podemos pagar hasta 5/3 más sin reducir el valor del funcional.
CAMBIO DEL VALOR DE Z EN CADA ITERACION
En cada iteración del algoritmo Simplex, Z variara en un Z = -ѳ(Zj – Cj)
Donde Z es la variación del funcional al transformar la base
Ѳ es el valor que toma la variable que será introducida en la base, siempre debe ser no negativo.
(Zj – Cj) corresponde al incremento de beneficio neto provocado por el incremento en 1 unidad de la variable de decisión xj
METODO SIMPLEX para MAXIMIZAR (MIN): Paso a Paso
1- Se plantean la FO y las restricciones en forma estándar
2- Se transforman las desigualdades en igualdades introduciendo las VH. Este paso es necesario, pues las variables de holgura generaran la primera base, que resulta ser una matriz identidad. Y esto genera a su vez el primer punto extremo de la región de factibilidad cuyas coordenadas están dadas por el vector b.
3- Se plantea la tabla SIMPLEX: esta consiste básicamente en una matriz de los coeficientes de las m ecuaciones de restricciones incluyendo las VH. 
aij = coeficientes en la ecuación de restricción i de la vD xj
	
	Cj
	C1
	C2
	0
	0
	
	Ck 
	Xk
	bk
	X1
	X2
	X3
	X4
	Ѳ
	0
	X3
	b1
	a11
	a21
	1
	0
	Ѳ3
	0
	X4
	b2
	a12
	a22
	0
	1
	Ѳ4
	
	Zj
	0
	Z1
	Z2
	Z3
	Z4
	
	
	
	Zj-cj 
	Z1- C1
	Z2- C2
	Z3
	Z4
	
PRIMER TABLA DEL METODO SIMPLEX para un PL de 2 var y 2 restricciones
4- Se selecciona la variable de entrada calculando Zj –Cj. Entra aquel con el valor más negativo (positivo) (esto es una decisión arbitraria, se puede seleccionar cualquier variable con un valor negativo, y el algoritmo Simplex tarde o temprano llegara al optimo)
5- Se selecciona la variable de salida calculando Ѳ = bj / a ij , siendo j la columna de la variable de decisión que entra. Aquel con el valor de Ѳ > 0 más pequeño, será la variable que salga. Ѳ debe ser positivo para que el ingreso de la variable a la solución, incremente el valor de Z.
6- Por combinación lineal se obtiene un nuevo sistema de ecuaciones deseado, con la vD que entra reemplazando a la que sale. s
Para esto se extrae el pivote awv , que es el coeficiente ubicado en la intersección de la fila (w) de la Variable de Salida y la columna (v) de la Variable de Entrada.
· La fila del pivote se divide por este, esto se hace para que el coeficiente de la VE sea 1.
· Los coeficientes de las filas restantes se modifican de acuerdo a:
· aij ‘ = aij - 
7- Con la nueva tabla se repiten los pasos 4, 5 y 6 hasta que no haya ninguna variable que introduzca beneficio (reduzca) al valor del funcional. En ese momento se estará en la Solución Optima. Este paso se conoce como PRUEBA DE OPTIMALIDAD o CRITERIO de OPTIMALIDAD
Z n+1= Z n – ѳn (Zj – Cj)n
CASOS PARTICULARES QUE PUEDEN PRESENTARSE AL REALIZAR EL ALGORITMO SIMPLEX
PL DEGENERADO - CASO DE EMPATE ENTRE VARIABLES DE SALIDA - CONVERGENCIA
Se produce cuando en uno de los vértices se cortan más de 2 vectores y por lo tanto se anulan más de 2 variables, entonces, el numero de variables no nulas en ese extremo no alcanza el valor m.
Por lo que decimos que un PL es degenerado si tiene por lo menos una Solución Básica Factible en la que una variable básica es igual a cero.
 Esto se observa cuando hay 2 o más valores de ѳ iguales al mínimo valor positivo cuando intentamos determinar qué variable saldrá de la solución. Sin importar cuál de las 2 variables seleccionemos, terminaremos en el mismo punto extremo (degenerado) y el valor de Z será el mismo (ya que es el mismo punto). Pero, según cual camino tomemos, puede que tengamos que hacer una (o más, incluso puede generarse un ciclo infinito) tabla simplex, antes de poder salir de dicho punto y pasar a otro extremo más optimo. En este punto corremos el riesgo de que el valor de Z no cambie, siendo el valor de ѳ = 0 para la variable que sale.
Para evitar esto, se realiza lo siguiente:
1- Se dividen todos los valores de cada una de las filas en las que se produjo el empate por el que será su elemento pivote de resultar seleccionada.
2- Los valores de las filas así obtenidas se comparan ordenadamente, valor por valor, de izquierda a derecha. A la primera desigualdad encontrada, aquella con el menor valor será la que se seleccione para que salga de la base. 
Con este procedimiento nos aseguramos que una misma base no aparezca más de una vez durante el proceso de cómputo. 
CUANDO EL PUNTO EXTREMO DEGENERADO ES OPTIMO: no podrá detectarse el Punto optimo en dicho extremo, por lo que deberá redefinirse dicho extremo para que se evidencie que se esta en el optimo. Por lo tanto, cuando un punto extremo es degenerado y optimo, puede encontrarse una base asociada al mismo que ponga de manifiesto esta última condición.
PL NO ACOTADO – INCOMPATIBILIDAD - CASO DE CONVEXO ABIERTO
Un PL no acotado para un problema de maximización se presenta cuando una variable con coeficiente negativo en el renglón (Zj - Cj) tiene un coeficiente no positivo en cada restricción. De forma que el valor de ѳ no es un cociente positivo. Esto nos indica que la variable que entra en la solución puede incrementarse por un valor de ѳ arbitrario. 
Este problema surge de errores al momento de plantear las restricciones, que olvidan restringir alguna de las variables y por lo tanto pueden incrementarse indefinidamente.
 SOLUCIONES MULTIPLES - ALTERNATIVAS
Esto se da cuando existe un valor de (Zj - Cj) nulo en correspondencia con una variable no básica. Esto implicaría que si esta variable entra en la solución, el valor de Z no cambiaria, pero si variarían las variables básicas y por lo tanto se estaría en otro punto extremo. Las soluciones básicas factibles correspondientes a ambos extremos se denominan SOLUCIONES ALTERNATIVAS. Y en caso que esto se presente en correspondencia con el punto óptimo, entonces ambas soluciones son óptimas así como cada punto que se pueda obtener de la combinación lineal entre ellas. 
Dado P1 y P2, los 2 puntos extremos que son Soluciones alternativas, dado un número 0≥ α ≥1 tenemos y dados los vectoresXP1 y XP2 correspondientes a los valores de las vD en cada uno de los Puntos, tenemos:
(1-α) x [XP1] + (α) x [XP2]
Dándole valores a α podemos obtener todas las soluciones alternativas.
Si es posible graficar el PL, este caso se puede observar ya que el funcional tendrá la misma pendiente que una de las restricciones que forman parte de ese punto extremo. Por lo tanto, todos los puntos en el segmento que unen las 2 soluciones alternativas son también una solución óptima para el PL.
TECNICA DE LA BASE ARTIFICIAL:
Esta técnica se utiliza para aquellos PL donde existe al menos una restricción de la forma ≥ o =, donde no podemos generar la matriz identidad con las variables de holgura para poder obtener la primer solución básica factible de inicio. Para suplir la falta de variables de holgura, utilizamos variables artificiales o ficticias que realizan el trabajo de las holguras en las primeras iteraciones y luego son desechadas de forma legítima de la base. 
METODO DE PENALIZACION:
Este método consiste en:
· Para cada restricción i en la que no haya una variable de holgura, se aumenta una VARIABLE ARTIFICIAL µk, para poder formar una solución factible básica de inicio. El valor Ck de esta variable será un valor suficientemente grande . Si se maximiza, este valor será –M y si se minimiza será M. Esta PENALIZACION en el valor del coeficiente es para lograr que la variable sea extraída de la base y que no regrese a la misma. En caso de que al llegar a la tabla óptima alguna variable artificial siga en la base, significa que el problema es NO FACTIBLE.
METODO de 2 FASES:
· Este método es muy similar al anterior, excepto que esta refinado para evitar los problemas de redondeo y exactitud que pueden surgir al utilizar un valor M suficientemente grande contra los valores de los coeficientes de las demás variables que serán pequeños. Entonces, se divide el problema en 2 fases, en la primera encontrándose una solución básica factible de inicio sin las variables artificiales, y en la segunda optimizando el funcional en base a dicha base.
1- Se modifican las restricciones para que el lado derecho sea NO NEGATIVO
2- Se agregan las variables artificiales necesarias luego de pasar las restricciones a igualdades (usando el mismo criterio que en el método de penalización)
3- Se calculará el MINIMO de la función W’ = . Es decir, la suma de todas las variables artificiales.
4- De acuerdo al valor del optimo de W’ vemos que:
· Si W’op > 0 el PL NO tiene solución factible
· Si W’op = 0 y no hay variables artificiales en la base, se continua optimizando sin las columnas de las variables artificiales y con el funcional original en vez de W’.