• Categories
• Programación lineal
• Investigación de operaciones
• Algoritmos
• Conceptos matemáticos
• Física y matemáticas

Citation preview

Guía Práctica para Investigación de Operaciones PROGRAMACIÓN LINEAL Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro Janos von Neuman (1903-1957), quien en 1928 publicó su famoso trabajo Teoría de Juegos. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, discípulo de David Hilbert en Gotinga y, desde 1930, catedrático de la Universidad de Princenton de Estados Unidos, hace que otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina. En 1858 se aplicaron los métodos de la programación lineal a un problema concreto: el cálculo del plan óptimo de transporte de arena de construcción a las obras de edificación de la ciudad de Moscú. En este problema había 10 puntos de partida y 230 de llegada. El plan óptimo de transporte, calculado con el ordenador Strena en 10 días del mes de junio, rebajó un 11% los gastos respecto a los costos previstos. Se ha estimado, de una manera general, que si un país subdesarrollado utilizase los métodos de la programación lineal, su producto interior bruto (PIB) aumentaría entre un 10 y un 15% en tan sólo un año. Definición de Programación lineal: Se llama programación lineal al conjunto de técnicas matemáticas que pretenden resolver la situación siguiente: Optimizar (maximizar o minimizar) una función objetivo, función lineal de varias variables, sujeta a una serie de restricciones, expresadas por inecuaciones lineales. Un problema de programación lineal en dos variables, tiene la siguiente formulación estándar:

Pudiendo cambiarse maximizar por minimizar, y el sentido de las desigualdades. En un problema de programación lineal intervienen:  

La función z = ax + by llamada función objetivo y que es necesario optimizar. En esa expresión x e y son las variables de decisión, mientras que a, b y c son constantes. Las restricciones que deben ser inecuaciones lineales. Su número depende del problema en cuestión. El carácter de desigualdad viene impuesto por las limitaciones, disponibilidades o necesidades, que son: inferiores a … ( < o ); como mínimo de… ( > o ) . Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en cualquiera de los dos sentidos.

Página 31

Guía Práctica para Investigación de Operaciones 

Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se le denomina conjunto (o región) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución. En el apartado siguiente veremos cómo se determina la región factible.



La solución óptima del problema será un par de valores (x0, y0) del conjunto factible que haga que f(x,y) tome el valor máximo o mínimo.

Utilizaremos las siglas PPL para indicar problema de programación lineal

Determinación de la región factible: La solución de un problema de programación lineal, en el supuesto de que exista, debe estar en la región determinada por las distintas desigualdades. Esta recibe el nombre de región factible, y puede estar o no acotada.

Región factible acotada

Región factible no acotada

La región factible incluye o no los lados y los vértices, según que las desigualdades sean en sentido amplio (

o

) o en sentido estricto (< o >).

Si la región factible está acotada, su representación gráfica es un polígono convexo con un número de lados menor o igual que el número de restricciones.

El procedimiento para determinar la región factible es el siguiente: 1) Se resuelve cada inecuación por separado, es decir, se encuentra el semiplano de soluciones de cada una de las inecuaciones.  

Se dibuja la recta asociada a la inecuación. Esta recta divide al plano en dos regiones o semiplanos Para averiguar cuál es la región válida, el procedimiento práctico consiste en elegir un punto, por ejemplo, el (0,0) si la recta no pasa por el origen, y comprobar si las coordenadas satisfacen o no la inecuación. Si lo hacen, la región en la que está ese punto es aquella cuyos puntos verifican la inecuación; en caso contrario, la región válida es la otra.

2) La región factible está formada por la intersección o región común de las soluciones de todas las inecuaciones. Como sucede con los sistemas de ecuaciones lineales, los sistemas de inecuaciones lineales pueden presentar varias opciones respecto a sus soluciones: puede no existir solución, en el caso de que exista el conjunto solución puede ser acotado o no. Veámoslo con un ejemplo:

Página 32

Guía Práctica para Investigación de Operaciones Dibuja la región factible asociada a las restricciones: x+y y

4

y

x

4

Las rectas asociadas son: r : x + y = 4 ;

s : y = 4 , t: y = x

