Conjuntos convexos e suas propriedades. Para estudar as propriedades do LPP, é necessário dar uma definição rigorosa de um conjunto convexo. Anteriormente, um conjunto convexo era definido como um conjunto que, junto com quaisquer dois de seus pontos, contém um segmento conectando-os.

Uma generalização do conceito de um segmento para vários pontos é sua combinação linear convexa.

Ponto X é chamado combinação linear convexa pontos, se as condições forem atendidas

O conjunto de pontos é convexo, se ele, junto com qualquer um de seus dois pontos, contém sua combinação linear convexa arbitrária.

O seguinte teorema sobre a representação de um poliedro convexo pode ser provado.

Teorema 1.1. Um n-politopo convexo é uma combinação linear convexa de seus pontos de canto.

Do Teorema 1.1 segue-se que um poliedro convexo é gerado por seus pontos de canto ou vértices: um segmento por dois pontos, um triângulo por três, um tetraedro por quatro pontos, etc. Ao mesmo tempo, uma região poliédrica convexa, sendo um conjunto ilimitado, não é exclusivamente determinada por seus pontos de canto: qualquer ponto dela não pode ser representado como uma combinação linear convexa de pontos de canto.

Propriedades do problema de programação linear. Anteriormente, várias formas de um problema de programação linear foram consideradas e foi mostrado que qualquer problema de programação linear pode ser representado como um problema geral ou canônico.

Para substanciar as propriedades de um problema de programação linear e métodos para sua solução, é aconselhável considerar mais dois tipos de escrita do problema canônico.

Notação de matriz:

Aqui COM- matriz de linha, UMA- matriz do sistema, NS- matriz-coluna de variáveis, V- matriz-coluna de membros livres:

Notação vetorial:

onde vetores correspondem a colunas de coeficientes para incógnitas.

O seguinte teorema foi afirmado acima, mas não foi provado de forma geral.

Teorema 1.2. O conjunto de todas as soluções viáveis ​​para o sistema de restrições de um problema de programação linear é convexo.

Prova: Deixe ser - duas soluções admissíveis do LPP dadas em forma de matriz. Então e . Considere uma combinação linear convexa de soluções, ou seja,

e mostrar que também é uma solução admissível para o sistema (1.3). De fato

ou seja solução X satisfaz o sistema (1.3). Mas desde então NS> 0, ou seja, a solução satisfaz a condição de não negatividade.

Assim, ficou demonstrado que o conjunto de todas as soluções admissíveis do problema de programação linear é convexo, ou, mais precisamente, representa um poliedro convexo ou um domínio poliédrico convexo, que a seguir será denominado por um termo - poliedro de soluções.

A resposta à pergunta em que ponto do politopo de soluções é a solução ótima para um problema de programação linear é dada no seguinte teorema fundamental.

Teorema 1.3. Se o problema de programação linear tem uma solução ótima, a função linear assume seu valor máximo em um dos pontos de canto do politopo da solução. Se uma função linear assume seu valor máximo em mais de um ponto de canto, ela o leva em qualquer ponto que seja uma combinação linear convexa desses pontos.

Prova: Vamos assumir que o politopo da solução é limitado. Vamos denotar seus pontos de canto por , e a solução ideal é através X *... Então F (X *)³ F (X) para todos os pontos NS poliedro de soluções. Se X *É um ponto de canto, então a primeira parte do teorema é provada.

Vamos fingir que X * não é um ponto de vértice, então pelo Teorema 1.1 X * pode ser representado como uma combinação linear convexa de pontos de canto do poliedro de solução, ou seja,

Porque F (X)É uma função linear, obtemos

Nessa expansão, escolhemos o valor máximo entre os valores. Deixe que corresponda ao ponto de canto X k(£ 1 k£ R); vamos denotá-lo por M, Essa. . Substitua cada valor na expressão (1,5) por este valor máximo M. Então

Por suposição NS* É a solução ótima, portanto, por um lado, mas, por outro lado, está comprovado que
F (X *)£ M, portanto, onde X k- ponto de canto. Portanto, há um ponto crítico X k em que a função linear assume seu valor máximo.

Para provar a segunda parte do teorema, assuma que a função objetivo leva seu valor máximo em mais de um ponto de canto, por exemplo, nos pontos , Onde , então

Deixe ser NS- uma combinação linear convexa desses pontos de canto, ou seja,

Neste caso, dado que a função F (X)- linear, nós temos

Essa. Função linear F leva o valor máximo em um ponto arbitrário NS que é uma combinação linear convexa de pontos de canto.

Comente. O requisito de que o politopo de soluções seja limitado no teorema é essencial, uma vez que, no caso de um domínio poliédrico ilimitado, conforme observado no Teorema 1.1, nem todos os pontos de tal domínio podem ser representados por uma combinação linear convexa de seus pontos de canto .

O teorema provado é fundamental, pois indica uma forma fundamental de resolver problemas de programação linear. De fato, de acordo com este teorema, em vez de estudar um conjunto infinito de soluções viáveis ​​para encontrar a solução ótima desejada entre elas, é necessário investigar apenas um número finito de pontos de canto do poliedro de soluções.

O próximo teorema é dedicado ao método analítico para encontrar pontos de canto.

Teorema 1.4. Cada solução básica admissível de um problema de programação linear corresponde a um ponto de canto do poliedro de solução, e vice-versa, cada ponto de canto do poliedro de solução corresponde a uma solução básica admissível.

Prova: Seja uma solução básica admissível para o sistema de restrições LPP (1.4), em que o primeiro T o componente são as variáveis ​​principais e o resto n - t componente - variáveis ​​menores iguais a zero na solução básica (se este não for o caso, então as variáveis ​​correspondentes podem ser renumeradas). Vamos mostrar isso NS

Suponha o oposto, ou seja, o que NS não é um ponto angular. Então o ponto NS pode ser representado por um ponto interno de um segmento conectando dois diferentes que não coincidem com X, pontos

em outras palavras, uma combinação linear convexa de pontos poliedro de soluções, ou seja,

onde (presumimos que, caso contrário, o ponto NS coincide com o ponto NS 1 ou NS 2).

Escrevemos a igualdade vetorial (1.6) na forma de coordenadas:

Porque todas as variáveis ​​e coeficientes são não negativos, então a partir do último p-t igualdades segue-se que, ou seja, nas decisões NS 1 , NS 2 e NS sistema de equações (1.4) os valores n - t os componentes são iguais, neste caso, a zero. Esses componentes podem ser considerados os valores de variáveis ​​secundárias. Mas os valores das variáveis ​​menores determinam inequivocamente os valores das maiores, portanto,

Então todos NS componente em soluções NS 1 , NS 2 e NS coincidem e, portanto, os pontos NS 1 e NS 2 mesclar, o que contradiz a suposição. Portanto, XÉ o ponto de canto do poliedro da solução.

Vamos provar a afirmação inversa. Deixe ser o ponto de canto do politopo de soluções e seu primeiro T as coordenadas são positivas. Vamos mostrar isso NS- solução básica admissível. não é um ponto angular, o que contradiz a condição. Portanto, nossa suposição está incorreta, ou seja, vetores são linearmente independentes e NSÉ uma solução básica admissível para o problema (1.4).

Um importante corolário segue diretamente dos Teoremas 1.3 e 1.4: se um problema de programação linear tem uma solução ótima, então ele coincide com pelo menos uma de suas soluções básicas admissíveis.

Então, o ótimo de uma função linear de um problema de programação linear deve ser buscado entre um número finito de suas soluções básicas admissíveis.

A otimização de modelos lineares no MS Excel é realizada método simplex- enumeração proposital de soluções de suporte do problema de programação linear. O algoritmo do método simplex é reduzido à construção de um poliedro convexo em um espaço multidimensional, e então à iteração sobre seus vértices para encontrar o valor extremo função objetiva.

Remédios eficazes programação linear fundamentam a programação inteira e não linear para problemas de otimização mais complexos. Esses métodos, no entanto, levam mais tempo de computação.

Em palestras subsequentes, exemplos de resolução de problemas de otimização típicos e tomada de decisões de gerenciamento usando o suplemento do MS Excel "Busca por uma solução" serão analisados ​​em detalhes. As tarefas que são mais bem realizadas por esta ferramenta têm três propriedades principais:

• existe um único objetivo, funcionalmente relacionado a outros parâmetros do sistema, que precisa ser otimizado (encontrar seu máximo, mínimo ou um determinado valor numérico);
• existem restrições, geralmente expressas na forma de desigualdades (por exemplo, o volume de matérias-primas utilizadas não pode exceder o estoque de matérias-primas no armazém, ou o tempo de operação da máquina por dia não deve ser superior a 24 horas menos o tempo de atendimento);
• há um conjunto de valores de variáveis ​​de entrada que afetam os valores otimizados e as restrições.

Os parâmetros da tarefa são limitados pelos seguintes valores limite:

• número de incógnitas - 200;
• o número de restrições de fórmula em incógnitas - 100;
• o número de condições limitantes para incógnitas é 400.

O algoritmo para encontrar soluções ideais inclui vários estágios:

• trabalho preparatório;
• depurar a solução;
• análise da solução.

A seqüência do trabalho preparatório necessário executado na solução dos problemas de modelagem econômica e matemática usando o MS Excel é mostrada no diagrama de blocos da Figura 1.6.

Arroz. 1.6.

Dos cinco pontos do plano de trabalho preparatório, apenas o quinto ponto é formalizado. O resto do trabalho requer criatividade - e pode ser feito de maneiras diferentes por pessoas diferentes. Vamos explicar brevemente a essência da formulação dos pontos do plano.

Ao definir o problema, os coeficientes alvo e os coeficientes normalizados são conhecidos. No exemplo anterior, os coeficientes que formam a função objetivo eram os valores do lucro normalizado por prateleira do tipo ( ) e uma prateleira do tipo ( ) Os coeficientes normalizados foram as taxas de consumo de material e tempo de máquina por prateleira de cada tipo. A matriz era parecida com esta:

Além disso, os valores dos recursos são sempre conhecidos. No exemplo anterior, era um fornecimento semanal de pranchas e a capacidade de usar o tempo da máquina: , ... Freqüentemente, em tarefas, os valores das variáveis ​​precisam ser limitados. Portanto, é necessário determinar os limites inferior e superior da área de suas alterações.

Assim, na caixa de diálogo do programa de otimização "Buscar uma solução", devemos especificar o seguinte algoritmo de destino:

A função objetivo é igual ao produto do vetor dos valores desejados das variáveis ​​pelo vetor dos coeficientes objetivos

Os coeficientes normalizados para o vetor dos valores procurados das variáveis ​​não devem exceder o valor do vetor de recursos dado

Os valores da variável devem estar dentro dos limites especificados o número de elementos iniciais do sistema

O número de elementos iniciais do sistema

O número de tipos de recursos especificados

Depurar a solução é necessário no caso em que o programa emite uma mensagem sobre resultados negativos (Figura 1.7):

Arroz. 1,7.

• se uma solução viável não for obtida, corrija o modelo dos dados iniciais;
• se não recebido solução ótima e, em seguida, introduza restrições adicionais.

Os problemas do programa solução ótima apenas para modelar um problema real, não uma solução para o problema em si. Ao construir o modelo, várias suposições simplificadoras da situação real foram feitas. Isso permitiu formalizar o processo, refletindo aproximadamente as reais relações quantitativas entre os parâmetros do sistema e a meta. E se os parâmetros reais forem diferentes daqueles incluídos no modelo, como a decisão mudará? Para saber, antes de tomar uma decisão gerencial, é analisada uma decisão modelo.

Análise solução ótima, embutido no programa, é o estágio final da modelagem matemática dos processos econômicos. Permite uma verificação mais aprofundada da adequação do modelo ao processo, bem como da confiabilidade da solução ótima. É orientado por dados solução ótima e os relatórios que são emitidos na seção “Busca de uma solução”. Mas não exclui ou substitui a análise tradicional do plano do ponto de vista econômico antes de tomar uma decisão gerencial.

A análise econômica tem os seguintes objetivos:

• determinação das possíveis consequências no sistema como um todo e seus elementos ao alterar o parâmetro do modelo;
• avaliação da estabilidade do plano ótimo a mudanças em parâmetros individuais do problema: se não for resistente a mudanças na maioria dos parâmetros, a garantia de sua implementação e realização das reduções ótimas calculadas;
• realizar cálculos de variantes e obter novas variantes do plano sem resolver o problema da base original por meio de ajustes.

Os métodos de análise possíveis são mostrados no diagrama da Figura 1.8.

