Lineární programování je matematický koncept, který se používá k nalezení optimálního řešení lineární funkce. Tato metoda využívá jednoduchých předpokladů pro optimalizaci dané funkce. Lineární programování má obrovské uplatnění v reálném světě a používá se k řešení různých typů problémů.

Lineární programování se používá v různých průmyslových odvětvích, jako je lodní průmysl, zpracovatelský průmysl, dopravní průmysl, telekomunikace a další.

Termín lineární programování se skládá ze dvou slov lineární a programování, slovo lineární říká vztah mezi různými typy proměnných prvního stupně použitých v problému a slovo programování nám říká postup krok za krokem k řešení těchto problémů.

V tomto článku se podrobně seznámíme s lineárním programováním, jeho příklady, vzorci a dalšími koncepty.

Obsah

• Co je lineární programování?
• Komponenty lineárního programování
• Příklady lineárního programování
• Problémy lineárního programování
• Typy problémů lineárního programování
• Vzorec lineárního programování
• Jak řešit problémy lineárního programování?
• Metody lineárního programování
• Simplexní metoda lineárního programování
• Grafická metoda lineárního programování
• Aplikace lineárního programování
• Význam lineárního programování
• Aktuální aplikace lineárního programování
• Lineární programování v operačním výzkumu
• Simplexní metoda

Co je lineární programování?

Lineární programování nebo Lineární optimalizace je technika, která nám pomáhá najít optimální řešení pro daný problém, optimální řešení je řešení, které je nejlepším možným výsledkem daného konkrétního problému.

Jednoduše řečeno, je to metoda, jak zjistit, jak něco udělat co nejlépe. S omezenými zdroji musíte optimálně využívat zdroje a dosáhnout nejlepšího možného výsledku v konkrétním cíli, jako jsou nejnižší náklady, nejvyšší marže nebo nejméně času.

Situace, která vyžaduje hledání nejlepších hodnot proměnných podléhajících určitým omezením, je situace, kdy používáme problémy lineárního programování. Tyto situace nelze zvládnout běžným kalkulem a numerickými technikami.

Definice lineárního programování

Lineární programování je technika používaná pro optimalizaci konkrétního scénáře. Použití lineárního programování nám poskytuje nejlepší možný výsledek v dané situaci. Využívá všechny dostupné zdroje takovým způsobem, aby poskytovaly optimální výsledek.

Komponenty lineárního programování

Základní součásti problému lineárního programování (LP) jsou:

• Rozhodovací proměnné: Proměnné, které chcete určit, abyste dosáhli optimálního řešení.
• Cílová funkce: M atematickou rovnici, která představuje cíl, kterého chcete dosáhnout
• Omezení: Omezení nebo omezení, která musí vaše rozhodovací proměnné dodržovat.
• Omezení nezápornosti: V některých scénáře reálného světa, rozhodovací proměnné nemohou být záporné

Další vlastnosti lineárního programování

• Konečnost: Počet rozhodovacích proměnných a omezení v LP problému je konečný.
• Linearita: Cílová funkce a všechna omezení musí být lineárními funkcemi rozhodovacích proměnných . To znamená, že stupeň proměnných by měl být jedna.

Příklady lineárního programování

Situaci, ve které je lineární programování aplikováno, můžeme pochopit pomocí níže uvedeného příkladu,

Předpokládejme, že doručovatel musí doručit 8 paketů za den na různá místa ve městě. Musí vybrat všechny pakety z A a musí je doručit do bodů P, Q, R, S, T, U, V a W. Vzdálenost mezi nimi je vyznačena pomocí čar, jak je znázorněno na obrázku níže. Nejkratší dráha, kterou doručovatel sleduje, je vypočítána pomocí konceptu lineárního programování.

jak převést char na řetězec

Problémy lineárního programování

Problémy lineárního programování (LPP) zahrnují optimalizaci lineární funkce k nalezení řešení optimální hodnoty pro funkci. Optimální hodnota může být buď maximální, nebo minimální hodnota.