Elegimos el punto P(0,0), que se encuentra en el semiplano situado por debajo de la recta. Introduciendo las coordenadas (0,0) en la inecuación x + y 4, vemos que no la satisface: 0 + 0 = 0 < 4 . Por tanto, el conjunto de soluciones de la inecuación es el semiplano situado por encima de la recta r : x + y = 4 .

La recta t asociada a la restricción pasa por el origen, lo cual significa que si probásemos con el punto P(0,0) no llegaríamos a ninguna conclusión. Elegimos el punto (1,0) y vemos que no satisface la inecuación y x (y = 0 < 1 = x ). Por tanto, el conjunto solución de esta inecuación es el semiplano determinado por la recta t que no incluye al punto (1,0).

Procedemos como en el paso anterior. Las coordenadas (0,0) satisfacen la inecuación y 4 ( 0 4) . Por tanto, el conjunto de soluciones de la inecuación es el semiplano que incluye al punto O.

La región factible está formada por los puntos que cumplen las tres restricciones, es decir, se encuentran en los tres semiplanos anteriores.

Página 33

Guía Práctica para Investigación de Operaciones Método gráfico : Solución Gráfica de un problema de PL Problema 1. La WINDOR GLASS CO produce artículos de vidrio de alta calidad, entre ellos ventanas y puertas de vidrio. Tiene tres plantas. Los marcos y molduras de aluminio se hacen en la planta 1, los de madera en la planta 2; la 3 produce el vidrio y ensambla los productos.

Debido a una reducción de las ganancias, la alta administración ha decidido reorganizar la línea de producción de la compañía. Se descontinuarán varios productos no rentables y se dejará libre una parte de la capacidad de producción para emprender la fabricación de dos productos nuevos que tienen ventas potenciales grandes: – –

Producto 1: una puerta de vidrio de 8 pies con marco de aluminio. Producto 2: una ventana corrediza con marco de madera de 4 pies por 6.

El producto 1 requiere de la capacidad de producción en las plantas 1 y 3 y nada en la planta 2. El producto 2 sólo necesita trabajo en las plantas 2 y 3. La división de comercialización ha concluido que la compañía puede vender todos los productos que se puedan fabricar en las plantas. Sin embargo, como ambos productos competirán por la misma capacidad de producción en la planta 3, no está claro qué mezcla de productos sería la más rentable. Por lo tanto, se ha formado un equipo de IO para estudiar este problema. El grupo comenzó a realizar juntas con la alta administración para identificar los objetivos del estudio y desarrollaron la siguiente definición del problema: Determinar que tasas de producción deben tener los dos productos con el fin de maximizar las utilidades totales, sujetas a las restricciones impuestas por las capacidades de producción limitadas disponibles en las tres plantas. (Cada producto se fabricará en lotes de 20 unidades, de manera que la tasa de producción está definida con el número de lotes que se producen a la semana) Se permite cualquier combinación de tasas de producción que satisfaga estas restricciones, incluso no fabricar uno de los productos y elaborar todo lo que se posible del otro. El equipo de IO también identificó los datos que necesitan reunir: Número de horas de producción disponibles por semana en cada planta para estos nuevos productos. (Casi todo el tiempo de estas plantas estás plantas está comprometido con los productos actuales, lo que limita la capacidad para manufacturar nuevos productos.) Número de horas de fabricación que emplea cada lote producido de cada artículo nuevo en cada una de las plantas.

Página 34

Guía Práctica para Investigación de Operaciones La ganancia por lote de cada producto nuevo. (Se escogió la ganancia por lote producido como una medida adecuada una vez que el equipo llegó a la conclusión de que la ganancia incremental de cada lote adicional producido sería, en esencia, constante, sin importar el número total de lotes producidos. Debido a que no se incurre en costos sustanciales para iniciar la producción y comercialización de estos nuevos productos, la ganancia total de cada uno es aproximadamente la ganancia por lote producido multiplicado por el número de lotes.) La obtención de estimaciones razonables de estas cantidades requirió del apoyo de personal clave en varias unidades de la compañía. El personal de la división de manufactura proporcionó los datos de la primera categoría mencionada. El desarrollo de estimaciones para la segunda categoría requirió un análisis de los ingenieros de manufactura involucrados en el diseño de los procesos de producción para los nuevos artículos. Al analizar los datos de costos obtenidos por estos ingenieros, junto con la decisión sobre los precios de la división de mercadotecnia, el departamento de contabilidad calculó las estimaciones para la tercera categoría. •

