• Author / Uploaded
• Hamer Giraldo

• Categories
• Programación lineal
• Optimización matemática
• Física y matemáticas
• Matemática
• Áreas de la informática

Citation preview

UNIVERSIDAD DE GUAYAQUIL FACULTAD DE CIENCIAS MATEMÁTICAS Y FÍSICAS CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES Integrantes:

 Giraldo Marin Hamer  Martínez vera Jorge  Serrano Gomez Gabriela

Curso: ISI-S-MA-5-2

Docente: Ing. Cevallos Torres Lorenzo Materia: Investigación de operaciones Año Lectivo: 2017 – 2018 (II Ciclo)

Contenido El arte de programar en R: un lenguaje para la estadística .......................................................... 3 1.

Historia de R y S ........................................................................................................... 3

Guía Básica de instalación del R y el R-commander en Windows ................................................ 5 1.

Instalación R ...................................................................................................................... 5

Método gráfico ............................................................................................................................ 11 La función objetivo lineal ........................................................................................................ 11 Problema de transporte o distribución ....................................................................................... 13 Función objetivo ...................................................................................................................... 15 Restricciones en oferta............................................................................................................ 15 Restricciones en demanda ...................................................................................................... 15 Ejemplo: .............................................................................................................................. 15 El Problema ............................................................................................................................. 15 Solución mediante Programación Lineal ................................................................................. 16 Método de la esquina noroeste .............................................................................................. 21 Método Vogel.......................................................................................................................... 22 Método del costo mínimo ....................................................................................................... 22 Método simplex .......................................................................................................................... 23 Presentación del Método Simplex .......................................................................................... 23 Construcción de la tabla simplex ............................................................................................ 24 Método dual simplex .................................................................................................................. 26 Macro Método Simplex ............................................................................................................... 29 Bibliografía .................................................................................................................................. 29

2

El arte de programar en R: un lenguaje para la estadística Empezaremos diciendo que R es un lenguaje de programación interpretado, de distribución libre, bajo Licencia GNU, y se mantiene en un ambiente para el cómputo estadístico y gráfico. Este software corre en distintas plataformas Linux, Windows, MacOS, e incluso en PlayStation 3. El término ambiente pretende caracterizarlo como un sistema totalmente planificado y coherente, en lugar de una acumulación gradual de herramientas muy específicas y poco flexibles, como suele ser con otro software de análisis de datos. El hecho que R sea un lenguaje y un sistema es porque forma parte de la filosofía de creación1, como lo explica John Chambers (Chambers and Hastie [1991]), cito: “Buscamos que los usuarios puedan iniciar en un entorno interactivo, en el que no se vean, conscientemente, a ellos mismos como programadores. Conforme sus necesidades sean más claras y su complejidad se incremente, deberían gradualmente poder profundizar en la programación, es cuando los aspectos del lenguaje y el sistema se vuelven más importantes.” Por esta razón, en lugar de pensar de R como un sistema estadístico, es preferible verlo como un ambiente en el que se aplican técnicas estadísticas. Por ejemplo, en este libro nos inclinaremos hacia el lado de la programación (lenguaje) más que tocar los aspectos estadísticos. Esto con la finalidad de ampliar la gamma de aplicaciones en el tratamiento de datos. 1. Historia de R y S R fue creado en 1992 en Nueva Zelanda por Ross Ihaka y Robert Gentleman (Ihaka [1998]). La intención inicial con R, era hacer un lenguaje didáctico, para ser utilizado en el curso de Introducción a la Estadística de la Universidad de Nueva Zelanda. Para ello decidieron adoptar la sintaxis del lenguaje S desarrollado por Bell Laboratories. Como consecuencia, la sintaxis es similar al lenguaje S, pero la semántica, que aparentemente es parecida a la de S, en realidad es sensiblemente diferente, sobre todo en los detalles un poco más profundos de la programación.

3

Formato del código en el texto

Con el propósito de facilitar la lectura del presente texto, el código del lenguaje se diferencia en párrafos especiales, que han sido construidos con la ayuda del software knitr, gentilmente creado por Xie [2013]2. A continuación, se muestra un fragmento de código con las explicaciones correspondientes.

