जीप समस्या: Difference between revisions

Latest revision as of 10:23, 15 July 2023

ईंधन की तीन इकाइयों के लिए जीप समस्या के 'खोज (1-3)' और 'क्रॉसिंग (I-III)' संस्करणों के लिए ईंधन की मात्रा एफ बनाम मूल डी से दूरी का प्लॉट - रंगीन तीर डिपो को दर्शाते हैं, विकर्ण खंड यात्रा को दर्शाते हैं और ऊर्ध्वाधर खंड ईंधन स्थानांतरण को दर्शाते हैं

जीप समस्या,^[1] रेगिस्तान पार करने की समस्या^[2] या अन्वेषण समस्या^[3] एक गणित समस्या है जिसमें एक जीप को ईंधन की एक निश्चित मात्रा के साथ रेगिस्तान में यात्रा करने के लिए अधिकतम दूरी तय करनी होती है। जीप केवल एक निश्चित और सीमित मात्रा में ईंधन ले जा सकती है, किन्तु यह ईंधन छोड़ सकती है और रेगिस्तान में कहीं भी ईंधन को डंप पर एकत्र कर सकती है।

समस्या पहली बार 9वीं शताब्दी के संग्रह प्रोपोजीशन्स एड एक्यू n ्डोस जुवेन्स (युवा लोगों को तेज़ करने के लिए प्रस्ताव) में दिखाई दी, जिसका श्रेय अलकुइन को दिया गया, जिसमें पहेली एक यात्रा कर रहे ऊंट के अनाज खाने के बारे में थी।^[4] लुका पैसिओली की डी विरिबस क्वांटिटैटिस (सी.1500) भी समस्या पर चर्चा करते है। 1947 में n .जे. फाइन द्वारा एक आधुनिक उपचार दिया गया था।^[1]

समस्या की विविधताएं ऊंट और केले की समस्या हैं^[5] जहां एक व्यापारी को केले खाने वाले ऊंट का उपयोग करके बाजार में केले की अधिकतम संख्या पहुंचानी होती है, रेगिस्तान के पार यात्रियों की समस्या^[6] जहां कई यात्रियों को एक गंतव्य तक पहुंचना होता है और वे उन्हें छोड़ने के बजाय केवल आपूर्ति का आदान-प्रदान कर सकते हैं, और रेगिस्तान में कारों की समस्या^[7] जो फिर से केवल अपने ईंधन का आदान-प्रदान कर सकती हैं, किन्तु जहां खाली कारों को छोड़ा जा सकता है। इस अंतिम समस्या में बहुस्तरीय रॉकेट के संचालन के समान समानताएं होती हैं।

समस्या

ईंधन की तीन इकाइयों के लिए जीप समस्या के अन्वेषण (ऊपर) और क्रॉसिंग (नीचे) संस्करणों के पैमाने का प्लॉट। क्षैतिज अक्ष दूरी को दर्शाता है और ऊर्ध्वाधर अक्ष समय को दर्शाता है। ऊर्ध्वाधर रंगीन रेखा खंड ईंधन को छुपाने का संकेत देते हैं और क्षैतिज रेखा खंड निकाले गए ईंधन का उपयोग करके यात्रा को दर्शाते हैं। रंगीन संख्याएँ उस समय संग्रहीत ईंधन की इकाइयों को दर्शाती हैं।

एक निश्चित मूल भाग पर ईंधन की n इकाइयाँ संग्रहित होती हैं। जीप किसी भी समय अधिकतम 1 यूनिट ईंधन ले जा सकती है, और 1 यूनिट ईंधन पर 1 यूनिट की दूरी तय कर सकती है (जीप की ईंधन खपत स्थिर मानी जाती है)। यात्रा के किसी भी बिंदु पर जीप किसी भी मात्रा में ईंधन को ईंधन डंप पर छोड़ सकती है, या पिछली यात्रा में ईंधन डंप पर छोड़े गए ईंधन की किसी भी मात्रा को एकत्र कर सकती है, जब तक कि उसका ईंधन भार कभी भी अधिक न हो एक इकाई पर। समस्या के दो प्रकार होते हैं:

'रेगिस्तान की खोज' – प्रत्येक यात्रा के अंत में जीप को बेस पर वापस लौटना होगा।
रेगिस्तान को पार करते हुए – जीप को अंतिम यात्रा को छोड़कर प्रत्येक यात्रा के अंत में बेस पर वापस लौटना होगा, जीप का ईंधन खत्म होने से पहले जितनी दूर तक यात्रा कर सकती है, वो यात्रा करती है।

किसी भी स्थिति में उद्देश्य जीप द्वारा अपनी अंतिम यात्रा में तय की गई दूरी को अधिकतम करना है।वैकल्पिक रूप से, उद्देश्य किसी दी गई दूरी की अंतिम यात्रा के लिए आवश्यक ईंधन की न्यूनतम मात्रा का पता लगाना हो सकता है।

