Ajuda na Tele2, tarifas, dúvidas

Método simples é um método de transição sequencial de uma solução básica (vértice do poliedro da solução) de um sistema de restrições de um problema de programação linear para outra solução básica até que a função objetivo assuma um valor ótimo (máximo ou mínimo).

O método simplex é um método universal que pode resolver qualquer problema de programação linear, enquanto o método gráfico só é adequado para um sistema de restrições com duas variáveis.

O método simplex foi proposto pelo matemático americano R. Danzig em 1947. Desde então, problemas de programação linear com milhares de variáveis ​​​​e restrições têm sido frequentemente resolvidos por este método para necessidades industriais.

Antes de passar para o algoritmo do método simplex, algumas definições.

Qualquer solução não negativa para um sistema de restrições é chamada solução aceitável .

Que haja um sistema eu restrições de n variáveis ​​( eu n).

Solução básica admissível é uma solução contendo eu não negativo principal (básico ) variáveis ​​e n - eu não essencial . (não básico ou livre ) variáveis. As variáveis ​​​​menores na solução básica são iguais a zero, mas as variáveis ​​​​principais, via de regra, são diferentes de zero, ou seja, são números positivos.

Qualquer eu variáveis ​​do sistema eu equações lineares com n variáveis ​​são chamadas principal , se o determinante dos coeficientes deles for diferente de zero. Então o resto n - eu variáveis ​​são chamadas não essencial (ou livre ).

Algoritmo de método simplex

