Método simplex generalizado. Gran enciclopedia de petróleo y gas. Un ejemplo de resolución de un problema directo y dual utilizando el método simplex.

11.4. MÉTODO SIMPLEX DOBLE

De los resultados de los párrafos anteriores se deduce que para obtener una solución problema original podemos ir al dual y, usando estimaciones de su plan optimo, definir solución óptima tarea original.

La transición al problema dual no es necesaria, ya que si consideramos la primera tabla simplex con una base adicional unitaria, es fácil notar que el problema original está escrito en las columnas y el dual, en las filas.

Como se demostró, al resolver un problema directo en cualquier iteración, la diferencia, es decir. magnitud -coeficiente de la variable, es igual a la diferencia entre los lados derecho e izquierdo de la restricción correspondiente problema dual. Si, al resolver un problema directo con una función objetivo maximizada, la iteración no conduce a una solución óptima, entonces al menos para una variable y solo en el óptimo para todas diferencia .

Considerando esta condición teniendo en cuenta la dualidad, podemos escribir

.

Así, si, Eso . Esto significa que cuando la solución al problema directo es subóptima, la solución al problema dual no es factible. Allende en . De ello se deduce que la solución óptima del problema directo corresponde a una solución admisible del problema dual.

Esto hizo posible desarrollar un nuevo método para resolver problemas. programación lineal, cuando se utiliza, primero se obtiene una solución inaceptable, pero "mejor que óptima" (en el método simplex habitual, primero se encuentra aceptable, Pero subóptimo solución). Nuevo método, llamado método simplex dual, asegura el cumplimiento de las condiciones de optimidad para la solución y su “aproximación” sistemática a la región soluciones admisibles. Cuando la solución resultante resulta factible, finaliza el proceso iterativo de cálculos, ya que esta solución también es óptima.

Método simplex dual permite resolver problemas de programación lineal cuyos sistemas de restricciones, con base positiva, contienen términos libres de cualquier signo. Este método le permite reducir el número de transformaciones del sistema de restricciones, así como el tamaño. tabla simplex. Consideremos la aplicación del método simplex dual usando un ejemplo.

Ejemplo. Encuentra el mínimo de una función.

bajo restricciones

.

Pasemos a la forma canónica:

bajo restricciones

La tabla simplex inicial tiene la forma

Básico variables	incógnita 1	incógnita 2	incógnita 3	incógnita 4	incógnita 5	Solución
incógnita 3 incógnita 4 incógnita 5	–3 –4	–1 –3				–3 –6
	–2	–1

Solución básica inicialóptimo, pero no aceptable.

Al igual que el método simplex habitual, el método de solución considerado se basa en el uso de condiciones de admisibilidad y optimización.

Condición de admisibilidad. La variable básica negativa más grande en valor absoluto se selecciona como variable excluida (si hay alternativas, la elección se hace arbitrariamente). Si todas las variables base son no negativas, el proceso de cálculo finaliza, ya que la solución resultante es factible y óptima.

Condición optimidad. La variable incluida en la base se selecciona entre las variables no básicas de la siguiente manera. Se calculan las razones de los coeficientes del lado izquierdo.-ecuaciones a los coeficientes correspondientes de la ecuación asociada a la variable excluida. Relaciones con personas positivas o valor cero Los denominadores no se tienen en cuenta. En un problema de minimización, la variable de entrada debe corresponder al menor de relaciones especificadas, y en el problema de maximización, la relación que es la más pequeña en valor absoluto (si hay alternativas, la elección se hace arbitrariamente). Si los denominadores de todas las razones son cero o positivos, el problema no tiene soluciones factibles.

Después de seleccionar las variables que se incluirán en la base y se excluirán para obtener próxima decisión Se realiza la operación habitual de conversión de filas de una tabla simplex.

En este ejemplo, la variable excluida es. Los ratios calculados para determinar la nueva variable base se detallan en la siguiente tabla:

variables	incógnita 1	incógnita 2	incógnita 3	incógnita 4	incógnita 5
Ecuación incógnita 4 - ecuación	–2 –4	–1 –3
Actitud