Depois de obter a solução ótima, ela é analisada de acordo com os relatórios recebidos. Análise de estabilidade- estudo da influência das mudanças nos parâmetros individuais do modelo sobre os indicadores da solução ótima. Análise de limite- análise de mudanças aceitáveis ​​no plano ótimo, no qual o plano permanece ótimo.

Dada a responsabilidade de tornar econômico Decisão de gestão, o líder deve certificar-se de que o plano ótimo recebido é o único correto. Para fazer isso, é necessário obter respostas às seguintes questões com base no modelo:

• "e se…"
• "o que é necessário para ..."

A análise para responder à primeira pergunta é chamada análise de variantes; análise para responder à segunda pergunta é chamada soluções personalizadas.

A análise de variantes é dos seguintes tipos:

• Paramétrico- análise, que consiste em resolver um problema para diferentes valores de um determinado parâmetro.
• Análise estrutural- quando a solução para o problema de otimização é buscada com uma estrutura de restrições diferente.
• Análise multicritério- Esta é uma solução para o problema para diferentes funções de destino.
• Análise com dados de entrada condicionais- quando os dados iniciais usados ​​na resolução do problema dependem da observância de condições adicionais.

Após a análise, os resultados devem ser apresentados em forma gráfica e deve ser elaborado relatório com recomendações para a tomada de decisão, tendo em conta a situação económica específica.

Definição... Qualquer solução para o sistema de restrições é chamada de solução admissível do LPP.
Definição... Uma solução viável em que a função objetivo atinge seu valor máximo ou mínimo é chamada de solução ótima.

Em virtude dessas definições, o problema LP pode ser formulado da seguinte forma: entre todos os pontos de uma região convexa que é uma solução para o sistema de restrições, escolha aquele cujas coordenadas minimizam (maximizam) a função linear F = com 1 x + com 2 y.
Observe que as variáveis x, y no LPP tomam, como regra, valores não negativos ( x≥ 0, y≥ 0), então a região está localizada no quarto I do plano de coordenadas.

Considere uma função linear F = com 1 x + com 2 y e fixar alguns de seus valores F... Deixe, por exemplo, F= 0, ou seja com 1 x + com 2 y= 0. O gráfico desta equação será uma linha reta passando pela origem das coordenadas (0; 0) (Fig.).
Desenhando
Ao alterar este valor fixo F = d, em linha reta com 1 x+ com 2 y = d irá se mover em paralelo e "traçar" todo o plano. Deixe ser D- polígono - a área para resolver o sistema de restrições. Quando muda d em linha reta com 1 x + com 2 y = d, em algum valor d = d 1 alcançará o polígono D, vamos chamar este ponto UMA"Ponto de entrada", e então, passando o polígono, em algum valor d = d 2 teremos o último ponto comum com ele V, vamos ligar V"Ponto de saída".
Obviamente, a função objetivo de seu menor e maior valor F=com 1 x + com 2 y vai chegar nos pontos de entrada UMA e "sair" V.
Levando em consideração que a função objetivo assume o valor ótimo no conjunto de soluções viáveis ​​nos vértices da região D, o seguinte plano para resolver o LPP pode ser proposto:

1. construir a área de soluções do sistema de restrições;
2. construir uma linha reta correspondente à função objetivo, e por transferência paralela desta linha reta encontrar o ponto de "entrada" ou "saída" (dependendo da necessidade de minimizar ou maximizar a função objetivo);
3. determine as coordenadas deste ponto, calcule o valor da função objetivo neles.

Observe que o vetor ( com 1 , com 2), perpendicular à linha reta, mostra a direção de crescimento da função objetivo.

Ao resolver o LPP graficamente, existem dois casos possíveis que requerem uma discussão especial.

Caso 1
Figura 6
Ao mover-se em linha reta com 1 x + com 2 y= d A "entrada" ou "saída" (como na imagem) ocorrerá na lateral do polígono. Isso acontecerá se o polígono tiver lados paralelos a uma linha reta. com 1 NS+ com 2 no = d .
Neste caso, os pontos de "saída" ("entrada") são inúmeros, nomeadamente, qualquer ponto do segmento AB... Isso significa que a função objetivo assume o valor máximo (mínimo) não em um ponto, mas em todos os pontos situados no lado correspondente do polígono D.

Caso 2
Considere o caso em que a faixa de valores admissíveis é ilimitada.
No caso de uma área ilimitada, a função objetivo pode ser especificada de forma que a linha reta correspondente não tenha um ponto de “saída” (ou “entrada”). Então, o valor máximo da função (mínimo) nunca é alcançado - eles dizem que a função não é limitada.
Desenhando
É necessário encontrar o valor máximo da função objetivo F = 4x + 6y→ max, com um sistema de restrições
Vamos construir a região de soluções viáveis, ou seja, vamos resolver graficamente o sistema de desigualdades. Para fazer isso, construímos cada linha e definimos os semiplanos dados pelas desigualdades.
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x= 12 - paralelo ao eixo OY ;
y= 9 - paralelo ao eixo BOI ;
x= 0 - eixo OY ;
y = 0 - eixo BOI;
x OY;
y≥ 0 - meio plano acima do eixo BOI;
y≤ 9 - meio plano abaixo y = 9;
x ≤ 12 - meio plano para a esquerda x = 12;
0,5x + yx + y = 12;
x + y x + y = 18.
Desenhando
A interseção de todos esses semiplanos é obviamente o pentágono OAVSD, com vértices em pontos O(0; 0), UMA(0; 9), V(6; 9), COM(12; 6), D(12; 0). Este pentágono forma a região de soluções viáveis ​​para o problema.

F = 4x + 6y→ máx.

x	3	0
y	–2	0

F = 0: 4x + 6y x+ 6y COM(12; 6). Está nela F = 4x + 6y
Portanto, para x = 12, y= 6 função F F= 4 ∙ 12 + 6 ∙ 6 = 84, igual a 84. O ponto com as coordenadas (12; 6) satisfaz todas as desigualdades do sistema de restrições, e o valor da função objetivo nele é ótimo F* = 84 (o valor ideal será denotado por "*").
O problema foi resolvido. Portanto, é necessário produzir 12 produtos do tipo I e 6 produtos do tipo II, enquanto o lucro será de 84 mil rublos.

