WEBQUEST - Programação Linear

Faculdade de Tecnologia de Carapicuíba – Centro Estadual de Ensino Tecnológico Paula Souza – Governo do Estado de São Paulo

Atividade (webquest) da disciplina de Programação Linear no curso do Analise e Desenvolvimento de Sistemas do 5º semestre da Fatec de Carapicuíba,  proposto pelo professor Luciano Condori como atividade complementar.

A tarefa

Criar um página web sobre Programação Linear, como atividade complementar do Curso de ADS da Fatec Carapicuíba do Profº Luciano Condori."

Autor

Nome: Thiago Sousa Cruz

Instituição: Fatec - Carapicuíba

Curso: Análise e Desenvolvimento de Sistemas

E-mail: thisc007@gmail.com

Objetivo

- Obter conhecimentos específicos sobre os  conteúdos expostos;

- Ajudar no aprendizado em aula;

- Ajudar outras pessoas a terem acesso a essa ferramenta de estudo.

- Compartilhar o conhecimento adquirido através dessa atividade.

História da Programação Linear e Sistemas Lineares

O problema de optimizar uma função linear, sujeita a restrições, teve origem com os estudos de Fourier sobre sistemas lineares de inequações em 1826. No entanto, só em 1939 é que se percebeu a importância prática destes problemas, o que levou à criação de um algoritmo para a sua resolução.

• Verificar, no contexto do problema, a legitimidade do uso de inequações ou equações lineares.
• Identificar as variáveis.
• Identificar a função objetivo.
• Identificação das restrições.
• Resolver matematicamente o problema
• Depois de se ter obtida a fórmula matemática do problema, é então possível resolver o problema de otimização.

Atualmente na maior parte dos problemas é muito difícil não utilizar o computador, tal é a diversidade de variáveis e a quantidade de cálculos envolvidos.

A história dos sistemas de equações lineares começa no oriente. Em 1683, num trabalho do japonês Seki Kowa, surge a ideia de determinante[6] (como polinômio que se associa a um quadrado de números).

O uso de determinantes no Ocidente começou dez anos depois num trabalho de Leibniz, ligado também a sistemas lineares.

A conhecida regra de Cramer é na verdade uma descoberta do escocês Colin Maclaurin (1698-1746), datando provavelmente de 1729, embora só publicada postumamente em 1748 no seu Treatise of algebra.

O suíço Gabriel Cramer (1704-1752) não aparece nesse episódio de maneira totalmente gratuita. Cramer também chegou à regra independentemente.

O francês Étienne Bézout (1730-1783), autor de textos matemáticos de sucesso em seu tempo, tratou do assunto, sendo complementado posteriormente por Laplace, em Pesquisas sobre o cálculo integral e o sistema do mundo.

O termo determinante, com o sentido atual, surgiu em 1812 num trabalho de Cauchy sobre o assunto. Neste artigo, apresentado à Academia de Ciências, sugeriu a notação que hoje é aceita como convenção.

Já o alemão Jacobi fez a leitura dessa teoria da forma como atualmente se estuda.

Método Simplex Resolução Algébrica

O método algébrico para solução de um modelo linear
A solução de problemas de programação linear com mais de duas variáveis, não pode
ser obtida utilizando-se o algoritmo gráfico. Como cada variável é representada por um eixo
do gráfico, um problema com mais de duas variáveis não pode ser representado no plano, o
que torna a visualização da solução impossível ou muito complexa, como podemos observar
no exemplo a seguir.
Exemplo de P.P.L. com três variáveis de decisão.
Modelo:
Função Objetivo
MÁX Z = 4 * X1 + 4 * X2 + 4 * X3
Restrições:
R1  -->4 * X1 + 3 * X2 <= 12
R2 --> X2 <= 3
R3 --> X3 <= 2
Restrições implícitas:
R4 --> X1 >=0
R5 --> X2 >= 0
R6 --> X3 >= 0
OBS.:
- O conjunto de soluções viáveis para o modelo acima, será representado
graficamente em três dimensões, como um poliedro, cujas faces são os planos limites das
restrições.
- A função objetivo será representada como uma família de planos paralelos ao plano
Zqq apresentado na figura 6.1, que faz um ângulo de 45o com os três eixos.
- O ponto ótimo será o vértice do poliedro mais afastado da origem.
PESQUISA OPERACIONAL

Conceitos da álgebra linear utilizados pelo algoritmo SIMPLEX

