پاورپوینت هندسه محاسباتی


هندسه محاسباتی

2
بسیاری از اجسام اطراف ما، مانند شکل ماشینها، کاپ های پلاستیکی و … با استفاده از شکل دهی اتوماتیکی ساخته می شوند. کامپیوترها نقش مهمی را هم در فاز طراحی و هم در فاز ساختاربندی ایجاد می کنند، بنابراین امکانات CAD/CAM بخش حیاتی هر کارخانه مدرن می باشد. فاز ساختاربندی در واقع به بیان ساختن یک شئ خاص باتوجه به فاکتورهایی مثل: ماده شئ ای که باید ساخته شود، شکل شئ، اینکه آیا شئ به مقدار زیاد قابل ساختن می باشد یا نه و… می پردازد.
در این فصل به مطالعه منظرهای هندسی ساختن با قالبها، که یک پروسه رایج استفاده شده برای اشیاء فلزی یا پلاستیکی است، پرداخته می شود. برای اشیاء فلزی این پروسه به عنوان ریخته گری بیان می شود.

کار مضاعف همت مضاعف مقدمه

3
شکل 1-4 پروسه ریخته گری را شرح می دهد. فلز مایع داخل یک قالب ریخته می شود، منجمد می گردد و شئ از قالب بیرون می آید. مرحله آخر به همین سادگی انجام نمی شود، ممکن است بدون شکستن قالب شئ بیرون نیاید. ممکن است تنها با چرخاندن قالب شئ بیرون بیاید، وگاهی اشیائی وجود دارند که قالبی برای آنها وجود ندارد، مثل کره. بنابراین در این فصل بر روی وجود یا عدم وجود قالبی برای یک شئ که بتواند از آن خارج شود بحث می گردد.

شکل 1-4

َ
کار مضاعف همت مضاعف مقدمه

4

قرارداد 1: شئ چندوجهی درنظرگرفته می شود.

قرارداد 2: قالبها فقط یک تکه ای درنظر گرفته می شوند.(قالبهای دوتکه ای برای ساخت اشیائی مثل کره مورد استفاده قرار می گیرند.)

قرارداد 3: هر شئ را تنها با یک حرکت می توان از قالب بیرون آورد.(مثلا یک پیچ را نمی توان از قالبش بیرون آورد.) برای این کار حرکت انتقالی مناسب است.

کار مضاعف همت مضاعف مقدمه

5
مسئله: یک شئ با ریخته گری قابل ساخت است یا نه؟
پاسخ اول: باید برای آن یک قالب مناسب بیابیم که از آن خارج شود. شکل حفره داخل قالب توسط شکل شئ معین می شود ولی جهتهای مختلف شئ قالب های متمایزی را ایجاد می کنند، که این انتخاب جهت می تواند سخت باشد، چون در بسیاری از جهتها شئ از قالبش خارج نمی شود، درحالیکه در جهتهای دیگر ممکن است خارج شود.
یک محدودیت روی جهت این است که شئ باید یک top facet افقی داشته باشد. این سطح تنها جایی است که درتماس با قالب نخواهد بود.
پاسخ دوم: شئ قابل ریخته گری است
اگرحداقل از یک جهت با top facet
متناسب با آن جهت قابل بیرون آمدن
از قالبش باشد.

کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری

6
در ادامه بر روی تعیین اینکه ”آیا یک شئ با یک انتقال قابل بیرون آمدن از یک قالب معین می باشد یا نه“ بحث می شود و برای تصمیم گیری روی قابلیت ریخته گری یک شئ ”هر جهت ممکن“ مورد بررسی واقع می شود.
فرض کنید P یک چندوجهی سه بعدی است که با سطوح دو بعدی و یک top facet معین طراحی شده است.(دراینجا نیازی نیست که یک تعریف دقیق از polyhedron ارائه شود.)
قالب یک بلوک مستطیلی با حفره ای دقیقا مطابق P می باشد. وقتی چندوجهی داخل قالب قرار می گیرد، top facet آن باید هم سطح با بالاترین سطح قالب باشد، یعنی قالب هیچ قسمت اضافی که ممکن است مانع خروج شئ شود در سطح بالایی اش ندارد.

کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری

7
کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری
هر سطح P به غیر از top facet سطح ordinary نامیده می شود.
هر سطح ordinary به نام ƒ با یک سطح از قالب به نام ‘ƒ’ متناظر است.
آیا یک بردار جهت وجود دارد که P بتواند بدون برخورد با سطوح داخلی قالب در طول انتقال خارج شود؟ (لغزیدن درطول قالب ایرادی ندارد.)
ازآنجا که تنها سطح بدون تماس با قالب top facet است، جهت خروج باید در جهت مثبت محور zها باشد و این تنها شرط موجود بر روی جهت است.