विविधताएं

प्राचीन समस्या में जीप और ईंधन डंप पर ईंधन को सतत कार्य मात्रा के रूप में माना जाता है। समस्या पर अधिक जटिल विविधताएँ प्रस्तावित की गई हैं जिनमें ईंधन को केवल छोड़ा जा सकता है या अलग-अलग मात्रा में एकत्र किया जा सकता है।^[8]

ऊँट और केले की समस्या में, व्यापारी के पास केले की n इकाइयाँ होती हैं। ऊँट किसी भी समय अधिकतम 1 इकाई केले ले जा सकता है, और 1 इकाई केले पर 1 इकाई दूरी तय कर सकता है। बाज़ार m इकाई की दूरी पर है। यात्रा के किसी भी बिंदु पर ऊंट अपने साथ ले जा रहे केलों की किसी भी मात्रा को कैंप पोस्ट पर छोड़ सकता है, या पिछली यात्रा के समय कैंप पोस्ट पर छोड़े गए किसी भी मात्रा में केले एकत्र कर सकता है, जब तक कि उसके केले का भार 1 इकाई से अधिक न हो जाए। समस्या केले की अधिकतम इकाइयों की माँग करती है जिन्हें बाज़ार तक पहुँचाया जा सके।

रेगिस्तान की समस्या से जूझ रहे यात्रियों के लिए प्रारम्भिक बेस में आपूर्ति की असीमित इकाइयाँ होती हैं। प्रत्येक यात्री किसी भी समय आपूर्ति की अधिकतम 1 इकाई ले जा सकता है, और आपूर्ति की 1 इकाई पर 1 इकाई की दूरी तय कर सकता है। दूसरा मूल भाग m इकाई की दूरी पर होता है। पिछली दो समस्याओं के विपरीत, यात्री रेगिस्तान में आपूर्ति नहीं छोड़ सकते; चूँकि, यात्रा के किसी भी बिंदु पर, साथ जाने वाले यात्री आपस में आपूर्ति स्थानांतरित कर सकते हैं, जब तक कि प्रत्येक यात्री आपूर्ति की 1 इकाई से अधिक न ले जाए। प्रत्येक लौटने वाले यात्री के पास रास्ते में पर्याप्त आपूर्ति होनी चाहिए। समस्या दूसरे बेस तक पहुंचने के लिए आवश्यक यात्रियों के साथ आने वाली न्यूनतम संख्या की मांग करती है। इस समस्या मे उपलब्ध यात्रियों की कुल संख्या बताता है और अधिकतम दूरी पूछता है जिस तक पहुंचा जा सकता है।

रेगिस्तानी समस्या के पार की कारों में, प्रारम्भिक बेस में ईंधन की असीमित इकाइयाँ होती हैं। प्रत्येक कार किसी भी समय अधिकतम 1 यूनिट आपूर्ति ले जा सकती है, और 1 यूनिट ईंधन पर 1 यूनिट की दूरी तय कर सकती है। दूसरा मूल भाग m इकाई की दूरी पर है। गाड़ियाँ रेगिस्तान में ईंधन नहीं छोड़ सकतीं; चूँकि, यात्रा के किसी भी समय, साथ चलने वाली कारें आपस में ईंधन स्थानांतरित कर सकती हैं, जब तक कि प्रत्येक कार में 1 यूनिट से अधिक ईंधन न हो। बिना ईंधन वाली खाली कारों को रेगिस्तान में छोड़ दिया जाता है। समस्या दूसरे बेस तक पहुंचने के लिए आवश्यक कारों की न्यूनतम संख्या मांगती है। इस समस्या का एक प्रकार उपलब्ध कारों की कुल संख्या बताता है, और अधिकतम दूरी तक पहुंचने के लिए कहता है।

समाधान

File:Jeep problem 1.png

n = 3 के लिए रेगिस्तानी संस्करण की खोज का समाधान, प्रत्येक यात्रा की प्रारम्भिक में और प्रत्येक यात्रा पर टर्नअराउंड बिंदु पर जीप की ईंधन सामग्री और ईंधन डंप दिखाना।

रेगिस्तानी संस्करण की खोज के लिए अंतिम यात्रा पर तय की गई दूरी को अधिकतम करने वाली योजना इस प्रकार है:

जीप n यात्राएँ करती है। प्रत्येक यात्रा पर यह 1 यूनिट ईंधन के साथ मूल भाग से प्रारंभ होती है।
पहली यात्रा में जीप 1/(2n) यूनिट की दूरी तय करती है और ईंधन डंप पर (n - 1)/n यूनिट ईंधन छोड़ती है। जीप में अभी भी 1/(2n) यूनिट ईंधन है - जो मूल भाग पर लौटने के लिए पर्याप्त होते है।
बाद की प्रत्येक n - 1 यात्रा में जीप इस पहले ईंधन डंप से 1/(2n) यूनिट ईंधन एकत्र करती है, जिससे की वह 1 यूनिट ईंधन लेकर ईंधन डंप छोड़ सके। यह रास्ते में इससे पहले ईंधन डंप से 1/(2n) यूनिट ईंधन भी एकत्र करता है, जो बेस पर लौटने के लिए पर्याप्त ईंधन होता है।
दूसरी यात्रा में जीप पहले ईंधन डंप तक जाती है और ईंधन भरती है। फिर 1/(2n - 2) इकाइयों की दूरी तय करता है और दूसरे ईंधन डंप पर (n - 2)/(n - 1) इकाइयों को ईंधन शेष बचाती है। जीप में अभी भी 1/(2n − 2) यूनिट ईंधन है, जो पहले ईंधन डंप पर लौटने के लिए पर्याप्त है। यहां यह 1/(2n) यूनिट ईंधन एकत्र करता है, जो मूल भाग पर लौटने के लिए पर्याप्त ईंधन होता है।
आगामी प्रत्येक n - 2 यात्राओं में जीप इस दूसरे ईंधन डंप से 1/(2n − 2) यूनिट ईंधन एकत्र करती है, जिससे की वह 1 यूनिट ईंधन लेकर ईंधन डंप छोड़ दे। यह वापसी में दूसरे ईंधन डंप से 1/(2n − 2) यूनिट ईंधन भी एकत्र करता है, जो पहले ईंधन डंप में लौटने के लिए पर्याप्त ईंधन होता है।
जीप इस तरह से चलती रहती है, जिससे की यात्रा k पर यह पिछले ईंधन डंप से 1/(2n - 2k + 2) इकाइयों की दूरी पर एक नया kth ईंधन डंप स्थापित करे और (n − k)/(n − k + 1) छोड़ सके। बाद की प्रत्येक n − k यात्रा पर यह बाहर जाते समय kth डंप से 1/(2n − 2k + 2) यूनिट ईंधन एकत्र करता है और वापस आते समय 1/(2n − 2k + 2) यूनिट ईंधन एकत्र करता है।

जब जीप अपनी अंतिम यात्रा प्रारंभ करती है, तो n - 1 ईंधन डंप होता है। सबसे दूर वाले में ईंधन की एक इकाई का 1/2 भाग होता है, अगले सबसे दूर वाले में ईंधन की एक इकाई का 1/3 भाग होता है, इत्यादि, और निकटतम ईंधन डंप में केवल 1/n इकाई ईंधन बचा होता है। 1 यूनिट ईंधन के साथ, जिसके साथ यह मूल भाग से प्रारंभ होता है, इसका मतलब है कि जीप कुल राउंड ट्रिप दूरी तय कर सकता है।

1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{k=1}^{n}{\frac {1}{k}}\equiv 2\times \mathrm {explore} (n)

इकाइयाँ अपनी अंतिम यात्रा पर हैं (रेगिस्तान में तय की गई अधिकतम दूरी इसकी आधी है)।^[3] यह बाहर जाते समय प्रत्येक डंप पर बचे हुए ईंधन का आधा हिस्सा इकट्ठा करता है, जिससे उसका टैंक भर जाता है। सबसे दूर के ईंधन डंप को छोड़ने के बाद यह रेगिस्तान में 1/2 यूनिट आगे तक जाता है और फिर सबसे दूर के ईंधन डंप पर लौट आता है। यह वापसी में प्रत्येक ईंधन डंप से शेष ईंधन एकत्र करता है, जो अगले ईंधन डंप तक पहुंचने या अंतिम चरण में मूल भाग पर लौटने के लिए पर्याप्त है।

File:Jeep problem 2.png

n = 3 के लिए रेगिस्तानी संस्करण को पार करने का समाधान, प्रत्येक यात्रा की प्रारम्भिक में, पहली दो यात्राओं पर टर्नअराउंड बिंदु पर और अंतिम यात्रा के अंत में जीप की ईंधन सामग्री और ईंधन डंप को दिखाना।

अंतिम यात्रा में तय की गई दूरी nवाँ हार्मोनिक संख्या, H_n है। चूँकि हार्मोनिक संख्याएँ असीमित हैं, अंतिम यात्रा पर किसी भी दूरी को पार करना संभव है, साथ ही मूल भाग पर पर्याप्त ईंधन उपलब्ध होता है। चूँकि, आवश्यक ईंधन की मात्रा और ईंधन डंप की संख्या दोनों ही यात्रा की जाने वाली दूरी के साथ तेजी से बढ़ती हैं।

