TEMA: PROGRAMACIÓN LINEAL

TAREA 2.A. Resolver un problema de programación lineal por método gráfico.

¡Atención!

Esta es una VERSIÓN DE PRUEBA del trabajo No. 2073, el precio del original es 200 rublos. Diseñado en programa de microsoft Palabra.

Pago. Contactos.

Opción 7. Encuentra los valores máximo y mínimo.función lineal Ф = 2x 1 - 2 x 2con restricciones: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x yo ≥ 0, yo = 1,2.

Solución:

Reemplazando condicionalmente los signos de desigualdad por signos de igualdad, obtenemos un sistema de ecuaciones x1 + x2 = 4;

-x1 + 2x2 = 2;

x1 + 2x2 = 10.

Construyamos líneas rectas usando estas ecuaciones, luego, de acuerdo con los signos de las desigualdades, seleccionamos los semiplanos y obtenemos su parte común, la región de soluciones admisibles del ODR, el cuadrilátero MNPQ.

Valor mínimo de la función

ciones - en el punto M(2; 2)

Ф mín = 2·2 - 2·2 = 0.

El valor máximo se alcanza en el punto N (10; 0),

Ф máx = 2·10 - 2·0 = 20.

Opción 8. Encuentra los valores máximo y mínimo.

función lineal Ф = x 1 + x 2

con restricciones: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x yo ≥ 0, yo = 1,2.

Solución:

Reemplazando condicionalmente los signos de desigualdad por signos de igualdad, obtenemos un sistema de ecuaciones x1 - 4 x2 = 4 ;

3 x1 - x2 = 0;

Construyamos líneas rectas usando estas ecuaciones, luego, de acuerdo con los signos de las desigualdades, seleccionamos los semiplanos y obtenemos su parte común, la región de soluciones admisibles del ODR, el polígono ilimitado MNPQ.

Valor mínimo de la función

ciones – en NP directo, por ejemplo

en el punto P(4; 0)

Ф mín = 4 + 0 = 4.

El ODR no está limitado desde arriba, por lo tanto Ф max = + ∞.

Opción 10. Encuentra los valores máximo y mínimo.

función lineal Ф = 2 x 1 - 3 x 2

con restricciones: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x2≤5;

x yo ≥ 0, yo = 1,2.

Reemplazando condicionalmente los signos de desigualdad con signos de igualdad, obtenemos un sistema de ecuaciones

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Construyamos líneas rectas usando estas ecuaciones, luego, de acuerdo con los signos de las desigualdades, seleccionemos los semiplanos y obtengamos su parte común, la región de soluciones admisibles del ODR, el polígono MNPQRS.

Construyamos el vector Г(2; -3) y pasemos por el origen de coordenadas. línea de nivel- derecho.

Movemos la línea de nivel en la dirección en la que aumenta el valor de Ф. En el punto S(7; 0) la función objetivo alcanza un máximo Ф max =2·7–3·0= = 14. Movemos la línea de nivel en la dirección en la que el valor de Ф disminuye. El valor mínimo de la función está en el punto N(0; 5)

Ф mín = 2·0 – 3·5 = –15.

TAREA 2.B. Resolver un problema de programación lineal

método analítico simplex

Opción 7. Minimizar la función objetivo Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

con restricciones: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Solución:

Número de incógnitas n=6, número de ecuaciones m=3. Por lo tanto, r = n-m = 3 incógnitas pueden considerarse libres. Elijamos x 1, x 3 y x 6.

Expresamos las variables básicas x 2 , x 4 y x 5 en términos de libres y reducimos el sistema a una base unitaria

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

La función objetivo se verá así:

Ф = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

Pongamos x 1 = x 3 = x 6 = 0, y las variables básicas tomarán los valores x 2 = 2; x4 = 9; x 5 = 6, es decir, la primera solución factible (0; 2; 0; 9; 6; 0), función objetivo Ф 1 = 13.

Las variables x 3 y x 6 están incluidas en la función objetivo con coeficientes negativos, por lo tanto, a medida que aumentan sus valores, el valor de Ф disminuirá. Tomemos por ejemplo x 6. De la primera ecuación del sistema (*) se desprende claramente que es posible aumentar el valor de x 6 hasta x 6 = 1 (mientras x 2 ³ 0). En este caso, x 1 y x 3 siguen siendo iguales a cero. Ahora tomamos x 4, x 5, x 6 como variables básicas y x 1, x 2, x 3 como variables libres. Expresemos las nuevas variables básicas en términos de las nuevas libres. Obtenemos

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

Ф = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Asignemos valores cero a las variables libres, es decir, x 1 = x 2 = x 3 = 0, mientras que x 6 = 1, x 4 = 3, x 5 = 4, es decir, la tercera solución factible (0 ; 0; 0; 3; 4; 1). En este caso Ф 3 = 6.

La variable x 3 está incluida en la función objetivo con un coeficiente negativo, por lo tanto, un aumento de x 3 con respecto al valor cero conducirá a una disminución de F. De la segunda ecuación se desprende claramente que x 3 puede aumentar a 1/4 , de la tercera ecuación - a 2/3 . La segunda ecuación es más crítica. Convirtamos la variable x 3 al número de básicas y x 4 al número de libres.

Ahora tomamos x 1, x 2 y x 4 como nuevas variables libres. Expresemos a través de ellos las nuevas variables básicas x 3, x 5, x 6. Consigamos el sistema

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

La función objetivo tomará la forma

Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Las variables x 1 y x 2 están incluidas en la función objetivo con coeficientes negativos, por lo tanto, a medida que aumentan sus valores, el valor de Ф disminuirá. Tomemos por ejemplo x 2. De la segunda ecuación del sistema se desprende claramente que es posible aumentar el valor de x 2 hasta x 2 = 5 (mientras x 5 ³ 0). En este caso, x 1 y x 4 siguen siendo cero, los valores de otras variables son iguales a x 3 = 3/2; x 5 = 0, x 6 = 3/2, es decir, la cuarta solución factible (0; 5; 3/2; 0; 0; 3/2). En este caso Ф 4 = 5/4.

Ahora tomamos x 1, x 4 y x 5 como nuevas variables libres. Expresemos a través de ellos las nuevas variables básicas x 2, x 3, x 6. Consigamos el sistema

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

La función objetivo tomará la forma

Ф = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Los coeficientes de ambas variables en la expresión de Ф son positivos, por lo que es imposible una mayor disminución del valor de Ф.

