WBSSC SLST Math XI & XII : Linear Programming Problem (L.P.P.)

Explanation: The objective function (usually denoted by Z) represents the primary goal of the LPP, which is to find the best possible value (maximum profit or minimum cost) under a given set of restrictions.

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

Explanation: Constraints are the linear inequalities or equations that represent the limitations on available resources like labor, materials, or time.

ব্যাখ্যা: সীমাবদ্ধতা হলো রৈখিক অসমতা বা সমীকরণ যা শ্রম, কাঁচামাল বা সময়ের মতো উপলব্ধ সম্পদের উপর সীমাবদ্ধতা উপস্থাপন করে।

Explanation: The feasible region is the common area determined by all the given constraints of the LPP. Any point within this region is a possible solution to the problem.

ব্যাখ্যা: সম্ভাব্য অঞ্চল হলো LPP-এর সমস্ত প্রদত্ত সীমাবদ্ধতা দ্বারা নির্ধারিত সাধারণ এলাকা। এই অঞ্চলের যেকোনো বিন্দু সমস্যার একটি সম্ভাব্য সমাধান।

Explanation: An unbounded solution occurs when the feasible region is unbounded, and the objective function’s value can move towards infinity (for maximization) or negative infinity (for minimization) without leaving the feasible region.

ব্যাখ্যা: একটি সীমাহীন সমাধান ঘটে যখন সম্ভাব্য অঞ্চলটি সীমাহীন হয় এবং উদ্দেশ্য ফাংশনের মান সম্ভাব্য অঞ্চল ত্যাগ না করেই অসীমের দিকে (সর্বোচ্চকরণের জন্য) বা ঋণাত্মক অসীমের দিকে (সর্বনিম্নকরণের জন্য) যেতে পারে।

Explanation: According to the fundamental theorem of linear programming, if an optimal solution exists, it must occur at one of the corner points (or extreme points) of the feasible region.

ব্যাখ্যা: রৈখিক প্রোগ্রামিংয়ের মৌলিক উপপাদ্য অনুসারে, যদি একটি সর্বোত্তম সমাধান বিদ্যমান থাকে, তবে এটি অবশ্যই সম্ভাব্য অঞ্চলের একটি প্রান্তিক বিন্দুতে (বা চরম বিন্দুতে) ঘটবে।

Explanation: An infeasible solution means there are no points that simultaneously satisfy all the constraints. Graphically, this means the shaded regions for the constraints do not have a common overlapping area.

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

Explanation: The condition x ≥ 0 restricts the solution to the right of the y-axis, and y ≥ 0 restricts it to be above the x-axis. Together, they confine the feasible region to the first quadrant of the Cartesian coordinate system.

ব্যাখ্যা: x ≥ 0 শর্তটি সমাধানকে y-অক্ষের ডানদিকে সীমাবদ্ধ করে, এবং y ≥ 0 শর্তটি এটিকে x-অক্ষের উপরে সীমাবদ্ধ করে। একত্রে, তারা কার্টেসিয়ান স্থানাঙ্ক ব্যবস্থার প্রথম পাদে সম্ভাব্য অঞ্চলকে সীমাবদ্ধ করে।

Explanation: This is the fundamental definition of a convex set. For any two points x1 and x2 in the set S, all points on the line segment λx1 + (1-λ)x2 for 0 ≤ λ ≤ 1 must also be in S.

ব্যাখ্যা: এটি একটি উত্তল সেটের মৌলিক সংজ্ঞা। S সেটের যেকোনো দুটি বিন্দু x1 এবং x2-এর জন্য, 0 ≤ λ ≤ 1 শর্তে λx1 + (1-λ)x2 রেখাংশের সমস্ত বিন্দুও S-এর মধ্যে থাকতে হবে।

Explanation: Each linear constraint defines a half-space, which is a convex set. The intersection of multiple convex sets is also a convex set. Therefore, the feasible region of an LPP is always a convex set.

ব্যাখ্যা: প্রতিটি রৈখিক সীমাবদ্ধতা একটি অর্ধ-স্থানকে (half-space) সংজ্ঞায়িত করে, যা একটি উত্তল সেট। একাধিক উত্তল সেটের ছেদও একটি উত্তল সেট। সুতরাং, একটি LPP-এর সম্ভাব্য অঞ্চল সর্বদা একটি উত্তল সেট।

Explanation: An extreme point is a “corner” of the convex set. It cannot be on the line segment connecting two other points of the set.

ব্যাখ্যা: একটি চরম বিন্দু হলো উত্তল সেটের একটি “কোণা”। এটি সেটের অন্য দুটি বিন্দু সংযোগকারী রেখাংশের উপর থাকতে পারে না।

Explanation: This is a key theorem in LPP. Every Basic Feasible Solution (BFS) represents a vertex (extreme point) of the feasible region (convex polyhedron), and conversely, every vertex represents a BFS.

ব্যাখ্যা: এটি LPP-এর একটি মূল উপপাদ্য। প্রতিটি মৌলিক সম্ভাব্য সমাধান (BFS) সম্ভাব্য অঞ্চলের (উত্তল পলিহেড্রন) একটি শীর্ষবিন্দুকে (চরম বিন্দু) প্রতিনিধিত্ব করে, এবং বিপরীতভাবে, প্রতিটি শীর্ষবিন্দু একটি BFS-কে প্রতিনিধিত্ব করে।

Explanation: In a system with ‘m’ constraints, a basic solution has ‘m’ basic variables. A BFS is degenerate if one or more of these ‘m’ basic variables have a value of zero. This can sometimes cause cycling in the simplex method.

ব্যাখ্যা: ‘m’ সীমাবদ্ধতা সহ একটি সিস্টেমে, একটি মৌলিক সমাধানের ‘m’টি মৌলিক চলক থাকে। একটি BFS ডিজেনারেট হয় যদি এই ‘m’টি মৌলিক চলকের মধ্যে এক বা একাধিকের মান শূন্য হয়। এটি কখনও কখনও সিমপ্লেক্স পদ্ধতিতে সাইক্লিং-এর কারণ হতে পারে।

Explanation: A hyperplane in R^n is a set of points x satisfying c’x = z, where c is a non-zero vector and z is a scalar. For n=2, it’s a line. For n=3, it’s a plane.

ব্যাখ্যা: R^n-এ একটি হাইপারপ্লেন হলো x বিন্দুর একটি সেট যা c’x = z সমীকরণকে সিদ্ধ করে, যেখানে c একটি অশূন্য ভেক্টর এবং z একটি স্কেলার। n=2 এর জন্য এটি একটি রেখা। n=3 এর জন্য এটি একটি সমতল।

Explanation: The feasible region of an LPP, defined by constraints like a’x ≤ b, is the intersection of closed half-spaces, forming a convex polyhedron. If it is bounded, it is called a convex polytope.

ব্যাখ্যা: একটি LPP-এর সম্ভাব্য অঞ্চল, যা a’x ≤ b এর মতো সীমাবদ্ধতা দ্বারা সংজ্ঞায়িত, তা হলো বদ্ধ অর্ধ-স্থানের ছেদ, যা একটি উত্তল পলিহেড্রন গঠন করে। যদি এটি সীমাবদ্ধ হয়, তবে একে উত্তল পলিটোপ বলা হয়।

Explanation: A slack variable is added to the left-hand side of a ‘less-than-or-equal-to’ constraint to convert it into an equality. It represents the unused amount of a resource.

ব্যাখ্যা: একটি ‘less-than-or-equal-to’ সীমাবদ্ধতাকে সমীকরণে রূপান্তর করার জন্য বাম দিকে একটি ঘাটতি চলক (slack variable) যোগ করা হয়। এটি একটি সম্পদের অব্যবহৃত পরিমাণকে প্রতিনিধিত্ব করে।

Explanation: A surplus variable (or excess variable) is subtracted from the left-hand side of a ‘greater-than-or-equal-to’ constraint to turn it into an equation. It represents the amount by which the minimum requirement is exceeded.

ব্যাখ্যা: একটি ‘greater-than-or-equal-to’ সীমাবদ্ধতাকে সমীকরণে রূপান্তর করার জন্য বাম দিক থেকে একটি উদ্বৃত্ত চলক (surplus variable) বিয়োগ করা হয়। এটি সেই পরিমাণকে প্রতিনিধিত্ব করে যা দ্বারা ন্যূনতম প্রয়োজনীয়তা অতিক্রম করা হয়েছে।

Explanation: The standard form requires: 1) The objective function to be maximized (or minimized). 2) All constraints to be expressed as equalities. 3) The right-hand side of each constraint to be non-negative. 4) All decision variables to be non-negative.

ব্যাখ্যা: স্ট্যান্ডার্ড ফর্মের জন্য প্রয়োজন: ১) উদ্দেশ্য ফাংশনটিকে সর্বোচ্চ (বা সর্বনিম্ন) করতে হবে। ২) সমস্ত সীমাবদ্ধতাকে সমীকরণ হিসাবে প্রকাশ করতে হবে। ৩) প্রতিটি সীমাবদ্ধতার ডান দিককে অ-ঋণাত্মক হতে হবে। ৪) সমস্ত সিদ্ধান্ত চলককে অ-ঋণাত্মক হতে হবে।

Explanation: For a maximization problem, Cj-Zj represents the net increase in the objective function for each unit of the variable entering the basis. We choose the variable that offers the highest per-unit improvement, which corresponds to the most positive Cj-Zj value.

ব্যাখ্যা: একটি সর্বোচ্চকরণ সমস্যার জন্য, Cj-Zj ভিত্তিতে প্রবেশকারী চলকের প্রতিটি এককের জন্য উদ্দেশ্য ফাংশনে মোট বৃদ্ধি নির্দেশ করে। আমরা সেই চলকটি বেছে নিই যা প্রতি-এককে সর্বোচ্চ উন্নতি প্রদান করে, যা সবচেয়ে ধনাত্মক Cj-Zj মানের সাথে সঙ্গতিপূর্ণ।

Explanation: This is the feasibility condition. This “minimum ratio test” ensures that after the pivot operation, the new basic solution remains feasible (i.e., all variables in the solution column remain non-negative). Negative or zero denominators are ignored.

ব্যাখ্যা: এটি সম্ভাব্যতা শর্ত। এই “ন্যূনতম অনুপাত পরীক্ষা” নিশ্চিত করে যে পিভট অপারেশনের পরে, নতুন মৌলিক সমাধানটি সম্ভাব্য থাকে (অর্থাৎ, সমাধান কলামের সমস্ত চলক অ-ঋণাত্মক থাকে)। ঋণাত্মক বা শূন্য হর উপেক্ষা করা হয়।

Explanation: When all values in the net evaluation row (Cj-Zj) are zero or negative for a maximization problem, it means no non-basic variable can enter the basis to further increase the objective function value. Thus, the current solution is optimal.

ব্যাখ্যা: যখন একটি সর্বোচ্চকরণ সমস্যার জন্য নেট মূল্যায়ন সারির (Cj-Zj) সমস্ত মান শূন্য বা ঋণাত্মক হয়, এর অর্থ হলো কোনো অ-মৌলিক চলক ভিত্তিতে প্রবেশ করে উদ্দেশ্য ফাংশনের মান আর বাড়াতে পারবে না। সুতরাং, বর্তমান সমাধানটি সর্বোত্তম।

Explanation: When constraints are of ‘≥’ or ‘=’ type, slack variables cannot provide an initial identity matrix for the basis. Artificial variables are introduced, and the Two-Phase method is used. Phase I finds a basic feasible solution, and Phase II optimizes the original objective function.

ব্যাখ্যা: যখন সীমাবদ্ধতা ‘≥’ বা ‘=’ ধরনের হয়, তখন ঘাটতি চলকগুলি ভিত্তির জন্য একটি প্রাথমিক অভেদ ম্যাট্রিক্স সরবরাহ করতে পারে না। কৃত্রিম চলকগুলি চালু করা হয়, এবং টু-ফেজ পদ্ধতি ব্যবহার করা হয়। ফেজ-I একটি মৌলিক সম্ভাব্য সমাধান খুঁজে বের করে এবং ফেজ-II মূল উদ্দেশ্য ফাংশনকে অপ্টিমাইজ করে।

Explanation: The goal of Phase I is to drive all artificial variables to zero. This is achieved by creating an auxiliary objective function which is the sum of all artificial variables and minimizing it. If the minimum value is zero, a feasible solution has been found.

ব্যাখ্যা: ফেজ-I এর লক্ষ্য হলো সমস্ত কৃত্রিম চলককে শূন্যতে নিয়ে আসা। এটি একটি সহায়ক উদ্দেশ্য ফাংশন তৈরি করে অর্জন করা হয় যা সমস্ত কৃত্রিম চলকের যোগফল এবং এটিকে সর্বনিম্ন করা হয়। যদি সর্বনিম্ন মান শূন্য হয়, তবে একটি সম্ভাব্য সমাধান পাওয়া গেছে।

Explanation: A positive value for the sum of artificial variables at the end of Phase I means that at least one artificial variable remains in the basis with a positive value. This indicates that the original constraints cannot be satisfied, so no feasible solution exists.

ব্যাখ্যা: ফেজ-I এর শেষে কৃত্রিম চলকগুলির যোগফলের একটি ধনাত্মক মান মানে হলো অন্তত একটি কৃত্রিম চলক ধনাত্মক মান নিয়ে ভিত্তিতে রয়ে গেছে। এটি নির্দেশ করে যে মূল সীমাবদ্ধতাগুলি সন্তুষ্ট করা যায় না, সুতরাং কোনো সম্ভাব্য সমাধান নেই।

Explanation: Cycling is a situation where the simplex algorithm goes through a sequence of iterations that repeat a set of basic solutions without improving the objective function value, and never reaches the optimal solution. Degeneracy is a necessary condition for cycling to occur.

