پرش به محتویات

برنامه‌ریزی خطی با پایتون

نصب ماژول‌های پایتون 
pip install numpy scipy

بازاریابی

مثال انتخاب رسانه

یک شرکت ساخت و ساز در حال توسعه یک مجتمع کنار دریاچه خصوصی است. بازار هدف، خانواده‌های با درآمد متوسط و بالا در فاصله حدود ۱۰۰ مایلی است.

برای طراحی کمپین تبلیغاتی، شرکت BP&J استخدام شد. آن‌ها پیشنهاد کردند که در ماه اول تبلیغات محدود به پنج رسانه باشد و پس از یک ماه، استراتژی بر اساس نتایج بازبینی شود. BP&J داده‌هایی درباره تعداد مشتریان قابل دسترسی، هزینه هر تبلیغ، حداکثر دفعات استفاده و کیفیت نمایش هر رسانه جمع‌آوری کرد. کیفیت نمایش با واحدی سنجیده می‌شود که ارزش نسبی یک تبلیغ را نشان می‌دهد و عواملی مثل مشخصات جمعیتی مخاطبان، تصویر ارائه‌شده و کیفیت تبلیغ را در نظر می‌گیرد. بودجه ماه اول ۳۰,۰۰۰ دلار است و محدودیت‌ها شامل: حداقل ۱۰ تبلیغ تلویزیونی، حداقل پوشش ۵۰,۰۰۰ مشتری بالقوه و حداکثر هزینه ۱۸,۰۰۰ دلار برای تلویزیون است. چه برنامه‌ای برای انتخاب رسانه‌های تبلیغاتی توصیه می‌نمایید؟

تصمیمی که باید گرفته شود، تعداد دفعات استفاده از هر رسانه است. برای شروع، ابتدا متغیرهای تصمیم‌گیری را تعریف می‌کنیم:

  • \(DTV\): تعداد دفعات استفاده از تبلیغ در تلویزیون روز
  • \(ETV\): تعداد دفعات استفاده از تبلیغ در تلویزیون شب
  • \(W\): تعداد دفعات استفاده از بنرهای وب‌سایت
  • \(SN\): تعداد دفعات استفاده از روزنامه یکشنبه
  • \(R\): تعداد دفعات استفاده از رادیو
رسانه‌های تبلیغاتی تعداد مشتریان بالقوه قابل دسترسی هزینه هر تبلیغ حداکثر تعداد دفعات قابل استفاده در ماه واحدهای کیفیت نمایش
تلویزیون روز (یک دقیقه), شبکه WKLA 1000 1500 15 65
تلویزیون شب (۳۰ ثانیه), شبکه WKLA 2000 3000 10 90
تبلیغ وب سایت (بنر) 1500 400 25 40
مجله روزنامه یکشنبه (نیم صفحه رنگی), The Sunday Press 2500 1000 4 60
رادیو, اخبار ساعت ۸ صبح یا ۵ بعد از ظهر (۳۰ ثانیه) ایستگاه KNOP 300 100 30 20

با هدف بیشینه‌سازی مجموع واحدهای کیفیت نمایش برای کل برنامه انتخاب رسانه‌ها، مدل به شکل زیر خواهد بود:

\[\begin{align} Maximize\ Z & = 65DTV + 90ETV + 40W + 60SN + 20R \\ \\ Subject\ to \\ \\ DTV & \le 15\\ ETV & \le 10\\ W & \le 25\\ SN & \le 4\\ R & \le 30 \\ 1500DTV + 3000ETV + 400W + 1000SN + 100R & \le 30,000 \\ DTV + ETV & \ge 10 \\ 1500DTV + 3000ETV & \le 18,000 \\ 1000DTV + 2000ETV + 1500W + 2500SN + 300R & \ge 50,000 \\ DTV,ETV,W,SN,R & \ge 0 \\ \end{align}\]
پاسخ 
result = linprog(
    [-65, -90, -40, -60, -20],
    [
        [1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 1, 0, 0],
        [0, 0, 0, 1, 0],
        [0, 0, 0, 0, 1],
        [1500, 3000, 400, 1000, 100],
        [-1, -1, 0, 0, 0],
        [1500, 3000, 0, 0, 0],
        [-1000, -2000, -1500, -2500, -300],
    ],
    [15, 10, 25, 4, 30, 30000, -10, 18000, -50000],
)
print(result.x, -result.fun)
# [10, 0, 25, 2, 30] 2370

مثال تحقیقات بازار

شرکت MSI در زمینه ارزیابی واکنش مصرف‌کنندگان نسبت به محصولات، خدمات و کمپین‌های تبلیغاتی جدید تخصص دارد. یک شرکت مشتری از MSI خواست واکنش مصرف‌کنندگان نسبت به یک محصول خانگی تازه وارد بازار بررسی شود.

