Solução de tabelas simplex online em detalhes. Exemplo de solução de problema

11.4. MÉTODO DUAL SIMPLEX

Segue dos resultados das seções anteriores que para obter uma solução para o problema original, podemos passar para o dual e, usando estimativas de seu projeto ótimo, determinar a solução ótima para o problema original.

A transição para o problema dual não é necessária, pois se considerarmos o primeiro tableau simplex com uma base adicional de unidade, é fácil ver que as colunas contêm o problema original e o problema dual é escrito nas linhas.

Como foi mostrado, ao resolver o problema direto em qualquer iteração, a diferença, ou seja magnitude -coeficiente com uma variável, é igual à diferença entre os lados direito e esquerdo da restrição correspondente do problema dual. Se, ao resolver um problema direto com uma função objetivo maximizável, a iteração não leva a uma solução ótima, então pelo menos para uma variável e apenas no ótimo para todas diferença .

Considerando esta condição com dualidade levada em conta, podemos escrever

.

Assim, se, então . Isso significa que quando a solução para o problema primal não é ótima, a solução para o problema dual é inválida. Por outro lado no . Isso implica que a solução ótima do problema primal corresponde a uma solução admissível do problema dual.

Isso possibilitou o desenvolvimento de um novo método para resolver problemas de programação linear, ao usar o qual, a princípio, é obtida uma solução inaceitável, mas “melhor que ótima” (no método simplex usual, primeiro admissível, mas abaixo do ideal solução). Um novo método chamado método dual simplex, garante o cumprimento da condição de otimalidade da solução e sua sistemática “aproximação” à área de soluções viáveis. Quando a solução obtida for admissível, o processo iterativo de cálculos termina, pois essa solução também é ótima.

O método dual simplex permite resolver problemas de programação linear cujos sistemas de restrições, com base positiva, contêm termos livres de qualquer sinal. Este método permite reduzir o número de transformações do sistema de restrições, bem como o tamanho da tabela simplex. Considere a aplicação do método dual simplex usando um exemplo.

Exemplo. Encontre o mínimo de uma função

sob restrições

.

Vamos para a forma canônica:

sob restrições

O tableau simplex inicial tem a forma

Básico variáveis	x 1	x 2	x 3	x 4	x 5	Solução
x 3 x 4 x 5	–3 –4	–1 –3				–3 –6
	–2	–1

Solução básica inicialideal, mas não aceitável.

Como o método simplex usual, o método de solução em consideração é baseado no uso de condições de admissibilidade e otimalidade.

Condição de admissibilidade. A maior variável básica negativa em valor absoluto é escolhida como variável excluída (se houver alternativas, a escolha é feita arbitrariamente). Se todas as variáveis ​​básicas forem não negativas, o processo de computação termina, pois a solução resultante é viável e ótima.

Doença otimalidade. A variável incluída na base é selecionada dentre as variáveis ​​não básicas como segue. As razões dos coeficientes do lado esquerdo são calculadas-equações aos coeficientes correspondentes da equação associada à variável excluída. As relações com denominadores positivos ou nulos não são levadas em consideração. No problema de minimização da variável de entrada, a menor das razões indicadas deve corresponder, e no problema de maximização, a razão com o menor valor absoluto (se houver alternativas, a escolha é feita arbitrariamente). Se os denominadores de todas as razões forem zero ou positivos, o problema não tem soluções viáveis.

Após a escolha das variáveis ​​a serem incluídas na base e a serem excluídas, é realizada a operação usual de transformação das linhas da tabela simplex para obter a próxima solução.

Neste exemplo, a variável excluída é. Os índices calculados para determinar a nova variável base são mostrados na tabela a seguir:

Variáveis	x 1	x 2	x 3	x 4	x 5
A equação x 4 - equação	–2 –4	–1 –3
Atitude

A variável a ser incluída é x 2. A conversão de string subsequente resulta em uma nova tabela simplex:

Básico variáveis	x 1	x 2	x 3	x 4	x 5	Solução
x 3 x 2 x 5						–1 –1

Nova solução também ideal, mas ainda inválido. Como uma nova variável excluída, escolhemos (arbitrariamente) x 3 . Vamos definir uma variável incluída.

Variáveis	x 1	x 2	x 3	x 4	x 5
A equação x 4 - equação
atitude