ব্যাখ্যা: সাইক্লিং হলো এমন একটি পরিস্থিতি যেখানে সিমপ্লেক্স অ্যালগরিদম পুনরাবৃত্তিমূলক একটি ক্রমের মধ্য দিয়ে যায় যা উদ্দেশ্য ফাংশনের মান উন্নত না করেই মৌলিক সমাধানগুলির একটি সেট পুনরাবৃত্তি করে এবং কখনও সর্বোত্তম সমাধানে পৌঁছায় না। সাইক্লিং ঘটার জন্য ডিজেনারেসি একটি প্রয়োজনীয় শর্ত।

Explanation: Bland’s Rule is a specific pivot selection rule that guarantees the simplex algorithm will not cycle. It states that among all possible choices for the entering variable, choose the one with the smallest index. Similarly, for the leaving variable, choose the one with the smallest index.

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

Explanation: This is a fundamental theorem of duality. If you formulate the dual of an LPP and then formulate the dual of that new problem, you get back to the original (primal) LPP.

ব্যাখ্যা: এটি দ্বৈততার একটি মৌলিক উপপাদ্য। আপনি যদি একটি LPP-এর ডুয়াল গঠন করেন এবং তারপর সেই নতুন সমস্যার ডুয়াল গঠন করেন, তবে আপনি মূল (প্রাইমাল) LPP-তে ফিরে আসবেন।

Explanation: The nature of optimization is reversed in duality. A primal maximization problem corresponds to a dual minimization problem, and vice-versa.

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

Explanation: For any pair of feasible solutions, the objective value of the maximization primal is always less than or equal to the objective value of the minimization dual. This provides a bound on the optimal value.

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

Explanation: This is a direct consequence of the Weak Duality Theorem. If the primal (max) can go to infinity, there cannot be any feasible dual (min) solution, because any feasible dual solution would provide an upper bound to the primal, which is a contradiction.

ব্যাখ্যা: এটি দুর্বল দ্বৈততা উপপাদ্যের একটি সরাসরি ফলাফল। যদি প্রাইমাল (সর্বোচ্চ) অসীমের দিকে যেতে পারে, তবে কোনো সম্ভাব্য ডুয়াল (সর্বনিম্ন) সমাধান থাকতে পারে না, কারণ যেকোনো সম্ভাব্য ডুয়াল সমাধান প্রাইমালের জন্য একটি ঊর্ধ্ব সীমা প্রদান করবে, যা একটি স্ববিরোধিতা।

Explanation: Complementary Slackness provides conditions for optimality. It states that at optimality, if a primal variable is positive, the corresponding dual constraint must be binding (hold as an equality). Also, if a primal constraint is not binding (has positive slack), the corresponding dual variable must be zero.

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

Explanation: A transportation problem is balanced when the total availability of the commodity from all sources is equal to the total requirement of the commodity at all destinations.

ব্যাখ্যা: একটি পরিবহন সমস্যা ভারসাম্যপূর্ণ হয় যখন সমস্ত উৎস থেকে পণ্যের মোট প্রাপ্যতা সমস্ত গন্তব্যে পণ্যের মোট প্রয়োজনের সমান হয়।

Explanation: The assignment problem deals with assigning ‘n’ jobs to ‘n’ machines (or workers) on a one-to-one basis. This is equivalent to a transportation problem with ‘n’ sources and ‘n’ destinations, where each source has a supply of 1 and each destination has a demand of 1.

ব্যাখ্যা: অ্যাসাইনমেন্ট সমস্যা ‘n’টি কাজকে ‘n’টি মেশিনে (বা কর্মীকে) এক-এক ভিত্তিতে বরাদ্দ করার সাথে সম্পর্কিত। এটি ‘n’টি উৎস এবং ‘n’টি গন্তব্য সহ একটি পরিবহন সমস্যার সমতুল্য, যেখানে প্রতিটি উৎসের সরবরাহ ১ এবং প্রতিটি গন্তব্যের চাহিদা ১।

Explanation: The Hungarian Method is an efficient combinatorial optimization algorithm that solves the assignment problem in polynomial time. It is based on reducing the cost matrix to find an optimal assignment with zero cost.

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

Explanation: For a transportation problem with ‘m’ sources and ‘n’ destinations, a basic feasible solution must have exactly m + n – 1 allocations in independent positions. If the number of allocations is less than this, the solution is degenerate.

ব্যাখ্যা: ‘m’টি উৎস এবং ‘n’টি গন্তব্য সহ একটি পরিবহন সমস্যার জন্য, একটি মৌলিক সম্ভাব্য সমাধানের অবশ্যই m + n – 1টি স্বাধীন অবস্থানে বরাদ্দ থাকতে হবে। যদি বরাদ্দের সংখ্যা এর চেয়ে কম হয়, তবে সমাধানটি ডিজেনারেট।

Explanation: VAM is a heuristic method to find a good initial basic feasible solution for a transportation problem. It generally gives an initial solution that is closer to the optimal solution compared to the North-West Corner Method or the Least Cost Method.

ব্যাখ্যা: VAM একটি পরিবহন সমস্যার জন্য একটি ভাল প্রাথমিক মৌলিক সম্ভাব্য সমাধান খুঁজে বের করার একটি হিউরিস্টিক পদ্ধতি। এটি সাধারণত এমন একটি প্রাথমিক সমাধান দেয় যা উত্তর-পশ্চিম কোণ পদ্ধতি বা সর্বনিম্ন ব্যয় পদ্ধতির তুলনায় সর্বোত্তম সমাধানের কাছাকাছি থাকে।

Explanation: Decision variables (e.g., x1, x2) are the quantifiable decisions to be made. The goal of the LPP is to find the optimal values for these variables.

ব্যাখ্যা: সিদ্ধান্ত চলকগুলি (যেমন, x1, x2) হলো পরিমাণযোগ্য সিদ্ধান্ত যা নিতে হবে। LPP-এর লক্ষ্য হলো এই চলকগুলির জন্য সর্বোত্তম মান খুঁজে বের করা।

Explanation: When the iso-profit (or iso-cost) line is parallel to a boundary of the feasible region, all points on that boundary segment between two adjacent corner points are optimal solutions.

ব্যাখ্যা: যখন আইসো-প্রফিট (বা আইসো-কস্ট) রেখাটি সম্ভাব্য অঞ্চলের একটি সীমানার সমান্তরাল হয়, তখন দুটি সংলগ্ন প্রান্তিক বিন্দুর মধ্যে সেই সীমানা খণ্ডের সমস্ত বিন্দু সর্বোত্তম সমাধান হয়।

Explanation: In the standard matrix form, ‘c’ is the profit/cost vector, ‘X’ is the vector of decision variables, ‘A’ is the matrix of technological coefficients, and ‘b’ is the vector representing the right-hand side values of the constraints (resource limits).

ব্যাখ্যা: স্ট্যান্ডার্ড ম্যাট্রিক্স ফর্মে, ‘c’ হলো লাভ/ব্যয় ভেক্টর, ‘X’ হলো সিদ্ধান্ত চলকের ভেক্টর, ‘A’ হলো প্রযুক্তিগত সহগের ম্যাট্রিক্স, এবং ‘b’ হলো সীমাবদ্ধতার ডান দিকের মানগুলি (সম্পদ সীমা) উপস্থাপনকারী ভেক্টর।