"रेगिस्तान को पार करना" संस्करण को एक समान योजना के साथ हल किया जा सकता है, अतिरिक्त इसके कि अब अंतिम यात्रा पर वापस जाते समय ईंधन इकट्ठा करने की कोई आवश्यकता नहीं होती है। इसलिए यात्रा k पर जीप पिछले ईंधन डंप से 1/(2n − 2k + 1) इकाइयों की दूरी पर एक नया kth ईंधन डंप स्थापित करती है और (2n − 2k − 1)/(2n − 2k − 1) इकाइयों को शेष रखती है, वहाँ ईंधन प्रत्येक n − − k − 1 ट्रिप पर यह अपने रास्ते में kth डंप से 1/(2n − 2k − 1) यूनिट ईंधन एकत्र करता है और पीछे रास्ते में 1/(2n − 2k − 1) यूनिट ईंधन एकत्र करता है।

अब जब जीप अपनी अंतिम यात्रा प्रारंभ करती है, तो वहां कोई ईंधन डंप नहीं होता है। सबसे दूर वाले में ईंधन की एक इकाई का 1/3 हिस्सा होता है, अगले सबसे दूर वाले में ईंधन की एक इकाई का 1/5 हिस्सा होता है, और इसी तरह, और निकटतम ईंधन डंप में केवल 1/(2n − 1) इकाई ईंधन बचा होता है। ईंधन की 1 इकाई जिसके साथ यह बेस से प्रारंभ होती है, इसका मतलब है कि जीप कुल दूरी तय कर सकती है

1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}=\sum _{k=1}^{n}{\frac {1}{2k-1}}=H_{2n-1}-{\frac {1}{2}}H_{n-1}\equiv \mathrm {cross} (n)

इकाइयाँ अपनी अंतिम यात्रा पर हैं।^[1]^[3]यह बाहर जाते समय प्रत्येक डंप पर बचा हुआ सारा ईंधन एकत्र करता है, जिससे उसका टैंक भर जाता है। सबसे दूर स्थित ईंधन डंप से निकलने के बाद यह 1 यूनिट की अतिरिक्त दूरी तय करता है।

ध्यान दें कि

\mathrm {cross} (n)=\sum _{k=1}^{n}{\frac {1}{2k-1}}>\sum _{k=1}^{n}{\frac {1}{2k}}={\frac {1}{2}}H_{n}=\mathrm {explore} (n)

इसलिए सैद्धांतिक रूप से मूल भाग पर पर्याप्त ईंधन दिए जाने पर किसी भी आकार के रेगिस्तान को पार करना संभव है। पहले की तरह, आवश्यक ईंधन की मात्रा और ईंधन डंप की संख्या दोनों यात्रा की जाने वाली दूरी के साथ तेजी से बढ़ती हैं।

संक्षेप में, n यात्राओं में (n-1 बीच में ईंधन डंप और कुल n इकाइयों के ईंधन की खपत के साथ) जीप द्वारा (किसी भी समय दूरी की 1 इकाई के लिए ईंधन क्षमता के साथ) पहुंचने योग्य अधिकतम दूरी होती है

$\mathrm {explore} (n)={\frac {1}{2}}H_{n}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{6}}+\cdots +{\frac {1}{2n}}$ , रेगिस्तान की खोज के लिए जहां जीप को हर यात्रा के अंत में बेस पर लौटना होगा;
$\mathrm {cross} (n)=H_{2n-1}-{\frac {1}{2}}H_{n-1}=1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}$ , रेगिस्तान को पार करने के लिए जहां जीप को अंतिम यात्रा को छोड़कर हर यात्रा के अंत में बेस पर लौटना होता है, जब जीप ईंधन खत्म होने से पहले जितनी दूर तक यात्रा कर सकती है, यात्रा करती है।

यहाँ $H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}$ nवाँ हार्मोनिक संख्या होती है।

ईंधन की निरंतर मात्रा

मूल भाग पर उपलब्ध ईंधन इकाइयों की संख्या पूर्णांक होने की आवश्यकता नहीं है। सामान्य स्थिति में, रेगिस्तान की समस्या का पता लगाने के लिए प्राप्त होने वाली अधिकतम दूरी $n$ ईंधन की इकाई होती है

\mathrm {explore} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil n-f\rceil }}

पहला ईंधन डंप स्थित है $\{n\}/(2\lceil n\rceil )$ प्रारंभिक मूल भाग से दूरी की इकाई, दूसरा पर $1/(2\lceil n\rceil -2)$ पहले ईंधन डंप से दूरी की इकाइयाँ, तीसरे पर $1/(2\lceil n\rceil -4)$ दूसरे ईंधन डंप से दूरी की इकाई, इत्यादि। यहाँ $\{n\}=n-\lfloor n\rfloor$ n का भिन्नात्मक भाग होता है।

