Dividimos a terceira linha pelo elemento chave igual a 5, obtemos a terceira linha da nova tabela.

As colunas de base correspondem a colunas únicas.

Cálculo dos valores restantes da tabela:

"BP - Plano Básico":

; ;

"x1": ; ;

"x5": ; .

Os valores da linha do índice são não negativos, portanto obtemos a solução ótima: , ; .

Responda: o lucro máximo da venda de produtos manufaturados, igual a 160/3 unidades, é assegurado pela liberação de apenas produtos do segundo tipo no valor de 80/9 unidades.

Tarefa número 2

O problema de programação não linear é dado. Encontre o máximo e o mínimo da função objetivo usando um método gráfico-analítico. Componha a função de Lagrange e mostre que as condições mínimas (máximas) suficientes são satisfeitas nos pontos extremos.

Porque o último dígito da cifra é 8, então A=2; B=5.

Porque o penúltimo dígito da cifra é 1, então você deve escolher a tarefa número 1.

Decisão:

1) Vamos desenhar a área que o sistema de desigualdades define.

Esta área é um triângulo ABC com as coordenadas dos vértices: A(0; 2); B(4; 6) e C(16/3; 14/3).

Os níveis da função objetivo são círculos centrados no ponto (2; 5). Os quadrados dos raios serão os valores da função objetivo. Então a figura mostra que o valor mínimo da função objetivo é alcançado no ponto H, o valor máximo está no ponto A ou no ponto C.

O valor da função objetivo no ponto A: ;

O valor da função objetivo no ponto C: ;

Isso significa que o valor máximo da função é atingido no ponto A(0; 2) e é igual a 13.

Vamos encontrar as coordenadas do ponto H.

Para isso, considere o sistema:

ó

ó

Uma linha é tangente a um círculo se a equação tem uma única solução. Uma equação quadrática tem uma solução única se o discriminante for 0.

Então ; ; - o valor mínimo da função.

2) Componha a função de Lagrange para encontrar a solução mínima:

No x 1 =2.5; x 2 =4.5 Nós temos:

ó

O sistema tem uma solução para , ou seja. condições extremas suficientes são satisfeitas.

Compomos a função de Lagrange para encontrar a solução máxima:

Condições suficientes para um extremo:

No x 1 =0; x 2 =2 Nós temos:

ó ó

O sistema também tem uma solução, ou seja, condições extremas suficientes são satisfeitas.

Responda: o mínimo da função objetivo é alcançado em ; ; a função objetivo máxima é atingida quando ; .

Tarefa número 3

Duas empresas recebem fundos no valor d unidades. Quando alocado à primeira empresa por um ano x unidades de fundos que fornece renda k 1 x unidades, e quando alocado para a segunda empresa y unidades de fundos, proporciona rendimentos k 1 y unidades. O saldo de fundos no final do ano para a primeira empresa é igual a nx, e para o segundo minha. Como distribuir todos os fundos dentro de 4 anos para que a renda total seja a maior? Resolva o problema por programação dinâmica.

i=8, k=1.

A=2200; k1 =6; k2=1; n=0,2; m=0,5.

Decisão:

Todo o período de 4 anos é dividido em 4 etapas, cada uma das quais é igual a um ano. Vamos numerar as etapas a partir do primeiro ano. Sejam X k e Y k os fundos alocados respectivamente às empresas A e B no k-ésimo estágio. Então a soma X k + Y k =a k é a quantidade total de recursos usados ​​na k - essa etapa e restante da etapa anterior k - 1. na primeira etapa todos os fundos alocados são usados ​​e a 1 = 2200 unidades. a receita que será recebida no k - nessa fase, quando as unidades X k e Y k forem alocadas, será 6X k + 1Y k . deixe a receita máxima recebida nos últimos estágios a partir do k - esse estágio é f k (a k) unidades. Vamos escrever a equação funcional de Bellman expressando o princípio da otimalidade: qualquer que seja o estado inicial e a solução inicial, a solução subsequente deve ser ótima em relação ao estado obtido como resultado do estado inicial:

Para cada estágio, você precisa escolher o valor X k e o valor Y k=ak- Xk. Com isso em mente, encontraremos a renda no k-ésimo estágio:

A equação funcional de Bellman terá a seguinte aparência:

Considere todas as etapas, começando com a última.

(já que o máximo da função linear é alcançado no final do segmento em x 4 = a 4);

Agência Federal de Educação

Instituição de ensino do orçamento do estado

ensino profissional superior

"Universidade Técnica Estadual de Omsk"

CÁLCULO E TRABALHO GRÁFICO

pela disciplina"TEORIA DE CONTROLE ÓTIMO »

sobre o tema"MÉTODOS DE OTIMIZAÇÃO E PESQUISA OPERACIONAL »

opção 7

Concluído:

estudante por correspondência

Grupo do 4º ano ZA-419

Nome: Kuzhelev S.A.

Verificado:

Devyaterikova M.V.

Omsk - 2012
^

Tarefa 1. Método gráfico para resolução de problemas de programação linear.

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.

Etapa 1. Construindo uma área válida

As condições de não negatividade de variáveis ​​e quadrados limitam o intervalo de seus valores admissíveis ao primeiro quadrante. Cada uma das quatro desigualdades-restrições restantes do modelo corresponde a algum semiplano. A interseção desses semiplanos com o primeiro quadrante forma o conjunto de soluções viáveis ​​para o problema.

A primeira restrição do modelo é . Substituindo o sinal ≤ nele pelo sinal =, obtemos a equação . Na fig. 1.1 define uma linha (1) que divide o plano em dois semiplanos, neste caso acima e abaixo da linha. Para escolher qual satisfaz a desigualdade , substituímos nela as coordenadas de qualquer ponto que não esteja na linha dada (por exemplo, a origem X 1 = 0, X 2 = 0). Como obtemos a expressão correta (20 0 + 6 0 = 0 ≤15), o semiplano contendo a origem (marcado com uma seta) satisfaz a desigualdade. Caso contrário, outro semiplano.

Procedemos da mesma forma com as demais restrições do problema. A interseção de todos os semiplanos construídos com o primeiro quadrante forma ABCD(ver fig. 1). Este é o escopo válido da tarefa.

Etapa 2. Construindo uma linha de nível Linha de nível função objetivo é um conjunto de pontos no plano em que a função objetivo assume um valor constante. Tal conjunto é dado pela equação f ( x) = const. Vamos colocar, por exemplo, const = 0 e desenhe uma linha no nível f ( x) = 0, ou seja no nosso caso, direto 7 x 1 + 6x 2 = 0.

Esta linha passa pela origem e é perpendicular ao vetor . Este vetor é o gradiente da função objetivo em (0,0). O gradiente de uma função é um vetor de valores das derivadas parciais de uma determinada função no ponto em questão. No caso do problema LP, as derivadas parciais da função objetivo são iguais aos coeficientes Ceu, j = 1 , ..., n.

O gradiente mostra a direção do crescimento mais rápido da função. Movendo a linha de nível da função objetivo f ( x) = const. perpendicular à direção do gradiente, encontre o último ponto onde ele cruza com a área. No nosso caso, este é o ponto D, que será o ponto máximo da função objetivo (ver Fig. 2)

Encontra-se na intersecção das linhas (2) e (3) (ver Fig. 1) e define a solução ótima.

^ Observe que se você deseja encontrar o valor mínimo da função objetivo, a linha de nível é movida na direção oposta à direção do gradiente.

^ Etapa 3. Determinando as coordenadas do ponto máximo (mínimo) e o valor ideal da função objetivo