• Passo 1. Reduza o problema de programação linear à forma canônica. Para fazer isso, mova os termos livres para o lado direito (se entre esses termos livres houver negativos, multiplique a equação ou desigualdade correspondente por - 1) e introduza variáveis ​​adicionais em cada restrição (com um sinal de mais se estiver em a desigualdade original o sinal é “menor ou igual a” ", e com sinal de menos se "maior ou igual").
• Passo 2. Se no sistema resultante eu equações, então eu tome as variáveis ​​como principais, expresse as variáveis ​​principais em termos das não básicas e encontre a solução básica correspondente. Se a solução básica encontrada for admissível, passe para a solução básica admissível.
• etapa 3. Expresse a função objetivo em termos de variáveis ​​não básicas de uma solução básica admissível. Se o máximo (mínimo) de uma forma linear for encontrado e não houver variáveis ​​​​não básicas com coeficientes negativos (positivos) em sua expressão, então o critério de otimalidade é satisfeito e a solução básica resultante é ótima - a solução está completa. Se, ao encontrar o máximo (mínimo) de uma forma linear, sua expressão contém uma ou mais variáveis ​​não básicas com coeficientes negativos (positivos), prossiga para uma nova solução básica.
• Passo 4. Das variáveis ​​​​não básicas incluídas na forma linear com coeficientes negativos (positivos), selecione aquela que corresponde ao maior coeficiente (em valor absoluto) e converta-a em básicas. Vá para a etapa 2.

Termos importantes

Alguns casos especiais são discutidos em artigos separados: quando o máximo da função objetivo é infinito, Quando o sistema não tem solução, e quando a solução ótima não é a única .

A seguir, veremos um exemplo típico, quando o sistema de restrições é conjunto e existe um ótimo final e único. Uma variação do método simplex é método de distribuição para resolver um problema de transporte .

Método simplex com tabelas simplex

Ao construir tabelas simplex, resolver um problema de programação linear é muito mais fácil do que por meio de transformações algébricas, mostradas no próximo parágrafo. As tabelas simplex são muito visuais. Existem vários tipos de regras para trabalhar com tabelas simplex. Veremos uma regra que é mais frequentemente chamada de regra da coluna inicial e da linha inicial.

Seria útil abrir o manual Ações com frações em uma nova janela: há um número suficiente delas, para dizer o mínimo, em problemas que usam o método simplex.

Exemplo.

Introduzimos variáveis ​​​​não negativas adicionais e reduzimos este sistema de desigualdades ao seu sistema de equações equivalente

.

Isso foi feito obedecendo à seguinte regra: se a restrição original tiver sinal “menor ou igual”, então a variável adicional deve ser adicionada, e se “maior ou igual”, então a variável adicional deve ser subtraída.

As variáveis ​​​​adicionais introduzidas são consideradas as principais (básicas). Então e são variáveis ​​não básicas (livres).

Expressando as variáveis ​​principais (básicas) em termos de variáveis ​​não básicas (livres), obtemos

Também podemos expressar a função objetivo em termos de variáveis ​​não primárias (livres):

A partir dos coeficientes das variáveis ​​(desconhecidas) construiremos a primeira tabela simplex.

A última linha da tabela, que contém a função objetivo e os coeficientes das variáveis ​​livres nela contidas, será chamada de linha do índice.

A solução resultante não é ótima, pois na linha do índice os coeficientes das variáveis ​​livres são negativos. Ou seja, a solução ótima será aquela em que os coeficientes das variáveis ​​livres na linha do índice sejam maiores ou iguais a zero.

Para passar para a próxima tabela, vamos encontrar o maior (módulo) dos números e. Este número é 2. Portanto, a coluna inicial é a coluna na qual

Para determinar a linha inicial, encontramos a proporção mínima de termos livres para os elementos da coluna inicial e, se o numerador for um número positivo e o denominador for negativo, a proporção é considerada igual ao infinito.

.

Portanto, a linha principal é aquela em que está escrito

O elemento principal é, portanto, -2.

Compomos a segunda tabela simplex.

Inserimos o novo elemento básico na primeira linha e na coluna em que ele estava inserimos uma nova variável livre

Preencha a primeira linha. Para fazer isso, dividimos todos os números da primeira linha da Tabela 1 pelo elemento líder e os escrevemos na coluna correspondente da primeira linha da Tabela 2, exceto o número da coluna inicial, onde o inverso do líder elemento é escrito (ou seja, um dividido pelo elemento inicial).

Preencha a coluna de coeficientes auxiliares. Para este número na coluna principal da Tabela 1, além do elemento inicial, escrevemos com sinais opostos na coluna de coeficientes auxiliares da Tabela 2.

Quem ainda não abriu o manual Ações com Frações em uma nova janela pode fazê-lo agora, porque chegou a hora.

Para obter as demais linhas da tabela 2, multiplicamos os números já presentes na primeira linha desta tabela pelo coeficiente auxiliar da linha a ser preenchida, e ao resultado somamos o número da tabela 1, que está na mesma linha com a variável correspondente.

Por exemplo, para obter o termo livre da segunda linha, multiplicamos o número 1 por 1 e somamos o número -4 da tabela 1. Obtemos -3. Também encontramos o coeficiente para na segunda linha: . Como a tabela anterior não possui coluna com nova variável livre, o coeficiente da segunda linha da coluna da nova variável livre será (ou seja, adicionamos 0 da tabela 1, pois falta a coluna c na tabela 1).

A linha de índice também é preenchida:

A solução obtida desta forma novamente não é ótima, pois na linha do índice os coeficientes das variáveis ​​livres são novamente negativos.

Para passar para a próxima tabela simplex, encontramos o maior (módulo) dos números e, ou seja, os módulos dos coeficientes na linha do índice. Este número é 2. Portanto, a coluna principal é a coluna na qual .

Para encontrar a linha inicial, encontramos a proporção mínima de termos livres para os elementos da linha inicial. Nós temos:

.

Portanto, a linha inicial é aquela em que , e o elemento inicial é -3/2.

Compilando a terceira tabela simplex

Escrevemos a nova variável básica na primeira linha. Na coluna em que , inserimos uma nova variável livre.

Primeira linha:

Coeficientes auxiliares:

A solução resultante novamente não é ótima, uma vez que os coeficientes das incógnitas livres na linha do índice são novamente negativos.

Para ir para a quarta tabela simplex, encontramos o maior dos números e. Este é o número.

Portanto, a coluna inicial é aquela em que .

Módulos mínimos de relações de membros livres com elementos da coluna principal:

.

Portanto, a linha inicial é aquela em que , e o elemento inicial é 1/3.

Na quarta tabela simplex escrevemos a nova variável básica como a primeira linha. Na coluna onde escrevemos uma nova variável livre.

Primeira linha:

Coeficientes auxiliares:

Calculando as linhas restantes usando a segunda linha como exemplo:

A solução resultante também não é ótima, mas já é melhor que as anteriores, pois um dos coeficientes das variáveis ​​livres na linha do índice não é negativo.

Para melhorar o plano, vamos passar para a próxima tabela simplex.

Vamos encontrar o maior dos números 4 e . Este número é 4. Portanto, a coluna principal é .

Para encontrar a linha principal, encontramos

.

Portanto, a linha principal é aquela em que . Mas já estavam juntas entre as variáveis ​​livres. Portanto, para transferir a próxima variável de livre para básica, selecionamos outra coluna inicial - aquela em que .

Para encontrar a linha principal, encontramos

.

Portanto, a linha chave é aquela em que , e o elemento inicial é 1.

Na quinta tabela simplex escrevemos a nova variável básica como a primeira linha. Na coluna onde escrevemos uma nova variável livre.

Primeira linha:

Coeficientes auxiliares:

Vamos tentar descobrir imediatamente se a solução é ótima. Portanto, para as linhas restantes, calculamos apenas os termos livres (para saber os valores das variáveis ​​​​básicas quando as variáveis ​​​​livres são iguais a zero) e os coeficientes das variáveis ​​​​livres na linha do índice.

Membros gratuitos:

Na segunda linha;

Na terceira linha;

Na quarta linha.

Linha de índice:

Observamos a tabela simplex 5. Vemos que a solução ótima foi obtida, uma vez que os coeficientes para as incógnitas livres na linha do índice não são negativos.

Método simplex com transformações algébricas

Vamos resolver o mesmo exemplo do parágrafo anterior usando transformações algébricas. Deve-se notar que ao resolver este tipo de método simplex, é melhor não escrever a função objetivo na forma , pois é fácil se confundir nos sinais. Mas neste caso, o ponto do algoritmo que determina o critério de otimalidade será modificado da seguinte forma.

Se o máximo (mínimo) de uma forma linear for encontrado e não houver variáveis ​​​​não básicas com coeficientes positivos (negativos) em sua expressão, então o critério de otimalidade é satisfeito e a solução básica resultante é ótima - a solução está completa. Se, ao encontrar o máximo (mínimo) de uma forma linear, sua expressão contém uma ou mais variáveis ​​não básicas com coeficientes positivos (negativos), prossiga para uma nova solução básica.

Exemplo. Encontre o máximo de uma função sob restrições

Etapa I. Introduzimos variáveis ​​​​não negativas adicionais e reduzimos este sistema de desigualdades ao seu sistema de equações equivalente

.

Tomamos as variáveis ​​adicionais introduzidas como as principais, pois neste caso a solução básica do sistema é facilmente encontrada. Então e são variáveis ​​não básicas.

Expressando as principais variáveis ​​em termos de variáveis ​​não básicas, obtemos

Consequentemente, esta divisão das variáveis ​​​​em básicas e não básicas corresponde à solução básica , que é inválido (duas variáveis ​​são negativas) e, portanto, não é ideal. Desta solução básica passaremos para uma solução melhorada.

Para decidir qual variável deve ser transferida de menor para fundamental, considere qualquer uma das duas equações disponíveis deste último sistema com termos livres negativos, por exemplo a segunda. Mostra que e podem ser convertidos em variáveis ​​principais, pois nesta equação possuem coeficientes positivos (portanto, quando aumentam, e isso acontecerá se convertermos alguma delas em variáveis ​​principais, a variável aumentará).

Vamos tentar traduzi-lo na variável principal. Para estabelecer qual variável deve ser convertida de básica para não básica, encontramos o valor absoluto da menor razão entre os termos livres do sistema e os coeficientes em. Nós temos. É obtido a partir da terceira equação, que mostra que a variável positiva na solução básica original deve ser convertida em não básica. Consequentemente, a solução básica resultante, como a original, contém dois componentes negativos, ou seja, ao passar para tal solução básica, não haverá melhoria.

Programação linear é uma técnica de modelagem matemática projetada para otimizar o uso de recursos limitados. A LP é utilizada com sucesso no campo militar, na indústria, na agricultura, na indústria de transportes, na economia, no sistema de saúde e até mesmo nas ciências sociais. O uso generalizado deste método também é apoiado por algoritmos de computador altamente eficientes que implementam este método. Algoritmos de otimização para outros tipos mais complexos de modelos e problemas de pesquisa operacional (OR), incluindo programação inteira, não linear e estocástica, são baseados em algoritmos de programação linear.

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

Na sua forma mais geral, o problema de programação linear é escrito matematicamente da seguinte forma:

Onde X = (x 1 , x 2 , ... , x n ) ; C– faixa de valores permitidos de variáveis x 1 , x 2 , ... , x n ;f(X)- função objetiva.

Para resolver um problema de otimização, basta encontrar sua solução ótima, ou seja, indique aquilo em qualquer .

Um problema de otimização é insolúvel se não tiver uma solução ótima. Em particular, o problema de maximização será insolúvel se a função objetivo f(X) não é limitado de cima pelo conjunto admissível C.

Os métodos para resolver problemas de otimização dependem tanto do tipo de função objetivo f(X), e da estrutura do conjunto admissível C. Se a função alvo no problema for uma função n variáveis, então os métodos de solução são chamados de métodos de programação matemática.

As características dos problemas de programação linear são as seguintes:

índice de otimalidade f(X)é uma função linear dos elementos da solução X = (x 1 , x 2 , ... , x n ) ;

as condições restritivas impostas às soluções possíveis assumem a forma de igualdades ou desigualdades lineares.

Problema de programação linear é chamado de problema de pesquisa operacional, cujo modelo matemático tem a forma:

(2) (3) (4) (5)

Neste caso, o sistema de equações lineares (3) e desigualdades (4), (5), que determina o conjunto admissível de soluções para o problema C, chamado sistema de restrições problemas de programação linear e uma função linear f(X) chamado função alvo ou critério de otimalidade .

Solução válida é uma coleção de números ( plano ) X = (x 1 , x 2 , ... , x n ) , satisfazendo as restrições do problema. Solução ideal – este é um plano em que a função objetivo assume seu valor máximo (mínimo).

Se o modelo matemático de um problema de programação linear tiver a forma:

então eles dizem que o problema é apresentado em Forma canônica .

Qualquer problema de programação linear pode ser reduzido a um problema de programação linear na forma canônica. Para fazer isso, no caso geral, você precisa ser capaz de reduzir o problema de maximização ao problema de minimização; passar de restrições de desigualdade para restrições de igualdade e substituir variáveis ​​que não obedecem à condição de não negatividade. Maximizar uma determinada função equivale a minimizar a mesma função tomada com sinal oposto e vice-versa.

A regra para trazer um problema de programação linear para a forma canônica é a seguinte:

se no problema original for necessário determinar o máximo de uma função linear, então deve-se mudar o sinal e procurar o mínimo desta função;

se o lado direito das restrições for negativo, então esta restrição deve ser multiplicada por -1;

se houver desigualdades entre as restrições, então, ao introduzir variáveis ​​adicionais não negativas, elas serão transformadas em igualdades;

se alguma variável x j não tem restrições de sinal, então é substituída (na função objetivo e em todas as restrições) pela diferença entre duas novas variáveis ​​não negativas: x 3 =x 3 + -x 3 - , Onde x 3 + , x 3 - ≥ 0 .

Exemplo 1. Reduzindo o problema de programação linear à forma canônica:

min L = 2x 1 +x 2 -x 3 ; 2x 2 -x 3 ≤ 5; x 1 +x 2 -x 3 ≥ -1; 2x 1 -x 2 ≤ -3; x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Vamos introduzir variáveis ​​de nivelamento em cada equação do sistema de restrições x 4 , x 5 , x 6 . O sistema será escrito na forma de igualdades, e na primeira e terceira equações do sistema de restrições as variáveis x 4 , x 6 são inseridos no lado esquerdo com um sinal “+”, e na segunda equação a variável x 5 é inserido com um sinal "-".

2x 2 -x 3 +x 4 = 5; x 1 +x 2 -x 3 -x 5 = -1; 2x 1 -x 2 +x 6 = -3; x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Os termos livres na forma canônica devem ser positivos; para isso, multiplique as duas últimas equações por -1:

2x 2 -x 3 +x 4 = 5; -x 1 -x 2 +x 3 +x 5 = 1; -2x 1 +x 2 -x 6 = 3.

Método simplex para resolução de problemas de programação linear.

O algoritmo do método simplex encontra a solução ótima considerando um número limitado de soluções básicas viáveis. O algoritmo do método simplex sempre começa com alguma solução básica viável e então tenta encontrar outra solução básica viável que “melhore” o valor da função objetivo. Isto só é possível se um aumento em qualquer variável zero (não básica) levar a uma melhoria no valor da função objetivo. Mas para que uma variável não básica se torne positiva, uma das variáveis ​​básicas atuais deve ser definida como zero, ou seja, converter para não básico. Isto é necessário para que a nova solução contenha exatamente eu variáveis ​​básicas. De acordo com a terminologia do método simplex, a variável zero selecionada é chamada entrada (para a base), e a variável base a ser excluída é excluído (da base).

Vamos chamar duas regras para seleção de variáveis ​​de entrada e exclusão no método simplex condição de otimalidade E condição de admissibilidade . Vamos formular essas regras e também considerar a sequência de ações realizadas na implementação do método simplex.

Condição de otimalidade. A variável de entrada no problema de maximização (minimização) é uma variável não básica que possui o maior coeficiente negativo (positivo) em alvo-linha. Se em alvo-line contém vários desses coeficientes, então a escolha da variável inserida é feita arbitrariamente. A solução ótima é alcançada quando alvo-line, todos os coeficientes para variáveis ​​não básicas serão não negativos (não positivos).

Condição de admissibilidade. Tanto nos problemas de maximização quanto de minimização, a variável base para a qual a razão entre o valor do lado direito da restrição e o coeficiente positivo da coluna principal é mínima é selecionada como a excluída. Se existirem diversas variáveis ​​básicas com esta propriedade, então a escolha da variável excluída é arbitrária.

Vamos apresentar um algoritmo para resolver um problema de programação linear para encontrar um máximo usando tabelas simplex.

F = с 1 x 1 +с 2 x 2 +…+с n x n máx.

x 1 0, x 2 0,…, x n 0.

1º passo. Introduzimos variáveis ​​adicionais e escrevemos o sistema de equações e função linear resultante na forma de um sistema estendido.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.

2º passo. Compomos a tabela simplex inicial.

3º passo. Verificamos o cumprimento do critério de otimalidade - presença de coeficientes negativos na última linha. Se não houver nenhuma, então a solução é ótima e F * =c o, as variáveis ​​básicas são iguais aos coeficientes correspondentes b j, as variáveis ​​não básicas são iguais a zero, ou seja, X * =(b 1,b 2,…, b m, 0,…, 0).

4º passo. Se o critério de otimalidade não for atendido, então o maior coeficiente negativo absoluto na última linha (estimada) determina a coluna de resolução s.

Para determinar a linha de resolução, calculamos os índices de avaliação e preencha a última coluna da tabela.

A proporção estimada da i-ésima linha é

 se b i e a is têm sinais diferentes;

 se b i =0 e a é<0;

 se a for =0;

0 se b i =0 e a for >0;

Na coluna de relações avaliativas encontramos o elemento mínimo min que define a string de habilitação g.

Se não houver mínimo, então o problema não tem um ótimo final I e ​​é insolúvel.

Na interseção da linha e coluna de resolução há um elemento de resolução a gs.

5º passo. Vamos construir a seguinte tabela. Por esta

Vamos passar para a terceira etapa.

Método M Às vezes, ao resolver um ZLP, a matriz de coeficientes para restrições desconhecidas do sistema não possui colunas unitárias a partir das quais uma matriz unitária possa ser composta, ou seja, surge um problema na escolha das variáveis ​​de base ou a solução inicial é inaceitável. Nesses casos use método de base artificial (método M). Em todas as restrições onde não há variáveis ​​básicas, variáveis ​​artificiais. Variáveis ​​​​artificiais são introduzidas na função objetivo com um coeficiente (- M) para problemas com máximo e com um coeficiente (+ M) para problemas com mínimo, onde M é um número positivo suficientemente grande. Então o problema estendido é resolvido usando as regras do método simplex. Se todas as variáveis ​​​​artificiais forem iguais a zero, ou seja, são excluídos da base, então uma solução ótima para o problema original será obtida, ou o problema original será resolvido posteriormente e sua solução ótima será encontrada ou sua insolubilidade será estabelecida. Se pelo menos uma das variáveis ​​artificiais for diferente de zero, então o problema original não tem solução

Um método universal para resolver problemas de LP é chamado de método simplex. Aplicação deste método e sua modificação mais comum - o método simplex de duas fases.

No método gráfico de resolução de problemas de LP, escolhemos do conjunto de vértices pertencentes ao limite do conjunto de soluções do sistema de desigualdades o vértice no qual o valor da função objetivo atingiu o máximo (mínimo). No caso de duas variáveis, este método é totalmente intuitivo e permite encontrar rapidamente uma solução para o problema.

Se um problema tem três ou mais variáveis, e em problemas econômicos reais é exatamente essa a situação, fica difícil visualizar a área de solução do sistema de restrições. Tais problemas são resolvidos usando método simples ou pelo método de melhorias sucessivas. A ideia do método é simples e é a seguinte.

De acordo com uma determinada regra, o plano de referência inicial (algum vértice da área de restrição) é encontrado. Ele verifica se o plano é ideal. Se sim, então o problema está resolvido. Caso contrário, passaremos para outro plano melhorado – para outro pico. o valor da função objetivo neste plano (neste vértice) é obviamente melhor que no anterior. O algoritmo de transição é realizado utilizando uma determinada etapa computacional, que é convenientemente escrita na forma de tabelas chamadas tabelas simples . Como existe um número finito de vértices, em um número finito de etapas chegamos à solução ótima.

Consideremos o método simplex usando um exemplo específico do problema de elaboração de um plano.

Observemos mais uma vez que o método simplex é aplicável à resolução de problemas canônicos de PL reduzidos a uma forma especial, ou seja, tendo uma base, lados direitos positivos e uma função objetivo expressa em termos de variáveis ​​​​não básicas. Se a tarefa não for reduzida a um formulário especial, serão necessárias etapas adicionais, das quais falaremos mais tarde.

Consideremos o problema de um plano de produção, tendo previamente construído um modelo e dado uma forma especial.

Tarefa.

Para a fabricação de produtos A E EM O armazém não pode liberar mais de 80 unidades de matéria-prima. Além disso, para a fabricação do produto A duas unidades são consumidas e os produtos EM- uma unidade de matéria-prima. É necessário planejar a produção para que o maior lucro seja garantido se os produtos Aé necessário produzir no máximo 50 peças e produtos EM- não mais que 40 unidades. Além disso, o lucro da venda de um produto A- 5 rublos, e de EM- 3 esfregar.

Vamos construir um modelo matemático, denotando X 1 quantidade de produtos A no plano, para X 2 - número de produtos EM. então o sistema de restrições ficará assim:

x1 ≤50
x2 ≤40
2x 1 +x 2 ≤80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →máx.

Vamos trazer o problema para a forma canônica introduzindo variáveis ​​adicionais:

x1 +x3 =50
x2 +x4 =40
2x 1 +x 2 +x 5 =80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →máx.
-F = -5x 1 - 3x 2 → min.

Este problema tem uma forma especial (com base, os lados direitos são não negativos). Pode ser resolvido usando o método simplex.

EUestágio. Registrando um problema em uma tabela simplex. Existe uma correspondência biunívoca entre o sistema de restrições do problema (3.10) e a tabela simplex. Existem tantas linhas na tabela quantas igualdades no sistema de restrições, e existem tantas colunas quantas variáveis ​​livres. Variáveis ​​básicas preenchem a primeira coluna, variáveis ​​livres preenchem a linha superior da tabela. A linha inferior é chamada de linha de índice; nela estão escritos os coeficientes das variáveis ​​na função objetivo. No canto inferior direito, inicialmente escreve-se 0 se não houver membro livre na função; se houver, escreva com o sinal oposto. Neste local (no canto inferior direito) estará o valor da função objetivo, que deverá aumentar em valor absoluto ao passar de uma tabela para outra. Assim, a Tabela 3.4 corresponde ao nosso sistema de restrições, e podemos passar para a fase II da solução.

Tabela 3.4

IIestágio. Verificação do plano de referência quanto à otimização.

Esta tabela 3.4 corresponde ao seguinte plano de referência:

(X 1 , X 2 , X 3 , X 4 , X 5) = (0, 0, 50, 40, 80).

Variáveis ​​livres X 1 , X 2 é igual a 0; X 1 = 0, X 2 = 0. E as variáveis ​​básicas X 3 , X 4 , X 5 pegue valores X 3 = 50, X 4 = 40, X 5 = 80 – da coluna de termos livres. Valor da função objetivo:

-F = - 5X 1 - 3X 2 = -5 0 - 3 0 = 0.

Nossa tarefa é verificar se um determinado plano de referência é ideal. Para fazer isso, você precisa olhar para a linha de índice - a linha de função de destino F.

Várias situações são possíveis.

1. No índice F- não há elementos negativos na string. Isso significa que o plano é ideal e uma solução para o problema pode ser anotada. A função objetivo atingiu seu valor ótimo, igual ao número no canto inferior direito, tomado com sinal oposto. Vamos passar para o estágio IV.

2. A linha do índice possui pelo menos um elemento negativo cuja coluna não possui elementos positivos. Então concluímos que a função objetivo F→∞ diminui sem limite.

3. A linha do índice possui um elemento negativo que possui pelo menos um elemento positivo em sua coluna. Depois passamos para a próxima etapa III. Recalculamos a tabela, melhorando o plano de referência.

IIIestágio. Melhoria do plano de referência.

Dos elementos negativos do índice F-linhas, selecione aquela com maior módulo, chame a resolução da coluna correspondente e marque-a com “”.

Para selecionar uma linha de resolução, é necessário calcular as proporções dos elementos da coluna de termos livres apenas Para positivo elementos da coluna de resolução. Selecione o mínimo das relações obtidas. O elemento correspondente no qual o mínimo é alcançado é denominado resolução. Vamos destacá-lo com um quadrado.

No nosso exemplo, o elemento 2 é permissivo. A linha correspondente a este elemento também é chamada de resolução (Tabela 3.5).

Tabela 3.5

Selecionado o elemento permitido, recalculamos a tabela de acordo com as regras:

1. Em uma nova tabela do mesmo tamanho de antes, as variáveis ​​da linha e coluna de resolução são trocadas, o que corresponde à transição para uma nova base. No nosso exemplo: X 1 está incluído na base, em vez disso X 5, que sai da base e agora é livre (Tabela 3.6).

Tabela 3.6

2. No lugar do elemento de resolução 2, escreva seu número inverso ½.

3. Dividimos os elementos da linha de resolução pelo elemento de resolução.

4. Dividimos os elementos da coluna de resolução pelo elemento de resolução e os escrevemos com o sinal oposto.

5. Para preencher os restantes elementos da tabela 3.6, recalculamos utilizando a regra do retângulo. Digamos que queremos contar o elemento na posição 50.

Conectamos mentalmente este elemento com o que resolve, encontramos o produto, subtraímos o produto dos elementos localizados na outra diagonal do retângulo resultante. Dividimos a diferença pelo elemento de resolução.

Então, . Escrevemos 10 no lugar onde havia 50. Da mesma forma:
, , , .

Tabela 3.7

Temos uma nova tabela 3.7, as variáveis ​​básicas agora são as variáveis ​​(x 3,x 4,x 1). O valor da função objetivo passou a ser -200, ou seja, diminuiu. Para verificar a otimalidade desta solução básica, devemos voltar ao estágio II. O processo é obviamente finito; o critério de parada são os pontos 1 e 2 do estágio II.

Vamos completar a solução do problema. Para isso, vamos verificar a linha do índice e, vendo nela um elemento negativo -½, chamar a resolução da coluna correspondente e, conforme estágio III, recalcular a tabela. Depois de compilar as relações e escolher entre elas o mínimo = 40, determinamos o elemento resolutivo 1. Agora realizamos o recálculo de acordo com as regras 2-5.

Tabela 3.8

Após recalcular a tabela, certificamo-nos de que não há elementos negativos na linha do índice, portanto, o problema está resolvido, o plano básico é ótimo.

4estágio. Escrevendo a solução ideal.

Se o método simplex parou de acordo com o ponto 1 do estágio II, então a solução do problema é escrita da seguinte forma. As variáveis ​​​​base assumem os valores da coluna de termos fictícios de acordo. Em nosso exemplo X 3 = 30, X 2 = 40, X 1 = 20. As variáveis ​​livres são 0, X 5 = 0, X 4 = 0. A função objetivo assume o valor do último elemento da coluna de termos livres com sinal oposto: - F = -220 → F= 220, em nosso exemplo a função foi examinada em min, e inicialmente F→ max, então o sinal mudou duas vezes. Então, X* = (20, 40, 30, 0, 0), F* = 220. Resposta ao problema:

É necessário incluir 20 produtos do tipo no plano de produção A, 40 produtos do tipo B, enquanto o lucro será máximo e igual a 220 rublos.

Ao final desta seção, apresentamos um fluxograma do algoritmo do método simplex, que repete exatamente as etapas, mas talvez para alguns leitores seja mais conveniente de usar, pois as setas indicam uma direção clara de ações.

Os links acima das caixas do fluxograma indicam a qual estágio ou subponto pertence o grupo de transformações correspondente. a regra para encontrar o plano de referência inicial será formulada no parágrafo 3.7.

Exemplo. Resolva o seguinte problema de LP na forma canônica usando o método simplex.
f(x)=x 1 +9x 2 +5x 3 +3x 4 +4x 5 +14x 6 → min
x1 +x4 =20
x2 +x5 =50
x3 +x6 =30
x 4 +x 5 +x 6 =60
x eu ≥ 0, eu = 1,…,6
Diz-se que um problema LP tem forma canônica se todas as restrições (exceto as condições de não negatividade das variáveis) têm a forma de igualdades e todos os termos livres são não negativos. Portanto, temos o problema na forma canônica.
A ideia do método simplex é a seguinte. Primeiro você precisa encontrar algum vértice (inicial) do poliedro de soluções viáveis ​​(solução básica viável inicial). Então você precisa verificar esta solução quanto à otimização. Se for ideal, então foi encontrada uma solução; caso contrário, vá para outro vértice do poliedro e verifique novamente a otimização. Devido à finitude dos vértices do poliedro (conseqüência da finitude das restrições do problema LP), em um número finito de “etapas” encontraremos o ponto de mínimo ou máximo necessário. Deve-se notar que ao passar de um vértice para outro, o valor da função objetivo diminui (no problema mínimo) ou aumenta (no problema máximo).
Assim, a ideia do método simplex é baseada em três propriedades do problema LP.
Solução. Para encontrar a solução de base viável inicial, ou seja, para determinar as variáveis ​​de base, o sistema (5.6) deve ser reduzido a uma forma “diagonal”. Utilizando o método gaussiano (método de eliminação sequencial de incógnitas), obtemos de (5.6):
x2 +x1 +x3 =40
x 4 +x 1 =20
x 5 -x 1 -x 3 =10
x6 +x3 =30
Portanto, as variáveis ​​básicas são x 2 , x 4 , x 5 , x 6 , Damos a eles valores iguais aos membros livres das strings correspondentes: x 2 =40, x 4 =20, x 5 =10, x 6 =30,. Variáveis x 1 E x 3 não são básicos: x 1 =0, x 3 =0.
Vamos construir a solução básica viável inicial
x 0 = (0,40,0,20,10,30) (5,9)
Para verificar a otimalidade da solução encontrada x0é necessário excluir variáveis ​​básicas da função alvo (usando o sistema (5.8)) e construir uma tabela simplex especial.
Depois de eliminar as variáveis, é conveniente escrever a função objetivo na forma:
f(x) = -7x 1 – 14x 3 +880 (5,10)
Agora, usando (5.8)–(5.10), compomos a tabela simplex inicial:

A linha zero contém os coeficientes com sinal oposto das variáveis ​​correspondentes para a função objetivo. Critério de otimalidade (para o problema de busca mínimo): solução básica admissível( x0) é ideal se não houver um único número estritamente positivo na linha zero (sem contar o valor da função objetivo (880)). Esta regra também se aplica a iterações subsequentes (tabelas). Os elementos da linha zero serão chamados de estimativas de coluna.
Portanto, a solução de base viável inicial (5.9) é subótima: 7>0, 14>0 .
A coluna zero contém os valores das variáveis ​​​​básicas. Eles devem ser não negativos (ver equação (5.7)). Os coeficientes das variáveis ​​do sistema (5.8) são escritos da primeira à quarta linhas.
Porque x0 não é ideal, então precisamos passar para outro vértice do poliedro de soluções admissíveis (construir um novo d.b.r.). Para fazer isso, você precisa encontrar o elemento líder e realizar uma determinada transformação (transformação simplex).
Primeiro, encontramos o elemento principal da tabela, que fica na intersecção da coluna principal (a coluna com a pontuação positiva mais alta) e da linha principal (a linha correspondente à proporção mínima dos elementos da coluna zero para o elementos correspondentes (estritamente positivos) da coluna principal).
Na Tabela 1, a coluna inicial é a terceira coluna e a linha inicial é a quarta linha. (min(40/1,30/1)=30/1) são indicados por setas e o elemento principal é indicado por um círculo. O elemento principal indica que a variável subjacente x 6 precisa ser substituído por um não básico x 3. Então as novas variáveis ​​básicas serão x 2 , x 3 , x 4 , x 5 , e não básico - x 1, x 6,. Isto significa a transição para um novo vértice do poliedro de soluções admissíveis. Para encontrar os valores das coordenadas de uma nova solução de base viável x00 você precisa construir uma nova tabela simplex e realizar transformações elementares nela:
A) divida todos os elementos da linha principal pelo elemento principal, transformando assim o elemento principal em 1 (para facilitar o cálculo);
b) usando o elemento inicial (igual a 1), transforme todos os elementos da coluna inicial em zeros (semelhante ao método de eliminação de incógnitas);
Como resultado, os valores das novas variáveis ​​​​básicas são obtidos na coluna zero x 2 , x 3 , x 4 , x 5 ,(ver tabela 2) - componentes básicos do novo vértice x00(componentes não básicos x 1 =0, x 6 =0,).

