आपको संचालन अनुसंधान की मूल अवधारणाओं और परिभाषाओं को सीखना चाहिए।

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

टिप्पणी 1

समस्या के निर्माण पर ध्यान दिया जाना चाहिए: निर्णय लेना स्वयं संचालन अनुसंधान के दायरे से परे है और जिम्मेदार व्यक्ति या व्यक्तियों के समूह की क्षमता से संबंधित है, जो गणितीय रूप से उचित के अलावा अन्य विचारों को ध्यान में रख सकते हैं।

टिप्पणी 2

यदि संचालन अनुसंधान के कुछ कार्यों में इष्टतम समाधान वह है जिसमें चुना गया दक्षता मानदंड अधिकतम या न्यूनतम मान लेता है, तो अन्य कार्यों में यह बिल्कुल भी आवश्यक नहीं है। इसलिए, समस्या में, हम इष्टतम पर विचार कर सकते हैं, उदाहरण के लिए, ऐसे कई आउटलेट और कर्मचारी जिनमें औसत ग्राहक सेवा समय अधिक नहीं है, उदाहरण के लिए, 5 मिनट, और किसी भी समय औसत कतार की लंबाई होगी 3 से अधिक लोग न हों (1, पृष्ठ .10-11)।

उत्पादन और वाणिज्यिक गतिविधियों की दक्षता काफी हद तक विभिन्न स्तरों के प्रबंधकों द्वारा दैनिक आधार पर लिए गए निर्णयों की गुणवत्ता से निर्धारित होती है। इस संबंध में, निर्णय लेने की प्रक्रियाओं में सुधार के कार्य, जिन्हें संचालन अनुसंधान हल करने की अनुमति देता है, का बहुत महत्व है। "ऑपरेशन रिसर्च" शब्द का प्रयोग पहली बार 1939-1940 में किया गया था। सैन्य क्षेत्र में। इस समय तक, वैज्ञानिक और तकनीकी क्रांति के परिणामस्वरूप सैन्य उपकरण और उसका प्रबंधन मौलिक रूप से अधिक जटिल हो गया था। और इसलिए, द्वितीय विश्व युद्ध की शुरुआत तक, नए सैन्य उपकरणों के प्रभावी उपयोग, मात्रात्मक मूल्यांकन और कमांड द्वारा किए गए निर्णयों के अनुकूलन के क्षेत्र में वैज्ञानिक अनुसंधान करने की तत्काल आवश्यकता थी। युद्ध के बाद की अवधि में, शांतिपूर्ण क्षेत्रों में नए वैज्ञानिक अनुशासन की सफलताओं की मांग थी: उद्योग, उद्यमशीलता और वाणिज्यिक गतिविधियों में, सरकारी संस्थानों में और शैक्षणिक संस्थानों में।

संचालन अनुसंधान उद्देश्यपूर्ण मानव गतिविधि के सभी क्षेत्रों में समस्याओं के समाधान को सही ठहराने के लिए गणितीय मात्रात्मक तरीकों को लागू करने की एक पद्धति है। संचालन अनुसंधान के तरीके और मॉडल आपको ऐसे समाधान प्राप्त करने की अनुमति देते हैं जो संगठन के लक्ष्यों को सर्वोत्तम रूप से पूरा करते हैं।

संचालन अनुसंधान संगठनात्मक प्रणालियों के सबसे प्रभावी (या इष्टतम) प्रबंधन के लिए विधियों के विकास और व्यावहारिक अनुप्रयोग से संबंधित विज्ञान है।

संचालन अनुसंधान का मुख्य सिद्धांत इस प्रकार है: इष्टतम समाधान (नियंत्रण) चर के मूल्यों का एक ऐसा सेट है जो ऑपरेशन की दक्षता मानदंड (उद्देश्य कार्य) के इष्टतम (अधिकतम या न्यूनतम) मूल्य को प्राप्त करता है और निरीक्षण करता है निर्दिष्ट प्रतिबंध।

संचालन अनुसंधान का विषय अपने कामकाज की प्रभावशीलता के आकलन के आधार पर नियंत्रण के साथ एक प्रणाली में इष्टतम निर्णय लेने की समस्या है। संचालन अनुसंधान की विशिष्ट अवधारणाएं हैं: मॉडल, चर चर, बाधाएं, उद्देश्य कार्य।

वास्तव में संचालन अनुसंधान का विषय संगठनात्मक प्रबंधन प्रणाली (संगठन) है, जिसमें बड़ी संख्या में परस्पर क्रिया करने वाले विभाग होते हैं, और विभागों के हित हमेशा एक दूसरे के अनुरूप नहीं होते हैं और विपरीत हो सकते हैं।

संचालन अनुसंधान का उद्देश्य संगठनों के प्रबंधन पर किए गए निर्णयों को मात्रात्मक रूप से प्रमाणित करना है।

जो समाधान पूरे संगठन के लिए सबसे अधिक फायदेमंद साबित होता है, उसे इष्टतम कहा जाता है, और जो समाधान एक या अधिक विभागों के लिए सबसे अधिक फायदेमंद होता है, वह उप-इष्टतम होगा।

संगठनात्मक प्रबंधन की एक विशिष्ट समस्या के उदाहरण के रूप में, जहां विभागों के परस्पर विरोधी हित टकराते हैं, एक उद्यम की सूची के प्रबंधन की समस्या पर विचार करें।

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

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

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

संचालन अनुसंधान की मुख्य विशेषताएं:

1. उत्पन्न समस्या के विश्लेषण के लिए एक व्यवस्थित दृष्टिकोण। सिस्टम दृष्टिकोण, या सिस्टम विश्लेषण, संचालन अनुसंधान का मुख्य कार्यप्रणाली सिद्धांत है, जो इस प्रकार है। कोई भी कार्य, चाहे वह पहली नज़र में कितना ही निजी क्यों न हो, संपूर्ण प्रणाली के कामकाज की कसौटी पर उसके प्रभाव के दृष्टिकोण से माना जाता है। ऊपर, व्यवस्थित दृष्टिकोण को सूची प्रबंधन समस्या के उदाहरण द्वारा चित्रित किया गया था।

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

3. संचालन अनुसंधान की आवश्यक विशेषताओं में से एक समस्या का इष्टतम समाधान खोजने की इच्छा है। हालांकि, उपलब्ध संसाधनों (पैसा, कंप्यूटर समय) या आधुनिक विज्ञान के स्तर द्वारा लगाई गई सीमाओं के कारण ऐसा समाधान अक्सर अप्राप्य हो जाता है। उदाहरण के लिए, कई संयोजन समस्याओं के लिए, विशेष रूप से, मशीनों की संख्या n> 4 के साथ शेड्यूलिंग की समस्याएं, गणित के आधुनिक विकास के साथ इष्टतम समाधान केवल विकल्पों की एक साधारण गणना द्वारा पाया जा सकता है। फिर व्यक्ति को अपने आप को "काफी अच्छा" या उप-समाधान की खोज तक सीमित रखना होगा। इसलिए, इसके रचनाकारों में से एक, टी। साती ने संचालन अनुसंधान को "... उन व्यावहारिक प्रश्नों के खराब उत्तर देने की कला के रूप में परिभाषित किया, जिन्हें अन्य तरीकों से और भी बदतर उत्तर दिए गए हैं।"

4. परिचालन अनुसंधान की एक विशेषता यह है कि इसे कई क्षेत्रों में जटिल तरीके से किया जाता है। इस तरह का अध्ययन करने के लिए एक परिचालन समूह बनाया जा रहा है। इसमें ज्ञान के विभिन्न क्षेत्रों के विशेषज्ञ शामिल हैं: इंजीनियर, गणितज्ञ, अर्थशास्त्री, समाजशास्त्री, मनोवैज्ञानिक। ऐसे परिचालन समूहों को बनाने का कार्य समस्या के समाधान को प्रभावित करने वाले कारकों के पूरे सेट और विभिन्न विज्ञानों के विचारों और विधियों के उपयोग का व्यापक अध्ययन है।

प्रत्येक प्रचालनात्मक अनुसंधान क्रम में निम्नलिखित मुख्य चरणों से गुजरता है:

1) नियोजन कार्य का विवरण,

2) एक गणितीय मॉडल का निर्माण,

3) समाधान खोजना,

4) मॉडल की जाँच और सुधार,

5) व्यवहार में पाए गए समाधान का कार्यान्वयन।

योजना कार्य का विवरण:

नेटवर्क योजना और प्रबंधन के कार्य

संचालन (कार्यों) के एक बड़े परिसर को पूरा करने की समय सीमा और परिसर के सभी कार्यों की शुरुआत के क्षणों के बीच संबंधों पर विचार करें। इन कार्यों में संचालन के एक सेट की न्यूनतम अवधि, लागत का इष्टतम अनुपात और उनके कार्यान्वयन के समय का पता लगाना शामिल है।

कतारबद्ध कार्य अनुप्रयोगों या आवश्यकताओं की कतारों के साथ कतारबद्ध प्रणालियों के अध्ययन और विश्लेषण के लिए समर्पित हैं और इसमें सिस्टम के प्रदर्शन संकेतक, उनकी इष्टतम विशेषताओं, उदाहरण के लिए, सेवा चैनलों की संख्या, सेवा समय, आदि का निर्धारण करना शामिल है।

इन्वेंट्री प्रबंधन कार्य इन्वेंट्री स्तर (ऑर्डर पॉइंट) और ऑर्डर आकार के इष्टतम मूल्यों को खोजना है। ऐसे कार्यों की ख़ासियत यह है कि स्टॉक के स्तर में वृद्धि के साथ, एक तरफ उनके भंडारण की लागत बढ़ जाती है, लेकिन दूसरी ओर, स्टॉक किए गए उत्पाद की संभावित कमी के कारण नुकसान कम हो जाता है।

संसाधन आवंटन की समस्याएं संचालन (कार्यों) के एक निश्चित सेट के साथ उत्पन्न होती हैं जिन्हें सीमित उपलब्ध संसाधनों के साथ किया जाना चाहिए, और संचालन या संचालन की संरचना के बीच संसाधनों के इष्टतम वितरण को खोजने के लिए आवश्यक है।

उपकरण के टूट-फूट और समय के साथ इसे बदलने की आवश्यकता के कारण उपकरणों की मरम्मत और प्रतिस्थापन के कार्य प्रासंगिक हैं। कार्यों को इष्टतम समय, निवारक मरम्मत और जांच की संख्या, साथ ही आधुनिकीकरण के साथ उपकरण प्रतिस्थापन के क्षणों को निर्धारित करने के लिए कम किया जाता है।

शेड्यूलिंग (शेड्यूलिंग) का कार्य विभिन्न प्रकार के उपकरणों पर संचालन के इष्टतम अनुक्रम (उदाहरण के लिए, प्रसंस्करण भागों) को निर्धारित करना है।

नियोजन और प्लेसमेंट का कार्य नई वस्तुओं की संख्या और स्थान का निर्धारण करना है, मौजूदा वस्तुओं के साथ और आपस में उनकी बातचीत को ध्यान में रखते हुए।

मार्ग चयन की समस्याएं, या नेटवर्क की समस्याएं, अक्सर परिवहन और संचार प्रणाली में विभिन्न समस्याओं के अध्ययन में सामने आती हैं और सबसे किफायती मार्गों (1, पृष्ठ 15) को निर्धारित करने में शामिल होती हैं।

संचालनकिसी भी घटना (कार्य प्रणाली) को एक योजना द्वारा एकजुट किया जाता है और एक विशिष्ट लक्ष्य को प्राप्त करने की दिशा में निर्देशित किया जाता है। ऑपरेशन हमेशा होता है को नियंत्रितघटना, यानी इसके संगठन की विशेषता वाले कुछ मापदंडों को चुनने की विधि का निपटान करना संभव है। इन विकल्पों को कहा जाता है नियंत्रण चर.

ऐसे चरों के किसी निश्चित विकल्प को कहते हैं फेसला।निर्णय सफल और असफल, उचित और अनुचित हो सकते हैं। इष्टतमऐसे समाधानों को नाम दें जो कुछ मानदंडों के अनुसार दूसरों के लिए बेहतर हों।

संचालन अनुसंधान का उद्देश्य इष्टतम समाधानों का प्रारंभिक मात्रात्मक औचित्य है, जिनमें से एक से अधिक हो सकते हैं। निर्णय का अंतिम विकल्प संचालन अनुसंधान के दायरे से परे जाता है और तथाकथित निर्णय सिद्धांत के माध्यम से किया जाता है।

संचालन अनुसंधान के किसी भी कार्य में प्रारंभिक "अनुशासनात्मक" शर्तें होती हैं, अर्थात। ऐसा प्रारंभिक डेटा जो शुरू से ही तय होता है और उसका उल्लंघन नहीं किया जा सकता है। साथ में, वे संभावित समाधानों का तथाकथित सेट बनाते हैं।

विभिन्न समाधानों की प्रभावशीलता की तुलना करने के लिए, आपके पास एक मात्रात्मक मानदंड होना चाहिए जिसे कहा जाता है कार्यनिष्पादन संकेतक(या उद्देश्य समारोह)। यह सूचक ऑपरेशन के लक्ष्य अभिविन्यास को प्रतिबिंबित करने के लिए चुना जाता है।

अक्सर ऑपरेशन यादृच्छिक कारकों की कार्रवाई के साथ होता है। फिर, मूल्य ही नहीं, जिसे हम अनुकूलित करना चाहते हैं, लेकिन इसका औसत मूल्य (या गणितीय अपेक्षा) दक्षता के संकेतक के रूप में लिया जाता है।

कभी-कभी यादृच्छिक कारकों के साथ एक ऑपरेशन ऐसे लक्ष्य का पीछा करता है। लेकिन, जो या तो पूरी तरह से हासिल किया जा सकता है या बिल्कुल भी हासिल नहीं किया जा सकता है (जैसे "हां - नहीं")। फिर इस लक्ष्य को प्राप्त करने की संभावना को दक्षता के संकेतक के रूप में चुना जाता है। पी(ए) (यदि एक पी(ए) = 0 या 1, तो हम साइबरनेटिक्स में प्रसिद्ध "ब्लैक बॉक्स" समस्या पर पहुंचते हैं।)

प्रदर्शन संकेतक का गलत चुनाव बहुत खतरनाक है। असफल रूप से चुने गए मानदंड के अनुसार आयोजित संचालन से अनुचित लागत और हानि हो सकती है। (उदाहरण के लिए, "शाफ्ट" किसी उद्यम की आर्थिक गतिविधि के मूल्यांकन के लिए मुख्य मानदंड के रूप में।)

1.3. संचालन अनुसंधान के कार्य का सामान्य विवरण

संचालन अनुसंधान कार्य दो श्रेणियों में आते हैं: ए) प्रत्यक्ष और बी) उलटा।

प्रत्यक्ष कार्यप्रश्न का उत्तर दें: दक्षता संकेतक क्या होगा जेडयदि दी गई शर्तों के तहत आप  यूकुछ निर्णय लिया जाएगा एक्स  एक्स. ऐसी समस्या को हल करने के लिए, एक गणितीय मॉडल बनाया गया है जो दी गई शर्तों और समाधान के माध्यम से दक्षता संकेतक को व्यक्त करने की अनुमति देता है, अर्थात्:

कहाँ पे
दिए गए कारक (प्रारंभिक डेटा),

नियंत्रण चर (समाधान),

जेड- प्रदर्शन संकेतक (उद्देश्य समारोह),

एफ- चर के बीच कार्यात्मक निर्भरता।

विभिन्न मॉडलों में यह निर्भरता अलग-अलग तरीकों से व्यक्त की जाती है। के बीच निर्भरता तथा आमतौर पर सीमा के रूप में व्यक्त किया जाता है

यदि निर्भरता का प्रकार एफज्ञात, फिर संकेतक जेडप्रत्यक्ष प्रतिस्थापन द्वारा पाया जाता है तथा इस कार्यक्षमता के लिए।

उलटा समस्याप्रश्न का उत्तर दें: कैसे, दी गई शर्तों के तहत एक समाधान चुनें
ताकि प्रदर्शन संकेतक जेडअधिकतम (न्यूनतम) में बदल गया। ऐसी समस्या को समाधान अनुकूलन समस्या कहा जाता है।

सीधी समस्या को हल होने दें, यानी। ऑपरेशन मॉडल सेट है और निर्भरता का प्रकार एफज्ञात। फिर व्युत्क्रम समस्या (अर्थात अनुकूलन समस्या) को निम्नानुसार तैयार किया जा सकता है।

ढूँढना चाहता थाऐसा निर्णय
जिस पर दक्षता संकेतक जेड = चुनना:

यह सूत्र इस तरह पढ़ता है: जेडएक इष्टतम मूल्य है
संभावित समाधानों के सेट में शामिल सभी समाधानों को अपने हाथ में ले लिया एक्स.

दक्षता संकेतक के चरम की खोज करने की विधि जेडऔर संबंधित इष्टतम समाधान हमेशा फ़ंक्शन की विशेषताओं के आधार पर चुना जाना चाहिए एफऔर समाधान पर लगाए गए बाधाओं के प्रकार। (उदाहरण के लिए, एक क्लासिक रैखिक प्रोग्रामिंग समस्या।)

1. आईओ . की बुनियादी अवधारणाएं

और उस बारे में – वैज्ञानिक अनुशासन, विभिन्न संगठनात्मक प्रणालियों के सबसे प्रभावी प्रबंधन के लिए विधियों के विकास और व्यावहारिक अनुप्रयोग में लगे हुए हैं।

आईओ में निम्नलिखित खंड शामिल हैं:

1) गणितीय कार्यक्रम। (योजनाओं की पुष्टि, आर्थिक गतिविधि के कार्यक्रम); इसमें अनुभाग शामिल हैं: रैखिक कार्यक्रम, गैर-रेखीय कार्यक्रम, गतिशील कार्यक्रम

2) यादृच्छिक प्रक्रियाओं के सिद्धांत के आधार पर कतार का सिद्धांत;

3) गेम थ्योरी, जो सूचना की अपूर्णता की शर्तों के तहत किए गए निर्णयों को प्रमाणित करना संभव बनाता है।

एक विशिष्ट नियंत्रण समस्या को हल करते समय, IO विधियों के उपयोग में शामिल हैं:

जटिल परिस्थितियों में या अनिश्चितता की स्थिति में निर्णय लेने की समस्याओं के लिए आर्थिक और गणितीय मॉडल का निर्माण;

अंतर्संबंधों का अध्ययन जो बाद के निर्णय लेने का निर्धारण करते हैं, और प्रदर्शन मानदंड स्थापित करते हैं जो किसी को कार्रवाई के एक या दूसरे पाठ्यक्रम के लाभ का मूल्यांकन करने की अनुमति देते हैं।

आईओ की मूल अवधारणाएं और परिभाषाएं।

संचालन – लक्ष्य प्राप्त करने के उद्देश्य से कोई भी नियंत्रित गतिविधि। ऑपरेशन का परिणाम इसके कार्यान्वयन की विधि, संगठन पर निर्भर करता है, अन्यथा - कुछ मापदंडों की पसंद पर। एक ऑपरेशन हमेशा एक नियंत्रित घटना होती है, यानी यह हम पर निर्भर करता है कि इसके संगठन की विशेषता वाले कुछ पैरामीटर कैसे चुनें। यहां "संगठन" शब्द के व्यापक अर्थ में समझा जाता है, जिसमें ऑपरेशन में उपयोग किए जाने वाले तकनीकी साधनों का सेट भी शामिल है।

मापदंडों के किसी दिए गए विकल्प को कहा जाता है फेसला . निर्णय सफल और असफल, उचित और अनुचित हो सकते हैं। इष्टतम उन समाधानों पर विचार करें जो एक कारण या किसी अन्य के लिए दूसरों के लिए बेहतर हैं। संचालन अनुसंधान का मुख्य कार्य इष्टतम समाधानों का प्रारंभिक मात्रात्मक औचित्य है।

ऑपरेशन मॉडल – यह गणितीय उपकरण (विभिन्न प्रकार के कार्यों, समीकरणों, समीकरणों की प्रणाली और असमानताओं, आदि) का उपयोग करके ऑपरेशन का काफी सटीक विवरण है। एक ऑपरेशन मॉडल तैयार करने के लिए वर्णित घटना के सार और गणितीय तंत्र के ज्ञान को समझने की आवश्यकता है।

संचालन दक्षता – कार्य की पूर्ति के लिए इसकी अनुकूलन क्षमता की डिग्री मात्रात्मक रूप से दक्षता मानदंड के रूप में व्यक्त की जाती है - उद्देश्य कार्य। दक्षता मानदंड का चुनाव अध्ययन के व्यावहारिक मूल्य को निर्धारित करता है। (गलत तरीके से चुना गया मानदंड हानिकारक हो सकता है, क्योंकि इस तरह की दक्षता की कसौटी के तहत आयोजित संचालन कभी-कभी अनुचित लागत का कारण बनता है।)

नेटवर्क योजना और प्रबंधन के कार्य संचालन (कार्यों) के एक बड़े परिसर को पूरा करने की समय सीमा और परिसर के सभी कार्यों की शुरुआत के क्षणों के बीच संबंधों पर विचार करें। इन कार्यों में संचालन के एक परिसर की न्यूनतम अवधि, लागत का इष्टतम अनुपात और उनके कार्यान्वयन के समय का पता लगाना शामिल है।

कतारबद्ध कार्य अनुप्रयोगों या आवश्यकताओं की कतारों के साथ कतारबद्ध प्रणालियों के अध्ययन और विश्लेषण के लिए समर्पित और सिस्टम के प्रदर्शन संकेतक, उनकी इष्टतम विशेषताओं, उदाहरण के लिए, सेवा चैनलों की संख्या, सेवा समय आदि का निर्धारण करने में शामिल हैं।

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

संसाधन आवंटन कार्य संचालन (कार्य) के एक निश्चित सेट के साथ उत्पन्न होता है जिसे सीमित उपलब्ध संसाधनों के साथ किया जाना चाहिए, और संचालन या संचालन की संरचना के बीच संसाधनों के इष्टतम वितरण को खोजने के लिए आवश्यक है।

उपकरण मरम्मत और प्रतिस्थापन कार्य उपकरण के टूट-फूट और समय के साथ इसे बदलने की आवश्यकता के कारण प्रासंगिक। कार्यों को इष्टतम समय, निवारक मरम्मत और जांच की संख्या, साथ ही आधुनिकीकरण के साथ उपकरण प्रतिस्थापन के क्षणों को निर्धारित करने के लिए कम किया जाता है।

शेड्यूलिंग (शेड्यूलिंग) कार्य विभिन्न प्रकार के उपकरणों पर संचालन के इष्टतम अनुक्रम (उदाहरण के लिए, प्रसंस्करण भागों) को निर्धारित करने में शामिल हैं।

योजना और नियुक्ति कार्य एनआईएमौजूदा वस्तुओं के साथ और आपस में उनकी बातचीत को ध्यान में रखते हुए, नई वस्तुओं की इष्टतम संख्या और स्थान का निर्धारण करना शामिल है।

मार्ग चयन कार्य, या नेटवर्क परिवहन और संचार प्रणाली में विभिन्न समस्याओं के अध्ययन में सबसे अधिक बार आने वाले कार्य और सबसे किफायती मार्गों का निर्धारण करना शामिल है।

2. रैखिक कार्यक्रम का सामान्य कार्य। इष्टतम समाधान

आर्थिक और गणितीय मॉडल

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

एलपी विधियों को व्यावहारिक समस्याओं पर लागू किया जाता है जिसमें: 1) संभव लोगों के एक सेट से सबसे अच्छा समाधान (इष्टतम योजना) चुनना आवश्यक है; 2) समाधान को कुछ परिमाण चर के मूल्यों के एक सेट के रूप में व्यक्त किया जा सकता है; ए) समस्या की विशिष्ट स्थितियों द्वारा व्यवहार्य समाधानों पर लगाए गए प्रतिबंध रैखिक समीकरणों या असमानताओं के रूप में तैयार किए जाते हैं; 4) लक्ष्य को मुख्य चरों के रैखिक फलन के रूप में व्यक्त किया जाता है। उद्देश्य फ़ंक्शन के मूल्य, आपको विभिन्न समाधानों की तुलना करने की अनुमति देते हैं, समाधान की गुणवत्ता के लिए एक मानदंड के रूप में कार्य करते हैं।

