Otimização Convexa - Programação Linear

Metodologia

A Programação Linear, também chamada de Otimização Linear, é uma técnica usada para resolver problemas matemáticos nos quais as relações são lineares. a natureza básica da Programação Linear é maximizar ou minimizar umobjective function com assunto para alguns constraints. A função objetivo é uma função linear obtida a partir do modelo matemático do problema. As restrições são as condições que são impostas ao modelo e também são lineares.

  • A partir da pergunta fornecida, encontre a função objetivo.
  • encontre as restrições.
  • Desenhe as restrições em um gráfico.
  • encontre a região viável, que é formada pela interseção de todas as restrições.
  • encontre os vértices da região viável.
  • encontre o valor da função objetivo nesses vértices.
  • O vértice que maximiza ou minimiza a função objetivo (de acordo com a pergunta) é a resposta.

Exemplos

Step 1 - Maximize $ 5x + 3y $ sujeito a

$ x + y \ leq 2 $,

$ 3x + y \ leq 3 $,

$ x \ geq 0 \: and \: y \ geq 0 $

Solution -

O primeiro passo é encontrar a região viável em um gráfico.

Claramente a partir do gráfico, os vértices da região viável são

$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right ) $

Seja $ f \ left (x, y \ right) = 5x + 3y $

Colocando esses valores na função objetivo, obtemos -

$ f \ left (0, 0 \ right) $ = 0

$ f \ left (0, 2 \ right) $ = 6

$ f \ left (1, 0 \ right) $ = 5

$ f \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $ = 7

Portanto, a função é maximizada em $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $

Step 2- Uma empresa de relógios produz um relógio digital e um mecânico. As projeções de longo prazo indicam uma demanda esperada de pelo menos 100 relógios digitais e 80 mecânicos por dia. Devido às limitações da capacidade de produção, não mais do que 200 relógios digitais e 170 mecânicos podem ser produzidos diariamente. Para cumprir um contrato de remessa, um total de pelo menos 200 relógios deve ser despachado por dia.

Se cada relógio digital vendido resulta em uma perda de $ \ $ 2 $, mas cada relógio mecânico produz um lucro de $ \ $ 5 $, quantos de cada tipo devem ser feitos diariamente para maximizar o lucro líquido?

Solution -

Seja $ x $ o número de relógios digitais produzidos

$ y $ é o número de relógios mecânicos produzidos

De acordo com a pergunta, pelo menos 100 relógios digitais devem ser feitos diariamente e no máximo 200 relógios digitais podem ser feitos.

$ \ Rightarrow 100 \ leq \: x \ leq 200 $

Da mesma forma, pelo menos 80 relógios mecânicos devem ser feitos diariamente e no máximo 170 relógios mecânicos podem ser feitos.

$ \ Rightarrow 80 \ leq \: y \ leq 170 $

Uma vez que pelo menos 200 relógios devem ser produzidos a cada dia.

$ \ Rightarrow x + y \ leq 200 $

Uma vez que cada relógio digital vendido resulta em uma perda de $ \ $ 2 $, mas cada relógio mecânico produz um lucro de $ \ $ 5 $,

O lucro total pode ser calculado como

$ Lucro = -2x + 5y $

E temos que maximizar o lucro, portanto, a questão pode ser formulada como -

Maximize $ -2x + 5y $ sujeito a

$ 100 \: \ leq x \: \ leq 200 $

$ 80 \: \ leq y \: \ leq 170 $

$ x + y \: \ leq 200 $

Traçando as equações acima em um gráfico, obtemos,

Os vértices da região viável são

$ \ left (100, 170 \ right) \ left (200, 170 \ right) \ left (200, 180 \ right) \ left (120, 80 \ right) e \ left (100, 100 \ right) $

O valor máximo da função objetivo é obtido em $ \ left (100, 170 \ right) $ Assim, para maximizar os lucros líquidos, 100 unidades de relógios digitais e 170 unidades de relógios mecânicos devem ser produzidas.