کاربردهای LP

برنامه ریزی خطی (Linear Programming): تعدادی قید خطی (نامساوی) داریم و می خواهیم یک تابع خطی از همین متغیرها را مینیمم کنیم. بهترین زمان آن O(n) است.

1-خط تقسیم کننده:

دو مجموعه نقطه با n عضو داده شده است. خطی که آنها را تقسیم می کند پیدا کنید.

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

متغیرها: شیب خط و عرض از مبدا خط (جدا کننده)

تابع هدف: مثلا مینیمم m: چون تعداد خطهای جواب زیاد است، مهم نیست کدام را بدهد، مثلا می گوییم خط با شیب کمتر را بده.

2-برازش خط:

مجموعه n نقطه داده شده است، می خواهیم خطی را پیدا کنیم که فاصله ی عمودی (y) آن با نقاط مینیمم شود.

قید: فاصله عمودی نقاط تا خط (معادله ی خط در x آن نقطه را می نویسیم و منهای y نقطه می کنیم و قدر مطلق می گیریم). این باید بین d و 0 باشد. (برای اینکه خطی شود هر قید را به دو قید تبدیل می کنیم که قدر مطلق را برداریم.)

متغیر: شیب خط و عرض از مبدا خط و d (حداکثر فاصله عمودی یک نقطه تا خط)

تابع هدف: مینیمم کردن d

3- دو دایره هم مرکز پیدا کنید که همی نقاط بین این دو دایره بیفتند و مساحت بین دو دایره مینیمم شود.

تابع هدف: مینیمم کردن مساحت بین دو دایره (مساحت بزرگتر منهای کوچکتر: درجه یک نسبت به توان دو شعاع)

قید: فاصله نقاط تا مرکز دایره بین شعاع دایره بزرگتر و کوچکتر باشد. (هر کدام از این قیدها را به دو قید جدا می کنیم. سپس متغیرها را طوری تعریف می کنیم که خطی شوند.)

متغیرها: R2-x2-y2 و r2-x2-y2 و x و y (مرکز دایره)

4- کوچکترین دایره محیطی

مجموعه n نقطه داده شده است. دایره با کوچکترین شعاع را بیابید که همه ی نقاط را شامل شود.

قید: فاصله هر نقطه تا مرکز دایره (درجه 2)

متغیرها: مرکز دایره و شعاع دایره

تابع هدف: مینیمم کردن شعاع دایره

*خطی نیست اما محدب سه بعدی است.