Como mostra a Tabela 2, a nova solução básica x00 =(0,10,30,20,40,0) abaixo do ideal (a linha zero contém uma pontuação não negativa de 7). Portanto, com o elemento inicial 1 (ver Tabela 2) construímos uma nova tabela simplex, ou seja, construir uma nova solução básica viável

A Tabela 3 corresponde a uma solução básica aceitável x 000 = (10,0,30,10,50,0) e é ótimo, porque não há classificações positivas na linha zero. É por isso f(x 000)=390é o valor mínimo da função objetivo.
Responder: x000 =(10, 0, 30, 10, 50, 0)- ponto mínimo, f(x 000)=390.

Problema de programação linear convencionalmente padrão

1. Encontre o plano ideal para o problema direto:
   a) método gráfico;
   b) utilização do método simplex (para construção do plano de referência inicial recomenda-se a utilização do método de base artificial).
2. Construa um problema duplo.
3. Encontre o plano ótimo para o problema dual a partir da solução gráfica da reta, utilizando as condições de folga complementar.
4. Encontre o plano ótimo para o problema dual usando o primeiro teorema da dualidade, usando a tabela simplex final obtida pela resolução do problema direto (ver seção 1b). Verifique a afirmação “os valores das funções objetivo de um par de problemas duais coincidem em suas soluções ótimas”.
5. Resolva o problema dual usando o método simplex e, em seguida, usando a tabela simplex final do problema dual, encontre o plano ideal para o problema direto usando o primeiro teorema da dualidade. Compare o resultado com o resultado obtido graficamente (ver parágrafo 1a).
6. Encontre a solução inteira ideal:
   a) método gráfico;
   b) Método Gomori.
   Compare os valores das funções de solução inteira e não inteira

