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:

Dividimos todo o período de 4 anos 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-ésimo estágio, 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);

CONTROLAR O TRABALHO DA DISCIPLINA:

"MÉTODOS DE SOLUÇÕES ÓTIMAS"

Opção número 8

1. Resolva um problema de programação linear usando um método gráfico. Encontre o máximo e o mínimo da função  sob determinadas restrições:

,

.

Decisão

É necessário encontrar o valor mínimo da função objetivo e o máximo, sob o sistema de restrições:

9x1 +3x2 ≥30, (1)

X 1 + x 2 ≤4, (2)

x 1 + x 2 ≤8, (3)

Vamos construir o domínio de soluções admissíveis, ou seja, resolva graficamente o sistema de desigualdades. Para fazer isso, construímos cada linha reta e definimos os semiplanos dados pelas desigualdades (os semiplanos são marcados com um primo).

A intersecção dos semiplanos será a área, cujas coordenadas dos pontos satisfazem a condição das desigualdades do sistema de restrições do problema. Vamos denotar os limites da região do polígono solução.

Vamos construir uma reta correspondente ao valor da função F = 0: F = 2x 1 +3x 2 = 0. O vetor gradiente composto pelos coeficientes da função objetivo indica a direção de minimização de F(X). O início do vetor é o ponto (0; 0), o final é o ponto (2; 3). Vamos mover esta linha de forma paralela. Como estamos interessados ​​na solução mínima, portanto, movemos a linha reta até o primeiro toque da área designada. No gráfico, esta linha é indicada por uma linha pontilhada.

Em linha reta
intercepta a região no ponto C. Como o ponto C é obtido como resultado da interseção das linhas (4) e (1), suas coordenadas satisfazem as equações dessas linhas:
.

Tendo resolvido o sistema de equações, obtemos: x 1 = 3,3333, x 2 = 0.

Onde podemos encontrar o valor mínimo da função objetivo: .

Considere a função objetivo do problema.

Vamos construir uma linha reta correspondente ao valor da função F = 0: F = 2x 1 +3x 2 = 0. O vetor gradiente composto pelos coeficientes da função objetivo indica a direção de maximização de F(X). O início do vetor é o ponto (0; 0), o final é o ponto (2; 3). Vamos mover esta linha de forma paralela. Como estamos interessados ​​na solução máxima, movemos a linha reta até o último toque da área designada. No gráfico, esta linha é indicada por uma linha pontilhada.

Em linha reta
intercepta a região no ponto B. Como o ponto B é obtido como resultado da interseção das linhas (2) e (3), então suas coordenadas satisfazem as equações dessas linhas:

.

Onde podemos encontrar o valor máximo da função objetivo: .

Responda:
e
.

2 . Resolva um problema de programação linear usando o método simplex:

.

Decisão

Vamos resolver o problema direto de programação linear pelo método simplex, usando a tabela simplex.

Vamos determinar o valor mínimo da função objetivo
sob as seguintes condições-restrições:
.

Para construir o primeiro plano de referência, reduzimos o sistema de desigualdades a um sistema de equações introduzindo variáveis ​​adicionais.

Na 1ª desigualdade de significado (≥), introduzimos a variável básica x 3 com um sinal de menos. Na 2ª desigualdade de significado (≤), introduzimos a variável básica x 4 . Na 3ª desigualdade de significado (≤), introduzimos a variável básica x 5 .

Vamos introduzir variáveis ​​artificiais : na 1ª igualdade introduzimos uma variável x 6 ;

Para definir a tarefa para o mínimo, escrevemos a função objetivo da seguinte forma: .

Para o uso de variáveis ​​artificiais introduzidas na função objetivo, é imposta a chamada penalidade de M, um número positivo muito grande, que geralmente não é especificado.

A base resultante é chamada artificial, e o método de solução é chamado de método da base artificial.

Além disso, as variáveis ​​artificiais não estão relacionadas ao conteúdo da tarefa, mas permitem construir um ponto de partida, e o processo de otimização força essas variáveis ​​a assumir valores zero e garantir a admissibilidade da solução ótima.