किसी आर्थिक समस्या के गणितीय तरीकों से व्यावहारिक समाधान के लिए सबसे पहले उसे आर्थिक-गणितीय मॉडल का उपयोग करके लिखा जाना चाहिए। आर्थिक-गणितीय मॉडल - जांच की गई आर्थिक प्रक्रिया या वस्तु का गणितीय विवरण। यह मॉडल गणितीय संबंधों का उपयोग करते हुए आर्थिक प्रक्रिया के पैटर्न को अमूर्त रूप में व्यक्त करता है।

मॉडल निर्माण की सामान्य योजना: I

1) एक निश्चित संख्या में चर का चुनाव, असाइनमेंट - संख्यात्मक मान जिनमें से अध्ययन के तहत घटना के संभावित राज्यों में से एक को विशिष्ट रूप से निर्धारित करता है;

2) अध्ययन के तहत घटना में निहित संबंधों की अभिव्यक्ति, गणितीय संबंधों (समीकरणों, असमानताओं) के रूप में। ये संबंध समस्या बाधाओं की एक प्रणाली बनाते हैं;

3) एक उद्देश्य समारोह के रूप में चयनित इष्टतमता मानदंड की मात्रात्मक अभिव्यक्ति; मैं

4) समस्या का गणितीय सूत्रीकरण, उद्देश्य फ़ंक्शन के चरम को खोजने की समस्या के रूप में, चर पर लगाए गए बाधाओं के अधीन।

रैखिक प्रोग्रामिंग की सामान्य समस्याकी तरह लगता है:

m रैखिक समीकरणों और n चर के साथ असमानताओं की एक प्रणाली को देखते हुए

और रैखिक कार्य

सिस्टम X=(x1,x2,…,xj,…,xn) के लिए ऐसा समाधान खोजना आवश्यक है, जहां रैखिक फ़ंक्शन F इष्टतम (अर्थात अधिकतम या न्यूनतम) मान लेता है।

सिस्टम (1) को बाधा प्रणाली कहा जाता है, और फ़ंक्शन F को एक रैखिक फ़ंक्शन, एक रैखिक रूप, एक उद्देश्य फ़ंक्शन या एक उद्देश्य फ़ंक्शन कहा जाता है।

अधिक संक्षेप में, सामान्य रैखिक प्रोग्रामिंग समस्या को इस प्रकार दर्शाया जा सकता है:

प्रतिबंधों के साथ:

इष्टतम समाधान (या इष्टतम योजना)एलपी समस्या एक समाधान है X=(x1,x2,…,xj,…,xn), बाधा प्रणाली का (1), जो स्थिति (3) को संतुष्ट करता है, जिसके तहत रैखिक कार्य (2) इष्टतम (अधिकतम या अधिकतम) लेता है न्यूनतम मूल्य।

बशर्ते कि सभी चर गैर-ऋणात्मक हों, बाधाओं की प्रणाली (1) में केवल असमानताएं होती हैं - ऐसी रैखिक प्रोग्रामिंग समस्या को मानक (सममित) कहा जाता है; यदि व्यवरोधों के निकाय में केवल समीकरण होते हैं, तो समस्या को विहित कहा जाता है।

विहित समस्या का एक विशेष मामला मूल रूप में समस्या है, जो कि बाधा वेक्टर के सभी गुणांक में भिन्न है बीगैर-ऋणात्मक हैं, और प्रत्येक समीकरण में 1 के गुणांक वाला एक चर होता है, जो किसी अन्य समीकरण में शामिल नहीं होता है। इस गुण के साथ एक चर को आधार चर कहा जाता है।

मानक और विहित समस्याएं सामान्य के विशेष मामले हैं। उनमें से प्रत्येक का उपयोग अपने विशिष्ट क्षेत्र में किया जाता है। इसके अलावा, सभी तीन सूत्र एक दूसरे के बराबर हैं: किसी भी रैखिक प्रोग्रामिंग समस्या को सरल गणितीय परिवर्तनों का उपयोग करके एक विहित, मानक या सामान्य समस्या में कम किया जा सकता है।

4 . रैखिक बीजगणित के तत्व

n चर वाले m रैखिक समीकरणों के निकाय का रूप है:

या आशुलिपि में

n चर वाले m रैखिक समीकरणों के निकाय का कोई भी m चर (m .)< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

m . शर्त के तहत सिस्टम (2.1) को हल करने के लिए< n сформулируем утверждение.

कथन 2.1. अगर सिस्टम के लिएएमके साथ रैखिक समीकरणएनचर (एम < एन) चरों के गुणांकों के मैट्रिक्स की रैंक m के बराबर है, अर्थात। बुनियादी चर का कम से कम एक समूह है, तो यह प्रणाली अनिश्चित है, और गैर-मूल चर के मूल्यों का प्रत्येक मनमाना सेट सिस्टम के एक समाधान से मेल खाता है।

समाधानसिस्टम (2.1) के X=(x1,x2,…,xn) को स्वीकार्य कहा जाता है यदि इसमें केवल गैर-ऋणात्मक घटक होते हैं, अर्थात। xj>=0 किसी भी j=1,n के लिए। अन्यथा, समाधान को अमान्य कहा जाता है।

सिस्टम के समाधानों के अनंत सेट के बीच, तथाकथित बुनियादी समाधान प्रतिष्ठित हैं।

मूल समाधान n चर वाले m रैखिक समीकरणों की एक प्रणाली को एक समाधान कहा जाता है जिसमें सभी n-m गैर-मूल चर शून्य के बराबर होते हैं।

रैखिक प्रोग्रामिंग समस्याओं में, स्वीकार्य बुनियादी समाधान, या, जैसा कि उन्हें भी कहा जाता है, समर्थन योजनाएं, विशेष रुचि के हैं। एक मूल समाधान जिसमें कम से कम एक मुख्य चर शून्य के बराबर होता है, पतित कहलाता है।

बिंदुओं के उत्तल सेट

उत्तल बहुभुज को गैर-उत्तल बहुभुज से अलग करने वाली सामान्य परिभाषित संपत्ति यह है कि यदि आप इसके दो बिंदुओं को लेते हैं और उन्हें एक खंड से जोड़ते हैं, तो पूरा खंड इस बहुभुज से संबंधित होगा। इस गुण को बिंदुओं के उत्तल समुच्चय की परिभाषा के रूप में लिया जा सकता है।

बिन्दुओं के समुच्चय को उत्तल कहते हैं, यदि यह, अपने किन्हीं दो बिंदुओं के साथ, इन बिंदुओं को जोड़ने वाला संपूर्ण खंड समाहित करता है।

उत्तल समुच्चयों का एक महत्वपूर्ण होता है संपत्ति: किसी भी संख्या में उत्तल समुच्चयों का प्रतिच्छेदन (सामान्य भाग) उत्तल समुच्चय होता है।

उत्तल समुच्चय के बिंदुओं के बीच, कोई आंतरिक, सीमा और कोने के बिंदुओं को अलग कर सकता है।

सेट के बिंदु को आंतरिक कहा जाता है, यदि इसके कुछ पड़ोस में केवल इस सेट के बिंदु हैं।

समुच्चय के बिंदु को सीमा कहते हैं, यदि इसके किसी पड़ोस में दिए गए सेट से संबंधित दोनों बिंदु और इससे संबंधित बिंदु नहीं हैं।

रैखिक प्रोग्रामिंग समस्याओं में कोने के बिंदु विशेष रुचि रखते हैं। समुच्चय का बिंदु कहलाता है कोणीय(या चरम) यदि यह किसी भी खंड के लिए आंतरिक नहीं है जो पूरी तरह से दिए गए सेट से संबंधित है।

अंजीर पर। 2.4 बहुभुज के विभिन्न बिंदुओं के उदाहरण दिखाता है: आंतरिक (बिंदु एम), सीमा (बिंदु एन) और कोने (बिंदु ए, बी, सी, डी, ई)। बिंदु A कोणीय है, क्योंकि किसी भी खंड के लिए जो पूरी तरह से बहुभुज से संबंधित है, उदाहरण के लिए, खंड AP, यह आंतरिक नहीं है; बिंदु A खंड KL का आंतरिक है, लेकिन यह खंड पूरी तरह से बहुभुज से संबंधित नहीं है।

एक उत्तल सेट के लिए, कोने के बिंदु हमेशा बहुभुज (पॉलीहेड्रॉन) के कोने के साथ मेल खाते हैं, जबकि एक ही समय में, यह एक गैर-उत्तल सेट के लिए आवश्यक नहीं है। बिंदुओं के एक समूह को बंद कहा जाता है यदि इसमें इसके सभी सीमा बिंदु शामिल हों। बिंदुओं के समूह को कहा जाता है सीमित, यदि सेट के किसी भी बिंदु पर केंद्रित परिमित लंबाई की त्रिज्या की एक गेंद (वृत्त) है जिसमें दिया गया सेट पूरी तरह से है; अन्यथा सेट को अनबाउंड कहा जाता है।

एक समतल में बिंदुओं का एक उत्तल बंद सेट जिसमें कोने के बिंदुओं की एक सीमित संख्या होती है, उत्तल बहुभुज कहा जाता है यदि यह घिरा हुआ है, और उत्तल बहुभुज क्षेत्र यदि यह असीम है।

असमानताओं, समीकरणों और उनकी प्रणालियों के समाधान का ज्यामितीय अर्थ

आइए असमानताओं के समाधान पर विचार करें।

कथन 1. दो चरों वाली असमानता के समाधान का समुच्चय a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=बी1.

वांछित आधा-विमान (ऊपरी या निचला) निर्धारित करने के लिए, एक मनमाना नियंत्रण बिंदु स्थापित करने की अनुशंसा की जाती है जो इसकी सीमा पर स्थित नहीं है - निर्मित रेखा। यदि असमानता को नियंत्रण बिंदु पर संतुष्ट किया जाता है, तो यह नियंत्रण बिंदु वाले आधे तल के सभी बिंदुओं पर भी संतुष्ट होता है, और दूसरे आधे तल के सभी बिंदुओं पर संतुष्ट नहीं होता है। और इसके विपरीत, यदि असमानता नियंत्रण बिंदु पर संतुष्ट नहीं है, तो यह नियंत्रण बिंदु वाले आधे-तल के सभी बिंदुओं पर संतुष्ट नहीं है, और दूसरे आधे-तल के सभी बिंदुओं पर संतुष्ट है। एक नियंत्रण बिंदु के रूप में, निर्देशांक O (0; 0) का मूल लेना सुविधाजनक होता है, जो निर्मित रेखा पर नहीं होता है।

असमानताओं की प्रणालियों के समाधान के सेट पर विचार करें।

अभिकथन 2. दो चरों में रैखिक असमानताओं की एक संगत प्रणाली m के समाधान का सेट एक उत्तल बहुभुज (या एक उत्तल बहुभुज क्षेत्र) है।

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

कोने के बिंदुओं के निर्देशांक - बहुभुज के कोने संबंधित रेखाओं के प्रतिच्छेदन बिंदुओं के निर्देशांक के रूप में पाए जाते हैं।

असमानताओं की प्रणालियों के समाधान के क्षेत्रों का निर्माण करते समय, अन्य मामले भी हो सकते हैं: समाधानों का सेट एक उत्तल बहुभुज क्षेत्र है (चित्र। 2.9, ए); एक बिंदु (चित्र। 2.9, बी); एक खाली सेट जब असमानताओं की प्रणाली असंगत है (चित्र। 2.9, सी)।

5 . एलपी समस्याओं को हल करने के लिए ज्यामितीय विधि

एलपी समस्या का इष्टतम समाधान

प्रमेय 1. यदि एलपी समस्या का इष्टतम समाधान है, तो रैखिक फ़ंक्शन समाधान पॉलीहेड्रॉन के कोने बिंदुओं में से एक पर अपना अधिकतम मान लेता है। यदि एक रैखिक फलन एक से अधिक कोने वाले बिंदुओं पर अधिकतम मान लेता है, तो वह इसे किसी भी बिंदु पर लेता है जो इन बिंदुओं का उत्तल रैखिक संयोजन है।

प्रमेय एलपी समस्याओं को हल करने के प्रमुख तरीके को इंगित करता है। वास्तव में, इस प्रमेय के अनुसार, स्वीकार्य समाधानों के अनंत सेट का अध्ययन करने के बजाय, उनमें से वांछित इष्टतम समाधान खोजने के लिए, समाधान पॉलीहेड्रॉन के कोने बिंदुओं की केवल एक सीमित संख्या का अध्ययन करना आवश्यक है।

निम्नलिखित प्रमेय कोने के बिंदुओं को खोजने के लिए विश्लेषणात्मक विधि के लिए समर्पित है।

प्रमेय 2। एलपी समस्या का प्रत्येक स्वीकार्य मूल समाधान समाधान पॉलीहेड्रॉन के कोने बिंदु से मेल खाता है, और इसके विपरीत, समाधान पॉलीहेड्रॉन के प्रत्येक कोने बिंदु पर एक स्वीकार्य मूल समाधान से मेल खाता है।

एक महत्वपूर्ण परिणाम प्रमेय 1 और 2 से तुरंत अनुसरण करता है: यदि किसी एलपी समस्या का इष्टतम समाधान है, तो यह इसके कम से कम एक व्यवहार्य मूल समाधान के साथ मेल खाता है।

इसलिए, एलपी समस्या के रैखिक कार्य के इष्टतम को इसके स्वीकार्य बुनियादी समाधानों की एक सीमित संख्या के बीच मांगा जाना चाहिए।

तो, एलपी समस्या के स्वीकार्य समाधान (समाधान पॉलीहेड्रॉन) का सेट एक उत्तल पॉलीहेड्रॉन (या उत्तल पॉलीहेड्रल क्षेत्र) है, और समस्या का इष्टतम समाधान समाधान पॉलीहेड्रॉन के कोने बिंदुओं में से कम से कम एक में स्थित है।

मानक रूप में दो चर के साथ एक समस्या पर विचार करें (पी = 2).

मान लीजिए कि बाधाओं की प्रणाली का ज्यामितीय प्रतिनिधित्व एक बहुभुज है एबीसीडीई(चित्र। 4.1)। इस बहुभुज के बिंदुओं में से एक ऐसा बिंदु खोजना आवश्यक है जिस पर रैखिक कार्य F=c1x1+c2x2 अधिकतम (या न्यूनतम) मान लेता है।

तथाकथित पर विचार करें स्तर रेखा रैखिक प्रकार्य एफ, अर्थात। रेखा जिसके साथ यह फ़ंक्शन समान निश्चित मान लेता है एक, अर्थात। एफ = एक,या c1x1+c2x2=a.

समाधान बहुभुज पर, वह बिंदु ज्ञात कीजिए जिससे होकर फलन की समतल रेखा गुजरती है एफ सबसे बड़े (यदि रैखिक फ़ंक्शन को अधिकतम किया गया है) या सबसे छोटा (यदि इसे छोटा किया गया है) स्तर के साथ।

फ़ंक्शन की स्तर रेखा का समीकरण c1x1+c2x2=a एक सीधी रेखा का समीकरण है। विभिन्न स्तरों पर एकस्तर रेखाएँ समानांतर होती हैं, क्योंकि उनके ढलान केवल गुणांक c1 और c2 के बीच के अनुपात से निर्धारित होते हैं और इसलिए, समान होते हैं। तो फीचर लेवल लाइन्स एफ – ये अजीबोगरीब "समानांतर" हैं, जो आमतौर पर समन्वय अक्षों के कोण पर स्थित होते हैं।

एक रेखीय फलन की स्तर रेखा का एक महत्वपूर्ण गुण यह है कि एक दिशा में रेखा के समानांतर बदलाव के साथ, स्तर केवल बढ़ता है, और दूसरी दिशा में बदलाव के साथ, यह केवल घटता है। मूल से शुरू होने वाला वेक्टर c=(c1,c2) ​​फ़ंक्शन F की सबसे तेज़ वृद्धि की दिशा को इंगित करता है। रैखिक फ़ंक्शन की स्तर रेखा वेक्टर c=(c1,c2) ​​के लंबवत है।

एलपी समस्या के चित्रमय समाधान की प्रक्रिया:

1. एक हल बहुभुज की रचना कीजिए।

2. एक सदिश c = (c1, c2) की रचना कीजिए और इसके लिए एक रैखिक फलन के स्तर की एक रेखा खींचिए एफ, उदाहरण के लिए, एफ = 0।

3. बिंदु Amax(Bmin) को खोजने के लिए वेक्टर c(-c) की दिशा में सीधी रेखा F=0 का समानांतर विस्थापन, जहां F अपने अधिकतम (न्यूनतम) तक पहुंचता है।

1. इष्टतम बिंदु पर प्रतिच्छेद करने वाली रेखाओं के समीकरणों को एक साथ हल करने पर, इसके निर्देशांक ज्ञात कीजिए।

2. Fmax (Fmin) की गणना करें।

टिप्पणी।न्यूनतम बिंदु निर्णय बहुभुज में "प्रवेश" बिंदु है, और अधिकतम बिंदु बहुभुज से "निकास" बिंदु है।

6. सिंप्लेक्स विधि का सामान्य विचार। ज्यामितीय व्याख्या

ग्राफिकल विधि रैखिक प्रोग्रामिंग समस्याओं के एक बहुत ही संकीर्ण वर्ग पर लागू होती है: यह दो से अधिक चर वाली समस्याओं को प्रभावी ढंग से हल कर सकती है। रैखिक प्रोग्रामिंग के मुख्य प्रमेयों पर विचार किया गया, जिससे यह निम्नानुसार है कि यदि एक रैखिक प्रोग्रामिंग समस्या का इष्टतम समाधान होता है, तो यह समाधान पॉलीहेड्रॉन के कम से कम एक कोने बिंदु से मेल खाता है और कम से कम स्वीकार्य बुनियादी समाधानों में से एक के साथ मेल खाता है बाधा प्रणाली। किसी भी रैखिक प्रोग्रामिंग समस्या को हल करने का एक तरीका इंगित किया गया था: बाधा प्रणाली के व्यवहार्य बुनियादी समाधानों की एक सीमित संख्या की गणना करने के लिए और उनमें से एक को चुनें जिस पर लक्ष्य फ़ंक्शन इष्टतम निर्णय लेता है। ज्यामितीय रूप से, यह समाधान पॉलीहेड्रॉन के सभी कोने बिंदुओं की गणना से मेल खाता है। इस तरह की गणना अंततः एक इष्टतम समाधान (यदि यह मौजूद है) की ओर ले जाएगी, लेकिन इसका व्यावहारिक कार्यान्वयन भारी कठिनाइयों से जुड़ा हुआ है, क्योंकि वास्तविक समस्याओं के लिए व्यवहार्य बुनियादी समाधानों की संख्या, हालांकि सीमित है, बहुत बड़ी हो सकती है।

गणना किए जाने वाले स्वीकार्य बुनियादी समाधानों की संख्या को कम किया जा सकता है यदि गणना यादृच्छिक रूप से नहीं की जाती है, लेकिन रैखिक कार्य में परिवर्तन को ध्यान में रखते हुए, यानी। यह सुनिश्चित करने की कोशिश करना कि प्रत्येक अगला समाधान रैखिक फ़ंक्शन के मूल्यों के संदर्भ में पिछले एक की तुलना में "बेहतर" (या कम से कम "बदतर नहीं") है (अधिकतम खोजने पर इसे बढ़ाना, न्यूनतम खोजने पर इसे घटाना) . इस तरह की गणना किसी को इष्टतम खोजने में चरणों की संख्या को कम करने की अनुमति देती है। आइए इसे एक ग्राफिकल उदाहरण के साथ समझाते हैं।

एक बहुभुज द्वारा संभव समाधान के क्षेत्र का प्रतिनिधित्व करने दें एबीसीडीई. मान लीजिए इसका कोना बिंदु लेकिनमूल स्वीकार्य मूल समाधान से मेल खाती है। एक यादृच्छिक गणना को बहुभुज के पांच कोने बिंदुओं के अनुरूप पांच व्यवहार्य बुनियादी समाधानों का प्रयास करना होगा। हालाँकि, चित्र से पता चलता है कि शीर्ष के बाद लेकिनअगली चोटी पर जाना फायदेमंद पर,और फिर इष्टतम बिंदु पर से।पांच के बजाय, केवल तीन शीर्षों को पार किया गया, जिससे रैखिक कार्य में लगातार सुधार हुआ।

समाधान के क्रमिक सुधार के विचार ने रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए एक सार्वभौमिक विधि का आधार बनाया - योजना के क्रमिक सुधार की सरल विधि या विधि।

सिंप्लेक्स विधि का ज्यामितीय अर्थ बाधा पॉलीहेड्रॉन के एक शीर्ष (प्रारंभिक एक कहा जाता है) से पड़ोसी एक में क्रमिक संक्रमण होता है, जिसमें रैखिक फ़ंक्शन के संबंध में सबसे अच्छा (कम से कम सबसे खराब नहीं) मान लेता है समस्या का लक्ष्य; जब तक इष्टतम समाधान नहीं मिल जाता है - वह शीर्ष जहां लक्ष्य फ़ंक्शन का इष्टतम मूल्य पहुंच जाता है (यदि समस्या का एक सीमित इष्टतम है)।

सिम्प्लेक्स विधि पहली बार 1949 में अमेरिकी वैज्ञानिक जे। डेंजिग द्वारा प्रस्तावित की गई थी, लेकिन 1939 की शुरुआत में, विधि के विचारों को रूसी वैज्ञानिक एल.वी. द्वारा विकसित किया गया था। कांटोरोविच।

सिंप्लेक्स विधि, जो किसी भी रैखिक प्रोग्रामिंग समस्या को हल करने की अनुमति देती है, सार्वभौमिक है। वर्तमान में, इसका उपयोग कंप्यूटर गणना के लिए किया जाता है, लेकिन सिंप्लेक्स विधि का उपयोग करके सरल उदाहरणों को मैन्युअल रूप से भी हल किया जा सकता है।

सिंप्लेक्स विधि को लागू करने के लिए - समाधान के क्रमिक सुधार - इसमें महारत हासिल करना आवश्यक है तीन मुख्य तत्व:

समस्या के कुछ प्रारंभिक व्यवहार्य बुनियादी समाधान निर्धारित करने की एक विधि;

सर्वोत्तम (अधिक सटीक, सबसे खराब नहीं) समाधान के लिए संक्रमण का नियम;

पाए गए समाधान की इष्टतमता की जाँच के लिए मानदंड।

सिंप्लेक्स पद्धति का उपयोग करने के लिए, रैखिक प्रोग्रामिंग समस्या को विहित रूप में कम किया जाना चाहिए, अर्थात। बाधाओं की प्रणाली को समीकरणों के रूप में प्रस्तुत किया जाना चाहिए।

साहित्य पर्याप्त विस्तार से वर्णन करता है: प्रारंभिक संदर्भ योजना (प्रारंभिक व्यवहार्य बुनियादी समाधान) खोजना, कृत्रिम आधार विधि का उपयोग करना, इष्टतम संदर्भ योजना ढूंढना, सरल तालिकाओं का उपयोग करके समस्याओं को हल करना।

7 . सिंप्लेक्स विधि का एल्गोरिथ्म।

आइए हम सरल विधि द्वारा एलएलपी के समाधान पर विचार करें और इसे अधिकतम समस्या के संबंध में प्रस्तुत करें।

1. समस्या की स्थिति के अनुसार, इसका गणितीय मॉडल संकलित किया जाता है।

2. निर्मित मॉडल को विहित रूप में बदल दिया गया है। इस मामले में, एक प्रारंभिक संदर्भ योजना वाला आधार बाहर खड़ा हो सकता है।

3. समस्या का विहित मॉडल एक सिंप्लेक्स तालिका के रूप में लिखा गया है ताकि सभी मुक्त शब्द गैर-ऋणात्मक हों। यदि प्रारंभिक संदर्भ योजना का चयन किया जाता है, तो चरण 5 पर जाएँ।

