Erőforrások optimalizálása lineáris programozással

  • Rajt
  • PHPSimplex
    • PHPSimplex súgó
  • Operatív vizsgálat
    • Történelem
    • Valós esetek
  • Elmélet
    • Probléma modellezése
    • Simplex módszer
    • Kétfázisú módszer
    • Grafikus módszer
  • Példák
    • Probléma modellezése
      • Diéta probléma
      • Csapatszállítás problémája
      • Teherszállítási probléma
      • Gyümölcsfa probléma
      • Személyzeti kérdés
      • Minimális útvonal probléma
      • Helyprobléma
      • Részvény befektetési probléma
    • Simplex módszer
    • Grafikus módszer
  • George B. Dantzig
    • Életrajz
    • Interjú
  • Idióma
    • spanyol
    • angol
    • Français
    • portugál

A műveletek kutatásának története

A történelem során gyakori, hogy szoros együttműködést találunk a tudósok és a katonaság között annak érdekében, hogy meghatározzuk az optimális döntést a csatában és megpróbáljuk megszerezni a győzelmet. Éppen ezért a szakterület számos szakértője az operatív kutatás kezdetét Kr.e. 3. században, a második pun háború idején vizsgálja meg azzal az elemzéssel és megoldással, amelyet Archimédész javasolt a rómaiak által ostromolt Syracuse városának védelmére. Találmányai között szerepelt a katapult és a tükrök rendszere, amellyel felgyújtotta az ellenséges hajókat, a napsugarakkal összpontosítva őket.

1503-ban Leonardo da Vinci mérnökként vett részt a Pisa elleni háborúban, mivel ismert technikákat bombázások végrehajtására, hajók, páncélozott járművek, ágyúk, katapultok és más hadigépek felépítésére.

vizsgálat

Az Operations Research alkalmazásának egy másik előzménye az első világháború idején következik be Angliában, Frederick William Lanchester matematikai tanulmányával az ellentétes erők ballisztikus erejéről. Kidolgozta a differenciálegyenlet-rendszer alapján a Lanchester-féle kvadratikus harci törvényt is, amellyel meg lehetett állapítani a katonai csata kimenetelét a harcosok relatív numerikus ereje és relatív tűzereje alapján.

Thomas Alva Edison az Operations Research-et is felhasználta, hozzájárult a tengeralattjárók elleni hadviseléshez, technikákat fejlesztett ki annak érdekében, hogy a hajók kikerülhessék és megsemmisítsék az ellenséges tengeralattjárókat, torpedó elleni védelmet nyújtva számukra.

Matematikai szempontból a XVII – XVIII. Században Newton, Leibnitz, Bernoulli és Lagrange azon fáradozott, hogy bizonyos funkciókhoz feltételes maximumokat és minimumokat kapjanak. Jean Baptiste-Joseph Fourier francia matematikus felvázolta az aktuális lineáris programozás módszereit. És a 18. század utolsó éveiben Gaspar Monge megalkotta a Grafikus módszer precedenseit a Leíró Geometria fejlesztésének köszönhetően.

A 19. század végén Frederick Winslow Taylor a bányászok teljesítményét maximalizáló tanulmányt végzett, amelyben megállapították, hogy az egyetlen igazán jelentős változó a lapát és a terhelés együttes súlya. Ily módon a pengéket a különböző típusú anyagoknak megfelelően alakították ki, amelyekkel használni kívánták őket.

Janos Von Neumann 1928-ban publikálta "Játékelmélet" című munkáját, amely matematikai alapokat adott a lineáris programozáshoz. Később, 1947-ben, elképzelte a lineáris programozási problémák és az általa kidolgozott mátrixelmélet hasonlóságát.

1939-ben Leonid Vitálievich Kantorovich orosz matematikus és a holland Tjalling Charles Koopmans kidolgozta a "Lineáris programozás" elnevezésű matematikai elméletet, amiért közgazdasági Nobel-díjjal jutalmazták őket.

1945-ben George Joseph Stigler felvetette az étrend problémáját, az amerikai hadsereg azon törekvése eredményeként, hogy a lehető legalacsonyabb költségekkel biztosítsák csapataik alapvető táplálkozási szükségleteit. A cél az volt, hogy meghatározzuk azt a mennyiséget 77 különféle étel között, amelyet egy átlagosan körülbelül 70 kg-os embernek kell ennie naponta, hogy a minimális tápanyagigény megegyezzen az Észak-amerikai Nemzeti Kutatási Tanács által ajánlottakkal. A problémát manuálisan oldották meg heurisztikus módszerrel, amellyel az élelmiszerek ötvözésének 510 különböző lehetőségét vizsgálták, és amelynek megoldása csak néhány centivel különbözött az évekkel később a Simplex módszerrel biztosított megoldástól.

Az 1941-es és 1942-es években Kantorovich és Koopmans először önállóan tanulmányozták a közlekedési problémát, ezt a típusú problémát Koopmans-Kantorovich problémának hívták. Megoldásukhoz olyan geometriai módszereket használtak, amelyek kapcsolódnak Minkowski konvexitáselméletéhez.

