\documentclass[10pt,twocolumn]{article}
%
\usepackage{cite} %πακέτο για βιβλιογραφία
%
\usepackage[utf8]{inputenc}
\usepackage[english,greek]{babel}
\usepackage{alphabeta}
\usepackage{amsmath}
\usepackage{textgreek} %για εισαγωγή ελληνικών συμβόλων εκτός κειμένου 
\usepackage{amsthm}
\usepackage{IEEEtrantools} %πακέτο για στοίχιση εξισώσεων
\usepackage{mdframed} %πακέτο για εισαγωγή πλαισίων
\usepackage{fancybox}
% \usepackage{biblatex}
%\DeclareLanguageMapping{english}{greek}
%\addbibresource{mybiblio.bib}
%
\usepackage{graphicx} %πακέτο για εισαγωγή εικόνων
%
\usepackage[table,dvipsnames]{xcolor}
\usepackage[colorlinks,linkcolor=blue,citecolor=cyan,urlcolor=green,unicode]{hyperref} %πακέτο για υπερσυνδέσμους.Μπαίνει πάντα τελευταίο ως πακέτο
%
%\theoremstyle{theorem}
%\newtheorem{theorem}{ΘΕΩΡΗΜΑ}
\newtheoremstyle{neo}{8pt}{8pt}{\rmfamily }{0pt}{\bfseries}{{\color{red}.}}{\newline}{{\color{red}\thmname{#1} \thmnumber{#2}}\thmnote{(#3)}}
\mdfdefinestyle{theorembox}{
linewidth=1.5pt,
linecolor=gray,
roundcorner=1cm,
innerleftmargin=5pt,
innerrightmargin=5pt,
innertopmargin=5pt,
innerbottommargin=6pt,
backgroundcolor=blue!5,
} %ορίζουμε ένα στυλ mdframed με το όνομα theorembox
%\newenvironment{mytheorem}[1][]{\begin{mdframed}[style=theorembox,frametitle={\textbf{Θεώρημα \themytheorem}#1}]}{\end{mdframed}}
\theoremstyle{neo}
%\theoremstyle{definition}
\newtheorem{mytheorem}{{\color{red}ΘΕΩΡΗΜΑ}}
%
%ορισμός δύο νέων εντολών \newcommand{όνομα καινούριας εντολής}[αριθμός {} που θα δέχεται]{ορισμός εντολής}
%\newcommand{\eng}{\selectlanguage{english}}
%\newcommand{\gr}{\selectlanguage{greek}}
%έχω ορίσει δύο νέες εντολές
%
%\addto{\captionsenglish}{\renewcommand{\refname}{\textgreek{Αγγλική Βιβλιογραφία}}}
%\addto{\captionsgreek}{\renewcommand{\refname}{\textgreek{Ελληνική Βιβλιογραφία}}}
%
\title{Επιχειρησιακή Έρευνα: Η συμβολή των μαθηματικών στον γραμμικό προγραμματισμό και οι σύγχρονες εφαρμογές του}
\author{Παύλος Μαργαρίτης\\ Τμήμα Μαθηματικών, Πανεπιστήμιο Ιωαννίνων}
\date{\today}
%
\begin{document}
%
\renewcommand*{\familydefault}{\sfdefault} %για αλλαγή γραμματοσειράς
\definecolor{Orange1}{rgb}{1,0.85,0.5}
\maketitle
\tableofcontents
%
\section{Εισαγωγή}
\hspace{4mm}Η Επιχειρησιακή Έρευνα \textlatin{(Operational Reasearch)} είναι ο επιστημονικός κλάδος που περιλαμβάνει την ανάπτυξη και εφαρμογή επιστημονικών μεθοδολογιών
 και τεχνικών με στόχο την επίλυση προβλημάτων λήψης αποφάσεων, συνήθως υπό συνθήκες που απαιτούν την κατανομή σπάνιων παραγωγικών πόρων.
 Ο Μαθηματικός Προγραμματισμός είναι το σύνολο των μαθηματικών μεθόδων και υπολογιστικών τεχνικών (αλγορίθμων) που χρησιμοποιούνται για την επίλυση μιας
 ειδικής κατηγορίας προβλημάτων, των προβλημάτων βελτιστοποίησης~\cite{2022}.
\par
 Ένα τυπικό πρόβλημα βελτιστοποίησης περιγράφεται μέσω ενός μαθηματικού μοντέλου το οποίο αποτελείται από μια πραγματική συνάρτηση της οποίας ζητείται
 το μέγιστο (ή το ελάχιστο και από μια ομάδα συνθηκών που πρέπει να ικανοποιούνται από τις μεταβλητές της συνάρτησης.
 Στην περίπτωση που η συνάρτηση αυτή και οι απαιτούμενες συνθήκες εκφράζονται από γραμμικές σχέσεις, τότε κάνουμε λόγο για πρόβλημα Γραμμικού
 Προγραμματισμού.
\par
 Στην παρούσα εργασία θα αναλύσουμε τη συμβολή των μαθηματικών στον Γραμμικό 
 Προγραμματισμό, εστιάζοντας στην ιστορική εξέλιξη και στην μοντελοποίηση ενός αντιπροσωπευτικού θεωρητικού παραδείγματος εφαρμογής στην 
 ελαχιστοποίηση του κόστους παραγωγής. Επιπλέον θα παρουσιάσουμε εφαρμογές του Γραμμικού Προγραμματισμού σε διάφορους τομείς, καταδεικνύοντας έτσι την
  σπουδαιότητα και την αποτελεσματικότητά του στην αντιμετώπιση ενός μεγάλου εύρους προβλημάτων.
\section{Βιβλιογραφική ανασκόπηση και εφαρμογές}
\subsection{Βιβλιογραφική ανασκόπηση}
Τα πρώτα βήματα στην ανάπτυξη της Επιχειρησιακής Έρευνας έγιναν από τον \textlatin{Charles Babbage}(1791-1871), του οποίου η έρευνα είχε ως αντικείμενο το 
κόστος μεταφοράς και ταξινόμησης της αλληλογραφίας.
Το 1917 ο \textlatin{Anger Krarup Erlang(1878-1929)} μελέτησε προβλήματα που αφορούν τον χρόνο απασχόλησης των τηλεφωνικών κέντρων, και το 1920 ο \textlatin{Horace Clifford 
Levinson} ασχολήθηκε με προβλήματα πωλήσεων και εμπορίου.
 Η Επιχειρησιακή Έρευνα αναπτύχθηκε ραγδαία κατά τη διάρκεια του Β΄ Παγκοσμίου Πολέμου, λόγω του καθοριστικου ρόλου της στον στρατηγικό σχεδιασμό, τον
  εφοδιασμό και την κατανομή των πόρων.\footnote{Για περισσότερα ιστορικά στοιχεία βλ.~\cite{2021}}
  Τις δεκαετίες του 1950 και 1960, αναπτύχθηκαν θεμελιώδεις αλγόριθμοι και μεθοδολογίες βασισμένοι σε μαθηματικές τεχνικές και εργαλεία, όπως η μέθοδος
   του \textlatin{Simplex}~\cite{2017}, που αφόρουν την επίλυση προβλημάτων Γραμμικού Προγραμματισμού. 
\subsection{Εφαρμογές του Γραμμικού Προγραμματισμού}
Ο Γραμμικός Προγραμματισμός έχει βρει ευρύτερες εφαρμογές σε ποικίλους τομείς~\cite{2007}, όπως:
\begin{itemize}
\item ενέργεια: βελτιστοποίηση διανομής ενέργειας, σχεδιασμός ενεργειακών δικτύων~\cite{2020}
\item γεωργία: βελτιστοποίηση χρήσης γης και καλλιεργειών~\cite{2007}
\item διαχείριση εφοδιαστικής αλυσίδας και μεταφορές: βελτιστοποίηση δρομολογίων, διαχείριση αποθεμάτων, χωροθέτηση εγκαταστάσεων.~\cite{2017}
\item οικονομικά συστήματα: βελτιστοποίηση επενδύσεων, πιστωτικές πολιτικές~\cite{2016}
\item συστήματα υγείας: κατανομή ιατρικού προσωπικού και πόρων~\cite{1999}
\end{itemize}
\section{Μαθηματική περιγραφή και θεωρητικό παράδειγμα εφαρμογής}
Στη συνέχεια θα εστιάσουμε στη μαθηματική διατύπωση του γενικού προβλήματος γραμμικού προγραμματισμού και θα παρουσιάσουμε ένα από τα πλέον σημαντικά 
θεωρητικά παραδείγματα εφαρμογής στην κατανομή πόρων.
\subsection{Διατύπωση γενικού προβλήματος γραμμικού προγραμματισμού - μοντελοποίηση}
Ένα πρόβλημα γραμμικού προγραμματισμού μπορεί να μοντελοποιηθεί γενικά ως εξής:\cite{2022}
Να μεγιστοποιηθεί (ή να ελαχιστοποιηθεί) η συνάρτηση \vspace{1mm} \\ \colorbox{Orange1}{\begin{minipage}[l][1.2\totalheight]{0.968\linewidth}$$Z=c_1x_1+c_2x_2+ \dots + c_n x_n$$\end{minipage}} 
\begin{flushleft}υπό τους περιορισμούς\end{flushleft}  
\colorbox{Orange1}{\begin{minipage}[l]{0.955\linewidth}
\begin{align*}
   a_{11}x_1 &+& a_{12} x_2 &+&\dots &+&a_{1n}x_{n} \; &\{ \leq , =, \geq \}& b{_1}\\
   a_{21}x_1 &+& a_{22} x_2 &+&\dots &+&a_{2n}x_n \; &\{ \leq , =, \geq \}& b_2\\
   &\vdots&  &\vdots& &\vdots& &\vdots& \vdots \\
   a_{m1}x_1 &+& a_{m2} x_2 &+& \dots &+&a_{mn}x_n \; &\{ \leq , =, \geq \}& b_m
\end{align*} \end{minipage} } \vspace{1mm} \\ 
Τα $a_{ij},b_i,c_j , i\in \{ 1,2,\cdots ,m \}, j\in \{1,2, \cdots , n\}$ υποθέτουμε πως είναι πραγματικές σταθερές. Θεωρούμε ότι για κάθε έναν περιορισμό
μπορεί να ισχύει μόνο μία από τις σχέσεις $\leq , = , \geq$ και υποθέτουμε τη συνθήκη μη αρνητικότητας των μεταβλητών, δηλαδή ότι $x_1\geq 0 , x_2 \geq 0, \cdots , x_n \geq 0$.
Η συνάρτηση $Z$ λέγεται αντικειμενική συνάρτηση, οι συντελεστές $c_j$ αναφέρονται ως συντελεστές κέρδους (ή κόστους για προβλήματα μεγιστοποίησης) 
και οι $z_1 , x_2 , \cdots , x_n$ ως συντελεστές αποφάσεων. Η περιοχή στην οποία ικανοποιούνται όλοι οι περιορισμοί λέγεται εφικτή περιοχή.
\subsection{Θεωρητικό παράδειγμα εφαρμογής}
Ένα παράδειγμα προβλήματος Γραμμικού Προγραμματισμού, που διαδραματίζει καθοριστικό ρόλο στην κατανομή πόρων, είναι αυτό της έυρεσης του ελάχιστου κόστους παραγωγής.
Παραθέτουμε λοιπόν το εξής παράδειγμα~\cite{2006}:\\
Μια εταιρία παράγει δύο προϊόντα Α και Β. Η εταιρία έχει δύο εργοστάσια ηλεκτρικών μηχανημάτων τα οποία από κοινού κατασκευάζουν τα δύο προϊόντα στις 
ποσότητες ανά ώρα που φαίνονται στον ακόλουθο πίνακα:\\
\begin{center}
\begin{arrayrulecolor}{black}
\begin{tabular}{m{0.30\linewidth}||c|c}
\rowcolor{lightgray}
\cellcolor{white}	 &Εργοστάσιο 1 & Εργοστάσιο 2\\ \hline
\cellcolor{yellow} Προϊόν Α & 10 	      & 20    	    \\ \hline
\cellcolor{yellow} Προϊόν Β & 25          & 25 	    \\ \hline
\end{tabular}
\end{arrayrulecolor}
\end{center}
Η εταιρία λαμβάνει μια παραγγελία για 300 τεμάχια του προϊόντοος Α και 500 τεμάχια του προϊόντος Β. Η δαπάνη λειτουργίας του Εργοστασίου 1 είναι 10.000 
ευρώ ανά ώρα, ενώ του Εργοστασίου Β είναι 8.000 ευρώ ανά ώρα.
\begin{itemize}
\item Να σχηματιστεί το πρόβλημα γραμμικού προγραμματισμού για την ελαχιστοποίηση του συνολικού κόστους της παραγγελίας
\item Να βρεθεί το σημείο όπου ελαχιστοποιείται το κόστος, καθώς και το ελάχιστο κόστος
\end{itemize} \vspace{-0.3cm}
\begin{center}\textbf{Λύση}\end{center} \noindent \vspace{-0.5cm} \\
\underline{\textsc{Ορισμός μεταβλητών}}: \noindent  \vspace{2mm} \\
Έστω $x_1 , x_2$ είναι ο αριθμός των ωρών κατά τις οποίες εργάζονται τα δύο εργοστάσια για την ικανοποίηση της παραγγελίας.
Tο συνολικό κόστος λειτουργίας των δύο εργοστασίων είναι $z=10.000x_1 + 8.000x_2$. Επίσης, σε μία ώρα παράγονται $10x_1+20x_2$ τεμάχια του προϊόντος Α, 
και $25x_1 + 25x_2$ τεμάχια του προϊόντος Β. Εφόσον ζητούνται 300 τεμάχια του Α και 500 τεμάχια του Β, πρέπει να ισχύουν $10x_1+20x_2 \geq 300$ και 
$25x_1 + 25x_2 \geq 500$. Ισχύουν επίσης $x_1 \geq 0 $ και $x_2 \geq 0$.\vspace{1mm}\\
\underline{\textsc{Μαθηματική μοντελοποίηση}}:\noindent \vspace{2mm} \\
Θέλουμε να ελαχιστοποιήσουμε την αντικειμενική συνάρτηση $$z=10.000x_1 + 8.000x_2 $$ υπό τους περιορισμούς 
\begin{align*}
10x_1 + 20x_2 \geq 300\\
25x_1 + 25x_2 \geq 500\\
x_1 \geq 0 \\
x_2 \geq 0
\end{align*}
\underline{\textsc{Γραφική αναπαράσταση}}   \vspace{2mm} \\ \noindent
Στο παρακάτω σχήμα (σχήμα~\ref{im:1}) φαίνεται η εφικτή περιοχή του υπό μελέτη προβλήματος
\begin{figure}[h] %here η τοποθέτηση της εικόνας
\centering %κεντραρισμένη
\includegraphics[width=\linewidth, ]{img1a.pdf}
\caption{Αναπαράσταση της εφικτής περιοχής}
\label{im:1}
\end{figure}
\noindent \\
Για την εύρεση της λύσης χρησιμοποιούμε το παρακάτω θεώρημα:
%\begin{mdframed}[linewidth=1pt,
%roundcormer=5pt,
%innerleftmargin=8pt,
%innerrightmargin=8pt,
%innertopmargin=8pt,
%innerbottommargin=8pt,
%backgroundvolor=blue!10,
%}
\begin{mdframed}[style=theorembox]
\begin{mytheorem} %\label{thm:ex1}
Αν υπάρχει το καλύτερο διατεταγμένο ζεύγος $(x_1,x_2)$, δηλαδή το ζεύγος εκείνο που ελαχιστοποιεί (ή μεγιστοποιεί) την αντικειμενική συνάρτηση, τότε
 οι τιμές $x_1$ και $x_2$ θα είναι οι συντεταγμένες $(x_1,x_2)$ ενός (ή περισσοτέρων) σημείου από τις κορυφές της εφικτής περιοχής.
\end{mytheorem} \end{mdframed}
Συνεπώς, προσδιορίζουμε τα σημεία Α,Β,Γ που φαίνονται στο σχήμα~\ref{im:1}.
Για την εύρεση του σημείου Β, λύνουμε το σύστημα εξισώσεων:
\begin{IEEEeqnarray*}{l}
\begin{cases}
	25x_1 + 25x_2 = 500\\
	10x_1 + 20x_2 = 300
\end{cases} \Rightarrow 
\begin{cases}
	x_1+x_2=20\\
	x_1+2x_2=30
\end{cases} \Rightarrow \\
\begin{cases}
	x_1=20-x_2\\
	x_1+2x_2=30
\end{cases} \Rightarrow 
\begin{cases}
	x_1=20-x_2\\
	20-x_2+2x_2=30
\end{cases} \Rightarrow \\
\begin{cases}
	x_1=20-x_2\\
	x_2=10
\end{cases} \Rightarrow 
\begin{cases}
	x_1=10\\
	x_2=10
\end{cases}
\end{IEEEeqnarray*}
Με αντικατάσταση των σημείων Α(0,20), Β(10,10) , Γ(30,0) στην αντικειμενική συνάρτηση $z$, έχουμε:\\
\begin{description}
\item[Για το Α(0,20)] \noindent \\$z=10.000\cdot 0+8.000 \cdot 20 \; = \; 160.000$
\item[Για το Β(10,10)] \noindent \\$z=10.000 \cdot 10 + 8.000 \cdot 20 \; = \; 180.000$
\item[Για το Γ(30,0)] \noindent \\$z=10.000 \cdot 0 + 8.000 \cdot 30 \; = \; 300.000$
\end{description}
\underline{\textsc{Συμπεράσματα}}: \vspace{1mm} \\
Συνεπώς, το σημείο Α(0,20) ελαχιστοποιεί την αντικειμενική συνάρτηση $z$ και άρα είναι η λύση του υπό μελέτη προβλήματος. Αυτό σημαίνει ότι το ελάχιστο
 κόστος είναι \mbox{160.000} ευρώ και επιτυγχάνεται στο σημείο (0,20), δηλαδή όταν το Εργοστάσιο 1 δεν λειτουργεί καθόλου, ενώ το Εργοστάσιο 2 λειτουργεί 
 συνολικά για 20 ώρες.
\section{Συμπεράσματα}
Tα μαθηματικά διαδραματίζουν ουσιαστικό ρόλο στην επίλυση προβλημάτων Γραμμικού Προγραμματισμού και γενικότερα στην επιχειρησιακή 
έρευνα, παρέχοντας ένα ισχυρό και αναλυτικό πλαίσιο για την ανάλυση και την μοντελοποίηση. Η ευρεία εφαρμογή του Γραμμικού Προγραμματισμού στη διαχείρηση των αποθεμάτων, στην παραγωγή και
 στις μεταφορές, στα χρηματοοικονομικά και σε πολλούς άλλους τομείς, καταδεικνύει την τεράστια αξία και την αναγκαιότητα του. Η συνεχής ανάπτυξη 
 νέων μεθοδολογιών και υπολογιστικών εργαλίων αναμένεται να επηρρεάσει καταλυτικά την αντιμετώπιση ενός μεγάλου εύρους σύνθετων προβλημάτων στο μέλλον.  
 %εκτυπώνει όλη την βιβλιογραφία
\bibliographystyle{plain}
\bibliography{mybiblio}
\nocite{*}
\end{document}