La tabla siguiente resume los datos reunidos de la información anterior. Planta

Tiempo de producción por Lotes, Horas

Tiempo de producción disponible a la semana, horas

Producto 1 2 3 Ganancias por lote

1 1 0 3 $ 3000

2 0 2 2 $5000

4 12 18

El primer paso para la resolución del problema de programación es la definición de las variables de decisión en este caso tenemos dos tipos de producto: 1. Variables de decisión

x1  Número de lotes del producto1 fabricado por semana x2  Número de lotes del producto2 fabricado por semana

La función objetivo es lo que queremos optimizar (minimizar o maximizar), por ello está compuesta por los costos de cada producto, los cuales van acompañado por las variables de decisión en el caso de la minimización y de utilidades y variables de decisión en el caso de la maximización. En este problema en particular lo que desea la empresa es encontrar la solución que maximice sus utilidades. Colocamos 3 en lugar de 3000 y 5 en lugar de 5000, para trabajar en unidades mas pequeñas; pero al final representa miles de dólares. 2. Función Objetivo Maximizar Z  f ( x1 , x2 )  3x1  5x2 Página 35

Guía Práctica para Investigación de Operaciones

En este caso las restricciones son las limitantes que tiene la empresa para producir el producto1 y el producto2. Tenemos 3 restricciones bien definidas, las cuales. Cabe señalar que las restricciones de no negatividad, siempre es necesario incluirlas, ya que en las respuestas no pueden resultar valores menores que cero, sino la solución del problema no tendría ningún sentido. 3. Restricciones

x1  4 Horas disponibles en la planta 1, para producir lotes del producto 1

2 x2  12 Horas disponibles en la planta 2, para producir lotes del producto 2

3x1  2 x2  18 Horas disponibles en la planta 3, para producir lotes del producto 1 y producto 2

x1  0 x2  0

Restricciones de no negatividad

4. Formule el modelo matemático del PPL. Ahora se puede formular el modelo matemático del problema para lo cual definimos la función objetivo a maximizar, sujeta a las restricciones que se señalan.

Máx.

Z  3x1  5 x2 S.a

x1  4 2 x2  12 3 x1  2 x2  18 x1  0 x2  0

Página 36

Guía Práctica para Investigación de Operaciones

5. Con la forma estándar del modelo, graficamos para encontrar la región factible.

Si hacemos uso del WinQSB los pasos ha seguir son los siguientes 1. 2. 3. 4. 5. 6.

Nos vamos a INICIO. Elegimos todos los programas Damos clic derecho izquierdo en WinQSB y elegimos con un clic izquierdo la herramienta Goal Programming. Al cargar el programa nos vamos a archivo y damos clic en nuevo. Aparecerá una nueva ventana que nos muestra:  Título del problema: el título es totalmente opcional cada uno le pueda dar el nombre que desee.  Número de Goal, es decir número de metas. En este caso queremos encontrar un solo óptimo por lo cual, la meta es 1.  Número de variables: las variables de decisión, no son más que las que definimos al inicio, son dos. Entonces escribimos 2.  Número de restricciones: también ya las hemos definido. Son tres restricciones. El programa ya incluye las restricciones de no negatividad, por lo que solamente escribimos las otras faltantes 3.  El programa trae la opción de minimización o maximización. Como el nuestro es un problema de maximización le damos entonces clic en maximización.  Damos clic en aceptar y nos aparecerá una nueva ventana en la cual veremos en la primera columna C1, C2, C3; estas son las restricciones del problema. Aparece además en la primer fila la letra Z, allí colocaremos los coeficientes de las variables de decisión de la función objetivo.  Para tener una mejor interpretación es necesario que cambiamos los nombres a las restricciones e incluso a las variables de decisión, para ello nos vamos a Edición; elegimos la opción constraint name y podemos cambiarle el nombre a las restricciones de igual forma, podemos elegir la opción variable name y definir bien quien es x1 y x2.  Cuando hemos introducido los coeficientes de la función objetivo y de las restricciones, entonces podemos irnos a la opción Solve and Analize y elegimos Graphic Method, dado que nuestra intención es resolverlo por el método gráfico.  Al hacer esto el programa nos mandará a una nueva ventana, la cual nos indica que variable conforma el eje de las X y cual conforma el eje de las Y, le damos aceptar y ante nosotros aparecerá un gráfico como el que se muestra a continuación.

