Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Qual o maior disco inscrito em um polígono convexo?

0 votos
18 visitas
perguntada Nov 19 em Matemática por Stuart Mill (504 pontos)  

Enuncie, explique e ressalte a importância do problema. Apresente a solução do problema usando programação linear. Dê um exemplo e use uma biblioteca de programação linear do python para resolvê-lo computacionalmente.

Compartilhe

1 Resposta

+1 voto
respondida Nov 19 por Stuart Mill (504 pontos)  
editado Nov 29 por Stuart Mill
  • Seja P um polígono convexo como na imagem abaixo. Queremos encontrar o maior disco contido em P.

A imagem será apresentada aqui.

  1. Vamos definir o problema da seguinte forma: existem n linhas no \( \mathbb{R}^2\) e a região convexa delimitada por essas linhas constitui o polígono convexo P. Cada linha tem a equação genérica \(a_i x + b_i y + c_i = 0 \), com vetor normal \(n=(a_i ,b_i ) \) associado.

I - A importância do problema

O problema pode ser o de empacotar o maior número possível de objetos em um determinado recipiente. Como exemplos, poderíamos citar a maior quantidade de determinado alimento que cabe dentro de uma embalagem e a maior peça de roupa que pode ser feita a partir de um pedaço de tecido.

Do ponto de vista econômico, o problema poderia ser também o de construir uma usina nuclear ou lixão o mais longe possível da população (representada pelo polígono). Ou até mesmo de um vendedor que quer se colocar o mais longe possível de seus concorrentes em uma praça, de modo a se tornar um monopolista da região.


II - Solução Analítica

Seja \( s = (s_1, s_2) \) o centro do círculo de raio \( r\).

  • Queremos o maior raio tal que a distância entre o centro do círculo e cada um dos lados do polígono seja maior ou igual a esse raio. Portanto, primeiro precisamos de uma expressão para essa distância.
  • Seja \( Q = (x_1, x_2 )\) um ponto qualquer na linha \(a_i x + b_i y + c_i = 0 \), com vetor normal \(n=(a,b) \) e \( s = (s_1, s_2) \) o centro do círculo. O vetor \( Qs\) que parte de Q para s é dado por \( Qs = (s_1 - x_1, s_2 - x_2)\), e a distância d entre a linha e o centro do círculo será dada pela norma da projeção ortogonal de Qs sobre o vetor normal. Portanto:

\( d =\frac{|a_i(s_1 - x_1) + b_i(s_2 - x_2)|}{\sqrt{{a_i }^2 + {b_i} ^2}} = \frac{|a_i s_1 + b_i s_2 + c_i|}{\sqrt{{a_i }^2 + {b_i} ^2}} \because c_i = -a_i s_1 - b_i s_2 \)

\( r \le d \implies r \le \frac{|a_i s_1 + b_i s_2 + c_i|}{\sqrt{{a_i }^2 + {b_i} ^2}} \)

Portanto:

\( r \le \frac{a_i s_1 + b_i s_2 + c_i}{\sqrt{{a_i }^2 + {b_i} ^2}}\) se \( \ge 0\)
\( \frac{a_i s_1 + b_i s_2 + c_i}{\sqrt{{a_i }^2 + {b_i} ^2}}\le -r \) se \( \le 0\)

  • O programa pode, enfim, ser definido na forma linear como:

\( \max r \)

s.a.
\( r \le \frac{a_i s_1 + b_i s_2 + c_i}{\sqrt{{a_i }^2 + {b_i} ^2}}\) [se \( \ge 0\)]
\( \frac{a_i s_1 + b_i s_2 + c_i}{\sqrt{{a_i }^2 + {b_i} ^2}}\le -r \) [se \( \le 0\) ]

A solução ótima deve retornar os valores para as 3 variáveis de interesse, definindo assim o círculo inscrito. No exemplo abaixo discutirei melhor como caracterizar melhor o programa para cada situação.

Obs.: A solução apresentada aqui é mais geral que a do livro do Matousek e Gartner(Understanding and Using Linear Programming - Jiri Matousek and Bernd Gärtner), sobre o qual eu me baseei. Aqui, eu permito que qualquer linha limite o polígono (inclusive linhas verticais).

III - Um exemplo numérico

Considere o polígono convexo definido como anteriormente pelas seguintes equações:

\( 3x - 4y - 2 = 0\) [R1]
\( 4x + 3y - 12 = 0\) [R2]
\( y - 3x = 0\) [R3]
\( x - 0,25 = 0\) [R4]

  • Como definir o programa a partir dessas restrições? É possível interpretar esse problema da seguinte forma: inicialmente, por envolver a minimização de distâncias (que são funções não lineares), se poderia pensar que o problema só é resolvível por métodos de programação não linear. No entanto, com a transformação que fizemos, classificando as restrições em positivas ou negativas, contornamos esse problema e chegamos a um programa de fato linear. O custo disso, em contrapartida, é que devemos ser capazes de classificar corretamente as restrições em positivas ou negativas. Vejamos:

    A imagem será apresentada aqui.

  • Imaginando um centro de referência no ponto \( (1,1) \), o polígono é facilmente identificado por 4 linhas que o limitam:

1) Noroeste: Equação \( y = 3x\) e distância \( \frac{-3s_1 + s_2}{\sqrt{10}} \)
A equação a noroeste tem distância nula ao longo da própria linha. Ao caminharmos em direção ao centro de referência, tanto x quanto y diminuem. Portanto, a expressão da distância se torna certamente negativa. Logo, para esse caso a restrição é:
(Ra) \( \frac{-3s_1 + s_2}{\sqrt{10}} \le -r\)

2) Nordeste: Equação \( 4x + 3y - 12 = 0\) e distância \( \frac{4s_1 + 3s_2 -12}{5} \)
Pelo mesmo argumento anterior, conforme nos deslocamos em direção a esse centro de referência, tanto x quanto y diminuem, e portanto a expressão da distância se torna negativa. Logo, para esse caso a restrição é:

(Rb) \( \frac{4s_1 + 3s_2 -12}{5} \le -r \)

3) Sudoeste: Equação \( x = 0.25 \) e distância \(s_1 - 0.25\). Claramente, ao nos movermos para a direita na direção do centro de referência, a expressão de distância se torna positiva. Logo, para esse caso a restrição é:

(Rc) \(s_1 - 0.25 \ge r \)

4) Sul/Sudeste : Equação \(3x - 4y -2 = 0 \) e distância \( \frac{3s_1 -4s_2 -2}{5} \). A restrição cobre toda a parte inferior do polígono, e portanto a coordenada x não é de interesse aqui. No entanto, ao nos deslocarmos para o centro de referência, a coordenada y aumenta, e a expressão de distância se torna negativa. Logo:

(Rd) \( \frac{3s_1 -4s_2 -2}{5} \le -r\)

  • Portanto, o programa fica finalmente definido apropriadamente como:

\( \max r\)

s.a. Ra, Rb, Rc e Rd

  • Usando o Maple 13 (código no fim), os resultados são:
    \(r\) = 0.708781168963406704
    \( s_1 \) = 1.16770636345123036
    \(s_2 \) = 1.26175623379268132

O resultado pode ser visualizado no gráfico abaixo.

A imagem será apresentada aqui.

Obs.: Acredito que outra solução possível para a formulação do problema seria a de força bruta, testando todas as combinações de restrições e analisando as que dessem raios positivos e soluções interiores.

Código:

with(Optimization):
with(plottools):
with(plots):

r1 := inequal({x-.25 >= 0, y <= 3*x, 3*x-4*y <= 2, 4*x+3*y <= 12}, x = -3 .. 3, y = -3 .. 5, optionsfeasible = (color = blue), optionsclosed = (color = green), optionsclosed = (color = red), optionsexcluded = (color = white));

display(r1)

LPSolve(r, {s[1]-.25 >= r, (-3*s[1]+s[2])/sqrt(10) <= -r, (3*s[1]-4*s[2]-2)*(1/5) <= -r, (4*s[1]+3*s[2]-12)*(1/5) <= -r}, maximize)

d1 := disk([1.16770636345123036, 1.26175623379268088], .708781168963406926, color = yellow)

display(d1, r1)
comentou Dez 1 por MarcioGama (96 pontos)  
Bernardo, ótima resolução.  Achei muito interessante a forma de resolver. Se tiveres interesse, segue abaixo resolução do problema em python.

import numpy as np
from pulp import *
import matplotlib.pyplot as plt

def restr1(x): return (-2 + 3*x)/4
def restr2(x): return (12 - 4*x)/3
def restr3(x): return 3*x

x = np.linspace(-3,3,100)

prob = LpProblem("Polígono", LpMaximize)

s1 = LpVariable('s1', 0, None)
s2 = LpVariable('s2',0, None)
r = LpVariable('r',None, None)

prob += r

prob += (-3*s1 + s2)/np.sqrt(10) <= -r
prob += (4*s1 + 3*s2 - 12)/5 <= -r
prob += s1 - 0.25 >= r
prob += (3*s1 - 4*s2 - 2)/5 <= - r

prob.solve()

resultado = [r.varValue, s1.varValue, s2.varValue]

fig = plt.figure(1, figsize=(7,7), frameon=False, dpi=100)
ax = plt.gca()
circle = plt.Circle((resultado[1], resultado[2]), resultado[0], color = 'y', alpha = .5)
ax.add_artist(circle)
plt.plot(x, restr1(x), color = 'r')
plt.plot(x,restr2(x), color = 'r')
plt.plot(x,restr3(x), color = 'r')
plt.plot([0.25, 0.25], [-10,10], color = 'r')

plt.show()


Aqui o resultado que encontrei:

[0.70878117, 1.1677064, 1.2617562]

Abraços
comentou 6 dias atrás por Stuart Mill (504 pontos)  
Obrigado pela contribuição, Márcio, creio que será muito bom ter a referência em Python para o futuro! Abraço.
...