Método Simplex - este é um método de transição sucessiva de uma solução básica (o vértice do poliedro da solução) do sistema de restrições de um problema de programação linear para outra solução básica até que a função objetivo assuma o 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 é adequado apenas para um sistema de restrição de duas variáveis.

O método simplex foi proposto pelo matemático americano R. Danzig em 1947, desde então, para as necessidades da indústria, esse método costuma resolver problemas de programação linear com milhares de variáveis ​​e restrições.

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 .

Seja um sistema m restrições de n variáveis ​​( m n).

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

Algum m variáveis ​​do sistema m equações lineares com n variáveis ​​são chamadas a Principal , se o determinante dos coeficientes neles for diferente de zero. Então o resto n - m variáveis ​​são chamadas não essencial (ou gratuitamente ).

Algoritmo do Método Simplex

• Passo 1. Traga o problema de programação linear para a forma canônica. Para fazer isso, mova os termos livres para o lado direito (se entre esses termos livres forem 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 no desigualdade original o sinal é menor ou igual a ", e com um sinal de menos se "maior ou igual a").
• Passo 2. Se no sistema resultante m equações, então m tome as variáveis ​​como as 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, vá para a solução básica admissível.
• etapa 3. Expresse a função objetivo em termos das variáveis ​​menores da solução básica viável. Se o máximo (mínimo) da 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 é atendido e a solução básica resultante é ótima - a solução acabou. Se, ao encontrar o máximo (mínimo) de uma forma linear, sua expressão contiver uma ou mais variáveis ​​não básicas com coeficientes negativos (positivos), vá 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), escolha aquela que corresponde ao maior coeficiente (módulo) e transfira-a para as principais. Vá para a etapa 2.

Condições importantes

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

A seguir, analisaremos um exemplo típico, quando o sistema de restrições é consistente e existe um ótimo finito, e apenas um. Uma variação do método simplex é método de distribuição para resolver o problema de transporte .

Método simplex com tabelas simplex

Construindo tabelas simplex, é muito mais fácil resolver um problema de programação linear do que por meio de transformações algébricas, o que é mostrado no próximo parágrafo. As tabelas simplex são muito visuais. Existem vários tipos de regras para trabalhar com tabelas simplex. Analisaremos a regra, que geralmente é chamada de regra da coluna principal e da linha principal.

Seria útil abrir o manual Ações com frações em uma nova janela: há bastante delas, frações em problemas no método simplex, para dizer o mínimo.

Exemplo.

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

.

Isso foi feito de acordo com a seguinte regra: se o sinal na restrição original for "menor ou igual a", então a variável adicional deve ser somada, e se "maior que ou igual a", então a variável adicional deve ser subtraído.

As variáveis ​​adicionais introduzidas são tidas como 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 não básicas (livres), obtemos

Também expressamos a função objetivo em termos de variáveis ​​não básicas (livres):

A partir dos coeficientes das variáveis ​​(desconhecidas) construímos o primeiro tableau simplex.

tabela 1
Incógnitas básicas	Membros gratuitos	Incógnitas soltas		Coeficientes auxiliares
		X1	X2
X3	-2	1	-2
X4	-4	-1	-1
X5	2	1	-1
X6	6	0	1
F	0	-1	-2

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

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

Para ir para a próxima tabela, encontre o maior (módulo) dos números e . Este número é 2. Portanto, a coluna inicial é a coluna na qual está escrito

Para determinar a linha principal, encontramos o mínimo das razões dos membros livres para os elementos da coluna principal, e se o numerador tiver um número positivo e o denominador for negativo, a razão é considerada igual ao infinito.

.

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

O elemento principal é, portanto, -2.

Compomos a segunda tabela simplex.

Entramos no novo elemento básico na primeira linha e inserimos a coluna em que 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 inicial e escrevemos na coluna correspondente da primeira linha da tabela 2, exceto o número da coluna inicial, onde o inverso do primeiro elemento é escrito (ou seja, um dividido pelo elemento principal).

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

mesa 2
Incógnitas básicas	Membros gratuitos	Incógnitas soltas		Coeficientes auxiliares
		X1	X3
X2	1	-1/2	-1/2
X4	-3	-3/2	-1/2	1
X5	3	1/2	-1/2	1
X6	5	1/2	1/2	-1
F	2	-2	-1	2