Um sistema de equações lineares pode ser resolvido, algebricamente, dividindo-se e

multiplicando-se por constantes as equações e somando-as entre si. Estas operações alteram o

sistema inicial, mas não modificam o resultado dos sistemas.

Resolvendo o sistema abaixo algebricamente e acompanhando pelo gráfico temos:

Sistema Inicial: R1 --> 3 * x1 + 3 * x2 = 9

R2 --> 2 * x1 + 4 * x2 = 8

Determinamos um novo sistema executando as seguintes operações:

a) Dividindo R1 por (3) encontramos uma nova equação R1,

b) Multiplicando a nova R1 por (-2) e somando com R2 do sistema inicial,

encontramos a nova equação R2.

O novo sistema é mais simples, mas possui a mesma solução do sistema inicial.

O novo sistema: R1 --> 1 * x1 + 1 * x2 = 3

R2 --> 2 * x2 = 2

Determinamos um novo sistema executando as seguintes operações:

a) Dividindo R2 por (2) encontramos uma nova equação R2,

b) Multiplicando a nova R2 por (-1) e somando com R1 do sistema anterior,

encontramos a nova equação R1.

O novo sistema é mais simples, mas possui a mesma solução do sistema inicial.

O novo sistema: R1--> 1 * x1 = 2

R2 --> 1 * x2 = 1

Generalizando, a partir do exemplo anterior, verificamos que para resolver um

sistema qualquer de equações lineares, devemos transformar o sistema da forma geral para

uma forma reduzida onde cada variável apareça independente, associada à uma equação.

Exemplo: Forma Geral de um sistema linear com duas equações.

R1 --> a11 * x1 + a12 * x2 = b1

R2 --> a21 * x1 + a22 * x2 = b2

Forma Reduzida.

R1 --> x1 = d1

R2 --> x2 = d2

O sistema reduzido possui a mesma solução do sistema original.

Usando a notação matricial temos:

Forma geral: A*X = B Forma reduzida: I* X = D

Onde: A é uma matriz genérica;

X é um vetor de variáveis;

B e D são vetores de constantes e

I é a matriz identidade com a mesma ordem da matriz A.

Método Gráfico

Solução através do método gráfico o seguinte problema:

Maximizar	Z = f(x,y) = 3x + 2y
sujeita às restrições:	2x + y ≤ 18
	2x + 3y ≤ 42
	3x + y ≤ 24
	x ≥ 0 , y ≥ 0

1. Inicialmente, o sistema de coordenadas da associação de um eixo com variável "X" e o outro o "Y" é desenhado (geralmente associa-se "x" em relação ao eixo horizontal e o "y" ao vertical), como pode ser visto na figura.
2. Nestes eixos, marca-se uma escala numérica apropriada aos valores que podem assumir as variáveis conforme as restrições do problema. Para isto, em cada restrição anulam-se todas as variáveis, exceto aquelas que correspondem a um eixo concreto, estabelecendo o valor adequado para este eixo. Este processo é repetido para cada um dos eixos.
3. As restrições são representadas a seguir. Primeiramente, desenha-se a reta que é obtida ao considerar a restrição como uma igualdade. Ela é representada como o segmento que une A com B e região que delimita esta restrição é indicada pela cor AMARELA. O processo é repetido com as outras restrições, ficando delimitada a região de cor AZUL e VERMELHO para a segunda e terceira restrição respectivamente.
4. A região viável é a interseção das regiões definidas tanto pelo conjunto de restrições, como pelas condições de não negatividade das variáveis, ou seja, ambos os eixos de coordenadas. Tal região viável é representada pelo polígono O-F-H-G-C, de cor VIOLETA.
   
5. Como existe uma região viável, passamos a determinar os seus pontos extremos, ou vértices do polígono que representa. Esses vértices são os pontos candidatos a soluções ótimas. Neste exemplo são os pontos O-F-H-G-C da figura.
6. Finalmente, a função objetivo (3x + 2y) em cada um destes pontos (resultado determinado na tabela abaixo) é avaliada. Como o ponto G fornece o maior valor para a função Z e o objetivo é maximizar, este ponto é a solução ideal: Z = 33 con x = 3 e y = 12.

Ponto extremo	Coordenadas (x,y)	Valor objetivo (Z)
O	(0,0)	0
C	(0,14)	28
G	(3,12)	33
H	(6,6)	30
F	(8,0)	24

Comparação do método Gráfico com o método Simplex

