¿Qué es el Modelo Dual?

Índice

Introducción……………………………………………………..1,2

¿De dónde surge el modelo Dual?...................................................2

¿Qué es el Modelo Dual?...............................……………………..2

Concepto………………………………………………………......3

Forma Estándar…………………….……………………………...3

Variable de Holgura……………………………………………….4

Variable de exceso……………………………………...…………4

Variables Básicas y No básicas……………………………………4

Variables básicas…………………………………………………..4

Variable de Entrada y Variable de Salida…………………………5

Condición de Optimalidad………………………………………...5

Objetivo……………………………………………………………6

Ejercicio…………………………………………………………...6

1

Introducción

Hemos visto como la programación lineal puede ser usada para resolver una extensa variedad de problemas propios de los negocios, ya sea para maximizar utilidades o minimizar costos. Las variables de decisión en tales problemas fueron, por ejemplo, el número de productos a producir, la cantidad de pesos a emplear, etc. En cada caso la solución óptima no explicó cómo podrían ser asignados los recursos (ejemplo: materia prima, capacidad de las máquinas, el dinero, etc.) para obtener un objetivo establecido. El Método simplex es una herramienta de programación lineal desarrollado por George Dantzing.

El método consiste en buscar sistemáticamente a través de todas las posibles soluciones, la solución óptima a un problema. Es un método muy eficiente y permite el uso de muchas variables, tiene como punto de partida el origen, el cual  es la solución inicial (solución básica factible). La eficiencia del método se consigue debido a que se dirige la búsqueda haciendo cambios a una solución básica factible adyacente, que se distingue al tener m-1 variables básicas iguales; es decir, dos vértices adyacentes sólo difieren en una variable básica; seleccionando la ruta de mayor pendiente, para mejorar el valor de Z, o por lo menos conservarlo este método prueba todos los puntos extremos gráficos.

Para aplicar el método Simplex se requiere considerar:

-Las desigualdades deben ser igualdades

-Todas las bi ≥ 0

-El modelo debe tener únicamente variables de holgura.

Los pasos del método Simplex

1.- Utilizando la forma estándar determinar una solución básica factible igualando las m-n variables a cero (el origen).

2.- Seleccionar la variable de entrada que a incrementar su valor pueda mejorar el valor de la Función objetivo cuando no existe

2

esta situación la solución actual es la óptima, si no ir al siguiente paso.

3.- Seleccionar la variable de salida

4.- Determinar la nueva solución básica factible al hacer la variable de entrada en básica.

En el método simplex se hacen diversos cálculos de álgebra de matrices, para facilitar estos cálculos se hace uso de  una estructura de tabla  en la cual es expresado el modelo.

Para poder expresar un modelo en forma de tabla en necesario.

Expresar la Función objetivo como Zj-Cj

Ubicar las variables básicas en la solución inicial.

Las restricciones deben estar en forma de igualdad

¿De dónde surge el modelo Dual?

El problema dual es estudiado por medio de la Programación Lineal y se obtiene matemáticamente de un modelo primal dado (método simplex).

¿Qué es el Modelo Dual?

 El problema primal y dual explica dos     aspectos económicos distintos de un mismo  problema. Las variables dobles nos vienen a medir el valor de los recursos imputados a la producción, pero esta      valoración tiene unas características peculiares,      está    realizada en   términos de costo de             oportunidad.

El concepto de dualidad indica que para cada problema de Programación Lineal (PL) hay una asociación y una relación muy importante con otro problema de programación lineal, llamada precisamente dual.

3

Concepto

El método simplex dual resulta ser una estrategia algorítmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja, por ejemplo, puede requerir la utilización del método simplex de 2 fases.

Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetivo de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.

Forma estándar

El empleo de las soluciones básicas para resolver un modelo general de programación lineal, requiere poner el problema en una forma estándar y estas propiedades son:

1. Todas las restricciones son ecuaciones con un lado derecho no negativo.

2. Todas las variables son no negativas.

3. La función objetivo puede ser de maximización o minimización.

Ejemplo:

Maximizar z = 2x1 + 3x2

S.a

x1+x2 ≥ -5

-6x1+7x2 ≤ 4

x1+x2 = 10

x1,x2 ≥ 0

Forma Estándar

Maximizar z = 2x1 + 3x2

S.a

-x1-x2 +x3 = 5 ----> Se agrega una variable de exceso, y se multiplica por (-1) para tener un lado derecho no negativo.

-6x1+7x2 +x4 = 4 -----> Se agregó una variable de holgura.

4

x1+x2 = 10   --> Como es una ecuación no se necesitan variables de holgura ni de exceso.

x1,x2 ,x3,x4≥ 0.

Variable de holgura.

La variable de holgura aparece en las restricciones ≤, esta se agrega sumando en la restricción para que la desigualdad se vuelva ecuación.

...