عنوان پایان‌نامه
ارزیابی نتایج سختی بیشینه کردن سود در مسائل قیمت گذاری
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 77..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 68486
- تاریخ دفاع
- ۰۸ بهمن ۱۳۹۳
- دانشجو
- نیلوفر وحدت
- استاد راهنما
- دارا معظمی
- چکیده
- مسائل قیمت گذاری ، دسته¬ای از مسائل اقتصادی می¬باشد که در آن¬ها، تعدادی مشتری و مجموعه¬ای از کالاها داریم و هر مشتری، مقداری بودجه و لیستی از کالاهایی دارد که مورد نیازش می¬باشد و می¬بایست خریداری کند. حال هر مشتری، با توجه به بودجه¬ای که دارد به خرید کالا¬های مورد نیاز از لیست خریدش، می¬پردازد. بر همین اساس این مسائل به دو دسته مسائل "یو دی پی" و "اس ام پی"، تقسیم می¬شوند و هدف در این مسائل، تنظیم قیمت کالا¬ها به گونه¬ای است که سود (درآمد کلی فروشگاه)، ماکسیمم شود. 1) مسائل قیمت گذاری خرید ارزان تک تقاضا (یو دی پی) : در این دسته از مسائل هر مشتری، بر اساس میزان بودجه-ای که دارد، ارزانترین کالای لیست خود را می¬خرد و اگر بودجه¬اش نرسد هیچ کدام از کالا¬های لیستش را نمی¬خرد. 2) مسائل قیمت گذاری تک هدفی (اس ام پی) : در این دسته از مسائل یا هر مشتری، بودجه¬اش می¬رسد و کل کالاهای لیستش را می¬خرد، یا بودجه¬اش نمی¬رسد و هیچ یک از کالا¬های لیستش را نمی¬خرد. در این رساله، ابتدا اطلاعاتی راجع به کارهای صورت گرفته¬ی قبلی در زمینه¬ی پیدا کردن ضریب تقریبی در سه حالت مختلف برای مسئله¬ی "یو دی پی"¬، پرداخته می¬شود و سپس سه ضریب تقریبی جدید، برای این سه حالت مسئله ی "یو دی پی" ارائه خواهد شد.
- Abstract
- Pricing problems are as economic problems cases, where we are given a set of customers and a set of items. Each customer is associated with a subset of items of interest (customer list), with a defined budget, and each customer buys the items he needs based on his budget. Therefore the goal of these kinds of problems is to set the item prices so as to maximize the total profit. There are two groups based on customer list: 1) Unit-Demand min-buying Pricing (UDP): in this problem, each customer buys the cheapest item of his list, if the price of the item is no higher than the budget, and buys nothing otherwise. 2) Single-Minded Pricing (SMP): in this problem, either each customer buys the whole set of his customer list if its total price is at most the budget, or buys nothing otherwise. In this thesis, it will be tried to give a brief explanation about the history of finding approximation factor in three cases of UDP problem, and then show three new approximation factors of these cases.