सिंप्लेक्स टेबल: प्रतिबंधात्मक समीकरणों की एक प्रणाली और एक उद्देश्य फ़ंक्शन को प्रारंभिक आधार के संबंध में हल किए गए भावों के रूप में दर्ज किया जाता है। वह रेखा जिसमें वस्तुनिष्ठ फलन F के गुणांकों को प्रविष्ट किया जाता है, F-रेखा या वस्तुनिष्ठ फलन की रेखा कहलाती है।

4. प्रारंभिक संदर्भ योजना न्यूनतम सिम्प्लेक्स अनुपात के अनुरूप सकारात्मक रिज़ॉल्यूशन तत्वों के साथ सिम्प्लेक्स ट्रांसफॉर्मेशन करके पाई जाती है, और एफ-पंक्ति के तत्वों के संकेतों को ध्यान में रखते हुए नहीं। यदि परिवर्तन के क्रम में 0-पंक्ति है, जिसके सभी तत्व, मुक्त पद को छोड़कर, शून्य हैं, तो समस्या के प्रतिबंधात्मक समीकरणों की प्रणाली असंगत है। यदि, हालांकि, एक 0-पंक्ति है, जिसमें मुक्त पद के अलावा, कोई अन्य सकारात्मक तत्व नहीं हैं, तो प्रतिबंधात्मक समीकरणों की प्रणाली का कोई गैर-ऋणात्मक समाधान नहीं है।

सिस्टम की कमी (2.55), (2.56) को एक नए आधार पर कहा जाएगा सिंप्लेक्स परिवर्तन . यदि एक सिंप्लेक्स परिवर्तन को औपचारिक बीजगणितीय ऑपरेशन के रूप में माना जाता है, तो यह देखा जा सकता है कि इस ऑपरेशन के परिणामस्वरूप, रैखिक कार्यों की एक निश्चित प्रणाली में शामिल दो चर के बीच भूमिकाओं को पुनर्वितरित किया जाता है: एक चर निर्भर से स्वतंत्र में जाता है, और दूसरा इसके विपरीत - स्वतंत्र से आश्रित तक। इस ऑपरेशन को बीजगणित में जाना जाता है जॉर्डन उन्मूलन कदम।

5. इष्टतमता के लिए मिली प्रारंभिक मूल योजना की जांच की जाती है:

ए) यदि एफ-पंक्ति में कोई नकारात्मक तत्व नहीं हैं (मुक्त अवधि की गिनती नहीं), तो योजना इष्टतम है। यदि कोई शून्य नहीं है, तो इष्टतम योजना अद्वितीय है; यदि कम से कम एक शून्य है, तो अनंत संख्या में इष्टतम योजनाएं हैं;

बी) यदि एफ-पंक्ति में कम से कम एक नकारात्मक तत्व है, जो गैर-सकारात्मक तत्वों के कॉलम से मेल खाता है, तो;

सी) यदि एफ-पंक्ति में कम से कम एक नकारात्मक तत्व है, और उसके कॉलम में कम से कम एक सकारात्मक तत्व है, तो हम एक नई संदर्भ योजना पर स्विच कर सकते हैं जो इष्टतम के करीब है। ऐसा करने के लिए, निर्दिष्ट कॉलम को न्यूनतम सिंप्लेक्स अनुपात द्वारा हल करने के रूप में असाइन किया जाना चाहिए, हल करने वाली पंक्ति ढूंढें और एक सरल परिवर्तन करें। परिणामी आधार योजना की इष्टतमता के लिए पुन: जांच की जाती है। वर्णित प्रक्रिया तब तक दोहराई जाती है जब तक कि एक इष्टतम योजना प्राप्त नहीं हो जाती या जब तक समस्या का समाधान नहीं हो जाता।

आधार में शामिल एक चर के गुणांकों के स्तंभ को हल करना कहा जाता है। इस प्रकार, एफ-पंक्ति के नकारात्मक तत्व द्वारा आधार में पेश किए गए एक चर को चुनना (या एक समाधान कॉलम चुनना), हम यह सुनिश्चित करते हैं कि फ़ंक्शन एफ बढ़ता है .

आधार से बाहर किए जाने वाले चर का निर्धारण करना थोड़ा अधिक कठिन है। ऐसा करने के लिए, वे मुक्त सदस्यों के अनुपात को हल करने वाले कॉलम के सकारात्मक तत्वों (ऐसे संबंधों को सिम्प्लेक्स कहा जाता है) के अनुपात में बनाते हैं और उनमें से सबसे छोटा पाते हैं, जो बहिष्कृत चर वाले पंक्ति (समाधान) को निर्धारित करता है। नए संदर्भ डिजाइन में आधार घटकों की सकारात्मकता, जैसा कि पहले ही स्थापित किया जा चुका है, न्यूनतम सिंप्लेक्स अनुपात गारंटी के अनुसार आधार (या हल करने वाली स्ट्रिंग की पसंद) से बाहर किए जाने वाले चर का विकल्प।

एल्गोरिथम के चरण 3 में, यह माना जाता है कि मुक्त पदों के कॉलम के सभी तत्व गैर-ऋणात्मक हैं। यह आवश्यकता आवश्यक नहीं है, लेकिन यदि इसे पूरा किया जाता है, तो बाद के सभी सिंप्लेक्स परिवर्तन केवल सकारात्मक संकल्प तत्वों के साथ किए जाते हैं, जो गणना के लिए सुविधाजनक है। यदि मुक्त सदस्यों के कॉलम में ऋणात्मक संख्याएँ हैं, तो हल करने वाले तत्व को इस प्रकार चुना जाता है:

1) कुछ नकारात्मक मुक्त सदस्य के अनुरूप रेखा को देखें, उदाहरण के लिए, एक टी-पंक्ति, और उसमें किसी भी नकारात्मक तत्व का चयन करें, और इसके अनुरूप कॉलम को अनुमति के रूप में लिया जाता है (हम मानते हैं कि समस्या की बाधाएं संगत हैं );

2) मुक्त सदस्यों के कॉलम के तत्वों के अनुपात को हल करने वाले कॉलम के संबंधित तत्वों के अनुपात में बनाते हैं जिनमें समान संकेत होते हैं (सरल अनुपात);

3) सरलतम संबंधों में से सबसे छोटा चुनें। यह अनुमति स्ट्रिंग निर्धारित करेगा। इसे रहने दो, उदाहरण के लिए, आर-रेखा;

4) हल करने वाले स्तंभों और पंक्तियों के प्रतिच्छेदन पर एक हल करने वाला तत्व पाया जाता है। यदि y-स्ट्रिंग का तत्व हल करने वाला निकला, तो सिंप्लेक्स परिवर्तन के बाद इस स्ट्रिंग का मुक्त सदस्य सकारात्मक हो जाएगा। अन्यथा, अगले चरण में, टी-पंक्ति को फिर से संबोधित किया जाता है। यदि समस्या हल करने योग्य है, तो निश्चित चरणों के बाद मुक्त शर्तों के कॉलम में कोई नकारात्मक तत्व नहीं होंगे।

8. उलटा मैट्रिक्स विधि

फॉर्म के एलपी पर विचार करें:

ए बाधा मैट्रिक्स है;

C=(c1,c2,…,cn)-वेक्टर-पंक्ति;

एक्स=(x1,x2,…,xn) - चर;

दाईं ओर का वेक्टर है।

हम मानते हैं कि सभी समीकरण रैखिक रूप से स्वतंत्र हैं, अर्थात, रैंक (ए) = एम। इस मामले में, आधार मैट्रिक्स ए के क्रम का नाबालिग है। यानी, क्रम m का कम से कम एक सबमैट्रिक्स B ऐसा है कि |B|<>0. B के संगत सभी अज्ञात मूल कहलाते हैं। अन्य सभी स्वतंत्र हैं।

बी को कुछ आधार होने दें। फिर, मैट्रिक्स ए के कॉलम को क्रमित करके, कोई हमेशा ए को ए = (बी | एन) के रूप में ला सकता है,

जहां एन एक सबमैट्रिक्स है जिसमें मैट्रिक्स ए के कॉलम शामिल हैं जो आधार से संबंधित नहीं हैं। उसी तरह, वेक्टर x को - मूल चर के वेक्टर और में विभाजित करना संभव है।

समस्या का कोई भी समाधान (1) शर्त को संतुष्ट करता है A*x=b, और, परिणामस्वरूप, सिस्टम निम्नलिखित रूप लेता है:

इसलिये |बी|<>0 है, तो एक व्युत्क्रम मैट्रिक्स है। बाईं ओर के व्युत्क्रम से गुणा करने पर, हम प्राप्त करते हैं:

- आम निर्णय।

एक मूल समाधान (आधार बी के संबंध में) शर्त के तहत प्राप्त समस्या (2) का एक विशेष समाधान है। फिर यह विशिष्ट रूप से निर्धारित होता है।

मूल समाधान कहा जाता है अनुभव करने योग्य, यदि।

लागू बुनियादी समाधान के अनुरूप आधार। बुलाया वसूली योग्य आधार। मूल समाधान को पतित कहा जाता है यदि वेक्टर में शून्य घटक होते हैं।

सामान्य समाधान में मौजूद सभी समाधान होते हैं। आइए ऑब्जेक्टिव फंक्शन पर लौटते हैं। हम Cb-गुणांक को मूल चरों के सामने पेश करते हैं, Cn-बाकी।

इस प्रकार, हम प्राप्त करते हैं। हम सामान्य समाधान से प्रतिस्थापित करते हैं:

कथन। बुनियादी समाधान के लिए इष्टतमता मानदंड।

हम कहते हैं। तब मूल समाधान इष्टतम है। यदि, तो मूल समाधान इष्टतम नहीं है।

डॉक-इन:होने देना। मूल समाधान पर विचार करें, .

इसलिए, मूल समाधान के लिए उद्देश्य फलन का मान है।

चलो एक और समाधान हो: (एक्सबी, एक्सएन)।

फिर हम देखते हैं

इस प्रकार, मूल समाधान न्यूनतम है। चलो, इसके विपरीत, धारण न करें, अर्थात। मौजूद।

फिर एक समाधान है जिसके लिए उद्देश्य फ़ंक्शन का मान मूल समाधान के लिए उद्देश्य फ़ंक्शन के मान से कम होगा।

चलो एक मुक्त चर Xi:Xj से मेल खाता है, एक मान निर्दिष्ट करें और इसे आधार में पेश करें, और एक और चर प्राप्त करें और इसे निःशुल्क कॉल करें।

कैसे निर्धारित करें? को छोड़कर सभी मुक्त चर अभी भी 0 हैं।

फिर सामान्य समाधान में, जहां।

हम निकालते हैं: - एक आवश्यक शर्त।

एक मूल समाधान को नियमित कहा जाता है यदि। हम चर को आधार से प्राप्त करते हैं। एक नए समाधान के साथ, उद्देश्य फलन कम हो जाता है, क्योंकि

कलन विधि:

1. मानक रूप में एलपी समस्या।

2. हम रैखिक रूप से स्वतंत्र समीकरण छोड़ते हैं।

3. ऐसा आव्यूह B ज्ञात कीजिए कि |B|<>0 और मूल समाधान।

हम गणना करते हैं:

यदि, तो एक इष्टतम समाधान है - यह मूल समाधान है;

यदि, तो हम घटक पाते हैं, इसे संलग्न करते हैं, इस प्रकार हम एक और समाधान पाएंगे; - जिस पर मूल चर में से एक = 0। हम इस चर को आधार से हटाते हैं, xi दर्ज करते हैं। हमने आधार B1 से एक नया आधार B2 संयुग्म प्राप्त किया है। फिर हम फिर से गणना करते हैं।

1. यदि कोई इष्टतम समाधान है, तो सीमित चरणों के बाद हम इसे प्राप्त करेंगे।

ज्यामितीय रूप से, प्रक्रिया को एक कोने बिंदु से एक संयुग्मित कोने बिंदु पर सेट एक्स की सीमा के साथ एक संक्रमण के रूप में व्याख्या की जाती है, समस्या के समाधान का सेट। इसलिये कोने बिंदुओं की एक सीमित संख्या है और फ़ंक्शन एफ (एक्स) की सख्त कमी एक ही चरम बिंदु से दो बार गुजरने से मना करती है, फिर यदि कोई इष्टतम समाधान है, तो सीमित चरणों के बाद हम इसे प्राप्त करेंगे।

9. समस्या की आर्थिक व्याख्या, संसाधनों के उपयोग की दोहरी समस्या

एक कार्य।दो प्रकार के उत्पादों P1 और P2 के निर्माण के लिए, चार प्रकार के संसाधनों S1, S2, S3, S4 का उपयोग किया जाता है। संसाधनों के भंडार को देखते हुए, उत्पादन की एक इकाई के निर्माण पर खर्च किए गए संसाधनों की इकाइयों की संख्या। उत्पादन P1 और P2 की एक इकाई से प्राप्त लाभ ज्ञात है। उत्पादों के उत्पादन के लिए एक योजना तैयार करना आवश्यक है जिसमें इसकी बिक्री से लाभ अधिकतम होगा।

एक कार्यमैं(मूल):

F=c1x1+c2x2+…+CnXn->अधिकतम प्रतिबंधों के साथ:

और गैर-नकारात्मकता की स्थिति x1>=0, x2>=0,…,Xn>=0

ऐसी उत्पादन योजना तैयार करें X=(x1,x2,…,Xn), जिसमें उत्पादों की बिक्री से लाभ (राजस्व) अधिकतम होगा, बशर्ते कि प्रत्येक प्रकार के उत्पाद के लिए संसाधनों की खपत उपलब्ध से अधिक न हो शेयरों

एक कार्यद्वितीय(दोहरी)

Z=b1y1+b2y2+…+BmYm->min

प्रतिबंधों के साथ:

और गैर-नकारात्मकता की स्थिति

y1>=0, y2>=0,…,yn>=0.

संसाधनों की कीमतों (अनुमान) का ऐसा सेट खोजें Y=(y1,y2,…,yn), जिस पर संसाधनों की कुल लागत न्यूनतम होगी, बशर्ते कि प्रत्येक प्रकार के उत्पाद के उत्पादन में संसाधनों की लागत होगी इस उत्पादों की बिक्री से होने वाले लाभ (राजस्व) से कम नहीं

उपरोक्त मॉडल में, bi(i=1,2,…,m) संसाधन Si के स्टॉक को दर्शाता है; ऐज- उत्पादन की एक इकाई के उत्पादन में खपत की गई संसाधन इकाइयों की संख्या Pj(j=1,2,…,n); मुख्य न्यायाधीश- उत्पादन की एक इकाई की बिक्री से लाभ (राजस्व) Pj (या उत्पादन की कीमत Pj) .

मान लेते हैं कि किसी संगठन ने एंटरप्राइज़ संसाधन S1,S2,…,Sm खरीदने का निर्णय लिया है और इन संसाधनों y1,y2,…,ym के लिए इष्टतम मूल्य निर्धारित करना आवश्यक है। यह स्पष्ट है कि क्रय संगठन इस तथ्य में रुचि रखता है कि सभी संसाधनों की लागत Z मात्रा में b1,b2,…,bm कीमतों पर y1,y2,…,ym, क्रमशः न्यूनतम थे, अर्थात। Z=b1,y1+b2y2+…+bmym->min.

दूसरी ओर, संसाधनों को बेचने वाला एक उद्यम इस तथ्य में रुचि रखता है कि प्राप्त राजस्व उस राशि से कम नहीं है जो उद्यम को तैयार उत्पादों में संसाधनों को संसाधित करते समय प्राप्त हो सकता है।

संसाधन S1 की A11 इकाइयाँ, संसाधन S2 की a21 इकाइयाँ,…।, aj1 संसाधन की इकाइयाँ Si1,……, संसाधन Sm की am1 इकाइयाँ y1,y1,…,yi मूल्य पर उत्पाद P1 की एक इकाई के उत्पादन पर खर्च की जाती हैं। ,…,यम, क्रमशः। इसलिए, विक्रेता की आवश्यकताओं को पूरा करने के लिए, उत्पादन P1 की एक इकाई के निर्माण में उपभोग किए गए संसाधनों की लागत कम से कम इसकी कीमत c1 होनी चाहिए, अर्थात। a11y1+a21y2+…+am1ym>=c1.

इसी तरह, प्रत्येक प्रकार के उत्पाद P1,P2,…Pn के लिए असमानताओं के रूप में बाधाओं की रचना करना संभव है। आर्थिक-गणितीय मॉडल और इस प्रकार प्राप्त दोहरी समस्या II की सार्थक व्याख्या तालिका के दाहिने हिस्से में दी गई है।

संसाधन मूल्य y1,y1,…,yi,…,ym को आर्थिक साहित्य में विभिन्न नाम प्राप्त हुए हैं: लेखांकन, निहित, छाया . इन नामों का अर्थ है कि सशर्त , "नकली" कीमतें। उत्पादों के लिए "बाहरी" कीमतों c1,c2,…,cn के विपरीत, जिन्हें एक नियम के रूप में जाना जाता है, उत्पादन शुरू होने से पहले, संसाधनों की कीमतें y1,y2,…,ym हैं आंतरिक , क्योंकि वे बाहर से सेट नहीं होते हैं, लेकिन समस्या को हल करने के परिणामस्वरूप सीधे निर्धारित होते हैं, इसलिए उन्हें अक्सर कहा जाता है अनुमान साधन।

10. पारस्परिक रूप से दोहरी एलपी समस्याएं और उनके गुण

आइए तालिका में प्रस्तुत रैखिक प्रोग्रामिंग की दो समस्याओं I और II पर औपचारिक रूप से विचार करें, जो उनके आर्थिक और गणितीय मॉडल में शामिल मापदंडों की सार्थक व्याख्या से अलग हैं।

दोनों कार्यों में निम्नलिखित हैं गुण:

1. एक समस्या में, वे अधिकतम एक रेखीय फलन की तलाश में हैं, दूसरे में - एक न्यूनतम।

2. एक समस्या के रैखिक फलन में चरों के गुणांक दूसरी समस्या में व्यवरोध प्रणाली के मुक्त सदस्य होते हैं।

3. प्रत्येक समस्या को मानक रूप में दिया गया है, और अधिकतमकरण समस्या में रूप की सभी असमानताओं को "<=", а в задаче минимизации – все неравенства вида ">=".

4. दोनों समस्याओं के व्यवरोधों के निकाय में चरों के गुणांकों के आव्यूह एक-दूसरे को स्थानांतरित किए जाते हैं।

5. एक समस्या के व्यवरोधों के निकाय में असमानताओं की संख्या उतनी ही होती है जितनी कि दूसरी समस्या में चरों की संख्या।

6. दोनों समस्याओं में चरों की गैर-नकारात्मकता की शर्तें संरक्षित हैं।

टिप्पणी।यदि मूल समस्या का j-वें चर गैर-नकारात्मकता की स्थिति के अधीन है, तो दोहरी समस्या का j-वें बाधा एक असमानता होगी, लेकिन यदि j-वें चर सकारात्मक और नकारात्मक दोनों मान ले सकता है, तो दोहरी समस्या का j-वें अवरोध एक समीकरण होगा; मूल समस्या की बाधाएं और दोहरी समस्या के चर समान रूप से संबंधित हैं।

संकेतित गुणों के साथ रैखिक प्रोग्रामिंग की दो समस्याएं I और II सममित पारस्परिक रूप से दोहरी समस्याएं कहलाती हैं। निम्नलिखित में, सरलता के लिए, हम उन्हें सरलता से कहेंगे दोहरे कार्य।

प्रत्येक एलपी समस्या को उसकी दोहरी समस्या से जोड़ा जा सकता है।

11. दोहरी समस्या को संकलित करने के लिए एल्गोरिदम:

1. मूल समस्या की बाधा प्रणाली की सभी असमानताओं को एक अर्थ में लाओ: यदि मूल समस्या में अधिकतम रैखिक कार्य की मांग की जाती है, तो बाधा प्रणाली की सभी असमानताएं रूप में कम हो जाती हैं "<=", а если минимум – к виду ">="। उन असमानताओं के लिए जिनमें यह आवश्यकता पूरी नहीं होती है, -1 से गुणा करें।

2. सिस्टम ए का एक संवर्धित मैट्रिक्स संकलित करें, जिसमें चर के लिए गुणांक का एक मैट्रिक्स, प्रतिबंधों की प्रणाली के मुक्त सदस्यों का एक स्तंभ और एक रैखिक फ़ंक्शन में चर के लिए गुणांक की एक पंक्ति शामिल है।

3. मैट्रिक्स ए में स्थानांतरित मैट्रिक्स खोजें .

4. परिणामी मैट्रिक्स के आधार पर एक दोहरी समस्या तैयार करें और चर की गैर-नकारात्मकता के लिए शर्तें: दोहरी समस्या के उद्देश्य कार्य को बनाते हैं, चर के गुणांक के रूप में मूल समस्या की बाधाओं की प्रणाली के मुक्त सदस्य लेते हैं; दोहरी समस्या के लिए बाधाओं की एक प्रणाली की रचना करें, मैट्रिक्स के तत्वों को चर के गुणांक के रूप में, और चर के गुणांक को मूल समस्या के उद्देश्य समारोह में मुक्त सदस्यों के रूप में लेते हुए, और विपरीत अर्थ की असमानताओं को लिखें; दोहरी समस्या के चरों की गैर-नकारात्मकता की स्थिति लिखिए।

12. प्रथम द्वैत प्रमेय

द्वैत प्रमेयों की सहायता से दोहरी समस्याओं के इष्टतम समाधानों के बीच संबंध स्थापित किया जाता है।

इष्टतमता का पर्याप्त संकेत।

यदि एक एक्स*=(x1*,x2*,…,xn*) तथा वाई*=(y1*,y2*,…,ym*) पारस्परिक रूप से दोहरी समस्याओं के स्वीकार्य समाधान हैं जिनके लिए समानता है,

तब मूल समस्या I का इष्टतम समाधान है, और दोहरी समस्या II का इष्टतम समाधान है।

पारस्परिक रूप से दोहरी समस्याओं की इष्टतमता के लिए पर्याप्त मानदंड के अलावा, उनके समाधानों के बीच अन्य महत्वपूर्ण संबंध भी हैं। सबसे पहले, प्रश्न उठता है: क्या दोहरी समस्याओं के प्रत्येक जोड़े के लिए हमेशा एक साथ इष्टतम समाधान होता है; क्या यह संभव है कि दोहरी समस्याओं में से एक का समाधान हो और दूसरी के पास न हो। इन प्रश्नों का उत्तर निम्नलिखित प्रमेय द्वारा दिया गया है।

पहला (मुख्य) द्वैत प्रमेय। यदि पारस्परिक रूप से दोहरी समस्याओं में से एक का इष्टतम समाधान है, तो दूसरा भी करता है, और उनके रैखिक कार्यों के इष्टतम मूल्य हैं:

Fmax = ज़मिन या एफ(एक्स*)=जेड(वाई*) .

यदि किसी एक समस्या का रैखिक कार्य सीमित नहीं है, तो दूसरी समस्या की स्थितियाँ विरोधाभासी हैं (समस्या का कोई समाधान नहीं है)।

टिप्पणी।मुख्य द्वैत प्रमेय के दूसरे भाग के विपरीत कथन सामान्य स्थिति में सत्य नहीं है, अर्थात। इस तथ्य से कि मूल समस्या की स्थितियां विरोधाभासी हैं, इसका मतलब यह नहीं है कि दोहरी समस्या का रैखिक कार्य सीमित नहीं है।

प्रथम द्वैत प्रमेय का आर्थिक अर्थ।

उत्पादन योजना X*=(x1*,x2*,…,xn*) और संसाधनों का एक सेट (अनुमान) Y*=(y1*,y2*,…,ym*) इष्टतम साबित हो सकता है यदि और केवल अगर उत्पादों से लाभ (राजस्व), "बाहरी" (अग्रिम में ज्ञात) कीमतों पर पाया जाता है c1,c2,…,cn, "आंतरिक" (केवल निर्धारित) पर संसाधनों की लागत के बराबर है समस्या के समाधान से) कीमतें y1, y2,…,ym। अन्य सभी योजनाओं के लिए एक्सतथा यूदोनों कार्यों, उत्पाद से लाभ (राजस्व) हमेशा संसाधनों की लागत से कम (या बराबर) होता है।