Perguntas para autocontrole

1. Como uma tabela simplex é construída?
2. Como uma mudança na base é refletida na tabela?
3. Formule um critério de parada para o método simplex.
4. Como organizar o recálculo da tabela?
5. Qual linha é conveniente para começar a recalcular a tabela?

Este método é um método de enumeração proposital de soluções de referência para um problema de programação linear. Permite, num número finito de passos, encontrar uma solução óptima ou estabelecer que não existe uma solução óptima.

1. Indique um método para encontrar a solução de referência ótima
2. Indique o método de transição de uma solução de referência para outra, na qual o valor da função objetivo estará mais próximo do ótimo, ou seja, indicar uma maneira de melhorar a solução de referência
3. Defina critérios que permitam interromper imediatamente a busca por soluções de suporte na solução ótima ou tirar uma conclusão sobre a ausência de uma solução ótima.

Algoritmo do método simplex para resolução de problemas de programação linear

1. Traga o problema para a forma canônica
2. Encontre a solução de suporte inicial com “base unitária” (se não houver solução de suporte, então o problema não tem solução devido à incompatibilidade do sistema de restrições)
3. Calcule estimativas de decomposições vetoriais com base na solução de referência e preencha a tabela do método simplex
4. Se o critério para a unicidade da solução ótima for satisfeito, então a solução do problema termina
5. Se a condição para a existência de um conjunto de soluções ótimas for atendida, então todas as soluções ótimas serão encontradas por simples enumeração

