লিনিয়ার প্রোগ্রামিং: এটি কী, মডেল, সীমাবদ্ধতা, অ্যাপ্লিকেশনগুলির জন্য - গণিতশাস্ত্র - 2025

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

সাধারণত, ফাংশনটি অনুকূল হয়ে ওঠার জন্য একটি বাস্তব পরিস্থিতি যেমন একটি প্রস্তুতকারকের মুনাফা যার উপকরণ, শ্রম বা যন্ত্রপাতি সীমিত।

চিত্র 1. লিনিয়ার প্রোগ্রামিং ব্যাপকভাবে লাভের অনুকূলকরণের জন্য ব্যবহৃত হয়। সূত্র: পাইকসেলস।

সবচেয়ে সহজ ক্ষেত্রে অন্যতম হল লিনিয়ার ফাংশনটি সর্বাধিক করা যায় যা কেবলমাত্র দুটি ভেরিয়েবলের উপর নির্ভর করে, যাকে সিদ্ধান্ত ভেরিয়েবল বলা হয়। এটি ফর্ম হতে পারে:

জেড = কে ₁ এক্স + কে ₂ ই

কে ₁ এবং কে ₂ ধ্রুবক সহ। এই ফাংশনটি উদ্দেশ্যমূলক ফাংশন হিসাবে পরিচিত। অবশ্যই, এমন পরিস্থিতি রয়েছে যেগুলি আরও জটিল হওয়ার কারণে অধ্যয়নের জন্য দুটি ভেরিয়েবলের যোগ্যতা অর্জন করে:

জেড = কে ₁ এক্স ₁ + কে ₂ এক্স ₂ + কে ₃ এক্স ₃ +…।

এবং সীমাবদ্ধতাগুলিও x এবং y এর সমান রৈখিক সমীকরণ বা বৈষম্যের একটি সিস্টেম দ্বারা গাণিতিকভাবে মডেল করা হয়।

এই সিস্টেমে সমাধানগুলির সেটটিকে সম্ভাব্য সমাধান বা সম্ভাব্য পয়েন্টগুলি বলা হয়। এবং সম্ভাব্য পয়েন্টগুলির মধ্যে কমপক্ষে একটি রয়েছে, যা উদ্দেশ্যগত কার্যটি অনুকূল করে।

লিনিয়ার প্রোগ্রামিংটি স্বাধীনভাবে আমেরিকান পদার্থবিজ্ঞানী এবং গণিতবিদ জর্জ ড্যান্টজিগ (1914-2005) এবং দ্বিতীয় বিশ্বযুদ্ধের পরের রাশিয়ান গণিতবিদ এবং অর্থনীতিবিদ লিওনিড ক্যান্টোরিভিচ (1912-1986) দ্বারা স্বাধীনভাবে বিকশিত হয়েছিল।

সিমপ্লেক্স পদ্ধতি হিসাবে পরিচিত সমস্যা সমাধানের পদ্ধতিটি হ'ল ড্যান্টজিগের মস্তিষ্কপদ, যিনি মার্কিন বিমান বাহিনী, বার্কলে বিশ্ববিদ্যালয় এবং স্ট্যানফোর্ড বিশ্ববিদ্যালয়ের পক্ষে কাজ করেছিলেন।

চিত্র 2. গণিতবিদ জর্জ ড্যান্টজিগ (বাম) এবং লিওনিড ক্যান্টোরোভিচ (ডান)। সূত্র: এফ.জাপাটা।

লিনিয়ার প্রোগ্রামিং মডেল

একটি বাস্তব পরিস্থিতির জন্য উপযুক্ত, লিনিয়ার প্রোগ্রামিং মডেল স্থাপনের জন্য প্রয়োজনীয় উপাদানগুলি হ'ল:

-উদ্দেশ্য ফাংশন

-ডিশন ভেরিয়েবল

- নিষিদ্ধকরণ

অবজেক্টিভ ফাংশনে আপনি যা অর্জন করতে চান তা নির্ধারণ করুন। উদাহরণস্বরূপ, ধরুন আপনি নির্দিষ্ট পণ্য উত্পাদন থেকে প্রাপ্ত লাভ সর্বাধিক করতে চান। তারপরে পণ্যগুলি যে দামে বিক্রি হয় তার দাম অনুসারে "লাভ" ফাংশনটি প্রতিষ্ঠিত হয়।