La variable incluida está seleccionada. incógnita 2. La conversión de cadenas posterior da como resultado una nueva tabla simplex:

Básico variables	incógnita 1	incógnita 2	incógnita 3	incógnita 4	incógnita 5	Solución
incógnita 3 incógnita 2 incógnita 5						–1 –1

Nueva solución También es óptimo, pero sigue siendo inaceptable. Como nueva variable excluida elegimos (arbitrariamente) incógnita 3. Definamos la variable a incluir.

variables	incógnita 1	incógnita 2	incógnita 3	incógnita 4	incógnita 5
Ecuación incógnita 4 - ecuación
actitud

consideremos método simplex para resolver problemas de programación lineal (LP). Se basa en la transición de un plan de referencia a otro, durante la cual aumenta el valor de la función objetivo.

El algoritmo del método simplex es el siguiente:

1. Traducimos el problema original a vista canónica introduciendo variables adicionales. Para desigualdades de la forma ≤, las variables adicionales se introducen con un signo (+), pero si son de la forma ≥, entonces con un signo (-). Se introducen variables adicionales en la función objetivo con los signos correspondientes con un coeficiente igual a 0 , porque la función objetivo no debería cambiar su significado económico.
2. Los vectores están escritos. pi a partir de los coeficientes de las variables y la columna de términos libres. Esta acción determina el número de vectores unitarios. La regla es que debe haber tantos vectores unitarios como desigualdades en el sistema de restricciones.
3. Después de esto, los datos de origen se ingresan en una tabla simplex. Los vectores unitarios se introducen en la base y, al excluirlos de la base, se encuentra la solución óptima. Los coeficientes de la función objetivo se escriben con signo opuesto.
4. Un signo de optimización para un problema de PL es que la solución es óptima si en F– en la fila todos los coeficientes son positivos. Regla para encontrar la columna de habilitación - vista F– una cadena y entre sus elementos negativos se selecciona el más pequeño. Vector pi su contención se vuelve permisiva. La regla para elegir un elemento de resolución: se compilan las proporciones de los elementos positivos de la columna de resolución a los elementos del vector. P 0 y el numero que da proporción más pequeña se convierte en un elemento de resolución con respecto al cual se recalculará la tabla simplex. La línea que contiene este elemento se llama línea de habilitación. Si no hay elementos positivos en la columna de resolución, entonces el problema no tiene solución. Después de determinar el elemento de resolución, se procede al recálculo de una nueva tabla simplex.
5. Reglas para completar una nueva tabla simplex. La unidad se coloca en lugar del elemento de resolución y se supone que los demás elementos son iguales. 0 . El vector de resolución se suma a la base, de la cual se excluye el vector cero correspondiente, y los vectores de base restantes se escriben sin cambios. Los elementos de la cadena de resolución se dividen por el elemento de resolución y los elementos restantes se recalculan de acuerdo con la regla del rectángulo.
6. Esto se hace hasta F– todos los elementos de la cadena no se volverán positivos.

Consideremos resolver el problema usando el algoritmo discutido anteriormente.
Dado:

Llevamos el problema a forma canónica:

Componemos los vectores:

Complete la tabla simplex:

:
Recalculemos el primer elemento del vector. P 0, para lo cual hacemos un rectángulo de números: y obtenemos: .

Realizamos cálculos similares para todos los demás elementos de la tabla simplex:

En el plan recibido F– la línea contiene un elemento negativo – ​​(-5/3), vector P 1. Contiene en su columna el único elemento positivo, que será el elemento resolutivo. Recalculemos la tabla con respecto a este elemento:

No hay elementos negativos en F– línea significa encontrado plan optimo:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Programación lineal, M: Nauka, 1998,
• Ventzel E.S. Investigación de operaciones, M: Radio Soviética, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. programación matemática, M: Escuela de posgrado, 1986

Solución de programación lineal personalizada

Puede solicitar cualquier tarea en esta disciplina en nuestro sitio web. Puedes adjuntar archivos y especificar plazos en

Método simplex dual

