Se llama al valor óptimo de la función objetivo. Resolver problemas de programación lineal utilizando el método gráfico.

Construyamos en el plano un conjunto de soluciones factibles del sistema de desigualdades lineales y encontremos geométricamente el valor mínimo de la función objetivo.

Construimos líneas rectas en el sistema de coordenadas x 1 x 2

Encontramos los semiplanos definidos por el sistema. Dado que las desigualdades del sistema se satisfacen para cualquier punto del semiplano correspondiente, basta con comprobarlas para cualquier punto. Usamos el punto (0;0). Sustituyamos sus coordenadas en la primera desigualdad del sistema. Porque , entonces la desigualdad define un semiplano que no contiene el punto (0;0). De manera similar definimos los semiplanos restantes. Encontramos el conjunto de soluciones factibles como la parte común de los semiplanos resultantes; esta es el área sombreada.

Construimos un vector y una línea de nivel cero perpendicular a él.

Moviendo la recta (5) en la dirección del vector y vemos que el punto máximo de la región estará en el punto A de la intersección de la recta (3) y la recta (2). Encontramos la solución al sistema de ecuaciones:

Esto significa que entendimos el punto (13;11) y.

Moviendo la recta (5) en la dirección del vector y vemos que el punto mínimo de la región estará en el punto B de la intersección de la recta (1) y la recta (4). Encontramos la solución al sistema de ecuaciones:

Esto significa que obtuvimos el punto (6;6) y.

2. Una empresa de muebles produce armarios y mesas de ordenador combinados. Su producción está limitada por la disponibilidad de materias primas (tableros de alta calidad, herrajes) y el tiempo de funcionamiento de las máquinas que las procesan. Para cada armario se necesitan 5 m2 de tablas, para una mesa, 2 m2. Los accesorios cuestan $10 por un gabinete y $8 por una mesa. La empresa puede recibir de sus proveedores hasta 600 m2 de tableros al mes y accesorios por un valor de $2.000. Cada gabinete requiere 7 horas de operación de la máquina y la mesa requiere 3 horas. En total se pueden utilizar un total de 840 horas de funcionamiento de la máquina al mes.

¿Cuántos gabinetes combinados y mesas de computadora debe producir una empresa por mes para maximizar las ganancias si un gabinete genera $100 de ganancias y cada escritorio genera $50?

• 1. Redactar modelo matemático problema y resolverlo mediante el método simplex.
• 2. Crea un modelo matemático del problema dual, escribe su solución en base a la solución del original.
• 3. Establecer el grado de escasez de los recursos utilizados y justificar la rentabilidad del plan óptimo.
• 4. Explorar las posibilidades de seguir aumentando la producción en función del uso de cada tipo de recurso.
• 5. Evalúe la viabilidad de introducir un nuevo tipo de producto: estanterías, si la fabricación de una estantería cuesta 1 m 2 de tableros y accesorios por valor de 5 dólares, y es necesario dedicar 0,25 horas de funcionamiento de la máquina y el beneficio de la venta de un estante cuesta $20.
• 1. Construyamos un modelo matemático para este problema:

Denotemos por x 1 el volumen de producción de gabinetes y x 2 el volumen de producción de mesas. Creemos un sistema de restricciones y una función objetivo:

Resolvemos el problema mediante el método simplex. Escribámoslo en forma canónica:

Escribamos los datos de la tarea en forma de tabla:

tabla 1

Porque Ahora que todos los deltas son mayores que cero, entonces es imposible aumentar aún más el valor de la función objetivo f y hemos obtenido un plan óptimo.

TRABAJO DE CONTROL EN LA DISCIPLINA:

“MÉTODOS DE SOLUCIONES ÓPTIMAS”

Opción número 8

1. Decidir método gráfico 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 función objetivo tareas .

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

Trabajo de laboratorio nº 1. Resolución de problemas de programación lineal.

objetivo del trabajo Adquirir habilidades en la resolución de problemas de programación lineal utilizando métodos gráficos, simplex y Excel.

El problema de la programación lineal es estudiar formas de encontrar los valores máximos o mínimos de una función lineal en presencia de restricciones lineales. Una función objetivo es una función cuyo valor máximo o mínimo se encuentra. El conjunto de valores de variables en el que se alcanzan los valores máximos o mínimos se denomina solución óptima (plan óptimo), cualquier otro conjunto de valores que satisfaga las restricciones se denomina solución admisible (plan admisible).

Método de solución geométrica I Veamos problemas de programación lineal usando un ejemplo.

Ejemplo. Encuentre el valor máximo de la función objetivo. l=2X 1 +2X 2 bajo restricciones dadas

Solución. Construyamos el dominio de solución del sistema de restricciones, cambiando los signos de desigualdades por signos de igualdades exactas:

yo 1: 3X 1 -2X 2 +6=0,

