উদ্দেশ্য ফাংশনের সর্বোত্তম মান বলা হয়। গ্রাফিক্যাল পদ্ধতি ব্যবহার করে লিনিয়ার প্রোগ্রামিং সমস্যা সমাধান করা

আসুন আমরা সমতলে রৈখিক অসমতার সিস্টেমের সম্ভাব্য সমাধানের একটি সেট তৈরি করি এবং জ্যামিতিকভাবে উদ্দেশ্য ফাংশনের ন্যূনতম মান খুঁজে পাই।

আমরা x 1 x 2 স্থানাঙ্ক সিস্টেমে সরল রেখা তৈরি করি

আমরা সিস্টেম দ্বারা সংজ্ঞায়িত অর্ধ-বিমান খুঁজে. যেহেতু সিস্টেমের অসমতা সংশ্লিষ্ট অর্ধ-বিন্দুর যেকোন বিন্দুর জন্য সন্তুষ্ট, তাই যেকোনো একটি বিন্দুর জন্য তাদের পরীক্ষা করা যথেষ্ট। আমরা পয়েন্ট (0;0) ব্যবহার করি। এর স্থানাঙ্কগুলিকে সিস্টেমের প্রথম অসমতায় প্রতিস্থাপন করা যাক। কারণ , তারপর অসমতা একটি অর্ধ-সমতলকে সংজ্ঞায়িত করে যাতে বিন্দু (0;0) থাকে না। আমরা একইভাবে অবশিষ্ট অর্ধ-বিমানকে সংজ্ঞায়িত করি। আমরা ফলস্বরূপ অর্ধ-বিমানগুলির সাধারণ অংশ হিসাবে সম্ভাব্য সমাধানগুলির সেট খুঁজে পাই - এটি ছায়াযুক্ত এলাকা।

আমরা একটি ভেক্টর এবং এটির সাথে একটি শূন্য স্তরের রেখা তৈরি করি।

সরলরেখা (5) ভেক্টরের দিকে চলছি এবং আমরা দেখতে পাচ্ছি যে এই অঞ্চলের সর্বাধিক বিন্দুটি সরলরেখা (3) এবং সরলরেখা (2) এর ছেদকের A বিন্দুতে থাকবে। আমরা সমীকরণ সিস্টেমের সমাধান খুঁজে পাই:

এর মানে আমরা পয়েন্ট পেয়েছি (13;11) এবং।

সরলরেখা (5) ভেক্টরের দিকে সরানো এবং আমরা দেখতে পাচ্ছি যে এই অঞ্চলের সর্বনিম্ন বিন্দুটি সরলরেখা (1) এবং সরলরেখা (4) এর ছেদকের বি বিন্দুতে থাকবে। আমরা সমীকরণ সিস্টেমের সমাধান খুঁজে পাই:

এর মানে আমরা পয়েন্ট পেয়েছি (6;6) এবং।

2. একটি আসবাবপত্র কোম্পানি সম্মিলিত ক্যাবিনেট এবং কম্পিউটার টেবিল তৈরি করে। তাদের উৎপাদন কাঁচামালের প্রাপ্যতা (উচ্চ মানের বোর্ড, ফিটিংস) এবং তাদের প্রক্রিয়াকরণের মেশিনের অপারেটিং সময় দ্বারা সীমিত। প্রতিটি মন্ত্রিসভা বোর্ডের 5 m2 প্রয়োজন, একটি টেবিলের জন্য - 2 m2। একটি ক্যাবিনেটের জন্য জিনিসপত্রের দাম $10 এবং একটি টেবিলের জন্য $8৷ কোম্পানি তার সরবরাহকারীদের কাছ থেকে প্রতি মাসে 600 m2 বোর্ড এবং $2,000 মূল্যের আনুষাঙ্গিক পেতে পারে। প্রতিটি ক্যাবিনেটের জন্য 7 ঘন্টা মেশিন অপারেশন প্রয়োজন, এবং টেবিলের জন্য 3 ঘন্টা প্রয়োজন। প্রতি মাসে মেশিনের মাত্র 840 অপারেটিং ঘন্টা ব্যবহার করা সম্ভব।

একটি মন্ত্রিসভা যদি $100 লাভ করে এবং প্রতিটি ডেস্ক $50 আনে তবে লাভকে সর্বাধিক করার জন্য একটি কোম্পানির প্রতি মাসে কতগুলি সংমিশ্রণ ক্যাবিনেট এবং কম্পিউটার টেবিল তৈরি করা উচিত?

• 1. রচনা করুন গানিতিক প্রতিমাণসমস্যা এবং সিমপ্লেক্স পদ্ধতি ব্যবহার করে এটি সমাধান করুন।
• 2. দ্বৈত সমস্যার একটি গাণিতিক মডেল তৈরি করুন, আসলটির সমাধানের উপর ভিত্তি করে এর সমাধান লিখুন।
• 3. ব্যবহৃত সম্পদের অভাবের মাত্রা স্থাপন করুন এবং সর্বোত্তম পরিকল্পনার লাভজনকতাকে ন্যায়সঙ্গত করুন।
• 4. প্রতিটি ধরনের সম্পদের ব্যবহারের উপর নির্ভর করে উৎপাদন আউটপুট আরও বাড়ানোর সম্ভাবনাগুলি অন্বেষণ করুন।
• 5. একটি নতুন ধরণের পণ্য প্রবর্তনের সম্ভাব্যতা মূল্যায়ন করুন - বুকশেলফ, যদি একটি শেলফ তৈরিতে 1 মি 2 বোর্ড এবং আনুষাঙ্গিক $5 মূল্যের খরচ হয় এবং 0.25 ঘন্টা মেশিন অপারেশন এবং বিক্রয় থেকে লাভ ব্যয় করতে হয় একটি শেলফ $20।
• 1. আসুন এই সমস্যার জন্য একটি গাণিতিক মডেল তৈরি করি:

আসুন x 1 দ্বারা ক্যাবিনেটের উৎপাদনের আয়তন এবং x 2 দ্বারা টেবিলের উৎপাদনের আয়তন বোঝাই। আসুন সীমাবদ্ধতার একটি সিস্টেম এবং একটি লক্ষ্য ফাংশন তৈরি করি:

আমরা সিমপ্লেক্স পদ্ধতি ব্যবহার করে সমস্যার সমাধান করি। আসুন এটিকে ক্যানোনিকাল আকারে লিখি:

আসুন একটি টেবিল আকারে টাস্ক ডেটা লিখি:

1 নং টেবিল

কারণ এখন সমস্ত ডেল্টা শূন্যের চেয়ে বড়, তারপর লক্ষ্য ফাংশনের মান f এর আরও বৃদ্ধি করা অসম্ভব এবং আমরা একটি সর্বোত্তম পরিকল্পনা পেয়েছি।

শৃঙ্খলার উপর নিয়ন্ত্রণ কাজ:

"অনুকূল সমাধানের পদ্ধতি"

বিকল্প নং 8

1. সিদ্ধান্ত নিন গ্রাফিকাল পদ্ধতিলিনিয়ার প্রোগ্রামিং সমস্যা। প্রদত্ত সীমাবদ্ধতা সহ ফাংশনের সর্বাধিক এবং সর্বনিম্ন খুঁজুন:

,

.

সমাধান

বিধিনিষেধের সিস্টেমের অধীনে উদ্দেশ্য ফাংশনের সর্বনিম্ন মান এবং সর্বোচ্চটি খুঁজে বের করা প্রয়োজন:

9x 1 +3x 2 ≥30, (1)

X 1 + x 2 ≤4, (2)

x 1 + x 2 ≤8, (3)

আসুন আমরা সম্ভাব্য সমাধানগুলির একটি অঞ্চল তৈরি করি, যেমন চলুন বৈষম্যের ব্যবস্থাকে গ্রাফিকভাবে সমাধান করি। এটি করার জন্য, আমরা প্রতিটি সরল রেখা তৈরি করি এবং অসমতা দ্বারা সংজ্ঞায়িত অর্ধ-বিমানগুলিকে সংজ্ঞায়িত করি (অর্ধ-বিমানগুলি একটি প্রাইম দ্বারা নির্দেশিত হয়)।

অর্ধ-বিমানগুলির ছেদ এমন একটি এলাকা হবে যার পয়েন্টগুলির স্থানাঙ্কগুলি সমস্যার সীমাবদ্ধতার সিস্টেমের অসমতাকে সন্তুষ্ট করে। সমাধান বহুভুজের ক্ষেত্রফলের সীমানা চিহ্নিত করা যাক।

ফাংশনের মান F = 0: F = 2x 1 +3x 2 = 0 এর সাথে সঙ্গতিপূর্ণ একটি সরল রেখা তৈরি করা যাক। অবজেক্টিভ ফাংশনের সহগ দ্বারা গঠিত গ্রেডিয়েন্ট ভেক্টর F(X) এর ন্যূনতমকরণের দিক নির্দেশ করে। ভেক্টরের শুরু বিন্দু (0; 0), শেষটি বিন্দু (2; 3)। আমরা একটি সমান্তরাল পদ্ধতিতে এই লাইন সরানো হবে. যেহেতু আমরা ন্যূনতম সমাধানে আগ্রহী, তাই আমরা সরলরেখাটি সরাতে থাকি যতক্ষণ না এটি প্রথমে নির্ধারিত এলাকায় স্পর্শ করে। গ্রাফে, এই সরল রেখাটি একটি বিন্দুযুক্ত রেখা দ্বারা নির্দেশিত।

সোজা
অঞ্চলটিকে C বিন্দুতে ছেদ করে। যেহেতু বিন্দু C রেখা (4) এবং (1) ছেদ করার ফলে প্রাপ্ত হয়, তাই এর স্থানাঙ্কগুলি এই রেখাগুলির সমীকরণগুলিকে সন্তুষ্ট করে:
.

সমীকরণের সিস্টেমটি সমাধান করার পরে, আমরা পাই: x 1 = 3.3333, x 2 = 0।

কিভাবে আমরা উদ্দেশ্য ফাংশনের সর্বনিম্ন মান খুঁজে পেতে পারি:

চলো বিবেচনা করি লক্ষ্য ফাংশনকাজ .

F = 0 ফাংশনের মানের সাথে সঙ্গতিপূর্ণ একটি সরল রেখা তৈরি করা যাক: F = 2x 1 +3x 2 = 0। অবজেক্টিভ ফাংশনের সহগ দ্বারা গঠিত গ্রেডিয়েন্ট ভেক্টর F(X) এর সর্বাধিকীকরণের দিক নির্দেশ করে। ভেক্টরের শুরু বিন্দু (0; 0), শেষটি বিন্দু (2; 3)। আমরা এই সরল রেখাটিকে সমান্তরালভাবে সরাব। যেহেতু আমরা সর্বাধিক সমাধানে আগ্রহী, তাই আমরা মনোনীত এলাকার শেষ স্পর্শ না হওয়া পর্যন্ত সরলরেখাটি সরাই। গ্রাফে, এই সরল রেখাটি একটি বিন্দুযুক্ত রেখা দ্বারা নির্দেশিত।

সোজা
অঞ্চলটিকে বি বিন্দুতে ছেদ করে। যেহেতু বিন্দু বি রেখা (2) এবং (3) এর ছেদ করার ফলে প্রাপ্ত হয়, তাই এর স্থানাঙ্কগুলি এই রেখাগুলির সমীকরণগুলিকে সন্তুষ্ট করে:

.

কিভাবে আমরা উদ্দেশ্য ফাংশনের সর্বোচ্চ মান খুঁজে পেতে পারি: .

উত্তর:
এবং
.

2 . সিমপ্লেক্স পদ্ধতি ব্যবহার করে একটি লিনিয়ার প্রোগ্রামিং সমস্যা সমাধান করুন:

.

সমাধান

চলুন, সিমপ্লেক্স মেথড ব্যবহার করে একটি সিমপ্লেক্স টেবিল ব্যবহার করে সরাসরি লিনিয়ার প্রোগ্রামিং সমস্যার সমাধান করা যাক।

উদ্দেশ্য ফাংশনের সর্বনিম্ন মান নির্ধারণ করা যাক
নিম্নলিখিত শর্তাবলীর অধীনে - সীমাবদ্ধতা:
.

প্রথম রেফারেন্স প্ল্যান তৈরি করতে, আমরা অতিরিক্ত ভেরিয়েবল প্রবর্তন করে অসমতার সিস্টেমকে সমীকরণের সিস্টেমে কমিয়ে দিই।

অর্থের 1ম অসমতায় (≥) আমরা মৌলিক চলকটি প্রবর্তন করি এক্স 3 একটি বিয়োগ চিহ্ন সহ। অর্থের 2য় অসমতায় (≤) আমরা মৌলিক চলকটি প্রবর্তন করি এক্স 4 . অর্থের 3য় অসমতায় (≤) আমরা মৌলিক চলক x 5 প্রবর্তন করি।

কৃত্রিম ভেরিয়েবল প্রবর্তন করা যাক : ১ম সমতায় আমরা একটি পরিবর্তনশীল প্রবর্তন করি এক্স 6 ;

সমস্যাটিকে ন্যূনতম সেট করতে, আমরা উদ্দেশ্য ফাংশনটি নিম্নরূপ লিখি: .

উদ্দেশ্য ফাংশনে প্রবর্তিত কৃত্রিম ভেরিয়েবল ব্যবহারের জন্য, এম এর একটি তথাকথিত দণ্ড আরোপ করা হয়, একটি খুব বড় ধনাত্মক সংখ্যা যা সাধারণত নির্দিষ্ট করা হয় না।

ফলস্বরূপ ভিত্তিকে কৃত্রিম বলা হয়, এবং সমাধান পদ্ধতিকে কৃত্রিম ভিত্তি পদ্ধতি বলা হয়।

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

সমীকরণ থেকে আমরা কৃত্রিম ভেরিয়েবল প্রকাশ করি: x 6 = 4-x 1 -x 2 +x 3, যাকে আমরা উদ্দেশ্যমূলক ফাংশনে প্রতিস্থাপন করি: বা।

সহগ ম্যাট্রিক্স
এই সমীকরণ সিস্টেমের ফর্ম আছে:
.

চলুন মৌলিক ভেরিয়েবলের সমীকরণের সিস্টেমটি সমাধান করি: এক্স 6 , এক্স 4 , এক্স 5.

ধরে নিই যে ফ্রি ভেরিয়েবলগুলি 0 এর সমান, আমরা প্রথমটি পাই রেফারেন্স পরিকল্পনা:

X1 = (0,0,0,2,10,4)

মৌলিক সমাধানকে গ্রহণযোগ্য বলা হয় যদি এটি অ-নেতিবাচক হয়।

		এক্স 1	এক্স 2	এক্স 3	এক্স 4	এক্স 5	এক্স 6
এক্স 6
এক্স 4
এক্স 5

বর্তমান রেফারেন্স প্ল্যানটি সর্বোত্তম নয় কারণ সূচক লাইনে ইতিবাচক সহগ রয়েছে৷ অগ্রণী কলাম হিসাবে, আমরা x 2 ভেরিয়েবলের সাথে সম্পর্কিত কলামটি বেছে নেব, যেহেতু এটিই বৃহত্তম সহগ। এর মান গণনা করা যাক ডি i এবং তাদের থেকে আমরা সবচেয়ে ছোটটি বেছে নিই: মিনিট (4: 1, 2: 2, 10: 2) = 1।

অতএব, ২য় লাইনটি অগ্রণী।

সমাধানকারী উপাদানটি (2) এর সমান এবং এটি অগ্রণী কলাম এবং অগ্রণী সারির সংযোগস্থলে অবস্থিত।

		এক্স 1	এক্স 2	এক্স 3	এক্স 4	এক্স 5	এক্স 6
এক্স 6
এক্স 4
এক্স 5

আমরা সিমপ্লেক্স টেবিলের পরবর্তী অংশ গঠন করি। পরিবর্তনশীল x 4 এর পরিবর্তে, প্ল্যান 1 ভেরিয়েবল x 2 অন্তর্ভুক্ত করবে।

প্ল্যান 1 এ ভেরিয়েবল x 2 এর সাথে সম্পর্কিত সারিটি প্ল্যান 0 এর সারির x 4 এর সমস্ত উপাদানকে সমাধানকারী উপাদান RE = 2 দ্বারা ভাগ করে পাওয়া যায়। সমাধানকারী উপাদানের জায়গায় আমরা 1 পাই। x 2 কলামের অবশিষ্ট কোষগুলিতে আমরা শূন্য লিখি।

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

		এক্স 1	এক্স 2	এক্স 3	এক্স 4	এক্স 5	এক্স 6
এক্স 6
এক্স 2
এক্স 5
		1 1/2 +1 1/2 M

বর্তমান রেফারেন্স প্ল্যানটি সর্বোত্তম নয় কারণ সূচক সারিতে ইতিবাচক সহগ রয়েছে৷ অগ্রণী কলাম হিসাবে, আমরা x 1 ভেরিয়েবলের সাথে সম্পর্কিত কলামটি বেছে নেব, যেহেতু এটিই বৃহত্তম সহগ। এর মান গণনা করা যাক ডি iবিভাজনের ভাগফল হিসাবে সারি দ্বারা: এবং তাদের থেকে আমরা সবচেয়ে ছোটটি বেছে নিই: মিনিট (3: 1 1 / 2, -, 8: 2) = 2।

অতএব, ১ম লাইনটি অগ্রণী।

সমাধানকারী উপাদানটি (1 1/2) এর সমান এবং এটি অগ্রণী কলাম এবং অগ্রণী সারির সংযোগস্থলে অবস্থিত।

		এক্স 1	এক্স 2	এক্স 3	এক্স 4	এক্স 5	এক্স 6
এক্স 6		1 1 / 2
এক্স 2
এক্স 5
		-1 1 / 2 +1 1 / 2 এম

আমরা সিমপ্লেক্স টেবিলের পরবর্তী অংশ গঠন করি। পরিবর্তনশীল x 6-এর পরিবর্তে, প্ল্যান 2-এ x 1 ভেরিয়েবল অন্তর্ভুক্ত থাকবে।

আমরা একটি নতুন সিমপ্লেক্স টেবিল পাই:

		এক্স 1	এক্স 2	এক্স 3	এক্স 4	এক্স 5	এক্স 6
এক্স 1
এক্স 2
এক্স 5

সূচক স্ট্রিং মানগুলির মধ্যে কোন ইতিবাচক মান নেই। অতএব, এই টেবিলটি সমস্যার জন্য সর্বোত্তম পরিকল্পনা নির্ধারণ করে।

সিমপ্লেক্স টেবিলের চূড়ান্ত সংস্করণ:

		এক্স 1	এক্স 2	এক্স 3	এক্স 4	এক্স 5	এক্স 6
এক্স 1
এক্স 2
এক্স 5

যেহেতু সর্বোত্তম সমাধানে কোন কৃত্রিম ভেরিয়েবল নেই (তারা শূন্যের সমান), এই সমাধানটি গ্রহণযোগ্য।

সর্বোত্তম পরিকল্পনাটি নিম্নরূপ লেখা যেতে পারে: x 1 = 2, x 2 = 2:।

উত্তর:
,
.

3. থ্রি ফ্যাট মেন কোম্পানি শহরের বিভিন্ন স্থানে অবস্থিত তিনটি গুদাম থেকে তিনটি দোকানে টিনজাত মাংস পৌঁছে দেয়। গুদামগুলিতে উপলব্ধ টিনজাত খাবারের স্টক, সেইসাথে স্টোর অর্ডারের পরিমাণ এবং ডেলিভারির হার (প্রচলিত আর্থিক ইউনিটে) পরিবহন টেবিলে উপস্থাপন করা হয়।

একটি পরিবহন পরিকল্পনা খুঁজুন যা সর্বনিম্ন আর্থিক খরচ প্রদান করে ("উত্তর পশ্চিম কোণ" পদ্ধতি ব্যবহার করে প্রাথমিক পরিবহন পরিকল্পনা সম্পাদন করুন)।

সমাধান

আসুন আমরা সমস্যার সমাধানযোগ্যতার জন্য প্রয়োজনীয় এবং পর্যাপ্ত শর্ত পরীক্ষা করি:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

ভারসাম্য শর্ত পূরণ করা হয়. সমান চাহিদা সরবরাহ করে। অতএব, মডেল পরিবহন সমস্যাবন্ধ.

ডিস্ট্রিবিউশন টেবিলে প্রাথমিক তথ্য প্রবেশ করা যাক।

চাহিদা

উত্তর-পশ্চিম কোণার পদ্ধতি ব্যবহার করে, আমরা পরিবহন সমস্যার প্রথম রেফারেন্স পরিকল্পনা তৈরি করব।

পরিকল্পনাটি উপরের বাম কোণ থেকে পূরণ করতে শুরু করে।

প্রয়োজনীয় উপাদান হল 4। এই উপাদানটির জন্য, ইনভেন্টরি হল 300টি, প্রয়োজনীয়তা হল 250টি। যেহেতু ন্যূনতম হল 250, আমরা এটি বিয়োগ করি:।

			300 - 250 = 50
250 - 250 = 0

প্রয়োজনীয় উপাদানটি 2 এর সমান। এই উপাদানটির জন্য, জায় 50, প্রয়োজনীয়তা 400। যেহেতু সর্বনিম্ন 50, আমরা এটি বিয়োগ করি:।

			50 - 50 = 0
	400 - 50 = 350

প্রয়োজনীয় উপাদান হল 5। এই উপাদানটির জন্য, ইনভেন্টরিগুলি হল 300, প্রয়োজনীয়তা হল 350৷ যেহেতু সর্বনিম্ন হল 300, আমরা এটি বিয়োগ করি:

			300 - 300 = 0
	350 - 300 = 50

প্রয়োজনীয় উপাদান হল 3৷ এই উপাদানটির জন্য, জায় হল 200টি, প্রয়োজনীয়তা হল 50৷ যেহেতু সর্বনিম্ন হল 50, আমরা এটি বিয়োগ করি:

			200 - 50 = 150
	50 - 50 = 0

প্রয়োজনীয় উপাদান হল 6৷ এই উপাদানটির জন্য, ইনভেন্টরিগুলি হল 150, প্রয়োজনীয়তা হল 150৷ যেহেতু সর্বনিম্ন হল 150, তাই আমরা এটি বিয়োগ করি:

			150 - 150 = 0
		150 - 150 = 0

চাহিদা

ল্যাবরেটরি কাজ নং 1. লিনিয়ার প্রোগ্রামিং সমস্যা সমাধান

কাজের লক্ষ্যগ্রাফিক্যাল, সিমপ্লেক্স এবং এক্সেল পদ্ধতি ব্যবহার করে লিনিয়ার প্রোগ্রামিং সমস্যা সমাধানে দক্ষতা অর্জন করা।

রৈখিক প্রোগ্রামিংয়ের সমস্যা হল রৈখিক সীমাবদ্ধতার উপস্থিতিতে একটি রৈখিক ফাংশনের সর্বাধিক বা সর্বনিম্ন মান খুঁজে বের করার উপায়গুলি অধ্যয়ন করা। একটি উদ্দেশ্য ফাংশন একটি ফাংশন যার সর্বোচ্চ বা সর্বনিম্ন মান পাওয়া যায়। ভেরিয়েবলের মানগুলির সেট যেখানে সর্বাধিক বা সর্বনিম্ন মানগুলি অর্জন করা হয় তাকে একটি সর্বোত্তম সমাধান (অনুকূল পরিকল্পনা) বলা হয়, সীমাবদ্ধতাগুলিকে সন্তুষ্ট করে এমন অন্য কোনও মানগুলির সেটকে একটি গ্রহণযোগ্য সমাধান (অনুমোদিত পরিকল্পনা) বলা হয়।

জ্যামিতিক সমাধান পদ্ধতি আমিআসুন একটি উদাহরণ ব্যবহার করে লিনিয়ার প্রোগ্রামিং সমস্যাগুলি দেখি।

উদাহরণ. উদ্দেশ্য ফাংশনের সর্বোচ্চ মান খুঁজুন এল=2এক্স 1 +2এক্সপ্রদত্ত বিধিনিষেধের অধীনে 2

সমাধান।আসুন আমরা সীমাবদ্ধতার সিস্টেমের সমাধান ডোমেন তৈরি করি, অসমতার চিহ্নগুলিকে সঠিক সমতা চিহ্নগুলিতে পরিবর্তন করি:

l 1: 3এক্স 1 -2এক্স 2 +6=0,

l 2: 3এক্স 1 +এক্স 2 -3=0,

l 3:এক্স 1 -3=0.

ডিসঙ্গে

2 0 1 3 এক্স 1

(l 1) (l 3)

সোজা l 1 সমতলকে ভাগ করে এক্সসম্পর্কিত এদুটি অর্ধ-বিমানে, যেখান থেকে আপনাকে এমন একটি বেছে নিতে হবে যা সিস্টেমের প্রথম অসমতাকে সন্তুষ্ট করে (3)। এটি করতে, এর টি নিতে দিন. সম্পর্কিত(0; 0) এবং এটিকে অসমতায় প্রতিস্থাপন করুন। যদি এটি সত্য হয়, তাহলে আপনাকে তথাকথিত অবস্থিত সরলরেখা থেকে অর্ধ-বিমানকে ছায়া দিতে হবে। সম্পর্কিত(0; 0)। সোজা লাইন দিয়ে একই কাজ করুন। l 2 এবং l 3. অসমতার সমাধানের ডোমেইন (3) একটি বহুভুজ এবিসিডি. সমতলে প্রতিটি পয়েন্টের জন্য ফাংশন এলএকটি নির্দিষ্ট মান লাগে এল=এল 1 সমস্ত বর্তমান বিন্দুর সেট একটি সরল রেখা এল=গ 1 এক্স 1 +গ 2 এক্স 2 (আমাদের ক্ষেত্রে এল=2এক্স 1 +2এক্স 2), ভেক্টরের লম্ব সঙ্গে(সঙ্গে 1 ;সঙ্গে 2) (সঙ্গে(2; 2)), উৎপত্তি থেকে আসছে। যদি এই রেখাটি ভেক্টরের ধনাত্মক দিকে সরানো হয় সঙ্গে, তারপর উদ্দেশ্য ফাংশন এলবাড়বে, অন্যথায় কমবে। এইভাবে, আমাদের ক্ষেত্রে, বহুভুজ থেকে প্রস্থান এ সরল রেখা এবিসিডিসিদ্ধান্ত তথাকথিত মাধ্যমে যেতে হবে ভিতরে(3; 7.5), এবং তাই সহ। ভিতরেউদ্দেশ্য ফাংশন সর্বোচ্চ মান নেয়, যেমন এলসর্বোচ্চ =2ּ3+2ּ7.5=21। একইভাবে, এটি নির্ধারিত হয় যে ফাংশনটি ন্যূনতম মানটি নেয় ডি(1; 0) এবং এলমিনিট =2ּ1+2ּ0=2।

লিনিয়ার প্রোগ্রামিং সমস্যা সমাধানের জন্য সিমপ্লেক্স পদ্ধতির অ্যালগরিদম নিম্নরূপ।

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

2. লক্ষ্য ফাংশন মৌলিক এবং সহায়ক ভেরিয়েবলের মাধ্যমে প্রকাশ করা হয়।

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

4. প্রতিটি সিমপ্লেক্স টেবিল একটি লিনিয়ার প্রোগ্রামিং সমস্যার সমাধান দেয়: ফ্রি ভেরিয়েবলগুলি শূন্যের সমান, মৌলিক ভেরিয়েবলগুলি যথাক্রমে মুক্ত পদের সমান।

5. সর্বোত্তমতার মানদণ্ড হল সর্বাধিক সমস্যা সমাধানের জন্য টেবিলের শেষ সারিতে নেতিবাচক উপাদানের অনুপস্থিতি এবং সর্বনিম্ন জন্য ইতিবাচক উপাদান।

6. সমাধানটি উন্নত করার জন্য, একটি সিমপ্লেক্স টেবিল থেকে অন্য টেবিলে যেতে হবে। এটি করার জন্য, পূর্ববর্তী সারণীতে একটি কী কলাম খুঁজুন যা সর্বাধিক সমস্যায় টেবিলের শেষ সারির ক্ষুদ্রতম ঋণাত্মক উপাদান এবং সর্বনিম্ন সমস্যায় বৃহত্তম ধনাত্মক সহগটির সাথে মিলে যায়। তারপর একটি কী সারি কী কলামের সংশ্লিষ্ট ধনাত্মক উপাদানগুলির সাথে মুক্ত পদের ন্যূনতম অনুপাতের সাথে সঙ্গতিপূর্ণ পাওয়া যায়। একটি কী কলাম এবং একটি কী সারির সংযোগস্থলে কী উপাদান রয়েছে।

7. আমরা ভিত্তিটি পূরণ করে নিম্নলিখিত সিমপ্লেক্স টেবিলটি পূরণ করতে শুরু করি: কী সারির সাথে সম্পর্কিত পরিবর্তনশীলটি ভিত্তি থেকে উদ্ভূত হয়েছে এবং কী কলামের সাথে সম্পর্কিত পরিবর্তনশীলটি তার জায়গায় প্রবেশ করা হয়েছে। প্রাক্তন কী স্ট্রিংয়ের উপাদানগুলি পূর্বের উপাদানটিকে কী এক দ্বারা ভাগ করে পাওয়া যায়। প্রাক্তন কী কলামের উপাদানগুলি শূন্য হয়ে যায়, মূল উপাদানটি ছাড়া, যা একটি। অন্যান্য সমস্ত উপাদান আয়তক্ষেত্র নিয়ম ব্যবহার করে গণনা করা হয়:

8. একটি সর্বোত্তম পরিকল্পনা প্রাপ্ত না হওয়া পর্যন্ত সিমপ্লেক্স টেবিলের রূপান্তর বাহিত হয়।

উদাহরণ. একটি ফাংশনের সর্বোচ্চ মান খুঁজুন
, যদি ভেরিয়েবল হয়
বিধিনিষেধ সিস্টেম সন্তুষ্ট:

সমাধান। 1. নতুন ভেরিয়েবল প্রবর্তন করুন
, যার সাহায্যে আমরা সিস্টেমের অসমতাকে সমীকরণে রূপান্তরিত করি:

আমরা বস্তুনিষ্ঠ ফাংশনের সহগগুলির চিহ্ন পরিবর্তন করি বা আকারে লিখি
. আমরা প্রথম সিমপ্লেক্স টেবিলটি পূরণ করি, শূন্য লাইনে আমরা লিখি এক্স 1 ,এক্স 2 এবং (মুক্ত মতভেদ)। শূন্য কলামে - এক্স 3 ,এক্স 4 ,এক্স 5 এবং চ. আমরা সমীকরণের ফলাফল সিস্টেম এবং রূপান্তরিত উদ্দেশ্য ফাংশন ব্যবহার করে এই টেবিলটি পূরণ করি।

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

2. নিম্নরূপ প্রথম টেবিলের সমাধানকারী উপাদান খুঁজুন। শেষ সারির উপাদানগুলির মধ্যে, আমরা মাত্রায় বৃহত্তম ঋণাত্মক সহগ নির্বাচন করি (এটি -3) এবং দ্বিতীয় কলামটিকে সমাধান হিসাবে গ্রহণ করি। যদি কলামের সমস্ত সহগ অ-ধনাত্মক হয়, তাহলে
.

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

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

দ্বিতীয় টেবিলের অবশিষ্ট উপাদানগুলি প্রথম টেবিলের উপাদানগুলি থেকে আয়তক্ষেত্রের নিয়ম ব্যবহার করে প্রাপ্ত করা হয়। ঘরটি পূরণ করার জন্য এবং সমাধানকারী উপাদান সহ ঘরটির জন্য, আমরা একটি আয়তক্ষেত্র তৈরি করি। তারপর, ঘরটি পূর্ণ করার জন্য উপাদান থেকে, আমরা সমাধানকারী উপাদান দ্বারা ভাগ করে অন্য দুটি শীর্ষবিন্দুর উপাদানগুলির গুণফল বিয়োগ করি। দ্বিতীয় টেবিলের প্রথম সারি পূরণ করতে এই নিয়ম ব্যবহার করে গণনা দেখাই:

.

মানদণ্ড পূরণ না হওয়া পর্যন্ত আমরা এই নিয়ম অনুসারে টেবিলগুলি পূরণ করতে থাকি। আমাদের টাস্কের জন্য আরও দুটি টেবিল আছে।

	এক্স 1	এক্স 4					এক্স 3	এক্স 2
এক্স 3						এক্স 1
এক্স 2						এক্স 2
এক্স 5						এক্স 5

4. এই অ্যালগরিদম কার্যকর করার ফলাফল নিম্নরূপ লেখা হয়। চূড়ান্ত সারণীতে, সারির সংযোগস্থলে থাকা উপাদান
এবং কলাম খ, উদ্দেশ্য ফাংশনের সর্বোচ্চ মান দেয়। আমাদের ক্ষেত্রে
. সারি ভেরিয়েবলের মানগুলি মুক্ত সহগগুলির সমান। আমাদের সমস্যার জন্য আমরা আছে
.

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

ন্যূনতম জন্য একটি রৈখিক প্রোগ্রামিং সমস্যা সমাধান করার সময়, শেষ লাইনে বৃহত্তম ইতিবাচক সহগ নির্বাচন করা হয় এবং শেষ লাইনে কোন ইতিবাচক সহগ না হওয়া পর্যন্ত নির্দিষ্ট অ্যালগরিদমটি কার্যকর করা হয়।

এক্সেল ব্যবহার করে লিনিয়ার প্রোগ্রামিং সমস্যার সমাধান নিম্নরূপ সঞ্চালিত হয়।

লিনিয়ার প্রোগ্রামিং সমস্যা সমাধান করতে, সমাধান অনুসন্ধান অ্যাড-অন ব্যবহার করুন। প্রথমে আপনাকে নিশ্চিত করতে হবে যে এই অ্যাড-ইনটি বিশ্লেষণ গ্রুপের ডেটা ট্যাবে উপস্থিত রয়েছে (2003-এর জন্য, টুলস দেখুন)। যদি একটি সমাধান খুঁজুন কমান্ড বা বিশ্লেষণ গ্রুপ অনুপস্থিত, আপনি এই অ্যাড-ইন ডাউনলোড করতে হবে.

এটি করার জন্য, মাইক্রোসফ্ট অফিস ফাইল (2010) এ ক্লিক করুন, তারপর এক্সেল বিকল্প বোতামে ক্লিক করুন। প্রদর্শিত এক্সেল বিকল্প উইন্ডোতে, বাম দিকে অ্যাড-ইন বাক্সটি নির্বাচন করুন। উইন্ডোর ডানদিকে, নিয়ন্ত্রণ ক্ষেত্রের মানটি এক্সেল অ্যাড-ইনগুলিতে সেট করা উচিত, এই ক্ষেত্রের পাশে অবস্থিত "গো" বোতামে ক্লিক করুন। অ্যাড-ইন উইন্ডোতে, সমাধান খুঁজুন এর পাশের চেকবক্সটি নির্বাচন করুন এবং ঠিক আছে ক্লিক করুন। তারপরে আপনি সমাধান অ্যাড-অনের জন্য ইনস্টল করা অনুসন্ধানের সাথে কাজ করতে পারেন।

একটি সমাধানের জন্য অনুসন্ধান কল করার আগে, আপনাকে একটি ওয়ার্কশীটে একটি লিনিয়ার প্রোগ্রামিং সমস্যা (একটি গাণিতিক মডেল থেকে) সমাধানের জন্য ডেটা প্রস্তুত করতে হবে:

1) ঘরগুলি নির্ধারণ করুন যেখানে সমাধানের ফলাফলটি এর জন্য স্থাপন করা হবে প্রথম লাইনে আমরা ভেরিয়েবল এবং উদ্দেশ্য ফাংশনটি প্রবেশ করি। আমরা এই কোষগুলিতে দ্বিতীয় লাইন (পরিবর্তনযোগ্য কোষ) পূরণ করি না সর্বোত্তম ফলাফল পাওয়া যাবে। পরবর্তী লাইনে উদ্দেশ্য ফাংশনের জন্য ডেটা এবং পরবর্তী লাইনগুলিতে সীমাবদ্ধতার সিস্টেম (অজানাদের জন্য সহগ) লিখুন। ডান পাশসীমাবদ্ধতা (মুক্ত সহগ) প্রবর্তন করা হয়, সীমাবদ্ধতার সিস্টেমের সহগ রেকর্ড করার পরে একটি বিনামূল্যে ঘর ছেড়ে যায়।

2) অবজেক্টিভ ফাংশনের জন্য পরিবর্তনশীল কোষের উপর নির্ভরতা এবং অবশিষ্ট মুক্ত কোষগুলিতে সীমাবদ্ধতার সিস্টেমের বাম অংশগুলির জন্য পরিবর্তনশীল কোষের উপর নির্ভরতার পরিচয় দিন। নির্ভরতা সূত্র প্রবর্তন করতে, গাণিতিক ফাংশন SUMPRODUCT ব্যবহার করা সুবিধাজনক।

এর পরে, আপনাকে একটি সমাধান অ্যাড-অনের জন্য অনুসন্ধান ব্যবহার করতে হবে। ডেটা ট্যাবে, বিশ্লেষণ গ্রুপে, একটি সমাধান খুঁজুন নির্বাচন করুন। সমাধানের জন্য অনুসন্ধান ডায়ালগ বক্স প্রদর্শিত হবে, যা নিম্নরূপ সম্পন্ন করতে হবে:

1) "অপ্টিমাইজ অবজেক্টিভ ফাংশন" ফিল্ডে উদ্দেশ্য ফাংশন ধারণকারী ঘরটি নির্দিষ্ট করুন (এই সেলটিতে অবশ্যই উদ্দেশ্য ফাংশনের সূত্র থাকতে হবে)। টার্গেট সেলের মান অপ্টিমাইজ করার জন্য বিকল্পটি নির্বাচন করুন (সর্বোচ্চকরণ, ন্যূনতমকরণ):

2) "পরিবর্তনশীল কোষ" ক্ষেত্রে, পরিবর্তন করতে ঘরগুলি লিখুন। পরবর্তী ক্ষেত্রে "নিষেধাজ্ঞা অনুসারে", "যোগ করুন" বোতামটি ব্যবহার করে নির্দিষ্ট সীমাবদ্ধতাগুলি লিখুন। প্রদর্শিত উইন্ডোতে, সীমাবদ্ধতা সিস্টেমের সূত্র সম্বলিত ঘরগুলি প্রবেশ করান, সীমাবদ্ধতা চিহ্ন এবং সীমাবদ্ধতার মান (মুক্ত সহগ) নির্বাচন করুন:

3) "অনিয়ন্ত্রিত ভেরিয়েবলগুলি অ-নেতিবাচক করুন" চেকবক্সটি চেক করুন৷ সমাধান পদ্ধতি নির্বাচন করুন "সিমপ্লেক্স পদ্ধতি ব্যবহার করে রৈখিক সমস্যার সমাধানের জন্য অনুসন্ধান করুন।" "সমাধান খুঁজুন" বোতামে ক্লিক করার পরে, সমস্যা সমাধানের প্রক্রিয়া শুরু হয়। ফলস্বরূপ, "সমাধান অনুসন্ধান ফলাফল" ডায়ালগ বক্স প্রদর্শিত হবে এবং ভেরিয়েবল মান এবং উদ্দেশ্য ফাংশনের সর্বোত্তম মানগুলির জন্য ভরাট ঘর সহ প্রাথমিক টেবিল।

উদাহরণ।এক্সেল সলিউশন অ্যাড-ইন ব্যবহার করে একটি লিনিয়ার প্রোগ্রামিং সমস্যা সমাধান করুন: একটি ফাংশনের সর্বোচ্চ মান খুঁজুন
বিধিনিষেধের অধীনে

,

;

,
.

সমাধান।আমাদের সমস্যা সমাধানের জন্য, আসুন একটি এক্সেল ওয়ার্কশীটে নির্দিষ্ট অ্যালগরিদমটি কার্যকর করি। একটি টেবিল আকারে প্রাথমিক তথ্য লিখুন

আমরা উদ্দেশ্যমূলক ফাংশন এবং বিধিনিষেধের সিস্টেমের জন্য নির্ভরতা প্রবর্তন করি। এটি করতে, C2 ঘরে =SUMPRODUCT(A2:B2;A3:B3) সূত্রটি লিখুন। C4 এবং C5 কক্ষে, যথাক্রমে, সূত্রগুলি হল: =SUMPRODUCT(A2:B2,A4:B4) এবং =SUMPRODUCT(A2:B2,A5:B5)। ফলস্বরূপ, আমরা একটি টেবিল পেতে.

"সমাধানের জন্য অনুসন্ধান করুন" কমান্ডটি চালান এবং নিম্নরূপ প্রদর্শিত একটি সমাধান উইন্ডোটির জন্য অনুসন্ধানটি পূরণ করুন। "অপ্টিমাইজ অবজেক্টিভ ফাংশন" ফিল্ডে, সেল C2 লিখুন। লক্ষ্য সেল মান "সর্বোচ্চ" অপ্টিমাইজেশান নির্বাচন করুন.

"পরিবর্তনশীল কোষ" ক্ষেত্রে, পরিবর্তনশীল কোষগুলি A2:B2 লিখুন। "নিষেধাজ্ঞা অনুসারে" ক্ষেত্রে, "যোগ করুন" বোতাম ব্যবহার করে নির্দিষ্ট বিধিনিষেধ লিখুন। সেল $C$4:$C$5 সীমাবদ্ধতার উল্লেখ =$D$4:$D$5 তাদের মধ্যে সাইন<= затем кнопку «ОК».

"অনিয়ন্ত্রিত ভেরিয়েবলগুলি অ-নেতিবাচক করুন" চেকবক্সটি চেক করুন৷ সমাধান পদ্ধতি নির্বাচন করুন "সিমপ্লেক্স পদ্ধতি ব্যবহার করে রৈখিক সমস্যার সমাধানের জন্য অনুসন্ধান করুন।"

"সমাধান খুঁজুন" বোতামে ক্লিক করলে সমস্যা সমাধানের প্রক্রিয়া শুরু হয়। ফলস্বরূপ, "সমাধান অনুসন্ধান ফলাফল" ডায়ালগ বক্স এবং ভেরিয়েবল মানগুলির জন্য ভরাট ঘর সহ মূল টেবিল এবং উদ্দেশ্য ফাংশনের সর্বোত্তম মান প্রদর্শিত হবে।

"সমাধান অনুসন্ধান ফলাফল" ডায়ালগ বক্সে, ফলাফলটি সংরক্ষণ করুন x1=0.75, x2=0.75, F=1.5 - উদ্দেশ্য ফাংশনের সর্বোচ্চ মানের সমান।

স্বাধীন কাজের জন্য কাজ

অনুশীলনী 1.গ্রাফিক্যাল, সিমপ্লেক্স পদ্ধতি এবং এক্সেল টুল ব্যবহার করে, একটি ফাংশনের সর্বোচ্চ এবং সর্বনিম্ন মান খুঁজুন চ(এক্সএকটি প্রদত্ত বিধিনিষেধের অধীনে।

1. চ(এক্স)=10এক্স 1 +5এক্স 2 2. চ(এক্স)=3এক্স 1 -2এক্স 2

3. চ(এক্স)=3এক্স 1 +5এক্স 2 4. চ(এক্স)=3এক্স 1 +3এক্স 2

5. চ(এক্স)=4এক্স 1 -3এক্স 2 6. চ(এক্স)=2এক্স 1 -এক্স 2

7. চ(এক্স)=-2এক্স 1 +4এক্স 2 8. চ(এক্স)=4এক্স 1 -3এক্স 2

9. চ(এক্স)=5এক্স 1 +10এক্স 2 10. চ(এক্স)=2এক্স 1 +এক্স 2

11. চ(এক্স)=এক্স 1 +এক্স 2 12. চ(এক্স)=3এক্স 1 +এক্স 2

13. চ(এক্স)=4এক্স 1 +5এক্স 2 14. চ(এক্স)=3এক্স 1 +2এক্স 2

15. চ(এক্স)=-এক্স 1 -এক্স 2 16. চ(এক্স)=-3এক্স 1 -5এক্স 2

17. চ(এক্স)=2এক্স 1 +3এক্স 2 18. চ(এক্স)=4এক্স 1 +3এক্স 2

19. চ(এক্স)=-3এক্স 1 -2এক্স 2 20. চ(এক্স)=-3এক্স 1 +4এক্স 2

21. চ(এক্স)=5এক্স 1 -2এক্স 2 22. চ(এক্স)=-2এক্স 1 +3এক্স 3

23. চ(এক্স)=2এক্স 1 +3এক্স 2 24. চ(এক্স)=4এক্স 1 +3এক্স 2

25. চ(এক্স)=-3এক্স 1 -2এক্স 2 26. চ(এক্স)=-3এক্স 1 +4এক্স 2

27. চ(এক্স)=-2এক্স 1 +4এক্স 2 28. চ(এক্স)=4এক্স 1 -3এক্স 2

29. চ(এক্স)=-এক্স 1 -এক্স 2 30. চ(এক্স)=-3এক্স 1 -5এক্স 2

প্রশ্ন নিয়ন্ত্রণ করুন।

1. কোন সমস্যাকে লিনিয়ার প্রোগ্রামিং সমস্যা বলা হয়?

2. লিনিয়ার প্রোগ্রামিং সমস্যার উদাহরণ দাও।

3. গ্রাফিক্যাল পদ্ধতি ব্যবহার করে কিভাবে একটি লিনিয়ার প্রোগ্রামিং সমস্যা সমাধান করা হয়?

4. লিনিয়ার প্রোগ্রামিং সমস্যা সমাধানের জন্য সিমপ্লেক্স পদ্ধতির অ্যালগরিদম বর্ণনা করুন।

5. এক্সেল ব্যবহার করে লিনিয়ার প্রোগ্রামিং সমস্যা সমাধানের জন্য একটি অ্যালগরিদম বর্ণনা করুন।

শিক্ষার জন্য ফেডারেল এজেন্সি

রাজ্য বাজেট শিক্ষা প্রতিষ্ঠান

উচ্চ পেশাগত শিক্ষা

"ওমস্ক স্টেট টেকনিক্যাল ইউনিভার্সিটি"

গণনা এবং গ্রাফিক কাজ

শৃঙ্খলা দ্বারা"সর্বোত্তম নিয়ন্ত্রণ তত্ত্ব »

বিষয়ে "অপ্টিমাইজেশন পদ্ধতি এবং অপারেশন গবেষণা »

বিকল্প 7

সম্পন্ন:

চিঠিপত্র ছাত্র

চতুর্থ বর্ষের গ্রুপ ZA-419

পুরো নাম: কুজেলেভ এস এ।

চেক করা হয়েছে:

দেব্যাটেরিকোভা এম.ভি.

ওমস্ক - 2012
^

টাস্ক 1. লিনিয়ার প্রোগ্রামিং সমস্যা সমাধানের জন্য গ্রাফিক্যাল পদ্ধতি।

7) 7এক্স 1 + 6এক্স 2 → সর্বোচ্চ 20এক্স 1 + 6এক্স 2 ≤ 15 16এক্স 1 − 2এক্স 2 ≤ 18 8এক্স 1 + 4এক্স 2 ≤ 20 13এক্স 1 + 3এক্স 2 ≤ 4 এক্স 1 , এক্স 2 ≥ 0.

ধাপ 1: সম্ভাব্য অঞ্চল নির্মাণ

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

মডেলের প্রথম সীমাবদ্ধতার ফর্ম আছে . এটিতে ≤ চিহ্নটিকে = চিহ্ন দিয়ে প্রতিস্থাপন করলে, আমরা সমীকরণটি পাই . চিত্রে। 1.1 এটি একটি সরল রেখা (1) সংজ্ঞায়িত করে, যা সমতলকে দুটি অর্ধ-বিমানে বিভক্ত করে, এই ক্ষেত্রে লাইনের উপরে এবং নীচে। কোনটি বৈষম্যকে সন্তুষ্ট করে তা বেছে নিতে , এটিতে একটি নির্দিষ্ট রেখায় অবস্থিত নয় এমন কোনও বিন্দুর স্থানাঙ্কগুলি প্রতিস্থাপন করুন (উদাহরণস্বরূপ, উত্স এক্স 1 = 0, এক্স 2 = 0)। যেহেতু আমরা সঠিক অভিব্যক্তি (20 0 + 6 0 = 0 ≤15) পাই, তাহলে অর্ধ-বিমান যেখানে স্থানাঙ্কের উৎপত্তি রয়েছে (একটি তীর দ্বারা চিহ্নিত) অসমতাকে সন্তুষ্ট করে। নইলে আরেকটা অর্ধেক প্লেন।

আমরা সমস্যার অবশিষ্ট সীমাবদ্ধতার সাথে একইভাবে এগিয়ে যাই। প্রথম চতুর্ভুজ ফর্ম সহ সমস্ত নির্মিত অর্ধ-বিমানগুলির ছেদ এ বি সি ডি(চিত্র 1 দেখুন)। এটি সমস্যার সম্ভাব্য ক্ষেত্র।

ধাপ 2. একটি লেভেল লাইন লেভেল লাইন আঁকা অবজেক্টিভ ফাংশন হল সমতলের বিন্দুগুলির সেট যেখানে উদ্দেশ্য ফাংশন একটি ধ্রুবক মান নেয়। এই ধরনের একটি সেট সমীকরণ দ্বারা দেওয়া হয় চ ( এক্স) = const. উদাহরণ স্বরূপ ধরা যাক, const = 0 এবং স্তরে একটি রেখা আঁকুন চ ( এক্স) = 0, অর্থাৎ আমাদের ক্ষেত্রে সরলরেখা 7 এক্স 1 + 6এক্স 2 = 0.

এই রেখাটি মূলের মধ্য দিয়ে যায় এবং ভেক্টরের সাথে লম্ব। এই ভেক্টরটি বিন্দুতে (0,0) অবজেক্টিভ ফাংশনের গ্রেডিয়েন্ট। একটি ফাংশনের গ্রেডিয়েন্ট হল প্রশ্নবিন্দুতে একটি প্রদত্ত ফাংশনের আংশিক ডেরিভেটিভের মানগুলির একটি ভেক্টর। এলপি সমস্যার ক্ষেত্রে, উদ্দেশ্য ফাংশনের আংশিক ডেরিভেটিভগুলি সহগগুলির সমান গআমি, j = 1 , ..., n.

গ্রেডিয়েন্ট ফাংশনের দ্রুততম বৃদ্ধির দিক দেখায়। উদ্দেশ্য ফাংশন স্তর লাইন সরানো চ ( এক্স) = const. গ্রেডিয়েন্টের দিকে লম্বভাবে, আমরা শেষ বিন্দুটি খুঁজে পাই যেখানে এটি অঞ্চলের সাথে ছেদ করে। আমাদের ক্ষেত্রে, এটি হল বিন্দু ডি, যা হবে উদ্দেশ্যমূলক ফাংশনের সর্বাধিক বিন্দু (চিত্র 2 দেখুন)

এটি লাইন (2) এবং (3) এর সংযোগস্থলে অবস্থিত (চিত্র 1 দেখুন) এবং সর্বোত্তম সমাধানটি নির্দিষ্ট করে।

^ লক্ষ্য করুন যে আপনি যদি উদ্দেশ্য ফাংশনের ন্যূনতম মান খুঁজে পেতে চান তবে স্তর রেখাটি গ্রেডিয়েন্টের দিকের বিপরীত দিকে সরানো হয়।

^ ধাপ 3. সর্বাধিক (ন্যূনতম) বিন্দুর স্থানাঙ্ক এবং উদ্দেশ্য ফাংশনের সর্বোত্তম মান নির্ধারণ করা

C বিন্দুর স্থানাঙ্কগুলি খুঁজে বের করার জন্য, সরলরেখার সাথে সম্পর্কিত সমীকরণ সমন্বিত একটি সিস্টেম সমাধান করা প্রয়োজন (এই ক্ষেত্রে, সমীকরণ 2 এবং 3):

16এক্স 1 − 2এক্স 2 ≤ 18

8এক্স 1 + 4এক্স 2 ≤ 20

আমরা পাই সর্বোত্তম সমাধান = 1.33।

^ উদ্দেশ্য ফাংশনের সর্বোত্তম মান চ * = চ (এক্স*) = 7 * 0 + 6 * 1,33 = 7,8