El método simplex dual, al igual que el método simplex, se utiliza para encontrar una solución a un problema de programación lineal escrito en forma de problema principal, para el cual entre los vectores Pi compuestos por coeficientes de incógnitas en el sistema de ecuaciones, existe metro soltero. Al mismo tiempo, el método simplex dual se puede utilizar para resolver un problema de programación lineal, cuyos términos libres del sistema de ecuaciones pueden ser cualquier número(al resolver el problema utilizando el método simplex, se supuso que estos números no eran negativos). Consideremos ahora tal problema, habiendo asumido previamente que los vectores son unitarios, es decir, consideraremos el problema que consiste en determinar el valor máximo de la función.

bajo condiciones

y entre los números los hay negativos.

EN en este caso Hay una solución al sistema. ecuaciones lineales(55). Sin embargo, esta solución no es un plan para el problema (54) - (56), ya que entre sus componentes hay números negativos.

Dado que los vectores son vectores unitarios, cada uno de los vectores se puede representar como una combinación lineal de estos vectores y los coeficientes de descomposición de vectores en vectores son números.

Así se puede encontrar:

A partir de los datos iniciales, se compila una tabla simplex en la que algunos elementos de la columna del vector son números negativos. Si no existen tales números, entonces el plan óptimo para el problema (54) - (56) se escribe en la tabla simplex, ya que, por supuesto, todo. Por tanto, para determinar el plan óptimo del problema, siempre que exista, se debe realizar una transición ordenada de una tabla simplex a otra hasta que se excluyan los elementos negativos de la columna del vector P0. En este caso, todos los elementos deben permanecer no negativos en todo momento ( t+1)ª línea, es decir para cualquiera

Así, después de compilar una tabla simplex, verifican si hay números negativos en la columna del vector Po. Si no hay ninguno, entonces se encuentra el plan óptimo para el problema original. Si existen (lo cual suponemos), elija el número negativo que sea mayor en valor absoluto. En el caso de que haya varios números de este tipo, tome uno de ellos: deje que este número b yo . La elección de este número determina el vector excluido de la base, es decir, en este caso el vector se deriva de la base. PAG yo . Para determinar qué vector se debe ingresar en la base, encontramos

Déjalo ser valor mínimo se acepta en j=r, entonces el vector se introduce en la base R r . El número es el elemento resolutivo. La transición a una nueva tabla simplex se realiza mediante reglas normales método simplex. El proceso iterativo continúa hasta que la columna del vector R 0 ya no serán números negativos. En este caso se encuentra el plan óptimo para el problema original y por tanto el dual. Si en algún paso resulta que iésima fila de la tabla simplex en la columna de vectores R 0 es un número negativo b i, y no hay elementos negativos entre los elementos restantes de esta línea, entonces el problema original no tiene solución.

Por lo tanto, encontrar una solución a un problema utilizando el método simplex dual incluye los siguientes pasos:

• 1. Encuentre un pseudoplan para el problema.
• 2. Verifique que este pseudoplan sea óptimo. Si el pseudoplan es óptimo, entonces se ha encontrado una solución al problema. De lo contrario, establecen la insolubilidad del problema o pasan a un nuevo pseudoplan.
• 3. Seleccione la línea de resolución determinando el mayor en valor absoluto número negativo vector de columna R 0 y la columna de resolución encontrando la proporción de elementos de valor absoluto más pequeña ( metro+1)-y líneas a los correspondientes elementos negativos de la línea de resolución.
• 4. Encuentre un nuevo pseudoplan y repita todas las acciones a partir de la etapa 2.

Encontrar valor máximo funciones

bajo condiciones:

Solución. Escribamos el problema de programación lineal original en la forma del problema principal: encuentre el máximo de la función en las condiciones

Creemos un problema dual para el último problema. Este es un problema cuya solución requiere encontrar el valor mínimo de la función

Construimos una tabla simplex:

Iteración 0:

La condición de admisibilidad se cumple, ya que todos los valores en la columna "Solución" son positivos, pero la condición de optimidad no se cumple, ya que la línea contiene un coeficiente negativo. Continuamos con nuestras acciones.