Explanation: A basic solution is found by setting n – m variables (called non-basic variables) to zero and solving the resulting m x m system for the remaining m variables (called basic variables).

ব্যাখ্যা: একটি মৌলিক সমাধান n – m চলককে (যাদের অ-মৌলিক চলক বলা হয়) শূন্যতে সেট করে এবং অবশিষ্ট m চলকের (যাদের মৌলিক চলক বলা হয়) জন্য প্রাপ্ত m x m সিস্টেম সমাধান করে পাওয়া যায়।

Explanation: A BFS is non-degenerate if all of its ‘m’ basic variables have a strictly positive value. If any basic variable is zero, it is a degenerate BFS.

ব্যাখ্যা: একটি BFS নন-ডিজেনারেট হয় যদি এর ‘m’টি মৌলিক চলকের সবগুলির মান কঠোরভাবে ধনাত্মক হয়। যদি কোনো মৌলিক চলক শূন্য হয়, তবে এটি একটি ডিজেনারেট BFS।

Explanation: The convex hull is defined as the intersection of all convex sets that contain S. It can also be described as the set of all convex combinations of points in S.

ব্যাখ্যা: উত্তল হালকে S ধারণকারী সমস্ত উত্তল সেটের ছেদ হিসাবে সংজ্ঞায়িত করা হয়। এটিকে S-এর বিন্দুগুলির সমস্ত উত্তল সমাবেশের সেট হিসাবেও বর্ণনা করা যেতে পারে।

Explanation: Slack and surplus variables are introduced only to convert inequalities into equations. They represent unused resources or excess production, which do not contribute to the profit or cost. Hence, their coefficient in the objective function is always zero.

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

Explanation: If there is a column with a positive Cj-Zj (for maximization), indicating a potential improvement, but all its elements are negative or zero, it means the entering variable can be increased indefinitely without making any current basic variable infeasible (negative). This signals an unbounded solution.

ব্যাখ্যা: যদি একটি ধনাত্মক Cj-Zj (সর্বোচ্চকরণের জন্য) সহ একটি কলাম থাকে, যা একটি সম্ভাব্য উন্নতি নির্দেশ করে, কিন্তু এর সমস্ত উপাদান ঋণাত্মক বা শূন্য হয়, এর অর্থ হলো প্রবেশকারী চলককে অনির্দিষ্টভাবে বাড়ানো যেতে পারে কোনো বর্তমান মৌলিক চলককে অসম্ভাব্য (ঋণাত্মক) না করেই। এটি একটি সীমাহীন সমাধান নির্দেশ করে।

Explanation: Similar to the Two-Phase method, the Big-M method uses artificial variables for ‘≥’ and ‘=’ constraints. It assigns a very large penalty cost (-M for maximization, +M for minimization) to these variables in the objective function to ensure they are driven out of the final solution.

ব্যাখ্যা: টু-ফেজ পদ্ধতির মতো, বিগ-এম পদ্ধতি ‘≥’ এবং ‘=’ সীমাবদ্ধতার জন্য কৃত্রিম চলক ব্যবহার করে। এটি উদ্দেশ্য ফাংশনে এই চলকগুলির জন্য একটি খুব বড় জরিমানা ব্যয় (-M সর্বোচ্চকরণের জন্য, +M সর্বনিম্নকরণের জন্য) নির্ধারণ করে যাতে তারা চূড়ান্ত সমাধান থেকে বেরিয়ে যায়।

Explanation: In primal-dual correspondence, a ‘≤’ constraint in primal corresponds to a ‘≥ 0’ variable in the dual. A ‘≥’ constraint corresponds to a ‘≤ 0’ variable. An ‘=’ constraint corresponds to a variable that is unrestricted in sign.

ব্যাখ্যা: প্রাইমাল-ডুয়াল সঙ্গতিতে, প্রাইমালে একটি ‘≤’ সীমাবদ্ধতা ডুয়ালে একটি ‘≥ 0’ চলকের সাথে সঙ্গতিপূর্ণ। একটি ‘≥’ সীমাবদ্ধতা একটি ‘≤ 0’ চলকের সাথে সঙ্গতিপূর্ণ। একটি ‘=’ সীমাবদ্ধতা এমন একটি চলকের সাথে সঙ্গতিপূর্ণ যা চিহ্নে অবাধ।

Explanation: This is the core theorem of duality. It guarantees that if one problem has a finite optimal solution, so does the other, and the optimal values of their objective functions are identical. (Z_max = W_min).

ব্যাখ্যা: এটি দ্বৈততার মূল উপপাদ্য। এটি নিশ্চিত করে যে যদি একটি সমস্যার সসীম সর্বোত্তম সমাধান থাকে, তবে অন্যটিরও থাকে, এবং তাদের উদ্দেশ্য ফাংশনগুলির সর্বোত্তম মানগুলি অভিন্ন। (Z_max = W_min)।

Explanation: The MODI method calculates dual variables u_i and v_j using the condition that for every basic (occupied) cell (i, j), we have u_i + v_j = c_ij. Therefore, u_i + v_j – c_ij is always zero for occupied cells.

ব্যাখ্যা: MODI পদ্ধতি ডুয়াল চলক u_i এবং v_j গণনা করে এই শর্ত ব্যবহার করে যে প্রতিটি মৌলিক (দখলকৃত) কোষ (i, j) এর জন্য, আমাদের u_i + v_j = c_ij রয়েছে। অতএব, দখলকৃত কোষগুলির জন্য u_i + v_j – c_ij সর্বদা শূন্য হয়।

Explanation: To balance the problem, a dummy destination is created to “absorb” the excess supply. The demand for this dummy destination is set to (Total Supply – Total Demand). The transportation costs to this dummy destination are usually set to zero.

ব্যাখ্যা: সমস্যাটিকে ভারসাম্যপূর্ণ করতে, অতিরিক্ত সরবরাহ “শোষণ” করার জন্য একটি ডামি গন্তব্য তৈরি করা হয়। এই ডামি গন্তব্যের চাহিদা (মোট সরবরাহ – মোট চাহিদা) হিসাবে সেট করা হয়। এই ডামি গন্তব্যে পরিবহন ব্যয় সাধারণত শূন্য ধরা হয়।

Explanation: The method involves row and column reductions to create zeros in the cost matrix. These zeros represent zero opportunity cost. The algorithm then tries to make an optimal assignment using only these zero positions.

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

Explanation: Once an initial basic feasible solution is found (using methods like NWCR, LCM, or VAM), its optimality must be checked. The MODI (Modified Distribution) method and the Stepping Stone method are two standard procedures for this purpose.

ব্যাখ্যা: একবার একটি প্রাথমিক মৌলিক সম্ভাব্য সমাধান পাওয়া গেলে (NWCR, LCM, বা VAM এর মতো পদ্ধতি ব্যবহার করে), এর সর্বোত্তমতা পরীক্ষা করতে হবে। MODI (মডিফাইড ডিস্ট্রিবিউশন) পদ্ধতি এবং স্টেপিং স্টোন পদ্ধতি এই উদ্দেশ্যে দুটি স্ট্যান্ডার্ড পদ্ধতি।