Um exemplo de resolução de um problema usando o método simplex

Resolva o problema usando o método simplex:

Solução:

Trazemos o problema para a forma canônica.

Para fazer isso, introduzimos uma variável adicional x 6 com coeficiente +1 no lado esquerdo da primeira restrição de desigualdade. A variável x 6 está incluída na função objetivo com coeficiente zero (ou seja, não está incluída).

Nós temos:

Encontramos a solução de suporte inicial. Para fazer isso, igualamos variáveis ​​​​livres (não resolvidas) a zero x1 = x2 = x3 = 0.

Nós temos solução de referência X1 = (0,0,0,24,30,6) com base unitária B1 = (A4, A5, A6).

Nós calculamos estimativas de decomposições vetoriais condições com base na solução de referência de acordo com a fórmula:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vetor de coeficientes da função objetivo para as variáveis ​​​​básicas
• X k = (x 1k, x 2k, ..., x mk) - vetor de expansão do vetor correspondente A k de acordo com a base da solução de referência
• C k é o coeficiente da função objetivo para a variável x k.

As estimativas dos vetores incluídos na base são sempre iguais a zero. A solução de referência, coeficientes de expansão e estimativas de expansões de vetores de condição com base na solução de referência são escritos em tabela simples:

No topo da tabela, para facilitar o cálculo das estimativas, estão escritos os coeficientes da função objetivo. Na primeira coluna “B” estão escritos os vetores incluídos na base da solução de referência. A ordem em que estes vetores são escritos corresponde ao número de incógnitas permitidas nas equações de restrição. Na segunda coluna da tabela “C b” os coeficientes da função objetivo para as variáveis ​​básicas são escritos na mesma ordem. Com a correta disposição dos coeficientes da função objetivo na coluna “C b”, as estimativas dos vetores unitários incluídos na base são sempre iguais a zero.