Iteración 1:

.
Reduzcamos el sistema de restricciones al sistema de desigualdades de significado ≤ multiplicando las líneas correspondientes por (-1).
Determinemos el valor mínimo de la función objetivo F(X) = x 1 + x 2 bajo las siguientes condiciones de restricción.
- 5x 1 - 6x 2 ≤-1
- 15x 1≤-1
- 7x 1 - 12x 2 ≤-1
Para construir el primer plan de referencia, reducimos el sistema de desigualdades a un sistema de ecuaciones introduciendo variables adicionales ( transición a la forma canónica).
En la 1ª desigualdad de significado (≤) introducimos la variable básica x 3 . En la segunda desigualdad de significado (≤) introducimos la variable básica x 4 . En la tercera desigualdad de significado (≤) introducimos la variable básica x 5 .
-5x 1 -6x 2 + 1x 3 + 0x 4 + 0x 5 = -1
-15x 1 + 0x 2 + 0x 3 + 1x 4 + 0x 5 = -1
-7x 1 -12x 2 + 0x 3 + 0x 4 + 1x 5 = -1
La matriz de coeficientes A = a(ij) de este sistema de ecuaciones tiene la forma:

A=	-5	-6	1	0	0
	-15	0	0	1	0
	-7	-12	0	0	1

Variables básicas Se trata de variables que se incluyen en una sola ecuación del sistema de restricciones y, además, con un coeficiente unitario.
Resolvamos el sistema de ecuaciones para las variables básicas:
x3, x4, x5,
Creyendo que variables libres son iguales a 0, obtenemos el primero plan de referencia:
X1 = (0,0,-1,-1,-1)
Solución básica se considera admisible si no es negativo.

	B	x1	x2	x3	x4	x5
	-1	-5	-6	1	0	0
	-1	-15	0	0	1	0
	-1	-7	-12	0	0	1
	0	-1	-1	0	0	0

.
El plan 0 en una tabla simplex es un pseudoplan, por lo que determinamos la fila y la columna principales.
.

La línea principal será la primera línea y la variable x 3 debe derivarse de la base.
.
El valor mínimo de θ corresponde a la 2ª columna, es decir la variable x 2 debe ingresarse en la base.
En la intersección de la fila y la columna principales hay un elemento de resolución (RE) igual a (-6).

	B	x1	x2	x3	x4	x5
	-1	-5	-6	1	0	0
	-1	-15	0	0	1	0
	-1	-7	-12	0	0	1
	0	-1	-1	0	0	0
	0	-1: (-5) = 1 / 5	-1: (-6) = 1 / 6	-	-	-

4. Nuevo cálculo de la tabla simplex..

	B	x1	x2	x3	x4	x5
	1 / 6	5 / 6	1	-1 / 6	0	0
	-1	-15	0	0	1	0
	1	3	0	-2	0	1
	1 / 6	-1 / 6	0	-1 / 6	0	0

	x1	x2	x3	x4	x5
	5 / 6: 1	1: 1	-1 / 6: 1	0: 1	0: 1
1-(1 / 6 0):1	-15-(5 / 6 0):1	0-(1 0):1	0-(-1 / 6 0):1	1-(0 0):1	0-(0 0):1
	3-(5 / 6 0):1	0-(1 0):1	-2-(-1 / 6 0):1	0-(0 0):1	1-(0 0):1
1 / 6 -(1 / 6 0):1	-1 / 6 -(5 / 6 0):1	0-(1 0):1	-1 / 6 -(-1 / 6 0):1	0-(0 0):1	0-(0 0):1