पहले द्वैत प्रमेय के आर्थिक अर्थ की व्याख्या इस प्रकार भी की जा सकती है: उद्यम इस बात की परवाह नहीं करता है कि इष्टतम योजना X*=(x1*,x2*,…,xn*) के अनुसार उत्पादों का उत्पादन किया जाए और अधिकतम लाभ प्राप्त किया जाए ( राजस्व) अधिकतम कीमतों पर संसाधनों को अधिकतम या बेचें Y* =(y1*,y2*,…,ym*) और इसके बराबर बिक्री से प्रतिपूर्ति संसाधनों की न्यूनतम लागत Zmin।

13. दूसरा द्वैत प्रमेय

दो परस्पर दोहरी समस्याएँ दें। यदि इनमें से प्रत्येक समस्या को सरल विधि द्वारा हल किया जाता है, तो उन्हें एक विहित रूप में कम करना आवश्यक है, जिसके लिए समस्या I (संक्षेप में) की बाधाओं की प्रणाली में पेश करना आवश्यक है। टीगैर-ऋणात्मक चर, लेकिन समस्या II की बाधाओं की प्रणाली में () – एन गैर-ऋणात्मक चर, जहां i(j) असमानता की संख्या है जिसमें अतिरिक्त चर पेश किया जाता है।

पारस्परिक रूप से दोहरी समस्याओं में से प्रत्येक के लिए बाधाओं की प्रणाली रूप लेगी:

आइए दोहरी समस्याओं में से एक के प्रारंभिक चर और दूसरी समस्या (तालिका) के अतिरिक्त चर के बीच एक पत्राचार स्थापित करें।

प्रमेय। पारस्परिक रूप से दोहरी समस्याओं में से एक के इष्टतम समाधान के सकारात्मक (गैर-शून्य) घटक दूसरी समस्या के इष्टतम समाधान के शून्य घटकों के अनुरूप हैं, अर्थात। किसी के लिए i=1,2,…,m u j=1,2,…,n: यदि X*j>0, तो; यदि , फिर, और इसी तरह,

तो अगर ; तो अगर।

इस प्रमेय से एक महत्वपूर्ण निष्कर्ष निकलता है कि इष्टतम तक पहुँचने पर पारस्परिक रूप से दोहरी समस्याओं के चर के बीच शुरू किया गया पत्राचार (यानी, सिंप्लेक्स विधि द्वारा प्रत्येक समस्या को हल करने के अंतिम चरण में) के बीच एक पत्राचार का प्रतिनिधित्व करता है मुख्य(एक नियम के रूप में, शून्य के बराबर नहीं) दोहरी समस्याओं में से एक के चर और गैर-प्रमुख(शून्य के बराबर) किसी अन्य समस्या के चर जब वे स्वीकार्य बुनियादी समाधान बनाते हैं।

दूसरा द्वैत प्रमेय। दोहरी समस्या के इष्टतम समाधान के घटक मूल समस्या के रैखिक कार्य के संगत चर पर गुणांक के पूर्ण मूल्यों के बराबर होते हैं, जो इसके इष्टतम समाधान के मामूली चर के संदर्भ में व्यक्त किए जाते हैं।

टिप्पणी।यदि पारस्परिक रूप से दोहरी समस्याओं में से एक में इष्टतम समाधान की विशिष्टता का उल्लंघन होता है, तो दोहरी समस्या का इष्टतम समाधान पतित होता है। यह इस तथ्य के कारण है कि यदि मूल समस्या के इष्टतम समाधान की विशिष्टता का उल्लंघन किया जाता है, तो गैर-मूल चर के संदर्भ में इसके इष्टतम समाधान के रैखिक कार्य की अभिव्यक्ति में कम से कम एक मुख्य चर गायब है।

14. वस्तुनिष्ठ रूप से निर्धारित आकलन और उनका अर्थ

दोहरी समस्या के इष्टतम समाधान के घटकों को मूल समस्या का इष्टतम (दोहरा) अनुमान कहा जाता है। शिक्षाविद एल.वी. कांटोरोविच ने उन्हें बुलाया वस्तुनिष्ठ रूप से वातानुकूलितअनुमान (साहित्य में उन्हें छिपी हुई आय भी कहा जाता है) .

मूल समस्या I के अतिरिक्त चर, संसाधनों के स्टॉक द्वि के बीच अंतर का प्रतिनिधित्व करते हैं S1,S2,S3,S4 और उनकी खपत, एक्सप्रेस बचे हुए संसाधन , और दोहरी समस्या II के अतिरिक्त चर, उनसे उत्पादन की एक इकाई के उत्पादन के लिए संसाधनों की लागत और उत्पादों की कीमतों के बीच अंतर का प्रतिनिधित्व करते हैं P1,P2 , अभिव्यक्त करना कीमत से अधिक लागत।

इस प्रकार, संसाधनों के निष्पक्ष रूप से निर्धारित अनुमान संसाधनों की कमी की डिग्री निर्धारित करते हैं: इष्टतम उत्पादन योजना के अनुसार, दुर्लभ (यानी, पूरी तरह से उपयोग किए गए) संसाधन गैर-शून्य अनुमान प्राप्त करते हैं, और गैर-दुर्लभ - शून्य अनुमान। मान y*i i-वें संसाधन का अनुमान है। अनुमान y*i का मान जितना अधिक होगा, संसाधन की कमी उतनी ही अधिक होगी। गैर-दुर्लभ संसाधन के लिए y*i=0.

इसलिए, केवल लागत प्रभावी, लाभहीन प्रकार के उत्पाद इष्टतम उत्पादन योजना में आ सकते हैं (हालांकि यहां लाभप्रदता की कसौटी अजीब है: किसी उत्पाद की कीमत उसके निर्माण में उपभोग किए गए संसाधनों की लागत से अधिक नहीं है, लेकिन बिल्कुल बराबर है उनको)।

तीसरा द्वैत प्रमेय . दोहरी समस्या के इष्टतम समाधान के घटक रैखिक फ़ंक्शन के आंशिक व्युत्पन्न के मूल्यों के बराबर हैं Fmax(बी1, बी2,…, बी.एम.)संबंधित तर्कों के अनुसार, अर्थात्।

संसाधनों के वस्तुनिष्ठ रूप से निर्धारित अनुमानों से पता चलता है कि उत्पादों की बिक्री से अधिकतम लाभ (राजस्व) कितनी मौद्रिक इकाइयाँ हैं, जब संबंधित संसाधन का स्टॉक एक इकाई द्वारा बदलता है।

दोहरे अनुमान लगातार बदलते उद्योग में विश्लेषण और सही निर्णय लेने के लिए एक उपकरण के रूप में काम कर सकते हैं। इसलिए, उदाहरण के लिए, संसाधनों के उद्देश्यपूर्ण रूप से निर्धारित अनुमानों की मदद से, इष्टतम सशर्त लागत और उत्पादन परिणामों की तुलना करना संभव है।

संसाधनों के वस्तुनिष्ठ रूप से निर्धारित अनुमान किसी के प्रभाव का न्याय करना संभव नहीं बनाते हैं, लेकिन संसाधनों में केवल अपेक्षाकृत छोटे परिवर्तन होते हैं। अचानक परिवर्तन के साथ, अनुमान स्वयं भिन्न हो सकते हैं, जिससे उत्पादन दक्षता के विश्लेषण के लिए उनका उपयोग करना असंभव हो जाएगा। वस्तुनिष्ठ रूप से निर्धारित अनुमानों के अनुपात के अनुसार, संसाधन प्रतिस्थापन के परिकलित मानदंड निर्धारित किए जा सकते हैं, जिसके तहत दोहरे अनुमानों की स्थिरता के भीतर चल रहे प्रतिस्थापन इष्टतम योजना की दक्षता को प्रभावित नहीं करते हैं। निष्कर्ष।दोहरे अंक हैं:

1. संसाधनों और उत्पादों की कमी का सूचक।

2. उद्देश्य समारोह के मूल्य पर प्रतिबंधों के प्रभाव का एक संकेतक।

3. इष्टतमता मानदंड के दृष्टिकोण से कुछ प्रकार के उत्पादों के उत्पादन की दक्षता का एक संकेतक।

4. कुल आकस्मिक लागतों और परिणामों की तुलना करने के लिए एक उपकरण।

15. लागत की कसौटी के अनुसार परिवहन कार्य का विवरण।

टीके - उत्पादन के एक बिंदु (प्रस्थान स्टेशनों) से उपभोग बिंदुओं (गंतव्य स्टेशनों) तक एक सजातीय या विनिमेय उत्पाद के परिवहन के लिए सबसे किफायती योजना का कार्य - एलपी का सबसे महत्वपूर्ण निजी कार्य है, जिसमें व्यापक व्यावहारिक अनुप्रयोग नहीं हैं केवल परिवहन समस्याओं के लिए।

टीके को एलपी में आर्थिक विशेषताओं की निश्चितता, गणितीय मॉडल की विशेषताओं, समाधान के विशिष्ट तरीकों की उपस्थिति से अलग किया जाता है।

लागत के संदर्भ में टीओआर का सरलतम सूत्रीकरण इस प्रकार है: टीप्रस्थान के बिंदु A1,…, Am क्रमशः a1,…, am सजातीय कार्गो (संसाधन) की इकाइयाँ हैं जिन्हें वितरित किया जाना है एनउपभोक्ता B1,…,Bn मात्रा b1,…,bn इकाइयों (आवश्यकताओं) में। परिवहन लागत Cij को प्रस्थान के i-th बिंदु से j-th बिंदु तक खपत के एक इकाई के परिवहन के लिए जाना जाता है।

एक परिवहन योजना तैयार करना आवश्यक है, अर्थात, यह पता लगाने के लिए कि कितने यूनिट कार्गो को प्रस्थान के i-वें बिंदु से उपभोग के j-th बिंदु तक इस तरह भेजा जाना चाहिए कि जरूरतें पूरी तरह से संतुष्ट हों और वह कुल परिवहन लागत न्यूनतम है।

स्पष्टता के लिए, टीके की शर्तों को एक तालिका के रूप में प्रस्तुत किया जाएगा, जिसे कहा जाता है वितरण .

प्रदाता	उपभोक्ता			कार्गो स्टॉक
जरुरत

यहां, i-वें मूल बिंदु से j-वें गंतव्य तक ले जाने वाले कार्गो की मात्रा xij के बराबर है, प्रस्थान के i-वें बिंदु पर कार्गो का स्टॉक मूल्य ai>=0 द्वारा निर्धारित किया जाता है, और कार्गो में j-वें गंतव्य की मांग bj>=0 है। यह माना जाता है कि सभी xij>=0.

मैट्रिक्स कहा जाता है टैरिफ मैट्रिक्स (लागत या परिवहन लागत)।

परिवहन कार्य योजना मैट्रिक्स कहा जाता है, जहां प्रत्येक संख्या xij कार्गो इकाइयों की संख्या को दर्शाती है जिन्हें प्रस्थान के i-वें बिंदु से j-वें गंतव्य तक पहुंचाया जाना चाहिए। मैट्रिक्स xij कहा जाता है यातायात मैट्रिक्स।

परिवहन योजना के कार्यान्वयन से जुड़ी कुल कुल लागत को उद्देश्य कार्य द्वारा दर्शाया जा सकता है

चर xij को स्टॉक, उपभोक्ताओं पर प्रतिबंधों और गैर-नकारात्मकता की शर्तों को पूरा करना चाहिए:

- स्टॉक पर प्रतिबंध (2);

- उपभोक्ताओं पर प्रतिबंध (2);

गैर-नकारात्मकता स्थितियां हैं (3)।

इस प्रकार, गणितीय रूप से परिवहन समस्या निम्नानुसार तैयार की जाती है। बाधाओं की प्रणाली (2) शर्त के तहत (3) और उद्देश्य समारोह (1) दिए गए हैं। सिस्टम (2) के समाधान के सेट के बीच, ऐसा गैर-नकारात्मक समाधान ढूंढना आवश्यक है जो फ़ंक्शन (1) को कम करता है।

समस्या के लिए बाधाओं की प्रणाली (1) - (3) में m + n समीकरण शामिल हैं टीएनचर। यह माना जाता है कि कुल भंडार कुल जरूरतों के बराबर है, अर्थात।

16. परिवहन समस्या की सॉल्वेबिलिटी का संकेत

परिवहन समस्या के लिए स्वीकार्य योजनाएँ होने के लिए, यह आवश्यक और पर्याप्त है कि समानता

परिवहन कार्य दो प्रकार के होते हैं: बंद किया हुआ , जिसमें आपूर्तिकर्ताओं के कार्गो की कुल मात्रा उपभोक्ताओं की कुल मांग के बराबर है, और खोलना , जिसमें आपूर्तिकर्ताओं की कुल उत्पादन क्षमता उपभोक्ताओं की मांग से अधिक है या उपभोक्ताओं की मांग आपूर्तिकर्ताओं की वास्तविक कुल क्षमता से अधिक है, अर्थात।

एक खुले मॉडल को बंद मॉडल में बदला जा सकता है। इसलिए, यदि, तो एक काल्पनिक (n + 1)-वें गंतव्य को परिवहन समस्या के गणितीय मॉडल में पेश किया जाता है। ऐसा करने के लिए, कार्य मैट्रिक्स में एक अतिरिक्त कॉलम प्रदान किया जाता है, जिसके लिए आवश्यकता आपूर्तिकर्ताओं की कुल क्षमता और उपभोक्ताओं की वास्तविक मांग के बीच के अंतर के बराबर होती है:

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

यदि, तो एक काल्पनिक (एम + 1) - प्रस्थान का बिंदु पेश किया जाता है, जिसके बराबर कार्गो स्टॉक को जिम्मेदार ठहराया जाता है।

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

परिवहन समस्या के लिए निम्नलिखित प्रमेय का बहुत महत्व है।

प्रमेय। परिवहन समस्या के मैट्रिक्स का रैंक समीकरणों की संख्या से एक कम है, अर्थात। आर ( एक )= एम + एन -1.

यह प्रमेय से इस प्रकार है कि प्रत्येक संदर्भ डिजाइन में शून्य के बराबर (एम -1) (एन -1) मुक्त चर होना चाहिए और एम + एन -1 मूल चर होना चाहिए।

हम सीधे वितरण तालिका में परिवहन कार्य की परिवहन योजना की तलाश करेंगे। हम मानते हैं कि यदि चर xij एक मान लेता है, तो हम इस मान को संबंधित सेल (I,j) में लिखेंगे, लेकिन यदि xij = 0 है, तो हम सेल (I, j) को खाली छोड़ देंगे। वितरण तालिका में मैट्रिक्स के रैंक पर प्रमेय को ध्यान में रखते हुए मास्टर प्लान में शामिल होना चाहिएएम+एन-1 कब्जे वाली कोशिकाएंऔर बाकी मुफ्त होंगे।

आधार योजना के लिए ये आवश्यकताएं केवल एक ही नहीं हैं। आधार योजनाओं को साइकिल से संबंधित एक और आवश्यकता को पूरा करना चाहिए।

ट्रैफ़िक मैट्रिक्स सेल का एक सेट जिसमें दो और केवल दो पड़ोसी सेल एक पंक्ति या एक कॉलम में स्थित होते हैं और सेट का अंतिम सेल उसी पंक्ति या कॉलम में होता है, जिसमें पहली सेल बंद होती है चक्र .

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

परिवहन कार्य योजनाओं के निम्नलिखित महत्वपूर्ण गुण चक्र कोशिकाओं के सेट से जुड़े हैं:

1) परिवहन कार्य की एक स्वीकार्य योजना एक संदर्भ है यदि और केवल अगर इस योजना के कब्जे वाले कक्षों से कोई चक्र नहीं बनाया जा सकता है;

2) यदि हमारे पास एक बुनियादी योजना है, तो प्रत्येक मुक्त सेल के लिए केवल एक चक्र बनाना संभव है जिसमें यह सेल और कब्जे वाली कोशिकाओं का कुछ हिस्सा हो।

17. प्रारंभिक आधार रेखा का निर्माण

उत्तर-पश्चिम कोने का नियम।

प्रारंभिक परिवहन योजना तैयार करने के लिए, उत्तर-पश्चिम कोने के नियम का उपयोग करना सुविधाजनक है, जो इस प्रकार है।

हम ऊपरी बाएँ से शुरू करते हुए, सशर्त रूप से "उत्तर-पश्चिम कोना" कहलाते हैं, जो लाइन के साथ दाईं ओर या कॉलम के नीचे आगे बढ़ते हैं। हम सेल (1; 1) में संख्या a1 और b1 में से छोटी संख्या डालते हैं, अर्थात . यदि, तो पहला कॉलम "बंद" है, यानी, पहले उपभोक्ता की मांग पूरी तरह से संतुष्ट है। इसका मतलब है कि पहले कॉलम के अन्य सभी सेल के लिए, कार्गो की मात्रा .

यदि, तो पहली पंक्ति समान रूप से "बंद" है, अर्थात, के लिए . हम आसन्न सेल (2; 1) में भरने के लिए आगे बढ़ते हैं, जिसमें हम प्रवेश करते हैं।

दूसरी सेल (1; 2) या (2; 1) भरने के बाद, हम दूसरी पंक्ति में या दूसरे कॉलम में अगले तीसरे सेल को भरने के लिए आगे बढ़ते हैं। हम इस प्रक्रिया को तब तक जारी रखेंगे जब तक कि किसी स्तर पर संसाधन और जरूरतें समाप्त नहीं हो जातीं। अंतिम भरी हुई सेल अंतिम n-वें कॉलम में और अंतिम m-वें पंक्ति में होगी।

"न्यूनतम तत्व" नियम।

"उत्तर-पश्चिम कोने" नियम के अनुसार निर्मित प्रारंभिक संदर्भ योजना, आमतौर पर इष्टतम से बहुत दूर हो जाती है, क्योंकि इसे निर्धारित करते समय लागतों को ध्यान में नहीं रखा जाता है। इसलिए, आगे की गणना में, इष्टतम योजना को प्राप्त करने के लिए कई पुनरावृत्तियों की आवश्यकता होगी। यदि प्रारंभिक योजना "न्यूनतम तत्व" नियम के अनुसार बनाई गई है, तो पुनरावृत्तियों की संख्या कम की जा सकती है। इसका सार इस तथ्य में निहित है कि प्रत्येक चरण में सेल में कार्गो का अधिकतम संभव "आंदोलन" न्यूनतम टैरिफ के साथ किया जाता है। हम सेल से तालिका भरना शुरू करते हैं, जो टैरिफ मैट्रिक्स के सबसे छोटे तत्व cj से मेल खाती है। सबसे छोटी संख्या ai या bj को सबसे कम टैरिफ वाले सेल में रखा गया है . फिर, आपूर्तिकर्ता से संबंधित पंक्ति, जिसका स्टॉक पूरी तरह से समाप्त हो गया है, या उपभोक्ता से संबंधित कॉलम, जिसकी मांग पूरी तरह से संतुष्ट है, को विचार से बाहर रखा गया है। यह पता चल सकता है कि एक पंक्ति और एक कॉलम को एक ही समय में बाहर रखा जाना चाहिए यदि आपूर्तिकर्ता की सूची पूरी तरह से समाप्त हो गई है और उपभोक्ता की मांग पूरी तरह से संतुष्ट है। फिर, तालिका की शेष कोशिकाओं से, सबसे कम टैरिफ वाले सेल को फिर से चुना जाता है और स्टॉक वितरित करने की प्रक्रिया तब तक जारी रहती है जब तक कि सभी वितरित नहीं हो जाते और मांग पूरी नहीं हो जाती।

18. क्षमता का तरीका

संभावित विधि द्वारा परिवहन समस्या की इष्टतम योजना निर्धारित करने का सामान्य सिद्धांत सरल विधि द्वारा एलपी समस्या को हल करने के सिद्धांत के समान है, अर्थात्: पहले, परिवहन समस्या की मूल योजना पाई जाती है, और फिर यह क्रमिक रूप से होती है इष्टतम योजना प्राप्त करने के लिए सुधार किया गया।

संभावित विधि का सार इस प्रकार है। प्रारंभिक संदर्भ परिवहन योजना मिलने के बाद, प्रत्येक आपूर्तिकर्ता (प्रत्येक पंक्ति) को एक निश्चित संख्या सौंपी जाती है जिसे आपूर्तिकर्ता की संभावित एआई कहा जाता है, और प्रत्येक उपभोक्ता (प्रत्येक कॉलम) को एक निश्चित संख्या सौंपी जाती है जिसे उपभोक्ता की क्षमता कहा जाता है।

एक बिंदु पर एक टन कार्गो की लागत परिवहन से पहले एक टन कार्गो की लागत + इसके परिवहन की लागत के बराबर होती है: .

संभावित विधि द्वारा परिवहन समस्या को हल करने के लिए, यह आवश्यक है:

1. उल्लिखित नियमों में से एक के अनुसार एक बुनियादी परिवहन योजना बनाएं। भरे हुए कक्षों की संख्या m+n-1 होनी चाहिए।

2. संभावित और, क्रमशः, आपूर्तिकर्ताओं और उपभोक्ताओं की गणना करें (व्यस्त कोशिकाओं के लिए): . भरे हुए कक्षों की संख्या m+n-1 है, और समीकरणों की संख्या m+n है। इसलिये समीकरणों की संख्या अज्ञात की संख्या से एक कम है, तो अज्ञात में से एक मुक्त है और कोई भी संख्यात्मक मान ले सकता है। उदाहरण के लिए, । किसी दिए गए संदर्भ समाधान के लिए शेष संभावनाएं विशिष्ट रूप से निर्धारित की जाती हैं।

3. इष्टतमता के लिए जाँच करें, अर्थात्। मुक्त कोशिकाओं के लिए स्कोर की गणना करें। यदि, तो परिवहन समीचीन है और योजना X इष्टतम है - इष्टतमता का संकेत। यदि कम से कम एक अंतर है, तो एक नई संदर्भ योजना पर जाएं। अपने आर्थिक अर्थ में, मूल्य कुल परिवहन लागत में परिवर्तन को दर्शाता है जो कि i-वें आपूर्तिकर्ता द्वारा j-वें उपभोक्ता को एकल आपूर्ति के कार्यान्वयन के कारण होगा। यदि, तो एकल वितरण से परिवहन लागत में बचत होगी, यदि - उनमें वृद्धि के लिए। इसलिए, यदि आपूर्ति की मुक्त दिशाओं में कोई दिशा नहीं है जो परिवहन लागत को बचाती है, तो परिणामी योजना इष्टतम है।

4. सकारात्मक संख्याओं के बीच, एक मुक्त सेल के लिए बनाया गया अधिकतम चुना जाता है, जिससे यह पुनर्गणना चक्र से मेल खाता है। चयनित फ्री सेल के लिए साइकिल तैयार होने के बाद, आपको एक नई संदर्भ योजना पर आगे बढ़ना चाहिए। ऐसा करने के लिए, आपको पुनर्गणना चक्र द्वारा इस मुक्त सेल से जुड़ी कोशिकाओं के भीतर भार को स्थानांतरित करने की आवश्यकता है।

a) किसी दिए गए फ्री सेल के साथ एक चक्र से जुड़े प्रत्येक सेल को एक निश्चित चिन्ह सौंपा गया है, और यह फ्री सेल "+" है, और अन्य सभी सेल (चक्र के कोने) वैकल्पिक रूप से "-" और "+" संकेत हैं। . हम इन सेल को माइनस और प्लस कहेंगे।

बी) चक्र की ऋण कोशिकाओं में, हम न्यूनतम आपूर्ति पाते हैं, जिसे हम निरूपित करते हैं। ऋणात्मक कोशिकाओं में xij की छोटी संख्या इस मुक्त कोशिका में स्थानांतरित हो जाती है। उसी समय, इस संख्या को "+" चिह्न वाले कक्षों में संबंधित संख्याओं में जोड़ा जाता है और ऋणात्मक कक्षों में संख्याओं से घटाया जाता है। एक सेल जो पहले मुक्त था, व्यस्त हो जाता है और संदर्भ योजना में प्रवेश करता है; और माइनस सेल, जिसमें न्यूनतम संख्या xij थी, को मुक्त माना जाता है और संदर्भ योजना छोड़ देता है।