ईंधन की n इकाइयों के साथ "रेगिस्तान पार करने " की समस्या के लिए प्राप्त की जाने वाली अधिकतम दूरी होती है

\mathrm {cross} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil n-f\rceil -1}}

पहला ईंधन डंप स्थित है $\{n\}/(2\lceil n\rceil -1)$ प्रारंभिक मूल भाग से दूरी की इकाई, दूसरा पर पर $1/(2\lceil n\rceil -3)$ पहले ईंधन डंप से दूरी की इकाइयाँ, तीसरे पर $1/(2\lceil n\rceil -5)$ दूसरे ईंधन डंप से दूरी की इकाइयाँ, इत्यादि। यहाँ $\{n\}=n-\lfloor n\rfloor$ n का भिन्नात्मक भाग होता है।

समस्या के अन्य रूप

ऊँट और केले की समस्या में, यह मानते हुए कि व्यापारी के पास प्रारम्भिक मूल भाग पर केले की कुल n=7/3 इकाइयाँ होती हैं और बाज़ार m दूरी पर होता है:

यदि $m>\mathrm {cross} (n)=1/15+1/3+1$ , इस समस्या का कोई समाधान सम्मलित नहीं है;
यदि $m\leq \mathrm {cross} (n)-\mathrm {cross} (\lfloor n\rfloor )=1/15$ , परिवहन के लिए कोई मिडवे कैंप पोस्ट आवश्यक नहीं है, और दूरी m के लिए दोहराया जाएगा $2\lceil n\rceil -1=5$ कई बार ऊँट द्वारा, बाजार में केले की अधिकतम मात्रा पहुंचाई जाती है $n-m\times (2\lceil n\rceil -1)=7/3-5m$ ;
यदि $\mathrm {cross} (n)-\mathrm {cross} (\lfloor n\rfloor )<m\leq \mathrm {cross} (n)$ $\mathrm {cross} (n)-\mathrm {cross} (\lfloor n\rfloor )<m\leq \mathrm {cross} (n)$ , केले की अधिकतम मात्रा के परिवहन के लिए इष्टतम समाधान के लिए कुछ मध्य मार्ग शिविर चौकियों की आवश्यकता होती है:
1. एम=1/4<(1/3+1/15) के लिए, प्रारम्भिक बेस से 1/15 यूनिट की दूरी पर केवल एक मिडवे कैंप पोस्ट आवश्यक है, जहां कुल 2 यूनिट केले जमा होंगे . कैंप पोस्ट से बाज़ार की दूरी (1/4-1/15) है, जिसे ऊँट द्वारा 3 बार दोहराया जाएगा, और बाज़ार तक पहुँचाए जाने वाले केले की अधिकतम मात्रा 2-(1/4-1/) है 15)*3=1.45 इकाइयाँ होती है;
2. m=1/2>(1/3+1/15) के लिए, पहले कैंप पोस्ट से 1/3 यूनिट की दूरी पर एक और मिडवे कैंप पोस्ट आवश्यक है, जहां कुल 1 यूनिट केले जमा होंगे। दूसरे कैंप पोस्ट से बाज़ार की दूरी [1/2-(1/3+1/15)] है, जिसे ऊँट द्वारा केवल एक बार तय किया जाएगा, और बाज़ार तक पहुँचाए जाने वाले केले की अधिकतम मात्रा 1- है। [1/2-(1/3+1/15)]*1=0.9 इकाइयां होती है।

यदि ऊँट को अंततः प्रारंभिक मूल भाग पर लौटना आवश्यक हो, तो $\mathrm {explore} (n)$ फ़ंक्शन लागू होता है (अभी भी n=7/3 मानकर):

