Programacion lineal desde cero

Optimización de enteros python

/tmp/ipykernel_6899/1851481465.py:11: DeprecationWarning: `method='revised simplex'` está obsoleto y será eliminado en SciPy 1.11.0. Por favor, utilice uno de los solucionadores HiGHS (por ejemplo, `method='highs'`) en el nuevo código.

/tmp/ipykernel_6899/1937289231.py:21: DeprecationWarning: `method='revised simplex'` está obsoleto y será eliminado en SciPy 1.11.0. Por favor, utilice uno de los solucionadores HiGHS (por ejemplo, `method='highs'`) en el nuevo código.

Dualidad fuerte: Para el problema de programación lineal (21.1), si el problema primal tiene una solución óptima \(x\), entonces el problema dual también tiene una solución óptima. Denotemos una solución óptima del problema dual como \(p\). Entonces

Holgura complementaria: Si existe \(i\) tal que \(a_i' x - b_i < 0\) para algún \(i\), entonces \(p_i = 0\) por holgura complementaria. \(a_i' x - b_i < 0\) significa que para alcanzar su producción óptima, la fábrica no necesita tanto Recurso \(i\) como tiene.

Si existe \(j\) tal que \(A_j' p - c_j > 0\), entonces \(x_j = 0\) por holgura complementaria. \(A_j' p - c_j > 0\) significa que el valor de todos los recursos utilizados al producir una unidad de producto \(j\) es mayor que su coste.

Programación mixta entera en Python

Representación gráfica de un programa lineal simple con dos variables y seis inecuaciones. El conjunto de soluciones factibles se representa en amarillo y forma un polígono, un politopo bidimensional. El óptimo de la función de coste lineal se encuentra donde la línea roja corta el polígono. La línea roja es un conjunto de niveles de la función de costes, y la flecha indica la dirección en la que estamos optimizando.

Una región factible cerrada de un problema con tres variables es un poliedro convexo. Las superficies que dan un valor fijo de la función objetivo son planos (no se muestran). El problema de programación lineal consiste en encontrar un punto del poliedro que esté en el plano con el mayor valor posible.

La programación lineal (PL), también llamada optimización lineal, es un método para conseguir el mejor resultado (como el máximo beneficio o el menor coste) en un modelo matemático cuyos requisitos están representados por relaciones lineales. La programación lineal es un caso especial de la programación matemática (también conocida como optimización matemática).

Programación lineal Scipy

Debido a los costes de preparación relativamente elevados, puede ser conveniente no fabricar algunos de los productos. Sea una variable de decisión tal que si el producto se fabrica y en caso contrario . El límite garantiza que si es 0, también lo es , sin limitar el tamaño de más de lo que lo hacen otras restricciones:

John Conner se ha enterado de que Skynet planea atacar cinco asentamientos. Necesita desplegar soldados desde tres campamentos base a los asentamientos para hacer frente a la amenaza. El coste de combustible para transportar a un soldado del campamento base al asentamiento es:

La Orden Jedi está luchando contra los ejércitos separatistas liderados por Dooku. Dooku y dos de sus generales, Asajj Ventress y el general Grievous, han atacado tres colonias exteriores. La Orden Jedi envía a tres Jedi para ayudar a las colonias exteriores. Sean las probabilidades de que los Jedi venzan a los Sith :

Halla el inventario que una tienda minorista debe pedir de un producto por semana para minimizar el coste. Sean las existencias disponibles al principio de la semana . Sea el pedido de existencias recibido del mayorista al principio de la semana . El coste de comprar una unidad al mayorista es de 3 $:

Forma estándar de la programación lineal

contienen los multiplicadores de Lagrange en la solución x.Ejemploscomprimir todoPrograma lineal, Restricciones de desigualdad linealAbrir Live ScriptResolver un programa lineal simple definido por desigualdades lineales. Para este ejemplo, utilice estas restricciones de desigualdad lineal:

Programa lineal con desigualdades e igualdades linealesAbrir Live ScriptResolver un programa lineal simple definido por desigualdades e igualdades lineales. Para este ejemplo, utilice estas restricciones de desigualdad lineal:

Programa lineal con todos los tipos de restriccionesAbrir Live ScriptResuelva un programa lineal simple con desigualdades lineales, igualdades lineales y límites. Para este ejemplo, utilice estas restricciones de desigualdad lineal:

ub = [1.5,1.25];Utilice la función objetivo -x(1)-x(2)/3. f = [-1 -1/3];Establezca las opciones para utilizar el algoritmo de 'punto interior'. options = optimoptions('linprog','Algorithm','interior-point');Resuelva el programa lineal utilizando el algoritmo de 'punto interior'. x = linprog(f,A,b,Aeq,beq,lb,ub,options)Mínimo encontrado que satisface las restricciones.