Figura 1 La fuente de su trabajo se puede encontrar en http://yihui.name/knitr/ y en http://cran.rproject.org/web/packages/knitr/index.html.

4

Guía Básica de instalación del R y el R-commander en Windows 1. Instalación R Para la instalación del programa R y del paquete R-Commander, con su navegador abra la página www.r-project.org. Marque el enlace Download R como se ilustra.

Figura 2

Una vez abierta la página, elija el enlace de españa http://cran.es.rproject.org/. Se visualizará la página The Comprehensive R Archive Network, como se muestra a continuación, donde debe elegir el sistema operativo adecuado.

Figura 3

5

Para los usuarios de Windows, una vez elegida la opción Windows, se abrirá una página con enlaces a los dos directorios principales de la distribución de R, elija base. En la nueva página, como lo muestra la figura a continuación, se le presentará la última versión disponible de R (en el momento de la redacción de este texto, se trata de la 2.12.0).

Figura 4

Completada la descarga, ejecute el archivo R-2.12.0-win32.exe. Después de haber elegido el idioma se abrirá la pantalla de inicio de instalación, como se muestra en la figura

Figura 5

Continuar la instalación haciendo los cambios que se exponen a continuación.

6

En la instalación el siga los pasos sin modificar, hasta la quita pantalla cuando se pregunta si deseamos establecer opciones de configuración, se escoge Si.

Figura 6

También para poder utilizar el R-Commander se debe marcar la opción SDI en la sexta pantalla, como se muestra a continuación.

Figura 7

El último cambio que se hará será en la pantalla Acceso a Internet, donde se aconseja marcar la casilla Internet 2.

7

Figura 8

Luego siga la instalación hasta que el programa haya completado la instalación de R. Instalación R-Commander Una vez terminada la instalación del programa R, ejecútelo, el programa se abrirá con una ventana como se muestra, esta ventana se conoce como la consola de R, donde se tiene que escribir los comandos.

Figura 9

8

Para instalar el paquete R-Commander, asegurándose de tener activada una conexión a Internet. Seleccionar en la barra de menús Paquetes>Instalar paquete(s)

Figura 10

Tendría que abrirse entonces una ventana con todos los posibles espejos (CRAN mirror), como en la próxima figura de la izquierda, donde seleccionamos el espejo de Madrid. Una vez elegido el espejo, se abrirá otra ventana con los paquetes descargables desde el mismo, como se ilustra en la próxima figura de la derecha. Desplazándose hacia abajo se encontrarán los paquetes de interés: se trata de marcar todos los paquetes que comiencen con Rcmdr

Figura 11

9

El programa R empezará la instalación de los paquetes, también instalará otros que Rcommander necesita para su funcionamiento. Al detenerse la instalación volverá a mostrar la pantalla de la consola. Para arrancar el R-Commander, seleccione otra vez el menú Paquetes>Cargar paquete

Figura 12

Nuevamente se visualizarse una lista de paquetes, marcar Rcmdr y cárguelo.

Figura 13

Finalmente se abrirá la ventana del programa R-Commander,

10

Figura 14

Ahora, se tienen instalados tanto el R como el r-commander para trabajar con ellos. Cada vez que entremos en R se tiene que cargar nuevamente el Rcommander, sólo cargar no instalar. Se puede hacer por los menú y escribiendo en la consola > library(Rcmdr).

Método gráfico El método gráfico se utiliza para la solución de problemas de PL, representando geométricamente a las restricciones y el objetivo. El modelo se puede resolver en forma gráfica si tiene dos o tres variables. Para modelos con más variables, el método gráfico es impráctico o imposible

La función objetivo lineal La expresión matemática del objetivo se llama función objetivo y la meta debe ser maximizar o minimizar esa expresión. La función objetivo lineal se puede representar de las siguientes maneras:

𝑧 = 𝑐1 𝑥1 + 𝐶2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 o utilizando la notación de sumatorias 𝑛

𝑧 = ∑ ∑ 𝑐𝑗 𝑥𝑗 𝑗=1

11

Donde: 

𝑧 = Función objetivo lineal.



𝑐𝑗 = Precio neto o costo unitario, según sea el modelo.



𝑥𝑗 = Actividad o proceso.