Quem ainda não abriu em uma nova janela o manual Ações com frações, pode fazê-lo agora, porque está na hora.

Para obter as demais linhas da tabela 2, os números já na primeira linha desta tabela são multiplicados pelo coeficiente auxiliar na linha que está sendo 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 membro livre da segunda linha, multiplicamos o número 1 por 1 e adicionamos o número -4 da tabela 1. Obtemos -3. Encontramos o coeficiente para na segunda linha da mesma maneira: . Como não há coluna com nova variável livre na tabela anterior, o coeficiente da segunda linha da coluna da nova variável livre será (ou seja, da tabela 1 adicionamos 0, pois não há coluna c na tabela 1).

A linha de índice é preenchida da mesma maneira:

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

Para ir para a próxima tabela simplex, vamos encontrar o maior (módulo) dos números e , ou seja, os módulos dos coeficientes na linha de índice. Esse número é 2. Portanto, a coluna inicial é a coluna que contém .

Para procurar a linha principal, vamos encontrar a proporção mínima de membros gratuitos para os elementos da linha principal. Nós temos:

.

Portanto, a linha principal é aquela em que está escrito e o elemento principal é -3/2.

Compilando a terceira tabela simplex

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

Primeira linha:

Coeficientes auxiliares:

Tabela 3
Incógnitas básicas	Membros gratuitos	Incógnitas soltas		Coeficientes auxiliares
		X4	X3
X1	2	-2/3	1/3
X2	2	-1/3	-1/3	1/2
X5	2	1/3	-2/3	-1/2
X6	4	1/3	1/3	-1/2
F	6	-4/3	-1/3	2

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

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

Portanto, a coluna principal é aquela com .

Módulo mínimo de relações de membros livres para elementos da coluna principal:

.

Portanto, a linha principal é aquela em que está escrito e o elemento principal é 1/3.

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

Primeira linha:

Coeficientes auxiliares:

Tabela 4
Incógnitas básicas	Membros gratuitos	Incógnitas soltas		Coeficientes auxiliares
		X5	X3
X4	6	3	-2
X1	6	2	-1	2/3
X2	4	1	-1	1/3
X6	2	-1	1	-1/3
F	14	4	-3	4/3

Cálculo das linhas restantes usando o exemplo da segunda linha:

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

Para melhorar o plano, vamos passar para o próximo quadro simplex.

Encontre o maior dos números 4 e . Esse número é 4. Portanto, a coluna inicial é .

Para encontrar a linha principal, encontre

.

Portanto, a linha principal é aquela que contém . Mas eles já estavam juntos entre as variáveis ​​livres. Portanto, para transferir a próxima variável de livre para básica, selecionamos outra coluna inicial - aquela na qual está escrita.

Para encontrar a linha principal, encontre

.

Portanto, a linha chave é aquela em que está escrito e o elemento principal é 1.

Na quinta tabela simplex, a nova variável básica é escrita na primeira linha. Na coluna onde estava, escrevemos uma nova variável livre .

Primeira linha:

Coeficientes auxiliares:

Tabela 5
Incógnitas básicas	Membros gratuitos	Incógnitas soltas		Coeficientes auxiliares
		X5	X6
X3	2	-1	1
X4	10			2
X1	8			1
X2	6			1
F	20	1	3	3

Vamos tentar descobrir imediatamente se a solução não é ótima. Portanto, para as linhas restantes, calculamos apenas os termos livres (para descobrir 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, pois os coeficientes para incógnitas livres na linha do índice são não negativos.

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

Vamos resolver por transformações algébricas o mesmo exemplo do parágrafo anterior. Deve-se notar que, ao resolver esse tipo de método simplex, é melhor não escrever a função objetivo na forma , já que é 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) da 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 é atendido e a solução básica resultante é ótima - a solução acabou. Se, ao encontrar o máximo (mínimo) de uma forma linear, sua expressão contiver uma ou mais variáveis ​​não básicas com coeficientes positivos (negativos), vá 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 a um sistema de equações equivalente

.

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

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

Consequentemente, essa divisão de 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 é o ideal. Vamos passar desta solução básica para uma melhorada.