O método gráfico é utilizado para resolver problemas que possuíam apenas duas variáveis ​​no sistema de restrições. Este método também pode ser aplicado a sistemas de desigualdades com três variáveis. Geometricamente, a situação será diferente, o papel das retas será desempenhado pelos planos no espaço tridimensional e a solução para a desigualdade em três variáveis ​​será um meio-espaço localizado em um dos lados do plano. O papel das regiões será desempenhado pelos poliedros, que são a intersecção de meios-espaços.

Exemplo No. 2. A mina desenvolve duas costuras. A saída do corte na primeira camada é a1%; no segundo - a2%. A produção máxima do longwall para a primeira camada é de B1 mil toneladas por ano, para a segunda camada - B2 mil toneladas por ano. De acordo com a tecnologia de trabalho, a produção da segunda camada não pode ultrapassar a produção da primeira camada. A produção da mina na mina não deve ultrapassar C1 mil toneladas por ano. A carga total nas duas camadas por ano deve ser de pelo menos C2 mil toneladas por ano. Crie um modelo matemático e construa um conjunto de valores de carga admissíveis para a primeira e segunda camadas por ano.

Exemplo No. 3. A loja vende 2 tipos de refrigerante: Cola e Limonada. A renda de uma lata de cola é de 5 centavos, enquanto a renda de uma lata de limonada é de 7 centavos. Em média, uma loja vende, no máximo, 500 latas das duas bebidas por dia. Apesar de a cola ser produzida por uma marca conhecida, os compradores preferem a limonada porque é muito mais barata. Estima-se que as vendas de coca-cola e limonada sejam de pelo menos 2: 1, e sabe-se que a loja vende pelo menos 100 latas de coca-cola por dia. Quantas latas de cada bebida a loja deve ter no início do dia para maximizar a receita?

Exemplo No. 4. Resolva o problema de programação linear de forma aproximadamente gráfica com o cálculo subsequente do valor exato e max (min) do valor da função objetivo.

Exemplo No. 5. Uma agência de viagens requer não mais do que ônibus de três toneladas e não mais do que ônibus de cinco toneladas. O preço de venda dos ônibus da primeira marca é de 20.000 dólares, a segunda marca é de 40.000 dólares. Uma agência de viagens não pode alocar mais do que $ 1 para a compra de ônibus. Quantos ônibus de cada marca devem ser adquiridos separadamente para que sua capacidade de carga total (total) seja máxima. Resolva o problema graficamente.

Exemplo No. 6. Usando o método gráfico, encontre o plano de produção ideal para a tarefa fornecida na tabela.

Exemplo No. 7. Resolva o problema de programação linear por um método gráfico, submetendo o sistema de restrições do problema às transformações de Jordan-Gauss. O sistema de restrições do problema é o seguinte:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Diretrizes... As transformações de Jordan-Gauss podem ser realizadas usando este serviço ou através do estudo de SLAEs.

Exemplo No. 8. A empresa produz dois tipos de produtos, A e B, para cuja produção são utilizados três tipos de matérias-primas. Para a fabricação de uma unidade do produto A, é necessário gastar matérias-primas de cada tipo a1, a2, a3 kg, respectivamente, e para uma unidade do produto B - b1, b2, b3 kg. A produção é fornecida com matérias-primas de cada tipo na quantidade de Р1, Р2, Р3 kg, respectivamente. O custo de uma unidade do produto A é C1 rublos, e a unidade do produto B é C2 rublos. É necessária a elaboração de um plano de produção dos produtos A e B, que garanta o custo máximo do produto acabado.

Exemplo No. 2. É necessário encontrar o valor máximo da função objetivo F = 4x + 6y→ max, com um sistema de restrições:

Vamos construir a região de soluções viáveis, ou seja, vamos resolver graficamente o sistema de desigualdades. Para fazer isso, selecione o número de restrições igual a 4 (Figura 1).
Imagem 1

Em seguida, preenchemos os coeficientes para as variáveis ​​e as próprias restrições (Figura 2).
Figura 2

Figura 3
x= 12 - paralelo ao eixo OY;
y= 9 - paralelo ao eixo BOI;
x> = 0 - eixo OY
y= 0 - eixo BOI;
x≥ 0 - meio plano à direita do eixo OY;
y≥0 - meio plano acima do eixo BOI;
y≤ 9 - meio plano abaixo y = 9;
x≤ 12 - meio plano para a esquerda x = 12;
0,5x + y≤ 12 - meio plano abaixo de uma linha reta 0,5 x + y = 12;
x + y≤ 18 - meio plano abaixo da linha reta x + y = 18.

A intersecção de todos esses semiplanos é o pentágono ABCDE, com vértices em pontos UMA(0; 0), B(0;9), C(6; 9), D(12;6), E(12; 0). Este pentágono forma a região de soluções viáveis ​​para o problema.

Considere a função objetivo do problema F = 4x + 6y→ máx.

x	3	0
y	–2	0

Construímos uma linha reta correspondente ao valor da função F = 0: 4x + 6y= 0. Vamos mover esta linha de maneira paralela. De toda a família de linhas, 4 x + 6y= const o último vértice através do qual passa a linha reta ao passar do limite do polígono será o vértice COM(12; 6). Está nela F = 4x + 6y atinge seu valor máximo.

Portanto, para x = 12, y= 6 função F atinge seu valor máximo F= 4 ∙ 12 + 6 ∙ 6 = 84, igual a 84. O ponto com as coordenadas (12; 6) satisfaz todas as desigualdades do sistema de restrições, e o valor da função objetivo nele é ótimo F* = 84.

Teste na disciplina "Pesquisa Operacional"

(as respostas corretas são as primeiras)

1. O termo "pesquisa operacional" apareceu ...

durante a Segunda Guerra Mundial

na década de 50 do século XX

nos anos 60 do século XX

na década de 70 do século XX

nos anos 90 do século XX

no início do século XXI

2. Meios de pesquisa operacional (escolha a opção mais adequada) ...

um conjunto de métodos científicos para resolver problemas de gestão eficaz de sistemas organizacionais

um conjunto de medidas tomadas para implementar certas operações

um conjunto de métodos para implementar o plano concebido

métodos científicos de alocação de recursos na organização da produção

3. Organize as etapas pelas quais qualquer pesquisa operacional normalmente passa:

Formulação do problema

construção de um modelo significativo (verbal) do objeto considerado (processo)

construindo um modelo matemático

resolução de problemas formulados com base no modelo matemático construído

verificação dos resultados obtidos quanto à adequação da natureza do sistema em estudo

implementação da solução obtida na prática

4. Na pesquisa operacional, uma operação é entendida ...

qualquer evento (sistema de ações), unido por um único conceito e visando atingir um objetivo

qualquer evento incontrolável

um conjunto de medidas técnicas para garantir a produção de produtos de consumo

5. A solução é chamada de ótima, ...

se é preferível por um motivo ou outro

se é racional

se for acordado com as autoridades

se aprovado pela assembleia geral

6. Programação matemática ...

está empenhada no estudo de problemas extremos e no desenvolvimento de métodos para a sua solução

é o processo de criação de programas de computador sob a orientação de matemáticos

resolve problemas matemáticos em um computador

7. A tarefa da programação linear é ...

encontrar o maior (menor) valor de uma função linear na presença de restrições lineares

criar um programa linear em uma linguagem de programação selecionada projetada para resolver o problema

descrição de um algoritmo linear para resolver um determinado problema

8. Em um problema de programação quadrática ...

a função objetivo é quadrática

a área de soluções admissíveis é um quadrado

restrições contêm funções quadráticas

9. Em problemas de programação inteira ...

incógnitas só podem aceitar valores inteiros

a função objetivo deve necessariamente ter um valor inteiro, e as incógnitas podem ser qualquer

a função de destino é uma constante numérica

10. Em tarefas de programação paramétrica ...

função objetivo e / ou sistema de restrição contém parâmetro (s)

a área de soluções admissíveis é um paralelogramo ou paralelepípedo

o número de variáveis ​​só pode ser par

11. Em problemas de programação dinâmica ...

o processo de encontrar uma solução é multiestágios

precisa racionalizar a produção de dinamite

você deseja otimizar o uso de alto-falantes

12. O seguinte problema de programação linear é apresentado:

F(NS 1, NS 2) = 5NS 1 + 6NS 2→ max

0.2NS 1 + 0.3NS 2 ≤ 1.8,

0.2NS 1 + 0.1NS 2 ≤ 1.2,

0.3NS 1 + 0.3NS 2 ≤ 2.4,

NS 1 ≥ 0, NS 2 ≥ 0.

Selecione uma tarefa que seja equivalente a esta tarefa.

F(NS 1, NS 2)= 5NS 1 + 6NS 2 → max,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 6NS 1 + 5NS 2 → min,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 50NS 1 + 60NS 2 → max,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 5NS 12 + 6NS 22 → max,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

3NS 1 + NS 2 ≤ 2.4,

NS 1 ≥ 0,

NS 2 ≥ 0.

13. A função objetivo de um problema de programação linear pode ser a função:

F=12x1+20x2-3 0x3→min

F= →min

F=→max

F=→máx.

14. O sistema de restrições do problema de programação linear pode ser o sistema:

15. O método simplex é:

método analítico para resolver o problema principal de programação linear

um método para encontrar a região de soluções viáveis ​​para um problema de programação linear;

um método gráfico para resolver o problema principal da programação linear;

um método para reduzir um problema geral de programação linear a uma forma canônica.

16. A tarefa da programação linear é:

encontrar o maior ou o menor valor de uma função linear na presença de restrições lineares

desenvolvimento de um algoritmo linear e sua implementação em um computador

desenhar e resolver um sistema de equações lineares

a busca por uma trajetória linear de desenvolvimento do processo descrito por um determinado sistema de restrições.

17. Domínio de soluções viáveis ​​do problema de programação linear não pode parece com isso:

18. A função alvo de um problema de programação linear pode ser a função:

F=12x1+20x2-3 0x3→min

F= →min

F=→max

F=→máx.

19. O sistema de restrições do problema de programação linear pode ser o sistema:

20. A região de soluções viáveis ​​do problema de programação linear é a seguinte:

F(NS 1, NS 2)= 3NS 1 + 5NS 2 é igual a ...

21. A região de soluções viáveis ​​do problema de programação linear tem a forma:

Então, o valor máximo da função F(NS 1, NS 2)= 5NS 1 + 3NS 2 é igual a ...

22. A região de soluções viáveis ​​do problema de programação linear tem a forma:

Então, o valor máximo da função F(NS 1, NS 2)= 2NS 1 - 2NS 2 é igual a ...

23. A região de soluções viáveis ​​do problema de programação linear tem a forma:

F(NS 1, NS 2)= 2NS 1 - 2NS 2 é igual a ...

24. A região de soluções viáveis ​​para o problema de programação não linear tem a forma:

Então, o valor máximo da função F(NS 1, NS 2)= NS 2 – NS 12 é igual a ...

25. Valor máximo da função objetivo F(NS 1, NS 2)= 5NS 1 + 2NS 2 com restrições
NS 1 + NS 2 ≤ 6,

NS 1 ≤ 4,

NS 1 ≥ 0, NS 2 ≥ 0, é igual a ...

26. Uma pequena empresa produz dois tipos de produtos. Para a fabricação de um produto do tipo A, são consumidos 2 kg de matéria-prima, para a fabricação de um produto do tipo B - 1 kg. São 60 kg de matéria-prima no total. É necessário traçar um plano de produção que garanta o recebimento da maior receita, se o custo de venda de um produto do tipo A é de 3 unidades, o tipo B é de 1 unidade. Ou seja, os produtos do tipo A não precisam ser feitos mais do que 25 e do tipo B - não mais do que 30.

Esta tarefa é ...

problema de programação linear

o problema resolvido pelo método de programação dinâmica

tarefa de planejamento de rede.

27. Uma pequena empresa produz dois tipos de produtos. Para a fabricação de um produto do tipo A, são consumidos 2 kg de matéria-prima, para a fabricação de um produto do tipo B - 1 kg. São 60 kg de matéria-prima no total. É necessário traçar um plano de produção que garanta o recebimento da maior receita, se o custo de venda de um produto do tipo A é de 3 unidades, o tipo B é de 1 unidade. Ou seja, os produtos do tipo A não precisam ser feitos mais do que 25 e do tipo B - não mais do que 30.

A função objetivo desta tarefa é a função ...

F(x1, x2)=3x1+x2→max

F(x1, x2)=25x1+30x2→max

F(x1, x2)=2x1+x2→max

F(x1, x2)=60 -2x1 - x2→min