Página 37

Guía Práctica para Investigación de Operaciones

(2,6) (0,6)

(4,3)

Región Factible

(0,0)

(4,0)

Los pares ordenados que han sido seleccionados son los que acotan la llamada Región Factible, son las posibles soluciones al problema y son esenciales para descubrir cual es el óptimo. El siguiente paso es evaluar cada uno de estos puntos y encontrar el que maximice nuestras utilidades al mayor porcentaje posible. 6. Soluciones factibles. Valores permitidos de la región factible (0,0)

x1 , x2 

(0,6) (2,6) (4,3) (4,0)

Función Objetivo

Z Z Z Z Z

Z  3x1  5x2  3(0)  5(0)   3(0)  5(6)   3(2)  5(6)   3(4)  5(3)   3(4)  5(0) 

Soluciones factibles (FEV) 0 30 36 27 12

Después de haber analizado las soluciones factibles vemos que la que nos da la máxima utilidad es el punto (2,6) Esto se interpreta de la siguiente manera: 7. Soluciones óptimas: Para obtener la máxima utilidad que es de $36,000 tendremos que producir dos lotes del producto 1 y 6 lotes del producto 2.

Página 38

Guía Práctica para Investigación de Operaciones Problema 2. Rulisa fabrica masa para pasteles de tipo I y II. La de tipo I la vende a 5 euros el kilo, gastando 1 euro en ingredientes y 2 en mano de obra. La de tipo II se vende a 3 euros y cuestan 1 euro, tanto los ingredientes como el trabajo. Para hacer las masas se necesitan dos tipos de actividades: amasado y horneado. Rulisa dispone de 18 horas de amasado y 12 de horneado a la semana. La masa de tipo I necesita 2 horas de amasado Y 3 de horneado, mientras que la de tipo II, necesita 3 de amasado y 1 de horneado. Si la cantidad de masa que se puede vender es ilimitada, optimizar los beneficios semanales de Rulisa. Análisis del problema •

Identifiquemos los datos que necesitamos para la para definir el modelo: –

Número de horas disponibles para producción, por semana. (18 para amasado y 12 para horneado)

–

Número de horas que requiere cada tipo de masa (tipo I y II) en amasado y horneado.

–

La ganancia por cada producto (precio de venta - costos de producción) de cada uno.

La tabla siguiente resume los datos reunidos. Actividades

Tiempo de producción por producto, horas Tipo de masa I

Amasado Horneado Ganancias Por Producto

II 2 3 €2

3 1 €1

Tiempo de producción disponible a la semana, horas 18 12

Para lograr una mejor solución del problema definiremos nuestras variables de decisión, las cuales son: 1. Variables de decisión

x1  Kilogramos de masa I a fabricar semanalmente.

x2  Kilogramos de masa II a fabricar semanalmente.

Página 39

Guía Práctica para Investigación de Operaciones En este caso la función objetivo estará compuesta por la ganancia obtenida por cada tipo de masa y por las variables de decisión. El problema que estamos resolviendo es un problema de maximización. 2. Función Objetivo Maximizar

z  f ( x1 , x2 )  2 x1  x2

Dado que este producto requiere de dos operaciones fundamentales (Amasado, Horneado) las restricciones estarán dadas por la capacidad en horas semanales para estas actividades. Además colocaremos la restricción de no negatividad. 3. Restricciones

2 x1  3x2  18 3x1x2  12

x1  0 x2  0

Tiempo máximo de amasado permitido Tiempo máximo de horneado permitido

Restricciones de no negatividad

4. Ahora se puede formular el modelo matemático del problema para lo cual definimos la función objetivo a maximizar, sujeta a las restricciones que se señalaron anteriormente. Maximizar z  2 x1  x2 S. a

2 x1  3x2  18 3x1x2  12 5. Con la forma estándar del modelo, graficamos para encontrar la región factible.

x1  0

x 0

Para graficar la región factible 2es necesario que conozcamos los puntos por donde pasan las diferentes rectas por lo que hacemos uso de el método de intercepto. Aunque existen otros

Página 40

Guía Práctica para Investigación de Operaciones formas de resolver sistemas de ecuaciones haremos uso de este por considerarlo más sencillo de utilizar. Primero cambiamos el signo  por el =. Elegimos de las ecuaciones.

