% Dicas: 
%  - Gera arquivo com paginas especificas em PS
%        psselect -p3-13 corpo.ps pg3-13.ps
%  - Colocar duas paginas numa de 'letter'
%    pstops 2:0L@.7(21.6cm,0)+1L@.7(21.6cm,14.85cm) infile outfile -> NAO funcionou
%    psnup -pletter -Pletter -s0.6 -2 infile outfile

\documentclass[11pt,oneside]{article}  %{book}

\pagestyle{myheadings} % para fazer, no relat, um cabeçalho

\renewcommand{\sectionmark}{
    \markboth{{\bf MAC 315 - 2000 \ --- \ Exemplo: direções viáveis \ \hrulefill \ }}
    }

\usepackage[brazil]{babel}     % hifenação em português e
                               % tradução de títulos como `References'
                               % inclui o portuges.sty

\usepackage[latin1]{inputenc}  % `traduz' os acentos do portug
%\usepackage[epfs]{graphicx}
%\usepackage{makeidx}          % para fazer indices
\usepackage{amssymb}           % para carregar fontes tipo R com duas pernas
\usepackage{latexsym}          % Para ter coisas como o \Box.
%\usepackage{amscd}            % Ainda nao sei pra que isso, mas precisa,
                               % caso contrario da' erro em labels.

\setlength{\textwidth}{19cm}         %largura da pagina
\setlength{\textheight}{26cm}        %profundidade da pagina
\setlength{\topmargin}{-2cm}         %margem superior
\setlength{\oddsidemargin}{-1cm}     %margem esquerda
%\setlength{\evensidemargin}{-0.5cm} %magem direita
\setlength{\parskip}{.2cm}           %definir distancia entre linhas
\setlength{\parindent}{0cm}          %definir "indentacao" nos paragrafos
\setlength{\itemindent}{0.3cm}       %definir "indentacao" nos itens
\setlength{\columnsep}{.4cm}
\setlength\columnseprule{.4pt}
\setlength{\abovedisplayskip}{0cm}   %{-0.3cm} nao funciona
\setlength{\belowdisplayskip}{0cm}   %{-0.3cm} nao funciona
%\setlength{\abovedisplayshortskip}{0.2cm} 
%\setlength{\belowdisplayshortskip}{0.2cm} 

% Para fazer indices:
% - incluir no arquivo, fora do <document> (vai gerar um xxxxxx.idx): \makeindex
% - no prompt fazer: makeindex -o xxxxxx.ind xxxxxx.idx
% - dentro do <document>: \input{xxxxxx.ind}
%\makeindex


% Símbolos -------------------------------------------------------------------

\def\R{{\rm I\kern -0.2 em R}}
\def\nat{{\rm I\kern -0.2 em N}}
\def\maiorig{\stackrel{>}{{}_{=}}}
\def\menorig{\stackrel{<}{{}_{=}}}
\def\maiorigm{\:\,\_\kern -0.47 em {\_\kern -0.32 em ^{\succeq}}\:}
%\def\maiorigm{\succeq}
\def\menorigm{\:\,\_\kern -0.47 em {\_\kern -0.32 em ^{\preceq}}\:}
\def\subsetneq{\subset{\kern -0.32cm {}_{{}_{\not=}}}}

\renewcommand{\P}{{\sf (P)}}
\newcommand{\D}{{\sf (D)}}

% Abreviações ----------------------------------------------------------------

\newcommand{\sse}{\hbox{$\Leftrightarrow$}}
\newcommand{\Sse}{\hbox{$\Longleftrightarrow$}}
\newcommand{\ov}{\overline}

% Vetores --------------------------------------------------------------------