در جلسات با مشتری، MSI موافقت کرد مصاحبه‌های حضوری انجام شود تا پاسخ‌ها از خانوارهای دارای فرزند و خانوارهای بدون فرزند جمع‌آوری شود. همچنین MSI قرار شد مصاحبه‌ها هم در روز و هم در شب انجام شود.

قرارداد مشتری شامل ۱,۰۰۰ مصاحبه با رعایت سهمیه‌های زیر است:

  1. حداقل ۴۰۰ خانوار دارای فرزند مصاحبه شوند
  2. حداقل ۴۰۰ خانوار بدون فرزند مصاحبه شوند
  3. تعداد کل خانوارهایی که در شب مصاحبه می‌شوند حداقل برابر با تعداد خانوارهای مصاحبه شده در روز باشد
  4. حداقل ۴۰٪ از مصاحبه‌ها با خانوارهای دارای فرزند در شب انجام شود
  5. حداقل ۶۰٪ از مصاحبه‌ها با خانوارهای بدون فرزند در شب انجام شود

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

خانوار هزینه مصاحبه روز هزینه مصاحبه عصر
دارای فرزند ۲۰ دلار ۲۵ دلار
بدون فرزند ۱۸ دلار ۲۰ دلار

طرح مصاحبه خانوار و زمان روز که الزامات قرارداد را با حداقل هزینه کل مصاحبه برآورده کند، به صورت مدل برنامه‌ریزی خطی فرموله می‌شود.

متغیرهای تصمیم‌گیری:

  • \(DC\): تعداد مصاحبه‌های روز خانوارهای دارای فرزند
  • \(EC\): تعداد مصاحبه‌های شب خانوارهای دارای فرزند
  • \(DNC\): تعداد مصاحبه‌های روز خانوارهای بدون فرزند
  • \(ENC\): تعداد مصاحبه‌های شب خانوارهای بدون فرزند

با در نظر گرفتن شرایط غیرمنفی بودن متغیرهای تصمیم، مدل برنامه‌ریزی خطی با چهار متغیر و شش محدودیت به شکل زیر ارائه می‌شود:

\[\begin{align} Minimize\ Z & = 20DC + 25EC + 18DNC + 20ENC \\ \\ Subject\ to \\ \\ DC + EC & \ge 400 \\ DNC + ENC & \ge 400 \\ EC + ENC & \ge (DC + DNC) \\ EC & \ge 0.4(DC + EC) \\ ENC & \ge 0.6(DNC + ENC) \\ DC + EC + DNC + ENC & = 1000 \\ DC,EC,DNC,ENC & \ge 0 \end{align}\]
پاسخ 
result = linprog(
    [20, 25, 18, 20],
    [
        [-1, -1, 0, 0], 
        [0, 0, -1, -1], 
        [1, -1, 1, -1], 
        [0.4, -0.6, 0, 0], 
        [0, 0, 0.6, -0.4]
    ],
    [-400, -400, 0, 0, 0],
    [[1, 1, 1, 1]],
    [1000],
)
print(result.x, result.fun)
# [240, 160, 240, 360] 20320

اقتصادی

مثال انتخاب سبد بهینه

شرکت Inc واقع در نیویورک، پس از تبدیل اوراق قرضه صنعتی به وجه نقد، مبلغ ۱۰۰٬۰۰۰ دلار در اختیار دارد و به دنبال فرصت‌های سرمایه‌گذاری جدید است. بر اساس سرمایه‌گذاری‌های فعلی، تحلیل‌گر ارشد مالی شرکت توصیه می‌کند که تمام سرمایه‌گذاری‌های جدید در صنعت نفت، صنعت فولاد یا اوراق قرضه دولتی انجام شود.

به طور مشخص، پنج فرصت سرمایه‌گذاری شناسایی و نرخ بازده سالانه آن‌ها برآورد شده است.

مدیریت شرکت دستورالعمل‌های زیر را تعیین کرده است:

  1. هیچ‌یک از دو صنعت نفت یا فولاد نباید بیش از ۵۰٬۰۰۰ دلار دریافت کند.
  2. میزان سرمایه‌گذاری در اوراق قرضه دولتی باید حداقل ۲۵٪ سرمایه‌گذاری صنعت فولاد باشد.
  3. سرمایه‌گذاری در AOC (سرمایه‌گذاری با بازده بالا و ریسک زیاد) نباید بیش از ۶۰٪ کل سرمایه‌گذاری صنعت نفت باشد.