V LPP jsou volány lineární funkce objektivní funkce. Objektivní funkce může mít více proměnných, které podléhají podmínkám a musí je splňovat lineární omezení .

Typy problémů lineárního programování

Existuje mnoho různých problémů lineárního programování (LPP), ale my se v tomto článku budeme zabývat třemi hlavními problémy lineárního programování.

Výrobní problémy

Výrobní problémy jsou problémem, který se zabývá počtem jednotek, které by měly být vyrobeny nebo prodány, aby se maximalizoval zisk, když každý produkt vyžaduje pevnou pracovní sílu, strojní hodiny a suroviny.

Problémy s dietou

Používá se k výpočtu počtu různých druhů složek, které mají být zahrnuty do stravy, aby se dosáhlo minimálních nákladů, v závislosti na dostupnosti potravin a jejich cenách.

Dopravní problémy

Používá se k určení harmonogramu přepravy k nalezení nejlevnějšího způsobu přepravy produktu ze závodů / továren umístěných na různých místech na různé trhy.

Vzorec lineárního programování

Problém lineárního programování se skládá z

• Rozhodovací proměnné
• Objektivní funkce
• Omezení
• Negativní omezení

Rozhodovací proměnné jsou proměnné x a y, které rozhodují o výstupu problému lineárního programování a představují konečné řešení.

The Objektivní funkce , obecně reprezentovaná Z, je lineární funkce, kterou je třeba optimalizovat podle dané podmínky, aby bylo dosaženo konečného řešení.

The omezení uvalené na rozhodovací proměnné, které omezují jejich hodnoty, se nazývají omezení.

Obecný vzorec problému lineárního programování je,

Objektivní funkce : Z = sekera + by

Omezení: cx + dy ≥ e, px + qy ≤ r

Nezáporná omezení: x ≥ 0, y ≥ 0

Ve výše uvedené podmínce jsou x a y rozhodovací proměnné.

Jak řešit problémy lineárního programování?

Před řešením úloh lineárního programování musíme úlohy nejprve formulovat podle standardních parametrů. Kroky pro řešení problémů lineárního programování jsou,

Krok 1: Označte v problému rozhodovací proměnné.

Krok 2: Sestavte objektivní funkci problému a zkontrolujte, zda je třeba funkci minimalizovat nebo maximalizovat.

Krok 3: Zapište všechna omezení lineárních úloh.

Krok 4: Zajistěte nezáporná omezení rozhodovacích proměnných.

Krok 5: Nyní vyřešte problém lineárního programování pomocí jakékoli metody, obecně používáme buď simplexní nebo grafickou metodu.

Metody lineárního programování

Pro řešení úloh lineárního programování používáme různé metody. Nejčastěji se používají dvě metody,

• Simplexní metoda
• Grafická metoda

Podívejme se podrobně na tyto dvě metody v tomto článku,

Simplexní metoda lineárního programování

Jednou z nejběžnějších metod řešení problému lineárního programování je simplexová metoda. V této metodě opakujeme určitou podmínku ‚n‘ několikrát, dokud nedosáhneme optimálního řešení.

Kroky potřebné k řešení problémů lineárního programování pomocí simplexové metody jsou:

Krok 1: Formulujte problémy lineárního programování na základě daných omezení.

Krok 2: Převeďte všechny dané nerovnosti na rovnice nebo rovnosti problémů lineárního programování přidáním proměnné slack ke každé nerovnosti, kdykoli to bude potřeba.

Krok 3: Sestrojte počáteční simplexní tabulku. Reprezentací každé omezující rovnice v řadě a zápisem účelové funkce do spodního řádku. Takto získaná tabulka se nazývá Simplexová tabulka.

Krok 4: Identifikujte největší záporný záznam ve spodním řádku sloupec prvku s nejvyšším záporným záznamem se nazývá sloupec pivotu