Es decir, el valor mínimo de Ф min = - 5, la última solución factible (0; 5; 3/2; 0; 0; 3/2) es óptima.

Opción 8. Maximizar la función objetivo Ф = 4 x 5 + 2 x 6

con restricciones: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Solución:

El número de ecuaciones es 4, el número de incógnitas es 6. Por lo tanto, r = n – m = 6 – 4 = 2 variables se pueden elegir como variables libres y 4 variables como básicas. Elegimos x 5 y x 6 como libres, y x 1, x 2, x 3, x 4 como básicos. Expresemos las variables básicas en términos de libres y reduzcamos el sistema de ecuaciones a una base unitaria.

x 1 = 12 - x 5 - x 6 ;

x 2 = 30 - 5 x 5 + x 6 ;

x 3 = 6 - x 5 + 2 x 6 ;

x 4 = 9 - 3/2 x 5 + x 6;

Escribimos la función objetivo en la forma Ф = 4 x 5 + 2 x 6. Asignemos valores cero a las variables libres x 5 = x 6 = 0. En este caso, las variables básicas tomarán los valores x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , es decir, obtenemos la primera solución factible (12, 30, 6, 9, 0,) y Ф 1 = 0.

Ambas variables libres entran en la función objetivo con coeficientes positivos, es decir, es posible un aumento adicional en F. Convirtamos, por ejemplo, x 6 en el número de básicos. De la ecuación (1) queda claro que x 1 = 0 en x 5 = 12, en (2) ÷ (4) x 6 se incluye con coeficientes positivos. Pasemos a una nueva base: variables básicas - x 6, x 2, x 3, x 4, libre - x 1, x 5. Expresemos las nuevas variables básicas en términos de nuevas variables libres

x6 = 12 - x1 - x5;

x2 = 42 - x1 - 6x5;

x 3 = 30 - 2 x 1 - 3 x 5 ;

x 4 = 21 - x 1 - 5/2 x 5 ;

La función objetivo tomará la forma Ф = 24 - 2 x 1 + 2 x 5 ;

Asignemos valores cero a las variables libres x 1 = x 5 = 0. En este caso, las variables básicas tomarán los valores x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , es decir, obtenemos la segunda solución factible (0, 42, 30, 21, 0, 12) y Ф 2 = 24.

La función objetivo x 5 se incluye con un coeficiente positivo, es decir, es posible un aumento adicional en F. Pasemos a una nueva base: variables básicas - x 6, x 5, x 3, x 4, libre - x 1 , x 2. Expresemos las nuevas variables básicas mediante nuevas variables libres.

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2 ;

x 3 = 9 - 3/2 x 1 + 1/2 x 2 ;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5 ;

La función objetivo tomará la forma Ф = 38 – 7/2 x 1 – 1/3 x 2 ;

Asignemos valores cero a las variables libres x 1 = x 2 = 0. En este caso, las variables básicas tomarán los valores x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 /2, es decir, obtenemos la tercera solución factible X 3 = (0, 0, 9, 7/2, 7, 5) y Ф 3 = 38.

Ambas variables entran en la función objetivo con coeficientes negativos, es decir, es imposible un mayor aumento de Ф.

Por tanto, la última solución factible es óptima, es decir, X opt = (0, 0, 9, 7/2, 7, 5) y Ф max = 38.

Opción 10. Maximizar la función objetivo Ф = x 2 + x 3

con restricciones: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Solución:

El sistema de ecuaciones-restricciones es consistente, ya que los rangos de la matriz del sistema de ecuaciones y la matriz extendida son iguales e iguales a 2. En consecuencia, dos variables pueden tomarse como libres, las otras dos variables, básicas, pueden expresarse linealmente a través de dos libres.

Tomemos x 2 y x 3 como variables libres, entonces las variables básicas serán x 1 y x 2, que expresaremos en términos de variables libres.

x 1 = 1 + x 2 - x 3 ; (*)

x 4 = 2 - x 2 + 2 x 3 ;

La función objetivo ya está expresada en términos de x 2 y x 3, es decir, Ф = x 2 + x 3.

Para x 2 =0 y x 3 =0, las variables básicas serán iguales a x 1 = 1, x 4 = 2.

Tenemos la primera solución factible X 1 = (1, 0, 0, 2), con Ф 1 = 0.

Es posible aumentar Ф aumentando, por ejemplo, el valor de x 3, que se incluye en la expresión para Ф con un coeficiente positivo (x 2 sigue siendo igual a cero). La primera ecuación del sistema (*) muestra que x 3 se puede aumentar a 1 (a partir de la condición x 1 ³0), es decir, esta ecuación impone una limitación al aumento en el valor de x 3. La primera ecuación del sistema (*) se está resolviendo. Con base en esta ecuación, pasamos a una nueva base, intercambiando x 1 y x 3. Ahora las variables básicas serán x 3 y x 4, y las variables libres serán x 1 y x 2. Expresemos ahora x 3 y x 4 en términos de x 1 y x 2.

Obtenemos: x 3 = 1 - x 1 + x 2 ; (**)

x 4 = 4 - 2 x 1 + x 2 ;

Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Al igualar las variables libres a cero, obtenemos la segunda solución básica admisible X 2 = (0; 0; 1; 4), para la cual Ф 2 = 1.

Es posible un aumento de Ф con un aumento de x2. El aumento de x 2, a juzgar por el último sistema de ecuaciones (**), no está limitado. En consecuencia, Ф tomará valores positivos cada vez mayores, es decir, Ф max = + ¥.

Entonces, la función objetivo Ф no está limitada desde arriba, por lo tanto no existe una solución óptima.

TAREA 2.D. Redactar un problema dual al dado.

la tarea original.

Opción 7. Maximizar la función objetivo Ф = 2× x1 - x4

con restricciones: x 1 + x 2 = 20,

x2 + 2× x4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x yo ≥ 0 (yo = 1, 2, 3, 4)

Solución:

Llevemos el sistema de restricciones a una forma única, por ejemplo, canónica, introduciendo variables adicionales en la segunda y tercera ecuaciones.

x1 + x2 = 20,

x2 + 2 × x4 – x5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

Hemos obtenido un problema asimétrico de tipo 2. El problema dual se verá así:

Minimizar la función objetivo F = 20 × y 1 + 5 × y2+8 × y 3

en y 1 - y 3 ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Opción 8. Maximizar la función objetivo Ф = x 2 - x 4 - 3× x5

con restricciones: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x4 - x5 = 2,

3 × x 2 + x 5 + x 6 = 5,