Explanation: This property defines a cone. It means that any non-negative scaling of a vector within the cone results in a vector that is also within the cone. Geometrically, it’s a set of rays originating from the origin.

ব্যাখ্যা: এই বৈশিষ্ট্যটি একটি কোণকে সংজ্ঞায়িত করে। এর মানে হলো কোণের মধ্যে একটি ভেক্টরের যেকোনো অ-ঋণাত্মক স্কেলিং এমন একটি ভেক্টর তৈরি করে যা কোণের মধ্যেও থাকে। জ্যামিতিকভাবে, এটি মূলবিন্দু থেকে উদ্ভূত রশ্মির একটি সেট।

Explanation: The Separating Hyperplane Theorem is a fundamental result in convex geometry, stating that for any two non-empty disjoint convex sets in R^n, there exists a hyperplane that separates them.

ব্যাখ্যা: বিভাজক হাইপারপ্লেন উপপাদ্য উত্তল জ্যামিতির একটি মৌলিক ফলাফল, যা বলে যে R^n-এ যেকোনো দুটি অশূন্য বিযুক্ত উত্তল সেটের জন্য, একটি হাইপারপ্লেন বিদ্যমান যা তাদের পৃথক করে।

Explanation: A fundamental theorem states that if a feasible solution exists, a basic feasible solution also exists. One can be derived from the other by identifying linearly dependent columns associated with the positive variables and removing variables from the set of positive variables until a linearly independent set remains.

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

Explanation: The dual simplex method starts with a dual-feasible (optimal) but primal-infeasible solution. Primal infeasibility is indicated by negative values in the solution (RHS) column. The method selects the most negative RHS value to determine the leaving variable, aiming to restore primal feasibility.

ব্যাখ্যা: ডুয়াল সিমপ্লেক্স পদ্ধতি একটি ডুয়াল-সম্ভাব্য (সর্বোত্তম) কিন্তু প্রাইমাল-অসম্ভাব্য সমাধান দিয়ে শুরু হয়। প্রাইমাল অসম্ভাব্যতা সমাধান (RHS) কলামে ঋণাত্মক মান দ্বারা নির্দেশিত হয়। পদ্ধতিটি ত্যাগকারী চলক নির্ধারণ করতে সবচেয়ে ঋণাত্মক RHS মানটি নির্বাচন করে, প্রাইমাল সম্ভাব্যতা পুনরুদ্ধার করার লক্ষ্যে।

Explanation: When adding a new constraint to an already solved LPP, the solution might become infeasible but remain optimal. The dual simplex method is very efficient for such post-optimality analysis, as it can start from this point and restore feasibility without needing artificial variables.

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

Explanation: Loops are fundamental to the Stepping Stone method. They are used to evaluate the cost change of shifting one unit of allocation to an unoccupied cell. The corners of the loop (except the starting cell) must be occupied cells.

ব্যাখ্যা: লুপগুলি স্টেপিং স্টোন পদ্ধতির জন্য মৌলিক। এগুলি একটি অব্যবহৃত কোষে এক ইউনিট বরাদ্দ স্থানান্তরের ব্যয় পরিবর্তন মূল্যায়ন করতে ব্যবহৃত হয়। লুপের কোণগুলি (শুরুর কোষ ছাড়া) অবশ্যই দখলকৃত কোষ হতে হবে।

Explanation: The goal of the Hungarian method is to find a set of ‘n’ independent zeros (no two in the same row or column) in an n x n cost matrix. When this is achieved, an optimal assignment can be made.

ব্যাখ্যা: হাঙ্গেরিয়ান পদ্ধতির লক্ষ্য হলো একটি n x n ব্যয় ম্যাট্রিক্সে ‘n’টি স্বাধীন শূন্যের (একই সারি বা কলামে দুটি নয়) একটি সেট খুঁজে বের করা। যখন এটি অর্জন করা হয়, তখন একটি সর্বোত্তম বরাদ্দ করা যেতে পারে।

Explanation: Although there are m+n constraints, one of them is redundant in a balanced problem (since sum of supply equals sum of demand). Therefore, there are m+n-1 independent constraints, leading to m+n-1 basic variables in a non-degenerate solution.

ব্যাখ্যা: যদিও m+nটি সীমাবদ্ধতা রয়েছে, একটি ভারসাম্যপূর্ণ সমস্যায় তাদের মধ্যে একটি অপ্রয়োজনীয় (যেহেতু সরবরাহের যোগফল চাহিদার যোগফলের সমান)। অতএব, m+n-1টি স্বাধীন সীমাবদ্ধতা রয়েছে, যা একটি নন-ডিজেনারেট সমাধানে m+n-1টি মৌলিক চলকের দিকে পরিচালিত করে।

Explanation: By assigning an extremely high cost (or penalty) ‘M’ to a route, we ensure that the optimization algorithm (like LCM or VAM) will avoid selecting that route unless there is no other feasible alternative. This effectively prohibits the route.

ব্যাখ্যা: একটি রুটে একটি অত্যন্ত উচ্চ ব্যয় (বা জরিমানা) ‘M’ নির্ধারণ করে, আমরা নিশ্চিত করি যে অপ্টিমাইজেশান অ্যালগরিদম (যেমন LCM বা VAM) সেই রুটটি নির্বাচন করা এড়িয়ে চলবে যদি না অন্য কোনো সম্ভাব্য বিকল্প না থাকে। এটি কার্যকরভাবে রুটটিকে নিষিদ্ধ করে।

Explanation: In duality, each constraint in the primal corresponds to a variable in the dual, and each variable in the primal corresponds to a constraint in the dual. So the dimensions are swapped.

ব্যাখ্যা: দ্বৈততায়, প্রাইমালের প্রতিটি সীমাবদ্ধতা ডুয়ালের একটি চলকের সাথে সঙ্গতিপূর্ণ, এবং প্রাইমালের প্রতিটি চলক ডুয়ালের একটি সীমাবদ্ধতার সাথে সঙ্গতিপূর্ণ। তাই মাত্রাগুলি অদলবদল হয়।

Explanation: LPPs are broadly categorized by their objective. Problems aiming to reduce expenses, travel time, or waste are minimization problems. Problems aiming to increase profit, revenue, or output are maximization problems.

ব্যাখ্যা: LPP গুলি তাদের উদ্দেশ্য দ্বারা বিস্তৃতভাবে শ্রেণীবদ্ধ করা হয়। ব্যয়, ভ্রমণ সময়, বা অপচয় কমানোর লক্ষ্যে থাকা সমস্যাগুলি হলো সর্বনিম্নকরণ সমস্যা। লাভ, আয়, বা আউটপুট বাড়ানোর লক্ষ্যে থাকা সমস্যাগুলি হলো সর্বোচ্চকরণ সমস্যা।

Explanation: A fundamental property of convex sets is that their intersection (finite or infinite) is also a convex set. This is why the feasible region of an LPP, which is an intersection of half-spaces, is convex.