Krok 5: Rozdělte položky sloupce úplně vpravo položkami příslušného sloupce pivota, vyjma položek nejspodnějšího řádku. Řádek obsahující nejméně položek se nyní nazývá hlavní řádek. Otočný prvek je získán průsečíkem otočné řady a otočného sloupce.

Krok 6: Pomocí maticové operace a pomocí prvku pivot nastavte všechny položky ve sloupci pivot na nulu.

Krok 7: Zkontrolujte nezáporné položky v nejspodnějším řádku, pokud v dolním řádku nejsou žádné záporné položky, ukončete proces, jinak začněte proces znovu od kroku 4.

Krok 8: Takto získaná konečná simplexová tabulka poskytuje řešení našeho problému.

Grafická metoda lineárního programování

Grafická metoda je jiná metoda než metoda Simplex, která se používá k řešení problémů lineárního programování. Jak název napovídá, tato metoda využívá k řešení daných úloh lineárního programování grafy. Toto je nejlepší metoda pro řešení problémů lineárního programování a vyžaduje méně úsilí než simplexová metoda.

Při použití této metody vykreslíme všechny nerovnosti, které jsou vystaveny omezením v daných úlohách lineárního programování. Jakmile jsou všechny nerovnosti daného LPP vyneseny do XY grafu, společná oblast všech nerovností dává optimální řešení. Vypočítají se všechny rohové body použitelné oblasti a vypočítá se hodnota účelové funkce ve všech těchto bodech a porovnáním těchto hodnot dostaneme optimální řešení LPP.

Příklad: Najděte maximální a minimální hodnotu z = 6x + 9y, když jsou omezující podmínky,

• 2x + 3 roky ≤ 12
• x a y> 0
• x + y ≤ 5

Řešení:

Krok 1 : Nejprve převeďte nerovnice na normální rovnice. Rovnice tedy budou 2x+3y = 0, x = 0, y = 0 a x + y = 5.

Krok 2 : Najděte body, ve kterých 2x + 3y a x + y = 5 proříznou osu x a osu y. Pro nalezení průsečíku osy x vložte y = 0 do příslušné rovnice a najděte bod. Podobně pro průsečíky osy y vložte x = 0 do příslušné rovnice.

Krok 3 : Nakreslete dvě čáry protínající osu x a osu y. Zjistíme, že obě osy se navzájem protínají v (3,2).

Krok 4 : Pro x ≥ 0 a y ≥ 0 zjistíme, že jsou dodrženy obě nerovnice. Oblast tedy bude zahrnovat oblast oblasti ohraničenou dvěma osami a obě linie včetně počátku. Vykreslená oblast je znázorněna níže na obrázku.

Krok 5 : Najděte Z pro každý bod a maxima a minima.

Souřadnice	Z = 6x + 9 let
(0,5)	Z = 45
(0,4)	Z = 36
(5.0)	Z = 30
(6,0)	Z = 36
(3.2)	Z = 36

Zjistili jsme tedy, že Z = 6x + 9y je maximum v (0,5) a minimum v (5,0).

Aplikace lineárního programování

Lineární programování má aplikace v různých oblastech. Používá se k nalezení minimálních nákladů na proces, když jsou dána všechna omezení problémů. Používá se k optimalizaci nákladů na dopravu vozidla atd. Lineární programování má různé aplikace

Strojírenský průmysl

Engineering Industries používá lineární programování k řešení konstrukčních a výrobních problémů ak získání maximálního výkonu z daného stavu.

Výrobní průmysly

Výrobní průmysl používá lineární programování k maximalizaci zisku společností a ke snížení výrobních nákladů.

Energetický průmysl

Energetické společnosti využívají lineární programování k optimalizaci svého výrobního výkonu.

Dopravní průmysl

Lineární programování se také používá v dopravním průmyslu k nalezení cesty, jak minimalizovat náklady na dopravu.

Význam lineárního programování