yo 2: 3X 1 +X 2 -3=0,

yo 3:X 1 -3=0.

DCON

2 0 1 3 X 1

(yo 1) (yo 3)

Derecho yo 1 divide el avión X ACERCA DE en en dos semiplanos, de los cuales es necesario elegir uno que satisfaga la primera desigualdad del sistema (3). Para hacer esto, tomemos t. ACERCA DE(0; 0) y sustitúyalo en la desigualdad. Si es cierto, entonces es necesario sombrear el semiplano de la línea recta en la que se encuentra el llamado. ACERCA DE(0; 0). Haz lo mismo con las líneas rectas. yo 2 y yo 3. El dominio de soluciones a las desigualdades (3) es un polígono. A B CD. Para cada punto del plano la función l toma un valor fijo l=l 1 . El conjunto de todos los puntos actuales es una línea recta. l=C 1 X 1 +C 2 X 2 (en nuestro caso l=2X 1 +2X 2), perpendicular al vector CON(Con 1 ;Con 2) (CON(2; 2)), procedente del origen. Si esta línea se mueve en la dirección positiva del vector Con, entonces la función objetivo l aumentará, de lo contrario disminuirá. Así, en nuestro caso, la línea recta a la salida del polígono. A B CD las decisiones pasarán por el llamado EN(3; 7.5), y por tanto incl. EN la función objetivo toma el valor máximo, es decir l máx =2ּ3+2ּ7,5=21. De manera similar, se determina que el valor mínimo que toma la función es D(1; 0) y l mín =2ּ1+2ּ0=2.

El algoritmo del método simplex para resolver un problema de programación lineal es el siguiente.

1. tarea general La programación lineal se reduce a un problema canónico (las restricciones contienen signos iguales) introduciendo tantas variables auxiliares como desigualdades haya en el sistema de restricciones.

2. La función objetivo se expresa a través de variables básicas y auxiliares.

3. Se compila la primera tabla simplex. Las variables respecto de las cuales se permite el sistema de restricciones se escriben en la base (es mejor tomar variables auxiliares como base). La primera fila de la tabla enumera todas las variables y proporciona una columna para términos libres. Los coeficientes de la función objetivo con signos opuestos están escritos en la última fila de la tabla.

4. Cada tabla simplex da una solución a un problema de programación lineal: las variables libres son iguales a cero, las variables básicas son iguales a los términos libres, respectivamente.

5. El criterio de optimización es la ausencia de elementos negativos en la última fila de la tabla para resolver el problema máximo y elementos positivos para el mínimo.

6. Para mejorar la solución es necesario pasar de una tabla simplex a otra. Para hacer esto, busque una columna clave en la tabla anterior que corresponda al elemento negativo más pequeño en la última fila de la tabla en el problema máximo y al coeficiente positivo más grande en el problema mínimo. Luego se encuentra una fila clave correspondiente a la proporción mínima de términos libres con respecto a los elementos positivos correspondientes de la columna clave. En la intersección de una columna clave y una fila clave se encuentra el elemento clave.

7. Comenzamos a completar la siguiente tabla simplex completando la base: la variable correspondiente a la fila clave se deriva de la base y la variable correspondiente a la columna clave se ingresa en su lugar. Los elementos de la cadena clave anterior se obtienen dividiendo el elemento anterior por el elemento clave. Los elementos de la columna clave anterior se convierten en ceros, excepto el elemento clave, que es uno. Todos los demás elementos se calculan utilizando la regla del rectángulo:

8. Se realiza la transformación de tablas simplex hasta obtener un plan óptimo.

Ejemplo. Encuentra el valor máximo de una función.
, si variables
satisfacer el sistema de restricciones:

Solución. 1. Introducir nuevas variables
, con la ayuda del cual transformamos las desigualdades del sistema en ecuaciones:

Cambiamos el signo de los coeficientes de la función objetivo o lo escribimos en la forma
. Completamos la primera tabla simplex, en la línea cero escribimos X 1 ,X 2 y (cuotas gratuitas). En la columna cero - X 3 ,X 4 ,X 5 y F. Completamos esta tabla usando el sistema de ecuaciones resultante y la función objetivo transformada.

Verificamos el criterio de optimización para encontrar el valor máximo: en la última línea, todos los coeficientes deben ser positivos. Este criterio no se cumple, por lo que procedemos a elaborar la segunda tabla.

2. Encuentre el elemento resolutivo de la primera tabla de la siguiente manera. Entre los elementos de la última fila, seleccionamos el coeficiente negativo más grande en magnitud (esto es -3) y tomamos la segunda columna como resolutiva. Si todos los coeficientes de la columna no son positivos, entonces
.