28. Uma pequena empresa produz produtos de dois tipos. Para a fabricação de um produto do tipo A, são consumidos 2 kg de matéria-prima, para a fabricação de um produto do tipo B - 1 kg. São 60 kg de matéria-prima no total. É necessário traçar um plano de produção que garanta o recebimento da maior receita, se o custo de venda de um produto do tipo A é de 3 unidades, o tipo B é de 1 unidade. Ou seja, os produtos do tipo A não precisam ser feitos mais do que 25 e do tipo B - não mais do que 30

Um plano válido para esta tarefa é um plano:

X =(20, 20)

X =(25, 15)

X =(20, 25)

X =(30, 10)

29. Em dois pontos A1 e A2, existem, respectivamente, 60 e 160 unidades de mercadorias. Todas as mercadorias devem ser transportadas para os pontos B1, B2, B3 no valor de 80, 70 e 70 unidades, respectivamente. A matriz tarifária é a seguinte :. Planeje o transporte de forma que o custo seja mínimo.

Esta tarefa é ...

tarefa de transporte

problema de programação não linear

problema do caixeiro viajante

tarefa de atribuição

30. Em dois pontos A1 e A2, existem, respectivamente, 60 e 160 unidades de mercadorias. Todas as mercadorias devem ser transportadas para os pontos B1, B2, B3 no valor de 80, 70 e 70 unidades, respectivamente. A matriz tarifária é a seguinte :. Planeje o transporte de forma que o custo seja mínimo

O plano básico para esta tarefa é o plano:

;

31. Em dois pontos A1 e A2, existem, respectivamente, 60 e 160 unidades de mercadorias. Todas as mercadorias precisam ser transportadas para os pontos B1, B2, B3 no valor de 80, 70 e 70 unidades, respectivamente. A matriz tarifária é a seguinte :. Planeje o transporte de forma que o custo seja mínimo.

A função objetivo desta tarefa é a função:

F=4x11+6x12 + 8x13+5x21+8x22+7x23→min

F= →min

F=60x1+160x2 + 80x3+70x4+705 →max

F=60x1+160x2– 80x3– 70x4– 705 →min

32. Em dois pontos A1 e A2, existem, respectivamente, 60 e 160 unidades de mercadorias. Todas as mercadorias devem ser transportadas para os pontos B1, B2, B3 no valor de 80, 70 e 70 unidades, respectivamente. A matriz tarifária é a seguinte :. Planeje o transporte de forma que o custo seja mínimo.

O plano ideal para esta tarefa é o plano:

;

.

;

;

33. Problema de transporte

será fechado se ...

34. Problema de transporte

é um…

abrir

fechado

insolúvel

35. Problema de transporte

é um…

fechado

abrir

insolúvel

36. Para resolver o seguinte problema de transporte

Você deve entrar ...

consumidor fictício

fornecedor fictício;

tarifa efetiva

37. Para resolver o seguinte problema de transporte

Você deve entrar ...

fornecedor fictício;

consumidor fictício

tarifa efetiva

taxa de juros efetiva.

38. Entre essas tarefas de transporte

fechados são ...

39. O plano de linha de base inicial do problema de transporte pode ser traçado ...

por todos os métodos acima

Método do canto noroeste

pelo método de tarifa mínima

método de dupla preferência

pelo método de aproximação de Vogel

40. Se a função objetivo do problema de programação linear é definida para o máximo, então ... a função objetivo do problema dual é definida para o mínimo

não há função objetiva no problema dual

o problema duplo não tem soluções

o problema duplo tem infinitas soluções

41. Um problema de programação linear é dado:

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

O seguinte será duplo para esta tarefa ...

F *(y1, y2) = 14y1 + 8y2 → min,

3 anos 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

F *(y1, y2) = 2y1 + 7y2 → min,

2y1 + 3y2 ³ 14,

y 1 + y2 ³ 8,

y 1 £ 0, y2 £ 0.

F *(y1, y2) = 2y1 + 7y2 → min,

3 y 1 + y2 ³ 7,

y 1 £ 0, y2 £ 0.

F *(y1, y2) = 14y1 + 8y2 → min,

y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

42. Se um de um par de problemas duplos tem um plano ideal, então ...

e o outro tem um plano ótimo

o outro não tem um plano ideal

o outro não tem soluções viáveis

43. Se um dos dois problemas duais tem um plano ótimo, então ...

e o outro tem um plano ótimo e os valores das funções objetivo para seus planos ótimos são iguais entre si

e o outro tem um plano ótimo, mas os valores das funções objetivo para seus planos ótimos não são iguais entre si

outro problema pode não ter um plano ideal, mas ter soluções viáveis

44. Se a função objetivo de um do par de problemas duais não for limitada (para o problema máximo - de cima, para o problema mínimo - de baixo), então

outra tarefa não tem planos válidos

outra tarefa tem planos viáveis, mas não tem um plano ideal

a função objetivo de outra tarefa também não é limitada

45. Ao resolver alguns problemas de programação não linear, é usado ...

Método do multiplicador de Lagrange

Método de Gauss

Método de aproximação de Vogel

Método Gomori

46. ​​O problema da programação não linear está definido

F(NS 1, NS 2)= NS 12 + NS 22 → max,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

F(NS 1, NS 2) …

inacessível (+ ¥)

47. O problema da programação não linear está definido

F(NS 1, NS 2)= NS 12 + NS 22 → mno,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

F(NS 1, NS 2) …

48. O problema da programação não linear está definido

F(NS 1, NS 2)= NS 12 + NS 22 → max,

NS 1 + NS 2 =6,

NS 1, NS 2 - qualquer.

O maior valor da função objetivo F(NS 1, NS 2) …

inacessível (+ ¥)

49. O problema da programação não linear está definido

F(NS 1, NS 2)= NS 12 + NS 22 → mno,

NS 1 + NS 2 =6,

NS 1, NS 2 - qualquer.

O menor valor da função objetivo F(NS 1, NS 2) …

inacessível (- ¥)

50. A região de soluções viáveis ​​para o problema de programação não linear tem a forma:

Então, o valor máximo da função F(NS 1, NS 2)= NS 12 +NS 22 é igual a ...

51. A região de soluções viáveis ​​para o problema de programação não linear tem a forma:

Então, o valor mínimo da função F(NS 1, NS 2)= NS 12 +NS 22 é igual a ...

52. Para resolver o problema de transporte pode ser aplicado ...

método potencial

Método do multiplicador de Lagrange

Método de Gauss

método de desorientação