xyo ≥ 0, (i = 1, 6)

Solución:

Tenemos un problema de maximización inicial con un sistema de restricciones en forma de ecuaciones, es decir, un par de problemas duales tiene un tipo asimétrico 2, cuyo modelo matemático en forma matricial tiene la forma:

Problema original: Problema dual:

F = C × X máx F = B T × Ymín

en A × X = B en A T × Y ≥ C T

En el problema original, la fila de la matriz de coeficientes para las variables en función objetiva tiene la forma C = (0; 1; 0; -1; -3; 0),

la matriz-columna de términos libres y la matriz de coeficientes para variables en el sistema de restricciones tienen la forma

B = 2, A = 0 - 4 1 2 -1 0

Encontremos la matriz transpuesta de coeficientes, una matriz de filas de coeficientes para variables en la función objetivo y una matriz de columnas de términos libres.

0 1 0 0 VT = (1; 2; 5)

A T = -1 2 0 C T = -1

El problema dual se escribirá de la siguiente forma:

encuentre el valor mínimo de la función objetivo F = y 1 + 2 × y2+5 × y 3

bajo restricciones y 1 ≥ 0,

2× años 1 - 4 × y2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Opción 10. Minimizar la función Ф = x 1 + x 2 + x 3

con restricciones: 3× x1 + 9× x2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Solución:

Tenemos un problema de minimización inicial con un sistema de restricciones en forma de desigualdades, es decir, un par de problemas duales tiene una forma simétrica del tercer tipo, cuyo modelo matemático en forma matricial tiene la forma:

Problema original Problema dual

F = C × X mín F = B T × Y máx.

en A × X ≥ B en A T × Y ≤ CALLE

X ≥ 0 Y ≥ 0

En el problema original, la matriz-fila de coeficientes para variables en la función objetivo, la matriz-columna de términos libres y la matriz de coeficientes para variables en el sistema de restricciones tienen la forma

C = (1; 1; 1), B = 3, A = 6 4 5

Encontremos las matrices del problema dual.

B T = (2; 3; 4) C T = 3 A T = 9 4 2

El problema dual se formula como:

Maximizar la función objetivo F = 2y 1 + 3y 2 + 4y 3

bajo restricciones 3 × y 1 + 6 × y2+8 × y 3 ≤ 1,

9× y 1 + 4 × y2+2 × y 3 ≤ 1,

7× y 1 + 5 × y2+4 × y 3 ≤ 1,

y yo ≥ 0 (yo = 1, 2, 3)

TAREA 2.C. Resolver un problema de programación lineal utilizando tablas simplex.

Opción 7. Maximizar la función objetivo Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

con restricciones: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Solución:

Llevemos el sistema de restricciones a la forma canónica.

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Tenemos un sistema de 3 ecuaciones con 7 incógnitas. Elijamos 3 variables x 1 , z 1 , z 3 como básicas, x 2 , x 3 , x 4 , z 2 como libres y expresemos las variables básicas a través de ellas.

De (2) tenemos x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Sustituyendo en (1) y (3), obtenemos

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Creemos una tabla simplex

I iteración Tabla 1

Básico C.A.	Libertad. C.A.
x1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.

II iteración Tabla 2

x1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.

III iteración Tabla 3

x1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X3 = (1; 0; 6/7; 10/7; 0; 0; 0) F3 = 52/7.

IV iteración Tabla 4

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F4 = 149/14.

No hay una última tabla en la fila del índice. números negativos, es decir, en la expresión de la función objetivo todos Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Respuesta: Ф m ax = 149/14,

solución óptima (0; 0; 25/14; 37/14; 1/2; 0; 0)

Opción 8. Minimizar la función objetivo Ф = 5 x 1 - x 3

bajo restricciones: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 = 1,

Solución:

El número de variables es 4, el rango de la matriz es 2, por lo tanto el número de variables libres es r = 4 - 2 = 2, el número de variables básicas también es 2. Tomemos x 3, x 4 como variables libres, exprese las variables básicas x 1, x 2 en términos de libre y Reduzcamos el sistema a una base unitaria:

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Escribamos el sistema de ecuaciones y la función objetivo en una forma conveniente para la tabla simplex, es decir, x 2 + 2 x 4 = 1,

x 1 + 2 x 3 - 3 x 4 = 2

F + 11 x 3 - 15 x 4 = 10

hagamos una mesa

I iteración Tabla 1

Básico C.A.	Libertad. C.A.
X1	2	1	0		— 3		1/2
x2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) Ф 1 = 10.

II iteración Tabla 2

X3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) Ф 2 = -1.

III iteración Tabla 3

X3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X3 = (0; 0; 7/4; 1/2) F3 = -7/4.

No hay números positivos en la línea índice de la última tabla, es decir, en la expresión de la función objetivo todos Г i > 0. Tenemos el caso I, por lo tanto, la última solución básica es óptima.

Respuesta: Ф min = -7/4, solución óptima (0; 0; 7/4; 1/2)

********************

Opción 10. Minimizar la función objetivo Ф = x 1 + x 2,

bajo restricciones: x 1 –2 x 3 + x 4 = 2,

x2 – x3 + 2x4 = 1,

Solución:

El número de variables es 5, el rango de la matriz es 3, por lo tanto el número de variables libres es r = 6-3 = 2. Tomemos x 3 y x 4 como variables libres, y x 1, x 2, x 5 como los básicos. Todas las ecuaciones del sistema ya se han reducido a una unidad (las variables básicas se expresan en términos libres), pero están escritas en una forma que no es conveniente para usar tablas simplex. Escribamos el sistema de ecuaciones en la forma

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4 . = 5

Expresamos la función objetivo en términos de variables libres y la escribimos en la forma Ф - 3 x 3 +3 x 4 = 3

hagamos una mesa

I iteración Tabla 1

Básico C.A.	Libertad. C.A.
x1	2	1	0	-2	1	0	2	-1/2
x2	1	0	1	-1		0	1/2	1/2
x5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 = 3.

Tabla 2

x1	3/2	1	-1/2	-3/2	0	0
x4	1/2	0	1/2	-1/2	1	0
x5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X2 = (3/2; 0; 0; 1/2; 11/2) F2 = 3/2.

No hay números positivos en la fila del índice de la última tabla, es decir, en la expresión para la función objetivo todo Gi > 0. Tenemos el caso 1, por lo tanto, la última solución básica es óptima.

Respuesta: Ф min = 3/2, solución óptima (3/2; 0; 0; 1/2; 11/2).

Agencia Federal para la Educación

