Calculadora online do método simplex com solução. Método simplex para resolver zlp. Definindo uma coluna de ativação

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.

variáveis de base	Membros livres em restrições	Variáveis não básicas
variáveis de base	Membros livres em restrições	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	...	um 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

Breve teoria

A solução do problema

Construção do modelo

Vamos denotar o volume de negócios do 1º, 2º e terceiro tipos de mercadorias, respectivamente.

Então a função objetivo expressando o lucro recebido:

Restrições de recursos materiais e monetários:

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

Obtemos o seguinte problema de programação linear:

Preenchemos a tabela simplex da 0ª iteração.

Simplex
relações

520

65/2

140

810

-8

-6

-4

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

A transição para a próxima iteração é realizada da seguinte forma:

A coluna principal corresponde a .

A linha chave é determinada pelas proporções mínimas de membros livres e membros da coluna principal (proporções simplex):

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

Agora começamos a compilar a 1ª iteração. Em vez de um vetor unitário, introduzimos um vetor .

Na nova tabela, escrevemos 1 no lugar do elemento de permissão, todos os outros elementos da coluna chave são zeros. Os elementos de string de chave são divididos pelo elemento permissivo. Todos os outros elementos da tabela são calculados de acordo com a regra do retângulo.

Obtemos a tabela da 1ª iteração:

Simplex
relações

200

31/7

-16/7

1400/31

2/7

1/7

630

-7

-11/7

-9/7

160

-12/7

8/7

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

Encontramos a linha chave, para isso definimos:

Na interseção da coluna-chave e da linha-chave, encontramos o elemento de habilitação, ou seja, 31/7.

Deduzimos o vetor da base e inserimos o vetor .

Obtemos a tabela da 2ª iteração:

Simplex
relações

1400/31

14/31

7/31

-16/31

220/31

27/31

-2/31

9/31

21730/31

-195/31

11/31

-65/31

7360/31

86/31

12/31

8/31

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

Assim, é necessário vender 7,1 mil rublos. mercadorias do 1º tipo e 45,2 mil rublos. mercadorias do 3º tipo. Bens do 2º tipo não são lucrativos para vender. Nesse caso, o lucro será máximo e será de 237,4 mil rublos. Ao implementar o plano ótimo, o recurso restante do 3º tipo será de 701 unidades.

Se você não precisa de ajuda agora, mas pode precisar no futuro, para não perder o contato,

Este método é um método de enumeração proposital de soluções de referência de um problema de programação linear. Ele permite um número finito de etapas para encontrar a solução ótima ou estabelecer que não há solução ótima.

O conteúdo principal do método simplex é o seguinte:

Especifique um método para encontrar a solução de referência ideal
Especifique 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 forma de melhorar a solução de referência
Defina os critérios que permitem interromper oportunamente a enumeração de soluções de suporte na solução ideal ou seguir a conclusão de que não há solução ideal.

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

Para resolver o problema pelo método simplex, você deve fazer o seguinte:

Traga o problema para a forma canônica
Encontre uma solução de referência inicial com uma "base unitária" (se não houver solução de referência, o problema não tem solução devido à incompatibilidade do sistema de restrições)
Calcular estimativas de expansões vetoriais em termos da base da solução de referência e preencher a tabela do método simplex
Se o critério para a unicidade da solução ótima for satisfeito, então a solução do problema termina
Se a condição para a existência de um conjunto de soluções ótimas for satisfeita, então, por enumeração simples, todas as soluções ótimas são encontradas

Um exemplo de resolução do problema pelo método simplex

Exemplo 26.1

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 o coeficiente +1 no lado esquerdo da primeira restrição de desigualdade. A variável x 6 é incluída na função objetivo com um coeficiente zero (ou seja, não é incluída).

Nós temos:

Encontramos a solução de referência inicial. Para fazer isso, igualamos as 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).