نرخ بازده پیش بینی شده
(%) سرمایه‌گذاری
7.3 شرکت نفتی AOC
10.3 شرکت نفتی POC
6.4 شرکت فولاد MDS
7.5 شرکت فولاد HBS
4.5 اوراق قرضه دولتی

چه پیشنهاد سبد سرمایه‌گذاری، شامل نوع سرمایه‌گذاری و میزان آن، برای ۱۰۰٬۰۰۰ دلار موجود باید ارائه شود؟

با توجه به هدف بیشینه‌سازی بازده پیش‌بینی‌شده و در نظر گرفتن محدودیت‌های بودجه‌ای و مدیریتی، می‌توان این مسئله را با تدوین و حل یک مدل برنامه‌ریزی خطی پاسخ داد.

حل این مدل، پیشنهادهای سرمایه‌گذاری لازم را برای مدیریت شرکت Welte Mutual Funds ارائه خواهد کرد.

فرض کنید: متغیرهای تصمیم‌گیری:

  • \(A\): میزان سرمایه‌گذاری (دلار) در AOC
  • \(P\): میزان سرمایه‌گذاری (دلار) در POC
  • \(M\): میزان سرمایه‌گذاری (دلار) در MDS
  • \(H\): میزان سرمایه‌گذاری (دلار) در HBS
  • \(G\): میزان سرمایه‌گذاری (دلار) در اوراق قرضه دولتی

با استفاده از نرخ‌های بازده پیش‌بینی‌شده نشان‌داده‌شده در جدول، مدل ریاضی برای بیشینه‌سازی بازده کل سبد سرمایه‌گذاری را به شکل زیر می‌توان نوشت:

\[\begin{align} Maximize\ Z & = 0.073A + 0.103P + 0.064M + 0.075H + 0.045G \\ \\ Subject\ to \\ \\ A + P + M + H + G &= 100,000\\ A + P &\le 50,000\\ M + H &\le 50,000\\ G &\ge 0.25(M + H)\\ P &\le 0.60(A + P)\\ A,P,H,G &\ge 0 \end{align}\]
پاسخ 
result = linprog(
    [-.073, -.103, -.064, -.075, -.045],
    [
        [1, 1, 0, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, .25, .25, -1],
        [-.6, .4, 0, 0, 0]
    ],
    [50000, 50000, 0, 0],
    [[1, 1, 1, 1, 1]],
    [100000]
)
print(result.x, -result.fun)
# [20000, 30000, 0, 40000, 10000] 8000

مثال برنامه‌ریزی مالی

صندوق‌دار شرکت باید تعیین کند چه مقدار پول باید امروز کنار گذاشته شود تا هشت تعهد مالی سالانه در موعد خود پرداخت شوند. برنامه تأمین مالی برنامه بازنشستگی شامل سرمایه‌گذاری در اوراق قرضه دولتی و پس‌انداز است. سرمایه‌گذاری در اوراق قرضه دولتی محدود به سه گزینه است:

سر رسید نرخ (%) مبلغ (هزار دلار) اوراق
5 8.875 1150 1
6 5.500 1000 2
7 11.750 1350 3

اوراق قرضه دولتی دارای ارزش اسمی ۱,۰۰۰ دلار هستند، به این معنا که حتی با قیمت‌های متفاوت، هر اوراق در سررسید ۱,۰۰۰ دلار پرداخت می‌کند. نرخ‌های نشان‌داده‌شده بر اساس ارزش اسمی محاسبه شده‌اند. برای برنامه‌ریزی، صندوق‌دار فرض کرده است که هر وجهی که در اوراق سرمایه‌گذاری نشود، در پس‌انداز قرار می‌گیرد و سالانه ۴٪ بهره خواهد داشت.

متغیرهای تصمیم‌گیری به شرح زیر تعریف می‌شوند:

  • \(F\): کل مبلغ لازم برای پوشش هشت سال تعهد برنامه بازنشستگی
  • \(B_1\): تعداد واحدهای اوراق قرضه ۱ خریداری‌شده در ابتدای سال ۱
  • \(B_2\): تعداد واحدهای اوراق قرضه ۲ خریداری‌شده در ابتدای سال ۱
  • \(B_3\): تعداد واحدهای اوراق قرضه ۳ خریداری‌شده در ابتدای سال ۱
  • \(S_i\): مبلغ قرار داده‌شده در پس‌انداز در ابتدای سال \(i\)، به ازای \(i=1,...,8\)

تابع هدف کمینه‌سازی کل مبلغ لازم برای پوشش هشت سال تعهد برنامه بازنشستگی است، یعنی:

\[Minimize\ F\]