El objetivo puede ser la maximización de algunas variables de ingreso que pueden variar desde los ingresos netos o brutos, dependiendo según se estructure el modelo. La programación lineal puede también aplicarse a los problemas de minimización de costos y estos programas parten de un diferente conjunto de criterios para su optimización. Los coeficientes 𝑐1 , 𝑐2 … , 𝑐𝑛 son los coeficientes de costo (conocidos) o de ingresos,

según el

tipo de problema que

estemos

resolviendo.

Por otra

parte, 𝑥1 , 𝑥2 … , 𝑥𝑛 son las variables de decisión (variables, o niveles de actividad) que deben determinarse de tal manera que se alcance el objetivo dentro de las restricciones que enfrenta el problema. Un conjunto de restricciones o desigualdades lineales Las restricciones, expresadas mediante desigualdades lineales, están compuestas por los coeficientes técnicos (𝐴𝑖𝑗 ), las actividades o procesos (𝑥𝑛 ), las cuales también se tomaron en cuenta en la función objetivo y además los niveles o limitaciones (𝐵𝑖 ). El conjunto de restricciones se expresa de la siguiente manera:

𝐴11 𝑥1 + 𝐴12 𝑥2 + ⋯ + 𝐴1𝑛 𝑥𝑛 ≥ 𝐵1 𝐴21 𝑥1 + 𝐴22 𝑥2 + ⋯ + 𝐴2𝑚 𝑥𝑛 ≤ 𝐵2 …. …. 𝐴𝑚1 𝑥1 + 𝐴𝑚2 𝑥2 + ⋯ + 𝐴𝑚𝑛 𝑥𝑛 = 𝐵𝑚 𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0 Según Beneke y Winterboer (1984: 25), hay tres tipos básicos de restricciones: de “mayor que” (≥), de “menor que” (≤) o de igualdad (=), y estas pueden ser clasificadas en razón a su naturaleza:

12

Problema de transporte o distribución El problema de transporte o distribución es un problema de redes especial en programación lineal (Lopez, 2016) se refiere a que se funda en la necesidad de llevar unidades de un punto específico llamado Fuente u Origen hacia otro punto específico llamada Destino. Los principales objetivos de un modelo de transporte son la satisfacción de todos los requerimientos establecidos por los destinos y claro está la minimización de los costos relacionados con el plan determinado por las rutas escogidas. El contexto en el que se aplica el modelo de transporte es amplio y puede generar soluciones atinentes al área de operaciones, inventario y asignación de elementos. El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante programación lineal común, sin embargo su estructura permite la creación de múltiples alternativas de solución tales como la estructura de asignación o los métodos heurísticos más populares como Vogel, Esquina Noroeste o Mínimos Costos.

(-Cun-, 2011) El objetivo primordial del modelo de transporte es buscar minimizar los costos de envió de la cantidad de elementos que se enviaran de cada fuente a cada destino, tal que se minimice el costo del transporte total de los envíos. Por otra parte, el modelo de transporte establece un método que regula el transporte de mercancías de varias fuentes a varios destinos. Los elementos del modelo son: 1.

Indica el nivel de oferta que tiene cada fuente y la cantidad de demanda en cada

destino. 2.

Por lo contrario el costo de transporte unitario de la mercancía enviado por el

proveedor a cada destino. Como solo existe una mercancía y el destino puede recoger su demanda varias fuentes (proveedores).

(Castro, 2011) Es una técnica cuantitativa creada para minimizar los costos asociados a la distribución de un bien o servicio desde diferentes orígenes hasta diferentes destinos. Las condiciones de linealidad están Presentes, como en cualquier técnica de programación lineal.

13

Las características que hacen del Modelo Lineal de Transporte un modelo de programación lineal especial son: a) Los coeficientes de las variables, en las restricciones, son uno o cero. b) Las cantidades demandadas deben ser iguales a las cantidades ofrecidas para poder solucionar el modelo.

MODELO MATEMATICOS DEL PROBLEMA DE TRANSPORTE O DISTRIBUCION

VARIABLES DE DESICION Xi,j= Unidades a enviar desde la fuente i-ésima (i=1,...,m) al destino j-ésimo (j=1,...,n) Ci,j= Costo de enviar una unidad desde la fuente i-ésima (i=1,.,m) al destino j-ésimo (j=1,.,n) ai= Disponibilidad (oferta) en unidades, de la fuente i-ésima (i=1,...,m) bj= Requerimiento (demanda) en unidades, del destino j-ésimo (j=1,...,n)