\newcommand{\Vzero}{     { 0 \kern -0.4    em  0 }}   %{\hbox{$0$\kern -0.4 em $0$}}
\newcommand{\V}[1] {\hbox{$#1$\kern -0.48  em $#1$}} 


% Matrizes -------------------------------------------------------------------

\newcommand{\Mzero}{{\bf O}}
\newcommand{\M}[1]{{{\sf\bf #1}}}


% Macros ---------------------------------------------------------------------

\newcommand{\prova}{\noindent {\bf Demonstração }}
\newcommand{\fimteo} { \ \hfill $\rule{2mm}{2mm}$} % \vspace{.4cm} }
\newcommand{\fimex}  { \ \hfill $\Box$}            %

\newcommand{\autor}[1]{\index{#1}{\sf #1}}
\newcommand{\palavra}[1]{\index{#1}{\sc #1}}

\newcommand{\formula}[2]{
 \noindent
 \parbox[h]{16cm}{{\bf #1}\ {#2}}
 }


%\setcounter{chapter}{2}
%\setcounter{section}{2}

\newtheorem{teo}{Teorema}[section] %teor. e' numerado por capitulo
\newtheorem{lema}{Lema}[section]
\newtheorem{define}{Definição}     %numeracao unica p/ o texto todo
\newtheorem{cor}{Corolário}[section]
\newtheorem{exerc}{Exercício}[section]  %analogo por secao
\newtheorem{ex}{Exemplo}    
\newtheorem{obs}{Observação}
% macro para impressao de data-hora, basta fazer
%       \tempo

\newcount\hora
\def\tempo{\number\day\ de 
          {\ifcase\month\or
           janeiro\or fevereiro\or mar\c{c}o\or abril\or maio\or junho\or
           julho\or agosto\or setembro\or outubro\or novembro\or
           dezembro\fi}
          de \number\year\ \hora=\time \divide\hora by 60
          \relax\the\hora:\multiply\hora by -60 \advance\hora by \time 
          \ifnum\hora<10{0}\fi\the\hora}  


%\input{epsf}

\begin{document}

\section*{MAC 315 - 2000 / Resolução - Exercício 2.10}

%\begin{center}
%\palavra{Resolucao - Exercício 2.10}
%\end{center}

Segue abaixo a resolução do exercício 2.10 do texto do Professor Carlos Humes e
da Professora Ana Flora.

\begin{enumerate}

\newcommand{\vz}{\times}

\vspace{-0.2cm}
\item[(i)]
        
     Por inspec\~ao, temos: $\ov{\V{x}}:=(1;1;1;1;0)$, $\ov{\V{h}}:=(1;-5;-1;5;0)$ e
     \vspace{-0.3cm}
     \begin{center}
     $\M{A}\ov{\V{h}}:=\left(\begin{array} {cccccc}
                1 & 0 & 1 & 0 & -10\\
                0 & 1 & 0 & 1 & 5  \\
                \end{array}
        \right) \left(\begin{array} {c}
                1 \\ -5 \\ -1 \\ 5 \\ 0
                \end{array} \right)=$ % \\
                $\left(\begin{array} {c}
                1\vz 1 + (-5)\vz 0 + (-1)\vz 1 + 5\vz 0 + (-10)\vz 0 \\
                0\vz 1 + (-5)\vz 1 + 0\vz (-1) + 1\vz 5 + 5\vz 0
                \end{array} \right)=
                \left(\begin{array} {c}
                0 \\ 0
                \end{array} \right)$
     \end{center}

     \vspace{-0.5cm}
     \'E de f\'acil verificac\~ao que $\ov{\V{h}}\not=\Vzero$ e que
     % $\{x_i\}_{i=1}^{4} \neq 0$ e que $\{h_i\}_{i=1}^{4} \neq 0$. 
     $I(\ov{\V{h}}) \subseteq I(\ov{\V{x}})$.

\item[(ii)]
  A intersecc\~ao da reta L com o poliedro X ser\'a o segmento de reta:
  \vspace{-0.3cm}
  \begin{center}
  $L=(1,1,1,1,0)^T+ \lambda (1,-5,-1,5,0)^T$, $\lambda \in
  [\lambda_-,\lambda_+]$
  \end{center}

  \vspace{-0.3cm}
  Temos que encontrar os valores $\lambda_-$ e $\lambda_+$ que garantam
  que continuemos dentro do poliedro. Para tanto, basta lembrar que nao
  devem existir coordenas negativas em qualquer $\V{x}$ pertencente ao poliedro.

  Deste modo, para $ \lambda\in\R$, devemos ter que:
  $\forall \V{y}\in L \cap X$, \ 
  $\V{y}  = \ov{\V{x}} + \lambda \ov{\V{h}} \maiorig \Vzero$, \ ou seja,

  \vspace{-0.5cm}
  \begin{eqnarray}\label{eq:1}
  1+\lambda \maiorig 0  & \Longrightarrow & \lambda \maiorig -1 \\ \label{eq:2}
  1-5\lambda \maiorig 0 & \Longrightarrow & \lambda \menorig \frac{1}{5} \\\label{eq:3}
  1-\lambda \maiorig 0  & \Longrightarrow & \lambda \menorig 1 \\\label{eq:4}
  1+5\lambda \maiorig 0 & \Longrightarrow & \lambda \maiorig \frac{-1}{5} 
  \end{eqnarray}
  \vspace{-0.5cm}

  Sendo assim, qualquer $\lambda \in [\frac{-1}{5},\frac{1}{5}]$ serve.

\item[(iii)]
   Para encontrar um $\V{y}\in L \cap X$, tal que $\#I(\ov{\V{x}})<\#I(\V{y})$,
   tomar $\lambda=1/5$ (ou  $\lambda=-1/5$):

   \begin{center}
   $\V{y} := \ov{\V{x}} + \frac{1}{5} \ov{\V{h}} 
           = (1,1,1,1,0)^T + \frac{1}{5} (1,-5,-1,5,0)^T
           = (1,1,1,1,0)^T+(5,-1,-5,1,0)^T
           = (\frac{6}{5},0,\frac{4}{5},2,0)^T$
   \end{center}

   Podemos observar que $\#I(\ov{\V{x}})=4 > \#I(\V{y})=3$.
   Além disso, \ $\M{A}\V{y}=(\frac{6}{5}+\frac{4}{5};2)=(2;2)=\V{b}$.\\
   Faca o mesmo utilizando $\lambda=-\frac{1}{5}$.

\item[(iv)]
   Sendo $\lambda \in [\frac{-1}{5},\frac{1}{5}]$, suponha que exista
   um segmento de reta $\lambda^{*}_{+} > \lambda_{+} = \frac{1}{5}$. \\ 
   Substituindo $\lambda^{*}_{+}$ na equação (\ref{eq:2}), teremos 
   $1-\lambda<0$. Verificamos que uma das componentes
   ser\'a negativa no vetor $\ov{\V{y}}+\lambda\ov{\V{h}}$ e, portanto, um ponto
   fora do poliedro.  De modo an\'alogo, podemos considerar
   $\lambda^{*}_{+}<\frac{-1}{5}$ na equação (\ref{eq:4}).  Chegaremos a
   mesma conclus\~ao e $\lambda$ obrigatoriamente dever\'a pertencer ao
   intervalo $[\frac{-1}{5}, \frac{1}{5}]$.  

\end{enumerate}

Este exercício nos mostra que, quando um ponto do poliedro canônico {\bf não} é
vértice, podemos escolher uma {\em direção viável} $\ov{\V{h}}\not=\Vzero$ 
($\ov{\V{x}} + \lambda\ov{\V{h}}$ não sai do poliedro, para $\lambda$
 conveniente).
Ao escolhê-la, podemos percorre um segmento de reta definido 
pelos valores de $\lambda_-$ e $\lambda_+$ (no caso de semi-reta, apenas um
deles será finito) e deste modo
``encostaremos'' em um dos hiperplanos que define o poliedro.
Um tal ponto de intersecção, é ``mais próximo'' de ser um vértice (tem mair
número de componentes nulas).


\begin{exerc}
  Considere o seguinte problema de programação linear:
 
 \vspace{-0.5cm}
 \[
 \begin{array}{lccc}
                \max 2x_{1}+x_{2} \\
  \hbox{sujeito a:} & x_2 & \menorig & 2 \\
                    & x_1+x_2 & \menorig & 2 \\
                    & x_1-x_2 & \menorig & 4 \\
                    & {x_1},{x_2}& \maiorig \Vzero.
 \end{array}
 \]

\vspace{-0.5cm}
\begin{enumerate}

\item[(a)] { Transcreva o problema para a forma canônica;}

\item[(b)] { Encontre uma direção viável $\V{h}$ e o segmento de reta (ou semi-reta)
 associado a direção;}

\item[(c)] { Repita os passos do exercício 2.10 e verifique que, ao andarmos na
 direção $\V{h}$, estamos encontrando um candidato a vértice - um ponto viável
 com um número maior de componentes nulas.  }
\end{enumerate}

\end{exerc}

\end{document}









