https://um.mendelu.cz/... in URL, click View on GitHub to open this file on github.com.e on GitHub). However, an advanced VS Code editor (press . on GitHub) is better, since it provides preview how the Markdown code renders. Alternatively press pencil for simple editor or press triangle next to the pencil to get access to VS Code described as github.dev.Ctrl+V and K. Keep the preview open as you work, or close using a mouse.Source control (describe your changes, such as “Polish translation started”) and then press Commit&Push.is_finished: False in header to is_finished: True.https://um.mendelu.cz/..., otevřete jej na serveru github.com.e na GitHubu). Lepší je však pokročilý editor VS Code (stikněte . na GitHubu), protože poskytuje náhled, jak se kód Markdown interpretuje. Případně stiskněte tužku pro jednoduchý editor nebo stiskněte trojúhelníček vedle tužky, abyste získali přístup k editoru VS Code popsaný jako github.dev.Ctrl+V. a K. Během práce nechte náhled otevřený nebo jej zavřete pomocí myši.Zpráva (popište své změny, např. “Zahájen překlad do polštiny”) a poté stiskněte tlačítko Commit&Push.is_finished: False v záhlaví na is_finished: True.Lineární programování je matematická metoda používaná k nalezení nejlepšího řešení určitého problému. Jedná se o techniku, která se zaměřuje na maximalizaci nebo minimalizaci lineární funkce za určitých omezení, která jsou také vyjádřena jako lineární rovnice nebo nerovnice.
Tato oblast začala přitahovat pozornost matematiků až po první světové válce. Prvním z nich byl Lenoid Kantorovič, který však v důsledku tehdejších vládních represí (a posléze obav o svůj život) musel této práce zanechat. Ono totiž v tehdejším Sovětském svazu s centrálně řízenou ekonomikou optimalizovat výrobní procesy nebyl zrovna dobrý nápad (v jedné továrně se mu např. podařilo zefektivnit výrobu na 94 %, jenže pak přišlo nařízení, že všechny závody musí navýšit svoji efektivitu stejným způsobem).
Skutečným zlomovým bodem v rozvoji lineárního programování bylo zveřejnění tzv. simplexového algoritmu pro řešení těchto úloh v roce 1947. Jeho autorem je americký matematik George Dantzig, který se této oblasti začal věnovat v průběhu druhé světové války ve snaze zoptimalizovat některé procesy v americké armádě. Říkali tomu metody programovacího plánování pomocí stolních kalkulátorů. Ve své první odborné přednášce na toto téma hovořil o programování v lineární struktuře, což se následně zkrátilo pouze na lineární programování. Slůvko programování je pozůstatkem vojensky motivované terminologie, která odkazuje na plánování či rozvrhování tréninků, logistiky či rozmístění mužstva.
Principy si ukážeme na následujících jednoduchých příkladech.
Úloha 1. Berenika a Petr si otevřeli novou kavárnu s pražírnou, kde mimo jiné začali vyrábět dvě směsi kávy: letní a exotickou. Letní směs je umíchána ze 40,% ze zrn sladké etiopské kávy a ze 60,% ze zrn šťavnaté kávy z Peru. Exotická směs je vyrobena ze stejných kávových zrn, ale v poměru 3:1 (tentokrát je více etiopské kávy). K dispozici je \(90\,\text{kg}\) etiopské kávy a \(70\,\text{kg}\) peruánské kávy. Kilogram letní směsi se prodává za 650 Kč a kilogram exotické směsi za 800 Kč. Kolik které směsi by měli Berenika a Petr z dostupných kávových zrn namíchat, aby maximalizovali svůj zisk?
Řešení Nejdříve potřebujeme celý tento problém matematizovat. Začneme proto tím, že množství namíchané letní směsi označíme jako \(x\) a množství exotické směsi jako \(y\). Bez ohledu na to, kolik bude jednotlivých směsí vyrobeno, zisk \(z\) z jejich prodeje můžeme vyjádřit pomocí výrazu \[ z=650x+800y. \] Je jasné, že nelze vyrábět záporné množství, tj. určitě musí platit \[ x\geq0\quad \text{a zároveň}\quad y\geq0. \tag{1} \] Nyní musíme zohlednit to, že nemáme neomezené množství kávových zrn. Celkovou spotřebou etiopské kávy můžeme vzhledem k poměrům míchání vyjádřit jako \[ 0{,}4x+0{,}75y \] a v případě peruánské kávy to je \[ 0{,}6x+0{,}25y. \] Dohromady s dostupným množstvím získáváme dvojici podmínek \[ 0{,}4x+0{,}75y\leq90 \quad\text{a zároveň}\quad\quad 0{,}6x+0{,}25y\leq70. \tag{2} \] Množina bodů, které vyhovují podmínkám \((1)\) a \((2)\) je vyšrafována na obrázku níže, přičemž zelenou barvou je zakreslena hraniční přímka \(0{,}4x+0{,}75y=90\) a modrou barvou přímka \(0{,}6x+0{,}25y=70\).
Ve vyšrafované oblasti jsou tak všechny body, jejichž souřadnice \(x\) a \(y\) odpovídají možným řešením naší úlohy. Jak ale najdeme bod s maximálním ziskem, tj. bod ve kterém je hodnota výrazu \(z=650x+800y\) maximální?
Můžeme si uvědomit, že tento výraz je rovnicí roviny v trojrozměrném prostoru. Uvažujeme-li z této roviny pouze tu část, která je nad vyšrafovanou oblastí, dostáváme v prostoru čtyřúhelník.
Místo toho, abychom kreslili prostorový obrázek, dokreslíme si do obrázku ještě tzv. vrstevnice. Jsou to přímky s rovnicemi \[ 650x+800y=c \] pro vhodná \(c\). Význam těchto vrstevnic je podobný jako význam vrstevnic na mapě. Pouze místo bodů o stejné nadmořské výšce, spojují naše vrstevnice body, ve kterých dosáhneme stejného zisku.
Tímto postupem dostaneme obrázek s vrstevnicemi zakreslenými hnědou barvou.
Jak ale určíme vhodnou hodnotu \(c\)? Tu naštěstí nemusíme nijak složitě počítat, ale můžeme ji zjistit z našeho obrázku. Pro \(c=0\) dostaneme přímku procházející počátkem, a jelikož se všechny vrstevnice liší pouze hodnotou \(c\), musí být všechny hnědé přímky rovnoběžné. Odtud pak už jen vidíme, že maximum (vrstevnice se s rostoucí hodnotou \(c\) posouvají severovýchodním směrem) bude v bodě, kde se protne modrá a zelená přímka.
Souřadnice tohoto bodu tedy můžeme najít jako řešení soustavy lineárních rovnic o dvou neznámých \[ \begin{align*} 0{,}4x+0{,}75y&=90 \\ 0{,}6x+0{,}25y&=70. \end{align*} \] Je jím bod o souřadnicích \(\left[\frac{600}{7},\frac{520}{7}\right]\). Dosazením těchto hodnot do výrazu \(z=650x+800y\) dostaneme hodnotu maximálního zisku přibližně \(115\,143\,\text{Kč}\). Toho bude dosaženo, pokud Berenika s Petrem vyrobí \(600/7\,\text{kg}\), tj. přibližně \(85{,}71\,\text{kg}\) letní směsi a \(520/7\,\text{kg}\), tj. přibližně \(74{,}29\,\text{kg}\) exotické směsi.
Poznámka. To, že řešení vyšlo v průsečíku dvou hraničních přímek, však není náhoda. U těchto úloh, kdy všechny funkce jsou pouze lineární, platí, že řešení je vždy v některém z vrcholů mnohoúhelníku (pokud existuje) vymezujícího všechny přípustné body. Toho lze využít i v případě úloh s mnohem větším počtem neznámých.
Stačí najít všechny vrcholy a porovnat funkční hodnoty. Avšak toto použití tzv. hrubé síly má svá úskalí: může být výpočetně velmi náročné a vyžaduje mít zaručenu existenci řešení. Nicméně tato myšlenka stojí za prvním velmi efektivním (a dodnes používaným) algoritmem pro řešení těchto úloh. Při jeho použití jsou vrcholy procházeny systematicky (tj. ne nutně všechny).
Úloha 2. Místní developer se rozhodl zakoupit továrnu na výrobu videokazet a magnetofonových pásků. Továrna dnes již nemá žádné využití, a tak bude zbourána, aby na jejím místě vyrostlo P+R parkoviště pro osobní automobily a zároveň odstavné parkoviště pro nákladní automobily. Developer však nyní řeší problém, jakou nastavit kapacitu pro jednotlivé druhy vozů. Celkový dostupný prostor bude \(480\,\text{m}^2\). Parkovací místo pro osobní automobil zabere \(12\,\text{m}^2\), zatímco pro nákladní auto to je \(30\,\text{m}^2\).
Stavební úřad však zároveň požaduje, aby kapacita pro osobní automobily byla alespoň dvakrát větší než pro nákladní vozy, ale zároveň tam musí být nejméně 6 parkovacích míst pro nákladní automobily.
Stanovte optimální počet parkovacích míst pro osobní i nákladní automobily, který bude splňovat všechny uvedené podmínky a zároveň maximalizuje zisk z plného parkoviště, pokud za každé parkovací místo pro osobní automobily bude platba 100 Kč a pro nákladní vozy 400 Kč.
Řešení. Můžeme postupovat podobně jako v předchozím příkladě, avšak je potřeba mít na mysli, že tentokrát musí být počty parkovacích míst celočíselné. Označíme-li jako \(x\) počty parkovacích míst pro osobní automobily a jako \(y\) počty parkovacích míst pro nákladní vozy, pak naším cílem je maximalizovat zisk \(z\) daný vztahem \[ z=100x+400y. \] Navíc z uvedených podmínek plynou následující omezení.
| Podmínka | Zdůvodnění |
|---|---|
| \(y\geq 6\) | požadavek na minimální počet pro nákladní vozy |
| \(2y\leq x\) | požadavek na druhy parkovacích míst |
| \(12x+30y\leq480\) | dostupná kapacita pozemku |
| \(x,y\in\mathbb{N}\cup\{0\}\) | počty musí být přirozená čísla nebo případně nula |
Množina splňující všechny uvedené podmínky je vykreslena na obrázku níže. Vyznačeny jsou přímky \(y=6\) (zelenou barvou), \(2y=x\) (hnědou barvou), \(12x+30y=480\) (modrou barvou) a vrstevnice \(100x+400y=c\) pro různé hodnoty hodnoty \(c\) (červenou barvou). Čím větší je \(c\), tím více jsou vrstevnice “vpravo nahoře”.
Růžovou barvou je vyšrafován mnohoúhelník, který vyhovuje všem uvedeným podmínkám kromě poslední. Černé body jsou pak všechny body, které splňují i tuto podmínku, tj. mají navíc jenom jako souřadnice přirozená čísla (nula nepřichází v dané oblasti v úvahu).
Z obrázku je patrné, že maximum bude v bodě, který je nejvíce vpravo nahoře. Jaké jsou ale jeho souřadnice?
Vzhledem k tomu, že se jedná o průsečík modré a hnědé přímky, můžeme jeho souřadnice určit řešením soustavy rovnic \[ \begin{align*} 2y&=x\\ 12x+30y&=480 \end{align*} \] Jejím řešením je dvojice \([160/9,80/9]\), která ale není celočíselná.
Podíváme-li se na obrázek pozorně a zvážíme-li směr vrstevnic, můžeme odhadnout, že hledané maximum dostaneme pro \(y=8\). Současně vidíme, že černý bod s touto hodnotou leží na modré přímce. Tedy po dosazení \(y=8\) do rovnice této přímky, dostaneme \(x=20\).
Maximálního zisku \(5200\) Kč proto bude dosaženo v případě, kdy bude vybudováno \(20\) parkovacích míst pro osobní automobily a \(8\) parkovacích míst pro nákladní vozy.
Jako kontrolu můžeme samozřejmě určit všechny celočíselné body splňující daná omezení a ověřit, že v žádném z nich není hodnota výrazu \(100x+400y\) větší nebo rovna \(5200\).
Linear programming is a mathematical method used to find the best solution to a particular problem. It is a technique that aims to maximize or minimize a linear function under certain constraints, which are also expressed as linear equations or inequations.
This field began to attract the attention of mathematicians only after the First World War. One of the first was Leonid Kantorovich, who was later forced to abandon his work due to the government repression at that time, and eventually out of fear for his life. It was not a good idea to optimize production processes in the Soviet Union, which had a centrally planned economy at the time (for example, in one factory he managed to increase production efficiency to 94%, only to be told that all factories had to increase their efficiency in the same way).
The real turning point in the development of linear programming was the publication of the so-called simplex algorithm for solving these problems in 1947. Its author is the American mathematician George Dantzig, who began working in this field during the Second World War in an attempt to optimize certain processes in the US military. They called it programming methods using desktop calculators. In his first technical lecture on the subject, he talked about programming in a linear structure, which was subsequently shortened to just linear programming. The word programming is a relic of military terminology referring to the planning or scheduling of training, logistics, or team deployment.
We will illustrate the principles with the following simple examples.
Exercise 1. Berenika and Peter opened a new café with a roastery, where among other things they started to produce two blends of coffee: summer and exotic. The summer blend is made of 40% sweet Ethiopian coffee beans and 60% juicy coffee beans from Peru. The exotic blend is made from the same coffee beans, but in a 3:1 ratio (this time with more Ethiopian coffee beans). There are \(90\,\text{kg}\) of Ethiopian coffee and \(70\,\text{kg}\) of Peruvian coffee. A kilo of the summer blend sells for 650 CZK and a kilo of the exotic blend sells for 800 CZK. How much of which blend should Berenice and Peter mix from the available coffee beans to maximize their profit?
Solution First, we need to mathematize this whole problem. Let’s start, therefore, by denoting the amount of mixed summer mixture as \(x\) and the amount of exotic mixture as \(y\). Regardless of how many individual mixtures are produced, we can express the profit \(z\) from their sale using the equation \[ z=650x+800y. \] It is clear that a negative quantity cannot be produced, i.e. it must definitely hold that \[ x\geq0\quad \text{and}\quad y\geq0. \tag{1} \] Now we have to take into account that we do not have an unlimited amount of coffee beans. The total consumption of Ethiopian coffee, given the mixing ratios, can be expressed as \[ 0{.}4x+0{.}75y \] and in the case of Peruvian coffee it is \[ 0{.}6x+0{.}25y. \] Together with the available quantity, we obtain a pair of conditions \[ 0{.}4x+0{.}75y\leq90 \quad\text{and}\quad\quad 0{.}6x+0{.}25y\leq70. \tag{2} \] The set of points that satisfy conditions \((1)\) and \((2)\) is shaded in the figure below, with the boundary line \(0{.}4x+0{.}75y=90\) drawn in green and the line \(0{.}6x+0{.}25y=70\) drawn in blue.
The shaded area contains all points whose coordinates \(x\) and \(y\) represent possible solutions to our problem. But how do we find the point of maximum profit, i.e. the point at which the value of the expression \(z=650x+800y\) is at its maximum?
We can notice that this expression is the equation of a plane in three-dimensional space. If we consider only the part of this plane that is above the shaded area, we get a quadrilateral in space.
Rather than drawing a three-dimensional picture, we will draw so-called contour lines into the diagram—straight lines given by equations \[ 650x+800y=c \] for appropriate \(c\). The meaning of these contours is similar to the meaning of the contours on the map. Only instead of points of the same altitude, our contours connect points where we make the same profit.
Using this method, we obtain a diagram with contour lines drawn in brown.
But how do we determine the appropriate value of \(c\)? Fortunately, we don’t have to calculate this in any complicated way. We can read it from our diagram. For \(c=0\) we get a straight line passing through the origin, and since all contour lines differ only in the value of \(c\), all the brown lines must be parallel. From here we can just see that the maximum (the contour lines shift northeastward with increasing value of \(c\)) is at the point where the blue and green lines intersect.
We can therefore find the coordinates of this point as a solution to a system of linear equations with two unknowns \[ \begin{align*} 0{.}4x+0{.}75y&=90 \\ 0{.}6x+0{.}25y&=70. \end{align*} \]The solution is the point \(\left[\frac{600}{7},\frac{520}{7}\right]\). Substituting these values into the expression \(z=650x+800y\), we get the value of the maximum profit of approximately \(115{,}143\,\text{Kč}\). This will be achieved if Berenika and Petr produce \(600/7\,\text{kg}\), i.e. approximately \(85{.}71\,\text{kg}\) of the summer mixture and \(520/7\,\text{kg}\), i.e. approximately \(74{.}29\,\text{kg}\) of the exotic mixture.
Note. The fact that the solution is at the intersection of two boundary lines is no coincidence. In problems like this one, where only linear functions occur, the solution (if it exists) always lies at one of the vertices of the polygon which represents the feasible region. This fact can be used even in problems with a much larger number of variables.
All you need to do is find all the vertices and compare their function values. However, this use of the so-called brute force has its pitfalls: it can be computationally very demanding and requires having a guaranteed existence of a solution. Nevertheless, this idea is behind the first very efficient algorithm (which is still used today) for solving these problems. When using it, the vertices are traversed systematically (i.e. not necessarily all of them).
Exercise 2. A local developer has decided to buy a factory that produced video cassettes and magnetophone tapes. The factory is no longer in use, so it will be demolished to make way for a P+R parking lot for cars and a truck park. However, the developer is now solving the problem of how to set the capacity for each type of vehicle. The total available space is \(480\,\text{m}^2\). A parking space for a car takes up \(12\,\text{m}^2\), while for a truck it is \(30\,\text{m}^2\).
However, the planning and building department also requires that the capacity for passenger cars be at least twice as large as for trucks. At the same time, there must be at least 6 parking spaces for trucks.
Determine the optimal number of parking spaces for cars and trucks that will meet all of the conditions above and at the same time maximize the profit from a full parking lot if the payment for each parking space for cars is 100 CZK and for trucks is 400 CZK.
Solution. We can proceed in a similar way as in the previous example, but keep in mind that this time, the number of parking spaces must be an integer. If we denote as \(x\) the number of parking spaces for cars and as \(y\) the number of parking spaces for trucks, then our objective is to maximize the profit \(z\) given by equation \[ z=100x+400y. \] In addition, the following conditions arise from the given constraints.
| Condition | Reasoning |
|---|---|
| \(y\geq 6\) | required minimum parking spaces for trucks |
| \(2y\leq x\) | requirement for types of parking spaces |
| \(12x+30y\leq480\) | available capacity of the plot |
| \(x,y\in\mathbb{N}\cup\{0\}\) | solutions must be natural numbers or zero |
The set satisfying all the given conditions is shown in the diagram below. The lines \(y=6\) (green), \(2y=x\) (brown), \(12x+30y=480\) (blue) and the contour lines \(100x+400y=c\) for different values of \(c\) (red) are marked. The greater the value of \(c\), the more the contour shift towards the “upper right”.
The pink shaded polygon satisfies all the conditions except the last one. The black points are all the points that also satisfy the last condition, i.e. they only have natural numbers as coordinates (zero is not an option in the given area).
It is clear from the diagram that the maximum will be at the point that is most to the upper right. But what are its coordinates?
Since this is the intersection of the blue and brown lines, we can determine its coordinates by solving the following system of linear equations \[ \begin{align*} 2y&=x\\ 12x+30y&=480. \end{align*} \] Its solution is the pair \([160/9,80/9]\), which, however, is not an integer pair.
If we look at the diagram carefully and consider the direction of the contour lines, we can estimate that we get the desired maximum for the value \(y=8\). At the same time, we see that the black point with this value lies on the blue line. After substituting \(y=8\) into the equation of this line, we get \(x=20\).
The maximum profit of \(5200\) CZK is achieved when \(20\) parking spaces for cars and \(8\) parking spaces for trucks are built.
As a verification, we can of course determine all integer points satisfying the restrictions and verify that none of them has a value of \(100x+400y\) greater than or equal to \(5200\).