Para decidir qual variável deve ser transferida de não principal para principal, considere qualquer uma das duas equações disponíveis do último sistema com termos livres negativos, por exemplo, a segunda. Mostra que e pode ser traduzido nas variáveis ​​principais, pois nesta equação elas possuem coeficientes positivos (portanto, quando aumentam, e isso acontecerá se traduzirmos alguma delas nas variáveis ​​principais, a variável aumentará).

Vamos tentar traduzir para a variável principal . Para determinar qual variável deve ser transferida do principal para o não básico, encontramos o valor absoluto da menor razão dos membros livres do sistema para os coeficientes em . Nós temos . Ele é obtido a partir da terceira equação, que mostra que a variável deve ser convertida para não-básicas, o que é positivo na solução básica original. Consequentemente, a solução básica obtida, como a original, contém dois componentes negativos, ou seja, não haverá melhora na transição para tal solução básica.

Método Simplex− é um método de enumeração ordenada de planos de referência (a ordenação é assegurada por uma mudança monótona no valor da função objetivo durante a transição para o próximo plano). Nesse caso, é necessário observar o princípio: cada próximo passo deve melhorar ou, em casos extremos, não piorar o valor da função objetivo.

Para resolver o LLP método simplexé reduzido à forma canônica, i.e. de restrições - desigualdades é necessário fazer restrições - igualdades. Para fazer isso, cada restrição é complementada com um valor adicional não negativo. variável de balanço com o sinal “+” se o sinal de desigualdade for “£”, e com o sinal “–” se o sinal de desigualdade for “³”.

Na função objetivo, essas variáveis ​​adicionais entram com coeficientes zero, ou seja, a entrada da função de destino não será alterada. Cada variável que não está sujeita à condição de não negatividade pode ser representada como a diferença de duas variáveis ​​não negativas: .

Se as restrições da tarefa refletirem a presença e o consumo de recursos, o valor numérico da variável adicional no plano de tarefas, escrito em forma canônica, será igual à quantidade de recurso não utilizado.

Para resolver o problema pelo método simplex, usaremos tabelas simplex encurtadas de um sistema de equações lineares e o método de eliminação de Jordan modificado.

1. Elaboramos o primeiro plano básico

A tarefa continua a mesma. Vamos trazer a forma padrão do sistema de desigualdades (1) para a forma canônica do sistema de equações introduzindo variáveis ​​de equilíbrio adicionais x 3 , x 4 , x 5 ,x 6 .

No sentido econômico, os valores das variáveis ​​adicionais x 3 , x 4 , x 5 determinar o saldo de matérias-primas após a venda de produtos.

A matriz do sistema de equações resultante tem a forma:

Pode-se ver que na matriz UMA a base menor de 4ª ordem é o determinante, composto por coeficientes unitários para variáveis ​​adicionais x 3 , x 4 , x 5 ,x 6 , uma vez que é diferente de zero e igual a 1. Isso significa que os vetores de coluna para essas variáveis ​​são linearmente independentes, ou seja. Formato base, e as variáveis ​​correspondentes x 3 , x 4 , x 5 ,x 6 são básico(básico). Variáveis x 1 , x 2 será chamado gratuitamente(menor).

Se variáveis ​​livres x 1 e x 2 para definir valores diferentes, então, resolvendo o sistema em relação às variáveis ​​básicas, obtemos um conjunto infinito de soluções particulares. Se apenas valores zero forem definidos para variáveis ​​livres, então de um conjunto infinito de soluções particulares, soluções básicas- planos básicos.

Para saber se as variáveis ​​podem ser básicas, é necessário calcular o determinante constituído pelos coeficientes dessas variáveis. Se esse determinante não for igual a zero, então essas variáveis ​​podem ser básicas.

O número de soluções básicas e o número correspondente de grupos de variáveis ​​básicas não podem ser maiores que , onde né o número total de variáveis, ré o número de variáveis ​​básicas, r≤ m≤ n.

Para nossa tarefa r = 4; n= 6. Então , ou seja. São possíveis 15 grupos de 4 variáveis ​​básicas (ou 15 soluções básicas).

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

Supondo que as variáveis ​​livres x 1 = 0, x 2 = 0, obtemos os valores das variáveis ​​básicas: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, ou seja a solução básica será = (0; 0; 312; 15; 24; -10).