14

Función objetivo Minimizar 𝑍 = 𝐶1,1𝑋1,1+. . +𝐶1, 𝑗𝑋1, 𝑗 +...+ C1,nX1,n +...+ Ci,1Xi,1 +...+ Ci,jXi,j +...+ Ci,nXi,n +...+Cm,1Xm,1 +...+ Cm,jXm,j+...+ Cm,nXm,n

Restricciones en oferta

𝑋_11 + 𝑋_12 ≤ 𝑂_1 𝑋_21 + 𝑋_22 ≤ 𝑂_2 𝑋_31 + 𝑋_32 ≤ 𝑂_3 Restricciones en demanda

𝑋11 + 𝑋21 + 𝑋31 ≤ 𝐷1 1𝑋12 + 𝑋22 + 𝑋32 ≤ 𝐷2 Los problemas de transporte o distribución son uno de los más aplicados en la economía actual, dejando como es de prever múltiples casos de éxito a escala global que estimulan la aprehensión de los mismos. (Lopez, 2016). Ejemplo:

El Problema Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente. Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

CALI

BOGOTA

MEDELLIN

BARRANQUILLA

PLANTA 1

5

2

7

3

PLANTA 2

3

6

6

1

PLANTA 3

6

1

2

4

PLANTA 4

4

3

6

6

TABLA #1

15

Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.

Solución mediante Programación Lineal La solución de (Lopez, 2016) dice que el modelo básico de transporte es el modelo en el cual la cantidad ofertada es igual a la cantidad demandada, como es el caso de este ejercicio, sin embargo trasladar esta suposición a la realidad es casi imposible por lo cual hace falta crear orígenes y/o destinos ficticios con el excedente de oferta y/o demanda. Como ya lo hemos planteado en módulos anteriores el primer paso corresponde a la definición de las variables, regularmente se le denomina a las variables de manera algebraica Xi,j donde i simboliza a la fuente y j simboliza al destino. En este caso i define el conjunto {Planta 1, Planta 2, Planta 3 y Planta 4}, y j define el conjunto {Cali, Bogotá, Medellín y Barranquilla}. Sin embargo, es práctico renombrar cada fuente y destino por un número respectivo, por ende, la variable X1,2 corresponde a la cantidad de millones de KW enviados diariamente de la Planta 1 a la ciudad de Bogotá.

i

Xij

j

Planta 1

Cali

Planta 2

Bogotá

Planta 3

Medellín

Planta 4

Barranquilla

GRAFICA 1

El segundo paso corresponde a la formulación de las restricciones de oferta y demanda, cuya cantidad se encuentra determinada por el factor entre fuentes y destinos, en este caso 16 restricciones.

16

Restricciones de oferta o disponibilidad, las cuales son de signo ≤:

𝑋11 + 𝑋12 + 𝑋13 + 𝑋14 ≤ 80 𝑋21 + 𝑋22 + 𝑋23 + 𝑋24 ≤ 30 𝑋31 + 𝑋32 + 𝑋33 + 𝑋34 ≤ 60 𝑋41 + 𝑋42 + 𝑋43 + 𝑋44 ≤ 45

Restricciones de demanda, las cuales son de signo ≥:

𝑋11 + 𝑋12 + 𝑋13 + 𝑋14 ≤ 70 𝑋21 + 𝑋22 + 𝑋23 + 𝑋24 ≤ 40 𝑋31 + 𝑋32 + 𝑋33 + 𝑋34 ≤ 70 𝑋41 + 𝑋42 + 𝑋43 + 𝑋44 ≤ 35 Luego se procede a formular la función objetivo, en la cual se relaciona el costo correspondiente a cada ruta.

𝒁𝑴𝑰𝑵 = 5𝑋11 + 2𝑋12 + 7𝑋13 + 3𝑋14 + 3𝑋21 + 6𝑋22 + 6𝑋23 + 1𝑋24 + 6𝑋31 + 1𝑋32 + 2𝑋33 + 4𝑋34 + 4𝑋41 + 3𝑋42 + 6𝑋43 + 6𝑋44

17