Na última linha da tabela com estimativas de Δ k na coluna “A 0” são escritos os valores da função objetivo na solução de referência Z(X 1).

A solução de suporte inicial não é ótima, pois no problema máximo as estimativas Δ 1 = -2, Δ 3 = -9 para os vetores A 1 e A 3 são negativas.

De acordo com o teorema da melhoria da solução de suporte, se em um problema máximo pelo menos um vetor tiver estimativa negativa, então será possível encontrar uma nova solução de suporte na qual o valor da função objetivo será maior.

Vamos determinar qual dos dois vetores levará a um incremento maior na função objetivo.

O incremento da função objetivo é encontrado pela fórmula: .

Calculamos os valores do parâmetro θ 01 para a primeira e terceira colunas usando a fórmula:

Obtemos θ 01 = 6 para l = 1, θ 03 = 3 para l = 1 (Tabela 26.1).

Encontramos o incremento da função objetivo ao introduzir na base o primeiro vetor ΔZ 1 = - 6*(- 2) = 12, e o terceiro vetor ΔZ 3 = - 3*(- 9) = 27.

Consequentemente, para uma abordagem mais rápida à solução ótima, é necessário introduzir o vetor A3 na base da solução de referência em vez do primeiro vetor da base A6, uma vez que o mínimo do parâmetro θ 03 é alcançado na primeira linha ( eu = 1).