Calcular estimativas de decomposição vetorial condições com base na solução de referência de acordo com a fórmula:

Δ k \u003d C b X k - c k

C b = (с 1 , с 2 , ... , с m) é o vetor de coeficientes da função objetivo com variáveis básicas
X k = (x 1k , x 2k , ... , x mk) é o vetor de expansão do vetor correspondente A k em termos da base da solução de referência
C k - 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, os coeficientes de expansão e as estimativas de expansão dos vetores de condição em termos da base da solução de referência são escritos em tabela simplex:

Acima da tabela, para facilitar o cálculo das estimativas, estão escritos os coeficientes da função objetivo. A primeira coluna "B" contém os vetores incluídos na base da solução de referência. A ordem de escrita desses vetores corresponde ao número de incógnitas permitidas nas equações de restrição. Na segunda coluna da tabela "Com b" os coeficientes da função objetivo são escritos com as variáveis básicas 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" os valores da função objetivo são escritos na solução de referência Z(X 1).

A solução de referência 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 de melhoria da solução de referência, se no problema máximo pelo menos um vetor tiver uma estimativa negativa, então uma nova solução de referência pode ser encontrada na qual o valor da função objetivo será maior.

Vamos determinar qual dos dois vetores levará a um incremento maior da 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 quando o primeiro vetor ΔZ 1 = - 6 * (- 2) = 12 é introduzido na base e o terceiro vetor ΔZ 3 = - 3 * (- 9) = 27.

Portanto, para uma aproximação mais rápida da solução ótima, é necessário introduzir o vetor A3 na base da solução de referência ao invés do primeiro vetor da base A6, pois o mínimo do parâmetro θ 03 é alcançado na primeira linha (l = 1).

Realizamos a transformada de Jordan com o elemento X13 = 2, obtemos a segunda solução de referência X2 = (0.0.3.21.42.0) com a 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. Portanto, derivamos o segundo vetor 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 que não estão incluídos na base, as estimativas são positivas

Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 7/2.

Responda: max 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 ótima diante de severas restrições relacionadas aos recursos utilizados na produção (ativo imobilizado, materiais, recursos trabalhistas). A aplicação deste método na análise econômica permite solucionar problemas relacionados principalmente ao planejamento das atividades da organização. Este método ajuda a determinar os valores ideais de saída, bem como as direções para o uso mais eficiente dos recursos de produção disponíveis para a organização.

Utilizando este método, é realizada a solução dos chamados problemas extremos, que consiste em encontrar os valores extremos, ou seja, o máximo e o mínimo das funções das 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, estritamente funcional. O método de programação linear é utilizado para analisar variáveis na presença de certos fatores limitantes.

A solução do chamado problema de transporte usando o método de programação linear é bastante comum. 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, a duração do seu trabalho, 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 em tal distribuição do tempo de funcionamento do pessoal desta organização, que seria o mais aceitável tanto para os membros deste pessoal como para os clientes da organização.

O objetivo é maximizar o número de clientes atendidos, limitando o número de funcionários disponíveis e as horas 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 esses fenômenos econômicos, cuja relação não é linear. Para tanto, métodos de programação não linear, dinâmica e convexa podem ser utilizados.

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

A programação não linear é usada na análise econômica, em particular, ao estabelecer a relação entre os indicadores que expressam a eficácia das atividades da organização e o volume dessa atividade, a estrutura de 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 camada dessa árvore serve como um estágio para determinar as consequências da decisão anterior e para eliminar variantes ineficazes dessa decisão. Assim, a programação dinâmica tem um caráter multi-passo, multi-estágio. Este tipo de programação é utilizado na análise econômica para encontrar as melhores opções para o desenvolvimento da organização agora e no futuro.