ویژگی اصلی این نوع مسئله برنامه‌ریزی مالی این است که برای هر سال از افق برنامه‌ریزی یک محدودیت باید فرموله شود. به طور کلی، هر محدودیت به شکل زیر است:

(وجوه موجود در ابتدای سال) - (وجوه سرمایه‌گذاری شده در اوراق قرضه و قرار داده‌شده در پس‌انداز) = (تعهد نقدی همان سال)

وجوه موجود در ابتدای سال ۱ با \(F\) مشخص می‌شوند. با قیمت فعلی ۱,۱۵۰ دلار برای اوراق قرضه ۱ و با بیان سرمایه‌گذاری‌ها به هزار دلار، کل سرمایه‌گذاری برای \(B_1\) واحد از اوراق قرضه ۱ برابر با  \(1.15B_1\) خواهد بود. به همین ترتیب، کل سرمایه‌گذاری در اوراق ۲ و ۳ به ترتیب برابر با  \(1B_2\) و \(1.35B_3\) است. سرمایه‌گذاری در پس‌انداز برای سال ۱ برابر با \(S_1\) است.

با استفاده از این مقادیر و تعهد سال اول برابر با ۴۳۰، محدودیت سال ۱ به صورت زیر خواهد بود:

\[F - 1.15B_1 - 1B_2 - 1.35B_3 - S_1 = 430\]

سرمایه‌گذاری در اوراق قرضه تنها در سال اول انجام می‌شود و اوراق تا سررسید نگهداری می‌شوند.

وجوه موجود در ابتدای سال ۲ شامل بازده سرمایه‌گذاری‌ها است:

  • ۸٫۸۷۵٪ از ارزش اسمی اوراق ۱
  • ۵٫۵٪ از ارزش اسمی اوراق ۲
  • ۱۱٫۷۵٪ از ارزش اسمی اوراق ۳
  • ۴٪ از پس‌انداز سال قبل

مبلغ جدیدی که در پس‌انداز برای سال ۲ سرمایه‌گذاری می‌شود برابر با \(210S_2\) است. با توجه به تعهد سال دوم برابر با، محدودیت سال ۲ به شکل زیر خواهد بود:

\[0.08875B_1 + 0.055B_2 + 0.1175B_3 + 1.04S_1 - S_2 = 210\]

به همین ترتیب، محدودیت‌های سال‌های ۳ تا ۸ به شکل زیر هستند:

\[\begin{align} 0.08875B_1 + 0.055B_2 + 0.1175B_3 + 1.04S_2 - S_3 & = 222 \\ 0.08875B_1 + 0.055B_2 + 0.1175B_3 + 1.04S_3 - S_4 & = 231 \\ 0.08875B_1 + 0.055B_2 + 0.1175B_3 + 1.04S_4 - S_5 & = 240 \\ 1.08875B_1 + 0.055B_2 + 0.1175B_3 + 1.04S_5 - S_6 & = 195 \\ 1.055B_2 + 0.1175B_3 + 1.04S_6 - S_7 & = 225 \\ 1.1175B_3 + 1.04S_7 - S_8 & = 255 \\ \end{align}\]

توجه داشته باشید که محدودیت سال ۶ نشان می‌دهد وجوه موجود از اوراق قرضه ۱ برابر با \(1.08875B_1\) است. ضریب ۱.۰۸۸۷۵ نشان‌دهنده این است که اوراق ۱ در پایان سال ۵ سررسید می‌شود و ارزش اسمی به علاوه بهره آن در سال ۵، در ابتدای سال ۶ قابل استفاده است.

از آنجا که اوراق ۱ در سال ۵ سررسید می‌شود و در ابتدای سال ۶ در دسترس قرار می‌گیرد، متغیر \(B_1\) در محدودیت‌های سال‌های ۷ و ۸ ظاهر نمی‌شود.

تفسیر مشابهی برای اوراق ۲ وجود دارد که در پایان سال ۶ سررسید می‌شود و ارزش اسمی به علاوه بهره آن در ابتدای سال ۷ در دسترس است. همچنین اوراق ۳ در پایان سال ۷ سررسید می‌شود و ارزش اسمی به علاوه بهره آن در ابتدای سال ۸ قابل استفاده است.

در نهایت، توجه کنید که \(S_8\) در محدودیت سال ۸ ظاهر شده است. تعهد صندوق بازنشستگی در ابتدای سال ۸ تکمیل می‌شود، بنابراین انتظار می‌رود \(S_8=0\) و وجهی در پس‌انداز قرار داده نشود. با این حال، \(S_8\) در مدل لحاظ شده تا در صورتی که درآمد اوراق به علاوه بهره پس‌انداز سال ۷ بیش از نیاز نقدی ۲۵۵ سال ۸ باشد، نشان‌دهنده وجوه اضافی باقی‌مانده باشد. بنابراین، \(S_8\) یک متغیر مازاد است که هر وجه باقیمانده پس از تأمین نیازهای نقدی هشت سال را نشان می‌دهد.