গাণিতিক ভাষায়, এই ফাংশনটি সংক্ষেপণের স্বরলিপি ব্যবহার করে সংক্ষেপে প্রকাশ করা যেতে পারে:

জেড = ∑k _আমি এক্স _i

এই সমীকরণে, কে _আমি সহগ এবং x _আমি সিদ্ধান্ত ভেরিয়েবল।

সিদ্ধান্তের ভেরিয়েবলগুলি সেই ব্যবস্থার উপাদান যাগুলির নিয়ন্ত্রণ ছিল এবং তাদের মানগুলি ইতিবাচক বাস্তব সংখ্যা। প্রস্তাবিত উদাহরণে, সিদ্ধান্তের ভেরিয়েবলগুলি সর্বোচ্চ লাভ অর্জনের জন্য উত্পাদিত প্রতিটি পণ্যের পরিমাণ।

শেষ অবধি, আমাদের সীমাবদ্ধতা রয়েছে, যা সিদ্ধান্তের ভেরিয়েবলের ক্ষেত্রে লিনিয়ার সমীকরণ বা অসমতা। তারা সমস্যার সীমাবদ্ধতাগুলি বর্ণনা করে, যা পরিচিত এবং এটি হতে পারে, উদাহরণস্বরূপ, উত্পাদন পরিমাণে কাঁচামাল উপলব্ধ।

বিধিনিষেধের প্রকারগুলি

আপনি j = 1 থেকে j = এম থেকে শুরু করে একাধিক এম এর সীমাবদ্ধতা রাখতে পারেন গাণিতিকভাবে নিষেধাজ্ঞাগুলি তিন ধরণের:

1. এ _জ = ∑ এ _আইজে । x _i
2. বি _জে ≥ ∑ বি _আইজি । x _i
3. সি _জে ≤ ∑ সি _আইজি । x _i

প্রথম সীমাবদ্ধতাটি লিনিয়ার সমীকরণের ধরণের এবং এর অর্থ হ'ল A _j, যা পরিচিত, এটি সম্মান করতে হবে।

দুটি অবশিষ্ট বিধিনিষেধ লিনিয়ার বৈষম্য এবং এর অর্থ হ'ল পরিচিত মান B _j এবং C _j কে সম্মান বা ছাড়িয়ে যেতে পারে, যখন প্রদর্শিত প্রতীকটি ≥ (এর চেয়ে বড় বা সমান) বা সম্মানিত বা অতিক্রম না করা হয়, যদি প্রতীক is (অপেক্ষাকৃত ছোট বা সমান).

মডেল উদাহরণ

ব্যবসায়ের প্রশাসন থেকে শুরু করে পুষ্টি পর্যন্ত প্রয়োগের ক্ষেত্রগুলি অত্যন্ত বৈচিত্র্যময় তবে পদ্ধতিটি বোঝার জন্য দুটি ভেরিয়েবল সহ ব্যবহারিক পরিস্থিতির একটি সাধারণ মডেল নীচে প্রস্তাবিত।

একটি স্থানীয় প্যাটাসেরি দুটি বিশেষত্বের জন্য পরিচিত: ব্ল্যাক ফরেস্ট কেক এবং স্যাক্রিপ্যান্টাইন কেক।

এর প্রস্তুতির জন্য তাদের ডিম এবং চিনি প্রয়োজন। কালো বনের জন্য আপনার জন্য 9 টি ডিম এবং 500 গ্রাম চিনি দরকার রয়েছে, যখন স্যাক্রিপ্যান্টিনের জন্য আপনার জন্য 8 টি ডিম এবং 800 গ্রাম চিনি প্রয়োজন। সম্পর্কিত বিক্রয় মূল্যগুলি 8 ডলার এবং 10 ডলার।

সমস্যাটি হ'ল: প্রতিটি প্রকারের কয়টি কেককে তার লাভের সর্বাধিকতা অর্জন করতে হবে, এটি জেনে যে এটির 10 কেজি চিনি এবং 144 টি ডিম রয়েছে?

সিদ্ধান্ত ভেরিয়েবল

সিদ্ধান্তের পরিবর্তনগুলি হ'ল "x" এবং "y", যা প্রকৃত মান গ্রহণ করে:

-x: কালো বন কেকের সংখ্যা

-y: স্যাক্রিপ্যান্টাইন টাইপ কেক।

সীমাবদ্ধতা