8
اگر ƒ یک سطح ordinary، P باشد، آنگاه این سطح یا باید از یک طرف سطح متناظر ‘ƒ’ قالب حرکت کند و یا بر روی ‘ƒ’ بلغزد. برای ایجاد این دقت نیاز است به زاویه بین دو بردار در فضای سه بعدی.
زاویه بین دو بردار: دو بردار از یک مبدا درنظر گرفته شده و صفحه گذرنده از آن دو را ساخته، کوچکترین زاویه بین دو بردار زاویه موردنظر است.

شرط لازم روی : زاویه آن با بردار نرمال خارجی هر سطح ordinary،p حداقل 90 باشد.(لم 1-4)
کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری

9
لم 1-4: چندوجهی P می تواند در جهت از قالبش خارج شود، اگر و فقط اگر زاویه حداقل 90 با نرمال خارجی تمام سطوح ordinary، P بسازد.
اثبات: طرف رفت
اگر با نرمال خارجی یکی از سطوح ordinary، Pیعنی زاویه کمتر از 90 بسازد، هنگام انتقال تمام نقاط داخل f با قالب برخورد می کند.

کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری

10
طرف برگشت
فرض خلف: در جایی P با قالب برخورد کند، باید نشان دهیم که یک نرمال خارجی که زاویه کمتر از 90 با می سازد، وجود دارد. فرض کنید p نقطه ای از P است که با یک سطح ‘ƒ’ قالب برخورد کرده است، این بدین معنی است که p نمی تواند به سمت بیرون حرکت کند، پس باید زاویه بزرگتر از 90 با بسازد، در نتیجه با زاویه کمتر از 90 می سازد.

لم 1-4: چندوجهی P می تواند در جهت از قالبش خارج شود، اگر و فقط اگر زاویه حداقل 90 با نرمال خارجی تمام سطوح ordinary، P بسازد.

11
یک نتیجه جالب لم: اگر P را بتوان با دنباله ای از انتقال های کوچک از قالبش بیرون آورد، با یک انتقال هم می توان. پس امکان استفاده بیش از یک انتقال کمکی به حل مسئله نمی کند.
هدف: یافتن بردار با ویژگی بیان شده در لم 1-4.
یک جهت در فضای سه بعدی با یک بردار که
از مبدا مختصات شروع می شود، معین
می گردد. با توجه به مثبت بودن z بردار
این بردارها را به عنوان نقاطی در صفحه z=1 درنظر می گیریم.
نتیجه: هر نقطه در صفحه z=1 مثل (x,y,1)معرف بردار منحصر بفرد(x,y,1) می باشد و برعکس.
کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری

12
سوال: لم 1-4 شرایط لازم و کافی را روی جهت ارائه داد، چگونه این شرایط به صفحه جهت( صفحه z=1) انتقال یابد؟
فرض کنید نرمال خارجی یک سطح ordinary باشد، بردار یک زاویه حداقل 90 با می سازد، اگر و فقط اگر ضرب داخلی و غیرمثبت شود:

این نامساوی توصیف کننده یک نیم صفحه روی صفحه z=1 می باشد که در طرف راست یا چپ یک خط روی این صفحه می باشد.
نکته: این شرط برای سطوح افقی صحیح نمی باشد، چون . درنتیجه یا که همواره برقرار است و شرط بررسی نمی شود و یا که هیچگاه برقرار نیست.

کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری

13
بنابراین هر سطح غیر افقی P معرف یک نیم صفحه روی صفحه z=1 است، که هر نقطه در تقاطع مشترک این نیم صفحه ها معادل بردار جهتی است که با آن می توان شئ را از قالبش درآورد. این تقاطع مشترک می تواند تهی نیز باشد که بدین معنی است که شئ قابل خارج شدن از قالبش نمی باشد.
تبدیل مسئله به یک مسئله هندسی: یافتن یک نقطه در تقاطع مشترک یک مجموعه داده شده از نیم صفحه ها و یا تصمیم گیری اینکه تقاطع تهی است.
اگر چندوجهی موردنظر n سطح داشته باشد، حداکثر n-1 نیم صفحه مورد بحث است.(حداکثر به دلیل عدم حضور سطوح افقی و منهای 1 به دلیل عدم حضور top facet )
کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری

14
از آنجا که گفته شد برای تست قابلیت ریخته گری P باید تمام سطوح به عنوان top facet در نظر گرفته شوند، قضیه زیر بیان می شود.
قضیه 2-4: اگر Pچندوجهی با n سطح باشد در زمان مورد انتظار o(n2) و حافظه مورد نیاز o(n) برای ذخیره سازی می توان تصمیم گرفت که آیا P قابل ریخته گری است یا نه. به علاوه اگر P قابل ریخته گری باشد در زمان مشابهی می توان یک قالب و یک جهت مناسب برای خروج آن یافت.
کار مضاعف همت مضاعف 1-4 هندسه ی ریخته گری

15
فرض کنید که H={h1,h2,..,hn} مجموعه ای از معادلات خطی دومتغیره باشد، که هر معادله به صورت aix+biy ≤ ci است. ci وbi و ai ثابت هستند و bi و ai همزمان نمی توانند صفر باشند.

از لحاظ هندسی یک معادله به عنوان یک نیم صفحه بسته در R2 که با خط aix+biy = ci کراندار شده بیان می شود.

مسئله: یافتن ”تمام“ نقاط R2 (x,y) ∊ که در همه n معادله صدق کند، به عبارت دیگر یافتن تمام نقاط واقع شده در تقاطع مشترک نیم صفحه های H.(در این قسمت مسئله نسبت به قبل کلی تر می شود.)

کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

16
تعیین شکل ناحیه مشترک نیم صفحه ها:
هر نیم صفحه یک ناحیه محدب است واشتراک نواحی محدب نیز محدب است.
هر نقطه روی مرز تقاطع مشترک باید روی مرز یکی ازنیم صفحه ها واقع شود، درنتیجه یالهای سازنده ناحیه مشترک همان خطهای مرزی بعضی از نیم صفحه ها می باشند.
از آنجا که ناحیه تقاطع محدب است، هر خط مرزی یک نیم صفحه می تواند حداکثر سازنده یک یال باشد.
نتیجه: تقاطع مشترک n نیم صفحه یک
چندضلعی محدب است که حداکثر با
n یال محدود شده است.

کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

17

شکل فوق (2-4) چند مورد از این تقاطع ها را نشان می دهد. تقاطع هم می تواند نامحدود باشد(شکل iiو iii)، هم می تواند به صورت یک نقطه یا خط باشد(شکلiv) و هم می تواند تهی باشد(شکل v).
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

18
الگوریتم divide-and-conquer برای یافتن تقاطع مشترک n نیم صفحه ارائه می شود، که بر پایه یک INTERSECTREGIONCONVEX عادی برای محاسبه تقاطع دو ناحیه محدب است.

کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

19
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها
در نتیجه 7-2 دیده شد که نقاط اشتراک دو چندضلعی در زمان o(nlogn+klogn) قابل محاسبه است، که n مجموع تعداد رئوس در دو چندضلعی و k تعداد نقاط اشتراک بین دو ناحیه می باشد. البته در اینجا باید توجه کرد که نواحی مشترک می توانند خط و یا نقطه هم باشند یعنی لزوما چندضلعی نمی باشند.
اگرv نقطه مشترک یال e1 از C1 و یال e2 از C2 باشد، بدون توجه به چگونگی اشتراک e1وe2 ،v باید یک راس c1 ⋂c2 باشد،
و از آنجا که c1 ⋂c2 اشتراک n نیم صفحه است،
حداکثر n یال و n راس دارد. این نتیجه می دهد که
n ≤ k ،پس زمان اجرا برابر است با:o(nlogn).

20
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها
زمان اجرای کل الگوریتم:

بنابراین:

توجه: نواحی ای که در INTERECCONVEXREGIONS از آنها اشتراک گرفته می شود دو بعدی درنظر گرفته می شوند، اگر یکی یا هردوی آنها خط یا نقطه بودند، کار آسانتر می گردد و به عنوان تمرین رها می شود.

21
مشخصات جزئی تر برای معرفی یک چندضلعی محدب C: مرز چپ و راست C به طور جداگانه، که شامل لیست مرتب شده نیم صفحه ها به ترتیبی که وقتی مرز(چپ یا راست) از بالا به پایین طی می شود، اتفاق می افتد. این دو مرز را با Lleft(C) وLright(C) نمایش داده می شود.

رئوس در اینجا مرتب نشده اند که با یافتن
اشتراک خطوط متوالی به دست می آیند.
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

22
برای سادگی توصیف الگوریتم، فرض می شود که یال افقی وجود ندارد.(برای اینکه یالهای افقی نیز موجود باشند، می توان گفت اگر یال مذکور از بالا C را محدود کند متعلق به مرز چپ باشد و یا برعکس.)
الگوریتم جدید، یک الگوریتم sweep صفحه ای است، یک sweep line را روی صفحه به سمت پایین حرکت داده و یالهایی از C1 وC2 که با آن تقاطع دارند نگهداری می شوند.
با توجه به محدب بودن C1 وC2 حداکثر 4 یال متقاطع وجود دارد، پس به جای استفاده از ساختمان داده پیچیده از 4 اشاره گر left_edge_C1 و left_edge_C2 و right_edge_C1 و right_edge_C2 استفاده می شود.(درصورت عدم تقاطع nill)
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