پاسخ 
result = linprog(
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    None, None,
    [
        [1, -1.15, -1, -1.35, -1, 0, 0, 0, 0, 0, 0, 0],
        [0, .08875, .055, 0.1175, 1.04, -1, 0, 0, 0, 0, 0, 0],
        [0, .08875, .055, 0.1175, 0, 1.04, -1, 0, 0, 0, 0, 0],
        [0, .08875, .055, 0.1175, 0, 0, 1.04, -1, 0, 0, 0, 0],
        [0, .08875, .055, 0.1175, 0, 0, 0, 1.04, -1, 0, 0, 0],
        [0, 1.08875, .055, 0.1175, 0, 0, 0, 0, 1.04, -1, 0, 0],
        [0, 0, 1.055, 0.1175, 0, 0, 0, 0, 0, 1.04, -1, 0],
        [0, 0, 0, 1.1175, 0, 0, 0, 0, 0, 0, 1.04, -1],
    ],
    [430, 210, 222, 231, 240, 195, 225, 255],
)
print(result.x, result.fun)
# [1728.79, 144.99, 187.86, 228.19, 636.15, 501.61, 349.68, 182.68, 0, 0, 0, 0] 1728.79

مدیریت عملیات

مثال تصمیم ساخت یا خرید

شرکتی انواع مختلفی از پمپ‌ها را عرضه می‌کند که در کاربردهایی از جمله پمپاژ خون برای انتقال در بیمارستان‌ها تا پمپاژ آب در پروژه‌های مهندسی استفاده می‌شوند.

در حال حاضر، این شرکت در حال آماده‌سازی برای عرضه دو نوع پمپ است: یکی برای بازار انتقال خون پزشکی که «پمپ انتقال خون» نامیده می‌شود و دیگری برای بازار مهندسی که «پمپ عملکردی» نام دارد.

هر نوع پمپ از سه جزء تشکیل شده است: پایه، هسته و بخش بالایی. پایه در هر دو نوع پمپ یکسان است، اما هسته و بخش بالایی آن‌ها متفاوت‌اند. تمامی اجزا می‌توانند توسط شرکت تولید شوند یا از تأمین‌کنندگان خارجی خریداری گردند. هزینه‌های تولید و قیمت‌های خرید این اجزا در جدول اول خلاصه شده‌اند.

بر اساس پیش‌بینی‌ها، به ۳۰۰۰ پمپ عملکردی مهندسی و ۲۰۰۰ پمپ انتقال خون نیاز خواهد بود. با این حال، ظرفیت تولید محدود است. شرکت ۲۰۰ ساعت زمان تولید عادی و ۵۰ ساعت اضافه‌کاری در اختیار دارد که می‌توان آن‌ها را به تولید پمپ‌ها اختصاص داد. اضافه‌کاری با هزینه مازاد ۹ دلار به ازای هر ساعت همراه است. جدول دوم زمان‌های تولید اجزا (بر حسب دقیقه) را نشان می‌دهد.

هزینه هر واحد
خرید تولید (زمان عادی) پایه
0.60 دلار 0.50 دلار جزء
4.00 دلار 3.75 دلار هسته عملکردی
3.90 دلار 3.30 دلار هسته انتقال خون
0.65 دلار 0.60 دلار بخش بالایی عملکردی
0.78 دلار .075 دلار بخش بالایی انتقال خون
زمان تولید قطعات پمپ شرکت (بر حسب دقیقه برای هر واحد)
زمان تولید (دقیقه) جزء
1.0 پایه
3.0 هسته عملکردی
2.5 هسته انتقال خون
1.0 بخش بالایی عملکردی
1.5 بخش بالایی انتقال خون

مسئله شرکت این است که تعیین کند از هر جزء چه تعداد تولید و چه تعداد خریداری شود.

متغیرهای تصمیم به صورت زیر تعریف می‌شوند:

  • \(BM\): تعداد پایه‌های تولیدشده
  • \(BP\): تعداد پایه‌های خریداری‌شده
  • \(FCM\): تعداد هسته‌های عملکردیِ تولیدشده
  • \(FCP\): تعداد هسته‌های عملکردیِ خریداری‌شده
  • \(TCM\): تعداد هسته‌های انتقال خونِ تولیدشده
  • \(TCP\): تعداد هسته‌های انتقال خونِ خریداری‌شده
  • \(FTM\): تعداد بخش‌های بالاییِ عملکردیِ تولیدشده
  • \(FTP\): تعداد بخش‌های بالاییِ عملکردیِ خریداری‌شده
  • \(TTM\): تعداد بخش‌های بالاییِ انتقال خونِ تولیدشده
  • \(TTP\): تعداد بخش‌های بالاییِ انتقال خونِ خریداری‌شده