Realizamos a transformação de Jordan com o elemento X13 = 2, obtemos a segunda solução de referência X2 = (0,0,3,21,42,0) com base B2 = (A3, A4, A5). (Tabela 26.2)

Esta solução não é ótima, pois o vetor A2 tem uma estimativa negativa Δ2 = - 6. Para melhorar a solução é necessário introduzir o vetor A2 na base da solução de referência.

Determinamos o número do vetor derivado da base. Para fazer isso, calculamos o parâmetro θ 02 para a segunda coluna, é igual a 7 para l = 2. Conseqüentemente, derivamos o segundo vetor de base A4 da base. Realizamos a transformação de Jordan com o elemento x 22 = 3, obtemos a terceira solução de referência X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabela 26.3).

Esta solução é a única ótima, pois para todos os vetores não incluídos na base as estimativas são positivas

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Responder: máx. Z(X) = 201 em X = (0,7,10,0,63).

Método de programação linear em análise econômica

Método de programação linear permite justificar a solução económica mais óptima em condições de severas restrições relacionadas com os recursos utilizados na produção (activos fixos, materiais, recursos laborais). A utilização deste método na análise econômica permite solucionar problemas relacionados principalmente ao planejamento das atividades de uma organização. Este método ajuda a determinar as quantidades ideais de produção, bem como as orientações para o uso mais eficaz dos recursos de produção disponíveis para a organização.