23

شکل 3-4
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

24
سوال: اشاره گرها چگونه مقداردهی اولیه می شوند؟
پاسخ: اگر y1 مولفه بالاترین راس C1 باشد،(اگرC1 یال نامحدودی از بالا داشته باشد،  y1=) وy2 به طور مشابه باشد آنگاه ystart = min(y1,y2). برای محاسبه تقاطع C1 وC2 توجه لازم تنها روی قسمتی از صفحه با مولفه y کمتر یا مساوی ystart است. درنتیجه sweep را از ystart شروع به حرکت داده و مقدار اولیه تمامی اشاره گرها خط y=ystart داده می شود.
سوال: در الگوریتم sweep صفحه ای به صف eventها نیازی است؟
پاسخ: eventها درواقع ابتدا و انتهای یالهای C1 وC2و محل تقاطع آن دو می باشند که با sweep برخورد داشته اند، پس event بعدی که مشخص کننده یال بعدی است که به آن می رسیم، درواقع بالاترین end pointی است که یال آن در sweep قرار دارد، درنتیجه event بعدی را در زمان ثابت با استفاده از 4 اشاره گر موجود می توان به دست آورد و نیازی به صف نمی باشد.(end point با yهای مساوی را از چپ به راست درنظر گرفته و در end pointهایی که روی هم قرار دارند، چپ ترین یال را اول درنظر می گیریم.)
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

25
در هر event point یک سری یال جدید e روی مرز ایجاد می شود، برای کار روی e ابتدا بررسی می شود که اولا e متعلق است به C1 یاC2 و دوما روی مرز چپ قرار دارد یا مرز راست و سپس با توجه به این دو الگوریتم مناسب فراخوانی می شود.
در اینجا الگوریتمی که e بر روی مرز چپ C1 قرار دارد بیان می شود، بقیه به طور مشابه است.
فرض کنیدp بالاترین end point، e است، با سه حالت ممکن e به عنوان یالی از C درنظر گرفته می شود: یا یال با P به عنوان بالاترین end point، یا e∩ left_edge_C2 به عنوان بالاترین end point، یا e ∩ right_edge_C2 به عنوان بالاترین یال، که به صورت زیر بررسی می شود.
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

26
آیا p مابین left_edge_C2 و right_edge_C2 قرار دارد؟ اگر باشد، یال e را با شروع از p در C شرکت می دهیم و سپس نیم صفحه ای را که خط مرزی آن شامل e می شود را به Lleft(C) اضافه می کنیم.

آیا e با right_edge_C2 تقاطع دارد؟ اگر داشت آنگاه نقطه تقاطع یک راس C است و دو حالت ممکن دارد:
1. p سمت راست right_edge_C2 قرار می گیرد، آنگاه نقطه تقاطع شروع یالی است که باید در C قرار گیرد.
2. P سمت چپ right_edge_C2 قرار می گیرد، آنگاه نقطه تقاطع پایان یالی است که باید در C قرار گیرد.

کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

27
در حالت اول نیم صفحه ای که e را تعریف می کند در Lleft(C) قرار داده شده و نیم صفحه ای که right_edge_C2 را تعریف می کند درLright(C) . در حالت دوم هیچ کاری انجام نمی شود، چون این قبلا مورد بررسی قرار گرفته اند و در صورت نیاز وارد لیستها شده اند.

کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

28
آیا e با left_edge_C2 تقاطع دارد؟ اگر داشت، نقطه تقاطع راسی از C است و یال C که با نقطه تقاطع شروع می شود دو حالت ممکن دارد، یا قسمتی از e است یا قسمتی ازleft_edge_C2 که تصمیم گیری بین این دو در زمان ثابت صورت می گیرد. اگر p سمت چپ left_edge_C2 باشد آن یال قسمتی از e است وگرنه قسمتی ازleft_edge_C2. پس با توجه به این دو حالت یا e یا left_edge_C2 به C اضافه شده و نیم صفحه متناظرش به Lleft(C) .

کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