Esta solução básica é inaceitável, Porque x 6 = –10 ≤ 0, e pela condição de restrição x 6 ≥ 0. Portanto, em vez da variável x 6 como base, você precisa pegar outra variável entre as x 1 ou x 2 .

Vamos realizar a solução adicional usando tabelas simplex encurtadas, preenchendo as linhas da primeira tabela com os coeficientes do sistema da seguinte forma (Tabela 1):

tabela 1

F- a string é chamada índice. Ele é preenchido com coeficientes da função objetivo tomados com sinais opostos, pois a equação da função pode ser representada como F = 0 – (– 4x 1 – 3x 2).

Na coluna de membros livres b eu existe um elemento negativo b 4 = -10, ou seja a solução do sistema é inválida. Para obter uma solução válida (plano base), o elemento b 4 deve ser não negativo.

Escolher x 6 - uma linha com um membro livre negativo. Esta linha contém elementos negativos. Escolha qualquer um deles, por exemplo, "-1" em x 1-coluna, e x 1 - coluna aceita como coluna de permissão(vai determinar que a variável x 1 passará de gratuito para básico).

Compartilhamos membros gratuitos b eu sobre os elementos relevantes um é coluna de resolução, obtemos relações avaliativasΘ eu==(24, 15, 12, 10). Destes, escolhemos o menor positivo (minΘ eu=10), que corresponderá a linha de permissão. A string de permissão define uma variável xj, que na etapa seguinte se projeta da base e se torna livre. É por isso x 6 -line é uma linha permissiva e o elemento "-1" é elemento de habilitação. Nós o circundamos. Variáveis x 1 e x 6 são trocados.

Razões estimadas Θ eu em cada linha são determinados pelas regras:

1) Θ eu= se b eu e um é têm sinais diferentes;

2) Θ eu= ∞ se b eu= 0 e um é < 0;

3) Θ eu= ∞ se um é = 0;

4) Θ eu= 0 se b eu= 0 e um é > 0;

5) Θ eu= se b eu e um é têm os mesmos sinais.

Damos o passo da eliminação jordaniana modificada (MJJI) com um elemento permissivo e compilamos uma nova tabela (Tabela 2) de acordo com a seguinte regra:

1) no lugar do elemento de resolução (RE), um valor é definido, seu inverso, ou seja, ;

2) os elementos da linha permissiva são divididos em RE;

3) os elementos da coluna de resolução são divididos em RE e o sinal muda;

4) os elementos restantes são encontrados de acordo com a regra do retângulo:

Da Tabela. 2 mostra que os membros livres em b eu-coluna são não negativos, portanto, a solução inicial admissível é obtida - primeiro plano básico= (10; 0; 182; 5; 4; 0). Neste caso, o valor da função F() = 40. Geometricamente, isso corresponde ao topo F(10; 0) polígono de solução (Fig. 1).

mesa 2

2. Verificamos a otimização do plano. O plano básico não é o ideal, porque em F-line tem um coeficiente negativo "-4". Melhoramos o plano.

3. Encontrando uma nova linha de base

Selecionamos o elemento de permissão de acordo com a regra:

Escolhemos o menor coeficiente negativo em F-line "-4", que determina a coluna de habilitação - x 6; variável x 6 traduzem em básico;

Encontramos as razões Θ eu, entre eles escolhemos o menor positivo, que corresponde à string permissiva:

min Θ eu = min(14, 5, 2, ∞) = 2, portanto x 5 - linha - permissivo, variável x 5 traduzimos em livre (variáveis x 5 e x 6 são trocados).

Na interseção da linha e coluna permissivas está o elemento permissivo "2";

Executamos a etapa SHMZhI, construímos a tabela. 3 de acordo com a regra acima e obtenha um novo plano de referência = (12; 0; 156; 3; 0; 2).

Tabela 3

4. Verificando a otimização do novo plano básico

O plano básico também não é o ideal, pois em F-line tem um coeficiente negativo "-1". Valor da função F() = 48, que corresponde geometricamente ao topo E(12; 0) polígono de solução (Fig. 1). Melhoramos o plano.

5. Encontrando uma nova linha de base

