Mestrado em Engenharia Civil - UFF

Trabalho de Teoria da Decisão

Instruções

Abaixo são descritos 3 problemas de otimização linear para ser estudado pela dupla/trio.

Cada dupla deverá realizar as seguintes tarefas:

1- Apresentar o modelo completo seguindo os passos apresentados na disciplina: critério de otimalidade, definir precisamente as variáveis de decisão, escrever matematicamente a função objetivo e as restrições.

2- Aplicar o método gráfico para solucionar o problema

3- Aplicar o algoritmo simplex para solucionar o problema, apresentando todos os passos e todo o processo de cálculo.

4- Utilizar as soluções de cada iteração do algoritmo simplex mostrando no gráfico a estratégia do algoritmo, ou seja, de que ponto partiu, para onde foi até chegar ou não na solução ótima.

5- Pesquisar o procedimento de análise de sensibilidade e aplicá-la ao problema.

6- Produzir um relatório com todo o procedimento destas tarefas, mostrando de forma didática os passos, apontamentos, análises contextualizadas ao problema e conclusões. A entrega deverá ocorrer até o dia 18/07/2023, enviada ao email da profa em arquivo único contendo o nome da equipe, o problema e as tarefas organizadas adequadamente por seção no arquivo.

Critério de Avaliação

Importante: A aprovação na disciplina está condicionada a entrega do trabalho no prazo combinado.

A pontuação máxima deste trabalho foi estabelecida em concordância com a turma e será utilizada apenas aos que cumprirem com a entrega.

Os critérios para avaliação das tarefas serão:

Tarefa 1: A tarefa será avaliada conforme os seguintes critérios:

Correção: O modelo apresentado deve estar correto e coerente com os dados e o objetivo do problema.

Clareza: O modelo apresentado deve estar claro e bem organizado, usando símbolos e expressões matemáticas adequadas.

Completude: O modelo apresentado deve conter todos os elementos necessários: critério de otimalidade, variáveis de decisão, função objetivo e restrições.

Tarefa 2: A tarefa será avaliada conforme os seguintes critérios:

Correção: O gráfico apresentado deve estar correto e coerente com o modelo do problema.

Clareza: O gráfico apresentado deve estar claro e bem desenhado, usando escalas e legendas adequadas.

Completude: O gráfico apresentado deve conter todos os elementos necessários: eixos das variáveis de decisão, retas das restrições, região viável, reta da função objetivo e ponto ótimo.

Tarefa 3: A tarefa será avaliada conforme os seguintes critérios:

Correção: O algoritmo simplex apresentado deve estar correto e coerente com o modelo do problema.

Clareza: O algoritmo simplex apresentado deve estar claro e bem organizado, usando notações e cálculos adequados.

Completude: O algoritmo simplex apresentado deve conter todos os passos necessários: colocação na forma padrão, montagem da estrutura matricial e seu particionamento, verificação da otimalidade, escolha das variáveis de entrada e saída, realização das operações elementares e obtenção da solução ótima.

Tarefa 4: A tarefa será avaliada conforme os seguintes critérios:

Correção: O gráfico apresentado deve estar correto e coerente com o algoritmo simplex do problema.

Clareza: O gráfico apresentado deve estar claro e bem desenhado, usando escalas e legendas adequadas.

Completude: O gráfico apresentado deve conter todos os elementos necessários: eixos das variáveis de decisão, retas das restrições, região viável, reta da função objetivo e pontos correspondentes às soluções básicas de cada iteração do algoritmo simplex.

Tarefa 5: A tarefa será avaliada conforme os seguintes critérios:

Correção: A análise de sensibilidade apresentada deve estar correta e coerente com o modelo e a solução ótima do problema.

Clareza: A análise de sensibilidade apresentada deve estar clara e bem organizada, usando fórmulas e procedimentos adequados.