Presupuesto del Estado institución educativa

más alto educación vocacional

"Universidad Técnica Estatal de Omsk"

CÁLCULO Y TRABAJO GRÁFICO

por disciplina "TEORÍA DEL CONTROL ÓPTIMO »

en el tema "MÉTODOS DE OPTIMIZACIÓN E INVESTIGACIÓN DE OPERACIONES »

opción 7

Terminado:

estudiante por correspondencia

Grupo 4º año ZA-419

Nombre Completo: Kuzhelev S. A.

Comprobado:

Devyaterikova M. V.

Omsk – 2012
^

Tarea 1. Método gráfico para la resolución de problemas de programación lineal.

7) 7X 1 + 6X 2 → máx. 20X 1 + 6X 2 ≤ 15 16X 1 − 2X 2 ≤ 18 8X 1 + 4X 2 ≤ 20 13X 1 + 3X 2 ≤ 4 X 1 , X 2 ≥ 0.

Paso 1: construir la región factible

Las condiciones para la no negatividad de variables y cuadrados limitan el rango de sus valores permitidos al primer cuadrante. Cada una de las cuatro restricciones de desigualdad restantes del modelo corresponde a un determinado semiplano. La intersección de estos semiplanos con el primer cuadrante forma el conjunto de soluciones factibles del problema.

La primera restricción del modelo tiene la forma . Reemplazando el signo ≤ con el signo =, obtenemos la ecuación . En la Fig. 1.1 define una recta (1), que divide el plano en dos semiplanos, en en este caso por encima y por debajo de la línea. Para elegir cuál satisface la desigualdad , sustituya en él las coordenadas de cualquier punto que no se encuentre en una línea dada (por ejemplo, el origen X 1 = 0, X 2 = 0). Como obtenemos la expresión correcta (20 0 + 6 0 = 0 ≤15), entonces el semiplano que contiene el origen de coordenadas (marcado con una flecha) satisface la desigualdad. De lo contrario, otro semiplano.

Procedemos de manera similar con las restricciones restantes del problema. Se forma la intersección de todos los semiplanos construidos con el primer cuadrante. A B C D(ver figura 1). Ésta es el área factible del problema.

Paso 2. Dibujar una línea de nivel Línea de nivel La función objetivo es el conjunto de puntos del plano en los que la función objetivo toma un valor constante. Tal conjunto está dado por la ecuación F ( X) = constante. Pongamos, por ejemplo, constante = 0 y dibuja una línea en el nivel F ( X) = 0, es decir en nuestro caso línea recta 7 X 1 + 6X 2 = 0.

Esta recta pasa por el origen y es perpendicular al vector. Este vector es el gradiente de la función objetivo en el punto (0,0). El gradiente de una función es un vector de valores de las derivadas parciales de una función dada en el punto en cuestión. En el caso del problema LP, las derivadas parciales de la función objetivo son iguales a los coeficientes Ci, j = 1 , ..., norte.

El gradiente muestra la dirección del crecimiento más rápido de la función. Mover la línea de nivel de función objetivo F ( X) = constante. perpendicular a la dirección del gradiente, encontramos el último punto en el que se cruza con la región. En nuestro caso, este es el punto D, que será el punto máximo de la función objetivo (ver Fig. 2)

Se encuentra en la intersección de las líneas (2) y (3) (ver Fig. 1) y especifica la solución óptima.

^ Tenga en cuenta que si desea encontrar el valor mínimo de la función objetivo, la línea de nivel se mueve en la dirección opuesta a la dirección del gradiente.

^ Paso 3. Determinar las coordenadas del punto máximo (mínimo) y el valor óptimo de la función objetivo.

Para encontrar las coordenadas del punto C es necesario resolver un sistema formado por ecuaciones correspondientes a rectas (en este caso, ecuaciones 2 y 3):

16X 1 − 2X 2 ≤ 18

8X 1 + 4X 2 ≤ 20

Obtenemos la solución óptima = 1,33.

^ Valor óptimo función objetiva F * = F (X*) = 7 * 0 + 6 * 1,33 = 7,8

TRABAJO DE CONTROL EN LA DISCIPLINA:

“MÉTODOS DE SOLUCIONES ÓPTIMAS”

Opción número 8

1. Resolver gráficamente un problema de programación lineal. Encuentra el máximo y mínimo de la función con las restricciones dadas:

,

.

Solución

Es necesario encontrar el valor mínimo de la función objetivo y el máximo, bajo el sistema de restricciones:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Construyamos una región de soluciones factibles, es decir Resolvamos gráficamente el sistema de desigualdades. Para ello, construimos cada recta y definimos los semiplanos definidos por las desigualdades (los semiplanos se indican con un número primo).

La intersección de semiplanos será una región cuyas coordenadas puntuales satisfacen las desigualdades del sistema de restricciones del problema. Designemos los límites del área del polígono de solución.

Construyamos una línea recta correspondiente al valor de la función F = 0: F = 2x 1 +3x 2 = 0. El vector gradiente, compuesto por los coeficientes de la función objetivo, indica la dirección de minimización de F(X). El comienzo del vector es el punto (0; 0), el final es el punto (2; 3). Moveremos esta recta de forma paralela. Como estamos interesados ​​en la solución mínima, movemos la línea recta hasta que toque por primera vez el área designada. En el gráfico, esta línea recta está indicada por una línea de puntos.

Derecho
cruza la región en el punto C. Dado que el punto C se obtiene como resultado de la intersección de las líneas (4) y (1), sus coordenadas satisfacen las ecuaciones de estas líneas:
.

Habiendo resuelto el sistema de ecuaciones, obtenemos: x 1 = 3,3333, x 2 = 0.

¿Cómo podemos encontrar el valor mínimo de la función objetivo?

Consideremos la función objetivo del problema.

Construyamos una línea recta correspondiente al valor de la función F = 0: F = 2x 1 +3x 2 = 0. El vector gradiente, compuesto por los coeficientes de la función objetivo, indica la dirección de maximización de F(X). El comienzo del vector es el punto (0; 0), el final es el punto (2; 3). Moveremos esta recta de forma paralela. Como estamos interesados ​​en la solución máxima, movemos la línea recta hasta el último toque del área designada. En el gráfico, esta línea recta está indicada por una línea de puntos.

Derecho
cruza la región en el punto B. Dado que el punto B se obtiene como resultado de la intersección de las líneas (2) y (3), sus coordenadas satisfacen las ecuaciones de estas líneas:

.