x 2-coluna é permissiva, pois em F-linha o menor coeficiente negativo "-1" está em x 2 colunas (Δ 2 = -1). Encontrando o menor Θ eu: min Θ eu = min(≈ 9, 6, ∞, 24) = 6, portanto x 4ª linha - permissivo. Elemento permissivo "1/2". Trocando variáveis x 2 e x quatro. Executamos a etapa SHMZhI, construímos a tabela. 4, obtemos um novo plano de referência = (9; 6; 51; 0; 0; 5).

6. Verificando a otimização do plano básico

NO F-line, todos os coeficientes são não negativos, portanto, o plano de referência é ótimo. corresponde geometricamente a um ponto D(9;6) (ver Fig. 1). O plano ótimo fornece o valor máximo da função objetivo c.u.

Principal a ideia de um método simplex para resolver o LLP consiste na melhoria consistente das soluções de suporte LLP.

Existem várias maneiras de escrever o método simplex.

1. A forma básica do método simplex;
2. Método simplex na forma de uma tabela simplex;
3. Método simplex modificado;
4. Método simplex em forma colunar;
5. Método simplex em forma de linha.

Vamos definir o valor máximo da função objetivo F(X) = 3x 1 +5x 2 +4x 3 sob as seguintes condições de restrição.
0,1x 1 +0,2x 2 +0,4x 3 ≤1100
0,05x 1 +0,02x 2 +0,02x 3 ≤120
3x1 +x2 +2x3 ≤8000

Para construir o primeiro plano de referência, reduzimos o sistema de desigualdades a um sistema de equações introduzindo variáveis ​​adicionais (transição para a forma canônica).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000

Notação básica do método simplex

A solução é realizada expressando as variáveis ​​básicas por meio de variáveis ​​não básicas: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0,1x 1 -0,2x 2 -0,4x 3 x 5 = 120-0,05x 1 -0,02x 2 -0,02x 3 x 6 = 8000-3x 1 -x 2 -2x 3

Método simplex na forma de uma tabela simplex

A solução é realizada na forma de uma tabela simplex. O formulário é projetado para computação em um computador. Ao usar uma base artificial, é usado um número especial M (geralmente 10000).

Plano	Base	NO	x 1	x2	x 3	x4	x5	x6	min
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
Linha de índice	F(X1)	0	-3	-5	-4	0	0	0	0
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Linha de índice	F(X2)	27500	-0.5	0	6	25	0	0	0
3	x2	5375	0	1	2.25	6.25	-12.5	0	11000
	x1	250	1	0	-0.5	-2.5	25	0	250
	x6	1875	0	0	1.25	1.25	-62.5	1	1000
Linha de índice	F(X3)	27625	0	0	5.75	23.75	12.5	0	0

Método simplex modificado

Matriz de coeficientes A = a ij Matriz b. Iteração #1. = (4, 5, 6) Matriz c. c = (-3, -5, -4, 0, 0, 0) cB = (0, 0, 0) cN = (-3, -5, -4) Calculamos: A matriz B -1 é calculada através de adições algébricas. u = c B B -1 = (0, 0, 0)

Método Simplex em forma colunar

Passamos para a forma colunar do método simplex. Expressamos cada variável em termos de variáveis ​​não básicas. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0,1(-x 1)+0,2(-x 2)+0,4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0,05(-x 1)+0,02(-x 2)+0,02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Este sistema corresponde à tabela T 0 . 0 -1 0 0 0 0 -1 0 0 0 0 -1 1100 0.1 0.2 0.4 120 0.05 0.02 0.02 8000 3 1 2 0 -3 -5 -4

Método Simplex em forma de string

Como base inicial admissível, podemos tomar B 0 =<4, 5, 6>. Corresponderá à tabela a seguir. 1100 0.1 0.2 0.4 1 0 0 120 0.05 0.02 0.02 0 1 0 8000 3 1 2 0 0 1 0 -3 -5 -4 0 0 0

A matriz Q, composta pelos coeficientes do sistema, é chamada tabela simplex correspondente à base B. Um tableau simplex é chamado admissível, ou diretamente admissível, se q i0 ≥ 0. Os elementos q i0 da última linha da tabela simplex Q são chamados estimativas relativas.

Formas de solução pelo método de base artificial