1. Comprobación del criterio de optimización.
El plan 1 en una tabla simplex es un pseudoplan, por lo que determinamos la fila y la columna principales.
2. Definición de una nueva variable libre.
Entre valores negativos variables base, elegimos el módulo más grande.
La línea principal será la segunda línea y la variable x 4 debe derivarse de la base.
3. Definición de una nueva variable básica.
El valor mínimo de θ corresponde a la 1.ª columna, es decir la variable x 1 debe ingresarse en la base.
En la intersección de la fila y la columna principales hay un elemento de resolución (RE) igual a (-15).

	B	x1	x2	x3	x4	x5
	1 / 6	5 / 6	1	-1 / 6	0	0
	-1	-15	0	0	1	0
	1	3	0	-2	0	1
	1 / 6	-1 / 6	0	-1 / 6	0	0
	0	-1 / 6: (-15) = 1 / 90	-	-	-	-

4. Nuevo cálculo de la tabla simplex..
Realizamos transformaciones de la tabla simplex mediante el método de Jordano-Gauss.

	B	x1	x2	x3	x4	x5
	1 / 9	0	1	-1 / 6	1 / 18	0
	1 / 15	1	0	0	-1 / 15	0
	4 / 5	0	0	-2	1 / 5	1
	8 / 45	0	0	-1 / 6	-1 / 90	0

Presentemos el cálculo de cada elemento en forma de tabla:

	x1	x2	x3	x4	x5
1 / 9 -(1 / 15 0):1	0-(1 0):1	1-(0 0):1	-1 / 6 -(0 0):1	1 / 18 -(-1 / 15 0):1	0-(0 0):1
	1: 1	0: 1	0: 1	-1 / 15: 1	0: 1
4 / 5 -(1 / 15 0):1	0-(1 0):1	0-(0 0):1	-2-(0 0):1	1 / 5 -(-1 / 15 0):1	1-(0 0):1
8 / 45 -(1 / 15 0):1	0-(1 0):1	0-(0 0):1	-1 / 6 -(0 0):1	-1 / 90 -(-1 / 15 0):1	0-(0 0):1

En la columna de base, todos los elementos son positivos.
Pasemos al algoritmo principal del método simplex.
1. Comprobación del criterio de optimización.
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:

	B	x1	x2	x3	x4	x5
	1 / 9	0	1	-1 / 6	1 / 18	0
	1 / 15	1	0	0	-1 / 15	0
	4 / 5	0	0	-2	1 / 5	1
	8 / 45	0	0	-1 / 6	-1 / 90	0

El plan óptimo se puede escribir de la siguiente manera:
x1 = 1/15
x2 = 1/9
F(X) = 1 1/9 + 1 1/15 = 8/45

Como hay tres vectores unitarios, entonces
Puedes escribir inmediatamente el plan de referencia.
X=(0,0,0,360,192,180).
Creemos una tabla simplex cero

Comprobamos el plan de referencia resultante.
para la optimidad.
Calculamos el valor de la función objetivo y
diferencias simples.
F0 c P0 0 360 0 192 0 180 0,
1 z1 c1 c P1 c1 9,
2 z2 c2 cP2 c2 10,...

Como se puede ver en la tabla 0, distinto de cero
son las variables x4, x5, x6 y x, x, x
1
2
3
son iguales a cero, porque No son básicos, pero sí gratuitos.
Variables adicionales x4, x5, x6
tomar sus valores de acuerdo a
restricciones.
Estos valores de variables corresponden a esto.
"plan" según el cual no se produce nada, materias primas
no se utiliza y el valor de la función objetivo es
cero, es decir, el costo de los productos manufacturados.
ausente.
Este plan, por supuesto, no es óptimo.
Esto también se puede ver en la cuarta fila de la tabla, en la que
hay tres puntuaciones negativas: 9, -16 y -10.

10.

Los números negativos no son sólo
indican la posibilidad de aumentar
costo total de los productos manufacturados (en
columnas encima de calificaciones negativas
son números positivos), pero también
muestra cuánto aumentará esta cantidad
al introducir una unidad de esto o aquello en el plan
tipo de producto.
Entonces, el número -9 significa que cuando se incluye en
plan de producción para un producto A
proporciona un aumento en el costo
productos para 9 unidades

11.