Para encontrar as coordenadas do ponto C, é necessário resolver um sistema composto pelas equações diretas correspondentes (neste caso, das equações 2 e 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Obtemos a solução ótima = 1,33.

^ O valor ótimo da função objetivo f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

Decisão: encontre o valor máximo e mínimo da função \(f (x, y)\) sob as seguintes restrições $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \ \begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(cases) $$
É aconselhável usar o método gráfico de resolução do problema para problemas com duas variáveis ​​que são escritas de forma simétrica, bem como para problemas com muitas variáveis, desde que sua notação canônica não contenha mais de duas variáveis ​​livres.

Neste caso, uma tarefa com duas variáveis.

Algoritmo para resolver o problema "interpretação geométrica de um problema de programação linear":

1. Vamos construir o domínio das soluções admissíveis no plano xOy.
2. Selecione a área de soluções não negativas.

4. Vamos construir uma família de funções objetivo.
5. Encontre o valor máximo (mínimo) da função objetivo.

1. Construímos o domínio de soluções admissíveis do problema \(D\).

Para construir a área de soluções viáveis:
1) Construímos linhas de fronteira:
transformamos as desigualdades em igualdades e, em seguida, na equação de uma linha reta em segmentos nos eixos da forma \(\frac(x)(a)+\frac(y)(b) = 1\), então \ (x=a\) é um segmento cortado no eixo Ox, \(y=b\) - no eixo Oy $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(casos) => \begin(casos) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ Para cada linha, separe segmentos nos eixos e conecte-os. Temos as linhas certas.

2) Encontramos semiplanos que satisfazem as desigualdades dadas:
Para a desigualdade \(2x+3y\geq 6\) é o semiplano que fica acima da linha \(2x+3y = 6\). CA direto
Para a desigualdade \(3x-2y\leq 18 => -3x+2y \geq -18\) é um semiplano que fica acima da linha \(3x-2y = 18\). CB direto
Para a desigualdade \(-x+2y\leq 8\) é o semiplano que fica abaixo da linha \(-x+2y = 8\). AB direto

O domínio das soluções factíveis é definido como a parte comum dos três semiplanos correspondentes às desigualdades dadas. Esta área é um triângulo \(ABC\)

A região \(D\) é o triângulo \(ABC\) ver fig.

2. Selecione a área de soluções não negativas.

A região de soluções não negativas está localizada no primeiro trimestre e é uma parte comum de todos os cinco semiplanos, três dos quais são a região \(D\) obtida a partir de desigualdades e adicionalmente duas desigualdades \(x \geq 0\ ) - o semiplano superior (quartos I e II) e \(y \geq 0\) - o semiplano direito (quartos I e IV), que expressam a condição de não negatividade das variáveis ​​\(x; y\). Obteve a área desejada de soluções não negativas \(DEBFG\)

3.Encontre as coordenadas dos vértices da região.
As coordenadas dos quatro vértices já são conhecidas (são os pontos de intersecção das linhas com os eixos).
Vamos anotar essas coordenadas:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Encontre as coordenadas do ponto \(B\), como os pontos de interseção das linhas \(-x+2y = 8\) e \(3x-2y = 18\). Resolva o sistema de equações e encontre as coordenadas deste ponto $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(casos)=> \begin(casos) x = 13\\ y =10.5\end(casos)$$
Obtemos as coordenadas do ponto \(B(13;10.5)\)

4. Construímos uma família de funções objetivo.
A equação \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) define no plano xOy uma família de círculos concêntricos centrados no ponto com coordenadas \ (Q(4 ;3)\), cada um dos quais corresponde a um determinado valor do parâmetro \(f\). Como você sabe, para a equação de um círculo o parâmetro \(f=R^2\).

Vamos representar no mesmo sistema de coordenadas uma família de círculos concêntricos \(f\) e uma família de linhas. O problema de determinar o ponto de máximo (mínimo) do ponto \(f\) será reduzido a encontrar na área admissível o ponto por onde passa o círculo da família \(f=const\), que é responsável pela maior (menor) valor do parâmetro \(f\).

5. Encontre o valor máximo (mínimo) da função objetivo.

Valor mínimo da função objetivo: Aumentando gradualmente o raio do círculo, obtivemos que o primeiro vértice pelo qual o círculo passa é o ponto \(G(3;0)\). A função objetivo neste ponto será mínima e igual a \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

O valor máximo da função objetivo: Aumentando ainda mais o raio do círculo, obtivemos que o último vértice pelo qual o círculo passará é o ponto \(B(13;10.5)\). A função objetivo neste ponto será máxima e igual a \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\)