A programação convexa é um tipo de programação não linear. Esse tipo de programação expressa a natureza não linear da relação entre os resultados das atividades da organização e os custos por ela incorridos. A programação convexa (de outra forma côncava) analisa funções objetivas convexas e sistemas de restrições convexas (pontos de características). A programação convexa é utilizada na análise da atividade econômica para minimizar custos, e a programação côncava é utilizada para maximizar os rendimentos nas condições de restrições existentes à ação de fatores que afetam os indicadores analisados de forma inversa. Consequentemente, sob os tipos de programação considerados, as funções objetivo convexas são minimizadas e as côncavas são maximizadas.

Encontrar o maior valor de uma função

x 1 ≥ 0 x 2 ≥ 0

1. Os membros livres do sistema devem ser não negativos.

Esta condição foi cumprida.

2. Cada restrição do sistema deve ser uma equação.

x 1 + x 1 x 1 x2

2	x2	≤	4
-		x2	≥	1
+		≤	8

x 1 + S1 x 1 x 1 x2 S3

2	x2	+			=	4
-		x2	-	S2			=	1
+				+	=	8

S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0. As variáveis introduzidas S 1 , S 2 , S 3 são chamadas de variáveis de equilíbrio.

3. Encontrar a base inicial e o valor da função F, que corresponde à base inicial encontrada.

O que é uma base?
Uma variável é chamada básica para uma dada equação se ela entra na equação dada com fator um e não está incluído nas demais equações do sistema (desde que haja um número não negativo no lado direito da equação).
Se toda equação tem uma variável de base, diz-se que o sistema tem uma base.
Variáveis que não são básicas são chamadas de variáveis livres.

Qual é a ideia por trás do método simplex?
Cada base corresponde a um único valor da função. Um deles é o maior valor da função F.
Vamos passar de uma base para outra.
A próxima base será escolhida de forma a obter o valor da função F não menor que o existente.
Obviamente, o número de bases possíveis para qualquer problema não é muito grande.
Portanto, mais cedo ou mais tarde, a resposta será recebida.

Como é feita a transição de uma base para outra?
É mais conveniente registrar a solução na forma de tabelas. Cada linha da tabela é equivalente à equação do sistema. A linha destacada consiste nos coeficientes da função (veja a tabela abaixo). Isso permite que você não reescreva variáveis todas as vezes, o que economiza muito tempo.
Na linha selecionada, selecione o maior coeficiente positivo (você pode escolher qualquer um positivo).
Isso é necessário para obter o valor da função F não menor que o existente.
Coluna selecionada.
Para coeficientes positivos da coluna selecionada, calculamos a razão Θ e escolhemos o menor valor.
Isso é necessário para que após a transformação a coluna de termos livres permaneça não negativa.
Linha selecionada.
O elemento que será o elemento base está definido. A seguir, contamos.

Nosso sistema tem uma base?

x 1 + x 1 x 1 x2

Não há base, ou seja, não podemos iniciar uma solução.
Terá que encontrá-lo. Para fazer isso, resolvemos um problema auxiliar.
Vamos adicionar uma variável artificial à equação onde não há variável base.

x 1 + x 1 x 1 x2

R 1 ≥ 0. A variável introduzida R 1 é chamada de variável artificial.

Introduzimos a função W em consideração e procuramos seu menor valor.

O algoritmo para encontrar o menor valor da função W tem apenas uma diferença do algoritmo discutido acima.

x 1	x2	S1	S2	S3	R1	St. membro	Θ
1	2	1	0	0	0	4	4: 1 = 4
1	-1	0	-1	0	1	1	1: 1 = 1
1	1	0	0	1	0	8	8: 1 = 8
-1	1	0	1	0	0	W - 1
0	3	1	1	0	-1	3
1	-1	0	-1	0	1	1
0	2	0	1	1	-1	7
0	0	0	0	0	1	W - 0

Igualamos as variáveis livres a zero. Encontre verbalmente os valores das variáveis básicas. (ver tabela)
A função W é expressa em termos de variáveis livres. Portanto, o valor da função W, para uma dada base, pode ser encontrado instantaneamente. (ver linha destacada da tabela)