A partir das equações, expressamos variáveis ​​artificiais: x 6 \u003d 4-x 1 -x 2 +x 3, que substituímos na função objetivo: ou.

Matriz de Coeficientes
este sistema de equações tem a forma:
.

Vamos resolver o sistema de equações em relação às variáveis ​​básicas: x 6 , x 4 , x 5.

Assumindo que as variáveis ​​livres são 0, obtemos a primeira linha de base:

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

Uma solução básica é chamada admissível se for não negativa.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

A linha de base atual não é ideal porque há coeficientes positivos na linha do índice. Escolheremos a coluna correspondente à variável x 2 como a principal, pois este é o maior coeficiente. Calcule os valores D eu e escolha o menor deles: min(4: 1 , 2: 2 , 10: 2) = 1.

Portanto, a 2ª linha está liderando.

O elemento de resolução é igual a (2) e está localizado na interseção da coluna inicial e da linha inicial.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Formamos a próxima parte da tabela simplex. Em vez da variável x 4, a variável x 2 entrará no plano 1.

A linha correspondente à variável x 2 no plano 1 é obtida dividindo todos os elementos da linha x 4 do plano 0 pelo elemento habilitador RE=2. No lugar do elemento de resolução, obtemos 1. Nas células restantes da coluna x 2, escrevemos zeros.

Assim, no novo plano são preenchidas 1 linha x 2 e coluna x 2. Todos os outros elementos do novo plano 1, incluindo os elementos da linha de índice, são determinados pela regra do retâ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

A linha de base atual não é ideal porque há coeficientes positivos na linha do índice. Escolheremos a coluna correspondente à variável x 1 como a principal, pois este é o maior coeficiente. Calcule os valores D eu por linhas como um quociente de divisão: e deles escolhemos o menor: min (3: 1 1 / 2, -, 8: 2) = 2.

Portanto, a 1ª linha está liderando.

O elemento de resolução é igual a (1 1 / 2) e está localizado na interseção da coluna principal e da linha 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 M

Formamos a próxima parte da tabela simplex. Em vez da variável x 6 , a variável x 1 será incluída no plano 2.

Obtemos uma nova tabela simplex:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Nenhum dos valores da linha do índice é positivo. Portanto, esta tabela determina o plano de tarefa ideal.

A versão final da tabela simplex:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Como não há variáveis ​​artificiais na solução ótima (elas são iguais a zero), essa solução é viável.

O plano ideal pode ser escrito da seguinte forma: x 1 \u003d 2, x 2 \u003d 2:.

Responda:
,
.

3. A empresa "Três homens gordos" está envolvida na entrega de carne enlatada de três armazéns localizados em diferentes pontos da cidade para três lojas. Os estoques de enlatados disponíveis nos armazéns, bem como o volume de pedidos das lojas e as taxas de entrega (em unidades monetárias convencionais) são apresentados na tabela de transporte.

Encontre um plano de transporte que forneça os menores custos de caixa (execute o plano de transporte original usando o método "canto noroeste").

Decisão

Vamos verificar a condição necessária e suficiente para a resolubilidade do problema:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

A condição de equilíbrio é atendida. Estoque necessidades iguais. Portanto, o modelo do problema de transporte é fechado.

Vamos inserir os dados iniciais na tabela de distribuição.

Precisa

Usando o método do canto noroeste, construiremos o primeiro plano básico do problema de transporte.

O plano começa a ser preenchido a partir do canto superior esquerdo.

O elemento desejado é 4. Para este elemento, os estoques são 300, as necessidades são 250. Como o mínimo é 250, subtraímos: .

			300 - 250 = 50
250 - 250 = 0

O elemento desejado é 2. Para este elemento, os estoques são 50, as necessidades são 400. Como o mínimo é 50, subtraímos: .

			50 - 50 = 0
	400 - 50 = 350

O elemento desejado é 5. Para este elemento, os estoques são 300, as necessidades são 350. Como o mínimo é 300, subtraímos:

			300 - 300 = 0
	350 - 300 = 50

O elemento desejado é 3. Para este elemento, os estoques são 200, as necessidades são 50. Como o mínimo é 50, subtraímos:

			200 - 50 = 150
	50 - 50 = 0