Completude: A análise de sensibilidade apresentada deve conter todos os elementos necessários: identificação dos parâmetros a serem analisados, aplicação das fórmulas ou procedimentos para cada tipo de análise, interpretação dos resultados e conclusões sobre a estabilidade da solução ótima e o valor ótimo.

Os problemas

Aqui estão os de problemas de otimização linear aplicados à gestão na engenharia civil contendo duas variáveis de decisão:

Problema 1:

Dupla: André e Bernardo

Uma empresa de construção civil deseja maximizar o lucro obtido com a venda de dois tipos de apartamentos: A e B. Cada apartamento do tipo A ocupa 80 m² e custa R$ 200.000,00 para ser construído. Cada apartamento do tipo B ocupa 100 m² e custa R$ 250.000,00 para ser construído. A empresa dispõe de um terreno de 4000 m² e um orçamento de R$ 10.000.000,00. Além disso, a demanda por apartamentos do tipo A é de no máximo 40 unidades e a demanda por apartamentos do tipo B é de no máximo 30 unidades. O preço de venda de cada apartamento do tipo A é de R$ 300.000,00 e o preço de venda de cada apartamento do tipo B é de R$ 400.000,00.

Problema 2:

Dupla: Antonio e Ana Paula

Problema 2: Uma empresa de engenharia civil precisa decidir quais materiais deve comprar para uma obra, considerando os custos e as qualidades dos materiais. A empresa tem dois tipos de materiais: concreto e aço. Cada metro cúbico de concreto custa R$ 100,00 e tem uma qualidade de 80 pontos. Cada tonelada de aço custa R$ 500,00 e tem uma qualidade de 90 pontos. A empresa dispõe de no máximo R$ 10.000,00 para comprar os materiais e precisa de no mínimo 60 metros cúbicos de concreto e 10 toneladas de aço. A empresa deseja maximizar a qualidade média dos materiais comprados.

Problema 3:

Trio: Andrew, Valéria e Renata

Uma empresa de engenharia civil precisa decidir quanto investir em dois tipos de projetos: residenciais e comerciais para maximizar seu retorno financeiro. Cada projeto residencial requer um investimento de R$ 100.000,00 e gera um retorno de R$ 150.000,00. Cada projeto comercial requer um investimento de R$ 200.000,00 e gera um retorno de R$ 300.000,00. A empresa tem um capital disponível de R$ 1.000.000,00 e uma capacidade máxima de executar 8 projetos no total. Além disso, a empresa deve respeitar a seguinte política: o número de projetos residenciais deve ser pelo menos igual ao número de projetos comerciais.

Dicas

Aqui estão algumas dicas e orientações para cada tarefa:

Tarefa 1: Para apresentar o modelo completo, você deve seguir os seguintes passos:

Identificar o critério de otimalidade, ou seja, se o problema é de maximização ou minimização da função objetivo. Definir precisamente as variáveis de decisão, ou seja, as quantidades que devem ser determinadas pelo modelo e que afetam a função objetivo e as restrições. As variáveis de decisão devem ser representadas por símbolos (como x, y, z) e ter uma unidade de medida (como metros, toneladas, reais). Escrever matematicamente a função objetivo, ou seja, a expressão que representa o valor que se deseja maximizar ou minimizar em função das variáveis de decisão. A função objetivo deve ser linear, ou seja, uma combinação linear das variáveis de decisão com coeficientes constantes. Escrever matematicamente as restrições, ou seja, as expressões que representam as limitações impostas ao problema em função das variáveis de decisão. As restrições devem ser lineares e ter a forma de desigualdades (<= ou >=) ou igualdades (=). Além disso, deve-se incluir as restrições de não-negatividade das variáveis de decisão (>= 0).

Tarefa 2: Para aplicar o método gráfico para solucionar o problema, você deve seguir os seguintes passos:

Verificar se o problema tem apenas duas variáveis de decisão. Se tiver mais do que duas, o método gráfico não pode ser aplicado (no entando os problemas propostos foram formulados para terem duas variáveis, então reveja sua modelagem!). Desenhar um sistema de coordenadas cartesianas com os eixos representando as variáveis de decisão. Representar graficamente cada restrição como uma reta no plano cartesiano, usando os coeficientes das variáveis de decisão como inclinação e termo independente. A região viável do problema é a região delimitada pelas retas que satisfaz todas as restrições. Representar graficamente a função objetivo como uma reta no plano cartesiano, usando os coeficientes das variáveis de decisão como inclinação e um valor arbitrário para o termo independente. A solução ótima do problema é o ponto da região viável que maximiza ou minimiza a função objetivo. Para encontrar esse ponto, deve-se mover a reta da função objetivo paralelamente a si mesma até atingir o último ponto da região viável na direção do critério de otimalidade.

Tarefa 3: Para aplicar o algoritmo simplex para solucionar o problema, você deve seguir os seguintes passos:

Colocar o problema na forma padrão, ou seja, transformar todas as restrições em igualdades (=) introduzindo variáveis de folga (s) ou excesso (e) para cada restrição. A forma padrão do problema é:

Minimizar: \(Z = c_1 x_1 + c_2 x_2 + ... + c_n x_n\)

Sujeito a:

\(a_11 x_1 + a_12 x_2 + ... + a_1n x_n + s_1 = b_1\)

\(a_21 x_1 + a_22 x_2 + ... + a_2n x_n + s_2 = b_2\)

…

\(a_m1 x_1 + a_m2 x_2 + ... + a_mn x_n + s_m = b_m\)

\(x_i \>= 0, s_j \>= 0\), para \(i = 1,...,n\) e \(j = 1,...,m\)

Onde:

\(Z\) = valor da função objetivo

\(x_i\) = variável de decisão i

\(c_i\) = coeficiente da variável de decisão i na função objetivo

\(a_{ij}\) = coeficiente da variável de decisão i na restrição j

\(s_j\) = variável de folga ou excesso da restrição j

\(b_j\) = termo independente da restrição j

Escrever a forma matricial do Simplex, realizar o particionamento, aplicando os passos dentro de cada iteração até atingir uma das regras de parada do algoritmo.

Em cada iteração atentar para: Escolha da variável que entra na base, escolha da variável que sai da base, ou seja, a variável básica que tem o menor quociente chamado de tamanho de passo mínimo.

Tarefa 4: Para utilizar as soluções de cada iteração do algoritmo simplex mostrando no gráfico a estratégia do algoritmo, você deve seguir os seguintes passos:

Desenhar um sistema de coordenadas cartesianas com os eixos representando as duas variáveis de decisão do problema. Representar graficamente cada restrição como uma reta no plano cartesiano, usando os coeficientes das variáveis de decisão como inclinação e termo independente. A região viável do problema é a região delimitada pelas retas que satisfaz todas as restrições. Representar graficamente a função objetivo como uma reta no plano cartesiano, usando os coeficientes das variáveis de decisão como inclinação e um valor arbitrário para o termo independente. A solução ótima do problema é o ponto da região viável que maximiza ou minimiza a função objetivo. Para cada iteração do algoritmo simplex, marcar no gráfico o ponto correspondente à solução básica atual, indicando as coordenadas das variáveis básicas e o valor da função objetivo. Mostrar também a direção do movimento da reta da função objetivo até atingir o próximo ponto da região viável na direção do critério de otimalidade.

Tarefa 5: Para pesquisar o procedimento de análise de sensibilidade e aplicá-la ao problema, você deve seguir os seguintes passos:

Pesquisar em livros, artigos ou sites sobre o conceito e a metodologia da análise de sensibilidade em problemas de programação linear. A análise de sensibilidade consiste em estudar como as mudanças nos dados do problema (coeficientes da função objetivo, termos independentes das restrições, coeficientes das restrições) afetam a solução ótima e o valor ótimo do problema.