Introdução
O estágio moderno do desenvolvimento humano é diferente, pois o século da energia está sendo substituído pela era da informática. Há uma introdução intensiva de novas tecnologias em todas as esferas da atividade humana. Existe um problema real de transição para a sociedade da informação, para o qual o desenvolvimento da educação deve tornar-se uma prioridade. A estrutura do conhecimento na sociedade também está mudando. O conhecimento fundamental que contribui para o desenvolvimento criativo do indivíduo está se tornando cada vez mais importante para a vida prática. A construtividade do conhecimento adquirido, a capacidade de estruturá-lo de acordo com o objetivo também é importante. Com base no conhecimento, novos recursos de informação da sociedade são formados. A formação e aquisição de novos conhecimentos deve basear-se numa metodologia rigorosa de abordagem sistemática, dentro da qual um lugar distinto é ocupado por uma abordagem modelo. As possibilidades da abordagem de modelagem são extremamente diversas tanto em termos dos modelos formais utilizados quanto nas formas de implementação dos métodos de modelagem. A modelagem física permite obter resultados confiáveis para sistemas bastante simples.
Atualmente, é impossível nomear uma área de atividade humana na qual, de uma forma ou de outra, os métodos de modelagem não seriam usados. Isto é especialmente verdade para a gestão de vários sistemas, onde os principais são os processos de tomada de decisão com base nas informações recebidas.
1. Declaração do problema
função objetivo mínimo
Resolva o problema de encontrar o mínimo da função objetivo para o sistema de restrições especificado pelo polígono de decisão de acordo com a opção nº 16 da tarefa. O polígono de decisão é mostrado na Figura 1:
Figura 1 - Polígono de soluções de problemas
O sistema de restrições e a função objetivo do problema são apresentados a seguir:
É necessário resolver o problema usando os seguintes métodos:
Método gráfico para resolução de problemas de PL;
Método algébrico para resolução de problemas de PL;
Método Simplex para resolução de problemas de PL;
Método para encontrar uma solução viável para problemas de PL;
Resolvendo o problema de LP duplo;
O método de "ramificações e limites" para resolver problemas de PL inteiros;
o método de Gomory para resolver problemas de PL inteiros;
Método Balash para resolver problemas de PL booleano.
Compare os resultados da solução por diferentes métodos para tirar as conclusões apropriadas sobre o trabalho.
2. Solução gráfica do problema de programação linear
O método gráfico para resolver problemas de programação linear é usado nos casos em que o número de incógnitas não excede três. É conveniente para um estudo qualitativo das propriedades das soluções e é usado em conjunto com outros métodos (algébrico, branch and bound, etc.). A ideia do método é baseada na solução gráfica de um sistema de desigualdades lineares.
Arroz. 2 Solução gráfica do problema LP
Ponto baixo
Equação de uma linha reta que passa por dois pontos A1 e A2:
AB: (0;1); (3;3)
Sol: (3;3); (4;1)
CD: (4;1); (3;0)
EA: (1;0); (0;1)
FC: (0;1); (5;2)
com restrições:
Resolvendo um problema de programação linear pelo método simplex algébrico
A aplicação do método algébrico para a resolução do problema requer uma generalização da representação do problema de PL. O sistema original de restrições dado na forma de desigualdades é convertido para a notação padrão quando as restrições são dadas na forma de igualdades. A conversão de um sistema de restrições em um formulário padrão inclui as seguintes etapas:
Transforme as desigualdades de tal forma que as variáveis e os membros livres fiquem à esquerda e 0 à direita, ou seja. que o lado esquerdo seja maior ou igual a zero;
Introduzir variáveis adicionais, cujo número é igual ao número de desigualdades no sistema de restrições;
Introduzindo restrições adicionais sobre a não negatividade das variáveis adicionadas, substitua os sinais de desigualdade por sinais de igualdade estritos.
Ao resolver o problema de PL pelo método algébrico, uma condição é adicionada: a função objetivo deve tender a um mínimo. Se esta condição não for atendida, é necessário transformar adequadamente a função objetivo (multiplicar por -1) e resolver o problema de minimização. Depois que a solução for encontrada, substitua os valores das variáveis na função original e calcule seu valor.
A solução do problema usando o método algébrico é considerada ótima quando os valores de todas as variáveis básicas são não negativos e os coeficientes para variáveis livres na equação da função objetivo também são não negativos. Se essas condições não forem atendidas, é necessário transformar o sistema de desigualdades, expressando algumas variáveis em função de outras (alterando variáveis livres e básicas) para atingir as restrições acima. O valor de todas as variáveis livres é assumido como zero.
O método algébrico para resolver problemas de programação linear é um dos métodos mais eficazes para resolver problemas de pequenas dimensões manualmente. não requer um grande número de cálculos aritméticos. A implementação de máquina deste método é mais complicada do que, por exemplo, para o método simplex, porque o algoritmo para resolver pelo método algébrico é até certo ponto heurístico e a eficácia da solução depende em grande parte da experiência pessoal.
variáveis livres
Rua da rua - adicionar. kit
As condições de não negatividade são satisfeitas, portanto, a solução ótima é encontrada.
3. Resolvendo um problema de programação linear usando uma tabela simplex
Solução: Vamos trazer o problema para uma forma padrão para resolver usando uma tabela simplex.
Reduzimos todas as equações do sistema para a forma:
Construímos uma tabela simplex:
No canto superior de cada célula da tabela inserimos os coeficientes do sistema de equações;
Selecionamos o elemento positivo máximo na linha F, exceto que será a coluna geral;
Para encontrar o elemento geral, construímos uma relação para todos os positivos. 3/3; 9/1;- relação mínima na linha x3. Portanto - string geral e =3 - elemento geral.
Encontramos =1/=1/3. Trazemos no canto inferior da célula, onde está localizado o elemento geral;
Em todos os cantos inferiores não preenchidos da linha geral, inserimos o produto do valor no canto superior da célula por;
Selecione os cantos superiores da linha geral;
Em todos os cantos inferiores da coluna geral, inserimos o produto do valor no canto superior por - e selecionamos os valores resultantes;
As células restantes da tabela são preenchidas como produtos dos elementos selecionados correspondentes;
Em seguida, construímos uma nova tabela na qual as designações das células dos elementos da coluna e da linha gerais são invertidas (x2 e x3);
No canto superior da antiga linha e coluna gerais, os valores que estavam anteriormente no canto inferior são escritos;
A soma dos valores dos cantos superior e inferior dessas células na tabela anterior está escrita no canto superior das células restantes
4. Resolvendo o problema de programação linear encontrando uma solução viável
Seja dado um sistema de equações algébricas lineares:
Podemos supor que tudo, caso contrário, multiplicamos a equação correspondente por -1.
Introduzimos variáveis auxiliares:
Também introduzimos uma função auxiliar
Vamos minimizar o sistema sob restrições (2) e condições.
REGRA PARA ENCONTRAR UMA SOLUÇÃO VIÁVEL: Para encontrar uma solução viável para o sistema (1), minimizamos a forma (3) sob as restrições (2), como incógnitas livres tomamos xj como básicas.
Ao resolver um problema pelo método simplex, podem surgir dois casos:
min f=0, então todo i deve ser igual a zero. E os valores resultantes xj serão uma solução viável para o sistema (1).
min f>0, ou seja o sistema original não tem uma solução viável.
Sistema de origem:
A condição do problema do tópico anterior é usada.
Vamos adicionar variáveis adicionais:
Uma solução admissível para o problema original é encontrada: x1 = 3, x2 = 3, F = -12. Com base na solução viável obtida, encontramos a solução ótima para o problema original usando o método simplex. Para fazer isso, vamos construir uma nova tabela simplex a partir da tabela obtida acima, excluindo a linha e a linha com a função de destino da tarefa auxiliar:
Analisando a tabela simplex construída, vemos que a solução ótima para o problema original já foi encontrada (os elementos da linha correspondente à função objetivo são negativos). Assim, a solução viável encontrada ao resolver o problema auxiliar coincide com a solução ótima do problema original:
6. O problema dual da programação linear
O sistema inicial de restrições e a função objetivo do problema são mostrados na figura abaixo.
com restrições:
Solução: Trazemos o sistema de restrições para o formulário padrão:
A tarefa dupla a esta será semelhante a:
O problema dual será resolvido pelo método simplex.
Vamos transformar a função objetivo para que o problema de minimização seja resolvido e escrever o sistema de restrições na forma padrão para resolver pelo método simplex.
y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)
y7 = 5 - (-3y1 - y2 + y3 + y4)
Ф = 0 - (3a1 + 9a2 + 3a3 + aa4) ??min
Vamos construir o tableau simplex inicial para resolver o problema de PL dual.
A segunda etapa do método simplex
Assim, na terceira etapa do método simplex, a solução ótima do problema de minimização foi encontrada com os seguintes resultados: y2 = -7/8, y1 = -11/8, Ф = 12. Para encontrar o valor de a função objetivo do problema dual, substituímos os valores encontrados das variáveis básicas e livres na função de maximização:
Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
Como o valor da função objetivo dos problemas direto e duplo é o mesmo, a solução do problema direto é encontrada e é igual a 12.
Fmin \u003d Fmax \u003d -12
7. Resolvendo o problema de programação linear inteira usando o método “branch and bounds”
Vamos transformar o problema original de tal forma que a condição de inteiro não seja satisfeita ao resolver por métodos convencionais.
O polígono inicial de soluções para um problema de programação inteira.
Vamos construir um novo sistema de restrições para o polígono de solução transformado.
Escrevemos o sistema de restrições na forma de igualdades, para resolver pelo método algébrico.
Como resultado da solução, o plano de tarefa ideal foi encontrado: x1 = 9/4, x2 = 5/2, F = -41/4. Esta solução não atende a condição de integralidade estabelecida no problema. Dividimos o polígono da solução original em duas regiões, excluindo a região 3 dele Polígono alterado de soluções de problemas Vamos compor novos sistemas de restrições para as regiões formadas do polígono de solução. A área esquerda é um quadrilátero (trapézio). O sistema de restrições para a região esquerda do polígono de solução é apresentado a seguir. Sistema de restrição para a área esquerda A região da direita representa o ponto C. O sistema de restrições para a área de decisão correta é apresentado a seguir. Os novos sistemas de restrições são dois problemas subsidiários que precisam ser resolvidos independentemente um do outro. Vamos resolver o problema de programação inteira para a região esquerda do polígono de solução. Como resultado da solução, foi encontrado o plano de tarefa ideal: x1 = 3, x2 = 3, F = -12. Este plano satisfaz a condição de variáveis inteiras no problema e pode ser tomado como o plano de referência ótimo para o problema original de programação linear inteira. Não faz sentido realizar a solução para a região de solução correta. A figura abaixo mostra o progresso da resolução de um problema de programação linear inteira na forma de uma árvore. O curso de resolução de um problema de programação linear inteira pelo método de Gomory. Em muitas aplicações práticas, o problema de programação inteira é de grande interesse, no qual um sistema de desigualdades lineares e uma forma linear são dados É necessário encontrar uma solução inteira do sistema (1) que minimize a função objetivo F, e todos os coeficientes sejam inteiros. Um dos métodos para resolver o problema de programação inteira foi proposto por Gomori. A ideia do método é utilizar métodos de programação linear contínua, em especial, o método simplex. 1) Usando o método simplex, a solução do problema (1), (2) é determinada, para o qual o requisito de que a solução seja inteira é removido; se a solução for inteira, então a solução desejada para o problema inteiro também será encontrada; 2) Caso contrário, se alguma coordenada não for um inteiro, a solução obtida do problema é verificada quanto à possibilidade da existência de uma solução inteira (presença de pontos inteiros em um poliedro admissível): se em qualquer linha com um membro livre fracionário, todos os outros coeficientes forem inteiros, então não há inteiros, pontos em um poliedro admissível, e o problema de programação inteira não tem solução; Caso contrário, uma restrição linear adicional é introduzida, que corta do poliedro admissível uma parte pouco promissora para encontrar uma solução para um problema de programação inteira; 3) Para construir uma restrição linear adicional, selecione a l-ésima linha com um membro livre fracionário e escreva a restrição adicional onde e são, respectivamente, as partes fracionárias dos coeficientes e membro. Vamos introduzir uma variável auxiliar na restrição (3): Vamos determinar os coeficientes e incluídos na restrição (4): onde e são os inteiros inferiores mais próximos para e, respectivamente. Gomory provou que um número finito de tais etapas leva a um problema de programação linear cuja solução é inteira e, portanto, a desejada. Solução: Reduzimos o sistema de restrições lineares e a função objetivo para a forma canônica: Vamos determinar a solução ótima do sistema de restrições lineares, descartando temporariamente a condição inteira. Usamos o método simplex para isso. As tabelas abaixo apresentam sequencialmente a solução inicial do problema, e as transformações da tabela original são dadas para obter a solução ótima do problema: Resolvendo problemas de PL booleano pelo método Balash. Componha independentemente uma variante para o problema de programação linear inteira com variáveis booleanas, levando em consideração as seguintes regras: o problema usa no mínimo 5 variáveis, no mínimo 4 restrições, os coeficientes de restrições e a função objetivo são escolhidos arbitrariamente, mas em tal de forma que o sistema de restrições seja compatível. A tarefa é resolver o ZCLP com variáveis booleanas usando o algoritmo Balash e determinar a redução da complexidade computacional em relação à resolução do problema por busca exaustiva. Execução de restrições Valor F Restrição de filtro: Determinação de Redução de Cálculo A solução do problema pelo método de busca exaustiva é 6*25=192 expressões calculadas. A solução do problema pelo método Balash é 3*6+(25-3)=47 expressões calculadas. A redução total da complexidade dos cálculos em relação à resolução do problema pelo método de busca exaustiva é. Conclusão O processo de concepção de sistemas de informação que implementam novas tecnologias de informação está em constante aperfeiçoamento. Sistemas cada vez mais complexos estão se tornando o foco de atenção dos engenheiros de sistemas, o que dificulta o uso de modelos físicos e aumenta a importância dos modelos matemáticos e da simulação computacional de sistemas. A modelagem de máquinas tornou-se uma ferramenta eficaz para pesquisa e projeto de sistemas complexos. A relevância dos modelos matemáticos está em constante aumento devido à sua flexibilidade, adequação a processos reais, baixo custo de implementação com base em PCs modernos. Cada vez mais oportunidades são oferecidas ao usuário, ou seja, um especialista em modelagem de sistemas por meio de tecnologia computacional. O uso de modelagem é especialmente eficaz nos estágios iniciais de projeto de sistemas automatizados, quando o custo de decisões errôneas é mais significativo. As ferramentas computacionais modernas permitiram aumentar significativamente a complexidade dos modelos utilizados no estudo de sistemas, tornou-se possível construir modelos combinados, analíticos e de simulação que levam em conta toda a variedade de fatores que ocorrem em sistemas reais, ou seja, o uso de modelos mais adequados aos fenômenos em estudo. Literatura: 1. Lyashchenko I.N. Programação linear e não linear / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K.: "Escola Superior", 1975, 372 p. 2. Diretrizes para a implementação do projeto de curso na disciplina "Matemática Aplicada" para alunos da especialidade "Sistemas e Redes Computacionais" formas de ensino em tempo integral e meio período / Compilado por: I.A. Balakireva, A.V. Skatkov - Sevastopol: Editora SevNTU, 2003. - 15 p. 3. Orientações para o estudo da disciplina "Matemática Aplicada", secção "Métodos de pesquisa global e minimização unidimensional" / Obr. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31s. 4. Diretrizes para o estudo da disciplina "Matemática Aplicada" para alunos da especialidade "Sistemas e Redes de Computadores" Seção "Resolvendo Problemas de Programação Linear Inteira" das formas de ensino em tempo integral e por correspondência / Compilado por: I.A. Balakireva, A.V. Skatkov - Sevastopol : Editora SevNTU, 2000. - 13 p. 5. Akulich I.L. Programação matemática em exemplos e tarefas: 6. Proc. bolsa para economia estudantil. especialista. universidades.-M.: Superior. escola, 1986.- 319s., ll. 7. Andronov S.A. Métodos de projeto ótimos: Texto de palestra / SPbGUAP. SPb., 2001. 169 p.: il. Algoritmo para resolver problemas de programação linear pelo método simplex. Construção de um modelo matemático de um problema de programação linear. Resolvendo um problema de programação linear no Excel. Encontrar lucro e plano de produção ideal. trabalho de conclusão de curso, adicionado em 21/03/2012 Resolução gráfica de problemas. Elaboração de um modelo matemático. Determinação do valor máximo da função objetivo. Solução por um método simplex com base artificial de um problema de programação linear canônica. Verificação da otimalidade da solução. teste, adicionado em 04/05/2016 Base teórica da programação linear. Problemas de programação linear, métodos de solução. Análise da solução ótima. Solução de um problema de programação linear de índice único. Declaração do problema e entrada de dados. Etapas de construção e solução do modelo. trabalho de conclusão de curso, adicionado em 12/09/2008 Construção de um modelo matemático. Seleção, justificação e descrição do método de resolução do problema direto de programação linear pelo método simplex, utilizando uma tabela simplex. Formulação e solução de um problema dual. Análise do modelo de sensibilidade. trabalho de conclusão de curso, adicionado em 31/10/2014 Construir um modelo matemático para maximizar o lucro do empreendimento, uma solução gráfica para o problema. Resolução de problemas usando o complemento SOLVER. Análise de mudanças nas reservas de recursos. Determinação dos limites de variação dos coeficientes da função objetivo. trabalho de conclusão de curso, adicionado em 17/12/2014 Programação matemática. Programação linear. Problemas de programação linear. Método gráfico para resolver um problema de programação linear. Formulação económica do problema de programação linear. Construção de um modelo matemático. trabalho de conclusão de curso, adicionado em 13/10/2008 Resolvendo um problema de programação linear por método gráfico, sua verificação em MS Excel. Análise da estrutura interna da solução do problema no programa. Otimização do plano de produção. Solução do problema pelo método simplex. Sistema de filas multicanal. teste, adicionado em 02/05/2012 Resolvendo o problema de programação linear pelo método simplex: definindo o problema, construindo um modelo econômico e matemático. Solução do problema de transporte pelo método dos potenciais: construção do plano de referência inicial, determinação do seu valor óptimo. teste, adicionado em 11/04/2012 Apresentação do problema de programação não linear. Determinação de pontos estacionários e seu tipo. Construção de linhas de nível, gráfico tridimensional da função objetivo e restrições. Solução gráfica e analítica do problema. Manual do usuário e esquema de algoritmo. trabalho de conclusão de curso, adicionado em 17/12/2012 Análise da solução de um problema de programação linear. Método simplex usando tabelas simplex. Modelagem e solução de problemas de PL em um computador. Interpretação econômica da solução ótima do problema. Formulação matemática do problema de transporte. 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. 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. Soluçã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. 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 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. Soluçã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); 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. 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) )\certo.) 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. 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. 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. 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 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. 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. 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. 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 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: 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: , 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: 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. Se houver apenas um fator limitante (por exemplo, uma máquina escassa), a solução pode ser encontrada usando fórmulas simples (veja o link no início do artigo). Se houver vários fatores limitantes, o método de programação linear é usado. Programação linearé o nome dado a uma combinação de ferramentas utilizadas na ciência da gestão. Este método resolve o problema de alocar recursos escassos entre atividades concorrentes para maximizar ou minimizar algum valor numérico, como ganhos ou custos marginais. Nos negócios, pode ser usado em áreas como planejamento de produção para maximizar lucros, seleção de componentes para minimizar custos, seleção de portfólio de investimentos para maximizar a lucratividade, otimização do transporte de mercadorias para reduzir distâncias, alocação de pessoal para maximizar a eficiência do trabalho e programação de trabalho em para economizar tempo. Baixar nota em , desenhos em formato A programação linear envolve a construção de um modelo matemático do problema em consideração. Depois disso, a solução pode ser encontrada graficamente (discutida abaixo), usando o Excel (será considerado separadamente) ou programas de computador especializados. Talvez a construção de um modelo matemático seja a parte mais difícil da programação linear, exigindo a tradução do problema em consideração em um sistema de variáveis, equações e desigualdades - um processo que depende, em última instância, das habilidades, experiência, habilidade e intuição do compilador do modelo. Considere um exemplo de construção de um modelo matemático de programação linear Nikolai Kuznetsov dirige uma pequena fábrica mecânica. No próximo mês, ele planeja produzir dois produtos (A e B), para os quais o lucro marginal específico é estimado em 2.500 e 3.500 rublos, respectivamente. A fabricação de ambos os produtos exige o custo de usinagem, matéria-prima e mão de obra (Fig. 1). Para a fabricação de cada unidade do produto A, são alocadas 3 horas de processamento na máquina, 16 unidades de matéria-prima e 6 unidades de mão de obra. Os requisitos correspondentes para a unidade B são 10, 4 e 6. Nikolai prevê que no próximo mês ele poderá fornecer 330 horas de usinagem, 400 unidades de matéria-prima e 240 unidades de mão de obra. A tecnologia do processo de produção é tal que pelo menos 12 unidades do produto B devem ser produzidas em um determinado mês. Arroz. 1. Uso e provisão de recursos Nikolai quer construir um modelo para determinar o número de unidades dos produtos A e B que ele deve produzir no próximo mês para maximizar o lucro marginal. O modelo linear pode ser construído em quatro etapas. Etapa 1. Definição de variáveis Existe uma variável alvo (vamos denotar Z) que precisa ser otimizada, ou seja, maximizada ou minimizada (por exemplo, lucro, receita ou despesas). Nikolay busca maximizar o lucro marginal, portanto, a variável alvo é: Z = lucro marginal total (em rublos) recebido no próximo mês como resultado da produção dos produtos A e B. Há uma série de variáveis desconhecidas desconhecidas (vamos denotá-las x 1, x 2, x 3, etc.), cujos valores devem ser determinados para obter o valor ótimo da função objetivo, que, no nosso caso, é o lucro marginal total. Essa margem de contribuição depende da quantidade de produtos A e B produzidos. Os valores dessas quantidades devem ser calculados e, portanto, são as variáveis desejadas no modelo. Então vamos denotar: x 1 = o número de unidades do produto A produzidas no próximo mês. x 2 = número de unidades do produto B produzidas no próximo mês. É muito importante definir claramente todas as variáveis; preste atenção especial às unidades de medida e ao período de tempo a que as variáveis se referem. Palco. 2. Construção da função objetivo Uma função objetivo é uma equação linear que deve ser maximizada ou minimizada. Ele contém a variável alvo expressa em termos das variáveis desejadas, ou seja, Z expressa em termos de x 1 , x 2 ... como uma equação linear. Em nosso exemplo, cada produto fabricado A traz 2.500 rublos. lucro marginal, e na fabricação de x 1 unidades do produto A, o lucro marginal será 2500 * x 1. Da mesma forma, o lucro marginal da fabricação de x 2 unidades do produto B será 3500 * x 2. Assim, o lucro marginal total recebido no próximo mês devido à produção de x 1 unidades do produto A e x 2 unidades do produto B, ou seja, a variável alvo Z será: Z = 2500 * x 1 + 3500 * x 2 Nikolay procura maximizar este indicador. Assim, a função objetivo em nosso modelo é: Maximizar Z = 2500 * x 1 + 3500 * x 2 Palco. 3. Definição de restrições Restrições são um sistema de equações lineares e/ou desigualdades que limitam os valores das variáveis necessárias. Eles refletem matematicamente a disponibilidade de recursos, fatores tecnológicos, condições de marketing e outros requisitos. As restrições podem ser de três tipos: "menor que ou igual", "maior que ou igual", "estritamente igual". Em nosso exemplo, os produtos A e B exigem tempo de processamento, matérias-primas e mão de obra para serem produzidos, e a disponibilidade desses recursos é limitada. Os volumes de produção destes dois produtos (ou seja, os valores x 1 de 2) serão assim limitados pelo facto de a quantidade de recursos necessários no processo de produção não poder exceder o que está disponível. Considere a situação com o tempo de processamento da máquina. A produção de cada unidade do produto A requer três horas de processamento da máquina e, se forem produzidas x 1 unidades, serão gastas 3 * x 1 horas desse recurso. A produção de cada unidade do produto B requer 10 horas e, portanto, se forem produzidos x 2 produtos, serão necessárias 10 * x 2 horas. Assim, a quantidade total de tempo de máquina necessária para produzir x 1 unidades do produto A e x 2 unidades do produto B é 3 * x 1 + 10 * x 2 . Este tempo total da máquina não pode exceder 330 horas. Matematicamente, isso é escrito da seguinte forma: 3 * x 1 + 10 * x 2 ≤ 330 Considerações semelhantes se aplicam a matérias-primas e mão de obra, permitindo que mais duas restrições sejam anotadas: 16 * x 1 + 4 * x 2 ≤ 400 6 * x 1 + 6 * x 2 ≤ 240 Finalmente, deve-se notar que existe uma condição segundo a qual pelo menos 12 unidades do produto B devem ser fabricadas: Estágio 4. Escrevendo as condições de não negatividade As variáveis exigidas não podem ser números negativos, que devem ser escritas como desigualdades x 1 ≥ 0 e x 2 ≥ 0. Em nosso exemplo, a segunda condição é redundante, pois foi determinado acima que x 2 não pode ser menor que 12. O modelo de programação linear completo para o problema de produção de Nikolai pode ser escrito como: Maximizar: Z = 2500 * x 1 + 3500 * x 2 Desde que: 3 * x 1 + 10 * x 2 ≤ 330 16 * x 1 + 4 * x 2 ≤ 400 6 * x 1 + 6 * x 2 ≤ 240 Considere um método gráfico para resolver um problema de programação linear. Este método é adequado apenas para problemas com duas variáveis necessárias. O modelo construído acima será usado para demonstrar o método. Os eixos no gráfico representam as duas variáveis desconhecidas (Fig. 2). Não importa qual variável traçar ao longo de qual eixo. É importante escolher uma escala que permita construir um diagrama visual. Como ambas as variáveis devem ser não negativas, apenas o 1º quadrante é desenhado. Arroz. 2. Eixos Gráficos de Programação Linear Considere, por exemplo, a primeira restrição: 3 * x 1 + 10 * x 2 ≤ 330. Essa desigualdade descreve a área abaixo da linha: 3 * x 1 + 10 * x 2 = 330. Essa linha intercepta o eixo x 1 em x 2 \u003d 0, ou seja, a equação fica assim: 3 * x 1 + 10 * 0 \u003d 330 e sua solução: x 1 \u003d 330 / 3 \u003d 110 Da mesma forma, calculamos os pontos de interseção com os eixos x 1 e x 2 para todas as condições de restrição: Graficamente, a primeira limitação é mostrada na Fig. 3. Arroz. 3. Construção do domínio de soluções viáveis para a primeira restrição Qualquer ponto dentro do triângulo selecionado ou em suas bordas obedecerá a essa restrição. Esses pontos são chamados de válidos e os pontos fora do triângulo são chamados de inválidos. Da mesma forma, refletimos o restante das restrições no gráfico (Fig. 4). Os valores x 1 e x 2 sobre ou dentro da área sombreada ABCDE atenderão a todas as restrições do modelo. Essa região é chamada de domínio de soluções admissíveis. Arroz. 4. A área de soluções viáveis para o modelo como um todo Agora, na área de soluções viáveis, é necessário determinar os valores x 1 e x 2 que maximizam Z. Para fazer isso, na equação da função objetivo: Z = 2500 * x 1 + 3500 * x 2 dividimos (ou multiplicamos) os coeficientes antes de x 1 e x 2 pelo mesmo número, para que os valores resultantes caiam no intervalo mostrado no gráfico; no nosso caso, esse intervalo é de 0 a 120; então os coeficientes podem ser divididos por 100 (ou 50): Z = 25x 1 + 35x 2 em seguida, atribua a Z um valor igual ao produto dos coeficientes antes de x 1 e x 2 (25 * 35 = 875): 875 = 25x 1 + 35x 2 e, finalmente, encontre os pontos de intersecção da reta com os eixos x 1 e x 2: Vamos traçar esta equação alvo no gráfico da mesma forma que as restrições (Fig. 5): Arroz. 5. Aplicação da função objetivo (linha pontilhada preta) na área de soluções viáveis O valor Z é constante em toda a linha da função objetivo. Para encontrar os valores x 1 e x 2 que maximizam Z, você precisa transferir paralelamente a linha da função objetivo para tal ponto dentro dos limites da área de soluções admissíveis, que está localizada no máximo distância da linha original da função objetivo para cima e para a direita, ou seja, até o ponto C (Fig. 6). Arroz. 6. A linha da função objetivo atingiu seu máximo dentro da região de soluções viáveis (no ponto C) Pode-se concluir que a solução ótima estará localizada em um dos pontos extremos da área de decisão. Em qual, vai depender da inclinação da função objetivo e de qual problema estamos resolvendo: maximizando ou minimizando. Assim, não é necessário desenhar uma função objetivo - basta determinar os valores de x 1 e x 2 em cada um dos pontos extremos lendo o diagrama ou resolvendo o par de equações correspondente. Os valores encontrados de x 1 e x 2 são então substituídos na função objetivo para calcular o valor correspondente de Z. A solução ótima é aquela em que o valor máximo de Z é obtido ao resolver o problema de maximização e o mínimo ao resolver o problema de minimização. Vamos determinar, por exemplo, os valores de x 1 e x 2 no ponto C. Observe que o ponto C está na interseção das linhas: 3x 1 + 10x 2 = 330 e 6x 1 + 6x 2 = 240. O solução para este sistema de equações dá: x 1 = 10, x 2 = 30. Os resultados do cálculo para todos os vértices da área de soluções viáveis são dados na tabela: Assim, Nikolai Kuznetsom deve planejar a produção de 10 itens A e 30 itens B para o próximo mês, o que lhe permitirá obter um lucro marginal de 130 mil rublos. Resumidamente, a essência do método gráfico para resolver problemas de programação linear pode ser resumida da seguinte forma: 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: Soluçã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 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 Onde podemos encontrar o valor máximo da função objetivo: . Responda: 2
.
Resolva um problema de programação linear usando o método simplex: Soluçã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 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 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 de artificial, e o método de solução é chamado de método de 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 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 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: 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"). Solução Vamos verificar a condição necessária e suficiente para a resolubilidade do problema: 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
Documentos Semelhantes
;
; 
;
; 
.
.
Tarefa número 2
ó
ó 
Então 
; ; 
- o valor mínimo da função.
ó 
ó 
ó 
; ; a função objetivo máxima é atingida quando 
; .
Tarefa número 3
Exemplos
Funções suaves e sistemas de equações
Programação linear
Otimização combinatória
Capítulo 1. Apresentação do principal problema de programação linear
Programação linear
(1.2) requisitos de não negatividade
(1.3) onde x j– variáveis (desconhecidas);
- coeficientes do problema de programação linear.1.2. Método Simplex para resolver problemas de programação linear
.6.1 Introdução
6.2. Fundamentos da teoria de otimização
X1, x2, x3,...,xn.
Problemas de programação linear
, (5.1)
, , (5.2)
, (5.3) , , , (5.5)
. ,
.
Faixa aceitável
Limite de valores permitidos
Intersecção com o eixo x 1
Intersecção com o eixo x 2
3 * x 1 + 10 * x 2 ≤ 330
3 * x 1 + 10 * x 2 = 330
x1 = 110; x 2 = 0
x1 = 0; x 2 = 33
16 * x 1 + 4 * x 2 ≤ 400
16 * x 1 + 4 * x 2 = 400
x1 = 25; x 2 = 0
x1 = 0; x 2 = 100
6 * x 1 + 6 * x 2 ≤ 240
6 * x 1 + 6 * x 2 = 240
x1 = 40; x 2 = 0
x1 = 0; x 2 = 40
x 2 ≥ 12
x 2 = 12
não cruza; corre paralelamente ao eixo x 1
x1 = 0; x 2 = 12
Ponto
Valor x 1
Valor x 2
Z \u003d 2500x 1 + 3500x 2
MAS
22
12
97 000
NO
20
20
120 000
A PARTIR DE
10
30
130 000
D
0
33
115 500
E
0
12
42 000
,
.
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: 
.
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: 
.
e 
.
.
sob as seguintes condições-restrições: 
.
: na 1ª igualdade introduzimos uma variável x 6
;
este sistema de equações tem a forma: 
.
e escolha o menor deles: min(4: 1 , 2: 2 , 10: 2) = 1.
e deles escolhemos o menor: min (3: 1 1 / 2, -, 8: 2) = 2.
,
.
=
300 + 300 + 200 = 800 .
=
250 + 400 + 150 = 800.