یک متغیر تصمیم دیگر نیز لازم است تا تعداد ساعات اضافه‌کاری موردنیاز مشخص شود:

\(OT\) = تعداد ساعات اضافه‌کاری برنامه‌ریزی‌شده

تابع هدف، کمینه‌سازی هزینه کل است؛ شامل هزینه‌های تولید، هزینه‌های خرید و هزینه‌های اضافه‌کاری.

پنج محدودیت نخست، تعداد هر جزء موردنیاز برای تأمین تقاضای ۳۰۰۰ پمپ عملکردی و ۲۰۰۰ پمپ انتقال خون را مشخص می‌کنند. در مجموع به ۵۰۰۰ قطعه پایه نیاز است و تعداد سایر اجزا بسته به تقاضای هر نوع پمپ تعیین می‌شود.

پنج محدودیت مربوط به تقاضا به شرح زیر هستند:

متغیر تعداد مورد نیاز جزء
\(BM + BP\) 5000 پایه ها
\(FCM + FCP\) 3000 هسته‌های عملکردی
\(TCM + TCP\) 2000 هسته‌های انتقال خون
\(FTM + FTP\) 3000 بخش بالایی عملکردی
\(TTM + TTP\) 2000 بخش بالایی انتقال خون

دو محدودیت لازم است تا اطمینان حاصل شود که ظرفیت‌های تولید در زمان عادی و اضافه‌کاری نمی‌توانند بیش از حد استفاده شوند. محدودیت اول ظرفیت اضافه‌کاری را به ۵۰ ساعت محدود می‌کند، یا \(OT \le 50\)

محدودیت دوم بیان می‌کند که مجموع زمان تولید موردنیاز برای همه اجزا باید کمتر یا مساوی کل ظرفیت تولید باشد، شامل زمان عادی به‌علاوه اضافه‌کاری. زمان‌های تولید اجزا بر حسب دقیقه بیان شده‌اند، بنابراین محدودیت کل ظرفیت تولید را به دقیقه بیان می‌کنیم، که ۲۰۰ ساعت ظرفیت زمان عادی به صورت \((60 \times 200 = 12,000)\) دقیقه است. مقدار واقعی اضافه‌کاری در این مرحله نامعلوم است، بنابراین اضافه‌کاری را به صورت \((60 \ OT)\) دقیقه می‌نویسیم. با استفاده از زمان‌های تولید جدول دوم داریم:

\[BM + 3FCM + 2.5TCM + FTM + 1.5TTM \le 12,000 + 60OT\]

فرمول‌بندی کامل مسئله ساخت یا خرید شرکت با شرط اینکه همه متغیرهای تصمیم بزرگ‌تر یا مساوی صفر باشند، به صورت زیر است:

\[\begin{align} Minimize\ Z & = 0.5BM + 0.6BP + 3.75FCM + 4FCP + 3.3TCM + 3.9TCP \\ & + 0.6FTM + 0.65FTP + 0.75TTM + 0.78TTP + 9OT \\ Subject\ to \\ \\ BM + BP & = 5000\\ FCM + FCP & = 3000\\ TCM + TCP & = 2000\\ FTM + FTP & = 3000\\ TTM + TTP & = 2000\\ OT & \le 50\\ BM + 3FCM + 2.5TCM + FTM + 1.5TTM & \le 12,000 + 60OT \end{align}\]
پاسخ 
result = linprog(
    [.5, .6, 3.75, 4, 3.3, 3.9, .6, .65, .75, .78, 9],
    [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 3, 0, 2.5, 0, 1, 0, 1.5, 0, -60]
    ],
    [50, 12000],
    [
        [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
    ],
    [5000, 3000, 2000, 3000, 2000]
)
print(result.x, result.fun)
# [5000, 0, 666.67, 2333.33, 2000, 0, 0, 3000, 0, 2000, 0] 24443.33

مثال مدیریت تولید

شرکت بولینگر الکترونیکس دو نوع قطعه الکترونیکی را برای یک تولیدکننده موتور هواپیما تولید می‌کند. نیاز ماهانه قطعات برای سه ماه آینده توسط تولیدکننده موتور به بولینگر اعلام می‌شود و بسته به نوع موتور، متغیر است. سفارش مربوط به دوره سه ماهه آتی در جدول ارائه شده است.