Para o uso de variáveis ​​artificiais introduzidas na função objetivo, é imposta a chamada penalidade de M, um número positivo muito grande, que geralmente não é especificado.
A base resultante é chamada artificial, e o método de solução é chamado de método da base artificial.
Além disso, as variáveis ​​artificiais não estão relacionadas ao conteúdo da tarefa, mas permitem construir um ponto de partida, e o processo de otimização força essas variáveis ​​a assumir valores zero e garantir a admissibilidade da solução ótima.

Formas de solução pelo método de base artificial:

1. M-método (tabela simplex);
2. método simplex de duas fases ou duas fases (Notação básica, método simplex modificado, método simplex em forma de coluna, método simplex em forma de linha).

Se houver restrições com o sinal ≥ na condição do problema, elas podem ser reduzidas à forma ∑a ji b j multiplicando ambas as partes da desigualdade por -1. Introduzimos m variáveis ​​adicionais x n+j ≥0(j =1,m ) e transformamos as restrições na forma de igualdades

(2)

Suponhamos que todas as variáveis ​​iniciais do problema x 1 , x 2 ,..., x n sejam não básicas. Então as variáveis ​​adicionais serão básicas, e uma solução particular para o sistema de restrições tem a forma

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j = 1,m . (3)

Como neste caso o valor da função objetivo F 0 = 0 , podemos representar F(x) da seguinte forma:

F(x)=∑c i x i + F 0 =0 (4)

A tabela simplex inicial (tabela simplex 1) é compilada com base nas equações (2) e (4). Se as variáveis ​​adicionais x n+j forem precedidas pelo sinal “+”, como em (2), então todos os coeficientes antes das variáveis ​​xi e o termo livre b j são inseridos na tabela simplex sem alteração. Os coeficientes da função objetivo durante sua maximização são inseridos na linha inferior da tabela simplex com sinais opostos. Membros livres na tabela simplex determinam a solução do problema.

O algoritmo para resolver o problema é o seguinte:

1º passo. Os elementos da coluna de membros livres são pesquisados. Se todos forem positivos, então foi encontrada uma solução básica aceitável e deve-se prosseguir para o passo 5 do algoritmo, que corresponde a encontrar a solução ótima. Se houver termos livres negativos no tableau simplex inicial, a solução não é válida e você deve ir para a etapa 2.

2º passo. Para encontrar uma solução viável, é realizado, enquanto é necessário decidir quais das variáveis ​​não básicas incluir na base e qual variável retirar da base.

Tabela 1.

xn

variáveis ​​de base	Membros livres em restrições	Variáveis ​​não básicas
		x 1	x2	...	xl	...
xn+1	b 1	um 11	um 12	...	um 1l	...	um 1n
xn+2	b 2	um 21	um 22	...	um 2l	...	um 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+r	b2	um r1	um r2	...	um rl	...	um rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+m	bm	um m1	um m2	...	ml	...	amn
F(x)max	F0	-c 1	-c 2	...	-c 1	...	-c n

