\chapter{Programação Linear}
\label{cap:proglinear}

Segundo Luenberger e Ye~(2016), um programa linear é um problema de otimização no qual a função objetivo é linear nas incógnitas e as restrições consistem de equações e inequações lineares. 
%Analisando o nome verificamos que "programação" é "organização" e "linear" nos deixa a ideia de que as expressões matemáticas a serem utilizadas serão funções lineares. 

%Ao concluir que os problemas de otimização sempre possuirão ao menos uma solução, o próximo passo natural do processo é saber então, qual é a sua solução ótima. Nesta esteira, procuramos um conjunto de técnicas capazes de solucionar modelos de otimização. Uma ferramenta é a Programação Linear.

A programação linear tem aplicabilidade em variadas e grandes áreas. Por exemplo, por governos para a tomada de decisões de aplicabilidade de impostos, por hidroelétricas para o aproveitamento máximo dos seus recursos, pelas fábricas ao planejarem o recebimento e a distribuição de mercadorias e pelas empresas de aviação na definição da malha aérea. Os resultados obtidos influenciam na alocação de verbas e material humano, na localização industrial e ainda na composição da tabela de horários.

Não há uma técnica específica a ser utilizada para que se chegue a uma modelagem de um dado problema. Tanto a função objetivo quanto suas restrições serão arquitetadas de acordo com o conhecimento a respeito do assunto em questão. Contudo, Luenberger e Ye~(2016) formalizam que todo problema de programação linear, pode ser reduzido à seguinte forma:

%\begin{align}
%\textbf{Minimizar} f(x_{1},x_{2},\ldots,x_{n}) = c_1x_1 &+ c_2x_2+\ldots +c_nx_n \label{fun:obj}\\
%a_{11}x_1+a_{12}x_2+\ldots +a_{1n}x_n &= b_1 \nonumber \\
%a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n &= b_2 \nonumber \\
%&\vdots \\
%a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n &= b_m \nonumber \\
%x_1\geq0, x_2\geq0,\ldots,x_n &\geq 0
%\end{align}

\begin{equation}\label{fun:obj}
	\begin{aligned}[t]
		\minimizar\: & f(x_1,x_2,\ldots,x_n) = c_{1}x_{1}+c_{2}x_{2}+\ldots+c_{n}x_{n} \\
		\operatorname{s.a.}\: &
		\begin{aligned}[t]
			&a_{11}x_{1} + a_{12}x_{2} + \ldots + a_{1n}x_{n} =  b_{1}\\
			&a_{21}x_{1} + a_{22}x_{2} + \ldots + a_{2n}x_{n} =  b_{2}\\
			&\qquad\qquad\qquad\vdots\\
			&a_{m1}x_{m} + a_{m2}x_{m} + \ldots + a_{mn}x_{n} =  b_{m}\\
			&x_{1}+x_{2}+\ldots +x_{n}  = 1\\
			&x_{1}\geq0, x_{2}\geq0,\ldots,x_{n} \geq 0
		\end{aligned}
	\end{aligned}
\end{equation}



Sendo a função linear $f$ em~\eqref{fun:obj}, a chamada \emph{função objetivo}, as equações as quais $ f $ está sujeita são as \emph{restrições do problema}, e por fim, temos as \emph{condições de não-negatividade} das variáveis. Esta forma padrão, também pode ser escrita da seguinte maneira:
\begin{align*}
\minimizar f(\mathbf{x}) &= \mathbf{c}^{T}\mathbf{x}\\
\mathbf{A}\mathbf{x} &= \mathbf{b}\\
\mathbf{x} &\geq \mathbf{0},
\end{align*}