x 2 = 0 S 2 = 0 R 1 = 0
x 1 = 1 S 1 = 3 S 3 = 7

=> W - 0 = 0 => W = 0

Entre os coeficientes da linha selecionada, não há negativos. Portanto, o menor valor da função W é encontrado.
Uma base é obtida sem usar uma variável artificial. Que é o que era necessário.
A coluna correspondente à variável artificial pode ser riscada.
Como resultado, nosso sistema fica assim:

S2 S2

x 1

(

)

-1

Considerar método simplex para resolver problemas de programação linear (PL). Baseia-se na transição de um plano de referência para outro, no qual o valor da função objetivo aumenta.

O algoritmo do método simplex é o seguinte:

Traduzimos o problema original para uma forma canônica introduzindo variáveis adicionais. Para uma desigualdade da forma ≤, variáveis adicionais são introduzidas com um sinal (+), mas se for da forma ≥, então com um sinal (-). Variáveis adicionais são introduzidas na função objetivo com os sinais correspondentes com um coeficiente igual a 0 , Porque a função objetivo não deve mudar seu significado econômico.
Os vetores são emitidos Pi dos coeficientes das variáveis e da coluna de termos livres. Esta ação determina o número de vetores unitários. A regra é que deve haver tantos vetores unitários quantos forem as desigualdades no sistema de restrições.
Depois disso, os dados iniciais são inseridos na tabela simplex. Os vetores unitários são introduzidos na base e, excluindo-os da base, a solução ótima é encontrada. Os coeficientes da função objetivo são escritos com o sinal oposto.
O critério de otimalidade para o problema de PL é que a solução é ótima se em f– linha todos os coeficientes são positivos. Regra de localização da coluna de permissão - Visualizada fé uma string e entre seus elementos negativos é escolhido o menor. Vetor Pi sua contenção torna-se permissiva. A regra para escolher um elemento de resolução - as razões dos elementos positivos da coluna de resolução para os elementos do vetor são compiladas P 0 e o número que fornece a menor razão torna-se o elemento de resolução, em relação ao qual a tabela simplex será recalculada. A string que contém esse elemento é chamada de string de ativação. Se não houver elementos positivos na coluna de resolução, o problema não tem solução. Depois de determinar o elemento de resolução, eles procedem ao recálculo de uma nova tabela simplex.
Regras para preencher uma nova tabela simplex. No lugar do elemento de resolução, um é colocado e os outros elementos são considerados iguais 0 . O vetor de resolução é adicionado à base, da qual o vetor zero correspondente é excluído, e os vetores de base restantes são escritos inalterados. Os elementos da linha permissiva são divididos pelo elemento permissivo e os demais elementos são recalculados de acordo com a regra dos retângulos.
Isso é feito até o f– todos os elementos da string não se tornarão positivos.

Considere a solução do problema usando o algoritmo acima.
Dado:

Trazemos o problema para a forma canônica:

Compomos vetores:

Preencha a tabela simplex:

:
Recalcular o primeiro elemento do vetor P 0, para o qual fazemos um retângulo de números: e obtemos: .

Realizamos cálculos semelhantes para todos os outros elementos da tabela simplex:

No plano recebido f– a string contém um elemento negativo – (-5/3), vetores P1. Ele contém em sua coluna o único elemento positivo, que será o elemento resolvente. Vamos recalcular a tabela em relação a este elemento:

A ausência de elementos negativos na f- string significa encontrada plano ideal:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

Ashmanov S. A. Programação linear, M: Nauka, 1998,
Wentzel E.S. Pesquisa Operacional, M: Rádio Soviética, 2001,
Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Programação matemática, M: Escola superior, 1986

Solução de programação linear personalizada

Você pode encomendar quaisquer tarefas nesta disciplina em nosso site. Você pode anexar arquivos e especificar prazos em