Recent Forum Posts
From categories:
page 1123...next »

הי,

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

תודה!

ex5 q8
yota1234yota1234 24 May 2019 20:24
in discussion Discussions / Q&A, Spring 2019 » ex5 q8

שלום,
בתרגול "LP1" בתרגיל 3, נוסחה בעיית תכנות לינארי אבל בצורה לא סטנדרטית:
פוקנציית המטרה אינה מכילה משתנים כלל, אלא "T", שהינו חלק מהאילוצים שנכתבו פר w(e).
מדוע זהו פתרון לגיטימי או במילים אחרות מדוע הפתרון כפי שנכתב הוא בכלל linear program? זה לא עונה על הדרישות הבסיסיות של הגדרה פורמלית של תוכנית לינארית.

(השאלה נשאלת כיוון שבתרגיל 8 בש"ב אנו מתבקשים לכתוב לבעיה זו את התוכנית הדואלית, אך לעניות דעתי הפרימלית לא מוגדרת היטב)

ex5 q8 by yota1234yota1234, 24 May 2019 20:24

תודה!

Re: תרגיל 7 by omercomerc, 24 May 2019 14:49

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

Re: תרגיל 7 by tal_yanktal_yank, 24 May 2019 08:09

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

היי להב,
לעיתים מגדירים את R+ כממשיים חיוביים ולעיתים מגדירים את R+ כממשיים אי-שליליים, כאן הכוונה לשני.
טל

Re: תרגיל 5 שאלה 7א by tal_yanktal_yank, 24 May 2019 07:47
תרגיל 7
omercomerc 23 May 2019 17:42
in discussion Discussions / Q&A, Spring 2019 » תרגיל 7

בתרגיל 7 אנו מתבקשים לכתוב תוכנית לינארית ולמצוא את הבעיה הדואלית שלה.
התוכנית הלינארית המקורית שמתבקשים לכתוב אינה בצורה הסטנדרטית (נדרש מציאת מינימום ולא מקסימום).
האם הבעיה הדואלית מוגדרת רק עבור תוכנית לינארית בצורה הסטנדרטית, או שניתן באופן כללי לבצע שחלוף למטריצת האילוצים\מטרה גם עבור תוכנית לא סטנדרטית, על מנת לשמר את המבנה הקריא של הבעיה?
(כמובן שניתן בקלות לעבור מהבעיה הדואלית של הצורה הסטנדרטית לצורה קריאה, השאלה אם מעברי הביניים נדרשים, או שניתן לעבור ישירות בין בעיות שקל להבין את הבעיה שעולה מהן).

תרגיל 7 by omercomerc, 23 May 2019 17:42

שלום
האם צריכים לספק הוכחה כי התוכנית הלינארית שמצאנו בשאלה 2 וכו' היא נכונה ואכן פותרת את הבעיה המקורית?

או רק לספק הגדרה פורמלית של הבעיה בצורת LP ?

מתקיים

(1)
\begin{align} R^+ = \left \{ x \in R \mid x > 0 \right \} \end{align}

ועל כן נובע שיש אילוצי $x_i > 0$, אך אלו לא אילוצים חוקיים ב LP.

האם אני מפספס משהו, או שהכוונה היא שהפונקציה $f$ יכולה למפות גם ל 0?

תודה.

תרגיל 5 שאלה 7א by LahavLahav, 22 May 2019 16:41

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

שלום לכולם,
השבוע נקיים תירגולי השלמה בנושא APSP.
לנוחיותכם, מוצעים שלושה מועדים, שאפשר להגיע לכל אחד מהם, להלן:
יום שלישי 21.05 15:00 שנקר 204
יום שלישי 21.05 19:00 שנקר 204
יום שישי 24.05 11:00 אורנשטיין 102

שבוע טוב.

Re: תרגיל 5 שאלה 2 by tal_yanktal_yank, 18 May 2019 18:10

לגבי השאלה הראשונה ששאלת, אפשר לפתור את כל הסעיפים בתרגיל שלא מופיעה בהם המילה "דואלית" להטיותיה.
בפרט לגבי שאלה 2, אפשר לכתוב תוכנית לינארית מתאימה.

Re: Assignment5 Q2 by tal_yanktal_yank, 18 May 2019 18:09

אולי התכוונת חיובי במקום שלילי?
בוחרים במשתנה הבסיסי שמתאים לאילוץ שמגביל ביותר את ערך המשתנה הלא בסיסי, ואילוץ שבו המקדם הוא חיובי לא מגביל כלל.

האם אפשר להניח

(1)
\begin{align} \forall_{i=1..m} s_i \neq ti \end{align}

?

תרגיל 5 שאלה 2 by LahavLahav, 18 May 2019 16:30

(בשאלה 2 בתרגיל 5, יש מצב שבו אנחנו צריכים שכמות מסוימת של מחצב שהתחילה את דרכה למפעל, תמשיך כל הזמן על הקשתות עם אותה כמות, לא ברור לי איך אנחנו אמורים לעשות כזה דבר, האם למדנו איך להתחשב באילוץ מסוג זה?)

Assignment5 Q2 by tomer_htomer_h, 17 May 2019 12:58

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

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

אשמח לוודא שמה שכתבתי באמת נכון וככה עובד האלגוריתם.

תודה

הבנתי, תודה רבה.

Re: תרגיל 4 שאלה 7 by Thorson22Thorson22, 14 May 2019 07:57

היי,
במקרה הזה אפשר (וכדאי) יותר טוב.
טל

Re: תרגיל 4 שאלה 7 by tal_yanktal_yank, 14 May 2019 06:59

היי,
האם פיתרון בסיבוכיות $O(V^3)$ יתקבל?

תודה

תרגיל 4 שאלה 7 by Thorson22Thorson22, 13 May 2019 11:12
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License