ALKALMAZOTT MATEMATIKAI LAPOK 25. KÖTET (A MTA Matematikai Tudományok Osztályának Közleményei, 2008)
2008 / 1. sz. - SCHRIJVER, ALEXANDER: Szemelvények a kombinatorikus optimalizálás történetéből (1960-ig)
SZEMELVÉNYEK A KOMBINATORIKUS OPTIMALIZÁLÁS TÖRTÉNETÉBŐL 3 somme de ces produits sera la moindre possible, & le prix du transport total sera un minimum.2 Monge érdekes geometriai módszert adott a probléma megoldására. Vegyünk egy mindkét tartományt érintő egyenest, és szállítsuk az első tartomány érintési pontjában található m molekulát a második tartomány x érintési pontja által kijelölt helyre, majd ismételjük ezt addig, amíg az összes földet át nem hordtuk. Monge indoklása arról, hogy ez optimális, egészen egyszerű: ha az m molekula valamely más helyre kerülne, úgy egy másik molekulát szállítanánk az x helyre. Ez azt jelentené, hogy a két molekula útvonala keresztezné egymást, és ezért létezne egy rövidebb összúttal bíró megoldás: Étant données sur un même plan deux aires égales ABCD, & abcd, terminées par des contours quelconques, continus ou discontinus, trouver la route que doit suivre chaque molécule M de la premiere, &: le point m où elle doit arriver dans la seconde, pour que tous les points étant semblablement transportés, ils replissent exactement la seconde aire, & que la somme des produits de chaque molécule multipliée par l'espace parcouru soit un minimum. Si par un point M quelconque de la première aire, on mène une droite Bd., telle que le segment BAD soit égal au segment bad, je dis que pour satisfaire à la question, il faut que toutes les molécules du segment BAD, soient portées sur le segment bad, h que par conséquent les molécules du segment BCD soient portées sur le segment égal bcd\ car si un point К quelconque du segment BAD, étoit porté sur un point к de bed, il faudroit nécessairement qu'un point égal L, pris quelque part dans BCD, fût transporté dans un certain point l de bad, ce qui ne pourrait pas se faire sans que les routes Kk, Ll, ne se coupassent entre leurs extrémités, & la somme des produits des molécules par les espaces parcourus ne serait pas un minimum. Pareillement, si par un point M' infiniment proche du point M, on mène la droite B'd', telle qu'on ait encore le segment B' A'£>', égal au segment b'a'd', il faut pour que la question soit satisfaite, que les molécules du segment B' A' D' soient transportées sur b'a'd'. Donc toutes les molécules de l'élément BB'D'D doivent être transportées sur l'élément égal bb'd'd. Ainsi en divisant le déblai & le remblai en une infinité d'élémens par des droites qui coupent dans l'un & dans l'autre des segmens égaux entr'eux, chaque élément du déblai doit être porté sur l'élément correspondant du remblai. Les droites Bd & B'd' étant infiniment proches, il est indifférent dans quel ordre les molécules de l'élément BB'D'D se distribuent sur l'élément bb'd'd-, de quelque manière en effet que se fasse cette distribution, la somme des produits des molécules par les espaces parcourus, est toujours la même, mais si l'on remarque que dans la pratique il convient de débleyer premièrement les parties qui se trouvent sur le passage des autres, h de n'occuper que les dernières les parties du remblai qui sont 2Amidőn földet kell szállítanunk egyik helyről valamely másikra, úgy rendszerint Déblai névvel illetjük a szállítandó földmennyiséget, & Remblai-пак mondjuk azon helyet, melyet az elszállított földnek a munka végén kell kitöltenie. Miként egyetlen molekula szállításának ára (ha minden más egyezik) arányos annak súlyával és az általa megtétetett távolsággal és azért a teljes szállítási költség arányos lévén a molekulák megtett távolsággal való szorzatainak összegével, az következik, hogy - lévén a déblai és a remblai alak és elhelyezkedés szerint megadva - számít, ha a déblai egy bizonyos molekulája a remblai egyik avagy másik pontjába szállíttatik, ám létezik az előbbi molekuláknak az utóbbiakba egy bizonyos elosztása, amelynek révén ezen szorzatok összege a lehető legkisebb és a teljes szállítás ára minimális. Alkalmazott Matematikai Lapok (2008)