¿Cómo podemos encontrar el valor máximo de la función objetivo?

Respuesta:
Y
.

2 . Resuelva un problema de programación lineal utilizando el método simplex:

.

Solución

Resolvamos un problema de programación lineal directa usando el método simplex, usando una tabla simplex.

Determinemos el valor mínimo de la función objetivo.
bajo las siguientes condiciones-restricciones:
.

Para construir el primer plan de referencia, reducimos el sistema de desigualdades a un sistema de ecuaciones introduciendo variables adicionales.

En la 1ª desigualdad de significado (≥) introducimos la variable básica X 3 con un signo menos. En la 2ª desigualdad de significado (≤) introducimos la variable básica X 4 . En la tercera desigualdad de significado (≤) introducimos la variable básica x 5 .

Introduzcamos variables artificiales. : en la 1ª igualdad introducimos una variable X 6 ;

Para reducir el problema al mínimo, escribimos la función objetivo de la siguiente manera: .

Por el uso de variables artificiales introducidas en la función objetivo, se impone la llamada penalización de M, un número positivo muy grande que normalmente no se especifica.

La base resultante se llama artificial y el método de solución se llama método de base artificial.

Además, las variables artificiales no están relacionadas con el contenido del problema, pero permiten construir un punto de partida, y el proceso de optimización obliga a estas variables a tomar valores cero y asegurar la admisibilidad de la solución óptima.

A partir de las ecuaciones expresamos variables artificiales: x 6 = 4-x 1 -x 2 +x 3, que sustituimos en la función objetivo: o.

Matriz de coeficientes
este sistema de ecuaciones tiene la forma:
.

Resolvamos el sistema de ecuaciones para las variables básicas: X 6 , X 4 , X 5.

Suponiendo que las variables libres son iguales a 0, obtenemos la primera plan de referencia:

X1 = (0,0,0,2,10,4)

La solución básica se considera admisible si no es negativa.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 4
X 5

El plan de referencia actual no es óptimo porque hay coeficientes positivos en la línea del índice. Como columna principal elegiremos la columna correspondiente a la variable x 2, ya que este es el coeficiente más grande. Calculemos los valores. D i y de ellos elegimos el más pequeño: min(4:1, 2:2, 10:2) = 1.

Por tanto, la segunda línea es la principal.

El elemento de resolución es igual a (2) y está ubicado en la intersección de la columna principal y la fila principal.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 4
X 5

Formamos la siguiente parte de la tabla simplex. En lugar de la variable x 4, el plan 1 incluirá la variable x 2.

La fila correspondiente a la variable x 2 del plan 1 se obtiene dividiendo todos los elementos de la fila x 4 del plan 0 por el elemento resolutivo RE = 2. En lugar del elemento de resolución obtenemos 1. En las celdas restantes de la columna x 2 escribimos ceros.

Así, en el nuevo plan 1, se rellenan la fila x 2 y la columna x 2. Todos los demás elementos del nuevo plan 1, incluidos los elementos de la fila índice, están determinados por la regla del rectángulo.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6
X 2
X 5
		1 1/2 +1 1/2 M

El plan de referencia actual no es óptimo porque hay coeficientes positivos en la fila del índice. Como columna principal elegiremos la columna correspondiente a la variable x 1, ya que este es el coeficiente más grande. Calculemos los valores. D i por fila como cociente de división: y de ellos elegimos el más pequeño: min (3:1 1/2, -, 8:2) = 2.

Por tanto, la primera línea es la principal.

El elemento de resolución es igual a (1 1/2) y está ubicado en la intersección de la columna principal y la fila principal.

		X 1	X 2	X 3	X 4	X 5	X 6
X 6		1 1 / 2
X 2
X 5
		-1 1 / 2 +1 1 / 2 METRO

Formamos la siguiente parte de la tabla simplex. En lugar de la variable x 6, el plan 2 incluirá la variable x 1.

Obtenemos una nueva tabla simplex:

		X 1	X 2	X 3	X 4	X 5	X 6
X 1
X 2
X 5

No hay valores positivos entre los valores de la cadena de índice. Por lo tanto, esta tabla determina el plan óptimo para el problema.

La versión final de la tabla simplex:

		X 1	X 2	X 3	X 4	X 5	X 6
X 1
X 2
X 5

Dado que no hay variables artificiales en la solución óptima (son iguales a cero), esta solución es admisible.

El plan óptimo se puede escribir de la siguiente manera: x 1 = 2, x 2 = 2:.

Respuesta:
,
.

3. La empresa Three Fat Men entrega carne enlatada desde tres almacenes ubicados en diferentes puntos de la ciudad a tres tiendas. En la tabla de transporte se presentan las existencias de alimentos enlatados disponibles en los almacenes, así como los volúmenes de pedidos en las tiendas y las tasas de entrega (en unidades monetarias convencionales).

Encuentre un plan de transporte que proporcione los costos monetarios más bajos (realice el plan de transporte inicial utilizando el método de la “esquina noroeste”).

Solución

Comprobemos la condición necesaria y suficiente para la solucion del problema:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Se cumple la condición de equilibrio. Cubre necesidades iguales. Por tanto, el modelo del problema del transporte está cerrado.

Ingresemos los datos iniciales en la tabla de distribución.

Necesidades

Utilizando el método de la esquina noroeste, construiremos el primer plan de referencia del problema de transporte.

El plan comienza a completarse desde la esquina superior izquierda.

El elemento requerido es 4. Para este elemento, los inventarios son 300, los requerimientos son 250. Como el mínimo es 250, lo restamos: .

			300 - 250 = 50
250 - 250 = 0

El elemento requerido es igual a 2. Para este elemento, los inventarios son 50, los requerimientos son 400. Como el mínimo es 50, lo restamos: .

			50 - 50 = 0
	400 - 50 = 350

El elemento requerido es 5. Para este elemento, los inventarios son 300, los requerimientos son 350. Como el mínimo es 300, lo restamos:

			300 - 300 = 0
	350 - 300 = 50

El elemento requerido es 3. Para este elemento, los inventarios son 200, los requisitos son 50. Como el mínimo es 50, lo restamos:

			200 - 50 = 150
	50 - 50 = 0

El elemento requerido es 6. Para este elemento, los inventarios son 150, los requisitos son 150. Como el mínimo es 150, lo restamos:

			150 - 150 = 0
		150 - 150 = 0

Necesidades

Introducción