Aquí están los resultados:

Variable de

Actividad de la

Decisión

Variable

𝑋11

25

5

125

𝑋12

40

2

80

𝑋13

10

7

70

𝑋14

5

3

15

𝑋21

0

3

0

𝑋22

0

6

0

𝑋23

0

6

0

𝑋24

30

1

30

𝑋31

0

6

0

𝑋32

0

1

0

𝑋33

60

2

120

𝑋34

0

4

0

𝑋41

45

4

180

𝑋42

0

3

0

𝑋43

0

6

0

𝑋44

0

6

0

TOTAL

Costo por Unidad

Contribución Total

620

Tabla #2

18

i

Xij

j

Planta 1

Cali

Planta 2

Bogotá

Planta 3

Medellín

Planta 4

Barranquilla

GRAFICA 2

Este problema presenta una solución óptima alternativa, aquí los resultados.

Variable de

Actividad de la

Decisión

Variable

𝑋11

0

5

0

𝑋12

40

2

80

𝑋13

10

7

70

𝑋14

30

3

90

𝑋21

25

3

75

𝑋22

0

6

0

𝑋23

0

6

0

𝑋24

5

1

5

𝑋31

0

6

0

𝑋32

0

1

0

𝑋33

60

2

120

𝑋34

0

4

0

𝑋41

45

4

180

𝑋42

0

3

0

Costo por Unidad

Contribución Total

19

𝑋43

0

6

0

𝑋44

0

6

0

TOTAL

620

Tabla #3: Los análisis de dualidad y sensibilidad en los modelos de transporte resultan ser bastante interesantes, pues pueden llegar a determinar aumentos de capacidad en las fuentes si el precio sombra de las rutas en relación a ellas lo justifica

DESDE

CADENA 1

CADENA 2

CADENA 3

OFERTA

PROVEEDOR 1

4

7

2

1000

PROVEEDOR 2

3

5

2

3000

PROVEEDOR 3

9

11

10

1000

DEMANDA

1500

100

2500

EJEMPLOS APLICATIVOS PARA LOS METODOS: ESQUINA NOROESTE, VOGEL Y COSTOS MINIMOS (-Cun-, 2011) Una empresa de componentes informáticos puede comprar Discos Duros a tres proveedores y su objetivo es minimizar el costo total de la compra los proveedores disponen de 1.000, 3.000, 1.000 disco respectivamente. La empresa necesita los discos en tres cadenas de montajes si en las tres localizaciones distintas. Dichas cadenas requieren de 1.500, 1.000, y 2.500discos respectivamente; los precios en cientos de euros por cada disco entregado a cada cadena son los siguientes: PROVEERDORES

CADENAS

PROVEEDOR 1

CADENA 1

PROVEEDOR 2

CADENA 2

PROVEEDOR 3

CADENA 3

TABLA #4

20

Método de la esquina noroeste

(-Cun-, 2011) Este método asigna la cantidad máxima autorizada para la oferta y la demanda a la variable X11 ubicada en la esquina noroeste de la tabla. La columna o fila satisfecha se satura dejando ver las variables restantes en la columna o fila saturadas son igual a cero. Si la columna y la fila se satisfacen simultáneamente, solo uno de los dos debe ser saturada; garantizando localizar las variables básicas cero si existen. Después de ajustar las cantidades de oferta y demanda para todas las filas y columnas no saturadas, la cantidad máxima factible se asigna al primer elemento no saturado en la nueva columna o fila; el método finaliza cuando las filas o la columna se saturan.

Indicaciones para implementar el método de la esquina noroeste: 1. Se estructura una tabla de ofertas que muestra la disponibilidad de los proveedores y las demandas o lo que requieren los proveedores. 2. Se inicia la esquina noroeste. Determina al máximo lo mínimo entre la oferta y la demanda, equitativamente. 3. Restablezca la oferta y la demanda y sature con ceros el resto de las filas o columnas en donde la oferta o la demanda quede satisfecha. 4. Muévase a la derecha o hacia abajo, según aquedado la disponibilidad para asignar. 5. se repiten nuevamente los pasos del 3 al 5 recíprocamente hasta llegar a la esquina inferior derecha en la que se saturan fila y columna al mismo tiempo. 6. Para calcular el costo total del Método de la esquina se multiplica cada una de las variables ubicada en la tabla y luego se suma los resultados y encontraremos el total costo.