As tabelas construídas, sucessivamente, durante o método Simplex vão fornecendo o valor da função objetivo em diferentes vértices da região viável, ao mesmo tempo, ajustando os coeficientes das variáveis iniciais e de folga.

Na tabela inicial foi calculado o valor da função objetivo no vértice O, cujas coordenadas (0,0) se correspondem com o valor que têm as variáveis básicas e o resultado é 0.

Tabela I . Iteração 1
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P3	0	18	2	1	1	0	0
P4	0	42	2	3	0	1	0
P5	0	24	3	1	0	0	1
Z		0	-3	-2	0	0	0

A variável que entra na base do método Simplex determina a que novo vértice será realizado o deslocamento. Neste exemplo, como entra P1 (correspondente ao 'x'), o deslocamento é realizado pela aresta OF até atingir o vértice F, onde é calculado o valor que assume a função Z. Este passo ocorre na segunda iteração do método Simplex, mostrado na Tabela II. Onde foi calculado o valor correspondente à vértice F, obtendo-se um valor Z = 24 para a função.

Tabela II . Iteração 2
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P3	0	2	0	1/3	1	0	-2/3
P4	0	26	0	7/3	0	1	-2/3
P1	3	8	1	1/3	0	0	1/3
Z		24	0	-1	0	0	1

Um novo deslocamento é realizado na aresta FH até chegar em H (dados na tabela III). Na terceira iteração, o valor da função no vértice H é calculado, obtendo-se Z = 30.

Tabela III . Iteração 3
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P2	2	6	0	1	3	0	-2
P4	0	12	0	0	-7	1	4
P1	3	6	1	0	-1	0	1
Z		30	0	0	3	0	-1

O processo prossegue através da aresta HG, até o vértice G. Os dados obtidos são mostrados na Tabela IV. Neste ponto, o processo termina, e é possível verificar que a solução não é melhorada pela aresta GC até o vértice C (não excede o valor atual da função).

Tabela IV . Iteração 4
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P2	2	12	0	1	-1/2	1/2	0
P5	0	3	0	0	-7/4	1/4	1
P1	3	3	1	0	3/4	-1/4	0
Z		33	0	0	5/4	1/4	0

O valor máximo da função objetiva é 33, e corresponde aos valores x = 3 e y = 12 (coordenadas do vértice G).

Com o método gráfico é necessário calcular o valor da função objetivo em cada vértice da região viável, enquanto que o método simplex termina quando o valor ótimo é encontrado.

Pesquisa Operacional - Vídeo-aulas

PO - modelo de programação linear - exemplo 1

PO - 1 - modelo de programação linear - exemplo 2

PO - 1 - modelo de programação linear - exercício resolvido

Método Simplex - aula 1

Método Simplex - aula 2

Pesquisa Operacional - Método Simplex aula 3

Pesquisa Operacional - análise gráfica 1

Pesquisa Operacional - Análise gráfica aula 2

Pesquisa Operacional - Modelagem 1

Pesquisa Operacional: Modelagem 2

Pesquisa Operacional: Modelagem, resolução gráfica e Simplex - aula 1

Pesquisa Operacional: Modelagem, resolução gráfica e Simplex - aula 2

Pesquisa Operacional: Modelagem, resolução gráfica e Simplex - aula 3

O que é programação linear?

O problema geral de programação linear é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, chamada de função objetivo, sujeita a uma série de equações (ou inequações) lineares, chamadas restrições.

A formulação do problema a ser resolvido segue três pontos básicos:

• Definição do objetivo do problema
• Definição das variáveis de decisão envolvidas
• Conhecimento das restrições a que está sujeito o problema

O que é Programação Linear?

Suponha que uma empresa produza quatro modelos diferentes de brinquedos. Cada um deles gera uma quantidade de lucro diferente ao ser vendida. O brinquedo 1 gera $10 de lucro, o 2 gera $8, o 3 gera $9 e o 4 gera $7. A função que determina o lucro da empresa é:

${\displaystyle Z=10x_{1}+8x_{2}+9x_{3}+7x_{4}}$

Assumindo que as variáveis são a quantidade de cada brinquedo que é vendida.

Esta é uma função linear, pois cada um dos termos da equação que a forma é uma constante ou um produto entre uma constante e um valor variável. Suponha agora que nós estamos interessados em descobrir qual é o maior lucro possível para esta empresa assumindo que o número máximo de vendas do brinquedo 1 é 100, do brinquedo 2 é 60, do brinquedo 3 é 40 e do brinquedo 4 é 70. Podemos então expressar este problema da seguinte forma:

Máx ${\displaystyle Z=10x_{1}+8x_{2}+9x_{3}+7x_{4}}$ (Função Objetivo)

${\displaystyle 1x_{1}+0x_{2}+0x_{3}+0x_{4}\leq 100}$ (Restrição 1)

${\displaystyle 0x_{1}+1x_{2}+0x_{3}+0x_{4}\leq 60}$ (Restrição 2)

${\displaystyle 0x_{1}+0x_{2}+1x_{3}+0x_{4}\leq 40}$ (Restrição 3)

${\displaystyle 0x_{1}+0x_{2}+0x_{3}+1x_{4}\leq 70}$ (Restrição 4)

${\displaystyle x_{1},x_{2},x_{3},x_{4}\geq 0}$ (As variáveis de decisão são não-negativas)

O que temos acima é um modelo de Programação Linear. Ele é formado sempre por uma função linear (que é a função objetivo) e por um conjunto de ineqüações lineares (restrições do problema). No exemplo acima, desejamos obter o maior lucro possível (maior valor de Z). O objetivo da programação linear é justamente fornecer ferramentas para resolver o desafio de encontrar o maior ou o menor valor possível em uma função linear cujas variáveis possuem restrições.

Assim, o problema geral de programação linear pode ser definido por:

Maximizar (ou minimizar) a função objetivo:

${\displaystyle Z=c_{1}\cdot x_{1}+c_{2}\cdot x_{2}+...+c_{n}\cdot x_{n}\,\!}$

sujeita às restrições:

${\displaystyle a_{11}\cdot x_{1}+a_{12}\cdot x_{2}+...+a_{1n}\cdot x_{n}\leq b_{1}\,\!}$
${\displaystyle a_{21}\cdot x_{1}+a_{22}\cdot x_{2}+...+a_{2n}\cdot x_{n}\leq b_{2}\,\!}$
${\displaystyle a_{31}\cdot x_{1}+a_{32}\cdot x_{2}+...+a_{3n}\cdot x_{n}\leq b_{3}\,\!}$
a
${\displaystyle a_{m1}\cdot x_{1}+a_{m2}\cdot x_{2}+...+a_{mn}\cdot x_{n}\leq b_{m}\,\!}$

considerando que todas as variáveis de decisão assumem valores positivos:

 ${\displaystyle x_{1},x_{2},x_{n}\geq 0\,\!}$

Solução Gráfica

Um problema que contenha duas variáveis pode ser resolvido graficamente.

Traça-se um gráfico com os seus eixos sendo as variáveis ${\displaystyle x_{1}\,\!}$ e ${\displaystyle x_{2}\,\!}$.

A partir deste gráfico traçam-se as restrições do problema e delimita-se a região viável.

Após isso, traça-se uma reta com a inclinação da função objetivo, buscando retas paralelas a ela que forneçam a solução para o problema.

A História da Programação Linear

O desenvolvimento de técnicas algébricas para se lidar com inequações lineares é algo bastante antigo. Durante o século XVIII, o matemático e físico Jean-Baptiste Joseph Fourier desenvolveu vários métodos inovadores para se resolver sistemas de ineqüações. Um dos principais algoritmos desenvolvido por Fourier foi o Método de Eliminação de Fourier–Motzkin.

Durante a Segunda Guerra Mundial, novas tecnologias bélicas levaram à criação de grupos acadêmicos com o objetivo de resolver problemas como o uso eficiente de radares, canhões antiaéreos, escoltas navais, etc. O objetivo era sempre reduzir custos militares e buscar maximizar as baixas inimigas. Para resolver estes problemas, a Programação Linear mostrou-se extremamente útil. Os grupos acadêmicos que a utilizavam eram sempre mantidos secretos até o ano de 1947, após o término da guerra. Foi quando a Programação Linear passou a ser muito usada em empresas com o objetivo de reduzir despesas e maximizar lucros.

Também no ano de 1947, o matemático George Dantzig desenvolveu o Algoritmo Simplex, a maneira mais eficiente conhecida de se resolver modelos de Programação Linear. No mesmo ano, John von Neumann desenvolveu a teoria da dualidade e Leonid Kantorovich foi a primeira pessoa a aplicar a Programação Linear à Economia.