इस प्रकार, एक नई आधार रेखा निर्धारित की गई थी। ऊपर वर्णित एक आधार रेखा से दूसरे में संक्रमण को पुनर्गणना चक्र में बदलाव कहा जाता है। पुनर्गणना चक्र के साथ स्थानांतरित होने पर, कब्जे वाली कोशिकाओं की संख्या अपरिवर्तित रहती है, अर्थात्, यह एम + एन -1 के बराबर रहती है। इसके अलावा, यदि ऋणात्मक कोशिकाओं में दो या दो से अधिक समान संख्याएँ xij हैं, तो इनमें से केवल एक कोशिका खाली हो जाती है, और शेष को शून्य आपूर्ति के साथ छोड़ दिया जाता है।

5. परिणामी संदर्भ योजना की इष्टतमता के लिए जाँच की जाती है, अर्थात। पैराग्राफ 2 से सभी चरणों को दोहराएं।

19. गतिशील प्रोग्रामिंग की अवधारणा।

डीपी (योजना) बहु-चरण (बहु-चरण) समस्याओं के इष्टतम समाधान खोजने के लिए एक गणितीय विधि है। इनमें से कुछ समस्याएं स्वाभाविक रूप से अलग-अलग चरणों (चरणों) में टूट जाती हैं, लेकिन ऐसी समस्याएं हैं जिनमें डीपी पद्धति द्वारा हल करने के लिए विभाजन को कृत्रिम रूप से पेश करना पड़ता है।

आमतौर पर, डीपी विधियां कुछ नियंत्रित प्रणालियों के संचालन का अनुकूलन करती हैं, जिसके प्रभाव का अनुमान लगाया जाता है additive, या गुणक, वस्तुनिष्ठ कार्य। additiveकई चरों का एक फलन है f(x1,x2,…,xn) जिसका मान कुछ ऐसे फलनों के योग के रूप में परिकलित किया जाता है जो केवल एक चर xj: पर निर्भर करते हैं। एडिटिव ऑब्जेक्टिव फंक्शन की शर्तें नियंत्रित प्रक्रिया के अलग-अलग चरणों में लिए गए निर्णयों के प्रभाव के अनुरूप होती हैं।

आर बेलमैन का इष्टतमता का सिद्धांत।

गतिशील प्रोग्रामिंग में लागू दृष्टिकोण का अर्थ मूल बहुआयामी समस्या के समाधान को निम्न आयाम की समस्याओं के अनुक्रम के साथ बदलने में निहित है। कार्यों के लिए बुनियादी आवश्यकताएं:

1. शोध का उद्देश्य होना चाहिए नियंत्रित प्रणाली (वस्तु) दिए गए मान्य के साथ राज्यों और स्वीकार्य विभागों;

2. कार्य को एक बहु-चरणीय प्रक्रिया के रूप में व्याख्या की अनुमति देनी चाहिए, जिसके प्रत्येक चरण में स्वीकृति शामिल है समाधानके बारे मेंस्वीकार्य नियंत्रणों में से एक को चुनना जिसके कारण राज्य परिवर्तन सिस्टम;

3. कार्य चरणों की संख्या पर निर्भर नहीं होना चाहिए और उनमें से प्रत्येक पर परिभाषित होना चाहिए;

4. प्रत्येक चरण में सिस्टम की स्थिति को उसी (रचनात्मक रूप से) मापदंडों के सेट द्वारा वर्णित किया जाना चाहिए;

5. बाद की स्थिति जिसमें सिस्टम समाधान चुनने के बाद खुद को पाता है k- वांचरण, केवल दिए गए समाधान और आरंभिक अवस्था पर निर्भर करता है क- कदम। गतिशील प्रोग्रामिंग की विचारधारा के दृष्टिकोण से यह संपत्ति मुख्य है और इसे कहा जाता है परिणामों की कमी .

एक सामान्यीकृत रूप में गतिशील प्रोग्रामिंग मॉडल के अनुप्रयोग पर विचार करें। कुछ अमूर्त वस्तु के प्रबंधन का कार्य होने दें जो विभिन्न राज्यों में हो सकता है। वस्तु की वर्तमान स्थिति को कुछ निश्चित मापदंडों के साथ पहचाना जाएगा, जिसे निम्नलिखित में एस द्वारा दर्शाया जाएगा और कहा जाएगा राज्य वेक्टर. यह माना जाता है कि सभी संभावित राज्यों का समुच्चय S दिया गया है। सेट को ऑब्जेक्ट के लिए भी परिभाषित किया गया है स्वीकार्य नियंत्रण(नियंत्रण क्रियाएं) एक्स,जो, व्यापकता के नुकसान के बिना, एक संख्यात्मक सेट माना जा सकता है। समय पर असतत बिंदुओं पर नियंत्रण क्रियाएं की जा सकती हैं, और नियंत्रण समाधाननियंत्रणों में से एक को चुनने में शामिल है। योजनाकार्य या प्रबंधन रणनीतिवेक्टर x=(x1,x2,…,xn-1) कहा जाता है, जिसके घटक प्रक्रिया के प्रत्येक चरण में चयनित नियंत्रण होते हैं। अपेक्षित को देखते हुए परिणाम की कमीऑब्जेक्ट Sk और Sk+1 की प्रत्येक दो क्रमिक अवस्थाओं के बीच, एक ज्ञात कार्यात्मक निर्भरता है, जिसमें चयनित नियंत्रण भी शामिल है: . इस प्रकार, वस्तु की प्रारंभिक स्थिति निर्धारित करना और एक योजना चुनना एक्सविशिष्ट रूप से परिभाषित व्यवहार का प्रक्षेपवक्रवस्तु।

हर कदम पर प्रबंधन दक्षता कवर्तमान स्थिति Sk पर निर्भर करता है, चयनित नियंत्रण xk और फ़ंक्शन fk(xk,Sk) का उपयोग करके परिमाणित किया जाता है, जो सारांश हैं योगात्मक उद्देश्य समारोह , सुविधा प्रबंधन की समग्र दक्षता की विशेषता। (टिप्पणी , कि फ़ंक्शन fk(xk,Sk) की परिभाषा में स्वीकार्य मानों की श्रेणी शामिल है एक्सके , और यह क्षेत्र, एक नियम के रूप में, Sk की वर्तमान स्थिति पर निर्भर करता है)। इष्टतम नियंत्रण , किसी दिए गए प्रारंभिक राज्य S1 के लिए, ऐसी इष्टतम योजना x* को चुनने के लिए कम कर देता है , जिस पर अधिकतम राशि इसी प्रक्षेपवक्र पर fk का मान।

गतिशील प्रोग्रामिंग का मुख्य सिद्धांत यह है कि प्रत्येक चरण में फ़ंक्शन fk (xk, Sk) के एक पृथक अनुकूलन के लिए प्रयास नहीं करना चाहिए, लेकिन इस धारणा के तहत इष्टतम नियंत्रण x*k चुनें कि बाद के सभी चरण इष्टतम हैं। औपचारिक रूप से, इस सिद्धांत को प्रत्येक चरण में खोजने के द्वारा महसूस किया जाता है क सशर्त इष्टतम नियंत्रण , इस चरण से शुरू होने वाली उच्चतम कुल दक्षता प्रदान करते हुए, यह मानते हुए कि वर्तमान स्थिति एस है।

कार्यों के योग का अधिकतम मान Zk(s) द्वारा निरूपित करें fk से पूरे चरणों में कइससे पहले पी(प्रक्रिया के किसी दिए गए खंड पर इष्टतम नियंत्रण के तहत प्राप्त), बशर्ते कि चरण की शुरुआत में वस्तु कराज्य एस में है। तब कार्य Zk(s) को पुनरावर्ती संबंध को संतुष्ट करना चाहिए:

इस अनुपात को कहा जाता है मूल पुनरावृत्ति संबंध (मूल कार्यात्मक समीकरण)गतिशील प्रोग्रामिंग। यह गतिशील प्रोग्रामिंग के मूल सिद्धांत को लागू करता है, जिसे के रूप में भी जाना जाता है बेलमैन का इष्टतमता का सिद्धांत :

इष्टतम नियंत्रण रणनीति को निम्नलिखित शर्तों को पूरा करना चाहिए: प्रारंभिक अवस्था जो भी हो एसके kth स्टेप पर और इस स्टेप पर चुने गए कंट्रोल एक्सके, बाद के नियंत्रण (प्रबंधन निर्णय) के संबंध में इष्टतम होना चाहिए कोकमो यान्यू ,कदम k . पर किए गए निर्णय के परिणामस्वरूप .

मुख्य संबंध हमें Zk(s) कार्यों को खोजने की अनुमति देता है केवल मेंके साथ संयुक्त आरंभिक दशाजो हमारे मामले में समानता है।

ऊपर तैयार किया गया इष्टतमता का सिद्धांत केवल उन वस्तुओं को नियंत्रित करने के लिए लागू होता है जिनके लिए इष्टतम नियंत्रण का चुनाव नियंत्रित प्रक्रिया के प्रागितिहास पर निर्भर नहीं करता है, अर्थात सिस्टम वर्तमान स्थिति में कैसे आया। यह वह परिस्थिति है जो समस्या को विघटित करना और उसका व्यावहारिक समाधान संभव बनाना संभव बनाती है।

प्रत्येक विशिष्ट कार्य के लिए, कार्यात्मक समीकरण का अपना विशिष्ट रूप होता है, लेकिन यह निश्चित रूप से अभिव्यक्ति (*) में निहित आवर्तक प्रकृति को बनाए रखना चाहिए और इष्टतमता सिद्धांत के मुख्य विचार को मूर्त रूप देना चाहिए।

20. खेल मॉडल की अवधारणा।

संघर्ष की स्थिति के गणितीय मॉडल को कहा जाता है खेल , संघर्ष में शामिल पक्ष खिलाड़ियों और संघर्ष का परिणाम जीत.

प्रत्येक औपचारिक खेल के लिए, हम परिचय देते हैं नियमों , वे। शर्तों की एक प्रणाली जो निर्धारित करती है: 1) खिलाड़ियों के कार्यों के लिए विकल्प; 2) प्रत्येक खिलाड़ी के पास भागीदारों के व्यवहार के बारे में कितनी जानकारी है; 3) वह अदायगी जिस पर कार्रवाई का प्रत्येक सेट होता है। आमतौर पर, लाभ (या हानि) की मात्रा निर्धारित की जा सकती है; उदाहरण के लिए, आप शून्य से हार का मूल्यांकन कर सकते हैं, एक जीत से और 1/2 से ड्रा कर सकते हैं। खेल के परिणामों को परिमाणित करना कहलाता है भुगतान .

खेल कहा जाता है भाप से भरा कमरा , अगर इसमें दो खिलाड़ी शामिल हैं, और विभिन्न , यदि खिलाड़ियों की संख्या दो से अधिक है। हम केवल युग्मित खेलों पर विचार करेंगे। वे दो खिलाड़ियों द्वारा खेले जाते हैं लेकिनतथा पर,जिनके हित विपरीत हैं, और खेल से हमारा मतलब है कि की ओर से कार्यों की एक श्रृंखला लेकिनतथा पर।

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

नियमों द्वारा प्रदान की गई क्रियाओं में से किसी एक का चुनाव और कार्यान्वयन कहलाता है कदम खिलाड़ी। चालें हो सकती हैं व्यक्तिगत तथा यादृच्छिक रूप से . व्यक्तिगत चाल – यह संभावित कार्यों में से एक के खिलाड़ी द्वारा एक सचेत विकल्प है (उदाहरण के लिए, शतरंज के खेल में एक चाल)। प्रत्येक व्यक्तिगत चाल के लिए संभावित विकल्पों का सेट खेल के नियमों द्वारा नियंत्रित होता है और दोनों पक्षों पर पिछली चालों की समग्रता पर निर्भर करता है।

यादृच्छिक चाल – यह एक बेतरतीब ढंग से चुनी गई क्रिया है (उदाहरण के लिए, फेरबदल किए गए डेक से कार्ड चुनना)। खेल को गणितीय रूप से परिभाषित करने के लिए, खेल के नियमों को प्रत्येक यादृच्छिक चाल के लिए निर्दिष्ट करना होगा प्रायिकता वितरण संभावित नतीजे।

कुछ खेलों में केवल यादृच्छिक चालें (तथाकथित विशुद्ध रूप से संयोग का खेल) या केवल व्यक्तिगत चालें (शतरंज, चेकर्स) शामिल हो सकती हैं। अधिकांश ताश के खेल मिश्रित प्रकार के खेलों से संबंधित होते हैं, अर्थात उनमें यादृच्छिक और व्यक्तिगत दोनों चालें होती हैं। आगे हम केवल खिलाड़ियों की व्यक्तिगत चालों पर विचार करेंगे।

खेलों को न केवल चाल की प्रकृति (व्यक्तिगत, यादृच्छिक) द्वारा वर्गीकृत किया जाता है, बल्कि प्रकृति और प्रत्येक खिलाड़ी को दूसरे के कार्यों के बारे में जानकारी की मात्रा के अनुसार भी वर्गीकृत किया जाता है। खेलों का एक विशेष वर्ग तथाकथित "पूरी जानकारी वाले खेल" हैं। पूरी जानकारी वाला गेम एक खेल कहा जाता है जिसमें प्रत्येक खिलाड़ी प्रत्येक व्यक्तिगत चाल पर व्यक्तिगत और यादृच्छिक दोनों, पिछली सभी चालों के परिणामों को जानता है। पूरी जानकारी वाले खेलों के उदाहरण हैं शतरंज, चेकर्स और टिक-टैक-टो का प्रसिद्ध खेल। व्यावहारिक महत्व के अधिकांश खेल पूरी जानकारी वाले खेलों के वर्ग से संबंधित नहीं हैं, क्योंकि प्रतिद्वंद्वी के कार्यों के बारे में अज्ञात आमतौर पर संघर्ष स्थितियों का एक अनिवार्य तत्व है।

गेम थ्योरी की मूल अवधारणाओं में से एक अवधारणा है रणनीतियाँ .

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

प्रति तय करना खेल , या ढूँढो खेल निर्णय , प्रत्येक खिलाड़ी के लिए ऐसी रणनीति चुनना आवश्यक है जो शर्त को पूरा करे इष्टतमता , वे। खिलाड़ियों में से एक को प्राप्त करना चाहिए अधिकतम जीत, जब दूसरा अपनी रणनीति पर अडिग रहता है, उसी समय दूसरे खिलाड़ी के पास होना चाहिए न्यूनतम नुकसान , अगर पहला अपनी रणनीति का पालन करता है। ऐसी रणनीतियों को कहा जाता है इष्टतम . इष्टतम रणनीतियों को भी शर्त को पूरा करना चाहिए वहनीयता , वे। किसी भी खिलाड़ी के लिए इस खेल में अपनी रणनीति को छोड़ना लाभहीन होना चाहिए।

यदि खेल को पर्याप्त बार दोहराया जाता है, तो खिलाड़ियों को प्रत्येक विशेष खेल में जीतने और हारने में रुचि नहीं हो सकती है, एक औसत जीत (हार) सभी पार्टियों में।

गेम थ्योरी का लक्ष्य प्रत्येक खिलाड़ी के लिए इष्टतम रणनीति निर्धारित करना है।

21. भुगतान मैट्रिक्स। खेल की निचली और ऊपरी कीमत

खेल समाप्त करें जिसमें खिलाड़ी लेकिनयह है टीरणनीति, और खिलाड़ी बी - पीरणनीतियों को एम × एन गेम कहा जाता है।

दो खिलाड़ियों के m×n खेल पर विचार करें लेकिनतथा पर("हम" और "प्रतिद्वंद्वी")।

खिलाड़ी को चलो लेकिनहै टीव्यक्तिगत रणनीतियाँ, जिन्हें हम A1,A2,…, Am द्वारा निरूपित करते हैं। खिलाड़ी को चलो परउपलब्ध एनव्यक्तिगत रणनीतियाँ, हम उन्हें B1,B2,…,Bn निरूपित करते हैं।

प्रत्येक पक्ष को एक विशेष रणनीति चुनने दें; हमारे लिए यह ऐ होगा, प्रतिद्वंद्वी बीजे के लिए। एआई और बीजे () रणनीतियों की किसी भी जोड़ी के खिलाड़ियों द्वारा पसंद के परिणामस्वरूप, खेल का परिणाम विशिष्ट रूप से निर्धारित होता है, अर्थात। जीतो ऐज खिलाड़ी लेकिन(सकारात्मक या नकारात्मक) और खिलाड़ी की हानि (-aij) पर।

मान लें कि मान aij किसी भी रणनीति की जोड़ी के लिए जाना जाता है (ऐ, बीजे) . मैट्रिक्स पी = aij , जिनके तत्व ऐ और बीजे की रणनीतियों के अनुरूप अदायगी हैं, बुलाया भुगतान मैट्रिक्स या खेल मैट्रिक्स। इस मैट्रिक्स की पंक्तियाँ खिलाड़ी की रणनीतियों के अनुरूप होती हैं लेकिन,और कॉलम खिलाड़ी की रणनीतियाँ हैं बी. इन रणनीतियों को शुद्ध कहा जाता है।

एम × एन गेम मैट्रिक्स का रूप है:

मैट्रिक्स के साथ एक m×n गेम पर विचार करें और A1,A2,…,Am . रणनीतियों में से सर्वश्रेष्ठ का निर्धारण करें . एक रणनीति चुनना एआई खिलाड़ी लेकिनखिलाड़ी से उम्मीद करनी चाहिए परइसका जवाब उन रणनीतियों में से एक के साथ देगा, जिसके लिए खिलाड़ी को भुगतान किया जाता है लेकिनन्यूनतम (खिलाड़ी परखिलाड़ी को "नुकसान" पहुंचाना चाहता है ए).

खिलाड़ी के कम से कम भुगतान द्वारा निरूपित करें लेकिनजब वह खिलाड़ी की सभी संभावित रणनीतियों के लिए रणनीति एआई चुनता है पर(सबसे छोटी संख्या in मैंपेऑफ मैट्रिक्स की -th लाइन), यानी।

सभी संख्याओं में से () सबसे बड़ा चुनें: .

चलो कॉल करो खेल की कम कीमत, या अधिकतम जीत (अधिकतम)। यह खिलाड़ी बी की किसी भी रणनीति के लिए खिलाड़ी ए की गारंटीकृत अदायगी है। फलस्वरूप,

मैक्सिमिन के अनुरूप रणनीति को कहा जाता है अधिकतम रणनीति . खिलाड़ी परखिलाड़ी के भुगतान को कम करने में रुचि रखते हैं लेकिन, Bj की रणनीति चुनते हुए, वह अधिकतम संभव भुगतान को ध्यान में रखता है लेकिन।निरूपित

सभी संख्याओं में से, सबसे छोटा चुनें

और बुलाओ शीर्ष खेल मूल्य या मिनिमैक्स अदायगी(मिनीमैक्स)। खिलाड़ी बी के अहंकार की गारंटी हार. इसलिए,

मिनिमैक्स रणनीति को कहा जाता है मिनिमैक्स रणनीति।

वह सिद्धांत जो खिलाड़ियों को सबसे "सतर्क" मिनिमैक्स और मैक्सिमम रणनीतियों के चुनाव को निर्देशित करता है, कहलाता है न्यूनतम सिद्धांत . यह सिद्धांत उचित धारणा से चलता है कि प्रत्येक खिलाड़ी प्रतिद्वंद्वी के विपरीत लक्ष्य को प्राप्त करना चाहता है।

प्रमेय। खेल की कम कीमत कभी भी खेल की ऊपरी कीमत से अधिक नहीं होती है। .

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

यदि खिलाड़ियों में से एक (उदाहरण के लिए लेकिन)अपनी इष्टतम रणनीति पर कायम रहता है, और दूसरा खिलाड़ी (पर)किसी भी तरह से अपनी इष्टतम रणनीति से विचलित हो जाएगा, तब विचलन करने वाले खिलाड़ी के लिए, यह कभी फायदेमंद नहीं हो सकता;खिलाड़ी का ऐसा विचलन परअधिक से अधिक लाभ को अपरिवर्तित छोड़ सकते हैं। और सबसे खराब स्थिति में, इसे बढ़ाएं।

इसके विपरीत, यदि परअपनी इष्टतम रणनीति का पालन करता है, और लेकिनअपने आप से भटक जाता है, तो यह किसी भी तरह से फायदेमंद नहीं हो सकता है लेकिन।

शुद्ध रणनीतियों की एक जोड़ी खेल के लिए एक इष्टतम समाधान देती है यदि और केवल यदि संबंधित तत्व अपने कॉलम में सबसे बड़ा और अपनी पंक्ति में सबसे छोटा दोनों है। ऐसी स्थिति, यदि मौजूद हो, कहलाती है पावर प्वाइंट। ज्यामिति में, एक सतह पर एक बिंदु जिसमें संपत्ति होती है: एक समन्वय के साथ-साथ न्यूनतम और दूसरे के साथ अधिकतम, कहा जाता है शक्ति डॉट, सादृश्य द्वारा इस शब्द का प्रयोग गेम थ्योरी में किया जाता है।

खेल जिसके लिए , बुलाया पावर प्वाइंट खेल। जिस तत्व में यह गुण होता है वह मैट्रिक्स का पावर पॉइंट होता है।

इसलिए, पावर पॉइंट वाले प्रत्येक गेम के लिए, एक समाधान होता है जो दोनों पक्षों के लिए इष्टतम रणनीतियों की एक जोड़ी निर्धारित करता है, जो निम्नलिखित गुणों में भिन्न होता है।

1) यदि दोनों पक्ष अपनी इष्टतम रणनीतियों पर टिके रहते हैं, तो औसत भुगतान खेल की शुद्ध लागत के बराबर होता है वी, जो इसकी निचली और ऊपरी कीमत दोनों है।

2) यदि एक पक्ष अपनी इष्टतम रणनीति का पालन करता है, जबकि दूसरा अपने से विचलित होता है, तो विचलित करने वाला पक्ष केवल इससे हार सकता है और किसी भी स्थिति में अपना लाभ नहीं बढ़ा सकता है।

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

22. मिश्रित रणनीतियों में खेल का समाधान।

व्यावहारिक महत्व के परिमित खेलों में, बल बिंदु वाले खेल अपेक्षाकृत दुर्लभ हैं; अधिक विशिष्ट मामला तब होता है जब खेल के निचले और ऊपरी मूल्य अलग-अलग होते हैं। ऐसे खेलों के मैट्रिसेस का विश्लेषण करते हुए, हम इस निष्कर्ष पर पहुंचते हैं कि यदि प्रत्येक खिलाड़ी को एक ही रणनीति का विकल्प दिया जाता है, तो, एक यथोचित अभिनय प्रतिद्वंद्वी के आधार पर, यह विकल्प मिनिमैक्स सिद्धांत द्वारा निर्धारित किया जाना चाहिए। हमारी अधिकतम रणनीति का पालन करते हुए, प्रतिद्वंद्वी के किसी भी व्यवहार के लिए, हम निश्चित रूप से खेल α की कम कीमत के बराबर भुगतान की गारंटी देते हैं। मिश्रित रणनीतियाँ

मिश्रित रणनीति एसए खिलाड़ी A को शुद्ध रणनीतियों का अनुप्रयोग कहा जाता है A1,A1,…,Ai,…,Am with प्रायिकताएं p1,p2,…pi,…pm, और प्रायिकताओं का योग 1: के बराबर है। खिलाड़ी ए की मिश्रित रणनीतियों को मैट्रिक्स के रूप में लिखा जाता है

या एक स्ट्रिंग के रूप में Sa=(p1,p2,…,pi,…,pm).

इसी तरह, खिलाड़ी बी की मिश्रित रणनीतियों को निरूपित किया जाता है:

या Sb=(q1,q2,…,qi,…,qn),

जहां रणनीतियों के प्रकट होने की संभावनाओं का योग 1 के बराबर है।

जाहिर है, प्रत्येक शुद्ध रणनीति मिश्रित का एक विशेष मामला है, जिसमें एक को छोड़कर सभी रणनीतियों को शून्य आवृत्तियों (संभावनाओं) के साथ लागू किया जाता है, और यह 1 की आवृत्ति (संभाव्यता) के साथ लागू होता है।

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

जहां α और β खेल के निचले और ऊपरी मूल्य हैं।