এই সীমাবদ্ধতাগুলি এই সত্য দ্বারা প্রদত্ত যে কেকের সংখ্যাটি একটি ধনাত্মক পরিমাণ এবং তাদের প্রস্তুত করার জন্য সীমিত পরিমাণে কাঁচামাল রয়েছে।

সুতরাং, গাণিতিক আকারে, এই বিধিনিষেধগুলি রূপ নেয়:

1. x ≥ 0
2. এবং ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

1 এবং 2 সীমাবদ্ধতা পূর্বে উদ্ভাসিত অ-নেতিবাচক শর্ত গঠন করে এবং উত্থাপিত সমস্ত অসমতা লিনিয়ার। সীমাবদ্ধতায় 3 এবং 4 এর মানগুলি অতিক্রম করা উচিত নয়: 144 ডিম এবং 10 কেজি চিনি।

উদ্দেশ্য ফাংশন

পরিশেষে, উদ্দেশ্য ফাংশনটি হ'ল লাভের জন্য যখন "এক্স" পরিমাণে কৃষ্ণাঙ্গ বন কেকের পরিমাণ এবং "ওয়াই" পরিমাণ স্যাক্রিপ্যান্টাইনস তৈরি করা হয়। এটি তৈরি করা কেকের পরিমাণ দ্বারা এবং প্রতিটি ধরণের জন্য যোগ করে দামকে গুণিত করে তৈরি করা হয়। এটি একটি লিনিয়ার ফাংশন যা আমরা জি (x, y) কল করব:

জি = 8 এক্স + 10 এ

সমাধান পদ্ধতি

বিভিন্ন সমাধান পদ্ধতির মধ্যে গ্রাফিকাল পদ্ধতি, সিমপ্লেক্স অ্যালগরিদম এবং ইন্টিরির পয়েন্ট পদ্ধতি অন্তর্ভুক্ত কয়েকটি নাম অন্তর্ভুক্ত।

- গ্রাফিক বা জ্যামিতিক পদ্ধতি

পূর্ববর্তী বিভাগের মতো আপনার যখন দ্বি-পরিবর্তনশীল সমস্যা হয়, তখন সীমাবদ্ধতাগুলি XY বিমানের একটি বহুভুজ অঞ্চল নির্ধারণ করে, যাকে সম্ভাব্য অঞ্চল বা সম্ভাব্য অঞ্চল বলে।

চিত্র 3. সম্ভাব্য অঞ্চল, যেখানে অপ্টিমাইজেশান সমস্যার সমাধান পাওয়া যায়। সূত্র: উইকিমিডিয়া কমন্স।

এই অঞ্চলটি সীমাবদ্ধতার লাইন ব্যবহার করে নির্মিত হয়েছে, যা কেবলমাত্র সাম্যতার চিহ্ন দিয়ে কাজ করে বিধিনিষেধের বৈষম্য থেকে প্রাপ্ত লাইন।

মুনাফা অনুকূল করতে চায় এমন বেকারিগুলির ক্ষেত্রে, সীমাবদ্ধতাগুলি হ'ল:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

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

ভাগ্যক্রমে, প্যাস্ট্রি সমস্যার জন্য সম্ভাব্য অঞ্চলটি খালি নয়, আমাদের এটি নীচে রয়েছে।

চিত্র ৪. প্যাস্ট্রি সমস্যার সম্ভাব্য অঞ্চল। 0 লাভের সাথে লাইনটি উত্সটি অতিক্রম করে। সূত্র: জিওজেব্রা সহ এফ.জাপাটা।

অনুকূল সমাধান, যদি এটি বিদ্যমান থাকে তবে বস্তুনিষ্ঠ কার্যের সাহায্যে পাওয়া যায়। উদাহরণস্বরূপ, সর্বাধিক মুনাফা জি সন্ধান করার সময়, আমাদের নীচের লাইনটি রয়েছে, যাকে আইসো-লাভের লাইন বলা হয়:

জি = কে ₁ এক্স + কে ₂ ওয়াই → ওয়াই =-কে ₁ এক্স / কে ₂ + জি / কে ₂

এই রেখার সাহায্যে আমরা সমস্ত জোড়া (x, y) পাই যা প্রদত্ত লাভ জি সরবরাহ করে, তাই জি এর মান অনুসারে লাইনগুলির একটি পরিবার রয়েছে তবে সমস্তগুলি একই opeাল-কে ₁ / কে _{2 দিয়ে থাকে}, সুতরাং সেগুলি হয় সমান্তরাল রেখা.

