מהי שיטת העלות המינימלית?

ה שיטת העלות הנמוכה ביותר הוא אלגוריתם שמטרתו לפתח פתרון בעיות הקשורות ל- תחבורה או הפצה המשליכים תוצאות טובות יותר משיטות אחרות, כמו הפינה צְפוֹן מִזרָח. הסיבה לכך היא שניתן להתמקד בכמה מסלולים קטנים יותר, אשר בתורם יש להם עלויות נמוכות יותר.

ה תרשים זרימה מסוג זה של אלגוריתם, זה בדרך כלל הרבה יותר פשוט מאחרים, מכיוון שהוא פשוט קשור להקצאת כל כמויות היחידות האפשריות הכפופים לכל מגבלות הביקוש וההיצע, כלומר לכל תאי העלות הנמוכים ביותר של המטריצה ​​כולה עד סוף התקופה. שיטה.

כל זה אומר, שזה שיטת העלות הנמוכה ביותר, בפשטות מחפש דרך לאתר את הפתרון הראשוני הטוב ביותר של מודל התחבורה, באמצעות המסלולים הזולים ביותר.

מאפייני שיטת העלות המינימלית

בין המאפיינים הרלוונטיים ביותר של שיטה חשובה זו הם:

• זו שיטה שיכולה להצליח כאשר היא מפותחת היטב.
• ברור לך לגבי העלויות בעת ביצוע מטלות.
• זה נשאר בעיקר בצד הפיתרון האופטימלי.
• חשוב להתחיל לפתור אותו עבור התאים הריקים.
• מספר התאים צריך להיות שווה ל- m + n-1.
• יש לצייר קווים רק אופקית ואנכית.
• ניתן לצייר קווים דרך תאים מלאים או ריקים ללא שימוש.
• התפתחותו חייבת להתחיל בתא ריק וכשעוברים בתאים מלאים, חשוב שהוא יסתיים בתא הריק בו החל התהליך.
• במקרה שאחד ממדדי השיפור מניב תוצאה שלילית, יש לקחת את המספר הקטן ביותר של התא עם סימן שלילי. בתורו, יש להוסיף ערך זה לכל התאים המכילים סימן חיובי והוא יופחת גם מתאים שיש להם סימנים שליליות. באופן זה ייווצרו המטלות החדשות.
• אם שיעורי השיפור מספקים אפס כתוצאה או מספר שהוא חיובי, התרגיל מסתיים ומספק תוצאה אופטימלית.

אלגוריתם לפתרון שיטת העלות המינימלית

ה שיטת העלות הנמוכה ביותר ניתן ליישם אותה כדי להקים תוכנית תחבורה מהימנה עבור סחורה מסוימת המגיעה ממקורות שונים ליעדים שונים בעלות מינימלית. כדי לבצע זאת, יש לבצע את הצעדים הבאים:

שלב 1

נבחר הנתיב או התא בעלות הנמוכה ביותר של המטריצה ​​ויש לציין את מספר היחידות הגדול ביותר האפשרי. ניתן להגביל סכום זה עקב הגבלות ביקוש והיצע.

בשלב ראשון זה אנו ממשיכים להצדיק את ההיצע והביקוש שנמצאים בשורה ובעמודה המושפעת. זה מוצדק על ידי חיסור הסכום המוקצה לתא.

שלב 2

במהלך התהליך של שלב שני זה, יש לבטל את השורה או היעד שבו ההיצע או הביקוש הם 0 לאחר שלב 1, אם קורה שהמקרה שניים נמצאים ב 0, עליכם לבחור באופן שרירותי, איזה מהם עליכם לחסל ואת זה שנותר מחסר, עליכם להשאיר את הביקוש וההיצע על 0, תלוי ב מקרה.

שלב 3

כאשר מגיעים לשלב השלישי הזה, ניתן להציג שתי אפשרויות שהן:

• השאירו רק עמודה או שורה אחת, אם זה קורה יש לעצור אותה מכיוון שהשיטה הושלמה.
• באפשרות השנייה, אם נותרו יותר מעמודה או שורה אחת, יש צורך להתחיל מחדש בשלב 1.

יתרונות שיטת העלות המינימלית

• מספקים במהירות פתרונות טובים יותר.
• הוא מניח בניתוחו, הבדלים בין עלויות ההובלה הנמוכות יותר.
• זו שיטה משוחדת ומדויקת לחלוטין.
• נבחרים האתרים המייצרים את עלויות ההובלה הנמוכות ביותר שקשורים לחומר הגלם ולמוצר המוגמר.
• זה פשוט מאוד וקל ליישום, מכיוון שהוא לוקח בחשבון את ניתוח עלויות ההובלה.

חסרונות שיטת העלות המינימלית

• אין ביכולתו לספק שום סוג של קריטריון המאפשר לקבוע אם הפתרון המתקבל בשיטה זו הוא האופטימלי ביותר או לא.
• מספר הבקשות וההצעות זהים תמיד, מכיוון שהם אינם משתנים לאורך זמן.
• הוא אינו מחשיב סוגים אחרים של השפעות לאיתור, אלא רק את עלויות ההובלה.
• אתה יכול להשיג תוצאות שונות, בהתאם לקריטריונים איתם אתה מתחיל לעבוד, במקרה שהוקצה עמודה אחת בלבד.

חשיבותה של שיטת העלות המינימלית

בשיטה זו בניגוד לאלגוריתמים אחרים המקצים עלויות משלוח והובלה, במצבים ביקוש והיצע, זה הרבה יותר יעיל ורב-תכליתי משיטות הפצה שונות של עלויות. זה בדרך כלל הרבה יותר פשוט, מכיוון שהוא רק מבקש לייעד מספר גדול יותר של יחידות.

בשל החיפוש אחר פתרונות שיטה זו זוכה לחשיבות רבה מכיוון שיש לה את היכולת להציע את הפתרונות הטובים ביותר לבעיות.