Você pode verificar a correção da solução substituindo as coordenadas dos vértices restantes na equação da função objetivo:
no vértice \(D(0;2)\) o valor da função objetivo é igual a \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
no vértice \(E(0;4)\) o valor da função objetivo é igual a \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
no vértice \(F(6;0)\) o valor da função objetivo é \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Percebido

Responda:
o valor mínimo da função objetivo \(f_(min) = 10\)
o valor máximo da função objetivo \(f_(max) = 137,25\)

função objetiva- função real ou inteira de várias variáveis, passíveis de otimização (minimização ou maximização) para resolver algum problema de otimização. O termo é usado em programação matemática, pesquisa operacional, programação linear, teoria da decisão estatística e outras áreas da matemática, principalmente de natureza aplicada, embora o objetivo da otimização também possa ser a solução de um problema matemático em si. Além da função objetivo no problema de otimização, as variáveis ​​podem estar sujeitas a restrições na forma de um sistema de igualdades ou desigualdades. No caso geral, os argumentos da função objetivo podem ser especificados em conjuntos arbitrários.

Exemplos

Funções suaves e sistemas de equações

O problema de resolver qualquer sistema de equações

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_) (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\direita.)

pode ser formulado como um problema de minimização da função objetivo

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1))

Se as funções são suaves, então o problema de minimização pode ser resolvido por métodos de gradiente.

Para qualquer função objetivo suave, pode-se igualar a 0 (\displaystyle 0) as derivadas parciais em relação a todas as variáveis. A função objetivo ótima será uma das soluções para tal sistema de equações. No caso da função (1) (\displaystyle (1)) este será um sistema de equações de mínimos quadrados (LSM). Qualquer solução do sistema original é uma solução do sistema de mínimos quadrados. Se o sistema original for inconsistente, então o sistema LSM, que sempre tem uma solução, torna possível obter uma solução aproximada do sistema original. O número de equações do sistema LSM coincide com o número de incógnitas, o que às vezes facilita a solução de sistemas iniciais conjuntos.

Programação linear

Outro exemplo bem conhecido de uma função objetivo é uma função linear que ocorre em problemas de programação linear. Ao contrário da função objetivo quadrática, a otimização de uma função linear só é possível se houver restrições na forma de um sistema de igualdades ou desigualdades lineares.

Otimização combinatória

Um exemplo típico de uma função objetivo combinatória é a função objetivo do problema do caixeiro viajante. Esta função é igual ao comprimento do ciclo hamiltoniano no gráfico. Ela é dada no conjunto de permutações n − 1 (\displaystyle n-1) de vértices do grafo e é determinada pela matriz de comprimento de aresta do grafo. A solução exata de tais problemas muitas vezes se resume à enumeração de opções.

Capítulo 1. Apresentação do principal problema de programação linear

1. Programação linear

A programação linear é um ramo da programação matemática que estuda métodos para resolver problemas extremos que são caracterizados por uma relação linear entre variáveis ​​e um critério linear. Tais tarefas encontram amplas aplicações em várias esferas da atividade humana. Um estudo sistemático de problemas desse tipo começou em 1939-1940. nas obras de L. V. Kantorovich.

Os problemas matemáticos de programação linear incluem o estudo de situações econômicas e produtivas específicas, que de uma forma ou de outra são interpretadas como problemas de uso ótimo de recursos limitados.

A gama de problemas resolvidos usando métodos de programação linear é bastante ampla, como por exemplo:

o problema do uso ótimo dos recursos no planejamento da produção;

o problema das misturas (planejamento da composição dos produtos);

o problema de encontrar a combinação ótima de diferentes tipos de produtos para armazenamento em armazéns (gestão de estoque ou);

tarefas de transporte (análise da localização da empresa, movimentação de mercadorias).

A programação linear é a seção mais desenvolvida e amplamente utilizada da programação matemática (além disso, isso inclui: programação inteira, dinâmica, não linear e paramétrica). Isso se explica da seguinte maneira:

os modelos matemáticos de um grande número de problemas econômicos são lineares em relação às variáveis ​​requeridas;