53. No sistema de restrições do problema geral de programação linear ...

54. No sistema de restrições do problema de programação linear padrão (simétrico) ...

apenas desigualdades podem estar presentes

ambas as equações e desigualdades podem estar presentes

apenas equações podem estar presentes

55. No sistema de restrições do problema de programação linear canônica (básico) ...

apenas equações podem estar presentes (desde que as variáveis ​​sejam não negativas)

apenas desigualdades podem estar presentes (desde que as variáveis ​​sejam não negativas)

ambas as equações e desigualdades podem estar presentes (desde que as variáveis ​​não sejam negativas)

56. O problema da programação linear

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

Gravado em ...

forma padrão (simétrica)

formulário canônico (básico)

forma verbal

57. Para registrar uma tarefa

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

na forma canônica ...

58. Para registrar uma tarefa

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 + 4NS 2 ≥ 10,

NS 1 ≥ 0, NS 2 ≥ 0.

na forma canônica ...

é necessário introduzir três variáveis ​​não negativas adicionais

é necessário introduzir duas variáveis ​​não negativas adicionais

é necessário introduzir quatro variáveis ​​não negativas adicionais

59. Para registrar uma tarefa

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 = 14,

NS 1 + NS 2 ≤ 8,

NS 1 + 4NS 2 ≥ 10,

NS 1 ≥ 0, NS 2 ≥ 0.

na forma canônica ...

é necessário introduzir duas variáveis ​​não negativas adicionais

é necessário introduzir três variáveis ​​não negativas adicionais

é necessário introduzir quatro variáveis ​​não negativas adicionais

é necessário introduzir cinco variáveis ​​não negativas adicionais

60. Ao resolver problemas de programação inteira, ele pode ser usado ...

Método Gomori

Método do multiplicador de Lagrange

Método de Gauss

Método de aproximação de Vogel

61. No centro da resolução de problemas pelo método de programação dinâmica está ...

Navalha de Occam

o princípio "dente por dente, olho por olho"

Princípio de Heisenberg

62 Uma situação na qual estão envolvidas partes, cujos interesses são total ou parcialmente opostos, é chamada de ...

(conflito, conflito, conflito, conflito)

63. Um conflito real ou formal em que há pelo menos dois participantes (jogadores), cada um dos quais se esforça para atingir seus próprios objetivos, é chamado ...

(jogo, jogo)

64. As ações permissíveis de cada um dos jogadores, visando atingir determinado objetivo, são denominadas ...

(regras do jogo, regras do jogo)

65. A avaliação quantitativa dos resultados do jogo é chamada de ...

(por pagamento, pagamento, pagamento)

66. Se apenas dois lados (duas pessoas) participam do jogo, o jogo é chamado de ...

(duplas, duplas, duplas, duplas)

67. Se em um jogo de duplas a soma dos pagamentos é igual a zero, ou seja, a perda de um jogador é igual ao ganho do outro, então o jogo é chamado de jogo ...

(soma zero)

68. Uma descrição inequívoca da escolha do jogador em cada uma das situações possíveis em que ele deve fazer um movimento pessoal é chamada.

(estratégia do jogador, estratégia do jogador, estratégia, estratégia)

69. Se, com várias repetições do jogo, a estratégia fornece ao jogador o ganho médio máximo possível (perda média mínima possível), então tal estratégia é chamada de ...

(estratégia ótima, ótima, estratégia ótima, estratégia ótima)

70. Sejam a o preço baixo eb o preço alto de um jogo de duplas de soma zero. Então a afirmação é verdadeira ...

71. Sejam a o preço baixo eb o preço alto de um jogo de duplas de soma zero. Se a = b = v, então o número v é chamado ...

ao custo do jogo

ponto de equilíbrio

estratégia ótima

estratégia mista

72. Sejam a o preço baixo eb o preço alto de um jogo de duplas de soma zero. Se a = b, então o jogo é chamado ...

jogo de ponto de sela

conflito insolúvel

um jogo sem regras

73. Um vetor, cada um de cujos componentes mostra a frequência relativa de uso do jogador da estratégia pura correspondente, é chamado ...

estratégia mista

vetor de direção

vetor normal

gradiente

74. O preço mais baixo do jogo da matriz, dado pela matriz de pagamento, é igual a ...

Mais preço mínimo

igual ao preço mais baixo

não existe

81. Um jogo de matriz dado por uma matriz de payoff, ...

tem um ponto de sela

não tem ponto de sela

não emparelhado

82. O preço do jogo, dado pela matriz de payoff, é ...

83. Um jogo de matriz dado por uma matriz de payoff ...

está emparelhado

tem um ponto de sela

não emparelhado

84. Jogo de duplas de soma zero, dado por sua matriz de pay-off, pode ser reduzido a ...

problema de programação linear

problema de programação não linear

problema de programação linear inteira

problema de otimização clássico

85. O preço mais baixo do jogo da matriz dado pela matriz de pagamento é ...

Mais preço mínimo

igual ao preço mais baixo

não existe

92. Um jogo de matriz dado por uma matriz de payoff ...

não tem ponto de sela

tem um ponto de sela

não emparelhado

93. O preço do jogo, dado pela matriz de pagamento, está dentro de ...

94. Se no fluxo de eventos, os eventos se sucedem em intervalos de tempo predeterminados e estritamente definidos, então tal fluxo é chamado de ...

regular

organizado

95. Se a probabilidade de qualquer número de eventos cair em um intervalo de tempo depende apenas da duração desse intervalo e não depende de quão longe este intervalo está localizado desde o início do tempo, então o fluxo correspondente de eventos é chamado:

estacionário

fluir sem consequências

o mais simples

Poisson

96. Se o número de eventos caindo em um dos intervalos de tempo escolhidos arbitrariamente não depender do número de eventos caindo em outro, também intervalo de tempo escolhido arbitrariamente, desde que esses intervalos não se cruzem, então o fluxo de eventos correspondente é chamado ...

fluir sem consequências

regular

indicativo

normal

97. Se a probabilidade de dois ou mais eventos atingirem um intervalo de tempo muito curto de uma vez é insignificante em comparação com a probabilidade de atingir apenas um evento, então o fluxo correspondente de eventos é chamado de ...

comum

extraordinário

normal

Poisson

98. Se o fluxo de eventos possui simultaneamente as propriedades de estacionariedade, normalidade e ausência de consequências, então é chamado de:

mais simples (Poisson)