ব্যাখ্যা: উত্তল সেটের একটি মৌলিক বৈশিষ্ট্য হলো তাদের ছেদ (সসীম বা অসীম)ও একটি উত্তল সেট। এই কারণেই একটি LPP-এর সম্ভাব্য অঞ্চল, যা অর্ধ-স্থানের একটি ছেদ, উত্তল হয়।

Explanation: A supporting hyperplane “touches” the convex set at a boundary point without cutting through its interior. The entire set is on one side of the hyperplane.

ব্যাখ্যা: একটি সহায়ক হাইপারপ্লেন একটি সীমানা বিন্দুতে উত্তল সেটটিকে “স্পর্শ” করে এর অভ্যন্তরের মধ্য দিয়ে না গিয়ে। সম্পূর্ণ সেটটি হাইপারপ্লেনের একপাশে থাকে।

Explanation: The Simplex method starts at an initial corner point (BFS) and systematically moves to an adjacent corner point in a series of steps (iterations), improving the objective function value at each step until the optimum is reached.

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

Explanation: A tie in the minimum ratio test for the leaving variable means that in the next iteration, more than one basic variable will become zero simultaneously. This results in a degenerate basic feasible solution.

ব্যাখ্যা: ত্যাগকারী চলকের জন্য ন্যূনতম অনুপাত পরীক্ষায় একটি টাই মানে হলো পরবর্তী পুনরাবৃত্তিতে, একাধিক মৌলিক চলক একই সাথে শূন্য হয়ে যাবে। এর ফলে একটি ডিজেনারেট মৌলিক সম্ভাব্য সমাধান হয়।

Explanation: This is a key part of the theorem. If a resource (primal constraint) is not fully utilized (positive slack), its shadow price (the corresponding dual variable) must be zero. There is no gain from having more of an already abundant resource.

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

Explanation: The North-West Corner Rule is mechanically simple as it starts allocation from the top-left cell and does not consider transportation costs at all. This often leads to a high-cost initial solution that requires many iterations to optimize.

ব্যাখ্যা: উত্তর-পশ্চিম কোণ নিয়মটি যান্ত্রিকভাবে সহজ কারণ এটি উপরের-বাম কোষ থেকে বরাদ্দ শুরু করে এবং পরিবহন ব্যয় একেবারেই বিবেচনা করে না। এটি প্রায়শই একটি উচ্চ-ব্যয়ের প্রাথমিক সমাধানের দিকে নিয়ে যায় যা অপ্টিমাইজ করতে অনেক পুনরাবৃত্তির প্রয়োজন হয়।

Explanation: In an n x n assignment problem, there are n+n-1 = 2n-1 basic variables required for a non-degenerate solution. However, an assignment solution will have exactly ‘n’ allocations. Since n < 2n-1 (for n > 1), the solution is always degenerate from the transportation problem perspective.

ব্যাখ্যা: একটি n x n অ্যাসাইনমেন্ট সমস্যায়, একটি নন-ডিজেনারেট সমাধানের জন্য n+n-1 = 2n-1টি মৌলিক চলকের প্রয়োজন। যাইহোক, একটি অ্যাসাইনমেন্ট সমাধানে ঠিক ‘n’টি বরাদ্দ থাকবে। যেহেতু n < 2n-1 (n > 1 এর জন্য), পরিবহন সমস্যার দৃষ্টিকোণ থেকে সমাধানটি সর্বদা ডিজেনারেট।

Explanation: There is one constraint for each source (representing its supply) and one constraint for each destination (representing its demand), for a total of m + n constraints.

ব্যাখ্যা: প্রতিটি উৎসের জন্য একটি সীমাবদ্ধতা (এর সরবরাহ উপস্থাপন করে) এবং প্রতিটি গন্তব্যের জন্য একটি সীমাবদ্ধতা (এর চাহিদা উপস্থাপন করে) রয়েছে, মোট m + nটি সীমাবদ্ধতার জন্য।

Explanation: This theorem is the foundation of the Simplex method. It guarantees that we only need to search the finite number of corner points (BFS) of the feasible region to find the optimal solution, rather than checking an infinite number of interior points.

ব্যাখ্যা: এই উপপাদ্যটি সিমপ্লেক্স পদ্ধতির ভিত্তি। এটি নিশ্চিত করে যে অসীম সংখ্যক অভ্যন্তরীণ বিন্দু পরীক্ষা করার পরিবর্তে সর্বোত্তম সমাধান খুঁজে বের করার জন্য আমাদের শুধুমাত্র সম্ভাব্য অঞ্চলের সসীম সংখ্যক প্রান্তিক বিন্দু (BFS) অনুসন্ধান করতে হবে।

Explanation: If x is unrestricted, we can replace it with x = x’ – x”, where x’ ≥ 0 and x” ≥ 0. This allows the effective value of x to be positive (x’ > x”), negative (x’ < x''), or zero (x' = x'') while keeping all variables in the standard non-negative form.

ব্যাখ্যা: যদি x অবাধ হয়, আমরা এটিকে x = x’ – x” দ্বারা প্রতিস্থাপন করতে পারি, যেখানে x’ ≥ 0 এবং x” ≥ 0। এটি x-এর কার্যকর মানকে ধনাত্মক (x’ > x”), ঋণাত্মক (x’ < x''), বা শূন্য (x' = x'') হতে দেয় এবং সমস্ত চলককে স্ট্যান্ডার্ড অ-ঋণাত্মক ফর্মে রাখে।

Explanation: A circle (including its interior) is a convex set because the line segment connecting any two points within the circle lies entirely within the circle.

ব্যাখ্যা: একটি বৃত্ত (এর অভ্যন্তর সহ) একটি উত্তল সেট কারণ বৃত্তের মধ্যে যেকোনো দুটি বিন্দু সংযোগকারী রেখাংশ সম্পূর্ণরূপে বৃত্তের ভিতরে থাকে।

Explanation: When constraints are of ‘≥’ or ‘=’ type, we cannot use slack variables to form an initial identity basis. Artificial variables are added as placeholders to create this initial identity matrix, allowing the simplex algorithm to start.

ব্যাখ্যা: যখন সীমাবদ্ধতাগুলি ‘≥’ বা ‘=’ ধরনের হয়, তখন আমরা একটি প্রাথমিক অভেদ ভিত্তি গঠনের জন্য ঘাটতি চলক ব্যবহার করতে পারি না। কৃত্রিম চলকগুলি এই প্রাথমিক অভেদ ম্যাট্রিক্স তৈরি করার জন্য স্থানধারক হিসাবে যোগ করা হয়, যা সিমপ্লেক্স অ্যালগরিদমকে শুরু করতে দেয়।

Explanation: The optimal value of a dual variable represents the marginal value or “shadow price” of the corresponding primal constraint’s resource. It indicates how much the objective function would improve if one more unit of that resource were available.

ব্যাখ্যা: একটি ডুয়াল চলকের সর্বোত্তম মান সংশ্লিষ্ট প্রাইমাল সীমাবদ্ধতার সম্পদের প্রান্তিক মূল্য বা “ছায়া মূল্য” উপস্থাপন করে। এটি নির্দেশ করে যে যদি সেই সম্পদের আরও এক ইউনিট উপলব্ধ থাকতো তবে উদ্দেশ্য ফাংশনটি কতটা উন্নত হতো।

Explanation: The classic transportation problem seeks to find a shipping schedule that minimizes the total cost of transporting goods from a set of sources to a set of destinations, while satisfying supply and demand limits.

ব্যাখ্যা: ক্লাসিক পরিবহন সমস্যা একটি শিপিং সময়সূচী খুঁজে বের করতে চায় যা সরবরাহ এবং চাহিদার সীমা পূরণ করার সময় উৎসগুলির একটি সেট থেকে গন্তব্যগুলির একটি সেটে পণ্য পরিবহনের মোট ব্যয় সর্বনিম্ন করে।

Explanation: An LPP can have multiple (infinite) optimal solutions. This occurs when the objective function’s slope is the same as the slope of one of the binding constraint lines. In this case, every point on the line segment connecting two optimal corner points is also an optimal solution.

ব্যাখ্যা: একটি LPP-এর একাধিক (অসীম) সর্বোত্তম সমাধান থাকতে পারে। এটি ঘটে যখন উদ্দেশ্য ফাংশনের ঢাল একটি সক্রিয় সীমাবদ্ধতা রেখার ঢালের সমান হয়। এই ক্ষেত্রে, দুটি সর্বোত্তম প্রান্তিক বিন্দু সংযোগকারী রেখাংশের প্রতিটি বিন্দুও একটি সর্বোত্তম সমাধান।

Explanation: There is a direct correspondence between the algebraic concept of a Basic Feasible Solution (BFS) and the geometric concept of an extreme point (corner point) of the convex feasible region.

ব্যাখ্যা: একটি মৌলিক সম্ভাব্য সমাধানের (BFS) বীজগাণিতিক ধারণা এবং উত্তল সম্ভাব্য অঞ্চলের একটি চরম বিন্দুর (প্রান্তিক বিন্দু) জ্যামিতিক ধারণার মধ্যে একটি সরাসরি সঙ্গতি রয়েছে।

Explanation: The set of variables that form the identity matrix within the simplex tableau and have non-zero (or zero, in case of degeneracy) values in the solution column are called basic variables. All other variables are non-basic and are set to zero.

ব্যাখ্যা: যে চলকের সেট সিমপ্লেক্স টেবিলের মধ্যে অভেদ ম্যাট্রিক্স গঠন করে এবং সমাধান কলামে অশূন্য (বা ডিজেনারেসির ক্ষেত্রে শূন্য) মান থাকে তাদের মৌলিক চলক বলা হয়। অন্য সমস্ত চলক অ-মৌলিক এবং তাদের শূন্যতে সেট করা হয়।

Explanation: Artificial variables must be zero in a feasible solution because they don’t represent any real quantity in the original problem. If one remains in the basis with a positive value, it means the original constraints cannot be satisfied, so no feasible solution exists.

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

Explanation: According to the duality theorems, if the primal is infeasible, the dual can either have an unbounded solution or be infeasible itself. It cannot have a finite optimal solution.

ব্যাখ্যা: দ্বৈততা উপপাদ্য অনুসারে, যদি প্রাইমালটি অসম্ভাব্য হয়, তবে ডুয়ালটির একটি সীমাহীন সমাধান থাকতে পারে বা এটি নিজেও অসম্ভাব্য হতে পারে। এটির একটি সসীম সর্বোত্তম সমাধান থাকতে পারে না।

Explanation: The MODI method (also known as the u-v method) calculates dual variables (u_i and v_j) and uses them to check the optimality condition (c_ij – u_i – v_j ≥ 0 for all non-basic cells), which is derived directly from the duality theory of LPP.

ব্যাখ্যা: MODI পদ্ধতি (u-v পদ্ধতি নামেও পরিচিত) ডুয়াল চলক (u_i এবং v_j) গণনা করে এবং সেগুলি সর্বোত্তমতার শর্ত (সমস্ত অ-মৌলিক কোষের জন্য c_ij – u_i – v_j ≥ 0) পরীক্ষা করতে ব্যবহার করে, যা সরাসরি LPP-এর দ্বৈততা তত্ত্ব থেকে উদ্ভূত।

Explanation: Maximizing the original profit matrix is equivalent to minimizing the opportunity loss matrix. This loss matrix is created by subtracting every element in the profit matrix from the largest profit value. The Hungarian method can then be applied to this new minimization matrix.

ব্যাখ্যা: মূল লাভ ম্যাট্রিক্সকে সর্বোচ্চ করা সুযোগ ক্ষতি ম্যাট্রিক্সকে সর্বনিম্ন করার সমতুল্য। এই ক্ষতি ম্যাট্রিক্সটি লাভ ম্যাট্রিক্সের প্রতিটি উপাদানকে বৃহত্তম লাভ মান থেকে বিয়োগ করে তৈরি করা হয়। হাঙ্গেরিয়ান পদ্ধতিটি তখন এই নতুন সর্বনিম্নকরণ ম্যাট্রিক্সে প্রয়োগ করা যেতে পারে।

Explanation: The core purpose of Linear Programming is to aid in decision-making by finding the best way to allocate limited resources (like money, labor, time, materials) to achieve a specific objective (like maximum profit or minimum cost).

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

Explanation: A defining characteristic of the feasible region in any LPP is that it is always a convex set. A concave shape would imply that a line segment between two feasible points could pass through an infeasible area, which is not possible with linear constraints.

ব্যাখ্যা: যেকোনো LPP-তে সম্ভাব্য অঞ্চলের একটি সংজ্ঞায়িত বৈশিষ্ট্য হলো এটি সর্বদা একটি উত্তল সেট। একটি অবতল আকৃতি বোঝাবে যে দুটি সম্ভাব্য বিন্দুর মধ্যে একটি রেখাংশ একটি অসম্ভাব্য এলাকার মধ্য দিয়ে যেতে পারে, যা রৈখিক সীমাবদ্ধতার সাথে সম্ভব নয়।

Explanation: Degeneracy means a basic variable is zero. If this degenerate variable is chosen to leave the basis, the entering variable will also enter at a level of zero. This results in a new basis but no change (improvement) in the objective function’s value, which can lead to cycling.

ব্যাখ্যা: ডিজেনারেসি মানে একটি মৌলিক চলক শূন্য। যদি এই ডিজেনারেট চলকটিকে ভিত্তি ত্যাগ করার জন্য বেছে নেওয়া হয়, তবে প্রবেশকারী চলকটিও শূন্য স্তরে প্রবেশ করবে। এর ফলে একটি নতুন ভিত্তি হয় কিন্তু উদ্দেশ্য ফাংশনের মানে কোনো পরিবর্তন (উন্নতি) হয় না, যা সাইক্লিং-এর দিকে নিয়ে যেতে পারে।

Explanation: Once Phase I successfully finds a feasible solution (by driving artificial variables to zero), these artificial variables are no longer needed. We discard their columns, replace the Phase I objective function with the original problem’s objective function, recalculate the Cj-Zj row, and proceed with the standard simplex algorithm.

ব্যাখ্যা: একবার ফেজ-I সফলভাবে একটি সম্ভাব্য সমাধান খুঁজে পেলে (কৃত্রিম চলকগুলিকে শূন্যতে নিয়ে গিয়ে), এই কৃত্রিম চলকগুলির আর প্রয়োজন হয় না। আমরা তাদের কলামগুলি বাতিল করি, ফেজ-I উদ্দেশ্য ফাংশনকে মূল সমস্যার উদ্দেশ্য ফাংশন দিয়ে প্রতিস্থাপন করি, Cj-Zj সারিটি পুনরায় গণনা করি, এবং স্ট্যান্ডার্ড সিমপ্লেক্স অ্যালগরিদম দিয়ে এগিয়ে যাই।

Explanation: By definition, a basic solution is formed by setting n-m variables to zero (the non-basic variables) and solving for the remaining m variables (the basic variables).

ব্যাখ্যা: সংজ্ঞা অনুসারে, একটি মৌলিক সমাধান n-m চলককে শূন্যতে সেট করে (অ-মৌলিক চলক) এবং অবশিষ্ট m চলকের জন্য (মৌলিক চলক) সমাধান করে গঠিত হয়।

Explanation: Any set of values for the decision variables that satisfies all the given constraints, including the non-negativity restrictions, is called a feasible solution. The optimal solution is a specific feasible solution that also optimizes the objective function.

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

Explanation: The core constraint of the assignment problem is the one-to-one mapping. Each source (job) must be assigned to exactly one destination (person), and each destination can accept exactly one source.

ব্যাখ্যা: অ্যাসাইনমেন্ট সমস্যার মূল সীমাবদ্ধতা হলো এক-এক ম্যাপিং। প্রতিটি উৎস (কাজ) অবশ্যই ঠিক একটি গন্তব্যে (ব্যক্তি) বরাদ্দ করতে হবে, এবং প্রতিটি গন্তব্য ঠিক একটি উৎস গ্রহণ করতে পারে।

Explanation: The value of a dual variable at the optimal solution indicates the rate of change in the optimal objective function value per unit increase of the corresponding resource. This is known as its shadow price or marginal worth.

ব্যাখ্যা: সর্বোত্তম সমাধানে একটি ডুয়াল চলকের মান সংশ্লিষ্ট সম্পদের প্রতি একক বৃদ্ধির জন্য সর্বোত্তম উদ্দেশ্য ফাংশনের মানের পরিবর্তনের হার নির্দেশ করে। এটি এর ছায়া মূল্য বা প্রান্তিক মূল্য হিসাবে পরিচিত।

Explanation: Linearity implies two key properties. Proportionality: the contribution of each variable is proportional to its value (no economies of scale). Additivity: the total contribution is the sum of individual contributions (no interaction effects between variables).

ব্যাখ্যা: রৈখিকতা দুটি মূল বৈশিষ্ট্য বোঝায়। আনুপাতিকতা: প্রতিটি চলকের অবদান তার মানের আনুপাতিক (স্কেলের অর্থনীতি নেই)। যোজ্যতা: মোট অবদান হলো পৃথক অবদানের যোগফল (চলকগুলির মধ্যে কোনো মিথস্ক্রিয়া প্রভাব নেই)।

Explanation: This is a restatement of a core LPP theorem. The geometric corners (extreme points) of the feasible region are algebraically equivalent to the Basic Feasible Solutions (BFS).

ব্যাখ্যা: এটি একটি মূল LPP উপপাদ্যের পুনরাবৃত্তি। সম্ভাব্য অঞ্চলের জ্যামিতিক কোণগুলি (চরম বিন্দু) বীজগাণিতিকভাবে মৌলিক সম্ভাব্য সমাধানগুলির (BFS) সমতুল্য।

Explanation: For a minimization problem, the optimality condition is the reverse of a maximization problem. The solution is optimal when all Cj-Zj (or Zj-Cj ≤ 0) values are non-negative, as this indicates that no non-basic variable can enter the basis to further decrease the objective function cost.

ব্যাখ্যা: একটি সর্বনিম্নকরণ সমস্যার জন্য, সর্বোত্তমতার শর্ত একটি সর্বোচ্চকরণ সমস্যার বিপরীত। সমাধানটি সর্বোত্তম হয় যখন সমস্ত Cj-Zj (বা Zj-Cj ≤ 0) মান অ-ঋণাত্মক হয়, কারণ এটি নির্দেশ করে যে কোনো অ-মৌলিক চলক উদ্দেশ্য ফাংশনের ব্যয় আরও কমাতে ভিত্তিতে প্রবেশ করতে পারে না।

Explanation: The minimum ratio test determines which current basic variable will leave the basis. It is designed to ensure that in the next tableau, all basic variables remain non-negative, thus keeping the solution feasible.

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

Explanation: This is the reverse of the rule seen earlier. A non-negative primal variable corresponds to a ‘≥’ dual constraint. An unrestricted primal variable corresponds to an ‘=’ dual constraint. The relationship is symmetric.

ব্যাখ্যা: এটি আগে দেখা নিয়মের বিপরীত। একটি অ-ঋণাত্মক প্রাইমাল চলক একটি ‘≥’ ডুয়াল সীমাবদ্ধতার সাথে সঙ্গতিপূর্ণ। একটি অবাধ প্রাইমাল চলক একটি ‘=’ ডুয়াল সীমাবদ্ধতার সাথে সঙ্গতিপূর্ণ। সম্পর্কটি প্রতিসম।

Explanation: The Stepping Stone method requires drawing a unique closed loop for every single unoccupied cell to evaluate it. The MODI method calculates dual variables u_i and v_j once and then evaluates all unoccupied cells with a simple calculation (c_ij – u_i – v_j), making it much faster for large problems.

ব্যাখ্যা: স্টেপিং স্টোন পদ্ধতির জন্য প্রতিটি অব্যবহৃত কোষ মূল্যায়ন করার জন্য একটি অনন্য বন্ধ লুপ আঁকার প্রয়োজন। MODI পদ্ধতি ডুয়াল চলক u_i এবং v_j একবার গণনা করে এবং তারপর একটি সাধারণ গণনা (c_ij – u_i – v_j) দিয়ে সমস্ত অব্যবহৃত কোষ মূল্যায়ন করে, যা বড় সমস্যার জন্য এটিকে অনেক দ্রুততর করে তোলে।

Explanation: To apply the Hungarian method, the cost matrix must be square. If the number of rows and columns are unequal, a dummy row or column is added to make it square. The costs in this dummy entity are set to zero so they don’t affect the optimal cost of the real assignments.

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

Explanation: Linear programming is a highly versatile and powerful tool used across a vast range of fields to optimize resource allocation, scheduling, routing, blending, and many other types of decisions.

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

Explanation: A line segment trivially satisfies the definition of a convex set. If you pick any two points on the line segment, the line segment connecting them is, by definition, the original line segment itself, which is contained within the set.

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

Explanation: This is the key iterative step of the Hungarian algorithm. When an optimal assignment cannot be made, the matrix is revised to create new zeros. This is done by finding the smallest element not covered by any line, subtracting it from all uncovered elements, and adding it to elements at the intersection of two lines.

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