21

Método Vogel (-Cun-, 2011) Este método suele producir una mejor solución inicial que los métodos de noroeste, costo mínimo. Ya que provoca una solución inicial óptima, o inmediata al nivel óptimo.

Indicaciones para implementar el método Vogel:

1. Elaborar una tabla reflejando las ofertas y demanda y los costos. 2. Calcular el contraste entre el menor costo y el segundo costo menor; para cada fila y columna. 3. Escoger entre filas y columnas, que mayor diferencia en caso de igualdad, decida arbitrariamente. 4. Determine al máximo posible en el sector con el menor costo en la fila o columna elegida en el puesto 3. 5. Asigne cero (0) a el otro sector de la fila o columna donde el recurso o el requerimiento quede saturado. 6. Nuevamente se realizan los pasos 2 al 5, sin tener en cuantas filas y columnas saturas hasta que los sectores en su totalidad queden asignados. 7. Para calcular el costo total del Método de Vogel se multiplica cada una de las variables ubicada en la tabla y luego se suma los resultados y encontraremos el total costo.

Método del costo mínimo (-Cun-, 2011) Este método se elabora en función al sector con menor costo para realizar las asignaciones de la tabla. Indicaciones para implementar el método del costo mínimo: 1. Se Construye una tabla de disponibilidad, requerimientos y costos 2. Se inicia en el sector que tenga el menor costo de toda la tabla, si hay igualdad, se escoge de manera arbitrariamente cualquiera de los igualados. 3. Se asigna lo máximo posible entre la disponibilidad y el requerimiento el mínimo de los dos. 4. Sature con ceros 0 la fila o columna saturada y restablezca la disponibilidad y el requerimiento, restándoles lo asignado.

22

5. Muévase al sector con el costo mínimo de la tabla resultante no se debe tener en cuenta la fila o columna saturada. 6. Retornar a los puntos 3,4,5 continuamente, hasta que todos los sectores queden asignadas.

Método simplex El método simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables. El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex. Mientras que los Programas Lineales que solo tienen restricciones de ( ≤)se pueden resolver sólo usando variables de holgura con el método simplex, para aquellos programas lineales que involucren restricciones de tipo (≥) e (=) es necesario usar variables artificiales, las variables de holgura tienen un significado físico real que corresponde a las disponibilidades o requerimientos no usados en las restricciones, pero las variables artificiales no tienen ninguna representación física y sólo son usadas como un comodín matemático para ayudar en la solución del problema. Pues bien, cuando se tiene que usar variables artificiales al tener restricciones de (≥) e (=) se debe usar una de las siguientes variantes del método simplex: 

Método de la m grande



Método de dos fases

Presentación del Método Simplex Publicado por George Dantzig en 1947 es en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal, comienza con una solución factible y prueba si es o no óptima. Si no lo es, el método sigue a una mejor solución, hasta que encuentre una solución óptima, si es que existe. Si el Problema de Programación Lineal tiene solución, esta se encuentre en la región factible que es un conjunto convexo.

23

El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A de la región factible, entonces hay una arista que parte de A, a lo largo de la cual f aumenta; es decir, partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor) que conforman la región factible. Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución. Además de ser eficiente, dicho método tiene otras ventajas. Es completamente mecánico (se utilizan matrices, operaciones elementales sobre renglones y aritmética básica). Asimismo, no implica el uso de geometría. Esto permite resolver problemas de programación lineal que tiene cualquier número de restricciones y variables. Cabe destacar que, para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar.

𝑧 = 𝑐1 𝑥1 + 𝐶2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 Sujeto a:

𝐴11 𝑥1 + 𝐴12 𝑥2 + ⋯ + 𝐴1𝑛 𝑥𝑛 ≥ 𝐵1 𝐴21 𝑥1 + 𝐴22 𝑥2 + ⋯ + 𝐴2𝑚 𝑥𝑛 ≤ 𝐵2 …. …. 𝐴𝑚1 𝑥1 + 𝐴𝑚2 𝑥2 + ⋯ + 𝐴𝑚𝑛 𝑥𝑛 = 𝐵𝑚 𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0