قطعه آپریل می ژوئن
A322 1000 3000 5000
B802 1000 500 3000
ماه ظرفیت ماشین (ساعت) ظرفیت نیروی کار (ساعت) ظرفیت انبارداری (مترمربع)
آپریل 400 300 10,000
می 500 300 10,000
ژوئن 600 300 10,000
قطعه ماشین (ساعت) نیروی کار (ساعت) انبار (مترمربع)
A322 0.10 0.05 2
B802 0.08 0.07 3

پس از پردازش سفارش، وضعیت تقاضا به کنترل تولید ارسال و برنامه تولید سه ماهه قطعات تدوین می‌شود. در تهیه برنامه، مدیر تولید موارد زیر را مشخص می‌کند:

  • کل هزینه تولید
  • هزینه نگهداری موجودی
  • هزینه‌های تغییر سطح تولید

مدل ریاضی این مساله را می‌توان به صورت زیر نوشت:

  • \(I_m\): افزایش سطح کل تولید موردنیاز در ماه \(m\)
  • \(D_m\): کاهش سطح کل تولید موردنیاز در ماه \(m\)
\[\begin{align} Minimize\ Z & = 20x_{11} + 20x_{12} + 20x_{13} \\ & + 10x_{21} + 10x_{22} + 10x_{23} \\ & + 0.30s_{11} + 0.30s_{12} + 0.30s_{13} \\ & + 0.15s_{21} + 0.15s_{22} + 0.15s_{23} \\ & + 0.50I_1 + 0.50I_2 + 0.50I_3 \\ & + 0.20D_1 + 0.20D_2 + 0.20D_3 \\ Subject\ to \\ \\ x_{11} - s_{11} & = 500 \\ x_{21} - s_{21} & = 800 \\ s_{11} + x_{12} - s_{12} & = 3000 \\ s_{21} + x_{22} - s_{22} & = 500 \\ s_{12} + x_{13} - s_{13} & = 5000 \\ s_{22} + x_{23} - s_{23} & = 3000 \\ s_{13} & \ge 400 \\ s_{23} & \ge 200 \\ 0.10x_{11} + 0.08x_{21} & \le 400 \\ 0.10x_{12} + 0.08x_{22} & \le 500 \\ 0.10x_{13} + 0.08x_{23} & \le 600 \\ 0.05x_{11} + 0.07x_{21} & \le 300 \\ 0.05x_{12} + 0.07x_{22} & \le 300 \\ 0.05x_{13} + 0.07x_{23} & \le 300 \\ 2s_{11} + 3s_{21} & \le 10,000 \\ 2s_{12} + 3s_{22} & \le 10,000 \\ 2s_{13} + 3s_{23} & \le 10,000 \\ x_{11} + x_{21} - 2500 & = I_1 - D_1 \\ (x_{12} + x_{22}) - (x_{11} + x_{21}) & = I_2 - D_2 \\ (x_{13} + x_{23}) - (x_{12} + x_{22}) & = I_3 - D_3 \\ \end{align}\]
پاسخ 
result = linprog(
    [20, 20, 20, 10, 10, 10, 0.30, 0.30, 0.30, 0.15, 0.15, 0.15, 0.50, 0.50, 0.50, 0.20, 0.20, 0.20],
    [
        [0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0],
        [0.10, 0, 0, 0.08, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0.10, 0, 0, 0.08, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0.10, 0, 0, 0.08, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0.05, 0, 0, 0.07, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0.05, 0, 0, 0.07, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0.05, 0, 0, 0.07, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0],
    ],
    [-400, -200, 400, 500, 600, 300, 300, 300, 10000, 10000, 10000],
    [
        [1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0],
        [-1, 1, 0, -1, 1, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0],
        [0, -1, 1, 0, -1, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 1],
    ],
    [0, 0, 0, 0, 0, 0, 2500, 0, 0],
)
print(result.x, result.fun)   
# [0, 0, 400, 0, 200, 0, 0, 0, 400, 200, 0, 200, 0, 0, 0, 2700, 0, 0] 10720

مثال طرح اختلاط

مسائل اختلاط زمانی، در آن مدیران باید تصمیم بگیرند چگونه منابع را ترکیب کنند تا محصولات نهایی بسازند. منابع حاوی مواد اساسی هستند که در محصول باید درصد معینی داشته باشند؛ مدیریت باید مقداری از هر منبع را خریداری کند تا مشخصات محصول و تقاضای بازار را با کمترین هزینه برآورده سازد. این مسائل در صنایع نفت (ترکیب نفت خام)، شیمی (ترکیب مواد برای کود و سموم) و غذا (ترکیب مواد برای نوشیدنی‌ها و سوپ‌ها) رایج می‌باشند.

شرکت نفتی بنزین معمولی و ویژه را برای پمپ‌های مستقل تولید می‌کند و سه جزء نفتی را ترکیب می‌کند. بنزین معمولی با قیمت ۲.۹۰ دلار/گالن و بنزین سوپر با ۳.۰۰ دلار/گالن فروخته می‌شوند؛ هزینه‌های اجزای نفتی در جدول اولیه نمایش داده شده است. مشخصات هر بنزین محدودیت‌هایی بر درصد هر جزء دارد که در جدول دوم آمده است. تعهد فعلی به توزیع‌کنندگان حاکی از حداقل تولید ۱۰٬۰۰۰ گالن بنزین معمولی است.
هدف مسئله‌ی اختلاط تعیین مقدار هر جزء در ترکیب دو بنزین است تا سود حداکثر شود در حالی که:
- محدودیت‌های تأمین اجزای نفتی رعایت شوند - مشخصات محصول رعایت گردد - حداقل ۱۰٬۰۰۰ گالن بنزین معمولی تولید شود

اجزاء پتروشیمی هزینه به ازای هر گالن حداکثر مقدار موجود
۱ ۲.۵۰ دلار ۵۰۰۰ گالن
۲ ۲.۶۰ دلار ۱۰۰۰۰ گالن
۳ ۲.۸۴ دلار ۱۰۰۰۰ گالن
بنزین مشخصات
بنزین معمولی - حداکثر ۳۰٪ جزء ۱
- حداقل ۴۰٪ جزء ۲
- حداکثر ۲۰٪ جزء ۳
بنزین ویژه - حداقل ۲۵٪ جزء ۱
- حداکثر ۴۵٪ جزء ۲
- حداقل ۳۰٪ جزء ۳

متغیرهای تصمیم‌گیری:

  • \(x_{ij}\): گالن جزء \(i\) بنزین \(j\) استفاده می‌شود
  • \(i\): ۱، ۲، یا ۳ برای اجزاء ۱، ۲، یا ۳
  • \(j\): r اگر بنزین معمولی یا p اگر بنزین سوپر

بصورت زیر:

  • \(x_{1r}\): گالن جزء ۱ در بنزین معمولی
  • \(x_{2r}\): گالن جزء ۲ در بنزین معمولی
  • \(x_{3r}\): گالن جزء ۳ در بنزین معمولی
  • \(x_{1p}\): گالن جزء ۱ در بنزین ویژه
  • \(x_{2p}\): گالن جزء ۲ در بنزین ویژه
  • \(x_{3p}\): گالن جزء ۳ در بنزین ویژه

مدل ریاضی را بصورت زیر می‌توان نوشت:

\[\begin{align} Maximize\ Z & = 0.40x_{1r} + 0.30x_{2r} + 0.06x_{3r} + 0.50x_{1p} + 0.40x_{2p} + 0.16_x{3p}\\ \\ Subject\ to \\ \\ x_{1r} + x_{1p} & \le 5000\\ x_{2r} + x_{2p} & \le 10,000\\ x_{3r} + x_{3p} & \le 10,000\\ x_{1r} & \le 0.30(x_{1r} + x_{2r} + x_{3r})\\ x_{2r} & \ge 0.40(x_{1r} + x_{2r} + x_{3r})\\ x_{3r} & \le 0.20(x_{1r} + x_{2r} + x_{3r})\\ x_{1p} & \ge 0.25(x_{1p} + x_{2p} + x_{3p})\\ x_{2p} & \le 0.45(x_{1p} + x_{2p} + x_{3p})\\ x_{3p} & \ge 0.30(x_{1p} + x_{2p} + x_{3p})\\ x_{1r} + x_{2r} + x_{3r} & \ge 10,000\\ x_{1r}, x_{2r}, x_{3r}, x_{1p}, x_{2p}, x_{3p} & \ge 0 \end{align}\]
پاسخ 
result = linprog(
    [-.4, -.3, -.06, -.5, -.4, -.16],
    [
        [1, 0, 0, 1, 0, 0],
        [0, 1, 0, 0, 1, 0],
        [0, 0, 1, 0, 0, 1],
        [.7, -1, -1, 0, 0, 0],
        [.4, -.6, .4, 0, 0, 0],
        [-.2, -.2, .8, 0, 0, 0],
        [0, 0, 0, -.75, .25, .25],
        [0, 0, 0, -.45, .55, -.45],
        [0, 0, 0, .3, .3, -.7],
        [-1, -1, -1, 0, 0, 0]
    ],
    [5000, 10_000, 10000, 0, 0, 0, 0, 0, 0, -10000]
)
print(result.x, -result.fun)
# [1250, 6750, 2000, 3750, 3250, 8000] 7100