यह कथन तथाकथित की सामग्री है गेम थ्योरी का मूल सिद्धांत।यह प्रमेय पहली बार 1928 में जॉन वॉन न्यूमैन द्वारा सिद्ध किया गया था। प्रमेय के ज्ञात प्रमाण अपेक्षाकृत जटिल हैं; इसलिए, हम केवल इसके सूत्रीकरण को प्रस्तुत करते हैं।

प्रत्येक परिमित खेल में कम से कम एक इष्टतम समाधान होता है, संभवतः मिश्रित रणनीतियों के बीच।

यह मुख्य प्रमेय से इस प्रकार है कि प्रत्येक परिमित खेल की एक कीमत होती है।

चलो और – इष्टतम रणनीतियों की जोड़ी। यदि एक शुद्ध रणनीति को गैर-शून्य संभावना के साथ एक इष्टतम मिश्रित रणनीति में शामिल किया जाता है, तो इसे कहा जाता है सक्रिय (उपयोगी) .

निष्पक्ष सक्रिय रणनीति प्रमेय: यदि खिलाड़ियों में से एक अपनी इष्टतम मिश्रित रणनीति का पालन करता है, तो भुगतान अपरिवर्तित रहता है और खेल v की लागत के बराबर होता है, यदि दूसरा खिलाड़ी अपनी सक्रिय रणनीतियों से आगे नहीं जाता है।

खिलाड़ी अपनी किसी भी सक्रिय रणनीति का अपने शुद्ध रूप में उपयोग कर सकता है, और उन्हें किसी भी अनुपात में मिला भी सकता है।

यह प्रमेय बहुत व्यावहारिक महत्व का है - यह एक सैडल बिंदु के अभाव में इष्टतम रणनीतियों को खोजने के लिए विशिष्ट मॉडल देता है।

विचार करना 2x2 आकार का खेल, जो एक परिमित खेल का सबसे सरल मामला है। यदि इस तरह के खेल में एक काठी बिंदु है, तो इष्टतम समाधान इस बिंदु के अनुरूप शुद्ध रणनीतियों की एक जोड़ी है।

गेम थ्योरी के मौलिक प्रमेय के अनुसार बिना सैडल पॉइंट वाला गेम इष्टतम समाधान मौजूद है और मिश्रित रणनीतियों की एक जोड़ी द्वारा निर्धारित किया जाता हैतथा।

उन्हें खोजने के लिए, हम सक्रिय रणनीतियों पर प्रमेय का उपयोग करते हैं। अगर खिलाड़ी लेकिनअपनी इष्टतम रणनीति का पालन करता है , तो उसका औसत भुगतान खेल की कीमत के बराबर होगा वी, कोई फर्क नहीं पड़ता कि खिलाड़ी किस सक्रिय रणनीति का उपयोग करता है पर। 2v2 गेम के लिए, यदि कोई ssdl बिंदु नहीं है, तो किसी भी प्रतिद्वंद्वी की शुद्ध रणनीति सक्रिय है। खिलाड़ी जीत लेकिन(खिलाड़ी की हार पर)- एक यादृच्छिक चर, गणितीय अपेक्षा (औसत मूल्य) जिसमें से खेल की कीमत है। इसलिए, एक खिलाड़ी का औसत भुगतान लेकिन(इष्टतम रणनीति) के बराबर होगी वीपहली और दूसरी दोनों विरोधी रणनीतियों के लिए।

खेल को अदायगी मैट्रिक्स द्वारा दिया जाना चाहिए।

औसत खिलाड़ी अदायगी लेकिन,यदि वह इष्टतम मिश्रित रणनीति और खिलाड़ी का उपयोग करता है पर -शुद्ध रणनीति B1 (यह अदायगी मैट्रिक्स के पहले कॉलम से मेल खाती है आर),खेल की कीमत के बराबर वी: .

खिलाड़ी को समान औसत अदायगी प्राप्त होती है लेकिन, यदि दूसरा खिलाड़ी रणनीति B2 का उपयोग करता है, अर्थात। . यह देखते हुए, हम इष्टतम रणनीति निर्धारित करने के लिए समीकरणों की एक प्रणाली प्राप्त करते हैं और खेल की कीमतें वी:

इस प्रणाली को हल करते हुए, हम इष्टतम रणनीति प्राप्त करते हैं

और खेल की कीमत।

खोजने के लिए सक्रिय रणनीति प्रमेय लागू करना – खिलाड़ी की इष्टतम रणनीति पर,हम खिलाड़ी की किसी भी शुद्ध रणनीति के लिए इसे प्राप्त करते हैं लेकिन (ए1 या ए2) औसत खिलाड़ी नुकसान परखेल की कीमत के बराबर वी, अर्थात।

फिर इष्टतम रणनीति सूत्रों द्वारा निर्धारित की जाती है: .

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

डुप्लिकेट ऐसी रणनीतियाँ कहलाती हैं जो अदायगी मैट्रिक्स में तत्वों के समान मूल्यों के अनुरूप होती हैं, अर्थात। मैट्रिक्स में समान पंक्तियाँ (कॉलम) हैं।

यदि मैट्रिक्स की i-वें पंक्ति के सभी तत्व k-वें पंक्ति के संगत तत्वों से कम हैं, तो खिलाड़ी के लिए i-वें रणनीति लेकिनलाभहीन (कम जीतना)।

यदि मैट्रिक्स के rth कॉलम के सभी तत्व jth कॉलम के संबंधित तत्वों से अधिक हैं, तो खिलाड़ी के लिए पर r-th रणनीति लाभहीन है (नुकसान अधिक है)।

दोहराव और स्पष्ट रूप से लाभहीन रणनीतियों को खत्म करने की प्रक्रिया हमेशा खेल के समाधान से पहले होनी चाहिए।

23. 2×2 खेल की ज्यामितीय व्याख्या

खेल निर्णय 2×2एक स्पष्ट ज्यामितीय व्याख्या की अनुमति देता है।

खेल को अदायगी मैट्रिक्स P=(aij), i, j=1,2 द्वारा दिया जाता है।

भुज पर (अंजीर।) एक तरफ सेट करें इकाईखंड A1A2; बिंदु A1 ( एक्स= 0) रणनीति A1, बिंदु A2 को दर्शाता है ( एक्स=1) रणनीति A2 को दर्शाता है, और इस खंड के सभी मध्यवर्ती बिंदु पहले खिलाड़ी की मिश्रित रणनीति Sa हैं, और Sa से खंड के दाहिने छोर तक की दूरी रणनीति A1 की प्रायिकता p1 है। , बाएँ छोर की दूरी रणनीति A2 . की प्रायिकता p2 है .

आइए बिंदु A1 और A2 के माध्यम से x-अक्ष पर दो लंबवत बनाएं: अक्ष I-I और अक्ष II-II। I-I अक्ष पर, हम रणनीति A1 के तहत लाभ को स्थगित कर देंगे; अक्ष II-II पर - रणनीति A2 के तहत अदायगी।

यदि खिलाड़ी A रणनीति A1 का उपयोग करता है, तो खिलाड़ी B की रणनीति B1 के तहत उसका भुगतान a11 है, और रणनीति B2 के तहत यह a12 है। अक्ष I पर अंक a11 और a12 अंक B1 और B2 के संगत हैं।

यदि खिलाड़ी A रणनीति A2 का उपयोग करता है, तो खिलाड़ी B की रणनीति B1 के तहत उसका भुगतान a21 है, और रणनीति B2 के तहत यह a22 के बराबर है। अंक a21 और a22 अक्ष II पर बिंदु B1 और B2 के संगत हैं।

हम बिंदु B1 (I) और B1 (II) को जोड़ते हैं; बी 2 (आई) और बी 2 (द्वितीय)। दो सीधी रेखाएँ मिलीं। सीधी रेखा B1B1 - यदि खिलाड़ी लेकिनएक मिश्रित रणनीति लागू करता है (रणनीतियों का कोई भी संयोजन A1 और A2 संभावनाओं के साथ p1 और p2) और खिलाड़ी B रणनीति B1 लागू करता है। विजेता खिलाड़ी लेकिनइस रेखा पर किसी बिंदु से मेल खाती है। मिश्रित रणनीति के अनुरूप औसत अदायगी सूत्र a11p1+a21p2 द्वारा निर्धारित की जाती है और इसे बिंदु M1 द्वारा दर्शाया जाता है लाइन बी1बी1.

इसी तरह, हम दूसरे खिलाड़ी द्वारा रणनीति B2 के उपयोग के अनुरूप खंड B2B2 का निर्माण करते हैं। इस मामले में, औसत लाभ सूत्र a12p1+a22p2 द्वारा निर्धारित किया जाता है और इसे बिंदु M2 द्वारा दर्शाया जाता है सीधी रेखा B2B2 पर।

हमें एक इष्टतम रणनीति S*a खोजने की आवश्यकता है, यानी एक जिसके लिए न्यूनतम भुगतान (किसी भी व्यवहार के लिए .) पर)अधिकतम की ओर मुड़ जाएगा। ऐसा करने के लिए, हम निर्माण करेंगे लाभ की निचली सीमा B1B2 रणनीतियों के साथ , यानी, अंजीर में चिह्नित टूटी हुई रेखा B1NB2। मोटी रेखा। इस निचली सीमा खिलाड़ी के न्यूनतम भुगतान को व्यक्त करेगी लेकिनइसकी किसी भी मिश्रित रणनीति के लिए; दूरसंचार विभागएन , जिसमें यह न्यूनतम भुगतान अधिकतम तक पहुंच जाता है, और समाधान (इष्टतम रणनीति) और खेल की कीमत निर्धारित करता है। बिंदु निर्देशांक एनक्या खेलने की कोई कीमत है वी. बिंदु निर्देशांक एनहम रेखाओं B1B1 और B2B2 के प्रतिच्छेदन बिंदुओं के निर्देशांक के रूप में पाते हैं। हमारे मामले में, खेल का समाधान रणनीतियों के प्रतिच्छेदन बिंदु द्वारा निर्धारित किया गया था। हालांकि, ऐसा हमेशा नहीं होगा।

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

यदि अदायगी मैट्रिक्स में ऋणात्मक संख्याएँ होती हैं, तो समस्या के चित्रमय समाधान के लिए गैर-ऋणात्मक तत्वों के साथ एक नए मैट्रिक्स पर स्विच करना बेहतर होता है; ऐसा करने के लिए, मूल मैट्रिक्स के तत्वों में संबंधित सकारात्मक संख्या जोड़ना पर्याप्त है। खेल का निर्णय नहीं बदलेगा, लेकिन इस संख्या से खेल की कीमत बढ़ जाएगी। चित्रमय विधि का उपयोग खेल 2×n, m×2 को हल करने के लिए किया जा सकता है।

24. एक मैट्रिक्स गेम को रैखिक प्रोग्रामिंग समस्या में कम करना

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

मान लें कि m×n गेम को अदायगी मैट्रिक्स द्वारा दिया गया है . खिलाड़ी लेकिनरणनीतियाँ हैं A1,A2,..Ai,..Am , खिलाड़ी पर -रणनीतियाँ बी 1,बी 2,..बीमैं,.. बीएन। इष्टतम रणनीतियों को निर्धारित करना आवश्यक है और कहां संगत शुद्ध कार्यनीतियों को लागू करने की प्रायिकताएँ हैं Ai,Bj,

इष्टतम रणनीति निम्नलिखित आवश्यकता को पूरा करती है। यह खिलाड़ी प्रदान करता है लेकिनऔसत अदायगी खेल की कीमत से कम नहीं है वी, खिलाड़ी की किसी भी रणनीति के लिए परऔर खेल की कीमत के बराबर अदायगी वी, खिलाड़ी की इष्टतम रणनीति के साथ पर।व्यापकता के नुकसान के बिना, हम सेट करते हैं वी> 0; यह सभी तत्वों को बनाकर प्राप्त किया जा सकता है . अगर खिलाड़ी लेकिनकिसी भी शुद्ध रणनीति के खिलाफ मिश्रित रणनीति लागू करता है Bj खिलाड़ी पर,तब वह मिलता है औसत अदायगी , या जीतने की गणितीय अपेक्षा (यानी तत्व जे-जीहेपेऑफ मैट्रिक्स कॉलम को ए 1, ए 2, .. एआई, .. एएम और परिणाम जोड़े गए रणनीतियों की संबंधित संभावनाओं से शब्द द्वारा गुणा किया जाता है)।

एक इष्टतम रणनीति के लिए, सभी औसत भुगतान खेल की कीमत से कम नहीं हैं वी, इसलिए हमें असमानताओं की एक प्रणाली मिलती है:

प्रत्येक असमानता को एक संख्या से विभाजित किया जा सकता है। आइए नए चर पेश करें: . तब सिस्टम रूप लेता है

खिलाड़ी लक्ष्य लेकिन -अपने गारंटीकृत भुगतान को अधिकतम करें, अर्थात। खेल की कीमत वी

समानता से विभाजित करने पर, हम पाते हैं कि चर इस शर्त को पूरा करते हैं: . खेल मूल्य अधिकतमकरण वीमात्रा को कम करने के बराबर है , तो समस्या को निम्नानुसार तैयार किया जा सकता है: परिवर्तनीय मूल्यों को परिभाषित करें , एमएरैखिक बाधाओं को संतुष्ट करने के लिए(*) तथा जबकि रैखिक कार्य (2*) न्यूनतम में बदल गया।

यह एक रैखिक प्रोग्रामिंग समस्या है। समस्या हल करना (1*)–(2*), हम इष्टतम समाधान प्राप्त करते हैं और इष्टतम रणनीति .

इष्टतम रणनीति निर्धारित करने के लिए, यह ध्यान में रखा जाना चाहिए कि खिलाड़ी परगारंटीकृत भुगतान को कम करने का प्रयास करता है, अर्थात। अधिकतम खोजें चर असमानताओं को संतुष्ट करते हैं

जो इस तथ्य का अनुसरण करता है कि एक खिलाड़ी का औसत नुकसान परखेल के मूल्य से अधिक नहीं है, इससे कोई फर्क नहीं पड़ता कि खिलाड़ी किस शुद्ध रणनीति का उपयोग करता है लेकिन.

यदि हम (4*) को निरूपित करते हैं, तो हमें असमानताओं की एक प्रणाली प्राप्त होती है:

चर शर्त को पूरा करते हैं।

खेल को अगले कार्य के लिए कम कर दिया गया था।

परिवर्तनीय मान निर्धारित करें , जो असमानताओं की प्रणाली को संतुष्ट करते हैं (5*)तथा रैखिक फ़ंक्शन को अधिकतम करें

रैखिक प्रोग्रामिंग समस्या का समाधान (5*), (6*) इष्टतम रणनीति निर्धारित करता है। उसी समय, खेल की कीमत। (7*)

समस्याओं (1*), (2*) और (5*), (6*) के लिए विस्तारित मैट्रिक्स को संकलित करने के बाद, हम सुनिश्चित करते हैं कि ट्रांसपोज़िशन द्वारा एक मैट्रिक्स दूसरे से प्राप्त किया गया था:

इस प्रकार, रैखिक प्रोग्रामन समस्याएँ (1*), (2*) और (5*), (6*) परस्पर द्वैत हैं। जाहिर है, विशिष्ट समस्याओं में इष्टतम रणनीतियों का निर्धारण करते समय, किसी को पारस्परिक रूप से दोहरी समस्याओं में से एक को चुनना चाहिए, जिसका समाधान कम श्रमसाध्य है, और दूसरी समस्या का समाधान द्वैत प्रमेयों का उपयोग करके खोजना चाहिए।

एम × एन आकार के एक मनमाना परिमित खेल को हल करते समय, निम्नलिखित योजना का पालन करने की सिफारिश की जाती है:

1. अन्य रणनीतियों की तुलना में अदायगी मैट्रिक्स से स्पष्ट रूप से लाभहीन रणनीतियों को बाहर करें। खिलाड़ी के लिए ऐसी रणनीति लेकिन

नीचे संचालनएक विशिष्ट लक्ष्य को प्राप्त करने के लिए एक विचार और दिशा से एकजुट किसी भी घटना के रूप में समझा जाता है।

एक ऑपरेशन हमेशा एक प्रबंधित घटना होती है, यानी। यह हम पर निर्भर है कि हम उन मापदंडों को चुनें जो इसे व्यवस्थित करने के तरीके की विशेषता रखते हैं।

हमारे आधार पर मापदंडों के किसी भी निश्चित विकल्प को कहा जाएगा फेसला.

इष्टतम समाधान वे हैं जो एक कारण या किसी अन्य के लिए दूसरों के लिए बेहतर हैं।

संचालन अनुसंधान का मुख्य उद्देश्य है इष्टतम समाधानों का प्रारंभिक मात्रात्मक औचित्य. संचालन अनुसंधान का उद्देश्य निर्णय लेने को पूरी तरह से स्वचालित करना नहीं है। निर्णय हमेशा व्यक्ति द्वारा किया जाता है। संचालन अनुसंधान का उद्देश्य मात्रात्मक डेटा और सिफारिशें तैयार करना है जो किसी व्यक्ति के लिए निर्णय लेना आसान बनाता है।

मुख्य कार्य के साथ - इष्टतम समाधानों की पुष्टि -संचालन अनुसंधान के दायरे में अन्य कार्य शामिल हैं:

संचालन के आयोजन के लिए विभिन्न विकल्पों का तुलनात्मक मूल्यांकन,

विभिन्न मापदंडों के संचालन पर प्रभाव का मूल्यांकन,

"अड़चनों" की जांच, अर्थात्। तत्व, जिसके विघटन का संचालन की सफलता आदि पर विशेष रूप से प्रबल प्रभाव पड़ता है।

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

नीचे क्षमताऑपरेशन को उसके सामने आने वाले कार्य के प्रदर्शन के लिए उसके अनुकूलन की डिग्री के रूप में समझा जाता है।

एक ऑपरेशन की प्रभावशीलता का न्याय करने के लिए और अलग-अलग संगठित संचालन की प्रभावशीलता की तुलना करने के लिए, किसी के पास कुछ संख्यात्मक होना चाहिए मूल्यांकन मानदंडया कार्यनिष्पादन संकेतक.

संचालन अनुसंधान में क्रियाओं का क्रम।

1. अध्ययन का उद्देश्य तैयार किया जाता है और समस्या विवरण विकसित किया जाता है।

2. किसी भी क्षेत्र में मात्रात्मक विधियों को लागू करने के लिए, घटना का गणितीय मॉडल बनाना हमेशा आवश्यक होता है। मूल के गुणों के विश्लेषण के आधार पर यह मॉडल बनाया गया है।

3. मॉडल बनाने के बाद उस पर परिणाम प्राप्त होते हैं

4. उन्हें मूल के रूप में व्याख्यायित किया जाता है और मूल में स्थानांतरित किया जाता है।

5. तुलना की सहायता से, सिमुलेशन परिणामों की तुलना मूल के प्रत्यक्ष अध्ययन से प्राप्त परिणामों से की जाती है।

यदि मॉडल का उपयोग करके प्राप्त परिणाम मूल के अध्ययन में प्राप्त परिणामों के करीब हैं, तो इन गुणों के संबंध में, मॉडल को मूल के लिए पर्याप्त माना जा सकता है।

स्वचालित नियंत्रण प्रणालियों को डिजाइन और संचालित करते समय, कार्य अक्सर उनके कामकाज के मात्रात्मक और गुणात्मक पैटर्न दोनों के विश्लेषण से संबंधित होते हैं, उनकी इष्टतम संरचना का निर्धारण करते हैं, आदि।

इन समस्याओं को हल करने के लिए वस्तुओं पर प्रत्यक्ष प्रयोग के कई महत्वपूर्ण नुकसान हैं:

1. वस्तु के संचालन के स्थापित तरीके का उल्लंघन किया जाता है।

2. एक पूर्ण पैमाने के प्रयोग में, एक प्रणाली आदि के निर्माण के लिए सभी वैकल्पिक विकल्पों का विश्लेषण करना असंभव है।

इन समस्याओं को ऑब्जेक्ट से अलग और कंप्यूटर पर लागू किए गए मॉडल पर हल करने की सलाह दी जाती है।

सूचना प्रणाली मॉडलिंग करते समय, गणितीय मॉडल व्यापक रूप से उपयोग किए जाते हैं।

गणितीय मॉडलिंग की विधि एक उपयुक्त गणितीय विवरण को संकलित करके और उसके आधार पर, अध्ययन के तहत वस्तु की विशेषताओं की गणना करके विभिन्न वस्तुओं का अध्ययन करने की एक विधि है।

गणितीय मॉडल बनाना आवश्यक है। यह औपचारिक रूप से मूल के कामकाज को दर्शाता है और इसके व्यवहार के मुख्य पैटर्न का वर्णन करता है। इस मामले में, सभी माध्यमिक, महत्वहीन कारकों को विचार से बाहर रखा गया है।

गणितीय मॉडलिंग का उद्देश्य जटिल प्रणालियां हैं। एक जटिल प्रणाली बाहरी कारकों के प्रभाव में बड़ी संख्या में सूचना-संबंधित और परस्पर क्रिया करने वाले तत्वों का एक निश्चित तरीका संगठित और उद्देश्यपूर्ण कार्य है।

कंप्यूटर पर मॉडलिंग सिस्टम के 4 मुख्य चरण हैं:

प्रणाली के एक वैचारिक मॉडल का निर्माण और इसकी औपचारिकता;

सिस्टम मॉडल का एल्गोरिदमीकरण और मॉडलिंग कार्यक्रम का विकास;

प्रारंभिक सिमुलेशन परिणाम प्राप्त करना और उनकी व्याख्या करना;

मॉडल और प्रणाली की पर्याप्तता की जाँच करना; मॉडल समायोजन

मॉडलिंग के परिणामों, मॉडल के कार्यान्वयन के आधार पर सिस्टम के कामकाज के गुणवत्ता संकेतकों की मुख्य गणना।

व्याख्यान 3. विशेषज्ञ आकलन की विधि की बुनियादी अवधारणाएँ। विशेषज्ञ समूहों का गठन। मतदान प्रक्रियाएं। रैंकिंग के तरीके, युग्मित तुलना, सापेक्ष पैमाने में मूल्यांकन।

1. अर्थव्यवस्था में संचालन के अध्ययन का विषय और उद्देश्य। संचालन अनुसंधान के सिद्धांत की बुनियादी अवधारणाएं।

संचालन अनुसंधान का विषय संगठनात्मक प्रबंधन प्रणाली या संगठन है जिसमें बड़ी संख्या में परस्पर क्रिया करने वाली इकाइयाँ होती हैं जो हमेशा एक दूसरे के अनुरूप नहीं होती हैं और विपरीत हो सकती हैं।

संचालन अनुसंधान का उद्देश्य संगठनों के प्रबंधन पर किए गए निर्णयों को मात्रात्मक रूप से प्रमाणित करना है

जो समाधान पूरे संगठन के लिए सबसे अधिक फायदेमंद साबित होता है, उसे इष्टतम कहा जाता है, और जो समाधान एक या अधिक विभागों के लिए सबसे अधिक फायदेमंद होता है, वह उप-इष्टतम होगा।

संचालन अनुसंधान एक विज्ञान है जो संगठनात्मक प्रणालियों के सबसे इष्टतम प्रबंधन के लिए विधियों के विकास और व्यावहारिक अनुप्रयोग से संबंधित है।

एक ऑपरेशन किसी भी घटना (कार्यों की प्रणाली) है जो एक ही योजना से एकजुट होती है और किसी लक्ष्य की उपलब्धि की ओर निर्देशित होती है।

संचालन अनुसंधान का उद्देश्य इष्टतम समाधानों का प्रारंभिक मात्रात्मक औचित्य है।

हमारे आधार पर मापदंडों के किसी भी निश्चित विकल्प को समाधान कहा जाता है। समाधानों को इष्टतम कहा जाता है यदि वे किसी न किसी कारण से दूसरों पर पसंद किए जाते हैं।

पैरामीटर, जिनकी समग्रता से एक समाधान बनता है, समाधान के तत्व कहलाते हैं।

स्वीकार्य समाधानों के सेट को ऐसी शर्तें दी जाती हैं जो निश्चित हैं और जिनका उल्लंघन नहीं किया जा सकता है।

प्रदर्शन संकेतक - एक मात्रात्मक माप जो आपको दक्षता के संदर्भ में विभिन्न समाधानों की तुलना करने की अनुमति देता है।