2 x1  3 x2  18

x2  0

x1  0

2 x1  3(0)  18

2(0)  3 x2  18

x1  18 / 2

x2  18 / 3

x1  9

x2  6 Punto1 (0,6) Punto2 (9,0) este punto queda descartado dado que no es uno de los vértices de la región factible

3 x1  x2  12

x2  0

x1  0

3 x1  0  12

3(0)  x2  12

x1  12 / 3

x2  12

x1  4

Punto3 (0,12) Punto (4,0)

Descartamos este punto dado que No forma parte de la región Factible.

Para encontrar la intercepción de las rectas 2 x1  3x2  18 y 3x1  x2  12 usamos el método de sustitución. Veámoslo a continuación.

2 x1  3 x2  18  3 x1  x2  12 2 x1  3(12  3 x1 )  18 2 x1  9 x1  36  18  7 x1  18 x1  18 7 x2  30 7

Dado que no todos los puntos son parte de la región factible, podemos decir que los vértices de la región factible son:

Página 41

Guía Práctica para Investigación de Operaciones

3x1  x2  12

(0,6) (18/7,30/7)

2 x1  3x2  18

(4,0)

(0,0)

Para encontrar la solución óptima es necesario que evaluemos todos los valores de los vértices en la función objetivo. 6. Soluciones factibles.

Valores permitidos de la región factible (0,0)

x1 , x2 

(0,6) (18/7, 30/7) (4,0)

Función Objetivo

Z Z Z Z

Z  2 x1  x2  2(0)  0   2(0)  6   2(18 / 7)  30 / 7   2(4)  0 

Soluciones factibles (FEV) 0 6 66/7 8

La solución óptima se puede analizar de la siguiente manera. 7. Soluciones óptimas: Para alcanzar la máxima utilidad es necesario que la empresa produzca 18/7 kg de masa de tipo I y 30/7 Kg de masa de tipo II, para alcanzar una utilidad máxima de 66/7 de euros.

Página 42

Guía Práctica para Investigación de Operaciones

GUÍA PRÁCTICA # 2 Solución Gráfica de PPL Unidad 2: Programación lineal Contenidos: • •

Construcción del modelo de programación lineal. Solución gráfica del problema bidimensional

Objetivos: A l finalizar la práctica el estudiante adquiera las siguientes habilidades:    

Resolver problemas de programación lineal con dos y tres restricciones a través del Método Gráfico. Graficar la región de factibilidad en un sistema de coordenadas, haciendo uso de las restricciones del problema de programación lineal. Hacer uso del IOR Tutoríal para encontrar la región de factibilidad del problema de programación lineal. Encontrar la solución al problema de programación lineal de dos y tres restricciones.

I.

Resuelva los siguientes problemas por el método grafico.

Problema 1: La compañía INTEL produce dos dispositivos para computadoras, (producto 1 y producto 2) y requiere partes de metal y componentes eléctricos. La administración desea determinar cuantas unidades de cada producto fabricar para maximizar la ganancia. Por cada unidad del producto 1 se requiere 1 unidad de partes de metal y 2 unidades de componentes eléctricos. Por cada unidad del producto 2 se necesitan 3 unidades de partes de metal y 2 unidades de componentes eléctricos. La compañía tiene 200 unidades de partes de metal y 300 componentes eléctricos. Cada unidad del producto 1 da una ganancia de $ 2 y cada unidad del producto 2 da una ganancia de $ 3.00 a) formule un modelo de programación lineal. b) Utilice el método grafico para resolver este modelo. ¿Cuál es la ganancia total que resulta?

Materiales

Unidades de Material para cada Total de unidades dispositivo disponibles de cada material Producto 1 Producto 2

Ganancias por unidad Página 43

Guía Práctica para Investigación de Operaciones

1. Variables de decisión

2. Función Objetivo

3. Restricciones

4. Formule el modelo matemático del PPL. Ahora se puede formular el modelo matemático del problema para lo cual definimos la función objetivo a maximizar, sujeta a las restricciones que se señalan.

Forma estándar del modelo:

5. Con la forma estándar del modelo, graficamos para encontrar la región factible.

Página 44

Guía Práctica para Investigación de Operaciones