অনুকূল সমাধান

এখন, এটি দেখানো যেতে পারে যে একটি লিনিয়ার সমস্যার অনুকূল সমাধান হ'ল সম্ভাবনাময় অঞ্চলের একটি চূড়ান্ত বিন্দু বা শীর্ষস্থান। সুতরাং:

যদি উত্সের নিকটতম রেখার ব্যবহারযোগ্য অঞ্চলের সাথে একটি সম্পূর্ণ বিভাগ থাকে তবে বলা হয় যে এখানে অসীম সমাধান রয়েছে। আইসো-প্রফিট লাইনের opeাল অঞ্চলটি সীমাবদ্ধ অন্য যে কোনও লাইনের সমান হলে এই কেসটি ঘটে।

আমাদের প্যাস্ট্রিের জন্য, প্রার্থীর উল্লম্বগুলি হ'ল এ, বি এবং সি are

- ড্যান্টজিগের সিম্পলেক্স পদ্ধতি

গ্রাফিকাল বা জ্যামিতিক পদ্ধতি দুটি ভেরিয়েবলের জন্য প্রযোজ্য। যাইহোক, যখন আরও তিনটি ভেরিয়েবল থাকে তখন আরও জটিল হয় এবং বৃহত সংখ্যক ভেরিয়েবলের জন্য ব্যবহার করা অসম্ভব।

দুটিরও বেশি ভেরিয়েবলের সাথে সমস্যাগুলি মোকাবেলা করার সময়, সিমপ্লেক্স পদ্ধতিটি ব্যবহার করা হয়, যা উদ্দেশ্যমূলক ক্রিয়াকলাপগুলি অনুকূল করতে একাধিক অ্যালগরিদম নিয়ে গঠিত। ম্যাট্রিক এবং সহজ পাটিগণিতগুলি প্রায়শই গণনাগুলি চালাতে ব্যবহৃত হয়।

সিমপ্লেক্স পদ্ধতিটি একটি সম্ভাব্য সমাধান চয়ন করে এবং এটি সর্বোত্তম কিনা তা পরীক্ষা করে শুরু হয়। যদি এটি হয় তবে আমরা ইতিমধ্যে সমস্যার সমাধান করেছি, তবে এটি যদি না হয় তবে আমরা অপ্টিমাইজেশনের কাছাকাছি একটি সমাধানের দিকে এগিয়ে চলেছি। যদি সমাধানটি বিদ্যমান থাকে তবে অ্যালগরিদম এটি কয়েকটি চেষ্টা করে খুঁজে বের করে।

অ্যাপ্লিকেশন

ব্যয় হ্রাস এবং লাভ বাড়ানোর ক্ষেত্রে সর্বোত্তম সিদ্ধান্ত নেওয়ার জন্য লিনিয়ার এবং অ-লিনিয়ার প্রোগ্রামিং অনেক ক্ষেত্রে প্রয়োগ করা হয়, যা সর্বদা আর্থিক হয় না, যেহেতু সেগুলি সময়মতো পরিমাপ করা যায়, উদাহরণস্বরূপ, আপনি যদি প্রয়োজনীয় সময়কে ন্যূনতম করতে চান বিভিন্ন ক্রিয়াকলাপ পরিচালনা করতে।

এখানে কিছু ক্ষেত্র রয়েছে:

-বিপণনে এটি নির্দিষ্ট পণ্যের বিজ্ঞাপন প্রচারের জন্য মিডিয়া (সামাজিক নেটওয়ার্ক, টেলিভিশন, প্রেস এবং অন্যান্য) এর সর্বোত্তম সংমিশ্রণ সন্ধান করতে ব্যবহৃত হয়।

- কোনও সংস্থা বা কারখানার কর্মীদের পর্যাপ্ত কাজ বরাদ্দের জন্য বা তাদের সময়সূচী।

- সবচেয়ে পুষ্টিকর খাবার বাছাই এবং গবাদিপশু ও হাঁস-মুরগির শিল্পগুলিতে সর্বনিম্ন ব্যয়ে।

সমাধান ব্যায়াম

- অনুশীলনী 1

পূর্ববর্তী বিভাগগুলিতে উত্থিত লিনিয়ার প্রোগ্রামিং মডেলটি গ্রাফিকভাবে সমাধান করুন।

সমাধান

সমস্যাটিতে নির্দিষ্ট হওয়া বিধিনিষেধের সিস্টেম দ্বারা নির্ধারিত মানগুলির সেট গ্রাফ করা প্রয়োজন:

1. x ≥ 0
2. এবং ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

1 এবং 2 অসমতার দ্বারা প্রদত্ত অঞ্চলটি কার্টেসিয়ান বিমানের প্রথম চতুর্ভুজটির সাথে মিলে যায়। 3 এবং 4 বৈষম্য সম্পর্কে, আমরা সীমাবদ্ধতার রেখাগুলি সন্ধান করে শুরু করি:

9x + 8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

সম্ভাব্য অঞ্চলটি একটি চতুর্ভুজ যা এর শিখর বিন্দু A, B, C এবং D হয় vert

সর্বনিম্ন লাভ 0 হয়, সুতরাং 8x + 10y = 0 লাইনটি নিম্ন সীমা এবং আইসো-লাভের লাইনে linesাল -8/10 = - 0.8 রয়েছে।

এই মানটি অন্যান্য সীমাবদ্ধতার রেখার slালু থেকে পৃথক এবং সম্ভাব্য অঞ্চলটি সীমাবদ্ধ হওয়ায় অনন্য সমাধান বিদ্যমান solution

চিত্র 5. অনুশীলন 1 এর গ্রাফিকাল সমাধান, সম্ভাব্য অঞ্চল এবং সমাধান পয়েন্ট সি বর্ণিত অঞ্চলের একটি শীর্ষে অবস্থিত দেখায়। সূত্র: এফ.জাপাটা।

এই সমাধানটি slাল -0.8 এর একটি লাইনের সাথে মিলে যায় যা A, B বা C বিন্দুগুলির মধ্য দিয়ে যায়, যার স্থানাঙ্কগুলি:

এ (11; 5.625)

বি (0; 12.5)

সি (16, 0)

সন্তোষজনক সমাধান

আমরা এই প্রতিটি পয়েন্টের জন্য জি এর মান গণনা করি:

- (11; 5.625): জি _এ = 8 এক্স 11 + 10 এক্স 5.625 = 144.25

- (0; 12.5): জি _বি = 8 এক্স 0 + 10 এক্স 12.5 = 125

- (16, 0): জি _সি = 8 এক্স 16 + 10 এক্স 0 = 128

সর্বাধিক মুনাফা পাওয়া যায় 11 কালো বন কেক এবং 5,625 স্যাক্রিপ্যান্টাইন কেক উত্পাদন। এই সমাধানটি সফ্টওয়্যারটির মাধ্যমে পাওয়া একটির সাথে একমত।

- অনুশীলন 2

এক্সেল বা লিব্রেফিস ক্যালকের মতো স্লভার ফাংশন উপলভ্য সলভার ফাংশনটি ব্যবহার করে আগের অনুশীলনের ফলাফল যাচাই করুন, যা লিনিয়ার প্রোগ্রামিংয়ে অপ্টিমাইজেশনের জন্য সিম্প্লেক্স অ্যালগরিদমকে অন্তর্ভুক্ত করে।

সমাধান

চিত্র 6. লিবার অফিস ক্যালক স্প্রেডশিটের মাধ্যমে অনুশীলন 1 থেকে সমাধানের বিশদ বিবরণ। সূত্র: এফ.জাপাটা।

চিত্র 7. লিবার অফিস ক্যালক স্প্রেডশিটের মাধ্যমে অনুশীলন 1 থেকে সমাধানের বিশদ। সূত্র: এফ.জাপাটা।

তথ্যসূত্র

1. উজ্জ্বল। রৈখিক প্রোগ্রামিং. থেকে উদ্ধার: brilliant.org।
2. এপেন, জি। 2000. অ্যাডমিনিস্ট্রেটিভ সায়েন্সে অপারেশনস রিসার্চ। ৫ ম। সংস্করণ। প্রেন্টিস হল.
3. হিউসলার, ই। 1992. পরিচালনা ও অর্থনীতি সম্পর্কিত গণিত 2nd। সংস্করণ। গ্রুপো সম্পাদকীয় আইবেরোমরিকানা।
4. হিরু.ইউস রৈখিক প্রোগ্রামিং. থেকে উদ্ধার: hiru.eus।
5. উইকিপিডিয়া। রৈখিক প্রোগ্রামিং. থেকে উদ্ধার: এস। উইকিপিডিয়া.অর্গ।