2. नेटवर्क योजना और प्रबंधन की अवधारणा। प्रक्रिया और उसके तत्वों का नेटवर्क मॉडल।

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

नेटवर्क योजना और प्रबंधन का आधार नेटवर्क मॉडल (एसएम) है, जो एक विशिष्ट लक्ष्य को प्राप्त करने की प्रक्रिया को प्रतिबिंबित करने वाली परस्पर संबंधित गतिविधियों और घटनाओं का एक सेट मॉडल करता है। इसे ग्राफ या टेबल के रूप में प्रस्तुत किया जा सकता है।

नेटवर्क मॉडल की मूल अवधारणाएँ:

घटना, काम, रास्ता।

घटनाएँ एक या अधिक गतिविधियों के निष्पादन के परिणाम हैं। उनके पास समय का कोई विस्तार नहीं है।

एक पथ एक के बाद एक कार्य की एक श्रृंखला है, जो प्रारंभिक और अंतिम शिखर को जोड़ता है।

पथ की अवधि उसके घटक कार्यों की अवधि के योग से निर्धारित होती है।

3. नेटवर्क आरेख का निर्माण और क्रम।

एक नेटवर्क मॉडल का उपयोग एक मॉडल के रूप में किया जाता है जो नेटवर्क योजना और प्रबंधन प्रणाली (एसपीयू) में निर्माण और स्थापना कार्य की प्रक्रिया के तकनीकी और संगठनात्मक अंतर्संबंधों को दर्शाता है।

एक नेटवर्क मॉडल प्रक्रियाओं का एक चित्रमय प्रतिनिधित्व है, जिसके कार्यान्वयन से एक या अधिक लक्ष्यों की प्राप्ति होती है, जो इन प्रक्रियाओं के बीच स्थापित संबंधों को दर्शाता है। नेटवर्क आरेख परिकलित समय मापदंडों के साथ एक नेटवर्क मॉडल है।

नेटवर्क आरेख की संरचना, जो कार्य और घटनाओं की पारस्परिक निर्भरता को निर्धारित करती है, इसकी टोपोलॉजी कहलाती है।

कार्य एक उत्पादन प्रक्रिया है जिसके लिए समय, श्रम और भौतिक संसाधनों की आवश्यकता होती है, जो जब प्रदर्शन किया जाता है, तो कुछ परिणाम प्राप्त होते हैं।

निर्भरता (काल्पनिक कार्य), जिसमें समय के व्यय की आवश्यकता नहीं होती है, एक बिंदीदार तीर द्वारा दर्शाया गया है। घटनाओं और गतिविधियों के बीच संबंधों को दिखाने के लिए नेटवर्क आरेख में डमी कार्य का उपयोग किया जाता है।

नेटवर्क शेड्यूल में, समय, लागत और काम की अन्य विशेषताओं का उपयोग किया जाता है।

कार्य की अवधि - कार्य दिवसों या समय की अन्य इकाइयों में इस कार्य के निष्पादन का समय, नेटवर्क में सभी कार्यों के लिए समान। कार्य की अवधि या तो एक निश्चित (नियतात्मक) या इसके वितरण के कानून द्वारा निर्दिष्ट एक यादृच्छिक चर हो सकती है।

कार्य की लागत इस कार्य की अवधि और शर्तों के आधार पर इसके कार्यान्वयन के लिए आवश्यक प्रत्यक्ष लागत है।

संसाधनों को इस कार्य को करने के लिए आवश्यक भौतिक इकाइयों की आवश्यकता की विशेषता है।

गुणवत्ता, विश्वसनीयता और कार्य के अन्य संकेतक कार्य की अतिरिक्त विशेषताओं के रूप में कार्य करते हैं।

एक घटना एक या एक से अधिक नौकरियों के पूरा होने का तथ्य है, जो एक या अधिक बाद की नौकरियों की शुरुआत के लिए आवश्यक और पर्याप्त है। प्रत्येक घटना को एक संख्या सौंपी जाती है, जिसे एक कोड कहा जाता है। प्रत्येक कार्य को दो घटनाओं द्वारा परिभाषित किया जाता है: एक प्रारंभ ईवेंट कोड, जिसे i द्वारा दर्शाया जाता है, और एक अंतिम ईवेंट कोड, जिसे j द्वारा दर्शाया जाता है।

वे घटनाएँ जिनमें पिछली गतिविधियाँ नहीं होती हैं, प्रारंभिक घटनाएँ कहलाती हैं; ऐसी घटनाएं जिनमें बाद में नहीं है - अंतिम।

1 नेटवर्क बनाने की दिशा अलग प्रकृति की हो सकती है। एक नेटवर्क ग्राफ प्रारंभिक घटना से अंतिम एक तक और अंतिम एक से प्रारंभिक (प्रारंभिक) तक, साथ ही किसी भी घटना से प्रारंभिक या अंतिम एक तक बनाया जा सकता है।

2 नेटवर्क बनाते समय, निम्नलिखित प्रश्नों को हल किया जाता है:

इस काम को शुरू करने के लिए क्या काम (काम) करना होगा;

इस कार्य के समानांतर कौन-सा कार्य करना चाहिए;

3 प्रारंभिक नेटवर्क शेड्यूल नेटवर्क बनाने वाली गतिविधियों की अवधि को ध्यान में रखे बिना बनाया गया है।

4 ग्राफ का रूप सरल और देखने में आसान होना चाहिए।

5 दो घटनाओं के बीच केवल एक ही कार्य हो सकता है। इमारतों और संरचनाओं के निर्माण के दौरान, काम क्रमिक रूप से, समानांतर में या एक साथ, कुछ श्रृंखला में और कुछ समानांतर में किया जा सकता है, जिसके परिणामस्वरूप व्यक्तिगत कार्यों के बीच विभिन्न निर्भरताएं बनती हैं।

घटनाओं की संख्या (कोडिंग) नेटवर्क निर्माण के पूरा होने के बाद, प्रारंभिक घटना से अंतिम एक तक शुरू की जाती है।

4. नेटवर्क आरेख का महत्वपूर्ण पथ। समय आरक्षित। नेटवर्क आरेख में घटनाओं और गतिविधियों की प्रारंभिक और देर की तारीखें।

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

महत्वपूर्ण पथ को नेटवर्क आरेख पर मोटी या दोहरी रेखाओं (तीर) द्वारा दर्शाया गया है।

नेटवर्क आरेख बनाते समय दो अवधारणाओं का विशेष महत्व है:

कार्य की प्रारंभिक शुरुआत - वह अवधि जिसके पहले स्वीकृत तकनीकी अनुक्रम का उल्लंघन किए बिना यह काम शुरू करना असंभव है। यह आरंभिक घटना से इस कार्य के आरंभ तक के सबसे लंबे पथ द्वारा निर्धारित किया जाता है।

लेट फ़िनिश किसी कार्य की नवीनतम समाप्ति तिथि है जो कार्य की कुल अवधि को नहीं बढ़ाती है। यह किसी दिए गए घटना से सभी कार्यों के पूरा होने तक के सबसे छोटे रास्ते से निर्धारित होता है।

प्रारंभिक समाप्ति वह समय सीमा है जिसके पहले काम पूरा नहीं किया जा सकता है। यह प्रारंभिक शुरुआत और इस कार्य की अवधि के बराबर है।

देर से शुरू - वह अवधि जिसके बाद निर्माण की कुल अवधि को बढ़ाए बिना इस काम को शुरू करना असंभव है। यह दिए गए कार्य की अवधि को घटाकर देर से समाप्त करने के बराबर है।

यदि घटना केवल एक कार्य का अंत है (अर्थात, केवल एक तीर को निर्देशित किया गया है), तो इस कार्य का प्रारंभिक अंत अगले एक की प्रारंभिक शुरुआत के साथ मेल खाता है।

कुल (पूर्ण) आरक्षित अधिकतम समय है जिसके लिए कार्य की कुल अवधि को बढ़ाए बिना इस कार्य के निष्पादन में देरी हो सकती है। यह देर से और जल्दी शुरू (या देर से और जल्दी खत्म - जो समान है) के बीच के अंतर से निर्धारित होता है।

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

5. गतिशील प्रोग्रामिंग। बेलमैन का इष्टतमता और नियंत्रण का सिद्धांत।

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

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

बेलमैन के शब्दों में, विधि का मुख्य दोष "आयामीता का अभिशाप" है - इसकी जटिलता बढ़ती समस्या आयामीता के साथ भयावह रूप से बढ़ जाती है।

6. उद्यमों के बीच धन के वितरण की समस्या।

यह कहा जा सकता है कि गतिशील प्रोग्रामिंग विधि द्वारा इष्टतम नियंत्रण के निर्माण की प्रक्रिया को दो चरणों में विभाजित किया गया है: प्रारंभिक और अंतिम। प्रारंभिक चरण में, प्रत्येक चरण के लिए, सिस्टम की स्थिति (पिछले चरणों के परिणामस्वरूप प्राप्त) के आधार पर एसओसी निर्धारित किया जाता है, और इस से शुरू होने वाले सभी शेष चरणों में सशर्त रूप से इष्टतम लाभ भी निर्भर करता है राज्य। अंतिम चरण में, प्रत्येक चरण के लिए (बिना शर्त) इष्टतम नियंत्रण निर्धारित किया जाता है। प्रारंभिक (सशर्त) अनुकूलन चरण दर चरण उल्टे क्रम में किया जाता है: अंतिम चरण से पहले तक; अंतिम (बिना शर्त) अनुकूलन - चरणों से भी, लेकिन एक प्राकृतिक क्रम में: पहले चरण से अंतिम तक। अनुकूलन के दो चरणों में से पहला अतुलनीय रूप से अधिक महत्वपूर्ण और समय लेने वाला है। पहले चरण के अंत के बाद, दूसरे चरण के कार्यान्वयन में कोई कठिनाई नहीं होती है: पहले चरण में पहले से तैयार की गई सिफारिशों को "पढ़ना" बाकी है।

7. रैखिक प्रोग्रामिंग की समस्या का विवरण।

रैखिक प्रोग्रामिंग आर्थिक समस्याओं को हल करने के लिए एक लोकप्रिय उपकरण है जो एक मानदंड की उपस्थिति की विशेषता है (उदाहरण के लिए, उत्पादन कार्यक्रम के इष्टतम विकल्प के माध्यम से उत्पादन से आय को अधिकतम करने के लिए, या, उदाहरण के लिए, परिवहन लागत को कम करने के लिए, आदि) . आर्थिक कार्यों को संसाधन की कमी (सामग्री और/या वित्तीय) की विशेषता है। उन्हें असमानताओं की एक प्रणाली के रूप में लिखा जाता है, कभी-कभी समानता के रूप में।

एक सामान्यीकृत गैर-पैरामीट्रिक पद्धति के ढांचे के भीतर स्वीकार्य मूल्य अंतराल (या बिक्री की मात्रा) के पूर्वानुमान के दृष्टिकोण से, रैखिक प्रोग्रामिंग का उपयोग करने का अर्थ है:

मानदंड f ब्याज के समूह से अगले उत्पाद का MAX मूल्य है।

नियंत्रित चर समूह f के सभी उत्पादों की कीमतें हैं।

सामान्यीकृत गैर-पैरामीट्रिक पद्धति का उपयोग करके हमारी पूर्वानुमान समस्या की सीमाएँ हैं:

ए) असमानताओं की एक प्रणाली (उपभोक्ता व्यवहार की तर्कसंगतता पर बाधाएं) (4.2 देखें। एक सामान्यीकृत गैर-पैरामीट्रिक पद्धति के ढांचे के भीतर पूर्वानुमान);

बी) नियंत्रित चर की गैर-नकारात्मकता की आवश्यकता (हमारी पूर्वानुमान समस्या में, हमें यह आवश्यकता होगी कि समूह एफ के उत्पादों की कीमतें अंतिम समय बिंदु पर कीमतों के 80% से नीचे न गिरें);

सी) समानता के रूप में बजट की कमी - आवश्यकता है कि समूह एफ से उत्पादों की खरीद के लिए लागत की मात्रा स्थिर हो (उदाहरण के लिए 15% मुद्रास्फीति को ध्यान में रखते हुए)।

8. रैखिक प्रोग्रामन समस्याओं को हल करने के लिए आलेखीय विधि।

ग्राफिकल विधि एक रैखिक प्रोग्रामिंग समस्या की ज्यामितीय व्याख्या पर आधारित है और मुख्य रूप से द्वि-आयामी अंतरिक्ष की समस्याओं को हल करने में उपयोग की जाती है और केवल त्रि-आयामी अंतरिक्ष की कुछ समस्याएं होती हैं, क्योंकि समाधान पॉलीहेड्रॉन का निर्माण करना काफी कठिन होता है जो कि बनता है अर्ध-रिक्त स्थान के प्रतिच्छेदन का परिणाम। तीन से अधिक आयामों के स्थान के कार्य को रेखांकन द्वारा बिल्कुल भी प्रदर्शित नहीं किया जा सकता है।

मान लीजिए कि रैखिक प्रोग्रामिंग समस्या दो-आयामी स्थान में दी गई है, अर्थात, बाधाओं में दो चर होते हैं।

किसी फ़ंक्शन का न्यूनतम मान ज्ञात करें

(2.1) जेड = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

एएम1x1 + एएम2x2 बीएम

(2.3) x1 0, x2 0

आइए मान लें कि सिस्टम (2.2) अंडर कंडीशन (2.3) सुसंगत है और इसका समाधान बहुभुज परिबद्ध है। प्रत्येक असमानता (2.2) और (2.3), जैसा कि ऊपर उल्लेख किया गया है, सीमा रेखाओं के साथ एक अर्ध-तल को परिभाषित करता है: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 । Z के स्थिर मानों के लिए रैखिक फलन (2.1) एक सीधी रेखा का समीकरण है: C1x1 + C2x2 = const. आइए हम बाधा प्रणाली (2.2) के समाधान के बहुभुज और Z = 0 (चित्र 2.1) के लिए रैखिक फ़ंक्शन (2.1) का एक ग्राफ बनाएं। तब रैखिक प्रोग्रामिंग की दी गई समस्या को निम्नलिखित व्याख्या दी जा सकती है। समाधान बहुभुज का वह बिंदु ज्ञात कीजिए जिस पर सीधी रेखा C1x1 + C2x2 = const समर्थन रेखा है और Z फ़ंक्शन न्यूनतम तक पहुंच जाता है।

मान Z = C1x1 + C2x2 वेक्टर N = (C1, C2) की दिशा में बढ़ते हैं, इसलिए हम रेखा Z = 0 को वेक्टर X की दिशा में स्वयं के समानांतर ले जाते हैं। अंजीर से। 2.1 यह इस प्रकार है कि रेखा दो बार समाधान के बहुभुज (बिंदु ए और सी पर) के संबंध में एक संदर्भ बन जाती है, और न्यूनतम मान बिंदु ए पर होता है। हम बिंदु ए (x1, x2) के निर्देशांक को हल करके पाते हैं रेखा AB और AE के समीकरणों की प्रणाली।

यदि निर्णय बहुभुज एक असंबद्ध बहुभुज क्षेत्र है, तो दो मामले संभव हैं।

स्थिति 1. सीधी रेखा C1x1 + C2x2 = const, सदिश N की दिशा में या इसके विपरीत चलती हुई, हल बहुभुज को लगातार काटती है और किसी भी बिंदु पर इसका संदर्भ नहीं है। इस स्थिति में, रैखिक फलन ऊपर और नीचे दोनों हल बहुभुज पर असीमित होता है (चित्र 2.2)।

केस 2. सीधी रेखा, चलती हुई, फिर भी समाधान के बहुभुज के सापेक्ष एक समर्थन बन जाती है (चित्र। 2.2, ए - 2.2, सी)। फिर, क्षेत्र के प्रकार के आधार पर, रैखिक फ़ंक्शन को ऊपर से और नीचे से अनबाउंड किया जा सकता है (चित्र 2.2, ए), नीचे से घिरा और ऊपर से अनबाउंड (चित्र। 2.2, बी), या नीचे से और दोनों से घिरा हुआ है। ऊपर से (चित्र। 2.2, सी)।

9. सिंप्लेक्स विधि।

रेखीय प्रोग्रामिंग में सिंप्लेक्स विधि मुख्य है। समस्या का समाधान पॉलीहेड्रॉन स्थितियों के किसी एक शीर्ष पर विचार करने से शुरू होता है। यदि अध्ययन किया गया शीर्ष अधिकतम (न्यूनतम) के अनुरूप नहीं है, तो वे पड़ोसी एक पर चले जाते हैं, समस्या को हल करते समय लक्ष्य फ़ंक्शन के मूल्य को अधिकतम तक बढ़ाते हैं और समस्या को न्यूनतम तक हल करते समय घटते हैं। इस प्रकार, एक शीर्ष से दूसरे शीर्ष पर जाने से लक्ष्य फलन के मान में सुधार होता है। चूंकि पॉलीहेड्रॉन के शिखरों की संख्या सीमित है, इसलिए सीमित संख्या में चरणों में इष्टतम मूल्य खोजने या इस तथ्य को स्थापित करने की गारंटी है कि समस्या असफल है।

यह विधि सार्वभौमिक है, विहित रूप में किसी भी रैखिक प्रोग्रामिंग समस्या पर लागू होती है। यहां बाधाओं की प्रणाली रैखिक समीकरणों की एक प्रणाली है जिसमें अज्ञात की संख्या समीकरणों की संख्या से अधिक होती है। यदि सिस्टम का रैंक r है, तो हम r अज्ञात चुन सकते हैं, जिसे हम शेष अज्ञात के रूप में व्यक्त करेंगे। निश्चितता के लिए, हम मानते हैं कि पहले क्रमागत अज्ञात X1, X2, ..., Xr चुने गए हैं। तब हमारे समीकरणों की प्रणाली को इस प्रकार लिखा जा सकता है

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

10. परिवहन समस्या का विवरण। आधार योजनाओं को निर्धारित करने के तरीके।

कुछ समान उत्पाद के m प्रस्थान बिंदु ("आपूर्तिकर्ता") और n उपभोग बिंदु ("उपभोक्ता") हैं। प्रत्येक आइटम के लिए परिभाषित किया गया है:

ai - i-th आपूर्तिकर्ता की उत्पादन मात्रा, i = 1,…, m;

вj - j-वें उपभोक्ता की मांग, j= 1,…,n;

cij - उत्पादन की एक इकाई को बिंदु एआई - i-वें आपूर्तिकर्ता, बिंदु Bj- j-वें उपभोक्ता तक ले जाने की लागत।

स्पष्टता के लिए, डेटा को एक तालिका के रूप में प्रस्तुत करना सुविधाजनक है, जिसे परिवहन लागत की तालिका कहा जाता है।

एक परिवहन योजना खोजने की आवश्यकता है जो सभी उपभोक्ताओं की मांग को पूरी तरह से संतुष्ट करे, जबकि आपूर्तिकर्ताओं की पर्याप्त आपूर्ति होगी और कुल परिवहन लागत न्यूनतम होगी।

परिवहन योजना के तहत यातायात की मात्रा को समझा जाता है, अर्थात। i-वें आपूर्तिकर्ता से j-वें उपभोक्ता तक परिवहन किए जाने वाले माल की मात्रा। समस्या का गणितीय मॉडल बनाने के लिए, m n चर ij, i= 1,…, n, j= 1,…, m दर्ज करना आवश्यक है, प्रत्येक चर ij बिंदु A से बिंदु Bj तक यातायात की मात्रा को दर्शाता है। चरों का समुच्चय X = (xij) वह योजना होगी जिसे समस्या कथन के आधार पर खोजने की आवश्यकता है।

यह बंद और खुले परिवहन कार्यों (ZTZ) को हल करने के लिए एक शर्त है।

जाहिर है, समस्या 1 को हल करने के लिए, यह आवश्यक है कि कुल मांग आपूर्तिकर्ताओं से उत्पादन की मात्रा से अधिक न हो:

यदि इस असमानता को सख्ती से पूरा किया जाता है, तो समस्या को "खुला" या "असंतुलित" कहा जाता है, यदि समस्या को "बंद" परिवहन समस्या कहा जाता है, और इसका रूप होगा (2):

संतुलन की स्थिति।

यह बंद परिवहन कार्यों (ZTZ) को हल करने के लिए एक शर्त है।

11. परिवहन समस्या को हल करने के लिए एल्गोरिदम।

एल्गोरिथ्म के आवेदन के लिए कई पूर्वापेक्षाओं के अनुपालन की आवश्यकता होती है:

1. उत्पाद की एक इकाई को उत्पादन के प्रत्येक बिंदु से प्रत्येक गंतव्य तक ले जाने की लागत ज्ञात होनी चाहिए।

2. उत्पादन के प्रत्येक बिंदु पर उत्पादों का स्टॉक ज्ञात होना चाहिए।

3. उपभोग के प्रत्येक बिंदु पर भोजन की आवश्यकताओं को जानना चाहिए।

4. कुल आपूर्ति कुल मांग के बराबर होनी चाहिए।

परिवहन समस्या को हल करने के लिए एल्गोरिथ्म में चार चरण होते हैं:

चरण I. मानक तालिका के रूप में डेटा की प्रस्तुति और संसाधनों के किसी भी स्वीकार्य आवंटन की खोज करें। संसाधनों का एक स्वीकार्य वितरण ऐसा है कि यह गंतव्यों पर सभी मांग को पूरा करता है और उत्पादन बिंदुओं से उत्पादों की पूरी आपूर्ति को हटा देता है।

चरण 2. इष्टतमता के लिए प्राप्त संसाधन आवंटन की जाँच करना

चरण 3. यदि संसाधनों का परिणामी वितरण इष्टतम नहीं है, तो संसाधनों का पुनर्वितरण किया जाता है, जिससे परिवहन की लागत कम हो जाती है।

चरण 4. प्राप्त संसाधन आवंटन की इष्टतमता की पुन: जाँच करना।

इष्टतम समाधान प्राप्त होने तक यह पुनरावृत्ति प्रक्रिया दोहराई जाती है।

12. इन्वेंटरी प्रबंधन मॉडल।

इस तथ्य के बावजूद कि किसी भी इन्वेंट्री प्रबंधन मॉडल को दो बुनियादी सवालों (कब और कितना) का जवाब देने के लिए डिज़ाइन किया गया है, ऐसे मॉडलों की एक महत्वपूर्ण संख्या है जो विभिन्न प्रकार के गणितीय उपकरणों का निर्माण करने के लिए उपयोग करते हैं।

इस स्थिति को प्रारंभिक स्थितियों में अंतर से समझाया गया है। इन्वेंट्री प्रबंधन मॉडल को वर्गीकृत करने का मुख्य आधार संग्रहीत उत्पादों की मांग की प्रकृति है (याद रखें कि, अधिक सामान्य उन्नयन के दृष्टिकोण से, अब हम केवल स्वतंत्र मांग वाले मामलों पर विचार कर रहे हैं)।

इसलिए, मांग की प्रकृति के आधार पर, इन्वेंट्री प्रबंधन मॉडल हो सकते हैं

नियतात्मक;

संभाव्य

बदले में, नियतात्मक मांग स्थिर हो सकती है, जब खपत की तीव्रता समय के साथ नहीं बदलती है, या गतिशील होती है, जब विश्वसनीय मांग समय के साथ बदल सकती है।

संभाव्य मांग स्थिर हो सकती है, जब मांग की संभाव्यता घनत्व समय के साथ नहीं बदलती है, और गैर-स्थिर, जहां समय के साथ संभाव्यता घनत्व कार्य बदलता है। उपरोक्त वर्गीकरण को चित्र द्वारा दर्शाया गया है।

उत्पादों के लिए नियतात्मक स्थिर मांग का मामला सबसे सरल है। हालांकि, व्यवहार में इस प्रकार की खपत काफी दुर्लभ है। सबसे जटिल मॉडल गैर-स्थिर प्रकार के मॉडल हैं।

उत्पादों की मांग की प्रकृति के अलावा, इन्वेंट्री प्रबंधन मॉडल का निर्माण करते समय, कई अन्य कारकों को ध्यान में रखा जाना चाहिए, उदाहरण के लिए:

आदेशों के निष्पादन की शर्तें। खरीद अवधि की अवधि स्थिर हो सकती है या यादृच्छिक चर हो सकती है;