O elemento desejado é 6. Para este elemento, os estoques são 150, as necessidades são 150. Como o mínimo é 150, subtraímos:

			150 - 150 = 0
		150 - 150 = 0

Precisa

Encontre por um método gráfico o máximo da função objetivo

F= 2x 1 + 3x 2 ® máximo

Com restrições

Decisão usando planilhas do Excel

Primeiro, vamos construir uma solução para o sistema de desigualdades em uma planilha do Excel.

Considere a primeira desigualdade.

Vamos construir uma linha de fronteira a partir de dois pontos. Denote a linha por (L1) (ou Row1). Coordenadas X 2 contamos de acordo com as fórmulas:

Para construir, selecione um gráfico de dispersão

Escolhendo dados para uma linha reta

Altere o nome da linha:

Escolha um layout de gráfico. Altere o nome dos eixos de coordenadas:

Linha reta (L1) no gráfico:

A solução para a desigualdade estrita pode ser encontrada usando um único ponto de teste que não pertence à linha (L1). Por exemplo, usando o ponto (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

A inequação é verdadeira, portanto, a solução da inequação (1) será o semiplano no qual o ponto de teste está localizado (na figura abaixo da linha L1).

Então resolvemos a desigualdade (2) .

Vamos construir a linha de fronteira 2 a partir de dois pontos. Denote a linha por (L2).

Linha reta (L2) no gráfico:

A solução da desigualdade estrita 2 pode ser encontrada usando o único ponto de teste que não pertence à reta (L2). Por exemplo, usando o ponto (0; 0)W(L2).

Substituindo as coordenadas do ponto (0; 0), obtemos a desigualdade

2×0 + 0< 16 или 0 < 16 .

A inequação é verdadeira, portanto, a solução da inequação (2) será o semiplano em que se encontra o ponto de teste (na figura abaixo, a reta L2).

Então resolvemos a desigualdade (3) .

Vamos construir uma linha de fronteira a partir de dois pontos. Denote a linha por (L3).

Linha reta (L3) no gráfico:

A solução da desigualdade estrita 2 pode ser encontrada usando o único ponto de teste que não pertence à reta (L3). Por exemplo, usando o ponto (0; 0)W(L3).

Substituindo as coordenadas do ponto (0; 0), obtemos a desigualdade

A inequação é verdadeira, portanto, a solução da inequação (3) será o semiplano no qual o ponto de teste está localizado (na figura abaixo, linha L3).

Então resolvemos a desigualdade (4) .

Vamos construir uma linha de fronteira a partir de dois pontos. Denote a linha por (L4).

Adicionar dados à planilha do Excel

Linha reta (L4) no gráfico:

Solução da Desigualdade Estrita 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Substituindo as coordenadas do ponto (0; 0), obtemos a desigualdade

A inequação é verdadeira, portanto, a solução da inequação (4) será o semiplano no qual o ponto de teste está localizado (à esquerda da linha L4 na figura).

Resolvendo duas inequações (5) e (6)

é o 1º trimestre delimitado pelas linhas de coordenadas e .

O sistema de desigualdades é resolvido. A solução para o sistema de desigualdades (1) - (6) neste exemplo é um polígono convexo no canto inferior esquerdo da figura, delimitado pelas linhas L1, L2, L3, L4 e pelas linhas de coordenadas e . Você pode garantir que o polígono seja escolhido corretamente substituindo um ponto de teste, por exemplo (1; 1) em cada desigualdade do sistema original. Substituindo o ponto (1; 1), obtemos que todas as desigualdades, incluindo as restrições naturais, são verdadeiras.

Considere agora a função objetivo

F= 2x 1 + 3x 2 .

Vamos construir linhas de nível para valores de função F=0 e F=12(valores numéricos são escolhidos arbitrariamente). Adicionar dados à planilha do Excel

Linhas de nível no gráfico:

Vamos construir um vetor de direções (ou um gradiente) (2; 3). As coordenadas vetoriais coincidem com os coeficientes da função objetivo F.

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, foram desenvolvidos métodos especiais 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. Danzig.

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.