Para determinar la fila de resolución, dividimos los coeficientes libres en los elementos correspondientes de la columna de resolución y seleccionamos la proporción mínima, mientras no tomamos coeficientes negativos. Tenemos
, la segunda línea es permisiva. La intersección de la fila y la columna de resolución da el elemento de resolución: este es 3.

3. Complete la segunda tabla simplex. Las variables en cuya intersección obtenemos un elemento de resolución se intercambian, es decir Y . Reemplazamos el elemento de resolución con su inverso, es decir sobre el. Los elementos de la fila y columna de resolución (excepto el elemento de resolución) se dividen en el elemento de resolución. En este caso cambiamos el signo de los coeficientes de la columna de resolución.

Los elementos restantes de la segunda tabla se obtienen usando la regla del rectángulo a partir de los elementos de la primera tabla. Para la celda a llenar y la celda con el elemento de resolución, hacemos un rectángulo. Luego, al elemento de la celda a llenar le restamos el producto de los elementos de los otros dos vértices, dividido por el elemento resolutivo. Mostremos los cálculos usando esta regla para completar la primera fila de la segunda tabla:

.

Continuamos completando las tablas según estas reglas hasta cumplir el criterio. Disponemos de dos mesas más para nuestra tarea.

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

4. El resultado de ejecutar este algoritmo se escribe de la siguiente manera. En la tabla final, el elemento en la intersección de la fila.
y columna b, da el valor máximo de la función objetivo. En nuestro caso
. Los valores de las variables de fila son iguales a los coeficientes libres. Para nuestro problema tenemos
.

Hay otras formas de compilar y completar tablas simplex. Por ejemplo, para la etapa 1, todas las variables y coeficientes libres se registran en la línea cero de la tabla. Después de encontrar el elemento de resolución usando las mismas reglas en la siguiente tabla, reemplazamos la variable en la columna cero, pero no en la fila. Dividimos todos los elementos de la línea de permiso por el elemento de permiso y los escribimos en una nueva tabla. Para los elementos restantes de la columna de resolución escribimos ceros. A continuación, realizamos el algoritmo especificado teniendo en cuenta estas reglas.

Al resolver un problema de programación lineal para un mínimo, se selecciona el coeficiente positivo más grande en la última línea y se ejecuta el algoritmo especificado hasta que no haya coeficientes positivos en la última línea.

La resolución de problemas de programación lineal utilizando Excel se realiza de la siguiente manera.

Para resolver problemas de programación lineal, utilice el complemento Búsqueda de soluciones. Primero debe asegurarse de que este complemento esté presente en la pestaña Datos del grupo Análisis (para 2003, consulte Herramientas). Si falta el comando Buscar una solución o el grupo Análisis, debe descargar este complemento.

Para hacer esto, haga clic en Archivo de Microsoft Office (2010), luego haga clic en el botón Opciones de Excel. En la ventana Opciones de Excel que aparece, seleccione el cuadro Complementos a la izquierda. En el lado derecho de la ventana, el valor del campo Control debe establecerse en Complementos de Excel, haga clic en el botón "Ir", que se encuentra al lado de este campo. En la ventana Complementos, seleccione la casilla de verificación junto a Buscar una solución y haga clic en Aceptar. Luego podrá trabajar con el complemento Search for Solutions instalado.

Antes de llamar a Buscar una solución, debe preparar datos para resolver un problema de programación lineal (a partir de un modelo matemático) en una hoja de trabajo:

1) Determinar las celdas en las que se colocará el resultado de la solución para esto, en la primera línea ingresamos las variables y la función objetivo. No completamos la segunda línea (celdas cambiables), en estas celdas se obtendrá el resultado óptimo. Ingrese los datos de la función objetivo en la siguiente línea y el sistema de restricciones (coeficientes para incógnitas) en las siguientes líneas. Lado derecho Se introducen restricciones (coeficientes libres), dejando una celda libre después de registrar los coeficientes del sistema de restricciones.

2) Introducir una dependencia de celdas variables para la función objetivo y una dependencia de celdas variables para las partes izquierdas del sistema de restricciones en las celdas libres restantes. Para introducir fórmulas de dependencia es conveniente utilizar la función matemática SUMAPRODUCTO.

A continuación, debe utilizar el complemento Buscar una solución. En la pestaña Datos, en el grupo Análisis, seleccione Buscar una solución. Aparecerá el cuadro de diálogo Buscar Solución, el cual se debe completar de la siguiente manera:

1) Especifique la celda que contiene la función objetivo en el campo "Optimizar función objetivo" (esta celda debe contener la fórmula para la función objetivo). Seleccione la opción para optimizar el valor de la celda objetivo (maximización, minimización):

2) En el campo “Cambiar celdas variables”, ingrese las celdas a cambiar. En el siguiente campo "De acuerdo con las restricciones", ingrese las restricciones especificadas usando el botón "Agregar". En la ventana que aparece, ingrese las celdas que contienen las fórmulas del sistema de restricciones, seleccione el signo de restricción y el valor de la restricción (coeficiente libre):