La etapa actual del desarrollo humano se caracteriza por el hecho de que la era de la energía está siendo reemplazada por la era de la informática. Hay una introducción intensiva de nuevas tecnologías en todos los ámbitos de la actividad humana. Existe un problema real de transición a una sociedad de la información, para el cual el desarrollo de la educación debería convertirse en una prioridad. La estructura del conocimiento en la sociedad también está cambiando. Cada vez más importante para vida práctica Adquirir conocimientos fundamentales que contribuyan al desarrollo creativo del individuo. También son importantes la constructividad de los conocimientos adquiridos y la capacidad de estructurarlos de acuerdo con el objetivo. A partir del conocimiento se forman otros nuevos. recursos informativos sociedad. La formación y adquisición de nuevos conocimientos debe basarse en una metodología estricta de enfoque sistémico, dentro de la cual el enfoque modelo ocupa un lugar especial. Las posibilidades del enfoque modelo son extremadamente diversas, tanto en términos de los modelos formales utilizados como en los métodos de implementación de los métodos de modelado. El modelado físico permite obtener resultados confiables para sistemas bastante simples.

Actualmente, es imposible nombrar un área de la actividad humana en la que no se utilizarían métodos de modelado en un grado u otro. Esto es especialmente cierto en el ámbito de la gestión. varios sistemas, donde los principales procesos son la toma de decisiones en base a la información recibida.

1. Planteamiento del problema

función objetivo mínima

Resuelva el problema de encontrar el mínimo de la función objetivo para el sistema de restricciones especificado por el polígono de solución de acuerdo con la opción No. 16 de la tarea. El polígono de solución se muestra en la Figura 1:

Figura 1 - Polígono de soluciones al problema.

El sistema de restricciones y la función objetivo del problema se presentan a continuación:

Es necesario resolver el problema utilizando los siguientes métodos:

Método gráfico para la resolución de problemas de LP;

Método algebraico para la resolución de problemas de LP;

Método simplex para resolver problemas de LP;

Método para encontrar una solución admisible a los problemas de LP;

Solución del problema del LP dual;

Método de ramificación y unión para resolver problemas de LP con números enteros;

Método Gomori para resolver problemas LP de números enteros;

Método de Balazs para la resolución de problemas booleanos de LP.

Comparar los resultados de la solución diferentes metodos sacar conclusiones apropiadas del trabajo.

2. Solución gráfica problemas de programación lineal

El método gráfico para resolver problemas de programación lineal se utiliza en los casos en que el número de incógnitas no supera las tres. Conveniente para la investigación cualitativa de las propiedades de las soluciones y se utiliza junto con otros métodos (algebraico, ramificado y ligado, etc.). La idea del método se basa en la solución gráfica de un sistema de desigualdades lineales.

Arroz. 2 Solución gráfica del problema LP

Punto minimo

Ecuación de una recta que pasa por dos puntos A1 y A2:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

con restricciones:

Resolver un problema de programación lineal utilizando el método algebraico simplex

La aplicación de un método algebraico para resolver un problema requiere una generalización de la representación del problema PL. El sistema original de restricciones, especificado en forma de desigualdades, se convierte a una notación estándar cuando las restricciones se especifican en forma de igualdades. Transformación del sistema de restricciones a vista estándar incluye los siguientes pasos:

Transforme las desigualdades para que haya variables y términos libres a la izquierda y 0 a la derecha, es decir a lado izquierdo fue mayor o igual a cero;

Introducir variables adicionales, cuyo número sea igual al número de desigualdades en el sistema de restricciones;

Al introducir restricciones adicionales sobre la no negatividad de las variables agregadas, reemplace los signos de desigualdad con signos de igualdad estricta.

Al resolver un problema de PL mediante el método algebraico, se agrega una condición: la función objetivo debe tender al mínimo. Si esta condición no se satisface, es necesario transformar la función objetivo en consecuencia (multiplicar por -1) y resolver el problema de minimización. Una vez encontrada la solución, sustituya los valores de las variables en la función original y calcule su valor.

La solución de un problema mediante el método algebraico se considera óptima cuando los valores de todas las variables básicas no son negativos y los coeficientes de las variables libres en la ecuación de la función objetivo tampoco son negativos. Si no se cumplen estas condiciones, es necesario transformar el sistema de desigualdades, expresando unas variables en términos de otras (cambiando variables libres y básicas) para lograr el cumplimiento de las restricciones anteriores. El valor de todas las variables libres se considera igual a cero.

El método algebraico para resolver problemas de programación lineal es uno de los más métodos efectivos al resolver problemas de pequeña escala manualmente porque No requiere una gran cantidad de cálculos aritméticos. La implementación mecánica de este método es más complicada que, por ejemplo, la del método simplex, porque El algoritmo de solución que utiliza el método algebraico es hasta cierto punto heurístico y la eficacia de la solución depende en gran medida de la experiencia personal.

variables libres

callejón - adicional equipo

Se cumplen las condiciones de no negatividad, por lo que se ha encontrado la solución óptima.

3. Resolver un problema de programación lineal usando una tabla simplex

Solución: Llevemos el problema a una forma estándar para resolverlo utilizando una tabla simplex.

Reduzcamos todas las ecuaciones del sistema a la forma:

Construimos una tabla simplex:

En la esquina superior de cada celda de la tabla ingresamos los coeficientes del sistema de ecuaciones;

Seleccionamos el elemento máximo positivo en la fila F, excepto que esta será la columna general;

Para encontrar el elemento general, construimos una relación para todos los positivos. 3/3; 9/1;- relación mínima en la línea x3. Por lo tanto, la cadena general y =3, el elemento general.

Encontramos =1/=1/3. Lo llevamos a la esquina inferior de la celda donde se ubica el elemento general;

En todas las esquinas inferiores vacías de la línea general ingresamos el producto del valor en la esquina superior de la celda por;

Seleccione las esquinas superiores de la línea general;

En todas las esquinas inferiores de la columna general ingresamos el producto del valor en la esquina superior por - y seleccionamos los valores resultantes;

Las celdas restantes de la tabla se completan como productos de los elementos seleccionados correspondientes;

Luego construimos una nueva tabla en la que se intercambian las designaciones de las celdas de los elementos de la columna y fila general (x2 y x3);

Los valores que antes estaban en la esquina inferior se escriben en la esquina superior de la fila y columna general anterior;

La suma de los valores de las esquinas superior e inferior de estas celdas en la tabla anterior se escribe en la esquina superior de las celdas restantes.

4. Resolver un problema de programación lineal encontrando una solución admisible

Sea un sistema de ecuaciones algebraicas lineales:

Podemos suponer que todo lo es, de lo contrario multiplicamos la ecuación correspondiente por -1.

Introducimos variables auxiliares:

También introducimos una función auxiliar.

Minimizaremos el sistema bajo restricciones (2) y condiciones.

REGLA PARA ENCONTRAR UNA SOLUCIÓN PERMITIDA: Para encontrar una solución admisible para el sistema (1), minimizamos la forma (3) bajo las restricciones (2), tomando xj como incógnitas libres y xj como bases.

Al resolver un problema mediante el método simplex se pueden presentar dos casos:

min f=0, entonces todo i debe ser igual a cero. Y los valores resultantes de xj constituirán una solución admisible al sistema (1).

mín f>0, es decir el sistema original no tiene una solución factible.

Sistema fuente:

Se utiliza la condición del problema del tema anterior.

Introduzcamos variables adicionales:

Se ha encontrado una solución admisible al problema original: x1 = 3, x2 = 3, F = -12. Con base en la solución factible obtenida, encontraremos la solución óptima al problema original utilizando el método simplex. Para ello, construiremos una nueva tabla simplex a partir de la tabla obtenida anteriormente, eliminando la fila y la fila con la función objetivo del problema auxiliar:

Analizando la tabla simplex construida, vemos que ya se ha encontrado la solución óptima para el problema original (los elementos de la fila correspondiente a la función objetivo son negativos). Así, la solución factible encontrada al resolver el problema auxiliar coincide con la solución óptima del problema original:

6. Problema de programación lineal dual

El sistema original de restricciones y la función objetivo del problema se muestran en la siguiente figura.

con restricciones:

Solución: llevemos el sistema de restricciones a una forma estándar:

El problema dual a éste tendrá la forma:

La solución del problema dual se realizará mediante un método simplex simple.

Transformemos la función objetivo para que se resuelva el problema de minimización y escribamos el sistema de restricciones en forma estándar para resolverlo utilizando el método simplex.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Construyamos una tabla simplex inicial para resolver el problema dual LP.

Segundo paso del método simplex

Entonces, en el tercer paso del método simplex, se encontró una solución óptima al problema de minimización con los siguientes resultados: y2 = -7/8, y1 = -11/8, Ф = 12. Para encontrar el valor de la función objetivo del problema dual, sustituimos los valores encontrados de las variables básica y libre en la función de maximización:

Фmáx = - Фmín = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Dado que el valor de la función objetivo de los problemas directo y dual coincide, se encuentra la solución al problema directo y es igual a 12.

Fmín = Фmáx = -12

7. Resolver un problema de programación lineal entera utilizando el método de rama y límite

Transformemos el problema original de tal manera que la condición del número entero no se cumpla cuando se resuelva utilizando métodos convencionales.

Polígono inicial de soluciones a un problema de programación entera.

Para el polígono transformado de soluciones construimos nuevo sistema restricciones.

Anotamos el sistema de restricciones en forma de igualdades a resolver mediante el método algebraico.

Como resultado de la solución, se encontró el plan óptimo para el problema: x1 = 9/4, x2 = 5/2, F = -41/4. Esta solución no cumple con la condición de número entero establecida en el problema. Dividamos el polígono de la solución original en dos áreas, excluyendo el área 3

Polígono de solución de problema modificado

Creemos nuevos sistemas de restricciones para las áreas resultantes del polígono de solución. El área izquierda es un cuadrilátero (trapezoide). A continuación se presenta el sistema de restricciones para la región izquierda del polígono solución.

Sistema de restricción para la zona izquierda.

El área de la derecha representa el punto C.

A continuación se presenta el sistema de restricciones para la región de decisión correcta.

Los nuevos sistemas de restricciones representan dos problemas auxiliares que deben resolverse independientemente uno del otro. Resolvamos un problema de programación entera para la región izquierda del polígono solución.

Como resultado de la solución, se encontró el plan óptimo para el problema: x1 = 3, x2 = 3, F = -12. Este plan satisface la condición de que las variables del problema sean enteras y pueda aceptarse como el plan de referencia óptimo para el problema de programación lineal entera original. No tiene sentido buscar la región de solución correcta. La siguiente figura muestra el progreso de la resolución de un problema de programación lineal entera en forma de árbol.

Progreso en la resolución de un problema de programación lineal entera utilizando el método Gomori.

En muchas aplicaciones prácticas, es de gran interés un problema de programación entera en el que se da un sistema de desigualdades lineales y una forma lineal.

Se requiere encontrar una solución entera al sistema (1), que minimice la función objetivo F, y todos los coeficientes sean números enteros.

Gomori propuso uno de los métodos para resolver el problema de programación entera. La idea del método es utilizar métodos de programación lineal continua, en particular, el método simplex.

1) Utilizando el método simplex, se determina la solución al problema (1), (2), para lo cual se elimina el requisito de una solución entera; si la solución resulta ser un número entero, entonces también se encontrará la solución deseada al problema de los números enteros;

2) De lo contrario, si alguna coordenada no es un número entero, se verifica la solución resultante al problema para determinar la posibilidad de la existencia de una solución entera (la presencia de puntos enteros en un poliedro admisible):

si en cualquier fila con un término libre fraccionario todos los demás coeficientes resultan ser números enteros, entonces no hay números enteros ni puntos en el poliedro admisible y el problema de programación entera no tiene solución;

De lo contrario, se introduce una restricción lineal adicional, que corta una parte del poliedro admisible que no es prometedora para encontrar una solución al problema de programación entera;

3) Para construir una restricción lineal adicional, seleccione la l-ésima fila con un término libre fraccionario y escriba la restricción adicional

donde y son respectivamente partes fraccionarias de los coeficientes y libres

miembro. Introduzcamos una variable auxiliar en la restricción (3):

Determinemos los coeficientes incluidos en la restricción (4):

donde y son los números enteros más cercanos desde abajo para y respectivamente.

Gomori demostró que un número finito de pasos similares conduce a un problema de programación lineal cuya solución es entera y, por tanto, la deseada.

Solución: llevemos el sistema de restricciones lineales y la función objetivo a la forma canónica:

Determinemos la solución óptima al sistema de restricciones lineales, descartando temporalmente la condición de número entero. Usamos el método simplex para esto. A continuación, secuencialmente en las tablas, se presenta la solución original del problema y se dan las transformaciones de la tabla original para obtener la solución óptima al problema:

Resolución de problemas booleanos de LP mediante el método Balazs.