यदि $m>\mathrm {explore} (n)=1/18+1/4+1/2$ , इस समस्या का कोई समाधान सम्मलित नहीं होता है;
यदि $m\leq \mathrm {explore} (n)-\mathrm {explore} (\lfloor n\rfloor )=1/18$ , परिवहन के लिए कोई मिडवे कैंप पोस्ट आवश्यक नहीं है, और दूरी m के लिए दोहराया जाएगा $2\lceil n\rceil =6$ कई बार ऊँट द्वारा, इसलिए बाजार में केले की अधिकतम मात्रा पहुंचाई जाती है $n-m\times (2\lceil n\rceil )=7/3-6m$ ;
यदि $\mathrm {explore} (n)-\mathrm {explore} (\lfloor n\rfloor )<m\leq \mathrm {explore} (n)$ $\mathrm {explore} (n)-\mathrm {explore} (\lfloor n\rfloor )<m\leq \mathrm {explore} (n)$ , केले की अधिकतम मात्रा के परिवहन के लिए इष्टतम समाधान के लिए कुछ मध्य मार्ग शिविर चौकियों की आवश्यकता होती है:
1. एम=1/4<(1/4+1/18) के लिए, प्रारम्भिक मूल भाग से 1/18 यूनिट की दूरी पर केवल एक मिडवे कैंप पोस्ट आवश्यक है, जहां कुल 2 यूनिट केले (प्लस) ऊँट की अंतिम वापसी के लिए 1/18 इकाइयाँ) अर्जित होंगी। कैंप पोस्ट से बाज़ार की दूरी (1/4-1/18) है, जिसे ऊँट द्वारा 4 बार दोहराया जाएगा, और बाज़ार तक पहुँचाए जाने वाले केले की अधिकतम मात्रा 2-(1/4-1/) है 18)*4=1.22 इकाइयाँ;
2. m=1/2>(1/4+1/18) के लिए, पहले कैंप पोस्ट से 1/4 यूनिट की दूरी पर एक और मिडवे कैंप पोस्ट आवश्यक है, जहां केले की कुल 1 यूनिट (प्लस 1) /ऊंट की अंतिम वापसी के लिए 4 इकाइयां) अर्जित होंगी। दूसरे कैंप पोस्ट से बाज़ार की दूरी [1/2-(1/4+1/18)] है, जिसे ऊँट द्वारा दो बार दोहराया जाएगा, और बाज़ार तक पहुँचाए जाने वाले केले की अधिकतम मात्रा 1-[ है 1/2-(1/4+1/18)]*2=0.61 इकाइयाँ होती है ।

'रेगिस्तान के पार यात्रियों की समस्या' में, मान लें कि n यात्री आपूर्ति की n इकाइयों के साथ प्रारम्भिक बेस से निकलते हैं। 1/(n+1) इकाइयों की दूरी के बाद, वे पहले ही आपूर्ति की n/(n+1) इकाइयों का उपभोग कर चुके होंगे; इस बिंदु पर, यात्रियों में से एक को आपूर्ति की 1/(n+1) इकाइयों के साथ लौटना चाहिए, समूह को आपूर्ति की बिल्कुल (n-1) इकाइयों को छोड़कर, जिससे की प्रत्येक शेष यात्री आपूर्ति की बिल्कुल एक इकाई ले जाए। समूह फिर आपूर्ति की (n-1)/(n+1) इकाइयों का उपभोग करते हुए, 1/(n+1) इकाइयों की दूरी तय करता है; इस बिंदु पर, शेष यात्रियों में से एक को आपूर्ति की 2/(n+1) इकाइयों के साथ वापस लौटना चाहिए, जिससे की समूह आपूर्ति की बिल्कुल (n-2) इकाइयों को छोड़कर, प्रारंभिक मूल भाग पर सुरक्षित रूप से वापस आ सके। समूह 1/(n+1) इकाइयों की दूरी बढ़ाता रहता है और एक यात्री को कम करता रहता है, जब तक कि आपूर्ति की ठीक एक इकाई ले जाने वाला केवल एक यात्री न रह जाए। अंततः, यह यात्री सबसे दूर बिंदु तक पहुँचने के लिए एक इकाई दूरी तय कर सकता है। कुल मिलाकर, n यात्री सबसे लंबी दूरी तक पहुँच सकते हैं

\mathrm {travel} (n)={\frac {n-1}{n+1}}+1=2-{\frac {2}{n+1}}

इसे m के बराबर करके, m इकाई दूरी तय करने के लिए आवश्यक यात्रियों की न्यूनतम संख्या का समाधान निकाला जा सकता है। ध्यान दें कि समाधान केवल m<2 के लिए सम्मलित होती हैं।

यदि अंतिम और अंतिम यात्री को भी प्रारम्भिक बेस पर लौटने की आवश्यकता है, तो वह अकेले केवल 1/(n+1) यूनिट की यात्रा करेगा जिससे की उसके पास लौटने के लिए n/(n+1) यूनिट की आपूर्ति हो, इसलिए सबसे लंबी दूरी n यात्री पहुंच सकते हैं

\mathrm {travel_{return}} (n)={\frac {n}{n+1}}=1-{\frac {1}{n+1}}

इसे m के बराबर करके, m इकाई दूरी तय करने के लिए आवश्यक यात्रियों की न्यूनतम संख्या का समाधान निकाला जा सकता है। ध्यान दें कि समाधान केवल m<1 के लिए सम्मलित होते हैं।

