Kantorovičova teorie optimální alokace zdrojů. Vědecká elektronická knihovna. Rysy života, činnost, přínos pro vědu, ekonomické a matematické teorie L.V. Kantorovič. Analýza počáteční fáze historie lineárního programování, koncipovaná
Velikost: px
Začít zobrazení ze stránky:
přepis
1 Otisk článku: Odkaz laureátů Nobelovy ceny za ekonomii: Shestakova A.A., Zabrodova O.S. Dědictví Leonida Kantoroviče, Tjalling Koopmans: Teorie optimálního rozdělení zdrojů // Dědictví laureátů Nobelovy ceny za ekonomii: So. Umění. III všeruský. vědecko-praktické. conf. Mladá. vědec - Samara, Legacy of Leonid Kantorovich, Tjalling Koopmans: teorie optimální alokace zdrojů 2016 Shestakova Alexandra Aleksandrovna studentka Zabrodova Olesya Sergeevna studentka 2016 Ufimtseva Lyudmila Ivanovna docentka 2016 Bezglanaya Elena Alekseevna docentka lineárního programování Státní univerzity Samara State University of Economics Na příkladu podobného problému je uvažována metoda optimalizace alokace zdrojů s využitím grafických, matematických metod a simplexové metody. Klíčová slova: L.V. Kantorovich, T. Ch. Koopmans, Nobelova cena, optimalizace alokace zdrojů, lineární programování. Dědictví Leonid Kantorovich, Tjalling Koopmans: teorie optimální alokace zdrojů 2016 Shestakova Aleksandra Aleksandrovna studentka Zabrodova Olesya Sergeevna studentka 2016 Ufimtseva Lyudmila Ivanovna 2016 Bezglasnaya Elena Alekseevna Samara model analýzy státní ekonomické univerzity, model praktické činnosti Kantorovich, Kuptorovich použití lineárního programování, metoda optimalizace alokace zdrojů podle Kantoroviče je zvažována na příkladu podobného problému pomocí grafické, matematické metody a simplexního algoritmu.
2 Klíčová slova: L.V. Kantorovich, Tjalling Koopmans, Nobelova cena, optimalizace distribuce zdrojů, lineární programování. Až do dvacátého století. vědci-ekonomové nevěnovali náležitou pozornost matematickým metodám jako prostředku řešení problémů na makro a mikroúrovni ekonomické aktivity. Přesto mezi těmito vědami existuje úzké propojení, které dokázali vynikající vědci prokázat. Jedním z nich je L.V. Kantorovič a T.Ch. Koopmans, sovětští a američtí matematici ekonomové, kteří jako výsledek své práce obdrželi v roce 1975 Nobelovu cenu „za přínos k teorii optimální alokace zdrojů“. Model L.V. Kantorovič, SSSR. L.V. Kantorovich se stal jedním ze zakladatelů nejdůležitější a nejčastěji používané optimalizační metody – lineárního programování. V roce 1937 dostal L. Kantorovich za úkol vybrat nejlepší výrobní program pro nakládací loupací stroje pro překližkový trust. Zároveň je znám počet strojů, které lze použít pro výrobu určitých výrobků, a také počet dílů, z nichž se výrobek skládá. Technické koeficienty ukazují, kolik kusů každého dílu dokáže stroj vyrobit za den. Jinými slovy, Kantorovich musel vyřešit konkrétní technický a ekonomický problém s objektivní funkcí maximalizace výstupu hotových výrobků. Vědec tak stojí před typickým představitelem zcela nové třídy problémů, které vedou k otázkám nalezení nejlepšího výrobního plánu. Svou myšlenku, která se později stala základem teorie optimální alokace zdrojů a znamenala objev lineárního programování, nastínil Kantorovič ve svém díle Mathematical Methods for Organisation and Planning of Production (1939). Profesor v něm poprvé demonstroval, že různé produkční problémy lze formulovat jako optimalizační problémy určitého typu a navrhl obecný přístup k jejich řešení pomocí iterační metody. K vyřešení problému zavedl Kantorovich proměnnou, která by měla být maximalizována jako součet nákladů na produkty vyrobené všemi stroji. Omezení byla stanovena ve formě rovnic stanovujících vztah mezi všemi faktory podílejícími se na výrobě a množstvím výstupu vyrobeného na každém stroji. Pro ukazatele výrobních faktorů byly zavedeny koeficienty, nazývané "rozhodující faktory" (dále objektivně stanovené odhady). S jejich pomocí je úkol vyřešen. Klíčovým bodem Kantorovičovy metody jsou objektivně stanovené odhady. Jsou spojeny s interpretací podobnou Lagrangeovým multiplikátorům v klasických extrémních problémech a ekonomická podstata je v tom, že jde o mezní náklady omezujících faktorů. To znamená, že se jedná o objektivní ceny každého z výrobních faktorů ve vztahu k podmínkám konkurenčního trhu. Také tyto odhady nejsou libovolné, jejich hodnoty jsou objektivně určeny, jsou dány konkrétními podmínkami problému. Byl tak učiněn objev, který umožňuje optimalizovat výrobu, umožňuje decentralizovaně řídit činnost výrobních sektorů, jejichž technologickou strukturu lze popsat pomocí lineárních závislostí (rovnic a nerovnic). "Analýza činností" T.Ch. Koopmans, USA. O něco později než Kantorovich se Koopmans ve své práci „Korelace mezi toky nákladní dopravy po různých trasách“ (1942) zabýval problémem vypracování plánu pro obchod a
3 Odkaz laureátů Nobelovy ceny za ekonomii: navigace s minimální možností torpédování lodí ponorkami. Došel k závěru, že problém by měl být viděn jako lineární maximalizační funkce v rámci mnoha omezení. Omezení zase vědec předložil matematickými rovnicemi, které vyjadřují poměr počtu vynaložených výrobních faktorů (amortizace lodí, čas, mzdové náklady) k počtu zboží dodaného do různých destinací. V tomto případě celkové náklady nemohou přesáhnout výši nákladů na zboží dodané do každého přístavu. Koopmans došel k závěru, že podstatou principu lineárního programování je v optimálním případě shoda ideálních odhadů zdrojů nákladů a výsledků výroby. Do obecné metodiky lineárního programování vstoupila Koopmansova metoda, které se říkalo „analýza činnosti firmy“. Modely tohoto typu se liší od lineárních v tom, že v nich může být výroba spojena s uvolněním několika zboží. Pro každý typ výrobku je také možné volit mezi různými výrobními technologiemi. Důležité je, že model lze aplikovat jak v ekonomické teorii, tak v manažerské praxi. To je způsobeno stanovením koeficientu rovného nákladové ceně na ideálním trhu pomocí získaných rovnic. Koopmansův model má velkou hodnotu nejen pro centrální plánovací úřady, ale také pro jakékoli decentralizované výrobní procesy, kde je potřeba fungovat tváří v tvář omezeným zdrojům. Centrální orgány mohou stanovit cenové podmínky pro náklady, přičemž výběr optimálních cest ponechávají na místních lídrech. Uvnitř firmy metoda „rozboru činností“ umožňuje nejefektivněji organizovat práci. Platnost metody lineárního programování Abychom mohli posoudit validitu metody, zvažovali jsme ekonomický problém podobný tomu, který byl předložen před Kantorovičem. Předpokládejme, že společnost vyrábí řezivo a překližku. K jejich výrobě se na jednotku produkce používá smrkové a jedlové řezivo. Tabulka 1 - Příjmy z prodeje a zásoby surovin dříví spotřeba dříví na jednotku výroby Zásoby surovin řezivo smrková překližka množství výrobních příjmů na jednotku výroby Udělejme plán výroby řeziva a překližky, který přináší největší zisk: Nechte plán na výrobu - řezivo, - překližka. Pak zisk bude: Z(x)= max. Omezíme zásoby surovin: ;
4 Zvažte problém graficky: D-doména řešení systému omezení; ; přímky úrovně Z(x)=c probíhají kolmo k vektoru c a na těchto přímkách je hodnota zisku rovna. Když se čára úrovně pohybuje ve směru vektoru c, hodnota zisku se zvyšuje a největší hodnota bude v bodě M. Bod M - průsečík čar Takže zisk je maximální při výrobě 20 m řeziva a 1200 m překližky . Při uvažování dvou produktů je metoda jednoduchá a lze ji snadno znázornit jako graf. Je však také použitelný pro problémy vyššího řádu zahrnující tři nebo více produktů. V těchto případech nemůžeme použít grafické řešení, ale Kantorovich vyvinul algoritmické, s jehož pomocí lze získat řešení postupnou aproximací - simplexovou metodou. Takové problémy lze řešit simplexovou metodou pomocí počítačových programů. Řešení problému pomocí tabulkového editoru Microsoft Office Excel: Podařilo se nám tedy najít optimální řešení pomocí lineárního programování. Tento podnik může získané hodnoty dobře nastavit do plánu organizace výrobních činností pro výrobu překližky a řeziva. Z výše uvedeného vyplývá, že díky aktivitám Kantoroviče a Koopmanse nejen matematika, ale i ekonomie získala nový, vcelku univerzální, pohodlný a potřebný úsek - lineární programování, a tím byl položen základ pro optimalizační metody. Vynález lineárního programování pomáhá při řešení hlavního problému ekonomiky – optimální alokace omezených zdrojů. Výše uvedené modely využívající lineární programování poskytují výběr z několika řešení takové možnosti, která maximalizuje výstup, a nikoli
5 Odkaz laureátů Nobelovy ceny za ekonomii: nejen na podnikové úrovni, ale i na makroekonomické úrovni. Ostatně rozsah použití metody je široký a pestrý - v úkolech racionálního využívání surovin; optimální organizace dopravy; optimalizace umístění podniků; efektivní plánování mnoha výrobních procesů atd. Lineární programování se také stalo pevným základem pro vznik mnoha dalších metod, které umožňují najít optimum pro výrobu jakékoli složitosti, jakéhokoli systému omezení. Literatura 1. Nobelisté 20. století. Autor - Vasina LL, 2001 2. Ekonomické a matematické metody a modely. Kniha úkolů. Autoři: R.I. Gorbunova R.I., Makarov S.I., Ufimtseva L.I., 2008 3. Johansen L., "Přínos L.V. Kantoroviče k ekonomické vědě", 1976 4. Kantorovich L.V., "Ekonomický výpočet nejlepšího využití zdrojů", 1959. M. V. Dovbenko Osik Yu. I., "Moderní ekonomické teorie v dílech nositelů Nobelovy ceny", Moskva, 2011
ANALÝZA UDRŽITELNOSTI OBCHODNÍ ČINNOSTI PODNIKU Degtyareva Nina Adamovna, kandidátka ekonomie, docentka Komerční práce je činnost podniku zaměřená na řešení konkrétního souboru problémů. Studie
FEDERÁLNÍ AGENTURA PRO ŽELEZNIČNÍ DOPRAVU FEDERÁLNÍ STÁTNÍ VZDĚLÁVACÍ INSTITUCE VYSOKÉHO ODBORNÉHO VZDĚLÁVÁNÍ "MOSKVA STÁTNÍ UNIVERZITA KOMUNIKACÍ" (MIIT)
FEDERÁLNÍ AGENTURA ŽELEZNIČNÍ DOPRAVY FEDERÁLNÍ STÁTNÍ VZDĚLÁVACÍ INSTITUCE VYSOKÉHO ODBORNÉHO VZDĚLÁVÁNÍ "MOSKVA STÁTNÍ UNIVERZITA KOMUNIKACÍ (MIIT)
Knyazeva A., Lykova N.P. GOU VPO "Ruská státní univerzita pro humanitní vědy" pobočka v Samaře FORMULACE PROBLÉMŮ LINEÁRNÍHO PROGRAMOVÁNÍ A JEJICH ŘEŠENÍ POMOCÍ MS EXCEL
FEDERÁLNÍ AGENTURA PRO ŽELEZNIČNÍ DOPRAVU
Borisová M.V., Nedopekina K.I. Počítačová implementace postupů lineárního programování // Akademie pedagogických nápadů "Inovace". Řada: Studentský vědecký bulletin. 2019. 3 (březen). ART 195-el. 0,2
SWorld – 2.–12. října 2012 http://www.sworld.com.ua/index.php/ru/conference/the-content-of-conferences/archives-of-individual-conferences/oct-2012 PRAKTICKÁ APLIKACE N.
Úkol. Řešte graficky ma F Najděte průsečíky čar definujících nerovnost. Průsečík tedy do oblasti nepatří. Vytvořme doménu přípustných řešení. Vytvořme směrový vektor
Problémy s optimalizací. Koltsov S.N. 2014 www.linis.ru Problémy lineárního programování Problémy optimálního plánování související s nalezením optima dané účelové funkce (lineární formy) v přítomnosti
5. Pokyny pro přípravu na praktická cvičení ve studiu oboru "Metody optimálních řešení" Směr přípravy 080100.62 "Ekonomika" Profil "Ekonomika a investiční management"
Federální agentura pro vzdělávání STÁTNÍ UNIVERZITA EKONOMIE A MANAGEMENTU NOVOSIBIRSK - "NINH" Reg. 24-0/02 Katedra vyšší matematiky
MATEMATICKÉ MODELOVÁNÍ METODOU SIMPLEX NA PŘÍKLADU PEKÁRNY "SHOKOLADNITSA" Kirnozova I.R. Stavropolská státní agrární univerzita, Stavropol, Rusko MATEMATIKA
Metody optimálního rozhodování Testovací úkol 1. Podnik vyrábí dva typy produktů (A a B), přičemž při výrobě těchto produktů využívá tři druhy zdrojů (první, druhý a třetí).
Matematické programování Každý den, ne vždy si to uvědomuje, každý člověk řeší problém, jak dosáhnout co největšího efektu a přitom utrácet omezené finanční prostředky. Pro dosažení co největšího efektu, mít
ODBOR ŠKOLSTVÍ MĚSTA MOSKVA STÁTNÍ ROZPOČET ODBORNÝ VZDĚLÁVACÍ INSTITUCE MĚSTA MOSKVA "POLYTECHNICAL COLLEGE 50" Grafická metoda řešení problémů lineárního programování
MPRA Munich Personal RePEc Archive Využití nástrojů analytické geometrie pro hledání extrému produkční funkce Natalia Aleksenko a Nadezhda Il ina a Victoriya Motrich Financial University
Ekonomické aplikace teorie extrémů funkcí dvou proměnných Lyalikova Ye R Lyalikova Elena Reomirovna / Ljalikova Elena Reomirovna - kandidátka fyzikálních a matematických věd, docentka katedry matematiky
Řešení úlohy lineárního programování grafickou metodou, simplexní metodou a prostřednictvím "Hledat řešení" v Excel TASK. Společnost vyrábí dva typy produktů: Produkt a Produkt. Pro výrobu jednotky
Řešení problémů lineárního programování Arsenij Mamoshkin SPbGU ITMO Katedra CT 2010 Mamoshkin A. M. (SPbSU ITMO CT) http://rain.ifmo.ru/cat 1 / 28 Obsah Formulace problému 1. Formulace
Investigation of Operations in Economics POMŮCKA UČENÍ 2. vydání, revidováno a doplněno Edited by Professor N. Ó. Kremera Doporučeno Ministerstvem školství Ruské federace jako učební pomůcka
Ministerstvo školství a vědy Ruské federace NOVOSIBIRSKÁ STÁTNÍ UNIVERZITA EKONOMIE A MANAGEMENTU "NINH" Reg. 754-16/02 Oddělení statistiky METODICKÉ SMĚRNICE PRO ORGANIZAČNÍ NEZÁVISLÉ
VARIANTA 5 Pro výrobu různých produktů A, B, C podnik používá různé druhy surovin. Použití údajů v tabulce: Druh surovin Cenové sazby surovin Množství surovin А В С I II III 18 6 5 15 4 12 8 540
Ministerstvo školství a vědy Ruské federace Federální státní rozpočtová vzdělávací instituce vyššího odborného vzdělávání Katedra Uralského státního lesního inženýrství
Operační výzkum Definice Operace je činnost zaměřená na dosažení určitého cíle, umožňující více možností a jejich řízení Definice Operační výzkum je soubor matematických
Z HISTORIE RUSKÉ ŠKOLY HOSPODÁŘSKO-MATEMICKÉHO A STATISTICKÉHO MODELOVÁNÍ
Úkol lineární výroby. Podnik může vyrábět čtyři typy produktů pomocí tří typů zdrojů. Známá technologická matice A stojí 7 8 zdrojů na výrobu jednotky
LABORATORNÍ PRÁCE ROZHODOVÁNÍ PODPŮRNÉ NÁSTROJE JAKO FUNKCE EXCELU Příkaz Výběr parametru Úkol 1. Uvažujme úlohu založenou na úloze použití funkce NPV. Jste požádáni
Tokarev K.S. Grafická interpretace vzájemných vztahů řešení původních a duálních problémů lineárního programování // Akademie pedagogických idejí "Inovace". Řada: Studentský vědecký bulletin. 2018.
Dynamický problém stanovení optimálního výrobního programu Mishchenko A.V., Dzhamai E.V. V dnešní dynamicky se měnící ekonomice progresivní změny v národohospodářském komplexu země
Praktická práce 8 Řešení úloh lineárního programování grafickou metodou. Účel práce: Naučit se řešit úlohy lineárního programování pomocí grafické metody. Obsah práce: Základní pojmy.
1 MDT: 004.032:633/635 OPTIMALIZACE DOPRAVY POMOCÍ AUTOMATIZOVANÉHO INFORMAČNÍHO SYSTÉMU VIZUÁLNÍHO ŘEŠENÍ DOPRAVNÍCH PROBLÉMŮ Zamotailova Daria Aleksandrovna studentka Burda Aleksey Grigoryevich
Téma 3: DOPRAVNÍ PROBLÉM 2 Plán tématu 3 "Dopravní úkol": 3.. Vysvětlení problému, základní definice 3.2. Problém uzavřené a otevřené dopravy 3.3. Metoda severozápadního rohu 3.4. Potenciální metoda
Salniková N. I. Kandidátka ekonomie, docentka, docentka katedry ekonomické teorie Ústav ekonomiky a managementu V. I. Vernadskij Rusko, Simferopol EFEKTIVITA A JEJÍ INTERPRETACE V DOMÁCÍM A ZÁPADNÍM
Řešení úlohy v předmětu "Teorie rozhodování" Firma "X" vyrábí tři druhy chemikálií. Tato firma uzavřela smlouvu na nadcházející měsíc na dodávku následujících množství tří typů chemikálií; Typ
ANALÝZA VÝBĚRU SPOTŘEBITELŮ NA PŘÍKLADU LOGARITMICKÉ FUNKCE UŽITKU Logunova Yu.A. Samara State University of Economics Samara, Rusko ANALÝZA VÝBĚRU SPOTŘEBITELŮ NA PŘÍKLADU
Úkol: Proveďte matematické vyjádření problému a najděte optimální řešení pomocí grafické metody. Varianta 2. Učebny a laboratoře univerzity jsou dimenzovány maximálně pro 5000 studentů. univerzita
FEDERÁLNÍ AGENTURA PRO ŽELEZNIČNÍ DOPRAVU
INSTITUT SVĚTOVÉ HOSPODÁŘSTVÍ A INFORMATIZACE NESTÁTNÍ VZDĚLÁVACÍ ÚSTAV VYSOKÉHO ODBORNÉHO VZDĚLÁVÁNÍ Ekonomicko-matematické metody a modely. MOSKVA - 00 Praktické úkoly
UDC 330.46 Aplikační schopnosti WolframAlpha pro řešení problémů lineárního programování Sokolov Arsenty Borisovič Ruská ekonomická univerzita. G.V. Plekhanova Magisterský student Vědecký poradce:
Analytické přiřazení obrazců na rovině. Optimalizační úlohy Kružnice se středem v bodě A 0 (x 0,y 0) a poloměr R je dána rovnicí (x-x 0) 2 + (y-y 0) 2 = R 2. Kružnice ohraničená touto kružnicí,
PETERSBURG POBOČKA NÁRODNÍ VÝZKUMNÉ UNIVERZITY "NEJVYŠŠÍ ŠKOLA EKONOMICKÁ" Katedra matematiky N. P. Anisimová, E. A. Vanina LINEÁRNÍ PROGRAMOVÁNÍ Učební pomůcka
UDC 519.852:330.4 Kurysheva A.S. student specializace "Ekonomická bezpečnost", Ekonomický institut, Národní výzkumná univerzita "BelGU", Rusko, Belgorod Zueva E.O. studentka oboru "Ekonomická bezpečnost",
0 (75) 0 Ekonomické a matematické modelování MDT 59.853.3 ŘEŠENÍ ŘADY EKONOMICKÝCH PROBLÉMŮ ALGORITHEM METODY TESTOVACÍCH FUNKCÍ S NEÚPLNOU MINIMALIZACÍ POMOCNÝCH FUNKCÍ A. G. Isavnin, doktor magistra
Kapitola 2 Lineární programování V lineárním programování studujeme problémy na extrému lineární funkce několika proměnných pod omezeními, jako jsou rovnosti a nerovnosti, rovněž dané lineárními
METODY OPTIMALIZACE LOGISTICKÝCH NÁKLADŮ PODNIKU Abramkina T.N. Samara State University of Economics Samara, Rusko OPTIMALIZAČNÍ METODY FIRMY LOGISTICKÝCH NÁKLADŮ Abramkina T. Samara
Duální problémy Obsah Ekonomická interpretace problému, duální problém využití zdrojů 2 Vzájemně duální úlohy lineárního programování a jejich vlastnosti 5 Věty o dualitě
Úkol. (musí být řešeno grafickou metodou) Najděte maximum účelové funkce L=4+y za následujících omezení: Vyřešte problém za dodatečné podmínky (DE): DE: Najděte minimum účelové funkce L=-y s
MDT 00,57: 004,94 M.B. Kotlyarevsky doktor fyzikálních a matematických věd, profesor P.V. Zacharčenko kandidát technických věd, docent, Akademie managementu a informačních technologií "ARIM", Berdyansk
MDT 5: 378 INFORMACE Z VÝUKY V DISCIPLÍNĚ "OPERAČNÍ VÝZKUM" NA ZÁKLADĚ APLIKACE MODELOVÝCH OPERACÍ VG Getmanov doktor technických věd, profesor profesor Ústavu informatiky a aplikované matematiky e-ml:
Kapitola Extrémy funkcí více proměnných Lokální extrémy funkcí dvou proměnných Podmíněné extrémy Funkce z f) má maximální minimum) v bodě M, lze-li takové okolí bodu nalézt.
1. 2 CÍLE A ÚKOLY ZVLÁDNUTÍ DISCIPLÍNY 1.1. Cíle zvládnutí disciplíny: Seznámit studenty s různými matematickými modely v ekonomice, jako je model bilance vstupů a výstupů, model ekonomické
Klasický dopravní problém řešený potenciální metodou Lozgachev IA, Korepanov M. Yu., studenti. Uralská státní báňská univerzita Jekatěrinburg, Rusko Klasická doprava
Téma: Simplexová metoda řešení úlohy lineárního programování Obecná matematická formulace hlavního problému lineárního programování: je dána soustava m lineárních rovnic o n neznámých a11x1 a12
Lomonosov Moskevská státní univerzita Moskevská ekonomická škola
LABORATORNÍ PRÁCE 1 ŘEŠENÍ PROBLÉMŮ LINEÁRNÍHO PROGRAMOVÁNÍ POMOCÍ Microsoft Excel a Mathcad ÚČEL PRÁCE Získání dovedností při řešení úloh lineárního programování (LP) v tabulkovém editoru
Praktická práce "Ekonomické a matematické metody a modely" Možnost 2 Úkol 1. Řešte graficky. 150x + 70x max, 30x1 + 75x2 900, 3x1 + 2x2 30, x, x 0. Řešení. Vytvořme doménu přípustných řešení
XLI Studentská mezinárodní korespondenční vědecká a praktická konference "Vědecké fórum mládeže: Sociální a ekonomické vědy" MS EXCEL JAKO PROSTŘEDEK K ŘEŠENÍ PROBLÉMŮ EKONOMICKÉHO MODELOVÁNÍ A
FEDERÁLNÍ AGENTURA PRO VZDĚLÁVÁNÍ Státní vzdělávací instituce vyššího odborného vzdělávání "Pacific State University" Katedra "Dřevoobráběcí technologie" MODELOVÁNÍ
Problém nelineární optimalizace. Koltsov S.N. 2014 www.linis.ru Neomezený problém optimalizace
Gruk Lyubov Vladimirovna Státní rozpočtová vzdělávací instituce střední škola 603 okresu Frunzenskij v Petrohradě FUNKCE A MATEMATICKÉ MODELY Funkční
Leonid Vitalievich Kantorovich (19. ledna 1912 - 7. dubna 1986) Nobelova cena za ekonomii 1975 (spolu s Tjallingem Koopmansem) ruský matematik a ekonom Leonid Vitalievich Kantorovich
Přednáška 2. Hlavní problém lineárního programování. Všechny problémy lineárního programování lze zredukovat na standardní formu, ve které musí být účelová funkce maximalizována a všechna omezení
MINISTERSTVO ŠKOLSTVÍ RUSKÉ FEDERACE Iževská státní technická univerzita Katedra CAD
Testový úkol 5 Podnik má suroviny typů 1, 2, 3 Lze z něj vyrábět výrobky typů A a B. Zásoby druhů surovin v podniku nechť jsou b 1, b 2, b 3 jednotky , resp.
FEDERÁLNÍ AGENTURA ŽELEZNIČNÍ DOPRAVY FEDERÁLNÍ STÁTNÍ ROZPOČET VZDĚLÁVACÍ INSTITUCE VYSOKÉHO ŠKOLSTVÍ "MOSKVA STÁTNÍ UNIVERZITA CÍSAŘSKÉ DOPRAVY"
Lineární programování v problémech řízení výroby Mnoho problémů řízení, ekonomiky a organizace výroby je řešeno metodou lineárního programování. Lineární model
"NAUKA- RASTUDENT.RU" Elektronický vědecký a praktický časopis Harmonogram vydávání: měsíčně Jazyky: ruština, angličtina, němčina, francouzština ISSN: 2311-8814 EL FS 77-57839 ze dne 25. dubna 2014
Banka úloh pro středně pokročilou kontrolu Test. Téma "Lineární programování" Skládá se z - 3 teoretických otázek k tématu a 4 6 praktických úkolů, které poskytují dovednosti a schopnosti: skládat matematické
Knyazeva A., Lykova N.P.
SEI HPE "Ruská státní univerzita pro humanitní vědy"
Pobočka v Samaře
formulace úloh lineárního programování a jejich řešení pomocí msexcelu
Za dobu zrodu lineárního programování je považován rok 1939, kdy vyšla brožura Leonida Vitalieviče Kantoroviče „Matematické metody organizace a plánování výroby“. Protože metody popsané L. V. Kantorovičem nebyly příliš vhodné pro ruční výpočty a vysokorychlostní počítače v té době neexistovaly, zůstala práce L. V. Kantoroviče téměř bez povšimnutí.
Lineární programování se znovuzrodilo na počátku padesátých let s příchodem počítačů. Poté začalo všeobecné nadšení pro lineární programování, které následně způsobilo rozvoj dalších sekcí matematického programování. V roce 1975 obdrželi akademik L. V. Kantorovich a americký profesor T. Koopmans Nobelovu cenu za ekonomické vědy za „příspěvek k rozvoji teorie a optimálnímu využití zdrojů v ekonomice“.
Ukázalo se, že je nutné naučit se řešit úlohy hledání extrémů lineárních funkcí na mnohostěnech definovaných lineárními nerovnicemi. Na návrh Koopmanse se toto odvětví matematiky nazývalo lineární programování.
Americký matematik A. Dantzig v roce 1947 vyvinul velmi účinnou specifickou metodu pro numerické řešení úloh lineárního programování (říkalo se jí simplexová metoda). Myšlenky lineárního programování během pěti nebo šesti let získaly ve světě grandiózní rozšíření a jména Koopmans a Dantzig se stala všude známá.
Problémy optimálního plánování související s nalezením optima dané účelové funkce (lineární formy) za přítomnosti omezení ve formě lineárních rovnic nebo lineárních nerovnic souvisí s problémy lineárního programování.
Lineární programování- nejrozvinutější a nejrozšířenější odvětví matematického programování.
Rozsah problémů řešených metodami lineárního programování je poměrně široký:
problém optimálního využití zdrojů při plánování výroby;
problém směsí (plánování složení produktů);
problém hledání optimální kombinace různých typů produktů pro skladování ve skladech (řízení zásob nebo „batohový problém“);
dopravní úkoly (analýza umístění podniku, pohyb zboží).
Ekonomický a matematický model každého problému lineárního programování zahrnuje: objektivní funkci, jejíž optimální hodnota (maximum nebo minimum) musí být nalezena; omezení ve formě soustavy lineárních rovnic nebo nerovnic; požadavek nezápornosti proměnných.
Obecně je model napsán takto:
Objektivní funkce: F(x)= c 1 x 1 + c 2 x 2 + ... + cnxn → max (min) (1)
omezení:
a 11 x 1 + a 12 x 2 + ... + a 1n xn (≤ = ≥) b 1 ,
a 21 x 1 + a 22 x 2 + ... + a 2n xn (≤ = ≥) b 2, (2)
a m1 x 1 + a m2 x 2 + ... + a mn xn (≤ = ≥) b m;
požadavek na nezápornost: x j ≥ 0, j = 1, 2,……, n (3)
V tomto případě a ij , b i , c j (I = 1, 2, ….., m; j = 1, 2,……, n) - dané konstanty.
Problém je najít optimální hodnotu funkce (1) za podmínek (2) a (3).
Nazývá se systém omezení (2). funkční omezení úkolu, a omezení (3) - Přímo.
Vektor, který splňuje podmínky (2) a (3), se nazývá proveditelné řešení (plán) úlohy lineárního programování. Zavolá se plán, podle kterého funkce (1) dosáhne své maximální (minimální) hodnoty optimální.
Problémy lineárního programování lze řešit ručně, tzn. algebraicky a graficky, nebo můžete použít MS Excel. Tento program umožňuje rychle a snadno řešit problémy lineárního programování.
Rozeberme si řešení takových problémů na konkrétním příkladu:
Na kožešinové farmě lze pěstovat lišky černohnědé a lišky polární. Pro zajištění normálních podmínek pro jejich pěstování se používají tři druhy krmiv. Množství potravy pro jednotlivé druhy, které by lišky a polární lišky měly denně dostávat, je uvedeno v tabulce. Udává také celkové množství krmiva každého druhu, které může kožešinová farma využít, a zisk z prodeje jedné kůže lišky a lišky polární.
| Druh krmiva | Denní množství konv. zdroje Jednotky | Celkové množství krmiva, k.ú. | |
| Zisk z prodeje jedné kůže, rub. | |||
Určete, kolik lišek a polárních lišek by se mělo pěstovat na kožešinové farmě, aby byl zisk z prodeje jejich kůží maximalizován.
Pojďme napsat matematický model:
X ks - lišky, Y ks - polární lišky
16x+12y - max. (1)
Řešení tohoto problému se analyticky redukuje na řešení systému tří nerovnic (2-4), vyjadřujících hodnotu jedné proměnné prostřednictvím druhé, získáme:
x 90 - 1,5 let
4 (90 - 1,5 roku) + y 240
6(90 - 1,5r) + 7r 426
x 1 54 x 2 4.5
y 1 24 y 2 57
navíc x 2 a y 2 řešení nesplňují, protože počet zvířat nemůže být zlomkové číslo.
Proto bude účelová funkce rovna: 1152
S pomocí MS Excel je však řešení mnohem jednodušší a rychlejší.
Pro vyřešení problému v MS Excel je potřeba vytvořit tabulku s počátečními údaji (obr. 1)
Obr.1 - Tabulka s počátečními daty (problém pro optimalizaci výroby)
Poté pomocí vestavěných funkcí MS Excel (=SUMPRODUCT) zaveďte omezení a účelovou funkci (obr. 2)
Rýže. 2 - omezení a objektivní funkce
Po zadání všech omezení a účelové funkce byste měli použít vestavěný program MS Excel Hledání řešení(obr. 3), který také zavádí účelovou funkci, omezení a proměnné buňky (tj. neznámé proměnné).
Rýže. 3 - Hledání řešení
Než však přistoupíte k řešení, je také nutné v záložce možnosti hledat řešení pro nastavení: lineární model, nezáporné hodnoty a automatické škálování (obr. 4)
Rýže. 4 - Možnosti hledání řešení
Po dokončení zadání všech omezení a parametrů dostaneme požadované řešení problému (obr. 5)
Rýže. 5 - Konečná tabulka s výsledným řešením
V praxi mnoho ekonomických parametrů (ceny výrobků a surovin, zásoby surovin, poptávka na trhu, mzdy atd.) v čase mění své hodnoty. Optimální řešení úlohy LP získané pro konkrétní ekonomickou situaci se tedy po její změně může ukázat jako nevhodné nebo neoptimální. V tomto ohledu vyvstává problém citlivostní analýzy problému LP, totiž jak případné změny parametrů původního modelu ovlivní dříve získané optimální řešení.
Vazebná omezení procházejí optimálním bodem. Nezávazná omezení neprocházejí optimálním bodem. Zdroj reprezentovaný závazným omezením se nazývá vzácný zdroj, zatímco zdroj reprezentovaný nezávazným omezením se nazývá nedostatkový. O omezení se říká, že je nadbytečné, pokud jeho vyloučení neovlivní rozsah proveditelných řešení a následně optimální řešení.
Rozlišují se následující tři úkoly analýzy citlivosti.
1. Analýza snížení nebo zvýšení zdrojů:
1) o kolik lze zvýšit nebo snížit zásobu vzácného zdroje, aby se zlepšila optimální hodnota digitálního filtru?
2) o kolik lze snížit nebo zvýšit zásobu nedeficitního zdroje při zachování získané optimální hodnoty digitálního filtru?
2. Zvýšení (snížení) zásob, který ze zdrojů je nejvýnosnější?
3. Analýza změny cílových koeficientů: jaký je rozsah změny koeficientů digitálního filtru, ve kterém se optimální řešení nemění?
MS Excel umožňuje vytvořit zprávu o výsledcích, která se skládá ze 3 tabulek:
1 - Cílová buňka. Zobrazuje počáteční hodnotu účelové funkce a optimální hodnotu (výsledek).
2- Vyměnitelné články. Odráží počáteční hodnoty proměnných a výsledné (optimální) hodnoty. Pokud produkt není zahrnut v optimálním řešení (rovná se 0), pak je považován za nerentabilní.
3- Omezení. Kromě názvu omezení obsahuje buňka, do které je zapsána levá strana omezení, následující sloupce:
Hodnota - hodnota levé strany omezení pro optimální plán. Tito. kolik zdrojů se skutečně využívá.
Vzorec – zobrazuje znaménko limitu (větší nebo rovno, menší nebo rovno atd.)
Stav – Zobrazí se přidružené nebo nepřidružené omezení. Pokud je stav vázán, je zdroj plně využit. Pokud stav není připojen, není zdroj plně využit.
Rozdíl - zobrazí se množství zbývajícího nevyužitého zdroje.
Stejně jako zpráva o udržitelnosti, která se skládá ze 2 tabulek:
1 - vyměnitelné buňky. Kromě názvů proměnných a adres buněk obsahuje sloupce:
Výsledná hodnota je optimální plán.
Normalizované (snížené) náklady - ukazuje, jak moc se změní účelová funkce po nuceném zařazení jednotky tohoto produktu do optimálního plánu. Pokud je produkt ziskový, pak budou nivelizované náklady 0.
Cílový koeficient - hodnoty koeficientů účelové funkce.
Přípustné zvýšení, přípustné snížení - zobrazuje hranice změn koeficientů účelové funkce, při kterých je zachována množina proměnných zahrnutých do optimálního řešení.
2 - Omezení. Kromě názvů proměnných a adres buněk obsahuje sloupce:
Výsledná hodnota je hodnota levé strany omezení pro optimální plán. Tito. kolik zdrojů se skutečně využívá.
Stínová cena je změna cílové funkce, když se vzácný zdroj změní o 1 jednotku. Stínová cena nevzácného zdroje bude 0.
Omezení Pravá strana je zásoba zdroje.
Přípustné zvýšení, přípustné snížení – ukazuje, jak moc můžete změnit pravou stranu omezení, dokud neovlivní účelovou funkci.
Výhodou použití MS Excel k řešení problémů lineárního programování je, že:
po vytvoření tabulky ji lze použít pro úlohy stejného typu pouze změnou počátečních dat;
všechny vzorce potřebné k řešení problému jsou již uvedeny v MS Excel;
vyřešení problému trvá několikrát méně času než ruční řešení;
přesnost řešení je mnohem vyšší než ruční a chyby jsou minimalizovány.
Jedinou nevýhodou řešení úloh lineárního programování pomocí MS Excel může být: chybějící kompletní řešení, tzn. hledání řešení okamžitě dává pohotovou odpověď, aniž by ukazovalo všechny výpočty, což v zásadě není cílem řešení problému.
Bibliografie:
A.G. Trifonov. Příklady řešení optimalizačních problémů // 2008
Popova N.V. Matematické metody // M.: VTK. – 2005
Lykova NP, Knyazeva VYHLÁŠENÍ PROBLÉMŮ LINEÁRNÍHO PROGRAMOVÁNÍ A JEJICH ŘEŠENÍ POMOCÍ MS EXCEL // Vědecký elektronický archiv.
URL: (datum přístupu: 26.12.2019).
Jedním z cílů předchozích kapitol bylo najít cestu z této nejednoznačnosti a těsně propojit teorii cen s teorií hodnoty. Považuji za špatné rozdělovat ekonomii na Teorii hodnoty a distribuce na jedné straně a Teorii peněz na straně druhé. Skutečná hranice podle mého názoru musí ležet mezi Teorií samostatného průmyslu nebo firmy, která se zabývá odměnami faktorů a rozdělením zdrojů mezi různé způsoby využití jejich daného množství, a Teorií výroby a zaměstnanosti. obecně. Dokud se omezíme na studium určitého odvětví nebo firmy, za předpokladu konstantního celkového množství použitých zdrojů a také dočasně za předpokladu, že podmínky v jiných odvětvích nebo firmách zůstanou nezměněny, nemusíme se ve skutečnosti zabývat specifiky peníze. Ale jakmile začneme zjišťovat, co určuje objem výroby a zaměstnanost obecně, potřebujeme kompletní teorii Monetární ekonomie.
Podle Smithe může tržní automatizace optimalizovat alokaci zdrojů. Na rozdíl od všeobecného přesvědčení, že soukromý zájem je v rozporu se zájmem veřejným, Smith dokázal, že decentralizace a volná soutěž mohou zajistit maximální uspokojení potřeb. Volná konkurence se snaží dát rovnítko mezi ceny a výrobní náklady, optimalizovat distribuci zdrojů v rámci odvětví a na trzích výrobních faktorů, vyrovnat čisté výhody těchto faktorů ve všech odvětvích, a tím vytvořit optimální rozdělení zdrojů mezi odvětvími. To byl první krok k teorii optimalizace alokace zdrojů v dokonalé konkurenci.
Zároveň je třeba vzít v úvahu, že zisk, jak již bylo zmíněno dříve, má za prvé dvě definice (v účetnictví a v ekonomické teorii) a za druhé různé hodnoty zisku jako implicitního příjmu obdrženého společností. prostřednictvím využití vlastních výrobních faktorů zisk jako odměnu za podnikatelské riziko a inovace (která je zahrnuta v ekonomických nákladech) zisk jako monopolní příjem v podmínkách nedokonalé konkurence. Každá z výše uvedených hodnot zisku je způsobena rozmanitostí svých zdrojů, včetně alternativního využití alternativních nákladů, nejistoty v ekonomickém prostředí a inovací, přítomnosti tržní nebo monopolní síly nad cenou. Zisk tak působí jako jakýsi katalyzátor rozvoje ekonomiky, pobídka pro racionální rozdělování zdrojů, pobídka pro akumulaci kapitálu.
Mezi nejdůležitější třídy problémů I.o. můžeme jmenovat problémy řízení zásob, problémy s alokací a přiřazením zdrojů (problémy s distribucí), problémy s řazením ve frontě, problémy s výměnou zařízení, s objednávkou a koordinací (včetně teorie plánování), kontradiktorní (například hry), problémy s vyhledáváním atd. používané metody - matematické programování (lineární, nelineární atd.), diferenciální a diferenční rovnice, metody teorie grafů, Markovovy procesy, teorie her, teorie (statistického) rozhodování, teorie rozpoznávání vzorů a řada dalších.
M. je někdy nazývána teorií cen, neboť jejím předmětem je mechanismus rozdělování zdrojů a v tržní ekonomice slouží ceny jako hlavní nástroj takového rozdělování.
V jedné z nich, v díle L.V.Kantoroviče "Matematické metody organizace a plánování výroby" (1939), byly poprvé uvedeny principy nového oboru matematiky, který později vešel ve známost jako lineární programování, a když se podíváte šířeji, , to položilo základy ekonomické teorie optimální alokace zdrojů. L.V. Kantorovič jasně formuloval pojem ekonomického optima a zavedl do vědy optimální, objektivní
Pravidlo efektu identity" 280 "Předinstitucionální" teorie alokace zdrojů 301 "Nástroj" 138 Optimální kritérium 71 "Cena" firmy 390 "Princip nedostatečného důvodu" 112 "Příroda" 281 "Produktivní matrice" 189
Teorie alokace zdrojů a vytváření příjmů v učebnici mikroekonomické analýzy jsou uvedeny v části Trhy pro výrobu fluoru. Obecný plán zvažování problémů v této době nezůstal nezměněn od vydání knihy A. Marshe Principles of Economic Theory market, capital market and land rii. Poptávka firem po faktorech je tradičně spojena s mezním produktem těchto faktorů a nabídkou - s očekávaným jednotkovým příjmem. Tradičně učebnice zvažují elastickou poptávku po každém faktoru, která závisí jak na zastupitelnosti, tak na komplementaritě faktorů technologií.
Nebo bychom možná mohli rozlišovat mezi teorií stacionární rovnováhy a teorií pohyblivé rovnováhy, což znamená teorii systému, ve kterém měnící se představy o budoucnosti mohou ovlivnit současnou situaci. Význam peněz pramení především z toho, že jsou pojítkem mezi přítomností a budoucností. Můžeme analyzovat, jaké rozdělení zdrojů mezi různá použití je slučitelné s rovnováhou za normálních ekonomických motivů ve světě, ve kterém jsou naše představy o budoucnosti pevné a ve všech ohledech spolehlivé, a dále rozdělení mezi ekonomiku, která se nemění, a ekonomiku to podléhá změnám je možné, ale tam, kde jsou všechny události předvídány od samého začátku. Na druhou stranu můžeme přejít od tohoto zjednodušujícího modelu k problémům reálného světa, kde naše projekce do budoucna nemusí být proveditelné a kde předpoklady o budoucnosti ovlivňují to, co děláme dnes. Právě když provedeme tento přechod, měly by do našich výpočtů vstoupit peníze se svými speciálními vlastnostmi spojnice mezi přítomností a budoucností. Ale ačkoliv teorie pohyblivé rovnováhy musí být nutně vyjádřena v termínech peněžní ekonomiky, zůstává teorií hodnoty a distribuce, a vůbec ne samostatnou „teorií peněz“. Peníze jsou ze své podstaty především důmyslným prostředkem komunikace mezi přítomností a budoucností. Proto ani začít objasňovat dopad měnících se představ o budoucnosti na naše současné aktivity nemůže být jinak než z hlediska peněz. Peněz se nemůžeme zbavit, i když zničíme zlato, stříbro a další zákonná platidla. Specifické problémy peněžní ekonomiky budou vyvstávat i nadále, dokud budou existovat trvalé JAKFIB schopné převzít funkci
Vrcholným úspěchem axiomatického přístupu je teorie dokonalé konkurence. Navzdory tomu, že byl poprvé navržen asi před dvěma sty lety, nebyl nikdy překonán, pouze se zlepšila metoda analýzy. Teorie tvrdí, že za určitých, velmi specifických okolností vede neomezená touha po uspokojení vlastních zájmů k. Rovnovážného bodu je dosaženo, když je úroveň produkce společnosti taková, že mezní náklady se rovnají tržní ceně statku, a každý spotřebitel, když nakupuje, obdrží takové množství statku, že jeho celková mezní „užitečnost“ se rovná na jeho tržní cenu. Výzkumy ukazují, že rovnovážný stav maximalizuje výhody všech účastníků za předpokladu, že žádný kupující ani prodávající nemůže ovlivnit tržní ceny. Právě tento způsob uvažování sloužil jako teoretický základ pro politiku laissez faire, která dominovala v devatenáctém století, a také slouží jako základ pro moderní představy o „magické síle trhu“.
Světový kapitalistický systém je podporován ideologií, která má kořeny v teorii dokonalé konkurence. Podle této teorie mají trhy tendenci k rovnováze a rovnovážná pozice znamená nejefektivnější alokaci zdrojů. Jakákoli omezení svobody hospodářské soutěže snižují účinnost tržního mechanismu, a proto je třeba se jim bránit. Tento přístup jsem výše popsal jako ideologii volného trhu (laissezfaire), ale tržní fundamentalismus je lepší termín. Faktem je, že fundamentalismus předpokládá určitý druh víry, kterou lze snadno dovést do extrémů. Je to víra v dokonalost, víra v absolutno, víra, že každý problém musí mít řešení. Fundamentalismus předpokládá přítomnost autority s dokonalými znalostmi, i když tyto znalosti nejsou běžným smrtelníkům dostupné. Bůh je takovou autoritou a v naší době se věda stala její přijatelnou náhradou. Marxismus tvrdil, že má vědecký základ, stejně jako tržní fundamentalismus. Vědecký základ pro obě ideologie se vyvinul v 19. století, kdy věda stále slibovala vlastnictví konečné pravdy. Od té doby jsme si mnohé uvědomili
Pop Per zaútočil na marxismus a freudovskou psychoanalýzu na základě toho, že tyto teorie, stejně jako mnoho jiných, prohlašovaly, že jsou vědecké, ale nebylo možné je testováním prokázat jako nepravdivé, takže jejich tvrzení byla nepodložená. S tím souhlasím, ale půjdu ještě dál. Myslím, že argument, který použil proti marxismu, platí i pro tak vysoce respektované teorie, jako je teorie dokonalé konkurence, která hlásá, že za určitých podmínek neomezené sledování vlastního zájmu vede k co nejefektivnější alokaci zdrojů. Nechci ničit ekonomiku, myslím, že je to velmi elegantní teoretický konstrukt. Zpochybňuji její použitelnost v reálném životě a nejsem si jistý, zda obstojí ve zkoušce finančních trhů. Domnívám se, že činnost Quantum Fund sama o sobě dokazuje nepravdivost teorie náhodných procházek.
Zakladatelem této teorie je anglický filozof I. Bentham (1748-1832), který tomu věřil. filozofie nemá o nic hodnotnějšího povolání než podporovat ekonomiku v každodenním životě. Pro utilitaristy je potěšení cílem veškerého jednání a etika se redukuje na optimální alokaci zdrojů pro cíl největšího potěšení. Jsou přesvědčeni
D. r. - základní koncept moderní ekonomické vědy, poprvé představený do domácí vědy příznivci
ISSN 1992-6502 (tisk)_
2014. V. 18, č. 1 (62). s. 186-197
QjrAQnQj
ISSN 2225-2789 (online) http://journal.ugatu.ac.ru
MDT 621,35, 004,02
L. V. Kantorovich's Theory of Optimální využití zdrojů v problémech řezání-balení: Přehled a historie vývoje metod řešení
Yu. I. Valiakhmetova, a. S. Filippová
1 Bashkir State Agrarian University (BSAU) 2 Bashkir State Pedagogical University. M. Akmulla (BSPU)
Přijato 04.02.2014
Anotace. Jsou uvedeny příklady prohlášení o problémech řezání-balení, jejichž relevanci potvrzuje jejich rozmanitost a všestrannost aplikovaného významu. Zásadní pro vývoj metod řešení takových problémů byly práce L. V. Kantoroviče. Je uveden přehled metod pro řešení klasických problémů řezání-balení vyvinutých sovětskými a ruskými vědci za posledních 80 let, včetně vědeckých škol SSSR a Ruska. Jsou uvedeny stručné popisy metod a historie jejich vývoje.
Klíčová slova: řezání; balík; racionální využívání zdrojů; optimalizace; přesné metody; heuristické metody, algoritmy
Věnováno 100. výročí narození laureáta Nobelovy ceny L. V. Kantoroviče
ÚVOD
Příspěvek pozoruhodného a talentovaného vědce Leonida Vitalieviče Kantoroviče do různých oblastí matematiky a ekonomie měl velký význam pro rozvoj řešení aplikovaných výrobních problémů. Jeho koncept optimálního ekonomického modelu na makroekonomické úrovni má navíc stále velký potenciál. A v projevu švédského profesora Ragnara Bentzela, který pronesl v roce 1975 a představil laureáty Nobelovy ceny za ekonomii L. V. Kantoroviče a T. Koopmanse, byl univerzální význam tohoto konceptu pro jakoukoli ekonomiku bez ohledu na její společensko-politickou podobu. poznamenáno: nabídka produktivních zdrojů je všude omezená, každá společnost se potýká s řadou problémů souvisejících s optimálním využíváním dostupných zdrojů a spravedlivým rozdělením příjmů mezi občany. Hledisko, ze kterého lze takové normativní otázky posuzovat, nezávisí na politickém uspořádání dané společnosti. Proto výzkum a vývoj metod
Tato práce byla podpořena grantem RFBR 12-07-00631-a.
řešení problémů racionálního využívání zdrojů jsou aktuální dodnes.
1. ZÁKLADNÍ METODY
OPTIMÁLNÍ VYUŽITÍ ZDROJŮ
Zásadní roli ve formování a rozvoji teorie optimálního využití zdrojů a lineárního programování sehrála brožura vydaná profesorem L. V. Kantorovičem v roce 1939, která se zabývala různými praktickými problémy organizace výroby, v nichž bylo požadováno najít nejlepší řešení. Kniha byla napsána po konzultaci se zaměstnanci Plywood Trust o řešení problémů, které v té době nebylo možné řešit tradičními metodami. L. V. Kantorovich navrhl metodu řešení faktorů (indexů), která zakládá zásadní možnost nalezení nejlepšího řešení mnoha problémů národního hospodářství, včetně problému masového řezání. Přes obrovský rozsah vědeckých zájmů se L. V. Kantorovich v dalších letech opakovaně vracel například k problému racionálního řezání.
Ve 30. letech. minulého století byly položeny základy pro teorii řezání pilařských surovin, jejímž zakladatelem byl H. L. Feldman. Navrhl matematický přístup pro
řešení problému maximálních poloh při řezání kmenů. Spolu se svými následovníky vytvořil systém zaměřený na maximalizaci objemové a kvalitní výtěžnosti omítaného řeziva. Přesné matematické schéma řešení plně nezohledňovalo reálné podmínky, jako jsou kvalitativní charakteristiky surovin a řezaných výrobků, takže výsledky v praxi mohly být nesprávné. Později V. A. Zalgaller vyvinul grafickou metodu sestavování maximálních množin, založenou na geometrickém znaku extrému. Metoda navržená V. A. Zalgallerem umožnila přiblížit teorii maximálních dodávek podmínkám výroby.
Rozpracovaná a zdokonalená teorie však stále nemůže dát odpověď na mnohé problémy pilařské techniky, a proto je její další zdokonalování relevantní. Mezi hlavní důvody tohoto jevu patří: technický pokrok, změny rozměrových a kvalitativních charakteristik řezaných surovin vstupujících do řezu a jejich horninového složení, zpřísnění ekologických požadavků, změny stávajících norem pro suroviny a řezané výrobky.
2. ROZMANITOST STŘIH A BALENÍ
Řezné úlohy jsou důležitým technologickým problémem, jehož optimální řešení umožňuje minimalizovat spotřebu dostupných zdrojů. Jsou to úkoly jako:
Řezání lineárního materiálu;
Podélné řezání pásek a rolí;
Řezání listů na obdélníkové polotovary;
Použití materiálů různé délky;
Řezání sériových a nesériových výrobků;
3D balení kontejnerů;
Řezání kudrnatých polotovarů;
Umístění kruhů;
Geometrické pokrytí oblastí s překážkami prvky různých tvarů;
Problém výběru nejlepších rozměrů materiálu pro následné řezání;
Balení/obal s prvky náhodných velikostí,
a mnoho dalších.
S podobnými úkoly se v praxi setkáváme ve strojírenství, hutnictví, dřevozpracujícím průmyslu.
zpracovatelský a oděvní průmysl, celulózový a papírenský průmysl atd.
Mnoho úkolů, které na první pohled nepatří do třídy problémů s řezáním a balením, nakonec sejde na ně. Například problémy s plánováním, problémy se směrováním, problémy s rozkladem vícenásobně spojených ortogonálních polygonů a mnoho dalších aplikovaných problémů.
Pokud je hodnota řezaného zdroje vysoká, jsou v praxi uvažovány i zbytkové úkoly: pokusí se využít odpad vzniklý při řešení předchozích úkolů řezání, balení nebo geometrického pokrytí.
Úkoly řezání, balení nebo povlakování se mohou vyskytovat jako mezičlánek v jiných úkolech nebo se mohou střídat v rámci jednoho úkolu. Můžeme uvažovat například logistický problém, kdy je každému vozidlu přiřazena trasa pro spotřebitele a soubor zboží odpovídající těmto spotřebitelům. Úkolem třídy řezání-balení je pak hledání trasy každého vozidla a také nalezení plánu umístění zboží do nákladového prostoru. Při umisťování zboží navíc můžete zohlednit pořadí vozidla - tak, aby se jako první naložilo zboží určené pro posledního klienta.
Každá z tematických oblastí přináší své vlastní dodatečné požadavky na způsob řešení problémů a následně i na způsob adaptace známých algoritmů.
Tento článek poskytuje stručný přehled metod řešení klasických problémů řezání-balení vyvinutých sovětskými a ruskými vědci za posledních 80 let. Úlohy Cutting and Packing (C&P) jsou chápány jako široká třída problémů, které umožňují různé aplikované interpretace. Mezi ně patří následující úkoly:
Řezání materiálu (při řezání do určitých obrobků minimalizace výchozího materiálu);
Husté rozmístění geometrických objektů v dané oblasti (umístění zboží, zboží ve skladu atd.);
Balicí kontejnery (umístění položek do omezené oblasti);
Volba sortimentu (výběr při objednání jedné velikosti od standardních);
Uspořádání prostor (maximalizace užitných ploch při plánování s ohledem na technologické požadavky);
Zajištění rytmu výrobního procesu (problémy plánování, plánování víceprocesorových systémů);
Distribuce výrobních kapacit (přidělování počítačové paměti);
Problém nastavení v pilařství (poloha pil při řezání kmene na desky různé tloušťky, volba počtu pil pro maximalizaci výnosu);
Řezání kmene stromu na délku (maximalizace produkce při řezání kmene na kulaté sortimenty);
Prkénka na krájení (řezané na přířezy, které jsou blíže konečnému produktu; obejít defekty a maximalizovat celkovou kubaturu nebo celkovou komerční cenu);
Řezání listového materiálu na náhodné přířezy (řezání materiálu s přihlédnutím ke zpoždění při výrobě přířezů);
Maximální (minimální) geometrické pokrytí (uspořádání minimálního počtu kusů zařízení v dané oblasti) atp.
Každý z nich může být zase specifikován různými způsoby.
Společné pro problémy této třídy je přítomnost dvou skupin objektů. Mezi prvky těchto skupin se vytváří a hodnotí korespondence. Existují problémy lineárního (jednorozměrného), pravoúhlého (dvourozměrného) a rovnoběžnostěnného (trojrozměrného) řezání-těsnění. Mezi těmito úkoly vyniká řezání a balení gilotinou. Zvláště zdůrazněna je problematika vnořování - umístění součástí složitých geometrických tvarů do určených oblastí. U nich vystupují do popředí informační problémy nastavení obrazců, účtování a zajištění jejich neprotínání, kódování atd. Výčet geometrických vlastností obrobků a materiálu lze doplnit a zohlednit v matematickém modelu některým fyzikálním a / nebo ekonomické ukazatele. Podrobná klasifikace hlavních modelů úkolů C&P v Rusku je uvedena v.
Ve 40. letech. metody řešení hnízdních problémů byly zaměřeny především na problémy hromadné výroby, kde může být integrita výsledků zanedbaná. Metoda navržená L. V. Kantorovičem pro řešení takových problémů umožnila najít optimální řezání, avšak pracnost procesu ručního řešení vyžadovala přizpůsobení se výrobním podmínkám a zdokonalení výpočetního matematického aparátu. Právě toto číslo bylo věnováno především vědeckému vývoji následovníků a spolupracovníků L. V. Kantoroviče do 50.–60. Dále bylo možné implementovat algoritmy na počítači. Programy umožnily najít optimální plány pro řezání rozměrových lineárních materiálů a optimální plány pro řezání obdélníkových plechů na obdélníkové přířezy. Od 70. let. zvláštní pozornost badatelů v této oblasti byla zaměřena na řešení problémů jednorázové a malosériové výroby.
Problematiku řezání poprvé podrobně rozpracoval L. V. Kantorovič spolu s V. A. Zalgallerem v leningradském oddělení Matematického ústavu Akademie věd SSSR ve 40. letech. . Praktická zkouška úspěšnosti jimi vyvinutých matematických řešení byla provedena v Leningradských vozících v letech 1948-1949. S ohledem na technologické požadavky a složitost výpočtu způsobu řešení faktorů bylo vynaloženo mnoho práce na vývoji a přizpůsobení matematického aparátu tehdejší výrobní realitě zaváděním nových výpočtových a technologických metod. V. A. Zalgaller tedy vyvinul metodu pro výběr celočíselných indexů, navrhl řešení ploché úlohy pomocí pomocné lineární úlohy, metody pro řezání různě dlouhého materiálu a různá technická zařízení. Všechny vyvinuté a prakticky vyzkoušené metody té doby, metodika jejich použití byla popsána v knize „Rational Cutting of Industrial Materials“, vydané počátkem roku 1951. Řezné problémy byly autory považovány za příklady aplikace lineárního programování (Linear Programming, LP). Při řešení úloh vnořování se používá LP model s implicitně specifikovanými informacemi o vnořování (maticové sloupce). Tato kniha byla ve skutečnosti zprávou o úspěšné praktické realizaci v letech 1948-1949. lineární programování pro řešení průmyslových problémů. První zahraniční publikace věnované LP,
pocházejí z roku 1949. Hlavní výpočty uvedené v knize byly provedeny ručně. K překonání obtíží spojených s konstrukcí platných řezných tabulek autoři navrhli techniky, které v podstatě předjímaly myšlenky dynamického programování.
K vyřešení problému generování vnoření byly vyvinuty metody založené na dynamickém programování pro problém lineárního vnořování, pro gilotinové vnořování - metoda mřížky pro generování vnoření s maximálním skóre zohledňující úplnou indexovou tabulku. I. V. Romanovskij navrhl způsob lepení omezený na stavy odpovídající skokům. Později E. A. Mukhacheva vyvinul podmíněné metody pro generování řezů v každém kroku procesu lineárního programování s přihlédnutím ke specifikům skutečné výroby. V té době bylo hlavním cílem těchto a mnoha dalších prací aplikace lineárního programování v oblasti výrobních problémů. Tohoto cíle bylo do jisté míry dosaženo v podmínkách sériové a sériové výroby.
3. ČINNOST SOVĚTSKÝCH VĚDECKÝCH ŠKOL PŘI STUDIU PROBLEMATIKY ŘEZNÉHO BALENÍ
Tento směr byl nepochybně vyvinut a široce používán s příchodem počítačů: například první softwarová implementace na počítači metody indexové škály. V metodě a programu pro racionální řešení hromadného lineárního problému je uveden, strávit přijatelný čas na výpočet. Výpočet racionálních map pro řezání pravoúhlých plechů v 60. letech. pro velký počet přířezů (více než 60) prakticky nebylo možné. A příklady menších rozměrů vyžadovaly mnoho hodin počítačových programů.
Tedy využití počítačů k řešení a studiu problému hromadného řezání na počátku 60. let. minulého století byl prvním krokem ke vzniku ufánské vědecké školy pod vedením E. A. Muchačeva. Elita Alexandrovna Mukhacheva v roce 1962 vstoupila do postgraduálního kurzu Akademického města Novosibirsk Ústavu matematiky sibiřské pobočky Akademie věd SSSR v oddělení tvůrce teorie lineárního programování Leonida Vitalieviče Kantoroviče a dostala za úkol vývoj programu pro hromadné řezání materiálu, výsledek je popsán v.
Priorita L. V. Kantoroviče v této oblasti byla již ve světě uznávána, měl na starosti katedru matematiky a ekonomiky. Vědeckým poradcem Elity Aleksandrovna se stal pracovník katedry, student a kolega L. V. Kantoroviče, doktor fyzikálních a matematických věd G. Sh. Rubinshtein. Počátkem roku 1967 obhájila disertační práci „Numerické metody pro řešení některých tříd úloh lineárního programování“ pro stupeň kandidáta fyzikálních a matematických věd1. Od té doby probíhá aktivní výzkum v této oblasti na Státní letecké technické univerzitě v Ufě.
Pro problémy s kusovou výrobou, které jsou ze své podstaty diskrétními optimalizačními problémy, je řešení LP zjednodušením, které vám umožní získat výsledek blízký optimálnímu, s dalšími omezeními, která vznikají při sériové a hromadné výrobě. V budoucnu byly problémy C&P považovány bez tohoto zjednodušení za aplikované problémy kombinatorických problémů v operačním výzkumu. C&P problémy jsou typickými představiteli NP-těžkých problémů. Vzhledem k nepolynomiální složitosti exaktních algoritmů pro C&P problémy věnují autoři mnoha prací stále značnou pozornost aproximativním metodám a při vývoji přesných algoritmů postupům pro redukci vyčerpávajícího výčtu a počítání dolních odhadů.
Při řešení problémů C&P je nutné minimalizovat použitý materiál (kvantitativní
1 V roce 1983 obhájila E. A. Mukhacheva (1930-2011) svou doktorskou disertační práci „Aplikované problémy kombinatorické optimalizace, zejména problém řezání a balení“ a stala se první doktorkou věd na UAI (Ufa Aviation Institute). Při zpracování disertační práce konzultovala s L. V. Kantorovičem, V. A. Zalgallerem a v akademickém městě Novosibirsk. Z 59 let práce na Ufa Aviation University (UAI, USATU) vedla katedry 34 let. Vědecký význam děl E. A. Mukhacheva a jejích studentů je kolosální. Studenti, postgraduální studenti, vědci naší země studovali matematické programování, matematické metody operačního výzkumu, teorii a metody výpočtu v úlohách řezání-balení podle učebnic, monografií a článků od E. A. Mukhacheva. Mnoho jejích následovníků se dodnes rozvíjí v Rusku i v zahraničí. Výsledky četných prací byly implementovány například v závodě Kirov (Leningrad), při výrobě traktorů v strojním závodě Iževsk, v leteckém komplexu Uljanovsk atd.
v, ploše nebo objemu). V tomto případě bude optimální hodnota větší nebo rovna dolní hranici a menší nebo rovna horní hranici.
Pomocí hranic se vyhodnocuje řešení získané tou či onou metodou. Například horní mez získaná přibližně libovolnou heuristickou metodou a upřesněná v průběhu výpočtů se v metodě větvení a vazby používá k redukci množiny prohlížených uzlů rozhodovacího stromu: uzlů s odhadem ne menším než horní vázané jsou eliminovány.
Při řešení problémů pomocí exaktních metod může použití hranic zkrátit dobu běhu algoritmu. Více času přesného algoritmu je tedy vynaloženo na prokázání optimálnosti nalezeného řešení, získaného případně již na začátku výpočtů. Pro tuto fázi je velmi důležitá spodní hranice, jejíž hodnota by se měla co nejvíce blížit optimu. Problém výpočtu dolních odhadů zůstává hlavním problémem ve vývoji účinných exaktních metod pro řešení problémů C&P. U výpočtů jsou zvláště zajímavé upravitelné dolní meze, které umožňují buď rychle odříznout „slabá“ dílčí řešení, nebo jednoduše zastavit výpočty, když je dosaženo dostatečně dobrého výsledku. Je navržena metoda pro konstrukci dolních odhadů založená na lineární relaxaci. Je ukázáno, že optimální hodnotu původní úlohy lze odhadnout řešením příslušné úlohy lineárního řezání. Je navrženo zpřesnění této spodní hranice pomocí metody fixace určitých proměnných.
Tradiční pro jednotlivé C&P problémy jsou matematické modely celočíselného lineárního programování (ILP). Ale je třeba poznamenat i další, například ty, které byly navrženy na začátku 21. století: maticový model je reprezentace pravoúhlého obalu dvěma binárními maticemi charakterizujícími všechny možné průsečíky obdélníků s částmi oblasti kontejneru rovnoběžnými s osami souřadnic. ; model navržený V. N. Markovem, ve kterém je list materiálu popsán rastrovou sekvencí bodů.
Metody založené na CLP se ukázaly jako přijatelné pro řešení problémů lineárního (jednorozměrného) a gilotinového řezání. Pokud jde o třídy negilotinových problémů s balením, LP algoritmy lze jen stěží považovat za vhodné pro jejich řešení. Zatím pro tyto úkoly většina existujících přesných metod
Metody řešení jsou redukovány na výčet celého souboru proveditelných řešení. Vylepšené metody výčtu jsou pro tyto úlohy také kombinovány pod názvem "metody větví a vazeb". V roce 1973 IV. Romanovskij a NP Khristova navrhli metodu dichotomie pro řešení diskrétních problémů minimaxu. K získání dolní meze pro v autoři navrhli použít relaxaci problému, přechod od množiny proveditelných řešení k některým z jejích podmnožin.
V 60. letech. v Charkově se pod vedením V. L. Rvacheva a Yu.G. Stojana rozvíjejí přístupy k řešení problémů s tvarovanými polotovary. Pro popis obrazců ohraničených obrysem konečného počtu segmentů a oblouků kružnic se zavádí speciální typ R-funkcí, které umožňují určit, zda bod patří obrazci jednou nerovností, což umožňuje zjednodušit ověření vzájemného neprotínání obrazců. Hledání optimálních umístění se provádí skládáním velkého počtu náhodných nepřekrývajících se pozic, z nichž každá je následně převedena gradientovou metodou do lokálně minimální polohy. Tento přístup byl dále rozvíjen. R-funkce, používané jako prostředek matematického a počítačového modelování, významně přispěly k formalizaci 2D a 3D C&P problémů ak vývoji metod jejich řešení.
Je třeba poznamenat, že k teorii a praxi modelování umístění geometrických objektů významně přispěla vědecká škola Yu. G. Stoyana (Ukrajina, Ústav problémů strojního inženýrství Národní akademie věd). Na konci 60. let. Na bázi Ufa Aviation Institute pod vedením E. A. Mukhacheva vzniká další vědecká škola, ve které se dodnes aktivně zabývají problémy C&R, včetně problémů s libovolnou formou obrobků. Od 60. let. studie problémů řezání obrazců se provádějí na Gorkého univerzitě v týmu L. B. Belyakové v Ústavu technické kybernetiky Akademie věd BSSR, Minsk. Současně se v mnoha průmyslových podnicích SSSR používají zjednodušené algoritmy pro řešení problémů tvarového řezání s použitím počítačů.
Další přehled publikací před 70. lety. uvedena v přepracovaném druhém (1951) a třetím (2012) vydání knihy. Třetí vydání bylo připraveno za účasti V. A. Zalgallera.
ciálních podmínek týkajících se různých průmyslových odvětví: hutnictví, stavby lodí, dřevozpracujícího, papírenského a oděvního průmyslu. Například v Karelském institutu lesního průmyslu pod vedením I. V. Soboleva, na Petrozavodské státní univerzitě pod vedením V. A. Kuzněcova probíhají práce související s aplikací optimalizačních metod v průmyslových podnicích v Karélii a severozápadním Rusku. Zde se vyvíjejí metody řešení optimalizačních problémů v celulózovém a papírenském průmyslu. Jsou realizovány v komplexech aplikovaných programů zaměřených na řešení problémů spojených s řeznými a plánovacími pracemi v dřevozpracujícím průmyslu. Kromě úkolů přímo souvisejících s řezáním se při organizaci výroby zvažují technologické problémy: pro snadnou montáž je nutné vyrábět současně nebo téměř současně všechny součásti aktuálně vyráběného produktu a vlastnosti předběžného řezání omezit možnost pokládání těchto dílů do obdélníků, což vede k velkému odpadu . Jedná se například o řezání kulatiny, řezání vlnité lepenky.
V 70. letech. na Omské státní univerzitě pod vedením A. A. Kolokolova také začíná výzkum a vývoj algoritmů pro řešení diskrétních optimalizačních problémů, které jsou redukovány na cut-packing problémy. Hlavní pozornost této vědecké skupiny je věnována problematice lineárního celočíselného programování, aplikovaným problémům umístění, problémům stříhání v lehkém průmyslu a oděvní výrobě. Byly vyvinuty a zkoumány nové algoritmy a přístupy založené na použití pravidelných dělení relaxačních množin, L-partitionů. Je třeba poznamenat, že problémy s automatizací procesu řezání se v novosibirském Omsku řeší dodnes. Je uveden přehled stávajících CAD systémů pro návrh a technologickou přípravu oděvní výroby. Přestože hlavním úkolem těchto systémů je modelování jednotlivých a malosériových oděvů, proces řezání materiálu nevyužívá složité optimalizační metody výpočtu. Lze zaznamenat práce A. A. Petunina prováděné v Jekatěrinburgu od konce 70. let, které jsou zaměřeny na automatizaci návrhu řezání listového materiálu. Později umožnili vyvinout univerzální systém "Sirius" s vlastním
výkonné grafické uživatelské rozhraní pro širokou škálu zařízení pro řezání plechů.
4. MODERNÍ VÝVOJ METOD PRO ŘEŠENÍ PROBLÉMŮ S BALENÍM
Nové účinné přesné metody byly vyvinuty v několika směrech. Na jedné straně byly zdokonaleny nástroje ILP: modelování, metody větvení, řezné roviny. Na druhou stranu se vyvinuly čistě kombinatorické metody, které později v rámci metod umělé inteligence doznaly nejúplnějšího vývoje.
Například je prezentována hybridní metoda spojité optimalizace a výčtový algoritmus pro řešení problému sbalení polygonu, kde je problém sbalení obdélníků do pruhu považován za speciální případ, je vyvinuta strategie pro konstrukci soustavy soustav rovnic. a soubor pravidel pro ořezávání neperspektivních vrcholů rozhodovacího stromu. Tato metoda byla dále rozvíjena koncem 90. let.
Úloha jednorozměrného vnořování s jednoduchou úplností je nejvhodnější pro řešení kombinatorickými metodami. Jednou z prvních byla metoda větvení a vazby založená na LP relaxaci s generováním sloupců. Ve většině variant metody se větvení provádí na samostatných sloupcích. V tomto článku autor používá pro tento problém dichotomickou verzi zobecněné metody pro řešení diskrétních úloh minimaxu. V něm v každé fázi dochází k větvení podél rozhodovacího stromu na dvě podmnožiny, což snižuje výčet proveditelných řešení. Pro problémy jednorozměrného řezání s celočíselnou úplností - 1D problém řezného materiálu (1DCSP) - jsou metody ILP účinnější díky kombinatorické explozi. Většina z nich využívá model 1DCSP s generováním sloupů, který poprvé navrhli L. V. Kantorovich a A. A. Zalgaller. Tento model má velmi malou empirickou dualitu. Počet proměnných modelu není v dimenzi problému (počet položek) polynomiálně omezen, takže odhadnout počet vygenerovaných sloupců při hledání optima je poměrně obtížné. V praxi je velmi aktuální problém rychlého nalezení optima LP, tedy otázka urychlení konvergence procesu generování kolon.
Otázka efektivní aplikace exaktních kombinatorických metod pro řešení problémů velkorozměrného řezání-balení je stále otevřená. Probíhá výzkum s cílem identifikovat mezní hodnoty, které se vyhýbají zvažování symetrických variant pravidel redukce výčtu. Například u metody s postupy dominance se uvažuje seskupování, stanovení přípustné rezervy, což umožňuje snížit výčet.
Matematický aparát, který umožňuje vypočítat optimum v negilotinovém C&P problému v konečném počtu operací, byl poprvé navržen v roce , kde je problém obdélníkového balení formulován jako kombinatorický optimalizační problém a je navržena „zónová metoda“ k nalezení optimální řešení. Na základě konceptu „zón“ je dokázáno, že pro jakékoli balení obdélníků lze určit jejich pořadí, ve kterém se každý další obdélník neprotíná s žádnou z předchozích zón (topologické řazení). Ukazuje se, že mezi obaly postavenými na stupňovitých hranicích existují optimální. Aby se snížil počet možností, byla navržena řada omezení, která umožňují vyřadit možnosti, které jsou symetrické k těm, které již byly zvažovány, nebo které zjevně nejsou lepší než jiné.
Heuristické metody se úspěšně používají k řešení kombinatorických úloh ze třídy NP-těžkých. Mezi heuristikami na vysoké úrovni vynikají chamtivé algoritmy, které umožňují dosažení horních hranic. Víceprůchodová heuristika zahrnuje metodu sekvenčního zpřesňování odhadů (Sequential Value Correction, SVC), vycházející z myšlenky objektivně stanovených odhadů L. V. Kantoroviče. Metoda SVC je implementována podle upraveného schématu prvního fitování s postupy priority a opakování. Řazení prvků je založeno na ekonomickém smyslu duálních proměnných v lineárním programování. Metodu lze nazvat obecnou pro řešení problémů C&P: je použitelná pro lineární a gilotinové řezání, 2D a SD balení, stejně jako pro tvarové skládání.
Při implementaci schémat pro konstrukci řešení v kombinatorických úlohách se používají různé způsoby reprezentace proveditelného řešení ve formě kódu, který se pomocí příslušného pravidla (dekodéru) jednoznačně převede na plán balení. Způsoby kódování a dekódování výrazně ovlivňují efektivitu výsledných řešení. V tomto případě je samotný dekodér jednoprůchodový
todom. Jednoduchým a oblíbeným dekodérem je dekodér „vlevo dole“, který unikátním způsobem umožňuje získat plán balení podle kódu ve formě sekvence (seznamu) obdélníkových dílů. Tým Ufa vyvinul nové blokové dekodéry, které umožňují reprezentovat pravoúhlý balík ve formě lineárního řezání speciální struktury, pro kterou se používají lineární metody řešení, díky nimž jsou získána rychlá a efektivní řešení. Totéž platí pro 3D balení.
Pokud se zvolenou metodou dekódování zopakujeme řešení a mírně změníme již použitý kód, pak se hodnota účelové funkce změní k lepšímu nebo horšímu. Opakovaným opakováním můžete získat poměrně dobré řešení. Na tomto principu, v kombinaci s kombinací různých dekodérů, byly vyvinuty technologie pro konstrukci lokálních vyhledávacích algoritmů pro C&P.
Zavedení prvků náhodnosti do deterministického algoritmu tedy zvyšuje jeho účinnost. Takže například účinnost výše zmíněného SVC algoritmu se zvýšila poté, co do něj byly vloženy stochastické prvky. Rychlý vývoj pravděpodobnostních metod pro místní optimální vyhledávání začal před 20 lety s příchodem metaheuristiky pro řešení NP-těžkých problémů. V Rusku je přehled pravděpodobnostních metod pro místní optimální hledání NP-těžkých problémů uveden v . Recenze pojednává o obecných schématech tabuizovaných vyhledávacích algoritmů, simulovaného žíhání, evolučních a genetických algoritmů. Je ukázáno, že tyto algoritmy, odlišné svou strukturou, využívají obecnou matematickou konstrukci konečných Markovových řetězců, a je také prokázáno, že při správné implementaci vyhledávacích procedur pro tyto metaheuristiky, kdy nedochází k „zaseknutí“ v lokálním optimu bude pozorována konvergence pravděpodobnosti nejlepšího nalezeného řešení k optimálnímu řešení problémů.
Mezi komplexní metaheuristikou pro problémy C&P byly jako první použity genetické algoritmy. Existují různé způsoby kódování a techniky pro identifikaci nejjednodušších struktur (gen, alely, chromozomy). To dává vzniknout různým třídám genetických algoritmů. Úspěšně se vyvíjejí i genetické algoritmy pro řešení problémů tvarového řezání. Zkoumají se a používají se i další metaheuristika. Navíc v nedávné
V průběhu let se využití umělé inteligence aktivně rozvíjí.
Změny v zemi, které začaly v 80. letech 20. století, umožnily ruským vědcům aktivně publikovat svou práci v zahraničí v časopisech věnovaných operačnímu výzkumu a účastnit se mezinárodních konferencí. Komunita s názvem SICUP (Special Interest Group on Cut-and-Pack) sdružuje mnoho výzkumníků zajímajících se o tuto problematiku po celém světě. SICUP pořádá zasedání o otázkách C&D v rámci mezinárodních konferencí. Bylo rozhodnuto zorganizovat novou komunitu ESICUP (http://pagmas.fe.up.pt/~esicup/tiki-
index.php). A obrácená situace je například účast zahraničních badatelů na ruských speciálních edicích, společných výzkumech.
V SSSR se vědecké a praktické semináře a konference konaly v Leningradu, Ufě, Zvenigorodu a dalších městech. V moderní době jsou v rámci konferencí organizovány sekce: Matematické programování a aplikace (Jekatěrinburg, IMM URO AN RF); Diskrétní analýza a operační výzkum (DAOR, Novosibirsk, IM SB RAS); Počítačová věda a informační technologie (CSIT, Ufa, USATU); Technologie šetřící zdroje (OPTIM, Petrohrad); Optimalizační metody a jejich aplikace (Bajkal International Conference on Mathematical Programming, Irkutsk); Diskrétní matematika a ekonomické aplikace (Omsk, pobočka Ústavu matematiky sibiřské pobočky Ruské akademie věd) atd.
V posledním desetiletí zůstávají teoretické aspekty problému řezání-balení a geometrického pokrytí vzhledem k jejich NP-složitosti stále aktuální. Hlavní těžiště ruského vědeckého výzkumu metod a problémů C&P souvisí nejen se zlepšováním účinnosti metod jejich řešení, ale také s problémy, ve kterých jsou úkoly řezání a balení zahrnuty jako dílčí úkoly. To klade další podmínky a omezení při formulaci úkolů. Například: v dřevařském průmyslu, v lehkém průmyslu, při navrhování elektronických obvodů, v dopravní a skladové logistice, ve stavebnictví a lodním průmyslu atd.
Takže například články zkoumají problémy plánování výroby obalů z vlnité lepenky, výběru vozidel a umísťování produktů, plánování výroby řeziva, plánování nakládky vodní dopravy, řezání a vychystávání v modelu
analýzy technologických procesů v podmínkách stochastiky výrobního procesu, jsou zvažována kritéria efektivnosti těchto úloh.
V práci jsou popsány teoretické předpoklady pro vytvoření automatizovaného systému řízení stříhání v oděvním průmyslu, je zkoumána problematika parametrického modelování složitých trojrozměrných objektů a jeho aplikace. Příspěvek poskytuje stručný přehled existujících CAD systémů pro návrh a technologickou přípravu oděvní výroby. Jedním z prvních vývojů v oblasti CAD pro návrháře oděvů byl běloruský systém „AVTOKROY“ (Minsk), fungující v 80. letech. v NPO "Belbyttekhnika". Prvním systémem navrženým speciálně pro navrhování oděvů pomocí osobního počítače byl systém LECO, vyvinutý Ústředním výzkumným a výrobním ústavem oděvního průmyslu (TsNIIShP). V současné době systém využívají malé šicí a pletařské podniky a také univerzity, které školí specialisty v oblasti navrhování oděvů. Po LECO se objevuje řada CAD: ASSOL System (Centrum výpočetní techniky na Moskevském institutu fyziky a technologie); Systém T-FLEX/CLOTHING využívá standardní konstrukční techniky; GRACE a další Jedním z nejnovějších vývojů byl systém ELEANDR-CAD (Vědecké a technické centrum pro design a technologii Moskevské státní technické univerzity a společnost "Eleander", 2003). V tomto článku autoři studují problém minimálního krytí na příkladu navrhování kožešinových výrobků.
Studie ukázaly, že úkoly, ve kterých je nutné v určitém smyslu vytvořit optimální soubor objektů (stroje, soubory oděvních modelů, techniky, vlastnosti), pokrývající „potřeby“ jiného souboru (práce, zákazníci, zakázky). , charakteristiky) lze za určitých podmínek vzhledem ke specifikům problémy redukovat na krycí problémy a jejich různé modifikace. Na jeho základě byl vyvinut hybridní algoritmus pro řešení problémů optimalizace výběru objektů v procesu technické přípravy výroby, včetně stanovení dominantních vlastností materiálů, na příkladu lehkého průmyslu. T. Pa-
nukova, . Autor poznamenal, že v úlohách řezání listového materiálu je plochý graf modelem řezného plánu a dráha pokrývající všechny hrany určuje trajektorii řezného nástroje. Článek prezentuje modifikaci algoritmu pro konstrukci pokrytí s uspořádaným pokrytím pro případ vícenásobně souvislého grafu. Konstrukce grafové krytiny s uspořádanou krytinou řeší uvedený problém řezání. Největší zájem je o povlaky s minimálním počtem řetězů, protože přechod z jednoho řetězu na druhý odpovídá chodu řezného nástroje naprázdno.
V práci je uveden příklad aplikace genetických algoritmů pro automatizaci umístění palivových článků různých velikostí v elektronických modulech trojrozměrného uspořádání na základě tepelného kritéria.
Řada prací je věnována řešení problému umístění nákladu v nákladových prostorech vozidel, který vzniká jako dílčí úkol v logistických systémech. Například v úloze řízení nakládky kontejnerů s přihlédnutím k jejich fyzikálním vlastnostem se u tohoto úkolu berou v úvahu podmínky technologické nakládky a vykládky spotřebního zboží, tzn. sled návštěv zákazníků při doručování zboží.
Článek navrhuje algoritmus pro řešení problému, který vzniká např. ve stavebnictví - problému geometrického pokrytí vícenásobně spojeného polygonu ortogonálním zdrojem. Počáteční informací jsou rozměry kryté oblasti a dostupného ortogonálního zdroje a rozměry krycích prvků, které je třeba následně vyříznout ze zdroje, nejsou předem určeny. To vede k multikriteriální optimalizaci procesu konstruování propojených racionálních plánů pro geometrický kryt s pravoúhlými prvky blíže nespecifikovaných velikostí a řezání ortogonálního zdroje na krycí prvky.
Technologické vlastnosti řezacího zařízení způsobují vznik problémů při návrhu řídicích programů pro stroje na řezání plechů. Autor si v práci všímá důležitosti problému ceny a významu různých fází procesu řezání polotovarů z materiálového zdroje, jako je například přesun řezného nástroje na jiné místo na stříhaném plechu a nové řezání. Kromě hustého umístění obrobků na řezném plánu je tedy objektivní funkce zaměřena na optimalizaci trasy
řezný nástroj, s přihlédnutím k nákladům na řezy, nový návazec.
Značná pozornost je věnována i teoretickému vývoji problematiky řezání a balení. Například v článcích je problematika balení vln (ortogonálně spojených polygonů) uvažována z hlediska obecné teorie problému optimálního umístění geometrických objektů, algoritmů pro balení n-rozměrných vln na základě metod lineárního programování, jako např. jsou navrženy modely a metody pro optimalizaci uspořádání n-rozměrných rovnoběžnostěnů.
ZÁVĚR
Různorodost řezných úloh spolu s důležitostí jejich racionálního řešení předurčuje nehynoucí zájem zkušených i mladých badatelů na celém světě o tuto problematiku, což je důvodem neustálého růstu počtu nových metod jejich řešení.
Problémy C&P pozoruhodným způsobem kombinují svou širokou praktickou využitelnost a příslušnost k NP-tvrdým problémům, což z této problematiky činí důležité testovací pole pro nový výzkum. Díky tomu budou myšlenky L. V. Kantoroviče využívány a rozvíjeny v různých oblastech vědecké i praktické lidské činnosti související s problémem řezání.
BIBLIOGRAFIE
1. Kantorovič L. V. Matematika, management, informatika: monografie / ed.: G. A. Leonov, V. S. Katkalo, A. V. Buchvalov, Petrohrad: Vyšší. škola Vedení: Nakladatelství Petrohradské univerzity, 2010. 575 s. [ L. V. Kantorovich, Matematika, management, informatika: monografie, (v ruštině). Edited by G. A. Leonov, V. S. Katcalo, and A. V. Buhvalov, St. Ptsb.: Management high school: St. Petersbourg University Publishing House, 2010.]
2. Kantorovič L. V. Matematické metody organizace a plánování výroby. Leningradská státní univerzita, 1939. 67 s. . [ L. V. Kantorovich, Matematické metody řízení výroby a plánování, (v ruštině). Leningrad: Leningradská univerzita, 1939.]
3. L. V. Kantorovich, Racionální metody pro řezání kovů, Proizv.-techhn. bul. NK Munice SSSR. 1942. č. 7-8. s. 21-29. [ L. V. Kantorovich, "Efektivní metody řezání kovů," (v ruštině), Product.-techn. bulletin. NK Munice SSSR, čís. 7-8, str. 21-29, 1942]
4. Feldman Kh. L. Systém maximálního nastavení pro řezání. Moskva: Gostekhizdat, 1932. [H. L. Feldman, Systém maximálního podávání pro řezání, (v ruštině). Moskva: Gostehizdat, 1932.]
5. Zalgaller V. A. Novinka v přípravě sloupků pro řezání kulatiny. L .: TsNIIL "Sevzaples", 1956. Vydání. 67. [ V. A. Zalgaller, Krok vpřed ve formaci dodávky pro řezání dřeva, (v ruštině). Leningrad: CNIIL "Sevzaples", sv. 67, 1956]
6. Valiakhmetova Yu. I., Mukhacheva E. A., Filippova A. S., Gilmanova N. A., Karipov U. A. Multimethodnaya
technologie ortogonálního balení a její aplikace v úlohách dopravní logistiky // Příloha časopisu "Information Technologies". 2009. č. 12. 31 s. [ U. I. Valiahmetova, et al., "Multimethod technology of ortogonal bin-packing and its application in transport logistic problems," (v ruštině), v příloze časopisu Information technologies, no. 12, 2009.]
7. Mukhacheva E. A., Mukhacheva A. S., Valeeva A. F., Kartak V. M. Místní vyhledávací metody v problémech ortogonálního řezání a balení: analytický přehled a vyhlídky rozvoje // Informační technologie. 2004. č. 5. Přihláška. str. 2-17. [ E. A. Mukhacheva, et al., "Metody místního vyhledávání v problémech ortogonálního řezání-balení: analytický průzkum a výhled rozvoje," (v ruštině), v příloze časopisu Information Technologies, č. 5, str. 2-17, 2004.]
8. Kantorovich L. V., Zalgaller V. A. Výpočet racionálního řezání materiálů. Lenizdat, 1951. 198 s. [ L. V. Kantorovich a V. A. Zalgaller, Výpočet efektivního řezání materiálu , (v ruštině). Lenizdat, 1951.]
9. V. A. Bulavskii a M. A. Yakovleva, „Počítačové řešení problému optimálního řezání lineárních materiálů“, Lineární programování: Trudy Nauch. Setkání o aplikaci matematiky. metody v ekonomii. výzkum a plánování. M.: AN SSSR, 1961. T. IV. s. 83-87. [ V. A. Bulavski a M. A. Jakovleva, "K řešení problémů lineárního řezání materiálu na POČÍTAČI," (v ruštině), v lineárním programování. Příspěvky z vědecké konference o aplikaci matematických metod v ekonomii. výzkum a plánování, sv. IV. Moskva: AS SSSR, 1961, pp. 83-87. ]
10. Mukhacheva E. A. Racionální řezání pravoúhlých plechů na pravoúhlé polotovary // optimální plánování: c6. vědecký tr. TAK SSSR. 1966. Vydání. 6. S. 43-115. [ E. A. Mukhacheva, "Efektivní řezání pravoúhlých listů na obdélníkové předměty," (v ruštině), v Optimální plánování: Sborník vědeckých prací SO AS SSSR, číslo 6, s. 43-115, 1966.]
11. I. V. Romanovsky, „Řešení problému řezání gilotinou metodou státního zpracování seznamu“, Cybern. 1969. č. 1. S. 102-104. [ I. V. Romanovski, "Řešení problému řezání gilotinou metodou vytřídění ze státního seznamu," (v ruštině), Kybernetika, no. 1, str. 102-104, 1969.]
12. Mukhacheva E. A. Metody podmíněné optimalizace v problému racionálního řezání plechu // Optimalizace: c6. vědecký tr. TAK SSSR. 1978. Vydání. 22. S. 83-93. [ E. A. Mukhacheva, "Metody podmíněné optimalizace v problému efektivního řezání válcování plechu," (v ruštině), v Optimalizace: Sborník vědeckých prací SO AS SSSR, 1978, číslo 22, s. 83-93. ]
13. Romanovský I. V. Program pro řešení úlohy lineárního řezání. - Optimální plánování. Novosibirsk. 1969. Číslo 12. [ I. V. Romanovski, "Program řešení problému lineárního řezání," (v ruštině), v Optimálním plánování, Novosibirsk, 1969, číslo 12.]
14. V. M. Karták, „Aktualizovaná spodní hranice pro problém balení obdélníků do polonekonečného pruhu,“ Věstník UGATU. 2008. svazek 10, č. 2 (27). s. 154-158. [V. M. Kartak, "Nová nízká hranice pro problém ortogonálního balení," (v ruštině), Věstník UGATU, sv. 10, č. 2 (27), str. 154158, 2008.]
15. Belov G., Kartak V., Rohling H., Scheithauer G. Jednorozměrné relaxace a LP hranice pro ortogonální balení // ITOR, 2009. Vol. 16. str. 745-766. [G. Belov a kol. "Jednorozměrné relaxace a LP hranice pro ortogonální balení," ITOR, sv. 16, str. 745-766, 2009.]
16. V. M. Kartak, „Matricový algoritmus pro nalezení optimálního řešení problému balení obdélníků do polonekonečného pruhu“, Informační technologie. 2008. č. 2. S. 24-30. [ V. M. Kartak, "Matrixový algoritmus pro hledání optimálního řešení pravoúhlého balení v polonekonečném pásu," (v ruštině), Informační technologie, č. 2, str. 24-30, 2008.]
17. Markov VN Znalostní báze pro negilotinové řezání-balení // Informační technologie. 2007. č. 4. S. 17-23. [ V. N. Markov, "Základní znalosti pro negilotinové řezání-balení," (v ruštině), Informační technologie, č. 4, str. 17-23, 2007.]
18. I. V. Romanovsky a N. P. Khristova, „Řešení problémů diskrétního minimaxu metodou dichotomie“, Comp. matematika a matematika. fyzika. 1973. V. 13, č. 5. S. 1200-1209. [ I. V. Romanovski a N. P. Hristova, "Řešení problémů diskrétního minimaxu metodou dichotomie," (v ruštině), J. of calculat. matematika. a matematika. Fyzika, sv. 13, č. 5, str. 1200-1209, 1973.]
19. Stoyan Yu.G., Yakovlev S. V. Matematické modely a optimalizační metody geometrického navrhování. Kyjev: Naukova Dumka, 1986. 268 s. [ U. G. Stojan a S. V. Jakovlev, Matematické modely a optimalizační metody geometrického promítání, (v ruštině). Kyjev: Naukova dumka. 1986.]
20. V. L. Rvachev a Yu. G. Stoyan, „O problému optimálního umístění kruhových vzorů“, Cybern. 1965. č. 4. [ V. L. Rvachev a U. G. Stojan, "K problému optimálního umístění kulatých vzorů," (v ruštině), Kybernetika, no. 4, 1965]
21. Stoyan Y., Terno J., Romanova T., Scheithauer G.
Konstrukce F-funkce pro dva konvexní polytopy // Applications Mathematicae. 2002. V. 2, čís. 29. S. 199-218. [Y. Stoyan, J. Terno, T. Romanova a G. Scheithauer, "Konstrukce F-funkce pro dva konvexní polytopy," Applications Mathematicae, sv. 2, č. 29, str. 199-218, 2002.]
22. Verhoturov M. A., Sergeyeva O. Y. Metoda sekvenční korekce hodnot pro problém dvourozměrného nepravidelného řezného materiálu // PO. 2000 sv. 20, č. 2. S. 233-247. [ M. A. Verhoturov a O. Y. Sergeyeva, "Metoda sekvenční korekce hodnot pro problém dvourozměrného nepravidelného řezného materiálu", sv. 20, č. 2, str. 233-247, 2000.]
23. Babaev, F.V., Racionální řezání plechu do detailů složitých geometrických konfigurací, Welding Prod. 1968. č. 8. [ F. V. Babaev, "Efektivní řezání plechů na předměty geometrických složitých konfigurací," (v ruštině), Svařovací výroba, no. 8, 1968]
24. Kantorovich L. V., Zalgaller V. A. Racionální řezání průmyslových materiálů. 3. vyd. Petrohrad: Něvský dialekt, 2012. 304 s. [ L. V. Kantorovich a V. A. Zalgaller, Efektivní řezání průmyslového materiálu, vydání 3, (v ruštině). Svatý. Petersbourg: Něvský dialekt, 2012.]
25. Sobolev I. V. Řízení výroby řeziva. M.: Lesn. prom-st, 1981. 181 s. [ I. V. Sobolev, Řízení výroby dřeva, (v ruštině). Moskva: Timber prod., 1981.]
26. Kuzněcov V. A., Shegelman I. R. Využití matematických metod a PC při těžbě dřeva. Petrohrad: SPbLTA, 1988. 68 s. [ V. A. Kuzněcov a I. R. Shegelman, Aplikace matematických metod a PC v oblastech těžby dřeva, (v ruštině). St.Petersburg: Nakladatelství St.Petersburg Ptsb, LTA, 1988.]
27. Kuzněcov V. A. Problémy řezání v průmyslu celulózy a papíru. Petrohrad: SPbLTA, 2000. 132 s. [ V. A. Kuzněcov, Řezné problémy v průmyslu celulózy a papíru, (v ruštině). Svatý. Ptsb: Nakladatelství Ptsb. LTA, 2000.]
28. A. A. Kolokolov, „O počtu řezných rovin v prvním Gomoryho algoritmu“, Problémy analýzy diskrétních informací. Novosibirsk: IEiOPP SO AN SSSR, 1975, s. 84-96. [ A. A. Kolokolov, "O počtu řezných rovin v prvním algoritmu Gomory," (v ruštině), v Problémy analýzy diskrétních informací, Novosibirsk: IEOIP SO AS SSSR, 1975, str. 84-96. ]
29. Kolokolov A. A. Regular partitions and cuts in integer programming // Siberian Journal of Operations Research. 1994. č. 2. S. 18-39. [ A. A. Kolokolov, „Pravidelné štěpení a odřezávání v programování integr,“ (v ruštině), Sibiřský časopis operačního výzkumu, č. 2, str. 18-39, 1994]
30. A. A. Kolokolov, A. B. Korobova, E. O. Zakharova a Yu. Vývoj diskrétních optimalizačních modelů pro vytvoření kolekce oblečení pro dospívající // Omsk Scientific Bulletin. 2006. č. 7 (43). s. 138-140. [ A. A. Kolokolov, et al., "Vývoj diskrétních optimalizačních modelů pro navrhování oblečení pro teenagery", (v ruštině), The Omsk vědecký bulletin, č. 7 (43), str. 138-140, 2006.]
31. Frolovskiy V. D., Frolovskiy D. V. Modelování a vývoj složitých povrchů v AutoCADu R14 // CAD a grafika. 1998. č. 3. S. 74-75. [ V. D. Frolovski a D. V. Frolovski, "Modelování a vývoj složitých povrchů v AutoCADu R14," (v ruštině), SAD a grafika, č. 3, str. 74-75, 1998.]
32. Landovsky V. V., Pishchinskaya O. V., Frolovskiy V. D. Modelování procesu navrhování oděvů pro ženské postavy s poruchami držení těla. // Novinky vysokých škol. Severní Kavkazská oblast. Sériová technika. vědy. 2009. č. 6. S. 114-118. [ V. V. Landovski, O. V. Pischinskaja a V. D. Frolovski, "Modelování procesu navrhování oděvů pro ženské postavy s vadným držením těla," (v ruštině), Bulletin nejvyšších škol, region Severní Kavkaz. Řada tech. věda, no 6, str. 114118, 2009.]
33. Korobtseva N. A. CAD oblečení: historická odbočka a přehled existujících systémů // Textilní průmysl. 2003. č. 5. S. 61-62; č. 6. S. 63-65. [ N. A. Korobtsev, „SAD oblečení: historický exkurs a přehled současných systémů,“ (v ruštině), Textilní průmysl, č. 5, str. 61-62, č.p. 6, str. 63-65, 2003.]
34. Petunin A. A. Integrovaný CAD "Sirius" pro automatizaci výroby řezání a vysekávání. Pojem. Zkušenosti s vývojem a implementací // Technologie šetřící zdroje: matematická podpora optimalizačních problémů v systémech počítačově podporovaného navrhování: So. zpráva 1. všeruský. vědecko-praktické. conf. o řešení optimalizačních problémů v průmyslu. Petrohrad: TsNIITS, 2001, s. 126-129. [ A. A. Petunin, "Integrovaný SAD "Sinus" pro automatizaci výroby řezání-logování. Koncepce. Zkušenosti s vývojem a implementací," (v ruštině), in Technologie šetřící zdroje: Matematické zajištění optimalizačních problémů v systémech projektování automatů: Sborník zpráv 1. celosvazová vědecko-praktická konference o řešení optimalizačních problémů v průmyslu, St. Ptsb: CRITS, 2001, str. 126-129. ]
35. Petunin A. A. Optimalizace trasy nástroje pro stroje na řezání plechů // Počítačové vědy a informační technologie: Intern. vědecký red.: mater. 13. stážista. conf. CSIT"2011 (Gaar-misch-Panterkirchen, Německo, 27. září - 2. října 2011). Ufa, 2011. Vol. 1. S. 179-182. [ A. A. Petunin, "Optimalizace trasy nástrojů pro stroje na řezání konstrukčních plechů , " in Proc. 13th workshop on Computer Sciences and Information Technologies, (CSIT"2011) Garmish-Panterkirhen, Německo, 2011, (v ruštině), Ufa, 2011, sv. 1, str. 179-182. ]
36. Novožilová M. V. Řešení problému hledání globálního extrému lineární účelové funkce na struktuře lineárních nerovnic: předtisk. Akademie věd Ukrajinské SSR, Inst. Charkov, 1988. 48 s. [ M. V. Novozhilova, Řešení problému globálního extrémního hledání lineární cílové funkce na základě lineární nerovnicové struktury, (v ruštině). Předtisk. AS Ukr.SSR. Ústav problémů strojírenského průmyslu. Charkov, 1988.]
37. S. B. Katsev, „O třídě diskrétních problémů minimaxu“, Kybernetika. 1979. č. 5. S. 139-141. [ S. B. Katsev, "O jedné třídě diskrétních problémů minimaxu," (v ruštině), Kybernetika, no. 5, str. 139-141, 1979]
38. Lipovetsky A. I. O optimalizaci volného umístění obdélníků // Automatizace navrhování ve strojírenství. 1985. S. 80-87. [ A. I. Lipovetski, "K optimalizaci pravoúhlého volného umístění," (v ruštině), Automation design in engineering industry, Minsk, pp. 80-87, 1985]
39. Akkuratov G. V., Berezněv V. A., Brežněva O. A.
O metodě řešení rovnice s booleovskými proměnnými // Rozhodování za nejistoty: Meziuniverzita. vědecký sobota Ufa: UAI, 1990. S. 145-154. [G. V. Accuratov, V. A. Berezněv a O. A. Brežněva, "O metodě řešení rovnice s booleovskými proměnnými," (v ruštině), Rozhodování za podmínek nejistoty. Meziústavní vědecký sborník, Ufa: USATU, pp. 145-154, 1990.]
40. Mukhacheva E. A., Zalgaller V. A. Řezné problémy s lineárním programováním // Int. J. ze softwarového inženýrství a znalostního inženýrství. 1993. V. 3, čís. 4. str. 463-476. [E. A. Mukhacheva a V. A. Zalgaller, "Linear programming cutting problems," Int. J. of Software Engineering and Knowledge Engineering, sv. 3, č. 4, str. 463-476, 1993.]
41. A. S. Mukhacheva, A. F. Valeeva a V. M. Kartak, „Problémy balení 2D kontejnerů: Nové přístupy k vývoji místních optimálních vyhledávacích metod“, Zh. M.: MAI, 2004. 193 s. [ A. S. Mukhacheva, A. F. Valeeva a V. M. Kartack, Problémy 2D balení do kontejnerů: nové přístupy k vývoji místních optimálních vyhledávacích metod, (v ruštině). Moskva: MAI, 2004.]
42. Mukhacheva A. S. Technologie blokových struktur místního optimálního hledání v problémech obdélníkového balení // Informační technologie. Slepé střevo. 2004. č. 5. S. 18-31. [ A. S. Mukhacheva, "Technologie blokových struktur pro optimální místní vyhledávání v problémech s obdélníkovým zásobníkem", (v ruštině), v příloze k časopisu Informační technologie. Dodatek, č. 5, str. 18-31, 2004.]
43. Kochetov Yu.A. Pravděpodobnostní metody lokálního hledání diskrétních optimalizačních problémů // Diskrétní matematika a její aplikace: c6. přednášky pro mládež. a vědecký škola o diskrétní matematice a jejích aplikacích. M.: Vydavatelství Centra aplikovaného výzkumu při Mech.-Math. Fakulta Moskevské státní univerzity, 2000. S. 87-117. [ U. A. Kochetov, "Pravděpodobnostní metody místního hledání diskrétních optimalizačních problémů," (v ruštině), v Diskrétní matematice a její aplikace. Sborník přednášek studentských a vědeckých škol o diskrétní matematice a jejích aplikacích, Moskva: Vydavatelství centra aplikovaného výzkumu oddělení mech. matematiky. MSU, 2000, pp. 87-117. ]
44. Norenkovova IP heuristika a jejich kombinace v genetických metodách diskrétní optimalizace. // Informační technologie. 1999. č. 1. S. 2-7. [ I. P. Norenkov, "Heuristika a jejich kombinace v diskrétních optimalizačních genetických metodách," (v ruštině), v Dodatku k časopisu Informační technologie, č. 1, str. 2-7, 1999.]
45. A. S. Mukhacheva, A. V. Chiglintsev, M. A. Smagin a E. A. Mukhacheva, „Dvourozměrné problémy s balením: Vývoj genetických algoritmů založených na smíšených místních vyhledávacích postupech pro optimální řešení“, Informační technologie. Slepé střevo. 2001. č. 9. 28 s. [A. S. Mukhacheva, et al., "2D bin-packing problems: vývoj genetických algoritmů založených na složených postupech místního hledání optimálního řešení," (v ruštině), v dodatku k Magazine Information technologies, no. 9, 2001.]
46. Frolovsky V. D., Pushkaryova G. V. Optimalizace pohybu obrábění kovů pro návrh NC programů pomocí genetických algoritmů. Proč. 6. mezinár. Conf. o počítačové grafice a umělé inteligenci, Limoges (Francie), 14.-15. května 2003. S. 143-152. [V. D. Frolovsky a G. V. Pushkaryova, "Optimalizace pohybu obrábění kovů pro návrh NC programů s využitím genetických algoritmů," Proc. 6. mezinár. Conf. o počítačové grafice a umělé inteligenci, Limoges (Francie), 14.-15. května 2003, pp. 143-152. ]
47. Korchevskaya O. V., Zhukov L. A. Získání dolních odhadů pro problémy dvou a trojrozměrného ortogonálního balení [Elektronický zdroj] // Researched in Russia: electronic journal. 2008. 62. S. 685-694. URL: http:// zhurnal.ape.relarn/articles/2008/062.pdf [ O. V. Korchevskaja, L. A. Žukov, „Obstarávání nízkých hranic pro 2G a 3D ortogonální bin-packing problems,“ (v ruštině), elektronický časopis „Vyšetřováno v Rusku", 62, 2008. s. 685-694, http://zhurnal.ape.relarn/articles/2008/062.pdf]
48. Mukhacheva E., ed. Zvláštní vydání: Rozhodování za podmínek nejistoty (problémy řezání a balení) // The International Scientific Collection. 1997. Ufa, Rusko. [E. Mukhacheva, ed. Speciální problém: Rozhodování za podmínek nejistoty (problémy řezání-balení). The International Scientific Collection, Ufa, Rusko, 1997.]
49. Sergeyeva O., Scheithauer G., Terno J. Metoda korekce hodnot pro balení nepravidelných tvarů // Rozhodování za podmínek nejistoty (problémy řezání a balení): The Int. sci. sbírka. Ufa, 1997. S. 261-270. [ O. Sergeyeva, G. Scheithauer a J. Terno, "Metoda korekce hodnot pro balení nepravidelných tvarů", Rozhodování za podmínek nejistoty (problémy řezání - balení). The International Scientific Collection, Ufa, 1997, pp. 261-270. ]
50. Belov G., Kartak V., Rohling H., Scheithauer G. Jednorozměrné relaxace a LP hranice pro ortogonální balení. ITOR, 2009. V. 16. S. 745-766. [G. Belov, et al., "Jednorozměrné relaxace a LP hranice pro ortogonální balení," ITOR, sv. 16, str. 745-766, 2009.]
51. Frolovskiy VD Parametrické modelování a identifikace trojrozměrných objektů se složitou strukturou // Informační systémy a technologie: mater. Mezinárodní sci.-tech. Konf. Novosibirsk: NSTU, 2003. T. 1. S. 153-155. [ V. D. Frolovski, "Parametrická simulace a identifikace 3D objektů s komplikovanou strukturou," (v ruštině), v Proc. Int. Sci-Tech. Konference "Informační systémy a technologie", Novosibirsk, NGTU, 2003, sv. 1, str. 153-155. ]
52. Kolokolov A. A., Nagornaya Z. E., Arkhimenko M. Yu., Ivanova S. D. Design kožešinových výrobků pomocí matematického modelování. IV Stážista. sci.-tech. konf., oddaný 60. výročí OmSTU. Rezervovat. 1. Omsk: OmGTU, 2002. S. 297-299. [ A. A. Kolokolov a kol., "Návrh kožešinového zboží pomocí matematického modelování, Dynamika systémů, mechanismů a strojů," (v ruštině), v Proc. 4 Int. Sci-Tech. Konference k 60. výročí OmGTU, vol.1, Omsk, 2002, pp. 297-299. ]
53. Panyukova T. A., „Optimální Eulerovy kryty s uspořádaným uzavřením pro rovinné grafy“, Diskrétní analýza a operační výzkum. Březen-duben, 2011. Vol. 18, č. 2. S. 64-74. [ T. A. Panuková, "Optimální Eulerovy kryty s uspořádaným sjednocením pro ploché grafy," (v ruštině), v Diskrétní analýza a operační výzkum, březen duben, sv. 18, č. 2, str. 64-74, 2011.]
54. Novikov I. S. Automatické umisťování nadrozměrných elektronických prvků pomocí genetického vyhledávání s migrací // Návrh a technologie elektronických prostředků. 2007. č. 1. C. 33-38. [ I. S. Novikova, "Automatická alokace elektronických prvků různých velikostí genetickým vyhledáváním s migrací," (v ruštině), v Návrh a technologie elektronického zařízení, č. 1, str. 33-38, 2007.]
55. Mukhacheva E. A., Valeev R. S. Místní vyhledávání umístění komoditních položek na základě analýzy jejich nomenklaturní příslušnosti // Informační technologie. 2010. č. 6. S. 18-23. [ E. A. Mukhacheva a R. S. Valeev, "Místní vyhledávání alokace komodit na základě jejich sortimentu," (v ruštině), v Informační technologie, č. 6, str. 18-23, 2010.]
56. Mukhacheva E. A., Bukharbaeva L. Ya., Filippov D. V., Karipov U. A. Problémy optimalizace dopravní logistiky: operativní umístění kontejnerů při přepravě nákladu // Informační technologie. 2008. č. 7. S. 17-22. [ E. A. Mukhacheva a kol., "Problémy optimalizace dopravní logistiky; provozní přidělování kontejnerů při přepravě nákladu," (v ruštině), Informační technologie, č. 7, str. 17-23, 2008.]
57. Telitsky S. V., Filippova A. S. Integrovaný přístup k řešení problému pokrytí oblasti obrobky neurčitých velikostí. St. Petersburg State Polytechnical University Journal. Informatika. Telekomunikace. Řízení
ne. 2 (145) / 2012, Petrohrad, 2012, s. 61-67. [ S. V. Telitskiy a A. S. Filippova, "Komplexní přístup k řešení problému pokrytí oblastí předměty nedefinovaných velikostí," (v ruštině), v Nauchno-technicheskye Vedomosty SPbGPU, Informatika. telekomunikace. Management, 2(145)/2012, StPsb, pp. 61-67, 2012.]
58. L. I. Vasilyeva, „Algorithms for Packing N-Dimensional Corrugations Based on Linear Programming Methods“, Cand. ... bonbón. tech. Sciences / UGATU, 2000. [ L. I. Vasilyeva, "Packing algorithms of N-dimensionv corrugations based on linear programming methods," (v ruštině): Disertační práce pro vědecký titul Cand. of Tech. Sci, UGATU, 2000.].
59. V. M. Karták, Modely a optimalizační metody pro balení n-rozměrných rovnoběžnostěnů, Cand. ... bonbón. Fyzikální matematika Sciences / UGATU, 1999. [V. M. Kartak, "Modely a metody optimalizace n-rozměrného rovnoběžnostěnového balení," (v ruštině): Disertační práce pro vědeckou hodnost Cand. fyziky a matematiky Sci, UGATU, 1999.]
VALIAKHMETOVA Julia Ilyasovna, Assoc. kavárna matematika. Dipl. Ing. (UGATU, 2004). Cand. tech. Vědy v matematice. mod., č. metody a softwarové balíčky (USATU, 2008). Výzkum v oblasti optimalizace úkoly řezání-balení. FILIPPOVÁ Anna Sergejevna, prof. kavárna aplikovaná informatika. Dipl. Ing. (UGATU, 1996). Dr. tech. vědecká podložka. modelování, č. metody a softwarové balíčky (SSAU, 2007). Výzkum v oblasti kombinatorické algoritmy.
Název: Teorie optimálního využití zdrojů L. V. Kanto-roviče v problémech řezání-balení: přehled a historie vývoje metod řešení Autoři: Yu. I. Valiakhmetova, A. S. Filippová. příslušnost:
1 Baškirská státní agrární univerzita (BSAU), Rusko.
2 Baškirská státní pedagogická univerzita M. Akmully (BSPU), Rusko.
E-mailem: [e-mail chráněný], [e-mail chráněný] Jazyk: ruština.
Zdroj: Věstník UGATU (vědecký časopis Státní letecké technické univerzity Ufa), sv. 18, č. 1 (62), str. 186-197, 2014. ISSN 2225-2789 (Online), ISSN 1992-6502 (Tisk). Abstrakt: Článek uvádí příklady technik řešení problémů řezání-balení, které jsou stále aktuální s ohledem na jejich rozmanitost a mnohostrannou použitelnost. Za zásadní pro rozvoj těchto postupů jsou považovány vědecké práce L. V. Kantoroviče. Článek podává přehled postupů řešení problémů řezání-balení, které vyvinuli sovětští a ruští vědci v posledních 80 letech, včetně různých vědeckých škol SSSR a Ruska. Popsán je také souhrn postupů řešení a historie jejich vývoje. Klíčová slova: řezání, optimální využití zdrojů, optimalizace, exaktní metody, heuristické metody.
VALIAKHMETOVA, Yuliya Ilyasovna, Associate Prof., Odd. matematiky, Dipl. Inženýr-programátor (UGATU, 2004). Cand. of Tech. sci. (UGATU, 2008). FILIPPOVÁ, Anna Sergejevna, prof., odd. aplikované informatiky. Dipl. Systémový inženýr (UGATU, 1996). Cand. of Tech. sci. (Ufa State Univ., 1999)., Dr. of Tech. sci. (Samara State Aerospace Univ., 2007).
Až do poloviny XX století. teoretičtí ekonomové ignorovali matematické modely studie. Navzdory útlaku však matematici pokračovali v práci a dosahovali skvělých výsledků. Jsou mezi nimi zástupci matematické školy L. Kantorovich a T.-Ch. Koopmans.
Kantorovič Leonid Vitalievich (1912-1986) – sovětský ekonom, nositel Nobelovy ceny (1975). Narozen v Petrohradě, studoval na Leningradské univerzitě. V roce 1930 byl L. Kantorovich členem All-Union Matematického kongresu. Ve stejném roce absolvoval univerzitu a o čtyři roky později mu byl udělen titul profesor. V letech 1930-1939. pracoval v Leningradském institutu průmyslových stavebních inženýrů, poté (do roku 1948) - vedoucí katedry Vyšší strojírenské a technické školy.
V roce 1935 se stal doktorem fyzikálních a matematických věd; do roku 1960 byl profesorem na Leningradské univerzitě. Vlastní prvotřídní výsledky ve funkcionální analýze, teorii funkcí a výpočetní matematice. Jeho práce na deskriptivní teorii funkce a teorii množin, na konstruktivní teorii funkcí a přibližné metody analýzy získaly široké uznání; položil základy pro nový směr ve funkcionální analýze - teorii polouspořádaných vektorových prostorů, které se nazývají "K-prostory". Fenoménem L. Kantoroviče je, že byl zároveň nadaným matematikem a ekonomem, který upravil chápání ekonomických jevů, rozšířil ekonomické myšlení a stal se zakladatelem originální ekonomické školy.
V roce 1958 vytvořil L. Kantorovič společně s V. Němčinovem Laboratoř pro zavádění statistických a matematických metod v ekonomii.
L. Kantorovič se podílel na vytvoření Sibiřské pobočky Akademie věd SSSR. Na podzim 1960 v Leningradu vedl skupinu matematiků a ekonomů, která se přestěhovala do Novosibirsku a stala se součástí Ústavu matematiky sibiřské pobočky Akademie věd SSSR jako oddělení matematiky a ekonomie. Současně působil jako profesor na Novosibirské univerzitě. V roce 1971, když se vědec přestěhoval do Moskvy, vedl Problémovou laboratoř v Institutu řízení národního hospodářství Státního výboru Rady ministrů pro vědu a techniku SSSR.
Je autorem těchto prací: „Metody pro přibližné řešení parciálních diferenciálních rovnic“ (spoluautor V. Krylov) (1963), „Funkční analýza v semi-uspořádaných prostorech“ (spoluautor B. Vulich a A. Pinsker) (1949), „Funkční analýza a aplikovaná matematika“ (1948), „Ekonomický výpočet nejlepšího využití zdrojů“ (1959), „Funkční analýza v normovaných prostorech“ (spoluautor s G. Akilovem) , "Dynamický model optimálního plánování" (1967), "Cena a technický pokrok" (1979) atd.
L. Kantorovich je čestným členem Mezinárodní ekonometrické společnosti, čestným doktorem univerzit v Grenoblu, Helsinkách, Yale, Paříži, Cambridge, Pennsylvanii, dále univerzit ve Varšavě, Glasgow, Mnichově, Nice a Martina Luthera v Hullu. Statistický ústav v Kalkatě. Vyznamenán dvěma Leninovými řády.
Nejvýznamnějším přínosem L. Kantoroviče byla teorie optimálního rozdělení zdrojů.
Teorie optimální alokace zdrojů je teorií, která zajišťuje formulaci statistických a dynamických modelů současného a dlouhodobého plánování využití zdrojů na základě nových matematických přístupů v oblasti systematické konstrukce ekonomických ukazatelů používaných k analýze cenotvorby. efektivnost kapitálových investic.
Základy teorie optimálního rozdělení zdrojů poprvé nastínil ve svém díle Matematické metody pro organizaci a plánování výroby (1939). V něm představil zásadně novou třídu extremálních problémů s omezeními a vyvinul účinnou metodu jejich řešení. Právě v této době vědec formuloval úkol sestavit plán a cenový systém jako vzájemně závislé součásti nedělitelné duality. Je totiž nemožné minimalizovat náklady a zároveň maximalizovat výsledky. Tyto dva přístupy spolu zároveň souvisí: najdeme-li optimální dopravní schéma, pak tomu odpovídá určitý cenový systém. Pokud určíme optimální hodnoty cen, je poměrně snadné získat dopravní schéma, které splňuje požadavky na optimalitu.
Základem této teorie je metoda lineárního programování.
Lineární programování je řešení lineárních rovnic (rovnice prvního stupně) přidáváním programů a zaváděním různých metod pro jejich sekvenční řešení, což značně usnadňuje výpočty a dosahuje výsledků.
Jeho počátkem bylo hledání řešení praktického problému. V roce 1937 se na profesora Leningradské univerzity L. Kantoroviče obrátili inženýři místního překližkového trustu s žádostí o nalezení efektivního způsobu zajištění nejvyšší produktivity práce. Pro zpracování 5 druhů materiálu bylo přiděleno 8 strojů s určitou produktivitou každého z nich pro každý druh materiálu.
Jinými slovy, bylo nutné řešit konkrétní technicko-ekonomický problém s objektivní funkcí („funkční“) – maximalizovat výstup hotových výrobků. Bylo obtížné to udělat pomocí tehdy známých metod, protože bylo nutné vyřešit téměř miliardu algebraických rovnic. L. Kantorovich navrhl metodu lineárního programování, která se stala novým odvětvím v matematice a získala uznání v hospodářské praxi, přispěla k rozvoji a využití elektronických počítačů.
Vědec pochopil důležitost vytvoření matematického základu pro řešení typického ekonomického problému. Podmínky úlohy pro optimalitu a cíl lze vyjádřit pomocí soustavy lineárních rovnic. Neznámé v nich jsou pouze prvního stupně; žádná neznámá není násobena jinou neznámou. Takové rovnice vyjadřují závislosti, které lze znázornit na grafu přímkami. Protože existuje méně rovnic než neznámých, má problém několik řešení a vy musíte nějaké najít.
V problému optimalizace výroby překližky zavedl L. Kantorovich proměnnou, která by měla být maximalizována jako součet nákladů na produkty vyrobené všemi stroji. Limity byly stanoveny ve formě rovnic, které stanovují vztah mezi všemi faktory používanými při výrobě (dřevo, lepidlo, elektřina, pracovní doba) a množstvím vyrobeného produktu (překližka) na každém stroji. Pro ukazatele výrobních faktorů byly zavedeny koeficienty, nazývané "rozhodující faktory" (multiplikátory). S jejich pomocí je úkol vyřešen. Jsou-li známy hodnoty rozhodujících faktorů, lze poměrně snadno nalézt požadovaná množství, zejména optimální objem výroby.
L. Kantorovich zdůvodnil ekonomickou podstatu jím navrhovaných rozhodujících faktorů. Jsou to ve skutečnosti mezní náklady omezujících faktorů. To znamená, že se jedná o objektivní ceny každého z výrobních faktorů ve vztahu k podmínkám konkurenčního trhu. K vyřešení problému optimality vědec použil metodu postupných aproximací, sekvenčního porovnávání možností s výběrem toho nejlepšího v souladu s podmínkami problému.
Termín „rozhodující faktory“ zavedený L. Kantorovičem se v pozdějších dílech dočkal trochu jiného výkladu a jiné formulace – „objektivně stanovené odhady“. Tyto odhady nejsou libovolné, jejich hodnoty jsou objektivně určeny, jsou dány konkrétními podmínkami problému. Hodnoty těchto odhadů jsou vhodné pouze pro konkrétní úkol a na rozdíl od cen nejsou stanoveny zvenčí, ale jsou určeny samotným podnikem pro interní použití. Vědec navrhl vypočítat je při vývoji plánů; podniky se na tyto ukazatele mohou spolehnout při výpočtu nákladů a objemu výroby. Objektivně stanovené odhady jsou upravovány v závislosti na poměru poptávky a objemů produkce. Vložené
v praxi plánování a řízení by takové výpočty měly optimalizovat využití zdrojů.
Problémy lineárního programování byly známy již na konci 18. století. Ty však začali řešit až po vydání děl L. Kantoroviče. Ve Spojených státech začal výzkum lineárního programování teprve na konci 40. let 20. století. Hitchcockův transportní problém a Danzigova simplexová metoda, které jsou svou povahou podobné Kantorovičově metodě řešení úloh lineárního programování, byly vyvinuty o deset let později.
Na původní přístup L. Kantoroviče až do 50. let téměř žádná reakce. Když shrnul svůj výzkum, rozšířil rozsah analýzy.
V práci „Ekonomický výpočet nejlepšího využití zdrojů“ a v následujících dílech představil svou metodu lineárního programování pro studium široké škály plánovacích problémů, a to i na národní úrovni.
O něco později, ale nezávisle na L. Kantoroviči, navrhl podobnou metodologii T.-Ch. Koopmans.
Koopmans (Koopmans) Tyalling-Charles (1910-1985) – americký ekonom, nositel Nobelovy ceny (1975). Narozen v Graveland (Nizozemsko). Studoval na univerzitě v Utrechtu. Nejprve měl rád matematiku a fyziku, pracoval jako fyzik a pod dojmem Velké hospodářské krize začal studovat ekonomii.
Od roku 1934 studoval problém obecné rovnováhy na univerzitě v Amsterdamu. Doktorskou disertační práci na téma „Lineární regresní analýza ekonomických časových řad“ obhájil v roce 1936 na univerzitě v Leidenu. Vyučoval ekonomii a zabýval se výzkumnou činností na Nizozemském ekonomickém institutu v Rotterdamu.
V letech 1938-1940. pracoval jako expert Společnosti národů na peněžní oběh. Emigroval do USA. Učil na univerzitách v New Yorku, Chicagu a Harvardu. Od roku 1955 - profesor ekonomie na Yale University. V roce 1950 byl zvolen prezidentem Mezinárodní ekonometrické společnosti a v roce 1978 prezidentem Americké ekonomické asociace.
T.-Ch. Koopmans byl editorem a spoluautorem jedné z prvních základních prací o lineárním programování, Analýza výrobních a distribučních činností (1951).
Vědec vlastní důležité úspěchy ve vývoji teorie kapitálu, operační analýzy. Některé své práce věnoval optimálnímu rozdělení výrobních zdrojů, statistickému hodnocení parametrů v ekonomických a matematických modelech.
Jeho potomky jsou práce ze statistiky a matematické ekonomie. Nejoceňovanější prací byla „Analýza činnosti výroby a distribuce“, zpracovaná skupinou autorů pod jeho vedením, dále práce „Statistický závěr v dynamických modelech ekonomiky“ (1950), „Tři eseje o stav ekonomické vědy“ (1957) atd.
T.-Ch. Koopmans je váženým členem Americké ekonomické asociace, emeritním profesorem Yaleovy univerzity, získal čestné tituly na Nizozemské ekonomické škole, Severozápadní a Pensylvánské univerzitě a Katolické univerzitě v Lovani.
V letech 1944-1945. jménem Anglo-American United Council for the Regulation of Navigation T.-Ch. Koopmans vyvinul plán obchodní plavby, který minimalizoval možnost nebezpečného torpédování prázdných nákladních lodí fašistickými ponorkami. Cílem bylo minimalizovat chod lodí naprázdno.
Tohoto tématu se dotkl ve svém díle „Korelace mezi nákladní dopravou na různých trasách“ (1942). Vědec ukázal, že problém by měl být považován za lineární maximalizační funkci v rámci mnoha omezení. Omezení byla prezentována matematickými rovnicemi, které vyjadřují poměr počtu vstupních faktorů výroby (odpisy lodí, čas, mzdové náklady) k množství zboží dodaného do různých destinací. Hodnota jakýchkoli nákladů však nesmí překročit explicitní výši nákladů na zboží dodané do každého přístavu. Vědec došel k závěru, že podstatou principu lineárního programování je, že v optimálním případě a podle ideálních odhadů všech zdrojů se náklady a výsledky vyrovnají.
Při práci pro Britskou obchodní misi ve Washingtonu T.-Ch. Koopmans použil matematické nástroje a vytvořil metodu pro stanovení optimální alokace zdrojů mezi konkurenčními spotřebiteli. Touto metodou bylo možné například spočítat náklady na dodání milionů tun nákladu, který přepravují tisíce lodí po moři do stovek přístavů. Metoda T.-Ch. Koopmans, kterému se říkalo „analýza činnosti společnosti“, vstoupil do obecné metodiky lineárního programování.
V roce 1947 vědec oznámil své poznatky na mezinárodní konferenci o statistice. V té době aktivně rozvíjel a popularizoval metody lineárního programování. S jeho pomocí se v roce 1949 v Chicagu konala první speciální konference o lineárním programování.
V roce 1950 T.-Ch. Koopmans spolu se svými příznivci dokončil formulaci metody pro analýzu aktivit firmy. Modely tohoto typu, stejně jako meziodvětvové, lineární, v nich však může být každý typ výrobní činnosti spojen s uvolněním několika zboží. Pro každý typ výrobku je navíc možnost volby mezi různými výrobními technologiemi. Výrobní model, jako je analýza výkonnosti firmy, obvykle obsahuje více stupňů volnosti než typický vstupně-výstupní model, což vytváří přirozené příležitosti pro optimalizaci. Proto se analýza činnosti společnosti vyvíjela v úzké návaznosti na lineární programování.
Upozorňujeme na časopisy vydávané nakladatelstvím "Přírodovědná akademie"
Ifns: co to je a vlastnosti fungování inspekcí
Nauka o geografické (územní) dělbě práce
Země cizí Evropy podle oblastí
Darování bytu cizímu státnímu příslušníkovi
Dárek do bytu cizímu státnímu příslušníkovi
Zapsat polovinu bytu na jeho manželku
Co dělat při demolici místnosti