este tipo de problemas é atualmente o mais estudado. Para ele, métodos especiais foram desenvolvidos com a ajuda dos quais esses problemas são resolvidos e os programas de computador correspondentes;

muitos problemas de programação linear, sendo resolvidos, encontraram ampla aplicação;

alguns problemas que não são lineares na formulação original, após uma série de restrições e suposições adicionais, podem se tornar lineares ou podem ser reduzidos a tal forma que podem ser resolvidos por métodos de programação linear.

O modelo econômico e matemático de qualquer problema de programação linear inclui: uma função objetivo, cujo valor ótimo (máximo ou mínimo) deve ser encontrado; restrições na forma de um sistema de equações lineares ou desigualdades; exigência de não negatividade das variáveis.

Em geral, o modelo é escrito da seguinte forma:

função objetiva

(1.1) sob as restrições

(1.2) requisitos de não negatividade

(1.3) onde x j– variáveis ​​(desconhecidas);

- coeficientes do problema de programação linear.

O problema é encontrar o valor ótimo da função (1.1) sujeito às restrições (1.2) e (1.3).

O sistema de restrições (1.2) é chamado de restrições funcionais do problema, e as restrições (1.3) são chamadas de restrições diretas.

Um vetor que satisfaz as restrições (1.2) e (1.3) é chamado de solução viável (plano) de um problema de programação linear. O plano para o qual a função (1.1) atinge seu valor máximo (mínimo) é chamado de ótimo.

1.2. Método Simplex para resolver problemas de programação linear

O método simplex foi desenvolvido e aplicado pela primeira vez para resolver problemas em 1947 pelo matemático americano J. Dantzig.

Problemas de programação linear bidimensional são resolvidos graficamente. Para o caso N=3, podemos considerar um espaço tridimensional e a função objetivo atingirá seu valor ótimo em um dos vértices do poliedro.

Uma solução admissível (um plano admissível) de um problema de PL dado na forma padrão é um conjunto ordenado de números (x1, x2, ..., xn) que satisfazem as restrições; é um ponto no espaço n-dimensional.

O conjunto de soluções admissíveis forma a área de soluções admissíveis (SDR) do problema de PL. ODR é um poliedro convexo (polígono).

Em termos gerais, quando N-incógnitas estão envolvidas no problema, podemos dizer que a área de soluções viáveis ​​especificadas pelo sistema de condições limite é representada por um poliedro convexo no espaço n-dimensional e o valor ótimo do objetivo função é alcançada em um ou mais vértices.

Uma solução é chamada básica se todas as variáveis ​​livres são iguais a zero.

Uma solução de referência é uma solução básica não negativa. A solução de suporte pode ser não degenerada e degenerada. Uma solução de suporte é chamada não degenerada se o número de suas coordenadas diferentes de zero for igual ao posto do sistema, caso contrário é degenerada.

Uma solução viável, na qual a função objetivo atinge seu valor extremo, é chamada de ótima e é denotada .

É muito difícil resolver esses problemas graficamente quando o número de variáveis ​​é maior que 3. Existe uma maneira universal de resolver problemas de programação linear, chamada de método simplex.

O método simplex é um método universal de resolução de problemas de PL, que é um processo iterativo que começa com uma solução e, em busca da melhor opção, percorre os pontos de canto da área de soluções viáveis ​​até atingir o valor ótimo .

Ele pode ser usado para resolver qualquer problema de programação linear.

O método simplex baseia-se na ideia de melhoria sucessiva da solução resultante.

O significado geométrico do método simplex é mover sequencialmente de um vértice do poliedro de restrição para o vizinho, no qual a função objetivo assume o melhor (ou pelo menos não o pior) valor até que a solução ótima seja encontrada - o vértice onde o valor ótimo é alcançado pela função objetivo (se o problema tem um ótimo finito).