Crea tu propia versión para un problema de programación lineal entera con variables booleanas, teniendo en cuenta las siguientes reglas: el problema utiliza al menos 5 variables, al menos 4 restricciones, los coeficientes de las restricciones y la función objetivo se eligen arbitrariamente, pero en tal de manera que el sistema de restricciones sea compatible. La tarea es resolver el LCLP con variables booleanas utilizando el algoritmo de Balazs y determinar la reducción en la complejidad de los cálculos en relación con la resolución del problema utilizando el método de búsqueda exhaustiva.

Ejecución de restricciones

valor f

Limitación de filtrado:

Determinación de la reducción del esfuerzo computacional.

La solución al problema utilizando el método de búsqueda exhaustiva es 6*25=192 expresiones calculadas. La solución al problema utilizando el método Balazs es 3*6+(25-3)=47 expresiones calculadas. La reducción total de la complejidad de los cálculos en relación con la resolución del problema mediante el método de búsqueda exhaustiva es:

Conclusión

El proceso de diseño de sistemas de información que implementan nuevas tecnologías de la información se mejora constantemente. La atención de los ingenieros de sistemas se centra cada vez más en sistemas complejos, lo que dificulta el uso de modelos físicos y aumenta la importancia de los modelos matemáticos y la simulación mecánica de sistemas. La simulación de máquinas se ha convertido en una herramienta eficaz para estudiar y diseñar sistemas complejos. La relevancia de los modelos matemáticos aumenta continuamente debido a su flexibilidad, adecuación a los procesos reales y el bajo costo de implementación sobre la base de las PC modernas. Cada vez se ofrecen más oportunidades al usuario, es decir, al especialista en modelado de sistemas mediante tecnología informática. El uso de modelos es especialmente eficaz en las primeras etapas del diseño de sistemas automatizados, cuando el coste de las decisiones erróneas es más significativo.

Las herramientas informáticas modernas han permitido aumentar significativamente la complejidad de los modelos utilizados en el estudio de sistemas; se ha hecho posible construir modelos combinados, analíticos y de simulación que tengan en cuenta toda la variedad de factores que ocurren en los sistemas reales, es decir, , el uso de modelos más adecuados a los fenómenos en estudio.

Literatura:

1. Lyashchenko I.N. Programación lineal y no lineal / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K.: “Escuela superior”, 1975, 372 p.

2. Pautas para completar un proyecto de curso en la disciplina "Matemáticas Aplicadas" para estudiantes de la especialidad "Sistemas y Redes Computacionales" de tiempo completo y tiempo parcial / Compilado por: I.A. Balakireva, A.V. Skatkov - Sebastopol: SevNTU Editorial, 2003. - 15 p.

3. Pautas para el estudio de la disciplina “Matemáticas Aplicadas”, sección “Métodos de búsqueda global y minimización unidimensional” / Comp. A. V. Skatkov, I. A. Balakireva, L. A. Litvinova - Sebastopol: Editorial SevGTU, 2000. - 31 p.

4. Pautas para el estudio de la disciplina "Matemáticas Aplicadas" para estudiantes de la especialidad "Sistemas y Redes Computacionales" Sección "Resolución de problemas de programación lineal entera" para educación a tiempo completo y parcial / Compilado por: I.A. Balakireva, A.V. Skatkov - Sebastopol : Editorial SevNTU, 2000. - 13 p.

5. Akulich I.L. Programación matemática en ejemplos y problemas:

6. Libro de texto subsidio para estudiantes de economía. especialista. universidades.-M.: Superior. escuela, 1986.- 319 p., ill.

7. Andronov S.A. Métodos de diseño óptimos: Texto de conferencias / SPbSUAP. San Petersburgo, 2001. 169 p.: enfermo.

Documentos similares

Algoritmo para la resolución de problemas de programación lineal mediante el método simplex. Construcción de un modelo matemático de un problema de programación lineal. Resolver un problema de programación lineal en Excel. Búsqueda de ganancias y plan de producción óptimo.

trabajo del curso, añadido el 21/03/2012


Resolución de problemas gráficos. Elaboración de un modelo matemático. Determinación del valor máximo de la función objetivo. Solución por el método simplex con base artificial del problema de programación lineal canónica. Comprobando la optimidad de la solución.

prueba, añadido el 05/04/2016


Bases teóricas de la programación lineal. Problemas de programación lineal, métodos de solución. Análisis de la solución óptima. Solución de un problema de programación lineal de índice único. Planteamiento del problema y entrada de datos. Etapas de construcción y solución del modelo.

trabajo del curso, añadido el 09/12/2008


Construcción de un modelo matemático. Selección, justificación y descripción del método para la resolución de un problema de programación lineal directa mediante el método simplex, utilizando una tabla simplex. Formulación y solución de un problema dual. Análisis de sensibilidad del modelo.

trabajo del curso, añadido el 31/10/2014


Construcción de un modelo matemático con el fin de obtener el máximo beneficio para la empresa, solución gráfica del problema. Resolviendo el problema usando el complemento SOLVER. Análisis de cambios en las reservas de recursos. Determinación de los límites para cambiar los coeficientes de la función objetivo.

trabajo del curso, añadido el 17/12/2014


Programación matemática. Programación lineal. Problemas de programación lineal. Método gráfico para la resolución de problemas de programación lineal. Formulación económica del problema de programación lineal. Construcción de un modelo matemático.

trabajo del curso, añadido el 13/10/2008


Resolver un problema de programación lineal por método gráfico, comprobándolo en MS Excel. Análisis de la estructura interna de resolución de un problema en un programa. Optimización del plan de producción. Resolver el problema mediante el método simplex. Sistema de colas multicanal.

prueba, añadido el 02/05/2012


Resolución de un problema de programación lineal mediante el método simplex: planteamiento del problema, construcción de un modelo económico y matemático. Resolver el problema del transporte mediante el método potencial: construir el plan de referencia inicial, determinando su valor óptimo.

prueba, añadido el 11/04/2012


Planteamiento del problema de programación no lineal. Determinación de puntos estacionarios y su tipo. Construcción de líneas de nivel, gráfica tridimensional de la función objetivo y restricciones. Solución gráfica y analítica del problema. Manual de usuario y diagrama de algoritmo.

trabajo del curso, añadido el 17/12/2012


Análisis de la solución a un problema de programación lineal. Método simplex utilizando tablas simplex. Modelado y resolución de problemas de LP en una computadora. Interpretación económica de la solución óptima al problema. Formulación matemática del problema del transporte.