לגבי הגרסה המלאה:
אני מצליח להוכיח חלקית שאם הראשון מתקיים אז השני לא, אבל לא ממש את הכיוון השני
לגבי הכיוון הראשון בקיצור:
אם נעביר את הבעיה הפרימלית לצורת slack אפשר לראות שהפתרון האופטימלי הוא וקטור ה-0
ואז D היא או פיזבילית או לא
אם היא כן אז בהכרח יש לה אותו פתרון אופטימלי וזה שולל את 2
אם היא לא אז לא בטוח איך לשלול
בבקשה לצרף את השאלה - זה פורום, ואם רוצים שאנשים יהיו מסוגלים לענות על השאלה, עדיף לא לשלוח אותם לחפש אותה.
אז כשהשאלה תצורף אני אסתכל, וכמובן שאני מזמין גם אחרים.
בנוסף, אני אומר מראש שכלל לא הבנתי את מה שכתבת כ"כיוון הראשון" - כדאי להשקיע בלהיות יותר ברורים אם רוצים לקבל תשובה ברורה.
זאת השאלה:
לגבי פתרון הגרסה המלאה.
אפשר לתרגם את נתוני השאלה לתוכנית לינארית ואז לעשות את הדואלית שלה:
אני חושב שהדרך לפתור היא להעביר לצורת slack ואז אפשר לראות שאם 1 מתקיים אז וקטור ה-0 הוא הפתרון האופטימלי
במקרה כזה, D חסומה והיא או פיזבילית או לא
אם היא פיזבילית אז מדואליות חזקה בהכרח יש לה את אותו פתרון אופטימלי וזה שולל את 2
אם היא לא פיזבילית אני לא בטוח איך ממשיכים
ולגבי המקרה השני - להראות שכש-2 מתקיים 1 לא אני גם לא בטוח איך
שלום,
למה וקטור ה-0 הוא פתרון? ערכו אופטימלי, אבל האם הוא בהכרח עומד באילוץ של P?
בכל מקרה אין בכך צורך.
אם 1 מתקיים, אז P פיזיבילית, ומהגדרת פונ' המטרה כאן קל לראות שהיא גם בהכרח חסומה.
לכן גם D פיזיבילית וחסומה (דואליות חזקה). וזה כבר אומר ש-2 לא יכול להתקיים, כפי שנכתב.
אם 2 מתקיים, אז D בהכרח לא חסומה (לחשוב מדוע), ולכן 1 בהכרח לא פיזיבילית (שוב, אם הייתה פיזיבילית אז בגלל שהיא גם חסומה, אז גם D הייתה פיזיבילית וחסומה).
לגבי השאלה בגרסה החזקה יותר, זה מאוד דומה. מה תהיה הבעיה P במקרה הזה? מה תהיה הדואלית? כדאי לנסות…
התייחסתי במקור לגרסה החזקה (בשאלה נקראת מלאה) אבל יש לי 2 שאלות קודם על מה שכתבת:
1. מוודא משהו שכנראה לא הבנתי - מסקנה מדואליות חזקה היא שאם אחת הבעיות פיזבילית וחסומה אז בהכרח גם השנייה פיזבילית וחסומה? לא ייתכן מצב שאחת פיזבילית וחסומה והשנייה לא פיזבילית?
2. לגבי מה שהדגשת- האם הנימוק הוא - אם 2 מתקיים אז D פיזבילית וקיים לה פתרון אפשרי קטן מאפס. אז אם היא גם חסומה אז גם P ככה והפתרון האופטימלי של שתיהן שווה והוא קטן מאפס. אבל פונק' המטרה של P לא יכולה להיות קטנה מאפס בשום השמה. לכן בהכרח D לא חסומה ואז P לא פיזבילית ו-1 לא מתקיים
לגבי הגרסה החזקה/מלאה:האם זה נכון?
ואז הנימוקים זהים לאלו של הגרסה הפשוטה
1. זאת מסקנה מאיך שהוכחנו את משפט הדואליות החזקה (הוכחה בבת-אחת עם הנכונות של אלג' סימפלקס).
2. כן, זה נימוק אחד אפשרי ונכון. אפשרות אחרת היא לשים לב שאם יש ל-D פתרון y שערכו קטן מ-0 אז תמיד נוכל לקחת למשל את הוקטור 2y כדי לקבל פתרון אפילו קטן יותר, וכך הלאה.
וכן, זה נראה נכון.