Si incluye en el plan de producción para
un producto B y C, entonces el costo total
los productos manufacturados aumentarán
respectivamente en 10 y 16 unidades. Por lo tanto, con
punto económico ver apropiado
es la inclusión de los productos C en el plan.
Lo mismo debe hacerse desde ese punto.
ver que -16 es el más pequeño
valoración negativa. Entonces, a la base
introduzcamos el vector P3.

12.

Encontremos el número Q.
360 192 180
Qmín
;
;
mín 30; 24;60
3
12 8
Ingresémoslo en la última columna de la tabla.
El número 24 corresponde al vector P5.
192/8=24 desde el punto de vista económico
significa cuántos productos C
la empresa puede producir teniendo en cuenta
Tasas de consumo y volúmenes disponibles de materias primas.
cada tipo.

13.

Dado que se dispone de materias primas de cada tipo.
respectivamente 360, 192 y 180 kg, y para uno
El producto C requiere el gasto de materias primas para cada
tipos 12, 8 y 3 kg, entonces el número máximo
productos C que se pueden fabricar
empresa es igual
mín(360/12,192/8,180/3)=192/8=24, es decir
factor limitante para la producción
productos C es el volumen disponible de materias primas
2do tipo. Teniendo en cuenta su empresa puede
producir 24 productos C. En este caso, las materias primas del segundo tipo se utilizarán por completo y,
Esto significa que el vector debe ser excluido de
P5
base.

14.

Creemos la siguiente tabla. en eso
la segunda línea es permisiva,
y la columna de resolución es la tercera. En
su intersección contiene el elemento 8.
Divide la segunda línea por 8 y luego
cero usando el método de Jordan-Gauss
o según las fórmulas del triángulo tercero.
columna.

15.

16.

Calculemos las diferencias simplex y completemos la cuarta fila de la tabla.
Con este plan de producción
24 artículos C se producen y permanecen
72 kg de materia prima sin usar 1º y 108 kg
Materias primas del tercer tipo. 2do tipo de materia prima utilizada
completamente. El costo de todos los productos en
a este respecto es 384 u.m. Especificado
los números están escritos en la columna Plan. es otra vez
parámetros de la tarea, pero han sido sometidos
cambios. Los datos de otros también han cambiado.
columnas. Su contenido económico
se ha vuelto aún más complejo.

17.

Hay una calificación negativa -2.
El plan se puede mejorar. Introduzcamos en la base.
vector P2. calculemos
72 24 108
Q mín.;
;
mín 8; 48;72 8.
9 1/ 2 3 / 2
.
Derivamos de la base P4.

18.

Las líneas permisivas serán la 1ª línea y la 2ª
columna. Elemento permisivo 9.
Divida la primera línea entre 9, complete
1ra linea nueva mesa, entonces
Restablezcamos la segunda columna. Para esto
multiplica la primera línea por (-1/2) y
suma al 2do y luego multiplica el 1ro
línea por (-3/2) y agregar a la tercera línea.
Completemos la tabla 2.

19.

20.

Estamos convencidos de esto
calcular diferencias simplex
1 cP1 c1 10 1 16 0,25 9 5,
2 cP2 c2 10 1 16 0 10 0,
3 cP3 c3 10 0 16 1 0 0 16 0,
4 cP4 c4 10 1/ 9 16 1/ 8 0 (1/ 6) 2 / 9,
5 cP5 -c5 =10 (-1/6)+16 5/24+0(-1/2)=5/3,
6 0.

21.

El plan de producción óptimo no es
Se prevé la producción de productos A. Introducción a.
plan de producción para productos tipo A conduciría a
reducción del coste total indicado.
Esto se puede ver en la cuarta línea de la columna, donde el número es 5.
muestra que con este plan la inclusión
la salida de una unidad del producto A conduce a él
sólo a una disminución en el valor total
valor por 5 unidades
Entonces, el plan prevé el lanzamiento de 8 productos.
B y 20 productos C. Materias primas de los tipos 1 y 2
se utiliza en su totalidad y el tipo 3 queda con 96 kg sin utilizar.

22. PROBLEMAS DE PROGRAMACIÓN LINEAL DOBLE