Em 1979, Leonid Khachiyan desenvolveu um novo algoritmo para resolver modelos de programação linear: o Algoritmo Elipsóide. O seu algoritmo foi o primeiro criado que era capaz de resolver problemas em tempo polinomial. Apesar disso, era mais lento que o já conhecido Algoritmo Simplex, tanto na teoria como na prática.

Em 1984, surge mais um método de se resolver problemas de pesquisa operacional: o Algoritmo do Ponto Interior, criado por Narendra Karmarkar. Assim como o Algoritmo Elipsóide, ele era polinomial. A diferença é que ele era bem mais rápido e conseguia competir com o Algoritmo Simplex.

A Criação de Modelos

O conceito de modelos é de importância fundamental ao estudarmos pesquisa operacional. Um modelo é uma representação simplificada da realidade. Para criarmos um modelo de programação linear, precisamos identificar em um problema qual é a função objetivo, as restrições e o tipo de otimização que desejamos (queremos achar o máximo ou o mínimo da função-objetivo?). Veja o exemplo abaixo:

Uma empresa fabrica mesas e cadeiras. O quadro abaixo mostra os recursos consumidos por unidade de cada produto e os seus lucros.Quantas mesas e cadeiras podem ser fabricados para se maximizar o lucro?

Unidades Necessárias

Recurso	Mesa	Cadeira	Quantidade Disponível
Madeira	30	20	310
Metal	5	10	113
Lucro	6	8	-

A nossa função objetivo é o total de lucro da venda de mesas (M) e cadeiras (C). Queremos descobrir qual o valor máximo possível de lucro que podemos obter. Logo, nossa função objetivo é:

Máx ${\displaystyle Z=6M+8C}$ (Função-Objetivo)

Agora precisamos analisar as restrições. Temos uma quantidade máxima de madeira disponível (310) e cada mesa e cada cadeira gastam uma certa quantidade deste material (30 e 20). Logo, temos uma restrição:

${\displaystyle 30M+20C\leq 310}$ (Restrição 1)

Da mesma forma, existe uma quantidade limitada de metais, o que nos dá a segunda restrição:

${\displaystyle 5M+10C\leq 113}$ (Restrição 2)

Além disso, sabemos que não podemos fabricar uma quantidade negativa de cadeiras ou mesas:

${\displaystyle M,C\geq 0}$

Pronto! Terminamos de construir o nosso modelo!

Solução Gráfica

Muito bem! Já sabemos como criar os modelos de Programação Linear. Mas... Como podemos resolvê-los? Como usar todos aqueles algoritmos comentados na seção sobre a história da Programação Linear? Bem, vamos com calma. Vamos ver primeiro uma das formas mais simples de se resolver este problema (embora não seja computacionalmente eficiente). Vamos fazer um gráfico analisando o Domínio da função-objetivo mostrada no exempo acima:

As linhas mais finas representam o eixo X e Y, os quais representam respectivamente o número de mesas (M) e cadeiras (C). Todos os pontos dentro ou abaixo àquela reta grossa mais inclinada representam pontos que satisfazem a Restrição 2. Todos os pontos dentro ou abaixo àquela reta grossa menos inclinada satisfazem a Restrição 1. Pontos à direita da reta Y e acima do eixo X satisfazem a exigência de que não podemos fabricar um número negativo de objetos. Quanto mais restrições um ponto no gráfico acima satisfaz, mais escuro ele aparece. A única região onde todas as restrições são satisfeitas é aquele triângulo escuro localizado próximo ao centro do gráfico. Os vértices do triângulo são os pontos (0,0), (0,10) e (5,0).

No ponto (0,0), o nosso lucro é nulo, pois não fabricamos nenhum produto. No ponto (0,10), nosso lucro é $80. No ponto (5,0), nosso lucro é $30. No exemplo dado acima, a forma de obter o maior lucro possível é abandonar completamente a fabricação de mesas e se dedicar apenas às cadeiras. E devemos produzir exatamente 10 cadeiras para termos o maior lucro possível.

Perceba que no exemplo acima, o Domínio da função-objetivo era uma região triangular. Como estamos sempre lidando com eqüações e ineqüações lineares, o domínio sempre será um polígono. Nunca conseguiremos obter curvas no gráfico do Domínio da função-objetivo. Outra coisa interessante é que o ponto ótimo que estávamos buscando coincidiu com um dos vértices do polígono. No caso de modelos de programação linear, isso sempre será verdade.