'रेगिस्तान के पार कारों की समस्या' में, मान लें कि n कारें ईंधन की n इकाइयों के साथ प्रारम्भिक मूल भाग से निकलती हैं। 1/n इकाई की दूरी के बाद, समूह पहले ही ईंधन की ठीक एक इकाई की खपत कर चुका होगा; इस बिंदु पर, उन्हें अपने बीच ईंधन स्थानांतरित करना चाहिए, एक खाली कार को पीछे छोड़ना चाहिए, और (n-1) कारों के बीच ईंधन की (n-1) इकाइयों को ले जाना चाहिए। अन्य 1/(n-1) इकाइयों की दूरी के बाद, समूह ने ईंधन की एक और इकाई की खपत कर ली होगी; फिर से, उन्हें ईंधन स्थानांतरित करना चाहिए, एक खाली कार पीछे छोड़नी चाहिए, और (n-2) कारों के बीच ईंधन की (n-2) इकाइयाँ ले जानी चाहिए। समूह तब तक चलता रहता है और एक कार को कम करता रहता है, जब तक कि ईंधन की ठीक एक इकाई ले जाने वाली केवल एक कार न रह जाए। अंततः, यह यात्री सबसे दूर बिंदु तक पहुँचने के लिए एक इकाई दूरी तय कर सकता है। कुल मिलाकर, n कारें सबसे लंबी दूरी तक पहुंच सकती हैं वह nवां हार्मोनिक नंबर है:

H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}

इसे m के बराबर करके, m इकाई दूरी तय करने के लिए आवश्यक कारों की न्यूनतम संख्या का समाधान निकाला जा सकता है।

स्वतंत्रता का आदेश

ध्यान दें कि जीप यात्राओं का क्रम निश्चित नहीं है। उदाहरण के लिए समस्या के रेगिस्तानी संस्करण की खोज में, जीप बना सकती है $n - 1$ बेस और पहले ईंधन डंप के बीच राउंड-ट्रिप, प्रस्थान $(n - 1) / n$ ईंधन की इकाइयाँ हर बार ईंधन डंप पर जाती हैं और फिर एक बनाती हैं $n$ -पहले ईंधन डंप के लिए एकतरफ़ा यात्रा, इस प्रकार कुल मिलाकर वहाँ पहुँचना $(n - 1) + 1/(2 n)$ ईंधन की इकाइयाँ उपलब्ध होता हैं। वह $1/(2 n)$ इकाइयों को सबसे अंत में और दूसरे मूल भाग पर वापसी यात्रा के लिए सहेजा जाता है $n - 1$ ईंधन की इकाइयों का उपयोग पहले और दूसरे ईंधन डंप के बीच ईंधन को स्थानांतरित करने के लिए किया जाता है और इसी तरह। $n - 2$ राउंड-ट्रिप और फिर एक $(n -1)$ -दूसरे ईंधन डंप के लिए एकतरफ़ा यात्रा करते है।

व्यावहारिक अनुप्रयोग

ऑपरेशन ब्लैक बक#ब्लैक_बक_वन में, हमलावर वल्कन को बाहर की यात्रा पर सात बार और वापसी की यात्रा पर एक बार ईंधन भरा गया था। ग्रे रेखाएं हताहतों की संख्या की भरपाई के लिए आरक्षित विमान का संकेत देती हैं।

समस्या का युद्धकालीन स्थितियों में व्यावहारिक अनुप्रयोग हो सकता है, विशेषकर ईंधन दक्षता के संबंध में। द्वितीय विश्व युद्ध में बी-29 द्वारा जापान पर बमबारी के संदर्भ में, रॉबर्ट मैकनामारा ने फिल्म द फॉग ऑफ वॉर में कहा है कि ईंधन को आगे के ठिकानों तक पहुंचाने के कारण होने वाली ईंधन दक्षता के मुद्दे को समझना इस योजना का मुख्य कारण था। द्वीप पर जाने की योजना के पक्ष में चीन की मुख्य भूमि से बमबारी प्रारंभ करने का निर्णय छोड़ दिया गया:

""हमें उन विमानों को कंसास के बेस से भारत तक उड़ाना था।फिर हमें चीन में कूबड़ के ऊपर से ईंधन उड़ाना पड़ा। [...] हमें ये बी-29 लेने थे—वहां कोई टैंकर विमान नहीं था। हमें उनमें ईंधन भरना था, भारत से चेंगतू तक उड़ान भरनी थी; ईंधन उतारो; भारत वापस उड़ान भरें; चेंगतु में ईंधन बनाने के लिए पर्याप्त मिशन बनाएं; यवाता, जापान के लिए उड़ान भरें; इस्पात मिलों पर बमबारी करें; और भारत वापस जाओ चेंगतु में ईंधन बनाने के लिए पर्याप्त मिशन बनाएं; यवाता, जापान के लिए उड़ान भरें; इस्पात मिलों पर बमबारी करें; और भारत वापस जाओ. [ईंधन] दक्षता को अधिकतम करने की इस समस्या पर हमारे पास बहुत कम प्रशिक्षण था, हमने वास्तव में पाया कि ईंधन उतारने के अतिरिक्त कुछ बी-29 को वापस लेना पड़ा, उन्हें इसे लेना पड़ा। एक लंबी कहानी को छोटा करने के लिए, यह बहुत मूल्यवान नहीं थी। और यह लेमे ही था जो वास्तव में उस निष्कर्ष पर पहुंचा, और प्रमुखों को पूरी चीज़ को मारियाना में स्थानांतरित करने के लिए प्रेरित किया, जिसने जापान को तबाह कर दिया।"

