Identificación de restricciones y función objetivo en el dual

Teoría dualidad

Asociado a todo problema de pgr lineal, existe otro problema lineal llamado dual.

Teorema de La dualidad:

Las siguientes son las únicas relacione posibles entre los problemas Primal y dual.

1. Si un problema Tiene soluciones factibles y una función objetivo acotada (y, por ende,

una solución óptima)
, entonces Ocurre lo mismo con el otro problema, de manera q

se aplican tanto la propiedad de Dualidad débil como la fuerte.

2. Si uno de los Problemas tiene soluciones factibles y una función objetivo no acotada

(es decir, no tiene solución óptima), entonces el otro problema no tiene soluciones

factibles.

3. Si un problema no Tiene soluciones factibles, entonces el otro problema no tiene Soluciones

factibles o bien la función Objetivo es no acotada.. 

Principios de dualidad

Propiedad de Dualidad débil: Si x es una solución factible para el problema primal y yes una Solución factible para el problema dual, entonces cx  yb.
Propiedad de dualidad Fuerte: Si x*
es una solución óptima Para el problema primal y y*
es una Solución óptima para el problema dual, entonces cx* = y*b.

Propiedad De soluciones complementarias:

En cada iteración, el método símplex identifi

ca de manera simultánea una Solución FEV, x, para el problema primal y una solución

complementaria, y, para El problema dual (q se encuentra en el renglón 0, como los

coefi cientes de las variables de Holgura), donde cx = yb.
Si x no es óptima para el Problema primal, entonces y no es factible para el problema

dual.

Propiedad de soluciones Complementarias óptimas:

Al fi nal de cada iteración, el método símplex Identifi ca de manera simultánea una solución óptima x*
Para el problema

primal y una solución óptima Complementaria y*
Para el problema dual (q se encuentra

en el renglón 0 como los coefi Cientes de las variables de holgura), donde

cx*
= y*

b

Los valores de yi* son los precios sombra para el problema primal.

Propiedad De simetría:

En el caso de cualquier problema primal y su problema Dual,las relaciones entre ellos deben ser simétricas debido a q el dual De este problema dual es este problema primal. Holgura complementaria:
holgura Complementaria para esta última propiedad

es q enuncia (en parte) q para Cada par de variables asociadas, si una de ellas tiene holgura en su Restricción de no negatividad (una variable básica . 0), entonces la otra no debe tener holgura(variable no básica = 0).

Para la dualidad:

el análisis de sensibilidad consiste, en

esencia, en la investigación del Efecto q tiene sobre la solución óptima el hecho de hacer cambiosen los valores De los parámetros del modelo aij, bi y cj. Sin embargo, al Cambiar los valores  de los parámetros en El problema primal se cambian también los valores correspondientes en el problema Dual.

Análisis de Sensibilidad, Para investigar el

efecto q tendría sobre la solución óptima q proporciona el método símplex el hecho de q

los parámetros tomen otros valores Posibles. En general, habrá algunos parámetros a los q se

les pueda asignar cualquier valor Razonable sin q afecten la optimalidad de esta solución. Sin

embargo, también habrá parámetros Con valores probables q lleven a una nueva solución óptima.

Esta situación es seria, en Particular si la solución original adquiere valores muy inferiores en la

función objetivo, o tal vez no Factibles.

Por tanto, un objetivo fundamental Del análisis de sensibilidad es identificar los parámetros

sensibles (es decir, los Parámetros cuyos valores no pueden cambiar sin q cambie la solución óptima) .Para Coeficientes de la función objetivo q no están clasificados como sensibles, También puede resultar de gran utilidad determinar el intervalo de valores del parámetro para el q la solución óptima no cambia. (Este intervalo de valores se Conoce como intervalo permisible para ese coeficiente.) En algunos casos, El cambio del valor de un parámetro en la columna del lado derecho dentro de Una restricción funcional puede afectar la factibilidad de la solución BF óptima. Para manejar tales parámetros, es útil determinar el intervalo de Valores para el q la solución BF óptima (con los valores ajustados de las Variables básicas) seguirá siendo factible. (Este intervalo recibe el nombre de intervalo permisible por el lado derecho involucrado.) Este rango de Valores es también el rango dentro del cual el precio sombra actual de La restricción correspondiente permanece válido.

El valor más favorable signifi Ca el valor más grande si la función objetivo debe maximizarse, o El valor más peqño si la función objetivo debe minimizarse.

Una solución factible en un Vértice (FEV)
es una solución q se encuentra en una

esquina de la regíón factible.

Relación entre Las soluciones óptimas y las soluciones FEV:

El problema debe poseer Soluciones FEV y al menos una solución óptima. Además, la mejor solución FEV debe ser una solución óptima. Entonces, si un problema tiene exactamente una Solución óptima, ésta debe ser una solución FEV. Si el problema tiene Múltiples soluciones

óptimas, al menos dos deben ser Soluciones FEV.

Supuestos

Supuesto de Proporcionalidad:

La Contribución de cada actividad al valor de la función

objetivo Z es proporcional al nivel de la actividad xj, como lo representa el término cjxj en

la función objetivo. De manera Similar, la contribución de cada actividad al lado izquierdo

de cada Restricción funcional es proporcional al nivel de la actividad xj, como lo representa

en la restricción el término aijxj. En consecuencia, este supuesto elimina cualquier

exponente diferente de 1 para las Variables en cualquier término de las funciones —ya sea

la función objetivo o la función En el lado izquierdo de las restricciones funcionales— en

un modelo de pgr lineal.

Supuesto de Aditividad:

Cada función De un modelo de pgr lineal (ya sea la

función objetivo o el lado Izquierdo de las restricciones funcionales) es la suma de las

contribuciones Individuales de Las actividades respectivas.

Supuesto de Divisibilidad:

En Un modelo de pgr lineal, las variables de decisión

pueden tomar cualquier valor, Incluso valores no enteros, q satisfagan las restricciones

funcionales y de no negatividad. En consecuencia, estas variables no están restringidas

a sólo valores enteros. Como cada Variable de decisión representa el nivel de alguna

actividad, se supondrá q las Actividades se pueden realizar a niveles fraccionales.

Supuesto de Certidumbre:

Se Supone q los valores asignados a cada parámetro de un

modelo de pgr lineal son constantes Conocidas.

Transporte

Propiedad de Soluciones enteras:

En Los casos de problemas de transporte en los q si

y dj toman un valor entero, Todas las variables básicas (asignaciones), de toda solución

básica factible (inclusive la óptima), asumen también valores enteros.

Propiedad de Soluciones factibles:

un Problema de transporte tiene soluciones factibles

si y sólo si  M3 i=1 si = N3j=i este ultimo por dj.

Supuesto de Costo:

El Costo de distribuir unidades de un origen a un destino dados es directamente Proporcional al número de unidades distribuidas. Por tanto, este costo es Igual

al costo unitario de Distribución multiplicado por el número de unidades distribuidas. (El

costo unitario del origen i al Destino j se denota por cij.)

Tipos de pgr por metas :

Las tres formas de la función de Logro más antiguas y todavía más utilizadas en la

práctica son las siguientes:

1. Pgr por metas ponderadas

2. Pgr por metas lexicogáficas

3. Pgr por metas MINMAX