पुनःपूर्ति प्रक्रिया। तात्कालिक या समय के साथ वितरित किया जा सकता है;

कार्यशील पूंजी, भंडारण स्थान आदि पर प्रतिबंधों की उपस्थिति।

13. क्यूइंग सिस्टम (क्यूएस) और उनकी प्रभावशीलता के संकेतक।

क्यूइंग सिस्टम (क्यूएस) एक विशेष प्रकार के सिस्टम हैं जो एक ही प्रकार के कार्यों के बार-बार निष्पादन को लागू करते हैं। ऐसी प्रणालियाँ अर्थव्यवस्था, वित्त, उत्पादन और दैनिक जीवन के कई क्षेत्रों में महत्वपूर्ण भूमिका निभाती हैं। वित्तीय और आर्थिक में सीएमओ के उदाहरण के रूप में; क्षेत्र में, विभिन्न प्रकार के बैंक (वाणिज्यिक, निवेश, बंधक, अभिनव, बचत), बीमा संगठन, राज्य संयुक्त स्टॉक कंपनियां, कंपनियां, फर्म, संघ, सहकारी समितियां, कर निरीक्षक, लेखा परीक्षा सेवाएं, विभिन्न संचार प्रणाली (टेलीफोन एक्सचेंज सहित) ), लोडिंग और अनलोडिंग कॉम्प्लेक्स (बंदरगाह, फ्रेट स्टेशन), गैस स्टेशन, सेवा क्षेत्र में विभिन्न उद्यम और संगठन (दुकानें, सूचना डेस्क, हेयरड्रेसर, टिकट कार्यालय, मुद्रा विनिमय कार्यालय, मरम्मत की दुकानें, अस्पताल)। कंप्यूटर नेटवर्क जैसे सिस्टम, सूचना एकत्र करने, भंडारण और प्रसंस्करण के लिए सिस्टम, परिवहन प्रणाली, स्वचालित उत्पादन स्थल, उत्पादन लाइनें, विभिन्न सैन्य प्रणालियां, विशेष रूप से वायु रक्षा या मिसाइल रक्षा प्रणाली, को भी एक प्रकार का क्यूएस माना जा सकता है।

प्रत्येक क्यूएस में इसकी संरचना में एक निश्चित संख्या में सेवा उपकरण शामिल होते हैं, जिन्हें सर्विस चैनल (डिवाइस, लाइन) कहा जाता है। चैनलों की भूमिका विभिन्न उपकरणों द्वारा निभाई जा सकती है, कुछ ऑपरेशन करने वाले व्यक्ति (कैशियर, ऑपरेटर, हेयरड्रेसर, विक्रेता), संचार लाइनें, कार, क्रेन, मरम्मत दल, रेलवे, गैस स्टेशन, आदि।

क्यूइंग सिस्टम सिंगल-चैनल या मल्टी-चैनल हो सकता है।

प्रत्येक क्यूएस को अनुप्रयोगों (आवश्यकताओं) के एक निश्चित प्रवाह की सेवा (निष्पादित) करने के लिए डिज़ाइन किया गया है जो अधिकांश भाग के लिए सिस्टम के इनपुट पर नियमित रूप से नहीं, बल्कि यादृच्छिक समय पर पहुंचते हैं। सर्विसिंग अनुरोध, इस मामले में, एक स्थिर, पूर्व-ज्ञात समय नहीं, बल्कि एक यादृच्छिक समय तक रहता है, जो कई यादृच्छिक, कभी-कभी हमारे लिए अज्ञात, कारणों पर निर्भर करता है। अनुरोध को पूरा करने के बाद, चैनल जारी किया जाता है और अगला अनुरोध प्राप्त करने के लिए तैयार होता है। अनुप्रयोगों के प्रवाह की यादृच्छिक प्रकृति और उनकी सेवा का समय क्यूएस के असमान कार्यभार की ओर जाता है: अन्य समय में, क्यूएस के इनपुट पर असेवित अनुरोध जमा हो सकते हैं, जिससे क्यूएस का अधिभार होता है, और कभी-कभी वहां मुफ्त चैनलों के साथ क्यूएस के इनपुट पर कोई अनुरोध नहीं होगा, जिससे क्यूएस का भार कम हो जाता है, अर्थात। अपने चैनलों को निष्क्रिय करने के लिए। क्यूएस के प्रवेश द्वार पर जमा होने वाले एप्लिकेशन या तो कतार में "मिल जाते हैं", या कतार में आगे रहने की असंभवता के कारण, क्यूएस को छोड़ दिया जाता है।

जोड़ी "क्यूएस - उपभोक्ता" के प्रदर्शन संकेतक, जहां उपभोक्ता को अनुप्रयोगों के पूरे सेट या उनके कुछ स्रोत के रूप में समझा जाता है (उदाहरण के लिए, क्यूएस द्वारा प्रति यूनिट समय की औसत आय, आदि)। संकेतकों का यह समूह उन मामलों में उपयोगी होता है जहां सर्विसिंग अनुरोधों और सेवा लागतों से प्राप्त कुछ आय को समान इकाइयों में मापा जाता है। ये संकेतक आमतौर पर काफी विशिष्ट होते हैं और क्यूएस की बारीकियों, दिए गए अनुरोधों और सेवा अनुशासन द्वारा निर्धारित किए जाते हैं।

14. संभाव्य अवस्थाओं के लिए गतिकी के समीकरण (कोलमोगोरोव के समीकरण)। राज्यों की संभावनाओं को सीमित करें।

कोलमोगोरोव-चैपमैन समीकरण को s = 0 पर s के संबंध में औपचारिक रूप से विभेदित करते हुए, हम प्रत्यक्ष कोलमोगोरोव समीकरण प्राप्त करते हैं:

कोलमोगोरोव-चैपमैन समीकरण को t = 0 पर t के संबंध में औपचारिक रूप से विभेदित करते हुए, हम व्युत्क्रम कोलमोगोरोव समीकरण प्राप्त करते हैं

इस बात पर जोर दिया जाना चाहिए कि अनंत-आयामी रिक्त स्थान के लिए, ऑपरेटर अब आवश्यक रूप से निरंतर नहीं है, और हर जगह परिभाषित नहीं किया जा सकता है, उदाहरण के लिए, वितरण के स्थान में एक अंतर ऑपरेटर होने के लिए।

इस घटना में कि सिस्टम एस के राज्यों की संख्या सीमित है और प्रत्येक राज्य से (एक या दूसरे चरणों के लिए) एक दूसरे राज्य में जाना संभव है, तो राज्यों की सीमा संभावनाएं मौजूद हैं और निर्भर नहीं हैं प्रणाली की प्रारंभिक स्थिति पर।

अंजीर पर। स्थिति को संतुष्ट करने वाले राज्यों और संक्रमणों का एक ग्राफ दिखाता है: किसी भी राज्य से, सिस्टम जल्दी या बाद में किसी अन्य राज्य में जा सकता है। जब चित्र में ग्राफ़ पर तीर 4-3 की दिशा उलट दी जाती है तो शर्त पूरी नहीं होगी।

आइए मान लें कि बताई गई शर्त संतुष्ट है, और इसलिए, सीमांत संभावनाएं मौजूद हैं:

सीमित संभावनाओं को राज्यों की संभावनाओं के समान अक्षरों द्वारा दर्शाया जाएगा, जबकि उनका मतलब संख्या से है, न कि चर (समय के कार्य)।

यह स्पष्ट है कि राज्यों की सीमित संभावनाओं को एकता में जोड़ना चाहिए: नतीजतन, सिस्टम में एक निश्चित सीमित स्थिर मोड स्थापित किया जाता है: सिस्टम को अपने स्वयं के राज्यों को यादृच्छिक रूप से बदलने दें, लेकिन इनमें से प्रत्येक राज्य की संभावना निर्भर नहीं करती है समय और उनमें से प्रत्येक को कुछ निरंतर संभावना के साथ किया जाता है, जो कि औसत सापेक्ष समय है जो सिस्टम इस राज्य में खर्च करता है।

15. मृत्यु और प्रजनन की प्रक्रिया।

निरंतर समय के साथ मृत्यु और प्रजनन की एक मार्कोव प्रक्रिया से हमारा मतलब एक ऐसे एसपी से है जो केवल गैर-ऋणात्मक पूर्णांक मान ले सकता है; इस प्रक्रिया में परिवर्तन किसी भी समय t में हो सकते हैं, जबकि किसी भी समय यह या तो एक से बढ़ सकता है या अपरिवर्तित रह सकता है।

गुणन प्रवाह λi(t) पॉइसन प्रवाह हैं जो फलन X(t) में वृद्धि की ओर ले जाते हैं। तदनुसार, μi(t) मृत्यु प्रवाह हैं जो फलन X(t) में कमी की ओर ले जाते हैं।

आइए हम ग्राफ के अनुसार कोलमोगोरोव समीकरणों की रचना करें:

यदि राज्यों की एक सीमित संख्या वाला धागा:

सीमित संख्या में राज्यों के साथ मृत्यु और प्रजनन की प्रक्रिया के लिए कोलमोगोरोव समीकरणों की प्रणाली का रूप है:

शुद्ध प्रजनन की प्रक्रिया मृत्यु और प्रजनन की एक ऐसी प्रक्रिया है, जिसमें सभी मृत्यु प्रवाह की तीव्रता शून्य के बराबर होती है।

शुद्ध मृत्यु की प्रक्रिया मृत्यु और प्रजनन की एक ऐसी प्रक्रिया है, जिसमें सभी प्रजनन प्रवाह की तीव्रता शून्य के बराबर होती है।

16. विफलताओं के साथ कतारबद्ध प्रणाली.

कतार के सिद्धांत के ढांचे में मानी जाने वाली समस्याओं में से सबसे सरल एकल-चैनल QS का मॉडल है जिसमें विफलताएं या नुकसान होते हैं।

यह ध्यान दिया जाना चाहिए कि इस मामले में चैनलों की संख्या 1 () है। इस चैनल को अनुरोधों का एक पॉइसन प्रवाह प्राप्त होता है, जिसकी तीव्रता के बराबर होती है। समय तीव्रता को प्रभावित करता है:

यदि कोई एप्लिकेशन ऐसे चैनल में आता है जो वर्तमान में मुफ़्त नहीं है, तो उसे अस्वीकार कर दिया जाता है और अब सिस्टम में सूचीबद्ध नहीं है। अनुप्रयोगों को यादृच्छिक समय के दौरान सेवित किया जाता है, जिसका वितरण पैरामीटर के साथ घातीय कानून के अनुसार महसूस किया जाता है:

17. प्रतीक्षा के साथ कतारबद्ध प्रणाली.

एक अनुरोध जो उस समय आता है जब चैनल व्यस्त होता है कतारबद्ध होता है और सेवा की प्रतीक्षा करता है।

एक सीमित कतार लंबाई वाली प्रणाली। आइए पहले मान लें कि कतार में सीटों की संख्या संख्या m द्वारा सीमित है, अर्थात, यदि कोई ग्राहक ऐसे समय में आता है जब कतार में पहले से ही m ग्राहक होते हैं, तो यह सिस्टम को बिना सेवा के छोड़ देता है। भविष्य में, यदि m अनंत तक जाता है, तो हम कतार की लंबाई पर प्रतिबंध के बिना एकल-चैनल QS की विशेषताओं को प्राप्त करेंगे।

हम सिस्टम में अनुरोधों की संख्या के अनुसार क्यूएस राज्यों की संख्या देंगे (सेवा और प्रतीक्षा सेवा दोनों):

- चैनल मुफ़्त है;

— चैनल व्यस्त है, कोई कतार नहीं है;

— चैनल व्यस्त है, एक अनुरोध कतार में है;

— चैनल व्यस्त है, k-1 अनुरोध कतार में हैं;

- चैनल व्यस्त है, ढेरों आवेदन कतार में हैं।

18. संघर्ष की स्थिति में निर्णय लेने के तरीके। मैट्रिक्स गेम्स। शुद्ध और मिश्रित रणनीति खेल।

एक मैट्रिक्स गेम दो खिलाड़ियों का एक शून्य-योग अंतिम गेम है, जिसमें खिलाड़ी 1 का भुगतान मैट्रिक्स के रूप में दिया जाता है (मैट्रिक्स की पंक्ति खिलाड़ी 2 की लागू रणनीति की संख्या से मेल खाती है, कॉलम मेल खाती है खिलाड़ी 2 की लागू रणनीति की संख्या के लिए; मैट्रिक्स की पंक्ति और स्तंभ के चौराहे पर खिलाड़ी 1 का भुगतान है, जो लागू रणनीतियों के लिए प्रासंगिक है)।

मैट्रिक्स गेम के लिए, यह साबित होता है कि उनमें से किसी के पास एक समाधान है और इसे गेम को एक रैखिक प्रोग्रामिंग समस्या को कम करके आसानी से पाया जा सकता है।

दो-खिलाड़ी शून्य-योग मैट्रिक्स गेम को निम्नलिखित सार दो-खिलाड़ी गेम के रूप में देखा जा सकता है।

पहले खिलाड़ी के पास m रणनीतियाँ हैं i = 1,2,...,m, दूसरे के पास n रणनीतियाँ हैं j = 1,2,...,n। रणनीतियों की प्रत्येक जोड़ी (i, j) को एक नंबर aij दिया जाता है, जो खिलाड़ी 2 की कीमत पर खिलाड़ी 1 के भुगतान को व्यक्त करता है, यदि पहला खिलाड़ी अपनी i-th रणनीति को स्वीकार करता है, और 2 - उसकी j-th रणनीति।

प्रत्येक खिलाड़ी एक चाल चलता है: खिलाड़ी 1 अपनी i-th रणनीति (i=), 2 - उसकी j-th रणनीति (j=) चुनता है, जिसके बाद खिलाड़ी 1 खिलाड़ी 2 की कीमत पर अदायगी aij प्राप्त करता है (यदि aij

खिलाड़ी की प्रत्येक रणनीति i=; j = को अक्सर शुद्ध रणनीति कहा जाता है।

परिभाषा। एक खिलाड़ी की मिश्रित रणनीति उसकी शुद्ध रणनीतियों को लागू करने की संभावनाओं का पूरा सेट है।

इस प्रकार, यदि खिलाड़ी 1 में m शुद्ध रणनीतियाँ 1,2,...,m हैं, तो उसकी मिश्रित रणनीति x, संख्याओं का समुच्चय x = (x1,..., xm) है जो संबंधों को संतुष्ट करती है।

xi³ 0 (i= 1,m), =1.

इसी तरह, खिलाड़ी 2 के लिए, जिसकी n शुद्ध रणनीतियाँ हैं, मिश्रित रणनीति y संख्याओं का समुच्चय है

y = (y1, ..., yn), yj 0, (j = 1,n), = 1.

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

शुद्ध रणनीति मिश्रित रणनीति का एक विशेष मामला है। वास्तव में, यदि मिश्रित रणनीति में कोई भी i-th शुद्ध रणनीति संभाव्यता 1 के साथ लागू की जाती है, तो अन्य सभी शुद्ध रणनीतियाँ लागू नहीं होती हैं। और यह i-th शुद्ध रणनीति मिश्रित रणनीति का एक विशेष मामला है। गोपनीयता बनाए रखने के लिए, प्रत्येक खिलाड़ी दूसरे खिलाड़ी की पसंद की परवाह किए बिना अपनी रणनीतियों को लागू करता है।

19. मैट्रिक्स गेम को हल करने के लिए ज्यामितीय विधि।

2xn या nx2 आकार के खेलों का समाधान एक स्पष्ट ज्यामितीय व्याख्या की अनुमति देता है। ऐसे खेलों को ग्राफिक रूप से हल किया जा सकता है।

XY तल पर, भुज के अनुदिश, हम एक खंड A1A2 (चित्र 5.1) को अलग रखते हैं। खंड का प्रत्येक बिंदु कुछ मिश्रित रणनीति U = (u1, u2) से जुड़ा है। इसके अलावा, इस खंड के कुछ मध्यवर्ती बिंदु U से दाईं ओर की दूरी रणनीति A1 चुनने की प्रायिकता u1 है, बाएं छोर की दूरी रणनीति A2 चुनने की प्रायिकता u2 है। बिंदु A1 शुद्ध रणनीति A1 से मेल खाता है, बिंदु A2 शुद्ध रणनीति A2 से मेल खाता है।

बिंदु A1 और A2 पर, हम लंबवत को पुनर्स्थापित करते हैं और उन पर खिलाड़ियों के भुगतान को बंद कर देते हैं। पहले लंबवत (ओए अक्ष के साथ मेल खाते हुए) पर, हम रणनीति ए 1 का उपयोग करते समय खिलाड़ी ए का भुगतान दिखाते हैं, दूसरे पर - रणनीति ए 2 का उपयोग करते समय। यदि खिलाड़ी ए रणनीति ए 1 का उपयोग करता है, तो खिलाड़ी बी की रणनीति बी 1 के साथ उसका भुगतान 2 है, और रणनीति बी 2 के साथ यह 5 है। ओए अक्ष पर नंबर 2 और 5 अंक बी 1 और बी 2 के अनुरूप हैं। इसी तरह, दूसरे लंबवत पर हम अंक बी "1 और बी" 2 (अदायगी 6 और 4) पाते हैं।

कनेक्टिंग पॉइंट बी 1 और बी "1, बी 2 और बी" 2, हमें दो सीधी रेखाएं मिलती हैं, जिससे दूरी ओएक्स अक्ष से संबंधित रणनीतियों के किसी भी संयोजन के लिए औसत भुगतान निर्धारित करती है।

उदाहरण के लिए, खंड B1B"1 के किसी भी बिंदु से अक्ष OX की दूरी खिलाड़ी A की रणनीतियों A1 और A2 (संभावनाओं u1 और u2 के साथ) और खिलाड़ी B की रणनीति B1 के किसी भी संयोजन के लिए खिलाड़ी A का औसत भुगतान निर्धारित करती है।

पॉलीलाइन B1MB"2 से संबंधित बिंदुओं के निर्देशांक खिलाड़ी A की न्यूनतम अदायगी निर्धारित करते हैं जब वह किसी मिश्रित रणनीति का उपयोग करता है। यह न्यूनतम मान बिंदु M पर सबसे बड़ा है, इसलिए, यह बिंदु इष्टतम रणनीति U* = से मेल खाती है। ,), और इसकी कोटि खेल v की कीमत के बराबर है।

हम बिंदु M के निर्देशांक B1B"1 और B2B"2 रेखाओं के प्रतिच्छेदन बिंदु के निर्देशांक के रूप में पाते हैं।

ऐसा करने के लिए, आपको रेखाओं के समीकरणों को जानना होगा। आप दो बिंदुओं से गुजरने वाली एक सीधी रेखा के समीकरण के सूत्र का उपयोग करके ऐसे समीकरण बना सकते हैं:

आइए हम अपनी समस्या के लिए रेखाओं के समीकरणों की रचना करें।

रेखा B1B"1: = या y = 4x + 2।

प्रत्यक्ष B2B "2: = या y = -x + 5।

हमें सिस्टम मिलता है: y = 4x + 2,

आइए इसे हल करें: 4x + 2 = -x + 5,

एक्स = 3/5, वाई = -3/5 + 5 = 22/5।

तो यू = (2/5, 3/5), वी = 22/5।

20. बिमैट्रिक्स गेम्स।

एक बिमैट्रिक्स गेम एक गैर-शून्य योग के साथ दो खिलाड़ियों का एक परिमित खेल है, जिसमें प्रत्येक खिलाड़ी का भुगतान संबंधित खिलाड़ी के लिए अलग-अलग मैट्रिक्स द्वारा दिया जाता है (प्रत्येक मैट्रिक्स में, पंक्ति खिलाड़ी 1 की रणनीति से मेल खाती है, कॉलम खिलाड़ी 2 की रणनीति से मेल खाती है, पहले मैट्रिक्स में पंक्ति और स्तंभ के चौराहे पर खिलाड़ी 1 का भुगतान है, दूसरे मैट्रिक्स में - खिलाड़ी 2 का भुगतान।)

बिमाट्रिक्स खेलों के लिए, खिलाड़ियों के इष्टतम व्यवहार का सिद्धांत भी विकसित किया गया है, लेकिन ऐसे खेलों को हल करना पारंपरिक मैट्रिक्स खेलों की तुलना में अधिक कठिन है।

21. सांख्यिकीय खेल। पूर्ण और आंशिक अनिश्चितता की स्थितियों में निर्णय लेने के सिद्धांत और मानदंड।

संचालन अनुसंधान में, तीन प्रकार की अनिश्चितताओं के बीच अंतर करने की प्रथा है:

लक्ष्यों की अनिश्चितता;

पर्यावरण के बारे में हमारे ज्ञान की अनिश्चितता और इस घटना में काम करने वाले कारक (प्रकृति की अनिश्चितता);

एक सक्रिय या निष्क्रिय साथी या विरोधी के कार्यों की अनिश्चितता।

उपरोक्त वर्गीकरण में, गणितीय मॉडल के एक या दूसरे तत्व के दृष्टिकोण से अनिश्चितताओं के प्रकार पर विचार किया जाता है। इसलिए, उदाहरण के लिए, लक्ष्यों की अनिश्चितता समस्या के निर्माण में या तो व्यक्तिगत मानदंड, या उपयोगी प्रभाव के संपूर्ण वेक्टर के चुनाव में परिलक्षित होती है।

दूसरी ओर, अन्य दो प्रकार की अनिश्चितताएं मुख्य रूप से बाधा समीकरणों और निर्णय पद्धति के उद्देश्य कार्य के निर्माण को प्रभावित करती हैं। बेशक, उपरोक्त कथन बल्कि सशर्त है, जैसा कि वास्तव में, कोई वर्गीकरण है। हम इसे केवल अनिश्चितताओं की कुछ और विशेषताओं को उजागर करने के लिए प्रस्तुत करते हैं जिन्हें निर्णय लेने की प्रक्रिया में ध्यान में रखा जाना चाहिए।

तथ्य यह है कि अनिश्चितताओं के उपरोक्त वर्गीकरण के अलावा, किसी को उनके प्रकार (या "दया") को उनके संबंध के दृष्टिकोण से यादृच्छिकता को ध्यान में रखना चाहिए।

इस आधार पर, कोई स्टोकेस्टिक (संभाव्य) अनिश्चितता के बीच अंतर कर सकता है, जब अज्ञात कारक सांख्यिकीय रूप से स्थिर होते हैं और इसलिए संभाव्यता सिद्धांत की सामान्य वस्तुएं होती हैं - यादृच्छिक चर (या यादृच्छिक कार्य, घटनाएं, आदि)। इस मामले में, समस्या निर्धारित करते समय सभी आवश्यक सांख्यिकीय विशेषताओं (वितरण कानून और उनके पैरामीटर) को ज्ञात या निर्धारित किया जाना चाहिए।

इस तरह के कार्यों का एक उदाहरण हो सकता है, विशेष रूप से, किसी भी प्रकार के उपकरण के रखरखाव और मरम्मत के लिए एक प्रणाली, थिनिंग के आयोजन के लिए एक प्रणाली, आदि।

एक और चरम मामला गैर-स्टोकेस्टिक अनिश्चितता हो सकता है (ई.एस. वेंटजेल के अनुसार - "खराब अनिश्चितता"), जिसमें स्टोकेस्टिक स्थिरता के बारे में कोई धारणा नहीं है। अंत में, हम एक मध्यवर्ती प्रकार की अनिश्चितता के बारे में बात कर सकते हैं, जब यादृच्छिक चर के वितरण के नियमों के बारे में कुछ परिकल्पनाओं के आधार पर निर्णय लिया जाता है। साथ ही, निर्णय लेने वाले को अपने परिणामों और वास्तविक स्थितियों के बीच विसंगति के खतरे को ध्यान में रखना चाहिए। बेमेल के इस जोखिम को जोखिम गुणांक की सहायता से औपचारिक रूप दिया जाता है।

जोखिम निर्णय लेना निम्नलिखित मानदंडों में से एक पर आधारित हो सकता है:

अपेक्षित मूल्य मानदंड;

अपेक्षित मूल्य और विचरण के संयोजन;

ज्ञात सीमा स्तर;

भविष्य में सबसे संभावित घटना।