Construcción de la tabla simplex En la primera columna de la tabla aparecerá lo que llamaremos base, a partir de la segunda columna aparecerán cada una de las variables de la función objetivo (𝑃1 ) y en la última el término independiente de cada restricción (𝑃0 ). Para tener una visión más clara

24

de la tabla, incluiremos una fila en la que pondremos cada uno de los nombres de las columnas.

Sobre esta tabla que tenemos incluiremos dos nuevas filas: una que será la que liderará la tabla donde aparecerán las constantes de los coeficientes de la función objetivo, y otra que será la última fila, donde tomará valor la función objetivo. Nuestra tabla final tendrá tantas filas como restricciones.

Tabla 1 Los valores de la fila Z se obtienen de remplazar los valores Cim de la función objetivo y cero si no aparece en la base. El resto de las columnas se obtiene remplazando los coeficientes de las restricciones según se muestra en la tabla. Se observará al realizar el método Simplex, que, en esta primera tabla, en la base estarán las variables de holgura.  Condición de parada: Cuando en la fila Z no existe ningún valor negativo (para problemas de Maximización) o ningún valor positivo (para problemas de Minimización), se ha alcanzado la solución óptima del problema. En tal caso, se ha llegado al final del algoritmo. De no ser así, se continúa con las iteraciones.  Condición de parada: Cuando en la fila Z no existe ningún valor negativo (para problemas de Maximización) o ningún valor positivo (para problemas de Minimización), se ha alcanzado la solución óptima del problema. En tal caso, se ha llegado al final del algoritmo. De no ser así, se continúa con las iteraciones  Elección de la variable que sale: Una vez obtenida la variable entrante, obtendremos la variable que sale, sin más que seleccionar aquella fila cuyo

25

cociente 𝑃0 /𝑃𝑗 sea el menor de los estrictamente positivos (teniendo en cuenta que sólo se hará cuando 𝑃𝑗 sea mayor de 0). La intersección entre la columna entrante y la fila saliente nos determinará el elemento pivote.  Actualización de la tabla: Las filas correspondientes a la función objetivo y a los títulos permanecerán inalterados en la nueva tabla. El resto deberá calcularse de dos formas diferentes: La fila en la cual se encuentra el elemento pivote, se le denomina fila pivote, y la columna, columna pivote a. Si es la fila pivote cada nuevo elemento se calculará:

Nuevo Elemento Fila Pivote = Elemento Fila Pivote actual / Pivote b. Para el resto de los elementos de filas se calculará: Nuevo Elemento Fila = Elemento Fila Pivote actual - (Elemento Columna Pivote en la fila actual * Nuevo Elemento Fila). Esto se realiza con el fin de llegar a construir la matriz unitaria o base.

Método dual simplex Este método se aplica a los problemas óptimos pero infactible. En este caso, las restricciones se expresan en forma canónica (restricciones). La función objetivo puede estar en la forma de maximización o de minimización. Después de agregar las variables de holgura y de poner el problema en la tabla, si el elemento de la derecha es negativo y si la condición de la optimización está satisfecha, el problema puede resolver por el método Dual Simplex. Tenga en cuenta que un elemento negativo en el lado derecho significa que el problema comienza óptimo pero infactible como se requiere en el método dual simplex. En la iteración donde la solución básica llega a ser factible, esta será la solución óptima del problema (Peralta, 2015).

El método de solución para los problemas de maximización es el denominado Método Dual-Simplex y se aplica por medio de reglas de equivalencia Min. (z) = Max. (- z). En la maximización mediante el método Dual Simplex, se requiere que la función objetivo del dual se exprese en forma de maximización, Max (z).

26

Método Dual-Simplex empieza con una solución óptima o mejor que óptima, pero no factible y se mueve hacia el óptimo mediante iteraciones que mejoran su factibilidad conservando su optimalidad (Almenares, 2015). El problema de programación lineal dual que se define a partir de un problema original (primal), comparte con él los mismos coeficientes tanto de la función objetivo como de las restricciones, pero en diferente posición como más adelante se especificará (ROMO, 2005). DEFINICIÓN DEL PROBLEMA DUAL Para poder elaborar el problema dual a partir del primal, este se debe presentar en su forma canónica de la siguiente forma:

MAX Z=