Lineární programování má obrovský význam v různých průmyslových odvětvích, protože maximalizuje výstupní hodnotu a zároveň minimalizuje vstupní hodnoty podle různých omezení.

LP je vysoce použitelné, když máme při řešení problému více podmínek a musíme výstup problému optimalizovat, tj. buď musíme najít minimální nebo maximální hodnotu podle dané podmínky.

Přečtěte si více,

• Lineární nerovnosti
• Algebraické řešení lineárních nerovnic

Problémy lineárního programování

Problém 1: Společnost vyrábí a prodává dva typy produktů a náklady na výrobu každé jednotky a a b jsou 200 rupií a 150 rupií, každá jednotka produktu přináší zisk 20 rupií a každá jednotka produktu b přináší zisk 15 rupií při prodeji. . Společnost odhaduje, že měsíční poptávka po A a B bude maximálně na sklizené jednotce v celém výrobním rozpočtu na měsíc je stanovena na 50 000 rupií. Kolik jednotek by měla společnost vyrobit, aby dosáhla maximálního zisku z měsíčního prodeje z a b?

Řešení:

Nechť x = počet jednotek typu A

y = počet jednotek typu B

Maximalizovat Z = 40x + 50y

S výhradou omezení

3x + y ≤ 9

x + 2y ≤ 8

a x, y> 0

Zvažte rovnici,

3x + y = 9

x = 3

y = 0

a x + 2y = 8

x = 8

y = 0

Nyní můžeme určit maximální hodnotu Z vyhodnocením hodnoty Z ve čtyřech bodech (vrcholech), jak je uvedeno níže

Vrcholy	Z = 40x + 50y
(0, 0)	Z = 40 x 0 + 50 x 0 = Rs. 0
(3, 0)	Z = 40 x 3 + 50 x 0 = Rs. 120
(0, 4)	Z = 40 x 0 + 50 x 4 = Rs. 200
(23)	Z = 40 x 2 + 50 x 3 = Rs. 230

Maximální zisk, Z = Rs. 230

∴ Počet jednotek typu A je 2 a počet jednotek typu B je 3.

Úloha 2: Maximalizujte Z = 3x + 4y.

S výhradou omezení x + y ≤ 450, 2x + y ≤ 600 a x, y ≤ 0.

Řešení:

Máme z daného

Omezení (1)

X + Y = 450

Položení x = 0, ⇒ 0 + y = 450 ⇒ y = 450

Uvedení y = 0, ⇒ x + 0 = 450 ⇒ x = 450

Z, Omezení (2)

2x + y = 600

Položení x = 0, ⇒ 0 + y = 600 ⇒ y = 600

Položení y = 0, ⇒ 2x + 0 = 600 ⇒ x = 300

Nyní máme souřadnice bodů Z = 3x + 4y

Optimální řešení tedy maximum Z = 1800 na souřadnici x = 0 a y = 450. Graf je uveden níže.

Aktuální aplikace lineárního programování

Lineární programování, výkonná matematická technika, se používá k řešení optimalizačních problémů v různých průmyslových odvětvích. Zde jsou některé moderní aplikace:

• Optimalizace dodavatelského řetězce : Lineární programování pomáhá společnostem minimalizovat náklady a maximalizovat efektivitu v jejich dodavatelských řetězcích. Používá se k určení nákladově nejefektivnějších přepravních tras, skladových operací a strategií řízení zásob.
• Energetický management : V energetickém sektoru se lineární programování používá k optimalizaci kombinace metod výroby energie. To zahrnuje vyvážení tradičních zdrojů energie s obnovitelnými, aby se snížily náklady a dopad na životní prostředí při současném uspokojení poptávky.
• Návrh telekomunikační sítě : Lineární programování pomáhá při navrhování efektivních telekomunikačních sítí. Pomáhá při přidělování šířky pásma, navrhování rozložení sítě a optimalizaci toku dat pro zajištění vysokorychlostní komunikace s nižšími náklady.
• Finanční plánování : Firmy a finanční analytici používají lineární programování pro optimalizaci portfolia, řízení rizik a kapitálové rozpočtování. Pomáhá při investičních rozhodnutích, která maximalizují výnosy a zároveň minimalizují riziko.
• Logistika zdravotnictví : Ve zdravotnictví se lineární programování používá k optimalizaci alokace zdrojů, jako jsou nemocniční lůžka, zdravotnický personál a vybavení. Je to zásadní pro zlepšení péče o pacienty, zkrácení čekacích dob a efektivní řízení nákladů.
• Optimalizace výrobního procesu : Lineární programování se používá k určení optimální úrovně výroby pro více produktů ve výrobním závodě s ohledem na omezení, jako je práce, materiály a dostupnost stroje.
• Zemědělské plánování : Farmáři a zemědělští plánovači používají lineární programování k rozhodování o výběru plodin, využití půdy a alokaci zdrojů, aby maximalizovali výnosy a zisky a zároveň šetřili zdroje.
• Plánování posádky letecké společnosti : Aerolinky používají lineární programování k efektivnímu plánování posádek, což zajišťuje, že lety jsou obsazeny v souladu s předpisy a minimalizují provozní náklady.

Tyto aplikace demonstrují všestrannost a sílu lineárního programování při řešení složitých optimalizačních problémů v různých sektorech a ukazují jeho význam v dnešním světě založeném na datech.

Lineární programování v operačním výzkumu

• Základní nástroj : Lineární programování je základním nástrojem operačního výzkumu pro optimalizaci zdrojů.
• Rozhodování : Pomáhá při rozhodování o alokaci zdrojů, maximalizaci zisku nebo minimalizaci nákladů.
• Široké aplikace : Používá se v různých oblastech, jako je logistika, výroba, finance a zdravotnictví, pro řešení složitých problémů.
• Modelování problémů reálného světa : Transformuje problémy ze skutečného světa do matematických modelů za účelem nalezení nejefektivnějších řešení.

Simplexní metoda

• Optimalizační algoritmus : Simplexní metoda je výkonný algoritmus používaný v lineárním programování k nalezení optimálního řešení lineárních nerovností.
• Přístup krok za krokem : Iterativně se posouvá směrem k nejlepšímu řešení navigací po okrajích proveditelné oblasti definované omezeními.
• Účinnost : Známý pro svou efektivitu při řešení rozsáhlých problémů lineárního programování.
• Všestrannost : Použitelné v různých oblastech, jako je plánování stravy, síťové toky, plánování výroby a další, což předvádí svou všestrannost.

Lineární programování – FAQ

Co je lineární programování?

Lineární programování je matematický koncept, který se používá k optimalizaci daného lineárního problému, který má řadu omezení. Pomocí lineárního programování získáme optimální výstup zadaného problému

Jaké jsou problémy lineárního programování?

Problémy lineárního programování (LPP) jsou problémy, které dávají optimální řešení daných podmínek.

Co je vzorec lineárního programování?

Obecné vzorce lineárního programování jsou,

• Objektivní funkce: Z = ax + by
• Omezení: px + qy ≤ r, sx + ty ≤ u
• Nezáporná omezení: x ≥ 0, y ≥ 0

Jaké jsou různé typy lineárního programování?

Existují různé typy metod lineárního programování,

• Lineární programování simplexní metodou
• Lineární programování metodou R
• Lineární programování grafickou metodou

Jaké jsou požadavky na lineární programování?

Různé požadavky na problémy lineárního programování jsou,

• Linearita
• Objektivní funkce
• Omezení
• Nezápornost

Jaké jsou výhody lineárního programování?

Různé výhody lineárního programování jsou,

• Poskytuje optimální řešení jakéhokoli daného lineárního problému.
• Snadno se používá a vždy poskytuje konzistentní výsledky
• Pomáhá maximalizovat zisky a snižovat vstupní náklady.