29
سوال: ممکن است هم نیم صفحه متناظر با e و هم نیم صفحه متناظر باleft_edge_C2 به Lleft(C) اضافه شود، به چه ترتیبی این دو به لیست اضافه می شوند؟
پاسخ:left_edge_C2 تنها وقتی اضافه می شود که به عنوان یک یال C با شروع از نقطه تقاطع left_edge_C2و e باشد. برای اضافه کردن صفحه e دو دلیل ممکن است وجود داشته باشد:
یا e به عنوان یال C با شروع در بالاترین end point آن باشد( یعنی همان حالت اول) یا e به عنوان یال C با شروع از تقاطعش با right_edge_C2 باشد، در این صورت e به Lleft(C) اضافه می شود وright_edge_C2 به Lright(C) (طبق حالت دوم) وleft_edge_C2 هم به Lleft(C) (طبق همین حالت سوم). پس در هردو حالت اول باید e اضافه شود بعد left_edge_C2 .
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

30

31

32
نتیجه: برای رسیدن به یک یال زمان ثابت مورد نیاز است.
قضیه 3-4: تقاطع دو ناحیه محدب می تواند در زمان o(n) محاسبه شود.(چون حداکثرn نیم صفحه و درنتیجه n یال داریم.)
صحت الگوریتم منوط به اضافه شدن تمام یالهایC با ترتیب صحیح می باشد: یک یال C و نقطه p به عنوان upper end point آن را فرض کنید. آنگاه p یا upper end point ، یک یال از C1 یا C2 است و یا نقطه تقاطع e از C1 وe’ از C2. در مورد اول وقتی که به p می رسیم یال C هم یافت می شود و در مورد دوم وقتی که به upper end point پایین تری اش رسیدیم، یال اضافه می شود.( با توجه به حالتهای اول و دوم). بنابراین همه نیم صفحه ها اضافه می شوند. اثبات ترتیب مناسب اضافه شدن هم ساده می باشد.
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

33
با توجه به قضیه 3-4 برای الگوریتم INTERSECTHALFPLANE داریم:

نتیجه 4-4: تقاطع مشترک یک مجموعه با n نیم صفحه می تواند در زمان o(nlogn) محاسبه و با o(n) ذخیره شود.
کار مضاعف همت مضاعف 2-4 تقاطع نیم صفحه ها

34
در قسمت قبل تمام نقاط مشترک نیم صفحه ها یافت شد درحالیکه در بسیاری از مسائل از جمله مسئله ریخته گری یافتن یک جواب کافیست، پس احتمالا می توان به دنبال الگوریتم سریعتری بود.
یافتن یک جواب برای یک مجموعه از معادلات، ارتباط نزدیکی با مسئله شناخته شده درoperations research که linear optimization و یا linear programming نامیده می شود، دارد. با این تفاوت که در برنامه خطی جواب خاصی (جوابی که تابع خطی را ماکسیمم می کند.) از مجموعه معادلات مورد نیاز است، یعنی :
Maximize c1x1+ c2x2+…+ cdxd
Subject to a1,1×1+…+ a1,dxd ≤ b1
a2,1×1+…+ a2,dxd ≤ b2
.
.
.
an,1×1+…+ an,dxd ≤ bn

که ai,j وci و bi ثوابتی هستند که ورودی مسئله را شکل می دهند.

کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

35
تابعی که ماکسیمم می شود تابع objective، مجموعه معادلات به همراه تابع obj برنامه خطی و تعداد متغیرهای Lp بعد آن نامیده می شود.
از آنجا که معادلات خطی به عنوان نیم فضاهایی در Rd می باشند، تقاطع این نیم فضاها که در همه معادلات صدق می کند به عنوان ناحیه امکان(feasible) برنامه خطی و نقاط موجود در این ناحیه نقاط امکان و نقاط خارج از این ناحیه نقاط ناممکن(infiseable) نامیده می شوند. اگر نقاط امکان تهی باشد( شکل 2-4 قسمت (v)) Lp ناممکن نامیده می شود.
تابع obj به عنوان یک جهت در فضای بیان شده و ماکسیمم کردن یعنی یافتن نقطه (x1,x2,…,xd) که در جهت بردار ماکسیمم باشد.
در نتیجه حل Lp یعنی یافتن یک نقطه در ناحیه امکان که
در جهت ماکسیمم باشد.
: تابع obj تعریف شده توسط بردار .

کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

36
مسئله: یافتن یک نقطه pR2 که p∩H,و ماکسیمم شود.(
و )
برنامه خطی را با (H, )نمایش می دهیم، و از C برای نمایش ناحیه امکان استفاده می شود. که چهار جواب ممکن دارد.

کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