Assim, tendo um sistema de restrições reduzido à forma canônica (todas as restrições funcionais estão na forma de igualdades), encontra-se qualquer solução básica desse sistema, tendo o cuidado de encontrá-la da forma mais simples possível. Se a primeira solução básica encontrada for viável, então é verificada a otimalidade. Se não for ótimo, então é feita uma transição para outra solução básica, necessariamente admissível. O método simplex garante que, com esta nova solução, a função objetivo, se não atingir o ótimo, então se aproxima dele (ou pelo menos não se afasta dele). Com uma nova solução básica admissível, o mesmo é feito até que seja encontrada uma solução ótima.

O processo de aplicação do método simplex envolve a implementação de seus três elementos principais:

um método para determinar alguma solução básica viável inicial para o problema;

a regra de transição para a melhor (mais precisamente, não a pior) solução;

critério para verificar a otimalidade da solução encontrada.

O método simplex inclui várias etapas e pode ser formulado como um algoritmo claro (uma instrução clara para realizar operações sequenciais). Isso permite que você programe e implemente com sucesso em um computador. Problemas com um pequeno número de variáveis ​​e restrições podem ser resolvidos manualmente pelo método simplex.

6.1 Introdução

Otimização. Parte 1

Os métodos de otimização permitem que você escolha a melhor opção de design entre todas as opções possíveis. Nos últimos anos, muita atenção tem sido dada a esses métodos e, como resultado, foram desenvolvidos vários algoritmos altamente eficientes que possibilitam encontrar a opção de projeto ideal usando um computador digital. Este capítulo descreve os fundamentos da teoria da otimização, considera os princípios subjacentes à construção de algoritmos para soluções ótimas, descreve os algoritmos mais conhecidos e analisa suas vantagens e desvantagens.

6.2. Fundamentos da teoria de otimização

O termo “otimização” na literatura refere-se a um processo ou sequência de operações que permite obter uma solução refinada. Embora o objetivo final da otimização seja encontrar a melhor solução, ou "ótima", geralmente é preciso se contentar em melhorar as soluções conhecidas, em vez de aperfeiçoá-las. Portanto, a otimização é mais provável de ser entendida como a busca da perfeição, que, talvez, não seja alcançada.

Considerando algum sistema arbitrário descrito por m equações com n incógnitas, podemos distinguir três tipos principais de problemas. Se m=n , o problema é chamado de algébrico. Tal problema geralmente tem uma solução. Se m>n, então o problema é redefinido e, via de regra, não tem solução. Finalmente, para m

Antes de prosseguir com a discussão dos problemas de otimização, apresentamos algumas definições.

Parâmetros de projeto

Este termo denota parâmetros variáveis ​​independentes que definem de forma completa e inequívoca o problema de projeto que está sendo resolvido. Os parâmetros de projeto são quantidades desconhecidas, cujos valores são calculados durante o processo de otimização. Quaisquer grandezas básicas ou derivadas que sirvam para descrever quantitativamente o sistema podem servir como parâmetros de projeto. Assim, podem ser valores desconhecidos de comprimento, massa, tempo, temperatura. O número de parâmetros de projeto caracteriza o grau de complexidade deste problema de projeto. Normalmente, o número de parâmetros de projeto é denotado por n, e os próprios parâmetros de projeto por x com os índices correspondentes. Assim, n parâmetros de projeto deste problema serão denotados por

X1, x2, x3,...,xn.

função objetiva

Esta é a expressão cujo valor o engenheiro procura maximizar ou minimizar. A função objetivo permite comparar quantitativamente duas soluções alternativas. Do ponto de vista matemático, a função objetivo descreve alguma (n + 1) - superfície dimensional. Seu valor é determinado pelos parâmetros de projeto

M=M(x1, x2,...,xn).

Exemplos da função objetivo, frequentemente encontrados na prática de engenharia, são custo, peso, resistência, dimensões, eficiência. Se houver apenas um parâmetro de projeto, então a função objetivo pode ser representada por uma curva em um plano (Fig. 6.1). Se houver dois parâmetros de projeto, a função alvo será representada por uma superfície no espaço de três dimensões (Fig. 6.2). Com três ou mais parâmetros de projeto, as superfícies especificadas pela função objetivo são chamadas de hipersuperfícies e não podem ser representadas.