𝑛

∑

𝐶𝑗𝑋𝑗 𝑗−1

SA ∑𝑛𝑗−1 𝐴𝑖𝑗𝑋𝑗 ≤ B Xj ≥0 MIN Z= 315A + 110B + 50C SA

∑𝑛𝑗−1 = La sumatoria de 15A los elementos. + 2B + C ≥ 200 ≤ = Menor igual. ≥ = Mayor igual.

7,5A+ 3B + C ≥ 150 5A + 2B + C ≥ 120 A,B,C ≥ 0

i= 1, 2, 3,…… …, m (número de restricciones). j= 1, 2, 3,………, n (número de variables). i= 1, 2,3,………, m (número de variables). j= 1, 2,3,………, n (número de restricciones).

El problema dual se puede obtener a partir del problema primal y viceversa de la siguiente manera: 1. Cada restricción de un problema corresponde a una variable en el otro. 2.

Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes respectivos de la función objetivo en el otro.

3. Un problema busca maximizar y el otro minimizar. 4.

El problema de maximización tiene restricciones ≤ que y el problema de minimización tiene restricciones ≥ que.

5. Las variables en ambos casos son no negativas.

27

EJEMPLO SIMPLEX DUAL Considere el siguiente modelo de Programación Lineal:

MIN Z= 315A + 110B + 50C SA 15A + 2B + C ≥ 200 7,5A+ 3B + C ≥ 150 5A + 2B + C ≥ 120 A,B,C ≥ 0

Paso 1: Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se logra agregando variables de exceso en cada una de las restricciones (3 primeras: S1, S2, S3, respectivamente). Luego, se multiplica cada fila de las restricciones por -1 de modo de disponer una solución básica inicial (infactible) en las variables de exceso S1, S2 y S3. De esta forma se obtiene la siguiente tabla inicial.

Paso 2: Se selecciona el lado derecho "más negativo" lo cual indicará cuál de las actuales variables básicas deberá abandonar la base. En el ejemplo el lado derecho más negativo se encuentra en la primera fila, por tanto S1 deja la base. Para determinar cual de las actuales variables no básicas (A, B, C) entrará a la base se busca el mínimo de {-Yj/aij} donde aij es el coeficiente de la respectiva variable no básica en la fija i (del lado derecho más negativo, marcado en verde) y donde Yj es el costo reducido de la respectiva variable no básica. De esta forma se obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde el pivote (marcado en rojo) se encuentra al hacer el primer coeficiente, por tanto A entra a la base.

Paso 3: Se actualiza la tabla anterior siguiendo un procedimiento similar al utilizado en el Método Simplex. En el ejemplo se debe dejar a la variable A como básica y S1 como no básica. La tabla que resulta es la siguiente:

Continuar las iteraciones y siguiendo el mismo procedimiento hasta disponer de una solución básica factible. Luego de unas iteraciones se obtiene la siguiente tabla final:

28

Macro Método Simplex

Figura Macro 1

Bibliografía Castro. (7 de febrero de 2011). Slideshare.net. Obtenido de https://es.slideshare.net/castrov/programacin-lineal-de-transporte -Cun-. (16 de Mayo de 2011). Blogspot.com. Obtenido de http://metododetransporte2011.blogspot.com/2011/05/ejemplo-una-empresa-decomponentes.html#comment-form Lopez, B. S. (2016). Ingenieria Industrial:Online.com . Obtenido de https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingenieroindustrial/investigaci%C3%B3n-de-operaciones/problema-del-transporte-odistribuci%C3%B3n/ Almenares, W. J. (2015). metodo dual simplex. 88.\\ Fernández, C. G. (2010). Teoría de la Dualidad. En C. G. Fernández, Programación Lineal e Ingeniería Técnica (Vol. 2, págs. 77-94).\\ M. Caraveo Peralta. (2015). ibm.com. Obtenido de Sitio Oficial Bluemix®: http://www.academia.edu/8912801/METODO_DUAL_SIMPLEX\\ Peralta, M. C. (2013). METODO DUAL SIMPLEX. 11.\\ ROMO, N. H. (s.f.). ANALISIS DE DUALIDAD. En "MATEMATICAS PARA NEGOCIOS". ED BANCA Y COMERCIO.\\

29

30