37
LP ناممکن است هیچ جوابی برای مجموعه معادلات وجود ندارد.
ناحیه امکان بیکران است  یک پرتوی ρ وجود دارد که به طور کامل در ناحیه C قرار می گیرد و تابع مقادیر بزرگ دلخواه در طول ρ می گیرد. در اینجا حل مسئله توصیف اینچنین پرتویی است.
ناحیه C یک یال e دارد که نرمال خارجی آن در جهت است هر نقطه روی e نقطه ایست که را ماکسیمم می کند.
هیچ کدام از سه حالت فوق اتفاق نیفتد  جواب یگانه v وجود دارد، که در جهت ماکسیمم است.

کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

38
برای حل مسئله اولا: فرض می شود که معادلات یکی یکی اضافه شده و جواب هر برنامه خطی میانی، خوش تعریف و یگانه است که این نتیجه می دهد، جواب نهایی نیز یگانه است.(مطابق شکل iv)
بدین منظور دو معادله به LP اضافه می شود، تا برنامه خطی کراندار شود، مثلا اگر cx>0 و cy>0 آنگاه بازای یک MR بزرگ، معادلات px<M و py<M اضافه می شوند.( M باید بزرگ انتخاب شود، تا اثری روی جواب بهینه نداشته باشد.)
درنتیجه دو معادله زیر به مجموعه معادلات اضافه می شود:

کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

39
نکته: m1وm2 تابع هستند ومستقل از نیم صفحه های H و ناحیه امکان C0=m1∩m2 یک زاویه قائمه است.
دوما: برای وجود جواب یگانه در مورد(iii) هم کوچکترین نقطه از لحاظ قاموسی درنظر گرفته می شود، که معادل است با اینکه اندکی چرخانده شود تا با هیچ کدام از نرمال صفحات هم جهت نباشد.(توجه: حتی یک LP محدود ممکن است جواب یگانه قاموسی نداشته باشد(تمرین 11-4) که با وجود m1وm2 ممکن نمی باشد.)

نتیجه: با اعمال این دو قرارداد هر برنامه
خطی جواب یگانه دارد که یک راس ناحیه
ممکن است و راس بهینه نامیده می شود.

کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

40
فرض: (H, ) برنامه خطی مورد نظر،h1,h2,…,hn شماره گذاری صفحات H،Hi i معادله اول به همراه معادلات m1وm2 و Ci ناحیه ممکن آنها  با انتخاب C0 هر ناحیه ممکن Ci یک راس بهینه یگانه vi دارد Hi:={m1, m2, h1,.., hi}
Ci := m1 ∩ m2 ∩ h1∩ …∩ hi
 C1… Cn=C C0 و اگر= Ci  ji Cj=

لم 5-4: (بررسی چگونگی تغییر راس بهینه پس از اضافه شدن hi) اگرn 1i آنگاه داریم:
i) if vi-1 hi  vi= vi-1
ii) if vi-1 hi  Ci=  or vi  li li is the line bounding hi
کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

41
مثال
کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

42
اثبات:
i) اگر vi-1 hi آنگاه با توجه به hi Ci-1∩= Ci و vi-1 Ci-1 در نتیجه vi-1 Ci ، از آنجا که Ci  Ci-1 پس نقطه بهینه Ci نمی تواند بهتر از نقطه بهینه Ci-1 باشد، در نتیجه vi-1 همان راس بهینه Ci می باشد.
ii) vi-1hi، فرض خلف: Ci و vi روی li قرار نگیرد. آنگاه خط vi-1vi را داریم. چون viCi  Ci-1 در نتیجه viCi-1 و با توجه به محدب بودن Ci-1 و اینکه vi-1Ci-1 و خط vi-1vi کاملا داخل Ci-1 است. حال چون vi-1 نقطه بهینه Ci-1 است و تابع obj ، خطی می باشد،
پس در طول خط vi-1vi از vi به vi-1 افزایش می یابد.
حال نقطه تقاطع خط مذکور با li را q درنظر می گیریم.
(q وجود دارد چون: vi-1hi وviCi q  عضو
Ci هم است.) 
و این تناقض است با بهینه بودن vi در ناحیه .Ci
کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

43
لم 5-4 چگونگی یافتن راس جدید را بیان نمی کند.
مسئله: یافتن نقطه p روی li که را تحت محدودیت p  h برای h  Hi-1 ماکسیمم می کند.
برای سادگی فرض می شود liعمودی نیست، آنگاه با مولفه x پارامتری می شود. پس تابع زیر تعریف می شود:

برای هر نیم صفحه h،б(h,li) مولفه x نقطه تقاطع li و خط مرزی h است.(عدم تقاطع: یا هر نقطه روی li در معادله h صدق می کند، که معادله h نادیده گرفته می شود، و یا هیچ نقطه ای از li در h صدق نمی کند که LP ناممکن گزارش می شود.)
کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