Utilizando este método, são resolvidos os chamados problemas extremos, que consiste em encontrar valores extremos, ou seja, o máximo e o mínimo de funções de grandezas variáveis.

Este período baseia-se na resolução de um sistema de equações lineares nos casos em que os fenómenos económicos analisados ​​​​estão ligados por uma dependência linear e estritamente funcional. O método de programação linear é utilizado para analisar variáveis ​​na presença de determinados fatores limitantes.

É muito comum resolver o chamado problema de transporte utilizando o método de programação linear. O conteúdo desta tarefa é minimizar os custos incorridos com a operação de veículos sob as restrições existentes quanto ao número de veículos, sua capacidade de carga, duração da sua operação, caso haja necessidade de atender o número máximo de clientes.

Além disso, este método é amplamente utilizado na resolução do problema de escalonamento. Esta tarefa consiste numa distribuição do tempo de trabalho do pessoal de uma determinada organização que seja mais aceitável tanto para os membros desse pessoal como para os clientes da organização.

Esta tarefa consiste em maximizar o número de clientes atendidos em condições de limitação do número de funcionários disponíveis, bem como do fundo de tempo de trabalho.

Assim, o método de programação linear é muito comum na análise da colocação e utilização de diversos tipos de recursos, bem como no processo de planejamento e previsão das atividades das organizações.

No entanto, a programação matemática também pode ser aplicada a fenómenos económicos cuja relação não é linear. Para tanto, podem ser utilizados métodos de programação não linear, dinâmica e convexa.

A programação não linear depende da natureza não linear da função objetivo ou das restrições, ou de ambas. As formas da função objetivo e das restrições de desigualdade nessas condições podem ser diferentes.

A programação não linear é utilizada na análise económica, em particular, ao estabelecer a relação entre indicadores que expressam a eficiência das atividades de uma organização e o volume desta atividade, a estrutura dos custos de produção, as condições de mercado, etc.

A programação dinâmica é baseada na construção de uma árvore de decisão. Cada nível desta árvore serve como um estágio para determinar as consequências de uma decisão anterior e para eliminar opções ineficazes para essa decisão. Assim, a programação dinâmica tem uma natureza multietapas e multiestágios. Este tipo de programação é utilizado na análise econômica para encontrar opções ótimas para o desenvolvimento de uma organização agora e no futuro.

A programação convexa é um tipo de programação não linear. Este tipo de programação expressa a natureza não linear da relação entre os resultados das atividades de uma organização e os seus custos. A programação convexa (também conhecida como côncava) analisa funções objetivo convexas e sistemas de restrição convexos (pontos de viabilidade). A programação convexa é utilizada na análise das atividades económicas com o objetivo de minimizar custos, e a programação côncava com o objetivo de maximizar os rendimentos face às restrições existentes à ação dos fatores que influenciam os indicadores analisados ​​no sentido inverso. Consequentemente, com os tipos de programação em consideração, as funções objetivo convexas são minimizadas e as funções objetivo côncavas são maximizadas.

Linha, botões e tecido são usados ​​para fazer três tipos de camisas. Os estoques de linhas, botões e tecidos, as normas de seu consumo para costura de uma camisa estão indicadas na tabela. Encontre o lucro máximo e o plano ideal de produção do produto que o garante (encontre).

A solução do problema

Construção de modelo

Através e a quantidade de camisas do 1º, 2º e 3º tipos destinadas ao lançamento.

Então as restrições de recursos ficarão assim:

Além disso, de acordo com o significado da tarefa

Função objetivo que expressa o lucro recebido:

Obtemos o seguinte problema de programação linear:

Reduzindo um problema de programação linear à forma canônica

Reduzamos o problema à forma canônica. Vamos introduzir variáveis ​​adicionais. Introduzimos todas as variáveis ​​adicionais na função objetivo com um coeficiente igual a zero. Adicionamos variáveis ​​adicionais aos lados esquerdos das restrições que não possuem uma forma preferencial e obtemos igualdades.

Resolvendo o problema usando o método simplex

Preencha a tabela simplex:

Como estamos resolvendo o problema ao máximo, a presença de números negativos na linha do índice ao resolver o problema ao máximo indica que não obtivemos a solução ótima e que é necessário passar da tabela da 0ª iteração para o próximo.

Prosseguimos para a próxima iteração da seguinte forma:

coluna principal corresponde

A linha chave é determinada pela proporção mínima de termos livres e membros da coluna principal (relações simplex):

Na intersecção da coluna-chave e da linha-chave encontramos o elemento de habilitação, ou seja, 9.

Agora procedemos à compilação da 1ª iteração: Em vez de um vetor unitário, introduzimos o vetor .

Na nova tabela, no lugar do elemento habilitador escrevemos 1, todos os demais elementos da coluna chave são zeros. Os elementos da string chave são divididos no elemento enable. Todos os outros elementos da tabela são calculados usando a regra do retângulo.

A coluna chave para a 1ª iteração corresponde a

O elemento de resolução é o número 4/3. Derivamos o vetor da base e introduzimos o vetor. Obtemos a tabela da 2ª iteração.

A coluna chave para a 2ª iteração corresponde a

Encontramos a linha chave, para isso definimos:

O elemento de resolução é o número 10/3. Derivamos o vetor da base e introduzimos o vetor. Obtemos a tabela da 3ª iteração.

Na linha do índice, todos os termos são não negativos, então a seguinte solução para o problema de programação linear é obtida (escrevemos na coluna de termos livres):

É necessário costurar 24 camisas do 1º tipo, 7 camisas do 2º tipo e 3 camisas do 3º tipo. Nesse caso, o lucro recebido será máximo e totalizará 95 rublos.