Charles Babbage feltehetően az Operations Research atyja, az 1840-ben Angliában, az Uniform Penny Postnál végzett postai küldemények szállítási és válogatási költségeinek kutatása miatt.

Azt azonban nem tartják számon, hogy az Operations Research vagy Operations Research nevű új tudomány egészen a második világháborúig, a brit csata idején született volna. A Luftwaffe, a német légierő erőteljes zaklatásnak vetette alá ezt az országot, kihasználva a leszerelési politika miatt csökkent brit légi kapacitást, bár a harcban tapasztalt. A brit kormány, keresve valamilyen módszert az országának megvédésére, különféle tudományterületek tudósait hívta meg, hogy megpróbálják megoldani a problémát, és kihasználni a rendelkezésükre álló újonnan feltalált radarokat. Az antennák optimális elhelyezkedését és a jelek legjobb eloszlását meghatározó munkájuknak köszönhetően megduplázták a légvédelmi rendszer hatékonyságát, és megakadályozták, hogy a sziget a náci Németország kezébe kerüljön.

Miután értékelte ennek az új tudományágnak a körét, Anglia más, azonos természetű csoportokat hozott létre, hogy optimális eredményeket érjen el a versenyen. Ugyanígy az Egyesült Államok (USA), miután 1942-ben csatlakozott a háborúhoz, katonai úton kezdte alkalmazni az Operációkutatás technikáit, és néhány évvel később, 1947-ben munkacsoportot hozott létre, amelynek célja a tervezési folyamatok nagymértékű javítása: SCOOP projekt (Az optimális programok tudományos számítása). Ebben a csoportban George Bernard Dantzig dolgozott, aki 1947-ben kifejlesztette a Simplex módszer algoritmust.

A hidegháború idején a Marshall-tervből kizárt volt Szovjetunió (Szovjetunió) Berlinből akarta irányítani a szárazföldi kommunikációt, beleértve a folyami útvonalakat is. A város átadásának elkerülése és a német kommunista zónába való bekerülés elkerülése érdekében Anglia és az Egyesült Államok úgy döntött, hogy ellátja a várost, akár kísérő konvojokkal (ami új konfrontációhoz vezethet), akár légi szállítással, feltöréssel vagy a berlini blokádot elkerülő minden eset. Ezt a második lehetőséget választották, kezdve a Luftbrücke-t (légi szállítás) 1948. június 25-én. Ez egy másik probléma volt, amelyben az SCOOP csoport részt vett, ugyanazon év decemberében napi 4500 tonna utánpótlást lehetett biztosítani, és Kutatási tanulmányok szerint az ellátást addig optimalizálták, hogy 1949 márciusában elérte a napi 8000 vagy 9000 tonnát. Ez az adat megegyezett azzal, amelyet szárazföldön szállítottak volna, ezért a szovjetek 1949. május 12-én úgy döntöttek, hogy feloldják a blokádot.

A második világháború után helyénvalónak ítélték az Egyesült Államok erőforrásait (energia, fegyverek és mindenféle ellátás) optimalizálási modelleken keresztül, Linear Programming megoldásával.

Az Operációkutatás doktrínájával egyidőben számítógépes technikákat is kifejlesztettek, amelyek jelentősen csökkentették a problémák megoldásának idejét.

Ezeknek a technikáknak az első eredményét 1952-ben értük el, a Nemzeti Szabványügyi Hivatal SEAC számítógépének felhasználásával a probléma megoldására. A megoldási idő sikere annyira biztató volt, hogy azonnal felhasználta mindenféle katonai problémára, például a logisztikai és fegyverkezési pénzeszközök kezelésére, az optimális magasság meghatározására, amelyen a repülőgépeknek el kell repülniük az ellenséges tengeralattjárók felkutatásához, és még a mélységét is. amelyhez a vádakat el kellett küldeni, hogy az ellenséges tengeralattjárókhoz érjenek a legtöbb áldozatot okozó módon. Mindez a légierő hatékonyságának akár ötszörös növekedését jelentette.

Az 50-es és 60-as években nőtt az Operations Research érdeklődése és fejlődése, köszönhetően annak alkalmazásának a kereskedelem és az ipar területén. Erre példa az építési homok szállítási optimális tervének kiszámításának problémája Moszkva városában, ahol 10 kiindulási és 230 rendeltetési hely volt. Ennek megoldására 1958 júniusában egy Strena számítógépet használtak, és 10 napos számítás után olyan megoldást produkált, amely 11% -kal csökkentette a kiadásokat az eredeti várható költségekhez képest.

Ezeket a problémákat korábban az üzleti kutatás vagy az üzleti elemzés néven ismert tudományterületen vetették fel, amelynek nem voltak olyan hatékony módszerei, mint a második világháború alatt kifejlesztettek (például a Simplex módszer). Az Operatív Kutatás nem háborús alkalmazásai minden területre kiterjednek, az élelmiszerek, az állattenyésztés, a mezőgazdaság területeinek elosztása, az áruszállítás, a hely, a személyzet elosztása, a hálózati problémák, a sorok, grafikonok stb.

Példaként az Operational Research felhasználásának következő valós eseteit és a jelentett előnyöket lehet megfigyelni.