3) Marque la casilla de verificación "Hacer que las variables sin restricciones no sean negativas". Seleccione el método de solución “Búsqueda de soluciones a problemas lineales mediante el método simplex”. Después de hacer clic en el botón "Buscar solución", comienza el proceso de resolución del problema. Como resultado, aparece el cuadro de diálogo "Resultados de la búsqueda de soluciones" y la tabla original con celdas llenas para los valores de las variables y el valor óptimo de la función objetivo.

Ejemplo. Resuelva un problema de programación lineal utilizando el complemento de solución de Excel: encuentre el valor máximo de una función
bajo restricciones

,

;

,
.

Solución. Para resolver nuestro problema, ejecutemos el algoritmo especificado en una hoja de cálculo de Excel. Ingrese los datos iniciales en forma de tabla.

Introducimos dependencias para la función objetivo y el sistema de restricciones. Para hacer esto, ingrese la fórmula =SUMPRODUCT(A2:B2;A3:B3) en la celda C2. En las celdas C4 y C5, respectivamente, las fórmulas son: =SUMPRODUCTO(A2:B2,A4:B4) y =SUMPRODUCT(A2:B2,A5:B5). Como resultado, obtenemos una mesa.

Ejecute el comando "Buscar una solución" y complete la ventana Buscar una solución que aparece de la siguiente manera. En el campo "Optimizar función objetivo", ingrese la celda C2. Seleccione la optimización del valor de la celda objetivo "Máximo".

En el campo "Cambiar celdas variables", ingrese las celdas cambiantes A2:B2. En el campo "De acuerdo con las restricciones", ingrese las restricciones especificadas usando el botón "Agregar". Referencias a la celda $C$4:$C$5 Referencias a restricciones =$D$4:$D$5 entre ellas signo<= затем кнопку «ОК».

Marque la casilla de verificación "Hacer que las variables sin restricciones no sean negativas". Seleccione el método de solución “Búsqueda de soluciones a problemas lineales mediante el método simplex”.

Al hacer clic en el botón "Buscar solución" se inicia el proceso de resolución del problema. Como resultado, aparece el cuadro de diálogo "Resultados de la búsqueda de soluciones" y la tabla original con celdas llenas para los valores de las variables y el valor óptimo de la función objetivo.

En el cuadro de diálogo "Resultados de la búsqueda de soluciones", guarde el resultado x1=0,75, x2=0,75, F=1,5 - igual al valor máximo de la función objetivo.

Tareas para el trabajo independiente.

Ejercicio 1. Usando métodos gráficos, simplex y herramientas de Excel, encuentre el valor máximo y mínimo de una función F(X) bajo un determinado sistema de restricciones.

1. F(X)=10X 1 +5X 2 2. F(X)=3X 1 -2X 2

3. F(X)=3X 1 +5X 2 4. F(X)=3X 1 +3X 2

5. F(X)=4X 1 -3X 2 6. F(X)=2X 1 -X 2

7. F(X)=-2X 1 +4X 2 8. F(X)=4X 1 -3X 2

9. F(X)=5X 1 +10X 2 10. F(X)=2X 1 +X 2

11. F(X)=X 1 +X 2 12. F(X)=3X 1 +X 2

13. F(X)=4X 1 +5X 2 14. F(X)=3X 1 +2X 2

15. F(X)=-X 1 -X 2 16. F(X)=-3X 1 -5X 2

17. F(X)=2X 1 +3X 2 18. F(X)=4X 1 +3X 2

19. F(X)=-3X 1 -2X 2 20. F(X)=-3X 1 +4X 2

21. F(X)=5X 1 -2X 2 22. F(X)=-2X 1 +3X 3

23. F(X)=2X 1 +3X 2 24. F(X)=4X 1 +3X 2

25. F(X)=-3X 1 -2X 2 26. F(X)=-3X 1 +4X 2

27. F(X)=-2X 1 +4X 2 28. F(X)=4X 1 -3X 2

29. F(X)=-X 1 -X 2 30. F(X)=-3X 1 -5X 2

Preguntas de control.

1. ¿Qué problemas se llaman problemas de programación lineal?

2. Dé ejemplos de problemas de programación lineal.

3. ¿Cómo se resuelve un problema de programación lineal mediante el método gráfico?

4. Describir el algoritmo del método simplex para resolver problemas de programación lineal.

5. Describir un algoritmo para resolver problemas de programación lineal usando Excel.

Agencia Federal para la Educación

Institución educativa presupuestaria del estado

educación profesional superior

"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 este caso por encima de la recta y por debajo de ella. 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 de la función objetivo. F * = F (X*) = 7 * 0 + 6 * 1,33 = 7,8