Cada ZLP se puede combinar
problema llamado dual al original
tarea.
Considere el problema del uso
recursos. Supongamos que la empresa A
produce n tipos de productos, valor
cuya liberación está determinada por variables
x1, x2, ..., xn
.
En producción m diferente
tipos de recursos, cuyo volumen es limitado
valores b1, b2, ..., bn.

23.

Se conocen las tasas de costo de cada recurso por unidad.
cada tipo de producto formando una matriz,
a11
a21
A
...
am1
a12
a22
...
soy 2
...a1n
... a2 norte
... ...
... amn
así como el costo por unidad de producción de cada tipo
c1, c2, ..., cn
Es necesario organizar la producción para que
la empresa A recibió el máximo
ganancia.

24.

La tarea se reduce a encontrar
variables no negativas
x1, x2, ..., xn,
en el que el consumo de recursos no es
excede su número especificado, y
el costo de todos los productos alcanzará
máximo.

25.

En forma matemática el problema
está escrito de la siguiente forma:
F c1 x1 c2 x2 ... c j x j ... cn xn máx
bajo condiciones
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a21 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
.
...............................................................,
a x a x ... a x ... a x b
mj j
Minnesota
metro
m1 1 m 2 2
x j 0, j 1, norte.

26.

Con base en los mismos datos iniciales, puede ser
Se ha formulado otra tarea.
Supongamos que la empresa B decide comprar
todos los recursos disponibles para la empresa A. B
En este caso, la empresa B necesita establecer
precios óptimos para estos recursos, basados ​​en
siguientes condiciones:
costo total de los recursos para la empresa B
debe ser mínimo;
para cada tipo de recurso, la empresa A necesita
pagar no menos de la cantidad que
la empresa puede recibir durante el procesamiento
de este tipo de recurso en productos terminados.

27.

Si se denota por y1, y2, ..., yn
precios a los que la empresa B
compra recursos de la empresa A, luego
la tarea se reduce a lo siguiente: encontrar
tales valores de las variables y1, y2, ..., yn,
en el que el coste de los recursos,
gastado por unidad de cualquier tipo
Los productos no son menos que las ganancias (precios).
para esta unidad de producción, y el total
el costo de los recursos alcanza
mínimo,

28.

es decir, ¿cuál debería ser la calificación unitaria?
cada uno de los recursos y1, y2, ..., yn,
de modo que para volúmenes dados
recursos disponibles bi , dado
cuesta c j (j 1, n) unidades
productos y estándares de costos aij
minimizar evaluación general costos
para todos los productos.

29. Mat. modelo de problema dual

En forma matemática el problema
se escribe como:
*
F b1 y1 b2 y2 ... bm ym min
bajo restricciones
a11 y1 a21 y2 ... am1 ym c1 ,
a y a y ... a y c ,
m2m
2
12 1 22 2
..................................................
a y a y ... a y c ,
mn m
norte
1norte 1 2norte 2
yi 0, i 1, 2,..., metro.

30. Significado económico de las variables del problema dual

Variables yi del problema dual en la literatura.
puede tener diferentes nombres: contable, implícito,
evaluaciones sombra, determinadas objetivamente,
valoraciones duales o “precios” de los recursos.
Estas dos tareas forman un par mutuamente
problemas duales, cualquiera de los cuales puede
ser considerado como original. La solución a uno
tareas proporciona un plan de producción óptimo
productos, y la solución es diferente: óptima
sistema de clasificación de materias primas utilizadas para
producción de estos productos.

31.

Problemas duales de lineal.
la programación se llama
simétricos si satisfacen
las siguientes propiedades:
número de variables en un problema dual
es igual al número de restricciones del problema original, y
número de restricciones del problema dual
igual al número igual al número de variables en
original;
en un problema se busca el máximo del objetivo
funciones, en el otro – un mínimo;
coeficientes para variables en el objetivo
las funciones de una tarea son gratuitas
miembros del sistema de restricciones de otro problema;

32.