Zheniya meios convencionais. As propriedades topológicas da superfície da função objetivo desempenham um papel importante no processo de otimização, uma vez que a escolha do algoritmo mais eficiente depende delas.

A função objetivo em alguns casos pode assumir as formas mais inesperadas. Por exemplo, nem sempre é possível expressá-lo em

Fig. 1. Função objetivo unidimensional.

Fig.6.2.Função objetivo bidimensional.

matemática fechada, em outros casos pode

seja uma função suave por partes. Às vezes, uma função objetivo pode exigir uma tabela de dados técnicos (por exemplo, uma tabela de estado de vapor) ou pode ser necessário realizar um experimento. Em alguns casos, os parâmetros de design aceitam apenas valores inteiros. Um exemplo seria o número de dentes em uma engrenagem ou o número de parafusos em um flange. Às vezes, os parâmetros de design têm apenas dois valores - sim ou não. Parâmetros qualitativos, como satisfação do cliente, confiabilidade, estética, são difíceis de levar em conta no processo de otimização, pois são quase impossíveis de quantificar. No entanto, de qualquer forma que a função objetivo seja apresentada, ela deve ser uma função de valor único dos parâmetros de projeto.

Em vários problemas de otimização, é necessária a introdução de mais de uma função objetivo. Às vezes, um deles pode ser incompatível com o outro. Um exemplo é o projeto de aeronaves, quando é necessário fornecer resistência máxima, peso mínimo e custo mínimo ao mesmo tempo. Nesses casos, o projetista deve introduzir um sistema de prioridades e atribuir algum multiplicador adimensional para cada função objetivo. Como resultado, surge uma “função de compromisso”, que permite que uma função objetivo composta seja utilizada no processo de otimização.

Encontrando o mínimo e o máximo

Alguns algoritmos de otimização são adaptados para encontrar o máximo, outros para encontrar o mínimo. No entanto, independentemente do tipo de problema extremo a ser resolvido, pode-se usar o mesmo algoritmo, pois o problema de minimização pode ser facilmente transformado em um problema máximo alterando o sinal da função objetivo para o oposto. Essa técnica é ilustrada na Figura 6.3.

Espaço de design

Este é o nome da área definida por todos os n parâmetros de projeto. O espaço de design não é tão grande quanto parece, pois geralmente é limitado a um número de

condições associadas à essência física do problema. As restrições podem ser tão fortes que a tarefa não terá nenhum

Fig.6.3. Mudando o sinal da função objetivo para o oposto

A tarefa máxima torna-se a tarefa mínima.

solução satisfatória. As restrições são divididas em dois grupos: restrições - igualdades e restrições - desigualdades.

Restrições - igualdade

Restrições - igualdades - é a dependência entre os parâmetros de projeto que devem ser levados em consideração ao encontrar uma solução. Eles refletem as leis da natureza, economia, direitos, gostos predominantes e a disponibilidade dos materiais necessários. O número de restrições - as igualdades podem ser qualquer. Eles parecem

C 1 (x 1 , x 2 ,...,x n)=0,

C 2 (x 1 , x 2 ,...,x n)=0,

..................

Cj(x1, x2,...,xn)=0.

Se alguma dessas relações puder ser resolvida em relação a um dos parâmetros de projeto, isso permitirá que você exclua esse parâmetro do processo de otimização. Isso reduz o número de dimensões do espaço de projeto e simplifica a solução do problema.

Restrições - desigualdades

Este é um tipo especial de restrição expressa por desigualdades. No caso geral, pode haver qualquer número deles, e todos eles têm a forma

z 1 r 1 (x 1 , x 2 ,..., x n) Z 1

z 2 r 2 (x 1 , x 2 ,..., x n) Z 2

.......................

z k r k (x 1 , x 2 ,..., x n) Z k

Deve-se notar que muitas vezes, devido a limitações, o valor ótimo da função objetivo não é alcançado onde sua superfície tem gradiente zero. Muitas vezes, a melhor solução está em um dos limites do domínio do design.

Ótimo local

Este é o nome do ponto no espaço de projeto em que a função objetivo tem o maior valor em comparação com seus valores em todos os outros pontos em sua vizinhança imediata.