Para fazer isso, escolha qualquer um dos elementos negativos da coluna de membros livres (seja b 2 inicial ou permitido. Se não houver elementos negativos na linha com um membro livre negativo, o sistema de restrições é inconsistente e o problema não tem solução.

Ao mesmo tempo, a variável que é a primeira a mudar de sinal com o aumento do NP x l selecionado é excluída do PN. Este será x n+r , cujo índice r é determinado a partir da condição

Essa. a variável que corresponde à menor razão do termo livre para o elemento da coluna principal selecionada. Essa relação é chamada relação simples. Apenas relações simplex positivas devem ser consideradas.

A string correspondente à variável x n+r é chamada liderar ou permitir. O elemento da tabela simplex a rl , que está na interseção da linha inicial e da coluna inicial, é chamado de elemento inicial ou de resolução. Encontrar o elemento principal termina o trabalho com cada próximo tableau simplex.

3º passo. Uma nova tabela simplex é calculada, cujos elementos são recalculados a partir dos elementos da tabela simplex da etapa anterior e marcados com um primo, ou seja, b"j, a"ji, c"i, F"0. Os elementos são recalculados de acordo com as seguintes fórmulas:

Primeiro, a linha e a coluna que lideravam a tabela simplex anterior serão preenchidas na nova tabela simplex. A expressão (5) significa que o elemento a "rl no lugar do elemento inicial é igual ao recíproco do elemento da tabela simplex anterior. Os elementos da linha a ri são divididos pelo elemento inicial, e os elementos do coluna a jl também são divididas pelo elemento principal, mas são tomadas com o sinal oposto. Os elementos b" rec" l são calculados de acordo com o mesmo princípio.

O resto das fórmulas podem ser facilmente escritas usando .

O retângulo é construído de acordo com a antiga tabela simplex de forma que uma de suas diagonais seja formada pelos elementos recalculados (a ji) e principais (a rl) (Fig. 1). A segunda diagonal é determinada exclusivamente. Para encontrar um novo elemento a "ji, o produto dos elementos da diagonal oposta, dividido pelo elemento principal, é subtraído do elemento a ji (isso é indicado pelo sinal" - "na célula). Da mesma forma, os elementos b" j, (j≠r) ec"i são recalculados, (i≠l).

4º passo. A análise de uma nova tabela simplex começa a partir do 1º passo do algoritmo. A ação continua até que uma solução básica viável seja encontrada, ou seja, todos os elementos da coluna de membros livres devem ser positivos.

5º passo. Acreditamos que foi encontrada uma solução básica aceitável. Observamos os coeficientes da linha da função objetivo F(x) . Um sinal de otimalidade de uma tabela simplex é a não negatividade dos coeficientes para variáveis ​​não básicas na linha F.

Arroz. 1. Regra do retângulo

Se entre os coeficientes da linha F houver negativos (com exceção do termo livre), você precisará ir para outra solução básica. Ao maximizar a função objetivo, a base inclui a das variáveis ​​não básicas (por exemplo, x l), cuja coluna corresponde ao valor absoluto máximo do coeficiente negativo c l na linha inferior da tabela simplex. Isso permite selecionar a variável cujo aumento leva a uma melhoria na função meta. A coluna correspondente à variável x l é chamada de coluna principal. Ao mesmo tempo, essa variável x n + r é excluída da base, cujo índice r é determinado pela razão simplex mínima:

A linha correspondente a x n+r é chamada de linha principal, e o elemento da tabela simplex a rl , que está na interseção da linha principal e da coluna principal, é chamado elemento principal.

6º passo. de acordo com as regras estabelecidas na 3ª etapa. O procedimento continua até que uma solução ótima seja encontrada ou se conclua que ela não existe.

Se no processo de otimização da solução na coluna principal todos os elementos forem não positivos, a linha principal não poderá ser selecionada. Neste caso, a função no domínio das soluções admissíveis do problema não é limitada por cima e F max ->&∞.

Se na próxima etapa da busca por um extremo uma das variáveis ​​básicas se tornar igual a zero, então a solução básica correspondente é chamada degenerada. Nesse caso, ocorre o chamado looping, caracterizado pelo fato de que a mesma combinação de BP começa a se repetir com certa frequência (o valor da função F é preservado neste caso) e é impossível mudar para uma nova solução básica aceitável. O loop é uma das principais desvantagens do método simplex, mas é relativamente raro. Na prática, nesses casos, geralmente se recusa a inserir na base a variável cuja coluna corresponde ao valor absoluto máximo do coeficiente negativo na função objetivo, e é feita uma escolha aleatória de uma nova solução básica.

Exemplo 1. Resolver um problema

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Método Simplex e dar uma interpretação geométrica do processo de solução.

A interpretação gráfica da solução do problema é mostrada na fig. 2. O valor máximo da função objetivo é alcançado no topo do ODZP com coordenadas . Vamos resolver o problema usando tabelas simplex. Multiplicamos a segunda restrição por (-1) e introduzimos variáveis ​​adicionais para trazer as desigualdades para a forma de igualdades, então

As variáveis ​​iniciais x 1 e x 2 são consideradas não básicas, e as adicionais x 3 , x 4 e x 5 são consideradas básicas e compilamos uma tabela simplex (tabela simplex 2). A solução correspondente à tabela simplex. 2, não é válido; o elemento principal é delineado e selecionado de acordo com a etapa 2 do algoritmo acima. A próxima guia simplex. 3 define uma solução básica admissível; 2 O elemento principal é delineado e selecionado de acordo com o 5º passo do algoritmo para resolução do problema. Aba. 4 corresponde à solução ótima do problema, portanto: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x4 = 8; Fmáx = 20.

Arroz. 2. Solução gráfica do problema