en cada problema el sistema de restricciones se especifica en
en forma de desigualdades y, en el problema de encontrar
máximo, todas las desigualdades de la forma “≤”, y en el problema de
encontrar el mínimo, todas las desigualdades de la forma “≥”;
matriz de coeficientes del sistema de restricciones
uno se obtiene del otro por transposición;
cada restricción de un problema corresponde
variable de otra tarea, número variable
coincide con el número de restricción;
condiciones para la no negatividad de las variables
se guardan en ambas tareas;

33. Resolver problemas duales simétricos

Primer teorema de la dualidad.
Si uno de los problemas duales
tiene una solución óptima, entonces
otro tiene una solución óptima
tarea, mientras que los valores objetivo
Las funciones de las tareas son iguales entre sí.
Si la función objetivo es una de
Las tareas no están limitadas, luego otra tarea.
no tiene solución alguna

34. Contenido económico del primer teorema de la dualidad

Si el problema de determinar el plan óptimo,
maximizar la producción es solucionable, entonces
El problema de determinar las estimaciones de recursos también tiene solución.
Además, el precio del producto obtenido como resultado.
La implementación del plan óptimo coincide con
valoración total de los recursos.
Coincidencias de valores funciones objetivo Para
soluciones correspondientes a un par de problemas duales
suficiente para que estas decisiones sean
óptimo.
Decidir ZLP usando el método simplex, estamos al mismo tiempo
Resolvemos tanto el problema original como el dual.

35. Método para la solución simultánea de un par de problemas duales.

Problema original: Problema dual:
F c1x1 c2 x2 ... c j x j ... F * b1 y1 b2 y2 ...
cn xn máximo
a11 x1 a12 x2 ... a1n xn xn 1 b1 ,
a21 x1 a22 x2 ... a2 n xn xn 2 b2 ,
..........................................................
a x a x ... a x x b ,
Minnesota
m
metro
m1 1 m 2 2
x j 0, j 1, 2,..., n m.
bm ym min,
a11 y1 a21 y2 ... am1 ym ym 1 c1 ,
a y a y ... a y y c ,
m2m
metros 2
2
12 1 22 2
.............................................................
a y a y ... a y y c ,
mn m
mn
norte
1norte 1 2norte 2
yi 0, i 1, 2,..., m n.

36.

El número de variables en los problemas es el mismo.
y es igual a m + n. En el problema original
las variables básicas son

variables xn 1 , xn 2 , ..., xn m
,
y en el problema dual –
auxiliar no negativo
variables yn 1, yn 2, ..., yn m.
Variables básicas de un problema.
las variables libres corresponden
otra tarea y viceversa.

37.

38.

En decisión del PP Usando el método tabular simplex para resolver el problema dual.
contenida en la última fila de la tabla.
Este es j.
Además, las principales variables de la dualidad

adicional correspondiente
variables del problema original, y
variables adicionales del dual
las tareas están contenidas en columnas,
correspondiente a la principal
variables iniciales (originales)
tareas.

39. Ejemplo.

Formulemos un modelo del problema dual.
al problema del ejemplo 2 (comienzo de la conferencia):
Encuentra el máximo de una función.

40.

41.

Las variables del problema original x1, x2, x3 son la cantidad productos A, B y C. Introduzcamos
variables del problema dual y1, y2, y3
Encuentra el mínimo de una función.
F * 360 y1 192 y2 180 y3 min
bajo restricciones
18 y1 6 y2 5 y3 9,
15 y1 4 y2 3 y3 10,
12 y 8 y 3 y 16,
2
3
1
y1, y2, y3 0.

42. Considere la última tabla del problema original.

43.

El valor de y1 en la última fila de la columna P4,
aquellos. y1 2 ;
9 años 5
valor 2 3 en la última fila de la columna P5,
el valor de y3 0 en la última fila de la columna P6.
Los valores restantes se encuentran en las columnas 1,2,3.
2 5
Y (; ;0;5;0;0)
9 3
Al mismo tiempo
2
5
F 360 192 180 0 0 5 0 0 0 0 400
9
3
*
-Este costos mínimos para todos los productos.
2/9 y 5/3 son precios sombra de las materias primas del 1º y 2º
especies respectivamente.