Sabendo disso, você já cohece a forma mais rudimentar de encontrarmos a solução de um modelo de programação Linear. Basta fazermos o gráfico do Domínio da função-objetivo e checarmos os valores da função em todos os seus vértices. Entretanto, essa não é a melhor forma de resolver este tipo de problema. No exemplo acima, haviam apenas duas variáveis (M e C). Mas e se houvessem mais? Como esboçar o gráfico do Domínio? E se o nosso Domínio fôsse representado por um polígono com 300 vértices? Seria trabalhoso demais calcular o valor da função em 300 pontos diferentes!

Bem, veremos métodos melhores de se resolver este tipo de problemas nos próximos capítulos.

Exercícios[editar | editar código-fonte]

1. Um vendedor ambulante sabe preparar pastéis e cachorros-quentes. Um cachorro-quente custa o dobro do preço de um pastel. Ele nunca consegue vender mais do que três pastéis e mais do que quatro cachorros-quentes em um mesmo dia. Um pastel vem com uma pitada de mostarda e um cachorro-quente com duas pitadas. Ele só tem disponível nove pitadas de mostarda para gastar em um único dia. Quantos pastéis e cachorros-quentes ele deve produzir em um único dia para ter o máximo possível de lucro? Resolva construindo um modelo de programação linear.

---

2. Estamos durante a Segunda Guerra Mundial. Temos à nossa disposição tanques e bombardeiros para atacar nossos inimigos. Sabemos que um tanque causa em média 20 baixas inimigas e um bombardeiro causa 50 baixas. Temos apenas 4 tanques à nossa disposição. Um bombardeiro requer 1 soldado para pilotá-lo e um tanque requer 2 (e não cabem soldados adicionais no veículo). Temos a obrigação de enviar no mínimo 9 soldados para o ataque para colaborar com as tropas aliadas que também atacarão. Com quantos tanques e bombardeiros devemos atacar para causar o maior número de baixas?

---

3. No exemplo acima, o que mudaria se acrescentássemos a informação de que temos 5 bombardeiros à nossa disposição?

Respostas dos Exercícios[editar | editar código-fonte]

1. A função-objetivo é:

Máx ${\displaystyle Z=P+2C}$ (P=Pastel, C=Cachorro-Quente, Z=lucro)

As restrições são:

${\displaystyle P\leq 3}$

${\displaystyle C\leq 4}$

${\displaystyle P+2C\leq 9}$

${\displaystyle P,C\geq 0}$

O gráfico do Domínio é:

O polígono mais escuro que representa os pontos que atendem à todas as restrições possui como vértices os pontos (0,0), (3,0), (3,3), (1,4) e (0,4). O lucro em (0,0) é $0, em (3,0) é $3, em (3,3) é $9, em (1,4) é $9 e em (0,4) é $8. Neste exemplo, não existe apenas um único ponto que representa o máximo da função - existem infinitos pontos. Todos aqueles que pertencem ao Domínio e estão na reta que liga (3,3) e (1,4) são o máximo da função e representam a quantidade ideal de produção de pastéis e cachorros-quentes para o vendedor ambulante. Como o vendedor ambulante não pode fazer um número fracionário de pastéis e cachorros, quentes, a resposta é: 3 pastéis e 3 cachorros-quentes ou então 1 pastel e 4 cachorros-quente.

---

2. Temos que resolver o modelo:

Máx ${\displaystyle Z=50B+20T}$ sujeito às seguintes restrições:

${\displaystyle T\leq 4}$

${\displaystyle B+2T\geq 9}$ <<< reveja essa restrição, não pode ser >= 9... tem que ser <= 9 ... a solução do problema ficou errada, não tem como usar 4 tanques e 5 bombardeiros, sendo que só no tanque gastaria 8 soldados, e mais 5 no bombardeiro.. temos um limite de 9

${\displaystyle T,B\geq 0}$

Perceba que não é possível resolver este modelo. Não existe nenhuma informação que limite superiormente o número de bombardeiros que temos disponíveis. Logo, podemos simplesmente dizer que o melhor é atacar com infinitos bombardeiros. Isso é um absurdo. É uma solução inconcebível. Modelos com solução infinita costumam ocorrer quando algum tipo de restrição é omitida do modelo.

---

3. Isso acrescenta uma nova restrição ao modelo:

${\displaystyle B\leq 5}$

Agora sim podemos resolver o modelo. Tente desenhar o gráfico do Domínio desta função-objetivo. Ele gera um triângulo com três vértices. A resposta é que devemos enviar 4 tanques e 5 bombardeiros para que causemos em média 330 baixas no inimigo.