6. Soluciones factibles. Valores permitidos x1 , x 2  de la región factible

Función Objetivo

Soluciones factibles (FEV)

7. Soluciones óptimas:

Problema 2: Una fábrica de bombones tiene almacenados 500 Kg.. de chocolate, 100 Kg.. de almendras y 85 Kg.. de frutas. Produce dos tipos de cajas: las de tipo A contienen 3 Kg. de chocolote, 1 Kg. de almendras y 1 Kg. de frutas; la de tipo B contiene 2 Kg. de chocolate, 1,5 Kg. de almendras y 1 Kg. de frutas. Los precios de las cajas de tipo A y B son 13 y 13,50 €, respectivamente. ¿Cuántas cajas de cada tipo debe fabricar para maximizar sus ventas?

Página 45

Guía Práctica para Investigación de Operaciones Caja tipo A

Caja tipo B

Disponibles

Chocolate Almendras Frutas Precio en euros

1. Variables de decision

2. Función Objetivo

Página 46

Guía Práctica para Investigación de Operaciones Restricciones

3. Formule el modelo matemático del PPL. Ahora se puede formular el modelo matemático del problema para lo cual definimos la función objetivo a maximizar, sujeta a las restricciones que se señalan.

Forma estándar del modelo:

4. Con la forma estándar del modelo, graficamos para encontrar la región factible.

Página 47

Guía Práctica para Investigación de Operaciones 5. Soluciones factibles. Valores permitidos x1 , x 2  de la región factible

Función Objetivo

Soluciones factibles (FEV)

6. Soluciones óptimas:

Problema 3: Un laboratorio de Cómputos, almacena, al menos 300 Computadoras de un tamaño y 400 de un segundo tamaño. Se ha decidido que el número total de computadoras almacenadas no debe exceder de 1200. Determine las cantidades posibles de estos dos tipos de computadoras que pueden almacenarse. Restricciones

Tipo de Computadoras Computadora 1 Computadora 2

Total Computadoras

Tipos de Computadoras

1. Variables de decisión

2. Función Objetivo

3. Restricciones

Página 48

Guía Práctica para Investigación de Operaciones 4. Formule el modelo matemático del PPL. Ahora se puede formular el modelo matemático del problema para lo cual definimos la función objetivo a maximizar, sujeta a las restricciones que se señalan. Forma estándar del modelo:

5. Con la forma estándar del modelo, graficamos para encontrar la región factible.

6. Soluciones factibles. Valores permitidos x1 , x 2  de la región factible

Función Objetivo

Soluciones factibles (FEV)

7. Soluciones óptimas:

Página 49

Guía Práctica para Investigación de Operaciones El Método Simplex Para la solución de un problema de PL Para resolver los problemas de PL se utilizan varios Algoritmos. El más antiguo y más utilizado sigue siendo el Algoritmo del Simplex debido a Dantzig. La solución de los problemas de programación lineal parte de dos teoremas fundamentales:  El conjunto factible de un problema de PL puede representarse mediante un poliedro convexo.  Si un PL tiene solución óptima y finita ésta se encuentra en uno de los vértices del poliedro convexo. De ellos se deduce que: Puesto que el número de vértices de un poliedro factible es finito, el número de posibles soluciones de un PL también es finito. Esto sugiere, inicialmente, un algoritmo para calcular la solución óptima: Calcular el valor de la función objetivo en cada vértice del conjunto factible y escoger el mejor. Sin embargo, el número de vértices de un conjunto factible es:

m  n (m  n)!    m  m! (m  n - m)! m = número de restricciones n =número de variables Ejemplo: Sí m=3;

y

n=2; entonces el número de Vértices=10

El concepto de vértice es de naturaleza geométrica y es poco adecuado para construir un algoritmo utilizable por ordenadores. Conceptos importantes: Variable básica: Una de las variables restantes, diferentes a las no-básicas, de un programa lineal en forma estándar (igual en número al total de restricciones de igualdad) Variable no básica: conjunto seleccionado de variables de un programa lineal en forma estándar (en número igual al total de variables menos el número de restricciones de igualdad) cuyos valores se toman como cero. Forma estándar: Una forma particular de un problema de programación lineal en el que la función objetivo debe ser maximizada; solamente existen restricciones de igualdad y todos los lados derechos de las variables son no negativos

Página 50