Fig.6.4. Uma função objetivo arbitrária pode ter vários

ótimos locais.

Na fig. A Figura 6.4 mostra uma função objetivo unidimensional que possui dois ótimos locais. Muitas vezes, o espaço de projeto contém muitos ótimos locais e deve-se tomar cuidado para não confundir o primeiro com a solução ótima para o problema.

Ótimo global

O ótimo global é a solução ideal para todo o espaço de projeto. É melhor do que todas as outras soluções correspondentes a ótimos locais, e é isso que o projetista está procurando. O caso de vários ótimos globais iguais localizados em diferentes partes do espaço de projeto é possível. Como o problema de otimização é colocado é melhor ilustrado por um exemplo.

Exemplo 6.1

Seja necessário projetar um recipiente retangular com volume de 1 m , projetado para transportar fibra não embalada. É desejável que seja gasto o mínimo de material possível na fabricação de tais recipientes (assumindo uma espessura de parede constante, isso significa que a área de superfície deve ser mínima), pois será mais barato. Para facilitar o transporte do contêiner com uma empilhadeira, sua largura deve ser de pelo menos 1,5 m.

Vamos formular este problema de uma forma conveniente para a aplicação do algoritmo de otimização.

Parâmetros de projeto: x 1 , x 2 , x 3 .

A função objetivo (que precisa ser minimizada) é a área da superfície lateral do contêiner:

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.

Restrição - igualdade:

Volume \u003d x 1 x 2 x 3 \u003d 1m3.

Restrição - desigualdade:

Problemas de programação linear

Programação Linear (LP)é uma das seções de programação matemática - uma disciplina que estuda problemas extremos (otimização) e desenvolve métodos para resolvê-los.

Problema de otimizaçãoé um problema matemático que consiste em encontrar o valor ótimo (ou seja, máximo ou mínimo) da função objetivo, e os valores das variáveis ​​devem pertencer a uma determinada área de valores admissíveis (ODV).

Em geral, a formulação de um problema extremo de programação matemática consiste em determinar o maior ou o menor valor da função , chamado função objetiva, sob as condições (restrições) , onde e são dadas funções, e são dadas constantes. Ao mesmo tempo, restrições na forma de igualdades e desigualdades determinam o conjunto (região) de soluções factíveis (ODS), e são chamadas de Parâmetros de projeto.

Dependendo do tipo de funções e problemas de programação matemática são divididos em várias classes (linear, não linear, convexa, inteira, estocástica, programação dinâmica, etc).

NO visão geral O problema de PL tem a seguinte forma:

, (5.1)

, , (5.2)

, , (5.3)

onde , , são dadas constantes.

A função (5.1) é chamada de função objetivo; sistemas (5.2), (5.3) - por um sistema de restrições; condição (5.4) é a condição de não negatividade dos parâmetros de projeto.

O conjunto de parâmetros de projeto que satisfazem as restrições (5.2), (5.3) e (5.4) é chamado solução aceitável ou plano.

A solução ótima ou plano ideal O problema de PL é chamado de solução viável, na qual a função objetivo (5.1) assume o valor ótimo (máximo ou mínimo).

Tarefa padrão LP é chamado de problema de encontrar o valor máximo (mínimo) da função objetivo (5.1) sob a condição (5.2) e (5.4), onde , , ou seja. Essa. restrições apenas na forma de desigualdades (5.2) e todos os parâmetros de projeto satisfazem a condição de não negatividade, e não há condições na forma de igualdades:

,

, , (5.5)

.

Tarefa canônica (principal) O LP é chamado de problema de encontrar o valor máximo (mínimo) da função objetivo (5.1) sob as condições (5.3) e (5.4), onde , , ou seja. Essa. restrições apenas na forma de igualdades (5.3) e todos os parâmetros de projeto satisfazem a condição de não negatividade, e não há condições na forma de desigualdades:

,

.

O problema de PL canônico também pode ser escrito na forma matricial e vetorial.

A forma matricial do problema de PL canônico tem a seguinte forma:

Forma vetorial do problema de LP canônico.