בתשובה לאלון עמית, 23/05/04 19:53
האם ניתן להסביר לבורים (כמוני, למשל) מה זה P=NP? 223747
גדי אלכסנדרוביץ' • בתשובה לאלון עמית שבת, 5/6/2004, 23:05
תוכל בבקשה להסביר בשורה או שתיים מה זה "תכנון לינארי" או להפנות למקום שמסביר? בפעם האחרונה שנתקלתי בזה, זה היה בהקשר של תורת המשחקים, וגם אז רק שמעתי שמוכיחים איתו משפט (המינימקס של פון-נוימן, אם אני זוכר נכון), לנו הוכיחו את המשפט הזה עם קבוצות קמורות.
האם ניתן להסביר לבורים (כמוני, למשל) מה זה P=NP? 223751
ילדה • בתשובה לגדי אלכסנדרוביץ' שבת, 5/6/2004, 23:22
למיטב ידעתי:

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

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

איפשהו בשנות החמישים בחור בשם ג'ורג' דנציג פיתוח אלגוריתם לפיתרון שלהן למען הצבא הבריטי (אלגוריתם הסימפלקס). אומנם אין לו חסם אסימפטוטי פולינומיאלי, אבל נדמה לי שברוב המיקרים "הישומיים" הוא יעיל מאד ולכן נמצא גם היום בשימוש נרחב (זאת, והעובדה שהוא מאפשר ניתוח רגישות פשוט, עובדה חשובה מאד בעולם האמיתי, כך סיפרו לי), למרות שפותחו אלגוריתמים נוספים ופולינומיאלים לפיתרונן (הסימפלקס הוא אלגוריתם on-boundry - כלומר הולך ומתקרב לאופטימום על פני שפת תחום האילוצים, בעוד שהאלגוריתמים הפולינומיאלים הם in-boundy, ומתקרבים לאופטימום מתוך תחום האילוצים). אני, בכל אופן, נתקלתי רק בסימפלקס (קיימים לו גם ויראציות שונות, אשר יעילות יותר בצורות מיוחדות של בעיות תכנון ליניארי).

ודעה אישית לסיום: כל זה מאד מאד משעמם, אפילו שזה מתמטיקה.
האם ניתן להסביר לבורים (כמוני, למשל) מה זה P=NP? 223779
ערן בילינסקי • בתשובה לילדה יום א', 6/6/2004, 7:41
זיכרון מעורפל מנצנץ במוחי מהקורס בחישוביות וטוען שדווקא נמצא חסם לסימפלקס. (O(n^3 אם אני זוכר נכון.
האם ניתן להסביר לבורים (כמוני, למשל) מה זה P=NP? 223821
האייל האלמוני • בתשובה לערן בילינסקי יום א', 6/6/2004, 9:53
הזכרון מוטעה. ההסבר של הילדה די מדויק (למעט זה שאני לא בטוח שאפשר לתאר את אלגוריתם האליפסואיד כ in-boundary).

יש כל מיני תוצאות חיוביות על הסימפלקס כולל הוכחה שהוא רץ בזמן פולינומי על קלטים שעשו להם פרטרובציה קלה. ראה
שאלת תם 224740
האייל האנונימי • בתשובה לילדה יום ג', 8/6/2004, 23:02
הידע שלי בנושא זעום עד לא קיים, לכן אני מתנצל מראש על טיפשיות השאלה.

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

מן הסתם אני מפספס משהו, ואני מניח שזה קשור לזכרונות הלא ממש מדוייקים שלי משיעורי אינפי. מישהו מוכן להעמיד דברים על דיוקם?
שאלת תם 224756
עוזי וי • בתשובה להאייל האנונימי יום ג', 8/6/2004, 23:59
הכל נכון - רק שמספר הקודקודים של הקומפלקס הוא אקספוננציאלי במספר המשוואות...
שאלת תם 224786
האייל האנונימי • בתשובה לעוזי וי יום ד', 9/6/2004, 8:53
אם יש לי n משוואות, אני לא אמור לקבל מצולע עם (עד) n צלעות?
האם למצולע עם n צלעות אין בדיוק n קודקודים?
אפילו מספר נקודות החיתוך הכולל של n משוואות לינאריות הוא לפי דעתי סדר גודל של n^2.

שוב, אני כנראה מחמיץ משהו בסיסי...
שאלת תם 224790
אלון עמית • בתשובה להאייל האנונימי יום ד', 9/6/2004, 9:14
מימד. אתה מדבר על המישור (שני משתנים), שם הכל באמת קל. כשהמימד גדל, כלומר כשיש הרבה משתנים, מספר הקדקודים, ובאופן כללי הפאות, עשוי להיות גדול מאוד גם אם אין הרבה מדי משוואות.

דוגמה: את הקוביה ה-n ממדית אפשר להגדיר ע"י 2n אי-שוויונים:

0 <= xi <= 1

אבל יש לה שתיים-בחזקת-n קדקודים.
שאלת תם 224832
האייל האנונימי • בתשובה לאלון עמית יום ד', 9/6/2004, 11:22
נפל האסימון.
זה מה שקורה שמנסים להוכיח טענות באמצעות "נראה עבור n=2, ההוכחה הכללית דומה".

תודה רבה על ההבהרה (לך ולעוזי).
תן לי דקה להתרגל אליך שוב 223752
האייל האלמוני והארסי • בתשובה לגדי אלכסנדרוביץ' שבת, 5/6/2004, 23:22
יש לך קישור טוב למשהו שכתוב פשוט ובהיר על כהנמן ומחקר כלשהו שהוא עשה על הרגלי צריכה של סטודנטים?
תן לי דקה להתרגל אליך שוב 223759
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני והארסי יום א', 6/6/2004, 0:26
לא ברור לי למה אתה מניח שדווקא אני אדע דבר כזה. הידע שלי בתורת המשחקים (זו הסיבה?) הוא אפסי, וכולל קורס בסיסי אחד ועוד טיפה, אז אני חושש שאני לא יכול לעזור לך.

אם הצדקת את הכינוי (הקבוע) שלך, וזו הייתה הערה ארסית, פספסתי לגמרי את העוקץ, סליחה.
תן לי דקה להתרגל אליך שוב 223762
האייל האלמוני והארסי • בתשובה לגדי אלכסנדרוביץ' יום א', 6/6/2004, 0:31
שום ארסיות,פשוט חיפשתי עליו ופתאום הופעת עם תורת המשחקים...
בינתיים מצאתי משהו קטן.
האם ניתן להסביר לבורים (כמוני, למשל) מה זה P=NP? 223789
אלון עמית • בתשובה לגדי אלכסנדרוביץ' יום א', 6/6/2004, 9:14
לא נראה לי שיש הרבה מה להוסיף מעבר להסבר של ילדה, אלא אם כן אתה רוצה יותר פרטים טכניים. כדאי להזכיר שבתכנון לינארי יש תופעה חשובה של "דואליות" - לכל בעייה יש בעייה צמודה, ולפעמים הרבה יותר קל לפתור אותה. יש דוגמאות נאות בכל מיני מצבים מעשיים.

הפניות למקומות שמסבירים יש בלי סוף. הנה ספר על הרשת:

הספר הלא אלקטרוני שאני מכיר הוא זה של סחרייבר (Schrijver) ועוד כמה אנשים.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות