২. যোগাশ্রয়ী প্রোগ্রাম (Linear Programming)

যোগাশ্রয়ী প্রোগ্রাম (Linear Programming) হলো গাণিতিক অনুকূলন কৌশলের একটি শাখা যা সীমিত সম্পদের সর্বোত্তম ব্যবহার নির্ধারণে সহায়তা করে। খাদ্য উৎপাদন থেকে শিল্প কারখানার উৎপাদন পরিকল্পনা, পরিবহন ব্যবস্থা থেকে বিনিয়োগ পরিকল্পনা—সর্বত্র এই পদ্ধতির প্রয়োগ দেখা যায়। এই অধ্যায়ে আমরা যোগাশ্রয়ী প্রোগ্রামের গাঠনিক উপাদন, গাণিতিক মডেল গঠন এবং লেখচিত্র পদ্ধতিতে (Graphical Method) দ্বিমাত্রিক সমস্যার সমাধান শিখব।

মৌলিক ধারণা ও সংজ্ঞা

যোগাশ্রয়ী প্রোগ্রাম কী?

যোগাশ্রয়ী প্রোগ্রাম হলো এমন একটি পদ্ধতি যেখানে একটি রৈখিক লক্ষ্য ফাংশন (Linear Objective Function) কে কতিপয় রৈখিক সীমাবদ্ধতার (Linear Constraints) মাধ্যমে সংজ্ঞায়িত একটি অঞ্চলের মধ্যে সর্বাধিক বা সর্বনিম্ন করতে হয়।

প্রধান উপাদনসমূহ (Components)

১. সিদ্ধান্ত চলক (Decision Variables)

যে চলকগুলোর মান নির্ধারণ করতে হবে। সাধারণত \(x, y\) বা \(x_1, x_2, \dots\) দ্বারা প্রকাশ করা হয়। এগুলো অঋণাত্মক হয় (\(x, y \geq 0\))।

২. লক্ষ্য ফাংশন (Objective Function)

সর্বাধিক বা সর্বনিম্ন করতে হবে এমন একটি রৈখিক ফাংশন। সাধারণত \(Z = ax + by\) আকারে।

৩. সীমাবদ্ধতা (Constraints)

সম্পদের সীমা বা শর্তাবলী যা রৈখিক অসমতা বা সমীকরণ আকারে থাকে। যেমন: \(a_1x + b_1y \leq c_1\)

৪. অঋণাত্মকতার শর্ত (Non-negativity)

বাস্তব জগতের সমস্যায় চলকগুলো সাধারণত ঋণাত্মক হতে পারে না: \(x \geq 0, y \geq 0\)

যোগাশ্রয়ী প্রোগ্রামের গাণিতিক রূপ (Standard Form)

লক্ষ্য: \(Z = ax + by\) কে সর্বাধিক বা সর্বনিম্ন করতে হবে (Maximize or Minimize)

সীমাবদ্ধতাসমূহ:

\[a_1x + b_1y \leq c_1\]

\[a_2x + b_2y \leq c_2\]

\[\vdots\]

\[a_nx + b_ny \leq c_n\]

এবং \(x, y \geq 0\)

💡 মনে রাখুন: "যোগাশ্রয়ী" বলতে বোঝায় সব সমীকরণ ও অসমতা রৈখিক (first degree)। যদি কোনো চলকের ঘাত ২ বা তার বেশি থাকে, তবে তা যোগাশ্রয়ী প্রোগ্রাম নয়।

যোগাশ্রয়ী প্রোগ্রামের গঠন (Formulation of LPP)

একটি বাস্তব সমস্যাকে গাণিতিক মডেলে রূপান্তর করাকে গঠন (Formulation) বলে। এর ধাপসমূহ:

ধাপে ধাপে গঠন পদ্ধতি

  1. সিদ্ধান্ত চলক নির্ধারণ: কী কী পরিমাণ নির্ধারণ করতে হবে তা চিহ্নিত করুন এবং তাদের \(x, y\) ইত্যাদি দিয়ে প্রকাশ করুন।
  2. লক্ষ্য নির্ধারণ: লাভ বৃদ্ধি, খরচ কমানো, বা সময় সাশ্রয়—কী অর্জন করতে চান তা নির্ধারণ করুন এবং তা রৈখিক ফাংশন আকারে প্রকাশ করুন।
  3. সীমাবদ্ধতা চিহ্নিতকরণ: কাঁচামালের সীমা, শ্রমিকের সংখ্যা, মেশিনের সময়, বাজারের চাহিদা ইত্যাদি সীমাবদ্ধতাগুলো রৈখিক অসমতা হিসেবে লিখুন।
  4. অঋণাত্মকতার শর্ত: \(x \geq 0, y \geq 0\) যোগ করুন।

ব্যবহারিক উদাহরণ: উৎপাদন সমস্যা

উদাহরণ:

একটি কারখানায় দুটি ধরনের পণ্য \(A\) ও \(B\) তৈরি করা হয়। প্রতিটি পণ্য \(A\) বিক্রি করে ৩০ টাকা লাভ এবং প্রতিটি \(B\) বিক্রি করে ২০ টাকা লাভ হয়। পণ্য \(A\) তৈরিতে ২ ঘণ্টা এবং \(B\) তৈরিতে ১ ঘণ্টা সময় লাগে। মোট সময় ১০০ ঘণ্টা। আবার কাঁচামালের সীমার কারণে সর্বাধিক ৪০টি \(A\) এবং ৬০টি \(B\) তৈরি করা যায়। কীভাবে উৎপাদন পরিকল্পনা করলে লাভ সর্বাধিক হবে?

গাণিতিক মডেল:

ধরি, \(x\) = পণ্য \(A\) এর সংখ্যা, \(y\) = পণ্য \(B\) এর সংখ্যা

লক্ষ্য: \(Z = 30x + 20y\) সর্বাধিক করতে হবে (লাভ সর্বাধিককরণ)

সীমাবদ্ধতা:

  • সময়: \(2x + y \leq 100\)
  • কাঁচামাল \(A\): \(x \leq 40\)
  • কাঁচামাল \(B\): \(y \leq 60\)
  • অঋণাত্মকতা: \(x, y \geq 0\)

লেখচিত্র পদ্ধতি: দ্বিমাত্রিক যোগাশ্রয়ী প্রোগ্রামের সমাধান

যখন দুটি সিদ্ধান্ত চলক (\(x\) ও \(y\)) থাকে, তখন লেখচিত্র পদ্ধতি (Graphical Method) ব্যবহার করে সহজেই সমাধান করা যায়। এই পদ্ধতিতে সীমাবদ্ধতাগুলোকে অসমতার সাহায্যে লেখচিত্রে অঙ্কন করা হয় এবং সম্ভাব্য অঞ্চল (Feasible Region) চিহ্নিত করা হয়।

সমাধানের ধাপসমূহ

  1. অক্ষ নির্ধারণ: \(x\)-অক্ষে প্রথম চলক, \(y\)-অক্ষে দ্বিতীয় চলক নিন।
  2. সীমাবদ্ধতা অঙ্কন: প্রতিটি সীমাবদ্ধতাকে সমীকরণ হিসেবে বিবেচনা করে সরলরেখা অঙ্কন করুন।
  3. অঞ্চল নির্ধারণ: প্রতিটি সীমাবদ্ধতার জন্য কোন দিকে অসমতা সত্য তা শেডিং করে চিহ্নিত করুন। সাধারণত \(\leq\) হলে মূলবিন্দুর দিকে, \(\geq\) হলে বিপরীত দিকে।
  4. সম্ভাব্য অঞ্চল: সব শেডিং এর সাধারণ অংশই হলো সম্ভাব্য অঞ্চল। এটি বহুভুজ আকারের হয়।
  5. কোণা বিন্দু নির্ণয়: সম্ভাব্য অঞ্চলের শীর্ষবিন্দুগুলোর স্থানাঙ্ক নির্ণয় করুন।
  6. লক্ষ্য ফাংশনের মান নির্ণয়: প্রতিটি কোণা বিন্দুতে \(Z\) এর মান বের করুন।
  7. সর্বাধিক/সর্বনিম্ন নির্ধারণ: \(Z\) এর সর্বাধিক বা সর্বনিম্ন মানই হলো ইচ্ছিত সমাধান।

কোণা বিন্দু উপপাদ্য (Corner Point Theorem)

যদি সম্ভাব্য অঞ্চল সীমাবদ্ধ (bounded) হয়, তবে লক্ষ্য ফাংশনের সর্বাধিক বা সর্বনিম্ন মান অবশ্যই সম্ভাব্য অঞ্চলের কোনো কোণা বিন্দুতে (Vertex/Corner Point) অর্জিত হয়।

যদি সম্ভাব্য অঞ্চল অসীম (unbounded) হয়, তবে সর্বাধিক বা সর্বনিম্ম মান নাও থাকতে পারে।

উদাহরণ: লেখচিত্র পদ্ধতিতে সমাধান

সর্বাধিক করুন: \(Z = 3x + 2y\)

সীমাবদ্ধতা: \(x + y \leq 4\), \(x \leq 3\), \(y \leq 3\), \(x, y \geq 0\)

সমাধান:

কোণা বিন্দুগুলো:

  • \(O(0, 0)\): \(Z = 0\)
  • \(A(3, 0)\): \(Z = 9\)
  • \(B(3, 1)\): সীমাবদ্ধতা \(x=3\) ও \(x+y=4\) এর ছেদ বিন্দু, \(Z = 11\)
  • \(C(1, 3)\): সীমাবদ্ধতা \(y=3\) ও \(x+y=4\) এর ছেদ বিন্দু, \(Z = 9\)
  • \(D(0, 3)\): \(Z = 6\)

সুতরাং সর্বাধিক \(Z = 11\) যখন \(x = 3, y = 1\)

আইসো-লাভ বা আইসো-খরচ রেখা পদ্ধতি

কোণা বিন্দু পদ্ধতির বিকল্প হিসেবে আইসো-লাভ রেখা (Iso-profit Line) বা আইসো-খরচ রেখা (Iso-cost Line) পদ্ধতি ব্যবহার করা যায়। এটি বিশেষ করে লক্ষ্য ফাংশনের মান বৃদ্ধির দিক নির্ধারণে সহায়ক।

পদ্ধতির বিবরণ

  1. লক্ষ্য ফাংশন \(Z = ax + by\) থেকে \(ax + by = k\) (ধ্রুবক) রেখা অঙ্কন করুন।
  2. এই রেখাটি সমান লাভ বা সমান খরচ নির্দেশ করে।
  3. এই রেখাটি সমান্তরালভাবে সরিয়ে (ঊর্ধ্বে বা ডানদিকে) সর্বাধিক \(Z\) এর মান নির্ধারণ করুন যা এখনো সম্ভাব্য অঞ্চলের মধ্যে থাকে।
  4. যে বিন্দুতে এই রেখাটি সম্ভাব্য অঞ্চলকে স্পর্শ করে সর্বাধিক দূরত্বে, সেই বিন্দুই হলো ইচ্ছিত সমাধান।
নোট: সর্বাধিককরণে রেখাটি \(Z\) বৃদ্ধির দিকে (সাধারণত ডানে ও উপরে) সরাতে হয় এবং যেখানে শেষবার স্পর্শ করে সেখানেই সর্বাধিক মান। সর্বনিম্নকরণের ক্ষেত্রে বিপরীত দিকে সরাতে হয়।

বিশেষ ক্ষেত্রসমূহ (Special Cases)

১. একাধিক ইষ্টতম সমাধান (Multiple Optimal Solutions)

যদি লক্ষ্য ফাংশনের আইসো-লাভ রেখা সম্ভাব্য অঞ্চলের কোনো বাহুর সমান্তরাল হয়, তবে সেই বাহুর সব বিন্দুতেই একই সর্বাধিক/সর্বনিম্ন মান পাওয়া যায়। এর ফলে অসীত সংখ্যক সমাধান থাকে।

২. অসীম সমাধান (Unbounded Solution)

যদি সম্ভাব্য অঞ্চল অসীম হয় এবং লক্ষ্য ফাংশনের মান সেই দিকে অসীম বৃদ্ধি পায়, তবে সর্বাধিক মান নির্ধারণ করা যায় না। একইভাবে সর্বনিম্নকরণে যদি অসীম হ্রাস পায়।

উদাহরণ: সর্বাধিক করুন \(Z = 2x + 3y\)

সীমাবদ্ধতা: \(x - y \leq 1\), \(x + y \geq 3\), \(x, y \geq 0\)

এক্ষেত্রে সম্ভাব্য অঞ্চল উপরের দিকে অসীম এবং \(Z\) এর মানও অসীম বৃদ্ধি পায়।

৩. অসম্ভব সমাধান (Infeasible Solution)

যদি সীমাবদ্ধতাগুলোর কোনো সাধারণ অঞ্চল না থাকে (অর্থাৎ সম্ভাব্য অঞ্চল শূন্য সেট হয়), তবে সমস্যার কোনো সমাধান নেই। সাধারণত পরস্পরবিরোধী সীমাবদ্ধতার কারণে এমনটি হয়।

উদাহরণ: \(x + y \leq 2\) এবং \(x + y \geq 5\) একসাথে সম্ভব নয়।

যোগাশ্রয়ী প্রোগ্রামের ব্যবহার (Applications)

১. খাদ্য সমস্যা (Diet Problem)

নির্দিষ্ট পুষ্টির চাহিদা পূরণ করতে সর্বনিম্ন খরচে খাদ্যের মিশ্রণ নির্ধারণ। এখানে ভিটামিন, প্রোটিন, ক্যালোরি ইত্যাদি সীমাবদ্ধতা হিসেবে কাজ করে।

২. পরিবহন সমস্যা (Transportation Problem)

বিভিন্ন উৎস থেকে গন্তব্যস্থলে পণ্য পরিবহনে সর্বনিম্ন খরচ নির্ধারণ। এটি যোগাশ্রয়ী প্রোগ্রামের একটি বিশেষ রূপ যেখানে সরবরাহ ও চাহিদার সীমাবদ্ধতা থাকে।

৩. উৎপাদন পরিকল্পনা (Production Planning)

কাঁচামাল, শ্রম, মেশিন সময়ের সীমার মধ্যে কী পরিমাণ পণ্য উৎপাদন করলে লাভ সর্বাধিক হবে তা নির্ধারণ।

৪. বিনিয়োগ পরিকল্পনা (Portfolio Selection)

নির্দিষ্ট ঝুঁকির সীমার মধ্যে সর্বাধিক লাভের জন্য বিভিন্ন ধরনের বিনিয়োগের পরিমাণ নির্ধারণ।

উদাহরণ: খাদ্য সমস্যা

একজন রোগীর প্রতিদিন কমপক্ষে ৮ ইউনিট ভিটামিন A এবং ১০ ইউনিট ভিটামিন C প্রয়োজন। ফল \(X\) এ প্রতি কেজিতে ২ ইউনিট A এবং ১ ইউনিট C আছে, দাম ৩০ টাকা। ফল \(Y\) এ প্রতি কেজিতে ১ ইউনিট A এবং ২ ইউনিট C আছে, দাম ৪০ টাকা। কীভাবে ফল কিনলে সর্বনিম্ন খরচ হবে?

মডেল: সর্বনিম্ন করুন \(Z = 30x + 40y\)

সীমাবদ্ধতা: \(2x + y \geq 8\) (ভিটামিন A), \(x + 2y \geq 10\) (ভিটামিন C), \(x, y \geq 0\)

সংক্ষিপ্ত সারাংশ

  • যোগাশ্রয়ী প্রোগ্রাম: রৈখিক লক্ষ্য ফাংশনকে রৈখিক সীমাবদ্ধতার অধীনে সর্বাধিক বা সর্বনিম্ন করার পদ্ধতি।
  • মৌলিক উপাদন: সিদ্ধান্ত চলক (\(x, y\)), লক্ষ্য ফাংশন (\(Z = ax + by\)), সীমাবদ্ধতা (অসমতা/সমীকরণ), এবং অঋণাত্মকতা শর্ত।
  • লেখচিত্র পদ্ধতি: দ্বিমাত্রিক সমস্যার জন্য—সীমাবদ্ধতাগুলো অঙ্কন করে সম্ভাব্য অঞ্চল নির্ধারণ, কোণা বিন্দুতে \(Z\) এর মান যাচাই করে সর্বাধিক/সর্বনিম্ন নির্ণয়।
  • কোণা বিন্দু উপপাদ্য: সর্বোত্তম মান সর্বদা সম্ভাব্য অঞ্চলের কোণা বিন্দুতে পাওয়া যায়।
  • বিশেষ ক্ষেত্র: একাধিক সমাধান (আইসো-লাভ রেখা বাহুর সমান্তরাল), অসীম সমাধান (অসীম অঞ্চল), অসম্ভব সমাধান (সম্ভাব্য অঞ্চল শূন্য)।
  • ব্যবহার: উৎপাদন, পরিবহন, খাদ্য মিশ্রণ, বিনিয়োগ পরিকল্পনায় ব্যাপক প্রয়োগ।
📌 পরীক্ষার পরামর্শ: লেখচিত্র পদ্ধতিতে সমাধান করার সময় সরলরেখাগুলো সঠিকভাবে অঙ্কন করুন। কোণা বিন্দুর স্থানাঙ্ক সঠিকভাবে নির্ণয় করতে হবে—দুটি রেখার ছেদ বিন্দু সমীকরণ সমাধান করে বের করুন। সম্ভাব্য অঞ্চল সীমাবদ্ধ কিনা তা যাচাই করুন। সর্বশেষে লক্ষ্য ফাংশনের মান কোণা বিন্দুগুলোতে সঠিকভাবে হিসাব করে তুলনা করুন।
অনুশীলনী