למ נהל עבודה 6 מועמדים לעבודה . הוא רוצה לחלקם בין 4 מחלקות במפעלו , על מנת למקסם את האפקטיביות שלהם . אין הוא יכול להקצות עובד אחד ליותר מאשר מחלקה אחת , אולם הוא מסכים לא להקצות אף עובד לאחת המחלקות באם הוא יכול לתרום יותר במחלקה אחרת . הטבלה הבאה מציגה את הגידול האפקטיבי במספר המוצרים בכל מחלקה , בהתאם למספר הפועלים הנוספים המוקצים לה . מצא את מספר הפועלים , שיש להקצות לכל מחלקה , על מנת למקסם את הגידול בסה"כ המוצרים במפעל כולו . פתרון הבעיה - . נגדיר את הגורמים הנדרסים לפתרון בעיה בתכנות דינמי : שלב וו בתכנון - הקצאת עובדים למחלקה . 5-n דהיינו , שלב ו יהיה הקצאת עובדים למחלקה הרביעית , וכך הלאה . מצב isvn - s העובדים שנותרו להקצאה . משתנה החלטה - ^ מספר העובדים המוקצים בשלב וו , דהיינו למחלקה וו . 5- " ^ התיעלת ( מספר מוצרים נוסף ) המתקבלת 5-n ^ n ^ מהקצאת X פועלים בשלב התכנון ה י-ח- למחלקה וו . 5- 0 s ) = Max - ^> X = 0 , 1 ,..., s n
אל הספר