44
مسئله: با توجه به اینکه li∩h به چپ کراندار می شود یا به راست مسئله تبدیل می شود به:
Maximize
subject to x  б(h,li) , h  Hi-1 and li∩h is bounded to the left
x  б(h,li) , h  Hi-1 and li∩h is bounded to the right

که یک برنامه خطی یک بعدی می باشد.
کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

45
فرض کنید:
xleft=max hHi{б(h,li): li∩h is bounded to the left}
and
xright=min hHi{б(h,li): li∩h is bounded to the right}

فاصله [xleft:xright] ناحیه ممکن LP یک بعدی است، پس اگرxleft > xright LP, ناممکن و درغیر اینصورت نقطه بهینه نقطه ای روی خط li در نقطه xleftیا xrightمی باشد.(با توجه به تابع obj)

لم 6-4: برنامه خطی یک بعدی در زمان خطی حل می شود.(یافتن ماکسیمم i نیم صفحه) بنابراین آنگاه محاسبه راس بهینه جدید vi (یعنی حالت دوم لم 5-4) و یا تصمیم گیری ناممکن بودن برنامه خطی در زمان o(i) انجام می گیرد.

کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

46
کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

47
لم 7-4: الگوریتم فوق حل یک برنامه خطی کراندار با nمعادله و دو متغیر را در زمان o(n2) و ذخیره خطی محاسبه می کند.
اثبات صحت الگوریتم: با توجه به لم 5-4 هرگاه نیم صفحه جدید hi اضافه می شود، نقطه vi همچنان نقطه بهینه Ci است و اگربرنامه خطی یک بعدی روی li ناممکن باشد، آنگاه Ci تهی است و درنتیجه C=Cn  Ci هم تهی است، پس برنامه خطی ناممکن است.
اثبات زمان اجرا: نیم صفحه ها یکی یکی درn مرحله اضافه می شوند، بیشترین زمان اجرا در خط 6ام سپری می شود، که در مرحله iام برابر o(i) می باشد، پس زمان کل برابر است با:

گرچه الگوریتم ساده و خوب است ولی نسبت به الگوریتم قبل که تمام نقاط را می یافت کندتر است، آیا این تحلیل صحیح می باشد؟؟

کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

48
هزینه هر مرحلهi با o(i) کراندار می شود، اگرvi-1hi.. ولی اگر vi-1hi مرحله i در زمان ثابت انجام می گردد.
راس بهینه حداکثر می تواند n بار تغییر کند ولی اگر ترتیب اضافه شدن صفحات مناسب باشد، این مقدار کاهش می یابد.

شکل روبرو نشان می دهد که زمان اجرا
در بدترین حالت o(n2) می باشد.
کار مضاعف همت مضاعف 3-4 برنامه های خطی توسعه یافته

49
سوال: پس می توان نیم صفحه ها را به ترتیبی اضافه کرد که اصلا vi تغییری نکند تا زمان اجرا خطی شود. اینکه برای هر مجموعه از نیم صفحه ها یک ترتیب مناسب وجود دارد صحیح است ولی آیا یافتن این ترتیب ممکن و یا مقرون به صرفه است؟
پاسخ: چون این ترتیب باید قبل از شروع الگوریتم که هنوز هیچ از تقاطع نیم صفحه ها در دست نیست موجود باشد یافتن ترتیب مناسب ساده نیست. که در اینجا یک ترتیب تصادفی از H را برمی داریم.
درالگوریتم تصادفی از تابع RANDOM(k) استفاده می شود که در زمان ثابت یک عدد تصادفی بین 1 تا k را می دهد.
زمان اجرا وابسته به انتخاب تصادفی ساخته شده در الگوریتم میباشد.

کار مضاعف همت مضاعف 4-4 برنامه خطی تصادفی

50
کار مضاعف همت مضاعف 4-4 برنامه خطی تصادفی

51

تعداد حالات مختلف n! است که هرکدام زمان خاص اجرای خود را دارد. حال چون هرکدام از این زمان های اجرا احتمال یکسانی دارند، زمان اجرای مورد انتظار الگوریتم که متوسط تمام n! حالت مختلف زمان اجراست، مورد بررسی قرار می گیرد.
یادآوری: امید ریاضی و یا میانگین متغیر تصادفی

f(x): تابع چگالی احتمال
کار مضاعف همت مضاعف 4-4 برنامه خطی تصادفی

52
لم 8-4: مسئله برنامه نویسی خطی دوبعدی با n معادله در زمان مورد انتظار o(n) و ذخیره سازی خطی حل می شود.
اثبات: زمان اجرای RANDOMPERMUTATION برابراست با o(n). برای اضافه کردن صفحات، متغیر تصادفی Xi را بدین صورت تعریف می کنیم:

پس زمان سپری شده برای n صفحه در خط 6 برابر است با:

با توجه بودن به خطی بودن امید ریاضی:

کار مضاعف همت مضاعف 4-4 برنامه خطی تصادفی

53
سوال: E(Xi) چیست؟
پاسخ: احتمال اینکه vi-1hi، یعنی احتمال اینکه نقطه بهینه در این مرحله تغییر کند. برای تحلیل این احتمال از روند BackwardsAnalysis استفاده می شود، یعنی فرض می شود که الگوریتم انجام گرفته و راس بهینه vn بدست آمده، حال صفحه hn را حذف می کنیم،
با چه احتمالی نقطه بهینه تغییر می کند؟

از آنجا که vn راس Cn می باشد،
حداقل توسط دو تا از نیم صفحه ها تعریف می شوند
و وقتی vn تغییر می کند که راسی از Cn-1 نباشد، یعنی hn یکی از نیم صفحه هایی است که vn را تعریف می کند. و از آنجا که نیم صفحه ها به طور تصادفی اضافه شده اند، احتمال اینکه hn یکی از نیم صفحه های تعریف کننده vn باشد حداکثر 2/n می باشد.
کار مضاعف همت مضاعف 4-4 برنامه خطی تصادفی

54
سوال: چرا حداکثر2/n ؟
پاسخ: اولا اگر vn تعریف کننده بیش از دو یال باشد، آنگاه حذف hn ممکن است باعث تغییر vn نشود، چون ممکن است vn بعد از حذف hn باز هم راس باشد. دوما علاوه بر n معادله،
m1 و m2 هم می توانند در ساختن vn دخالت داشته
باشند،که این هم احتمال را از 2/n کمتر می کند.

ادامه پاسخ: حال اگر همین روند Backwards برای i معادله اول H درنظر گرفته شود، باز هم داریم:
E(xi)  2/ i
در نتیجه زمان کل مورد انتظار برای حل تمام برنامه های خطی دو بعدی برابر است با: (o(i).2/ i) = o(n)
کار مضاعف همت مضاعف 4-4 برنامه خطی تصادفی

55
در قسمت قبل برنامه خطی نامحدود را با اعمال دو محدودیت اضافی کراندار کردیم، اما این همیشه ممکن نیست و حتی گاهی برنامه خطی محدود می شود ولی کران یا همان مرز ناحیه ممکن بسیار بزرگ می شود به گونه ای که قابل شناخت نیست.
مسئله اول**: چگونگی تشخیص غیرکرانداری برنامه خطی (H, )؟
لم 9-4: یک برنامه خطی (H, ) غیرکراندار است اگر و فقط اگریک بردار وجود داشته باشد بطوریکه و برای تمام hH و برنامه خطی (H’, ) ممکن می باشد اگر
کار مضاعف همت مضاعف 5-4 برنامه خطی غیر کراندار

56
اثبات:
طرف رفت: قبلا گفته شد که بیکران بودن C به معنی وجود پرتوی ρ به گونه ایست که کامل در ناحیه ممکن قرار بگیرد و تابع obj در طول ρ مقادیر بزرگ دلخواه بگیرد.
p: نقطه شروع ρ، : بردار جهت آن ρ={p+λ : λ>0 } 
تابع obj در طول ρ مقادیر بزرگ می گیرد اگرو فقط اگر . از طرف دیگر اگر بردار نرمال نیم صفحه h به سمت ناحیه ممکن باشد، آنگاه داریم:
کار مضاعف همت مضاعف 5-4 برنامه خطی غیر کراندار

57
طرف برگشت: برنامه خطی (H, ) و بردار با شرایط داده شده در لم مفروض است.چون (H’, )ممکن است پس نقطه p0hH’h وجود دارد. فرض کنید پرتوی ρ0:={p0+ λ : λ >0} ،از آنجا که برایh  H’، پرتوی ρ0 به طور کامل در هر کدام از صفحات H’ قرار می گیرد. بنابراین از آنجا که تابع obj در طول ρ0 مقادیر بزرگ دلخواه می گیرد.
برای هرنیم صفحه h  HH’ ، داریم که نتیجه می دهد پارامتر λhی وجود دارد، که برای تمام λh =<λ p0+ λ  h. با فرضλh λ’ :=maxh  HH’ و λ’ P:=P0+ پرتوی ρ0 به طور کامل در هر کدام از صفحات عضو H قرار می گیرد. درنتیجه (H, ) بیکران است.

کار مضاعف همت مضاعف 5-4 برنامه خطی غیر کراندار

58
پایان