normal

99. Um sistema de canal único com falhas é uma estação de serviço diária para lavagem de carros. Aplicativo - um carro que chegou no momento em que o posto é ocupado - recebe uma negação de serviço. Taxa de fluxo do carro λ = 1,0 (carro por hora). O tempo médio de atendimento é de 1,8 horas. O fluxo do carro e o fluxo de serviço são os mais simples. Então, no estado estacionário, a taxa de transferência relativa qé igual a ...

100. Um sistema de canal único com falhas é uma estação de serviço diária para lavagem de carros. Aplicativo - um carro que chegou no momento em que o posto é ocupado - recebe uma negação de serviço. Taxa de fluxo do carro λ = 1,0 (carro por hora). O tempo médio de atendimento é de 1,8 horas. O fluxo do carro e o fluxo de serviço são os mais simples. Então, no estado estacionário, a porcentagem de carros que recebem uma negação de serviço é ...

Formulação geral do problema de programação linear (LPP). Exemplos de LPP

A programação linear é um ramo da matemática que estuda métodos para resolver problemas extremos, que se caracterizam por uma relação linear entre variáveis ​​e um critério linear de otimalidade. Algumas palavras sobre o próprio termo programação linear. Requer compreensão correta. Nesse caso, programar, é claro, não é escrever programas de computador. A programação aqui deve ser interpretada como planejamento, a formação de planos, o desenvolvimento de um programa de ação. Os problemas matemáticos da programação linear incluem o estudo da produção específica e das situações econômicas, que de uma forma ou de outra são interpretadas como problemas de uso ótimo de recursos limitados. A gama de tarefas que podem ser resolvidas usando métodos de programação linear é bastante ampla. Este é, por exemplo:

• - o problema da otimização do uso de recursos no planejamento da produção;
• - o problema das misturas (planejamento da composição dos produtos);
• - o problema de encontrar a combinação ideal de vários tipos de produtos para armazenamento em armazéns (gestão de inventário ou "problema da mochila");
• - tarefas de transporte (análise da localização da empresa, movimento de mercadorias). A programação linear é o ramo da programação matemática mais desenvolvido e amplamente utilizado (além disso, inclui: programação inteira, dinâmica, não linear e paramétrica). Isso se deve ao seguinte:
• - os modelos matemáticos de um grande número de problemas econômicos são lineares em relação às variáveis ​​procuradas;
• - este tipo de problema é atualmente o mais estudado. Para ele, métodos especiais foram desenvolvidos com a ajuda dos quais essas tarefas são resolvidas, e os programas de computador correspondentes;
• - muitos problemas de programação linear, tendo sido resolvidos, encontraram ampla aplicação;
• - alguns problemas que na formulação original não são lineares, após uma série de restrições e suposições adicionais podem se tornar lineares ou podem ser reduzidos a uma forma que possam ser resolvidos por métodos de programação linear. O modelo econômico e matemático de qualquer problema de programação linear inclui: uma função objetivo, cujo valor ótimo (máximo ou mínimo) precisa ser encontrado; restrições na forma de um sistema de equações lineares ou desigualdades; requisito de não negatividade das variáveis. Em termos gerais, o modelo é escrito da seguinte forma:
• - função objetiva:

C1x1 + c2x2 + ... + cnxn> max (min); - restrições:

a11x1 + a12x2 + ... + a1nxn (? =?) b1,

a21x1 + a22x2 + ... + a2nxn (? =?) b2

am1x1 + am2x2 + ... + amnxn (? =?) bm;

Requisito de não negatividade:

Nesse caso, aij, bi, cj () recebem constantes. O problema é encontrar o valor ótimo da função (2.1) sujeito às restrições (2.2) e (2.3). O sistema de restrições (2.2) é chamado de restrições funcionais do problema e as restrições (2.3) são chamadas diretas. Um vetor que satisfaça as restrições (2.2) e (2.3) é chamado de solução viável (plano) do problema de programação linear. O projeto no qual a função (2.1) atinge seu valor máximo (mínimo) é denominado ótimo.

Abaixo estão exemplos de alguns problemas típicos resolvidos usando métodos de programação linear. Essas tarefas têm um conteúdo econômico real. Agora, apenas os formularemos em termos de LPP e consideraremos métodos para resolver esses problemas a seguir.

1. O problema da otimização do uso de recursos no planejamento da produção. O significado geral das tarefas desta classe é o seguinte. A empresa produz n produtos diferentes. Sua produção requer m diferentes tipos de recursos (matérias-primas, materiais, tempo de trabalho, etc.). Os recursos são limitados, suas reservas no período de planejamento são, respectivamente, b1, b2, ..., bm unidades convencionais. Também são conhecidos os coeficientes tecnológicos aij, que mostram quantas unidades do i-ésimo recurso são necessárias para produzir uma unidade do j-ésimo tipo de produto (). O lucro auferido pela empresa com a venda do produto do tipo j é igual a cj. No período de planejamento, os valores de aij, bi e cj permanecem constantes. É necessário traçar tal plano de produção, em cuja implementação o lucro da empresa seria maior. Abaixo está um exemplo simples de uma tarefa desta classe.

A empresa é especializada na produção de tacos de hóquei e jogos de xadrez. Cada clube gera $ 2 de lucro para a empresa e $ 4 para cada jogo de xadrez. Demora quatro horas para fazer um clube no Site A e duas horas no Site B. Um jogo de xadrez é feito com seis horas no Site A, seis horas no Site B e uma hora no Site C. A capacidade de produção disponível no Site A é 120 Nm. - horas por dia, seção B - 72 n horas e seção C - 10 n horas. Quantos tacos e jogos de xadrez uma empresa deve produzir diariamente para maximizar os lucros?

As condições para problemas desta classe são freqüentemente apresentadas em forma de tabela (ver Tabela 2.1).

Sob esta condição, formulamos um problema de programação linear. Vamos designar: x1 - o número de tacos de hóquei produzidos diariamente, x2 - o número de jogos de xadrez produzidos diariamente. Redação ZLP:

4x1 + 6x2? 120,

Enfatizemos que cada desigualdade no sistema de restrições funcionais corresponde neste caso a um ou outro local de produção, a saber: o primeiro ao local A, o segundo ao local B, e o terceiro ao local C.

O sistema de variáveis ​​no problema de otimização da estrutura das áreas semeadas, levando em consideração as rotações de culturas.