(द्वितीय विश्व युद्ध के अंत में हिरोशिमा और नागासाकी पर परमाणु बमबारी उत्तरी मारियाना द्वीप समूह में प्रशांत महासागर के टीआई वर्ष द्वीप से बी-29 सुपर किले का उपयोग करके की गई थी।)

इन विचारों के अनुप्रयोग के लिए ऑपरेशन ब्लैक बक भी देखें। फ़ॉकलैंड युद्ध के समय आयोजित इन मिशनों में, शाही वायु सेना ने एस्केन्शन द्वीप पर स्थित एवरो वल्कन बमवर्षकों को फ़ॉकलैंड द्वीप समूह में लक्ष्य पर बमबारी करने में सक्षम बनाने के लिए टैंकरों को खड़ा करके हवा से हवा में ईंधन भरने का उपयोग किया है।

यह भी देखें

हार्मोनिक श्रृंखला (गणित)|हार्मोनिक श्रृंखला (गणित)
अनुकूलन (गणित)

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Weisstein, Eric W. "Jeep Problem". MathWorld.
↑ Gardner, Martin (1994). My Best Mathematical and Logic Puzzles. Dover. pp. 53. ISBN 0-486-28152-3.
↑ ^3.0 ^3.1 ^3.2 "Exploration problems. Another common question is concerned with the maximum distance into a desert which could be reached from a frontier settlement by an explorer capable of carrying provisions that would last him for a days." W. W. Rouse Ball and H.S.M. Coxeter (1987). Mathematical Recreations and Essays, Thirteenth Edition, Dover, p32. ISBN 0-486-25357-0.
↑ Problems to Sharpen the Young, John Hadley and David Singmaster, The Mathematical Gazette, 76, #475 (March 1992), pp. 102–126.
↑ "Puzzle 15 | (Camel and Banana Puzzle)". GeeksforGeeks (in English). 2015-03-11. Retrieved 2020-02-04.
↑ "रेगिस्तान के पार यात्री". mathforum.org. Retrieved 2020-02-04.{{cite web}}: CS1 maint: url-status (link)
↑ "रेगिस्तान के पार कारें पहेली - समाधान". www.mathsisfun.com. Retrieved 2020-02-04.
↑ Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling, Gunter Rote and Guochuan Zhang, June 1996

[wolfram-1] 1.0 ^1.1 ^1.2 Weisstein, Eric W. "Jeep Problem". MathWorld.

[2] Gardner, Martin (1994). My Best Mathematical and Logic Puzzles. Dover. pp. 53. ISBN 0-486-28152-3.

[coxeter-3] 3.0 ^3.1 ^3.2 "Exploration problems. Another common question is concerned with the maximum distance into a desert which could be reached from a frontier settlement by an explorer capable of carrying provisions that would last him for a days." W. W. Rouse Ball and H.S.M. Coxeter (1987). Mathematical Recreations and Essays, Thirteenth Edition, Dover, p32. ISBN 0-486-25357-0.

[a-4] Problems to Sharpen the Young, John Hadley and David Singmaster, The Mathematical Gazette, 76, #475 (March 1992), pp. 102–126.

[5] "Puzzle 15 | (Camel and Banana Puzzle)". GeeksforGeeks (in English). 2015-03-11. Retrieved 2020-02-04.

[6] "रेगिस्तान के पार यात्री". mathforum.org. Retrieved 2020-02-04.{{cite web}}: CS1 maint: url-status (link)

[7] "रेगिस्तान के पार कारें पहेली - समाधान". www.mathsisfun.com. Retrieved 2020-02-04.

[8] Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling, Gunter Rote and Guochuan Zhang, June 1996

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 130: / Line 130: @@
 == संदर्भ ==
 {{reflist}}
-[[Category: गणितीय अनुकूलन]] [[Category: मनोरंजक गणित]] [[Category: तर्क पहेलियाँ]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 maint]]
 [[Category:Created On 05/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with broken file links]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:गणितीय अनुकूलन]]
+[[Category:तर्क पहेलियाँ]]
+[[Category:मनोरंजक गणित]]

Anonymous

Search

जीप समस्या: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:23, 15 July 2023

Contents