রৈখিক প্রোগ্রামিং (Linear Programming)
1. একটি রৈখিক প্রোগ্রামিং সমস্যার (LPP) উদ্দেশ্যমূলক অপেক্ষক (objective function) কী হওয়া উচিত?
The objective function of a Linear Programming Problem (LPP) must be:
The objective function of a Linear Programming Problem (LPP) must be:
সঠিক উত্তর (Correct Answer): B) রৈখিক / Linear
ব্যাখ্যা: রৈখিক প্রোগ্রামিং-এর মূল ভিত্তি হলো উদ্দেশ্যমূলক অপেক্ষক এবং সমস্ত সীমাবদ্ধতা (constraints) রৈখিক হতে হবে। অর্থাৎ, চলরাশিগুলির (variables) ঘাত (power) এক (1) হবে।
Explanation: The fundamental requirement of Linear Programming is that the objective function and all constraints must be linear. This means the power of the variables must be one (1).
Explanation: The fundamental requirement of Linear Programming is that the objective function and all constraints must be linear. This means the power of the variables must be one (1).
2. একটি LPP-তে, যে শর্তগুলির অধীনে উদ্দেশ্যমূলক অপেক্ষককে সর্বাপেক্ষা অনুকূল (optimize) করা হয়, সেগুলিকে কী বলা হয়?
In an LPP, the conditions under which the objective function is to be optimized are called:
In an LPP, the conditions under which the objective function is to be optimized are called:
সঠিক উত্তর (Correct Answer): A) সীমাবদ্ধতা / Constraints
ব্যাখ্যা: সীমাবদ্ধতাগুলি হলো অসমীকরণ (inequalities) বা সমীকরণ (equations) যা একটি সমস্যার সীমিত সম্পদ বা শর্তাবলী প্রকাশ করে। উদ্দেশ্যমূলক অপেক্ষককে এই সীমাবদ্ধতাগুলি মেনেই অপ্টিমাইজ করতে হয়।
Explanation: Constraints are the inequalities or equations that represent the limited resources or conditions of a problem. The objective function must be optimized subject to these constraints.
Explanation: Constraints are the inequalities or equations that represent the limited resources or conditions of a problem. The objective function must be optimized subject to these constraints.
3. একজন আসবাবপত্র নির্মাতা চেয়ার এবং টেবিল তৈরি করেন। প্রতিটি চেয়ার তৈরি করতে 2 ঘন্টা এবং প্রতিটি টেবিল তৈরি করতে 4 ঘন্টা সময় লাগে। প্রতিদিন মোট 100 শ্রম-ঘন্টা পাওয়া যায়। চেয়ার থেকে লাভ ₹300 এবং টেবিল থেকে লাভ ₹500। লাভ সর্বাধিক করার জন্য উদ্দেশ্যমূলক অপেক্ষকটি কী হবে? (x = চেয়ারের সংখ্যা, y = টেবিলের সংখ্যা)
A furniture maker produces chairs and tables. Each chair requires 2 hours and each table requires 4 hours of labor. A total of 100 labor-hours are available per day. Profit from a chair is ₹300 and from a table is ₹500. What is the objective function to maximize profit? (x = no. of chairs, y = no. of tables)
A furniture maker produces chairs and tables. Each chair requires 2 hours and each table requires 4 hours of labor. A total of 100 labor-hours are available per day. Profit from a chair is ₹300 and from a table is ₹500. What is the objective function to maximize profit? (x = no. of chairs, y = no. of tables)
সঠিক উত্তর (Correct Answer): C) Max Z = 300x + 500y
ব্যাখ্যা: উদ্দেশ্যমূলক অপেক্ষক মোট লাভকে উপস্থাপন করে। যদি x সংখ্যক চেয়ার এবং y সংখ্যক টেবিল তৈরি করা হয়, তবে মোট লাভ হবে (প্রতি চেয়ারের লাভ × চেয়ারের সংখ্যা) + (প্রতি টেবিলের লাভ × টেবিলের সংখ্যা), অর্থাৎ 300x + 500y। যেহেতু লাভ সর্বাধিক করতে হবে, তাই এটি একটি Maximization সমস্যা।
Explanation: The objective function represents the total profit. If x chairs and y tables are produced, the total profit will be (profit per chair × no. of chairs) + (profit per table × no. of tables), which is 300x + 500y. Since the goal is to maximize profit, it’s a Maximization problem.
Explanation: The objective function represents the total profit. If x chairs and y tables are produced, the total profit will be (profit per chair × no. of chairs) + (profit per table × no. of tables), which is 300x + 500y. Since the goal is to maximize profit, it’s a Maximization problem.
4. একটি সেট S-কে উত্তল সেট (Convex Set) বলা হয় যদি সেটের যেকোনো দুটি বিন্দু P1 এবং P2-এর জন্য, সংযোগকারী রেখাংশ P1P2-এর সমস্ত বিন্দু…
A set S is called a Convex Set if for any two points P1 and P2 in the set, all points on the line segment joining P1 and P2 are…
A set S is called a Convex Set if for any two points P1 and P2 in the set, all points on the line segment joining P1 and P2 are…
সঠিক উত্তর (Correct Answer): B) সেটের ভিতরে থাকে / inside the set
ব্যাখ্যা: উত্তল সেটের সংজ্ঞা অনুযায়ী, সেটের যেকোনো দুটি বিন্দুকে যোগ করলে যে সরলরেখাংশ পাওয়া যায়, তার প্রতিটি বিন্দু অবশ্যই ওই সেটের মধ্যেই থাকতে হবে।
Explanation: By definition of a convex set, for any two points within the set, the line segment connecting them must lie entirely within the set.
Explanation: By definition of a convex set, for any two points within the set, the line segment connecting them must lie entirely within the set.
5. একটি LPP-এর সমস্ত সীমাবদ্ধতা দ্বারা নির্ধারিত সাধারণ অঞ্চলটিকে (common region) কী বলা হয়?
The common region determined by all the constraints of an LPP is called the:
The common region determined by all the constraints of an LPP is called the:
সঠিক উত্তর (Correct Answer): A) সম্ভাব্য অঞ্চল / Feasible region
ব্যাখ্যা: সম্ভাব্য অঞ্চল বা কার্যকরি অঞ্চল হলো সেই অঞ্চল যেখানে একটি LPP-এর সমস্ত সীমাবদ্ধতা একই সাথে সিদ্ধ হয়। এই অঞ্চলের যেকোনো বিন্দু একটি সম্ভাব্য সমাধান (feasible solution)।
Explanation: The feasible region is the area where all constraints of an LPP are satisfied simultaneously. Any point within this region is a feasible solution.
Explanation: The feasible region is the area where all constraints of an LPP are satisfied simultaneously. Any point within this region is a feasible solution.
6. রৈখিক প্রোগ্রামিং-এর মৌলিক উপপাদ্য (Fundamental Theorem of LPP) অনুযায়ী, যদি একটি অনুকূল সমাধান (optimal solution) বিদ্যমান থাকে, তবে এটি অবশ্যই সম্ভাব্য অঞ্চলের একটি _______ বিন্দুতে ঘটবে।
According to the Fundamental Theorem of LPP, if an optimal solution exists, it must occur at a/an _______ of the feasible region.
According to the Fundamental Theorem of LPP, if an optimal solution exists, it must occur at a/an _______ of the feasible region.
সঠিক উত্তর (Correct Answer): B) প্রান্তিক বিন্দু (শীর্ষবিন্দু) / extreme point (vertex)
ব্যাখ্যা: LPP-এর একটি গুরুত্বপূর্ণ উপপাদ্য হলো যে, যদি কোনো অনুকূল সমাধান থাকে, তাহলে সেটি সম্ভাব্য অঞ্চলের কোনো না কোনো প্রান্তিক বিন্দু বা শীর্ষবিন্দুতে (corner point) পাওয়া যাবে। যদি দুটি শীর্ষবিন্দুতে অনুকূল মান পাওয়া যায়, তবে তাদের সংযোগকারী রেখাংশের সমস্ত বিন্দুতেও একই অনুকূল মান পাওয়া যাবে।
Explanation: A key theorem in LPP states that if an optimal solution exists, it will be found at one of the extreme points (or corner points) of the feasible region. If the optimal value is found at two vertices, then all points on the line segment joining them will also yield the same optimal value.
Explanation: A key theorem in LPP states that if an optimal solution exists, it will be found at one of the extreme points (or corner points) of the feasible region. If the optimal value is found at two vertices, then all points on the line segment joining them will also yield the same optimal value.
7. একটি মৌলিক সম্ভাব্য সমাধান (Basic Feasible Solution – BFS) কী?
What is a Basic Feasible Solution (BFS)?
What is a Basic Feasible Solution (BFS)?
সঠিক উত্তর (Correct Answer): C) একটি মৌলিক সমাধান যা অ-ঋণাত্মক শর্ত (non-negativity condition) পূরণ করে / A basic solution that satisfies the non-negativity condition.
ব্যাখ্যা: একটি m x n সিস্টেম Ax=b-তে, একটি মৌলিক সমাধান (basic solution) পাওয়া যায় n-m সংখ্যক চলরাশিকে শূন্য ধরে। যদি এই মৌলিক সমাধানের সমস্ত চলরাশি অ-ঋণাত্মক (non-negative, অর্থাৎ ≥ 0) হয়, তবে তাকে মৌলিক সম্ভাব্য সমাধান বা BFS বলা হয়।
Explanation: In an m x n system Ax=b, a basic solution is obtained by setting n-m variables to zero. If all variables in this basic solution are non-negative (i.e., ≥ 0), then it is called a Basic Feasible Solution or BFS.
Explanation: In an m x n system Ax=b, a basic solution is obtained by setting n-m variables to zero. If all variables in this basic solution are non-negative (i.e., ≥ 0), then it is called a Basic Feasible Solution or BFS.
8. একটি LPP-কে তার স্ট্যান্ডার্ড ফর্মে (Standard Form) রূপান্তর করতে, যদি একটি সীমাবদ্ধতা ‘≤’ প্রকৃতির হয়, তবে আমরা কী যোগ করি?
To convert an LPP into its Standard Form, if a constraint is of ‘≤’ type, we add a:
To convert an LPP into its Standard Form, if a constraint is of ‘≤’ type, we add a:
সঠিক উত্তর (Correct Answer): A) স্ল্যাক চলরাশি / Slack variable
ব্যাখ্যা: স্ট্যান্ডার্ড ফর্মে, সমস্ত সীমাবদ্ধতা সমীকরণ (‘=’) আকারে থাকতে হয় এবং ডানদিকের মান (RHS) অ-ঋণাত্মক হতে হয়। ‘≤’ অসমীকরণকে সমীকরণে পরিণত করার জন্য বাম দিকে একটি অ-ঋণাত্মক স্ল্যাক চলরাশি যোগ করা হয়। যেমন, 2x + 3y ≤ 10 হয়ে যায় 2x + 3y + s1 = 10, যেখানে s1 ≥ 0।
Explanation: In standard form, all constraints must be equations (‘=’) and the right-hand side (RHS) values must be non-negative. To convert a ‘≤’ inequality into an equation, a non-negative slack variable is added to the left side. For example, 2x + 3y ≤ 10 becomes 2x + 3y + s1 = 10, where s1 ≥ 0.
Explanation: In standard form, all constraints must be equations (‘=’) and the right-hand side (RHS) values must be non-negative. To convert a ‘≤’ inequality into an equation, a non-negative slack variable is added to the left side. For example, 2x + 3y ≤ 10 becomes 2x + 3y + s1 = 10, where s1 ≥ 0.
9. একটি LPP-কে তার স্ট্যান্ডার্ড ফর্মে (Standard Form) রূপান্তর করতে, যদি একটি সীমাবদ্ধতা ‘≥’ প্রকৃতির হয়, তবে আমরা কী করি?
To convert an LPP into its Standard Form, if a constraint is of ‘≥’ type, we:
To convert an LPP into its Standard Form, if a constraint is of ‘≥’ type, we:
সঠিক উত্তর (Correct Answer): B) একটি উদ্বৃত্ত চলরাশি বিয়োগ করি / Subtract a surplus variable
ব্যাখ্যা: ‘≥’ অসমীকরণকে সমীকরণে পরিণত করার জন্য বাম দিক থেকে একটি অ-ঋণাত্মক উদ্বৃত্ত চলরাশি বিয়োগ করা হয়। যেমন, 4x + y ≥ 20 হয়ে যায় 4x + y – s2 = 20, যেখানে s2 ≥ 0।
Explanation: To convert a ‘≥’ inequality into an equation, a non-negative surplus variable is subtracted from the left side. For example, 4x + y ≥ 20 becomes 4x + y – s2 = 20, where s2 ≥ 0.
Explanation: To convert a ‘≥’ inequality into an equation, a non-negative surplus variable is subtracted from the left side. For example, 4x + y ≥ 20 becomes 4x + y – s2 = 20, where s2 ≥ 0.
10. গ্রাফিক্যাল পদ্ধতি (Graphical Method) ব্যবহার করে LPP সমাধান করা যায় যখন চলরাশির সংখ্যা হয়…
The graphical method can be used to solve an LPP when the number of variables is…
The graphical method can be used to solve an LPP when the number of variables is…
সঠিক উত্তর (Correct Answer): A) 2
ব্যাখ্যা: গ্রাফিক্যাল পদ্ধতি দ্বিমাত্রিক (2D) তলে কার্যকর, তাই এটি শুধুমাত্র দুটি চলরাশিযুক্ত সমস্যার জন্য উপযুক্ত। তিনটি চলরাশির জন্য এটি ত্রিমাত্রিক (3D) স্থানে কল্পনা করা কঠিন এবং দুটির বেশির জন্য অসম্ভব।
Explanation: The graphical method works on a two-dimensional (2D) plane, so it is only suitable for problems with two variables. For three variables, it becomes difficult to visualize in 3D space, and it’s impossible for more than two.
Explanation: The graphical method works on a two-dimensional (2D) plane, so it is only suitable for problems with two variables. For three variables, it becomes difficult to visualize in 3D space, and it’s impossible for more than two.
11. সিমপ্লেক্স পদ্ধতিতে (Simplex Method), একটি সর্বাধিকীকরণ (maximization) সমস্যার অনুকূল সমাধান (optimal solution) কখন পাওয়া যায়?
In the Simplex Method, the optimal solution for a maximization problem is reached when:
In the Simplex Method, the optimal solution for a maximization problem is reached when:
সঠিক উত্তর (Correct Answer): A) Zj – Cj সারির সমস্ত মান ≥ 0 / All values in the Zj – Cj row are ≥ 0
ব্যাখ্যা: একটি সর্বাধিকীকরণ সমস্যার জন্য সিমপ্লেক্স টেবিলের অপ্টিমালিটি শর্ত হলো Zj – Cj (বা Cj – Zj ≤ 0) সারির সমস্ত মান অ-ঋণাত্মক (non-negative) হতে হবে। এর অর্থ হলো, সমাধানে আর কোনো উন্নতি সম্ভব নয়।
Explanation: For a maximization problem, the optimality condition in a simplex tableau is that all values in the Zj – Cj row (or Cj – Zj ≤ 0) must be non-negative. This indicates that no further improvement in the solution is possible.
Explanation: For a maximization problem, the optimality condition in a simplex tableau is that all values in the Zj – Cj row (or Cj – Zj ≤ 0) must be non-negative. This indicates that no further improvement in the solution is possible.
12. যদি প্রাইমাল (Primal) সমস্যাটি একটি সর্বাধিকীকরণ (Maximization) সমস্যা হয়, তবে তার ডুয়াল (Dual) সমস্যাটি কী হবে?
If the Primal problem is a Maximization problem, then its Dual problem will be a:
If the Primal problem is a Maximization problem, then its Dual problem will be a:
সঠিক উত্তর (Correct Answer): B) ন্যূনতমকরণ সমস্যা / Minimization problem
ব্যাখ্যা: ডুয়ালিটির একটি মৌলিক নিয়ম হলো, যদি প্রাইমাল সমস্যাটি সর্বাধিকীকরণের হয়, তবে তার ডুয়াল সমস্যাটি ন্যূনতমকরণের হবে, এবং এর বিপরীতটিও সত্য।
Explanation: A fundamental rule of duality is that if the primal problem is maximization, its dual will be a minimization problem, and vice-versa.
Explanation: A fundamental rule of duality is that if the primal problem is maximization, its dual will be a minimization problem, and vice-versa.
13. একটি LPP-এর ডুয়ালের ডুয়াল (The dual of the dual) কী?
The dual of the dual of an LPP is the:
The dual of the dual of an LPP is the:
সঠিক উত্তর (Correct Answer): B) প্রাইমাল সমস্যা / Primal problem
ব্যাখ্যা: এটি ডুয়ালিটি তত্ত্বের একটি গুরুত্বপূর্ণ উপপাদ্য। একটি রৈখিক প্রোগ্রামিং সমস্যার ডুয়াল তৈরি করে, এবং তারপর সেই ডুয়াল সমস্যার আবার ডুয়াল তৈরি করলে মূল প্রাইমাল সমস্যাটিই ফিরে আসে।
Explanation: This is an important theorem in duality theory. If you formulate the dual of an LPP, and then formulate the dual of that resulting dual problem, you get back the original primal problem.
Explanation: This is an important theorem in duality theory. If you formulate the dual of an LPP, and then formulate the dual of that resulting dual problem, you get back the original primal problem.
14. একটি পরিবহন সমস্যাকে (Transportation Problem) সুষম (balanced) বলা হয় যদি…
A Transportation Problem is said to be balanced if…
A Transportation Problem is said to be balanced if…
সঠিক উত্তর (Correct Answer): C) মোট যোগান = মোট চাহিদা / Total Supply = Total Demand
ব্যাখ্যা: একটি পরিবহন সমস্যায়, যদি সমস্ত উৎস থেকে মোট যোগানের পরিমাণ সমস্ত গন্তব্যের মোট চাহিদার পরিমাণের সমান হয়, তবে সমস্যাটিকে সুষম বা ভারসাম্যযুক্ত বলা হয়।
Explanation: In a transportation problem, if the total amount of supply from all sources equals the total amount of demand at all destinations, the problem is called balanced.
Explanation: In a transportation problem, if the total amount of supply from all sources equals the total amount of demand at all destinations, the problem is called balanced.
15. অ্যাসাইনমেন্ট সমস্যা (Assignment Problem) সমাধানের জন্য কোন পদ্ধতিটি সবচেয়ে বেশি ব্যবহৃত হয়?
Which method is most commonly used to solve an Assignment Problem?
Which method is most commonly used to solve an Assignment Problem?
সঠিক উত্তর (Correct Answer): C) হাঙ্গেরিয়ান পদ্ধতি / Hungarian Method
ব্যাখ্যা: হাঙ্গেরিয়ান পদ্ধতি হলো অ্যাসাইনমেন্ট সমস্যা সমাধানের জন্য একটি বিশেষ এবং কার্যকর অ্যালগরিদম। এটি পরিবহন সমস্যার একটি বিশেষ রূপ হলেও, হাঙ্গেরিয়ান পদ্ধতিটি এর জন্য অনেক বেশি কার্যকরী।
Explanation: The Hungarian method is a specialized and efficient algorithm designed specifically for solving assignment problems. Although an assignment problem is a special case of a transportation problem, the Hungarian method is much more efficient for it.
Explanation: The Hungarian method is a specialized and efficient algorithm designed specifically for solving assignment problems. Although an assignment problem is a special case of a transportation problem, the Hungarian method is much more efficient for it.
16. একটি LPP-তে, যদি সম্ভাব্য অঞ্চলটি অসীম (unbounded) হয়, তাহলে সমাধানটি হবে…
In an LPP, if the feasible region is unbounded, then the solution will be…
In an LPP, if the feasible region is unbounded, then the solution will be…
সঠিক উত্তর (Correct Answer): C) সসীম বা অসীম হতে পারে / Can be bounded or unbounded
ব্যাখ্যা: একটি অসীম সম্ভাব্য অঞ্চলের ক্ষেত্রে, অনুকূল সমাধান থাকতেও পারে, আবার নাও থাকতে পারে। যদি উদ্দেশ্যমূলক অপেক্ষকের মান সম্ভাব্য অঞ্চলের দিকে অসীমভাবে বাড়তে বা কমতে থাকে, তবে সমাধানটি অসীম (unbounded) হবে। কিন্তু যদি তা না হয়, তবে একটি সসীম (bounded) অনুকূল সমাধানও থাকতে পারে।
Explanation: For an unbounded feasible region, an optimal solution may or may not exist. If the value of the objective function can be increased or decreased indefinitely in the direction of the feasible region, the solution is unbounded. However, if that’s not the case, a bounded optimal solution can still exist.
Explanation: For an unbounded feasible region, an optimal solution may or may not exist. If the value of the objective function can be increased or decreased indefinitely in the direction of the feasible region, the solution is unbounded. However, if that’s not the case, a bounded optimal solution can still exist.
17. যদি একটি LPP-এর কোনো সম্ভাব্য অঞ্চল (feasible region) না থাকে, তাহলে সমস্যাটির…
If an LPP has no feasible region, then the problem has…
If an LPP has no feasible region, then the problem has…
সঠিক উত্তর (Correct Answer): C) কোনো সম্ভাব্য সমাধান নেই / No feasible solution
ব্যাখ্যা: সম্ভাব্য অঞ্চল হলো সেই জায়গা যেখানে সমাধান থাকতে পারে। যদি সীমাবদ্ধতাগুলি পরস্পরবিরোধী হয় এবং কোনো সাধারণ অঞ্চল তৈরি না করে, তাহলে কোনো বিন্দুতেই সমস্ত শর্ত পূরণ করা সম্ভব নয়। এই অবস্থাকে অসম্ভাব্য (infeasible) বলা হয়।
Explanation: The feasible region is where a solution can exist. If the constraints are contradictory and do not form a common region, then no point can satisfy all conditions. This situation is called infeasible.
Explanation: The feasible region is where a solution can exist. If the constraints are contradictory and do not form a common region, then no point can satisfy all conditions. This situation is called infeasible.
18. একটি LPP-কে ম্যাট্রিক্স আকারে (Matrix Form) প্রকাশ করা হয়: Maximize Z = cX subject to AX ≤ b and X ≥ 0। এখানে ‘c’ কী?
An LPP in matrix form is expressed as: Maximize Z = cX subject to AX ≤ b and X ≥ 0. Here, ‘c’ represents the:
An LPP in matrix form is expressed as: Maximize Z = cX subject to AX ≤ b and X ≥ 0. Here, ‘c’ represents the:
সঠিক উত্তর (Correct Answer): C) মূল্য (ব্যয় বা লাভ) ভেক্টর / Cost (or profit) vector
ব্যাখ্যা: ম্যাট্রিক্স ফর্মে, ‘c’ হলো একটি সারি ভেক্টর যা উদ্দেশ্যমূলক অপেক্ষকের প্রতিটি চলরাশির সহগ (coefficients) ধারণ করে। এই সহগগুলি সাধারণত লাভ বা ব্যয়কে নির্দেশ করে।
Explanation: In matrix form, ‘c’ is a row vector containing the coefficients of each variable in the objective function. These coefficients typically represent profit or cost.
Explanation: In matrix form, ‘c’ is a row vector containing the coefficients of each variable in the objective function. These coefficients typically represent profit or cost.
19. সিমপ্লেক্স পদ্ধতিতে, কৃত্রিম চলরাশি (Artificial Variable) কখন ব্যবহার করা হয়?
In the Simplex method, when is an Artificial Variable used?
In the Simplex method, when is an Artificial Variable used?
সঠিক উত্তর (Correct Answer): B) ‘≥’ বা ‘=’ সীমাবদ্ধতার জন্য / For a ‘≥’ or ‘=’ constraint
ব্যাখ্যা: ‘≥’ বা ‘=’ প্রকৃতির সীমাবদ্ধতাগুলির জন্য একটি প্রাথমিক মৌলিক সম্ভাব্য সমাধান (initial BFS) সহজে পাওয়া যায় না। এই ধরনের ক্ষেত্রে একটি কৃত্রিম চলরাশি যোগ করে প্রাথমিক সমাধান তৈরি করা হয়। Big-M পদ্ধতি বা Two-Phase পদ্ধতিতে এই চলরাশিগুলিকে পরে সমাধান থেকে বাদ দেওয়া হয়।
Explanation: For constraints of ‘≥’ or ‘=’ type, an initial basic feasible solution (BFS) is not readily available. In such cases, an artificial variable is added to create an initial solution. These variables are then driven out of the solution in later steps using the Big-M method or the Two-Phase method.
Explanation: For constraints of ‘≥’ or ‘=’ type, an initial basic feasible solution (BFS) is not readily available. In such cases, an artificial variable is added to create an initial solution. These variables are then driven out of the solution in later steps using the Big-M method or the Two-Phase method.
20. যদি প্রাইমাল এবং ডুয়াল উভয়েরই সম্ভাব্য সমাধান থাকে, তাহলে প্রাইমালের অনুকূল উদ্দেশ্যমূলক মান (optimal objective value) ডুয়ালের অনুকূল উদ্দেশ্যমূলক মানের সাথে কীভাবে সম্পর্কিত?
If both the primal and the dual have feasible solutions, then how is the optimal objective value of the primal related to the optimal objective value of the dual?
If both the primal and the dual have feasible solutions, then how is the optimal objective value of the primal related to the optimal objective value of the dual?
সঠিক উত্তর (Correct Answer): C) প্রাইমালের মান = ডুয়ালের মান / Primal value = Dual value
ব্যাখ্যা: ডুয়ালিটি তত্ত্বের শক্তিশালী উপপাদ্য (Strong Duality Theorem) অনুযায়ী, যদি একটি সমস্যার অনুকূল সমাধান থাকে, তবে তার ডুয়াল সমস্যারও একটি অনুকূল সমাধান থাকবে এবং তাদের উদ্দেশ্যমূলক অপেক্ষকের অনুকূল মান দুটি সমান হবে। (Max Z = Min W)।
Explanation: According to the Strong Duality Theorem, if a problem has an optimal solution, then its dual problem also has an optimal solution, and their optimal objective function values are equal (Max Z = Min W).
Explanation: According to the Strong Duality Theorem, if a problem has an optimal solution, then its dual problem also has an optimal solution, and their optimal objective function values are equal (Max Z = Min W).
21. n-মাত্রিক স্থানে, c1x1 + c2x2 + … + cnxn = k সমীকরণটি কী উপস্থাপন করে?
In an n-dimensional space, the equation c1x1 + c2x2 + … + cnxn = k represents a:
In an n-dimensional space, the equation c1x1 + c2x2 + … + cnxn = k represents a:
সঠিক উত্তর (Correct Answer): A) হাইপারপ্লেন / Hyperplane
ব্যাখ্যা: একটি হাইপারপ্লেন হলো একটি রৈখিক সমীকরণ দ্বারা সংজ্ঞায়িত একটি উপ-স্থান, যার মাত্রা মূল স্থানের চেয়ে এক কম। দ্বিমাত্রিক স্থানে এটি একটি সরলরেখা, এবং ত্রিমাত্রিক স্থানে এটি একটি সমতল। n-মাত্রিক স্থানে এটিকে হাইপারপ্লেন বলা হয়। LPP-তে সীমাবদ্ধতাগুলি হাইপারপ্লেন তৈরি করে।
Explanation: A hyperplane is a subspace defined by a single linear equation, whose dimension is one less than that of the ambient space. In 2D, it’s a line; in 3D, it’s a plane. In n-dimensions, it’s called a hyperplane. Constraints in an LPP define hyperplanes.
Explanation: A hyperplane is a subspace defined by a single linear equation, whose dimension is one less than that of the ambient space. In 2D, it’s a line; in 3D, it’s a plane. In n-dimensions, it’s called a hyperplane. Constraints in an LPP define hyperplanes.
22. একটি LPP-এর সম্ভাব্য অঞ্চল (feasible region) সর্বদা একটি…
The feasible region of an LPP is always a…
The feasible region of an LPP is always a…
সঠিক উত্তর (Correct Answer): A) উত্তল পলিহেড্রন / Convex Polyhedron
ব্যাখ্যা: রৈখিক অসমীকরণ দ্বারা আবদ্ধ অঞ্চল সর্বদা উত্তল হয়। সসীম সংখ্যক রৈখিক অসমীকরণের ছেদ দ্বারা গঠিত অঞ্চলকে উত্তল পলিহেড্রন বলে। LPP-এর সম্ভাব্য অঞ্চল ঠিক এইভাবেই গঠিত হয়।
Explanation: A region bounded by linear inequalities is always convex. The intersection of a finite number of linear inequalities forms a convex polyhedron. The feasible region of an LPP is formed in exactly this way.
Explanation: A region bounded by linear inequalities is always convex. The intersection of a finite number of linear inequalities forms a convex polyhedron. The feasible region of an LPP is formed in exactly this way.
23. পরিবহন সমস্যায়, কোন পদ্ধতিটি প্রায়শই অনুকূল সমাধানের সবচেয়ে কাছাকাছি একটি প্রাথমিক সম্ভাব্য সমাধান (initial feasible solution) দেয়?
In transportation problems, which method often gives an initial feasible solution that is closest to the optimal solution?
In transportation problems, which method often gives an initial feasible solution that is closest to the optimal solution?
সঠিক উত্তর (Correct Answer): C) ভোগেলের আনুমানিক পদ্ধতি (VAM) / Vogel’s Approximation Method (VAM)
ব্যাখ্যা: VAM পদ্ধতিটি প্রতিটি সারি এবং কলামের জন্য পেনাল্টি (penalty) গণনা করে, যা সর্বনিম্ন এবং দ্বিতীয় সর্বনিম্ন ব্যয়ের মধ্যে পার্থক্য। এটি সুযোগ ব্যয় (opportunity cost)-কে বিবেচনা করে, তাই এর দ্বারা প্রাপ্ত প্রাথমিক সমাধানটি সাধারণত নর্থ-ওয়েস্ট কর্নার বা ন্যূনতম ব্যয় পদ্ধতির চেয়ে ভালো হয়।
Explanation: The VAM method calculates a penalty for each row and column, which is the difference between the smallest and second smallest costs. It considers the opportunity cost, so the initial solution it provides is generally better than those from the North-West Corner or Least Cost methods.
Explanation: The VAM method calculates a penalty for each row and column, which is the difference between the smallest and second smallest costs. It considers the opportunity cost, so the initial solution it provides is generally better than those from the North-West Corner or Least Cost methods.
24. একটি m x n পরিবহন সমস্যায়, যদি বরাদ্দকৃত সেলের (allocated cells) সংখ্যা m + n – 1-এর চেয়ে কম হয়, তবে সমাধানটিকে কী বলা হয়?
In an m x n transportation problem, if the number of allocated cells is less than m + n – 1, the solution is called:
In an m x n transportation problem, if the number of allocated cells is less than m + n – 1, the solution is called:
সঠিক উত্তর (Correct Answer): A) ডিজেনারেট / Degenerate
ব্যাখ্যা: একটি পরিবহন সমস্যার মৌলিক সম্ভাব্য সমাধানের জন্য ঠিক m+n-1 সংখ্যক বরাদ্দকৃত সেল থাকা প্রয়োজন। যদি এর চেয়ে কম থাকে, তবে সমাধানটি ডিজেনারেট হয়। এই অবস্থাটি অপ্টিমালিটি পরীক্ষার সময় সমস্যা তৈরি করতে পারে।
Explanation: For a basic feasible solution in a transportation problem, exactly m+n-1 allocated cells are required. If there are fewer than this, the solution is degenerate. This condition can cause issues during the optimality test.
Explanation: For a basic feasible solution in a transportation problem, exactly m+n-1 allocated cells are required. If there are fewer than this, the solution is degenerate. This condition can cause issues during the optimality test.
25. যদি একটি চলরাশি x, চিহ্নে সীমাবদ্ধ না থাকে (unrestricted in sign), তবে এটিকে কীভাবে দুটি অ-ঋণাত্মক চলরাশি দ্বারা প্রতিস্থাপন করা যায়?
If a variable x is unrestricted in sign, how can it be replaced by two non-negative variables?
If a variable x is unrestricted in sign, how can it be replaced by two non-negative variables?
সঠিক উত্তর (Correct Answer): B) x = x’ – x”
ব্যাখ্যা: যেকোনো বাস্তব সংখ্যাকে দুটি অ-ঋণাত্মক সংখ্যার বিয়োগফল হিসাবে প্রকাশ করা যায়। তাই, যদি x unrestricted হয়, আমরা x = x’ – x” লিখি, যেখানে x’ ≥ 0 এবং x” ≥ 0। এটি LPP সমাধানের জন্য একটি স্ট্যান্ডার্ড কৌশল।
Explanation: Any real number can be expressed as the difference of two non-negative numbers. Therefore, if x is unrestricted, we write x = x’ – x”, where x’ ≥ 0 and x” ≥ 0. This is a standard technique for solving LPPs.
Explanation: Any real number can be expressed as the difference of two non-negative numbers. Therefore, if x is unrestricted, we write x = x’ – x”, where x’ ≥ 0 and x” ≥ 0. This is a standard technique for solving LPPs.
26. একটি সর্বাধিকীকরণ (maximization) সিমপ্লেক্স সমস্যায়, কোন চলরাশিটি পরবর্তী ইটারেশনে বেসিসে প্রবেশ করবে (entering variable)?
In a maximization simplex problem, which variable enters the basis in the next iteration (entering variable)?
In a maximization simplex problem, which variable enters the basis in the next iteration (entering variable)?
সঠিক উত্তর (Correct Answer): B) Zj – Cj সারিতে সবচেয়ে ঋণাত্মক মানযুক্ত চলরাশি / The variable with the most negative value in the Zj – Cj row.
ব্যাখ্যা: সর্বাধিকীকরণ সমস্যায়, Zj – Cj সারির সবচেয়ে ঋণাত্মক মানটি নির্দেশ করে যে কোন চলরাশিটি বেসিসে প্রবেশ করলে উদ্দেশ্যমূলক অপেক্ষকের মান সবচেয়ে বেশি বৃদ্ধি পাবে। (দ্রষ্টব্য: যদি Cj – Zj সারি ব্যবহার করা হয়, তবে সবচেয়ে ধনাত্মক মানটি বেছে নেওয়া হয়)।
Explanation: In a maximization problem, the most negative value in the Zj – Cj row indicates the variable that will cause the greatest increase in the objective function value if it enters the basis. (Note: If the Cj – Zj row is used, the most positive value is chosen).
Explanation: In a maximization problem, the most negative value in the Zj – Cj row indicates the variable that will cause the greatest increase in the objective function value if it enters the basis. (Note: If the Cj – Zj row is used, the most positive value is chosen).
27. সিমপ্লেক্স পদ্ধতিতে, বেসিস থেকে কোন চলরাশিটি বেরিয়ে যাবে (leaving variable) তা কীভাবে নির্ধারণ করা হয়?
In the simplex method, how is the leaving variable from the basis determined?
In the simplex method, how is the leaving variable from the basis determined?
সঠিক উত্তর (Correct Answer): A) ন্যূনতম অনুপাতের নিয়ম দ্বারা / By the minimum ratio rule.
ব্যাখ্যা: সমাধান কলামের (Solution/RHS column) প্রতিটি মানকে পিভট কলামের সংশ্লিষ্ট ধনাত্মক মান দিয়ে ভাগ করে অনুপাত গণনা করা হয়। যে সারিটি সর্বনিম্ন অ-ঋণাত্মক অনুপাত দেয়, সেই সারির মৌলিক চলরাশিটি (basic variable) বেসিস থেকে বেরিয়ে যায়। এটি সমাধানের কার্যকারিতা (feasibility) বজায় রাখে।
Explanation: The ratio is calculated by dividing each value in the solution (RHS) column by the corresponding positive value in the pivot column. The basic variable in the row that yields the minimum non-negative ratio leaves the basis. This maintains the feasibility of the solution.
Explanation: The ratio is calculated by dividing each value in the solution (RHS) column by the corresponding positive value in the pivot column. The basic variable in the row that yields the minimum non-negative ratio leaves the basis. This maintains the feasibility of the solution.
28. সিমপ্লেক্স টেবিলের অনুকূল সমাধানে (optimal solution) যদি কোনো অ-মৌলিক চলরাশির (non-basic variable) জন্য Zj – Cj = 0 হয়, তবে এটি কী নির্দেশ করে?
In an optimal simplex tableau, if Zj – Cj = 0 for a non-basic variable, what does it indicate?
In an optimal simplex tableau, if Zj – Cj = 0 for a non-basic variable, what does it indicate?
সঠিক উত্তর (Correct Answer): A) একাধিক বা বিকল্প অনুকূল সমাধান / Multiple or alternative optimal solutions
ব্যাখ্যা: যখন অনুকূল অবস্থায় পৌঁছানোর পর কোনো অ-মৌলিক চলরাশির Zj – Cj মান শূন্য হয়, তার মানে হলো ওই চলরাশিটিকে বেসিসে প্রবেশ করালেও উদ্দেশ্যমূলক অপেক্ষকের মানের কোনো পরিবর্তন হবে না। এটি একটি ভিন্ন মৌলিক সমাধান দেবে যা একই অনুকূল মান দেয়, অর্থাৎ একাধিক অনুকূল সমাধান বিদ্যমান।
Explanation: When an optimal solution is reached and a non-basic variable has a Zj – Cj value of zero, it means that bringing this variable into the basis will not change the objective function’s value. This will lead to a different basic solution with the same optimal value, indicating the existence of multiple optimal solutions.
Explanation: When an optimal solution is reached and a non-basic variable has a Zj – Cj value of zero, it means that bringing this variable into the basis will not change the objective function’s value. This will lead to a different basic solution with the same optimal value, indicating the existence of multiple optimal solutions.
29. সিমপ্লেক্স পদ্ধতিতে, যদি একটি প্রবেশকারী চলরাশির (entering variable) পিভট কলামের সমস্ত উপাদান ঋণাত্মক বা শূন্য হয়, তবে এটি কী নির্দেশ করে?
In the simplex method, if all elements in the pivot column of an entering variable are negative or zero, what does it indicate?
In the simplex method, if all elements in the pivot column of an entering variable are negative or zero, what does it indicate?
সঠিক উত্তর (Correct Answer): A) অসীম সমাধান / Unbounded solution
ব্যাখ্যা: এই পরিস্থিতিতে, ন্যূনতম অনুপাত গণনা করা সম্ভব হয় না, কারণ কোনো ধনাত্মক ভাজক নেই। এর অর্থ হলো, প্রবেশকারী চলরাশির মান সীমাহীনভাবে বাড়ানো সম্ভব এবং উদ্দেশ্যমূলক অপেক্ষকের মানও অসীম পর্যন্ত বাড়তে থাকবে।
Explanation: In this situation, the minimum ratio cannot be calculated as there are no positive divisors. This means the entering variable can be increased indefinitely without limit, and the objective function value will also increase to infinity.
Explanation: In this situation, the minimum ratio cannot be calculated as there are no positive divisors. This means the entering variable can be increased indefinitely without limit, and the objective function value will also increase to infinity.
30. Big-M পদ্ধতিতে, অনুকূল সমাধানে যদি একটি কৃত্রিম চলরাশি (artificial variable) ধনাত্মক মানসহ বেসিসে থেকে যায়, তাহলে মূল সমস্যাটির সমাধান কী?
In the Big-M method, if an artificial variable remains in the basis with a positive value in the optimal solution, what is the solution to the original problem?
In the Big-M method, if an artificial variable remains in the basis with a positive value in the optimal solution, what is the solution to the original problem?
সঠিক উত্তর (Correct Answer): A) কোনো সম্ভাব্য সমাধান নেই (অসম্ভাব্য) / No feasible solution (Infeasible)
ব্যাখ্যা: কৃত্রিম চলরাশিগুলির কোনো বাস্তব অর্থ নেই এবং এগুলি শুধুমাত্র প্রাথমিক সমাধান খুঁজে বের করার জন্য ব্যবহৃত হয়। Big-M পদ্ধতিতে, এই চলরাশিগুলিকে একটি বড় পেনাল্টি (M) দিয়ে উদ্দেশ্যমূলক অপেক্ষক থেকে বাদ দেওয়ার চেষ্টা করা হয়। যদি চূড়ান্ত সমাধানেও কোনো কৃত্রিম চলরাশি ধনাত্মক মান নিয়ে থেকে যায়, তার মানে হলো মূল সমস্যার কোনো সম্ভাব্য সমাধান নেই।
Explanation: Artificial variables have no real meaning and are only used to find an initial solution. In the Big-M method, a large penalty (M) is used to drive these variables out of the objective function. If an artificial variable remains in the final solution with a positive value, it means the original problem has no feasible solution.
Explanation: Artificial variables have no real meaning and are only used to find an initial solution. In the Big-M method, a large penalty (M) is used to drive these variables out of the objective function. If an artificial variable remains in the final solution with a positive value, it means the original problem has no feasible solution.
31. যদি একটি প্রাইমাল (Primal) সর্বাধিকীকরণ সমস্যায় ‘i’-তম সীমাবদ্ধতাটি একটি সমীকরণ (‘=’) হয়, তবে ডুয়াল (Dual) ন্যূনতমকরণ সমস্যায় সংশ্লিষ্ট ‘i’-তম চলরাশিটি কী হবে?
If the i-th constraint in a Primal maximization problem is an equality (‘=’), then the corresponding i-th variable in the Dual minimization problem will be:
If the i-th constraint in a Primal maximization problem is an equality (‘=’), then the corresponding i-th variable in the Dual minimization problem will be:
সঠিক উত্তর (Correct Answer): C) চিহ্নে সীমাবদ্ধ নয় (Unrestricted in sign)
ব্যাখ্যা: প্রাইমাল-ডুয়াল সম্পর্ক অনুযায়ী:
- প্রাইমালের অসমীকরণ (‘≤’ বা ‘≥’) সীমাবদ্ধতা ডুয়ালের একটি চিহ্নে সীমাবদ্ধ চলরাশির (≥0 বা ≤0) সাথে সম্পর্কিত।
- প্রাইমালের সমীকরণ (‘=’) সীমাবদ্ধতা ডুয়ালের একটি চিহ্নে সীমাবদ্ধ নয় এমন চলরাশির (unrestricted) সাথে সম্পর্কিত।
- An inequality constraint (‘≤’ or ‘≥’) in the primal corresponds to a sign-restricted variable (≥0 or ≤0) in the dual.
- An equality constraint (‘=’) in the primal corresponds to an unrestricted variable in the dual.
32. দুর্বল ডুয়ালিটি উপপাদ্য (Weak Duality Theorem) অনুযায়ী, একটি সর্বাধিকীকরণ প্রাইমাল সমস্যার যেকোনো সম্ভাব্য সমাধানের মান…
According to the Weak Duality Theorem, the value of any feasible solution to a maximization primal problem is…
According to the Weak Duality Theorem, the value of any feasible solution to a maximization primal problem is…
সঠিক উত্তর (Correct Answer): C) সংশ্লিষ্ট ডুয়াল সমস্যার যেকোনো সম্ভাব্য সমাধানের মানের চেয়ে কম বা সমান / Less than or equal to the value of any feasible solution to its corresponding dual problem.
ব্যাখ্যা: দুর্বল ডুয়ালিটি উপপাদ্য বলে যে, যদি প্রাইমালটি একটি সর্বাধিকীকরণ সমস্যা হয় (Max Z), এবং ডুয়ালটি একটি ন্যূনতমকরণ সমস্যা হয় (Min W), তাহলে যেকোনো সম্ভাব্য প্রাইমাল সমাধানের জন্য Z ≤ W হবে। অর্থাৎ, প্রাইমালের উদ্দেশ্যমূলক অপেক্ষকের মান সর্বদা ডুয়ালের মানের চেয়ে কম বা সমান হবে।
Explanation: The Weak Duality Theorem states that if the primal is a maximization problem (Max Z), and the dual is a minimization problem (Min W), then for any feasible primal solution, Z ≤ W. That is, the primal’s objective function value will always be less than or equal to the dual’s value.
Explanation: The Weak Duality Theorem states that if the primal is a maximization problem (Max Z), and the dual is a minimization problem (Min W), then for any feasible primal solution, Z ≤ W. That is, the primal’s objective function value will always be less than or equal to the dual’s value.
33. একটি LPP-এর ডুয়াল চলরাশির (dual variables) অনুকূল মানগুলিকে প্রায়শই কী বলা হয়?
The optimal values of the dual variables in an LPP are often referred to as:
The optimal values of the dual variables in an LPP are often referred to as:
সঠিক উত্তর (Correct Answer): A) ছায়া মূল্য / Shadow prices
ব্যাখ্যা: একটি ডুয়াল চলরাশির অনুকূল মান (ছায়া মূল্য) নির্দেশ করে যে সংশ্লিষ্ট প্রাইমাল সীমাবদ্ধতার ডান দিকের (RHS) মান এক একক বৃদ্ধি করলে উদ্দেশ্যমূলক অপেক্ষকের মানে কতটা পরিবর্তন হবে। এটি একটি সম্পদের প্রান্তিক মূল্য (marginal value) বোঝায়।
Explanation: The optimal value of a dual variable (shadow price) indicates the amount by which the objective function value will change if the right-hand side (RHS) of the corresponding primal constraint is increased by one unit. It represents the marginal value of a resource.
Explanation: The optimal value of a dual variable (shadow price) indicates the amount by which the objective function value will change if the right-hand side (RHS) of the corresponding primal constraint is increased by one unit. It represents the marginal value of a resource.
34. কমপ্লিমেন্টারি স্ল্যাকনেস (Complementary Slackness) শর্ত অনুযায়ী, যদি একটি প্রাইমাল সীমাবদ্ধতা অনুকূল সমাধানে কঠোরভাবে (<) পূরণ হয় (অর্থাৎ স্ল্যাক চলরাশি > 0), তাহলে সংশ্লিষ্ট ডুয়াল চলরাশির মান কী হবে?
According to the Complementary Slackness condition, if a primal constraint is satisfied as a strict inequality (<) at optimality (i.e., its slack variable > 0), then the value of the corresponding dual variable must be:
According to the Complementary Slackness condition, if a primal constraint is satisfied as a strict inequality (<) at optimality (i.e., its slack variable > 0), then the value of the corresponding dual variable must be:
সঠিক উত্তর (Correct Answer): C) শূন্য / Zero
ব্যাখ্যা: কমপ্লিমেন্টারি স্ল্যাকনেস তত্ত্ব বলে যে, একটি প্রাইমাল চলরাশি এবং সংশ্লিষ্ট ডুয়াল স্ল্যাক/সারপ্লাস চলরাশির গুণফল শূন্য হবে, এবং একটি প্রাইমাল স্ল্যাক/সারপ্লাস চলরাশি এবং সংশ্লিষ্ট ডুয়াল চলরাশির গুণফল শূন্য হবে। সহজ কথায়, যদি একটি সীমাবদ্ধতায় কিছু “অবশিষ্ট” (slack) থাকে, তবে সেই সীমাবদ্ধতার ছায়া মূল্য (dual variable) শূন্য হবে।
Explanation: The Complementary Slackness theorem states that the product of a primal variable and its corresponding dual slack/surplus variable is zero, and the product of a primal slack/surplus variable and its corresponding dual variable is zero. Simply put, if a resource (constraint) is not fully used (has slack), its shadow price (dual variable) is zero.
Explanation: The Complementary Slackness theorem states that the product of a primal variable and its corresponding dual slack/surplus variable is zero, and the product of a primal slack/surplus variable and its corresponding dual variable is zero. Simply put, if a resource (constraint) is not fully used (has slack), its shadow price (dual variable) is zero.
35. একটি পরিবহন সমস্যায় যদি মোট যোগান (supply) মোট চাহিদা (demand) থেকে বেশি হয়, তবে সমস্যাটিকে ভারসাম্যপূর্ণ করার জন্য কী করতে হবে?
In a transportation problem, if the total supply is greater than the total demand, what must be done to balance the problem?
In a transportation problem, if the total supply is greater than the total demand, what must be done to balance the problem?
সঠিক উত্তর (Correct Answer): B) একটি ডামি গন্তব্য (dummy destination) যোগ করতে হবে / Add a dummy destination
ব্যাখ্যা: ভারসাম্য বজায় রাখার জন্য, একটি কৃত্রিম বা ডামি গন্তব্য যোগ করা হয়। এই ডামি গন্তব্যের চাহিদা হবে (মোট যোগান – মোট চাহিদা)-এর সমান। এই গন্তব্যে পরিবহনের ব্যয় শূন্য ধরা হয়।
Explanation: To maintain balance, an artificial or dummy destination is added. The demand for this dummy destination will be equal to (Total Supply – Total Demand). The transportation cost to this destination is considered to be zero.
Explanation: To maintain balance, an artificial or dummy destination is added. The demand for this dummy destination will be equal to (Total Supply – Total Demand). The transportation cost to this destination is considered to be zero.
36. পরিবহন সমস্যার অনুকূলতা পরীক্ষা করার জন্য ব্যবহৃত MODI (Modified Distribution) পদ্ধতিটি কোন ধারণার উপর ভিত্তি করে?
The MODI (Modified Distribution) method, used for testing the optimality of a transportation problem, is based on the concept of:
The MODI (Modified Distribution) method, used for testing the optimality of a transportation problem, is based on the concept of:
সঠিক উত্তর (Correct Answer): A) ডুয়ালিটি / Duality
ব্যাখ্যা: MODI বা u-v পদ্ধতিটি পরিবহন সমস্যার ডুয়াল চলরাশি (u_i এবং v_j) ব্যবহার করে। এটি খালি সেলগুলির জন্য সুযোগ ব্যয় (opportunity costs) বা d_ij = c_ij – (u_i + v_j) গণনা করে। যদি সমস্ত d_ij ≥ 0 হয়, তাহলে সমাধানটি অনুকূল। এটি ডুয়ালিটি তত্ত্বের একটি প্রত্যক্ষ প্রয়োগ।
Explanation: The MODI or u-v method uses the dual variables (u_i and v_j) of the transportation problem. It calculates the opportunity costs or d_ij = c_ij – (u_i + v_j) for the unoccupied cells. If all d_ij ≥ 0, the solution is optimal. This is a direct application of duality theory.
Explanation: The MODI or u-v method uses the dual variables (u_i and v_j) of the transportation problem. It calculates the opportunity costs or d_ij = c_ij – (u_i + v_j) for the unoccupied cells. If all d_ij ≥ 0, the solution is optimal. This is a direct application of duality theory.
37. একটি সর্বাধিকীকরণ অ্যাসাইনমেন্ট সমস্যাকে (maximization assignment problem) হাঙ্গেরিয়ান পদ্ধতি ব্যবহার করে সমাধান করার জন্য প্রথম পদক্ষেপ কী?
What is the first step to solve a maximization assignment problem using the Hungarian method?
What is the first step to solve a maximization assignment problem using the Hungarian method?
সঠিক উত্তর (Correct Answer): B) সম্পূর্ণ ম্যাট্রিক্সটিকে একটি সুযোগ-ক্ষতি ম্যাট্রিক্সে (opportunity-loss matrix) রূপান্তর করা / Converting the entire matrix into an opportunity-loss matrix
ব্যাখ্যা: হাঙ্গেরিয়ান পদ্ধতিটি একটি ন্যূনতমকরণ অ্যালগরিদম। তাই, সর্বাধিকীকরণ সমস্যা সমাধানের জন্য প্রথমে লাভ ম্যাট্রিক্সটিকে একটি ব্যয় বা সুযোগ-ক্ষতি ম্যাট্রিক্সে রূপান্তর করতে হয়। এটি করা হয় ম্যাট্রিক্সের সর্বোচ্চ উপাদানটি থেকে ম্যাট্রিক্সের প্রতিটি উপাদানকে বিয়োগ করে। এরপর এই নতুন ম্যাট্রিক্সের উপর ন্যূনতমকরণ প্রক্রিয়া প্রয়োগ করা হয়।
Explanation: The Hungarian method is a minimization algorithm. Therefore, to solve a maximization problem, the profit matrix must first be converted into a cost or opportunity-loss matrix. This is done by subtracting every element in the matrix from the largest element in the matrix. The minimization procedure is then applied to this new matrix.
Explanation: The Hungarian method is a minimization algorithm. Therefore, to solve a maximization problem, the profit matrix must first be converted into a cost or opportunity-loss matrix. This is done by subtracting every element in the matrix from the largest element in the matrix. The minimization procedure is then applied to this new matrix.
38. একটি LPP-এর সম্ভাব্য অঞ্চলের (feasible region) প্রান্তিক বিন্দুগুলির (extreme points) সাথে কীসের এক-এক对应তা (one-to-one correspondence) রয়েছে?
The extreme points of the feasible region of an LPP correspond one-to-one with what?
The extreme points of the feasible region of an LPP correspond one-to-one with what?
সঠিক উত্তর (Correct Answer): A) মৌলিক সম্ভাব্য সমাধান (BFS) / Basic Feasible Solutions (BFS)
ব্যাখ্যা: রৈখিক প্রোগ্রামিং-এর একটি মৌলিক সম্পর্ক হলো যে, সম্ভাব্য অঞ্চলের প্রতিটি প্রান্তিক বিন্দু (vertex or corner point) একটি মৌলিক সম্ভাব্য সমাধানের (BFS) সাথে মিলে যায়, এবং প্রতিটি BFS একটি প্রান্তিক বিন্দুর সাথে মিলে যায় (ডিজেনারেসি না থাকলে)।
Explanation: A fundamental relationship in linear programming is that every extreme point (vertex or corner point) of the feasible region corresponds to a Basic Feasible Solution (BFS), and every BFS corresponds to an extreme point (in the absence of degeneracy).
Explanation: A fundamental relationship in linear programming is that every extreme point (vertex or corner point) of the feasible region corresponds to a Basic Feasible Solution (BFS), and every BFS corresponds to an extreme point (in the absence of degeneracy).
39. m সংখ্যক সমীকরণ এবং n সংখ্যক চলরাশি (n > m) সহ একটি সিস্টেমে সর্বাধিক কতগুলি মৌলিক সমাধান (basic solutions) থাকতে পারে?
In a system with m equations and n variables (n > m), what is the maximum possible number of basic solutions?
In a system with m equations and n variables (n > m), what is the maximum possible number of basic solutions?
সঠিক উত্তর (Correct Answer): C) nCm (n choose m)
ব্যাখ্যা: একটি মৌলিক সমাধান পাওয়া যায় nটি চলরাশি থেকে (n-m)টি চলরাশিকে শূন্য ধরে এবং বাকি mটি চলরাশির জন্য সমীকরণ সমাধান করে। nটি চলরাশি থেকে mটি মৌলিক চলরাশি (basic variables) বেছে নেওয়ার মোট উপায় হলো nCm। সুতরাং, সর্বাধিক nCm সংখ্যক মৌলিক সমাধান থাকতে পারে।
Explanation: A basic solution is found by setting (n-m) variables to zero out of n variables and solving the equations for the remaining m variables. The total number of ways to choose m basic variables from n variables is nCm. Therefore, there can be at most nCm basic solutions.
Explanation: A basic solution is found by setting (n-m) variables to zero out of n variables and solving the equations for the remaining m variables. The total number of ways to choose m basic variables from n variables is nCm. Therefore, there can be at most nCm basic solutions.
40. একটি পরিবহন সমস্যায়, যদি কোনো একটি রুটে পরিবহন নিষিদ্ধ (prohibited) থাকে, তাহলে সেই সেলের ব্যয় (cost) কত ধরা হয়?
In a transportation problem, if transportation along a certain route is prohibited, what cost is assigned to that cell?
In a transportation problem, if transportation along a certain route is prohibited, what cost is assigned to that cell?
সঠিক উত্তর (Correct Answer): B) একটি খুব বড় সংখ্যা (M) / A very large number (M)
ব্যাখ্যা: নিষিদ্ধ রুটের জন্য একটি অত্যন্ত বড় ব্যয় (M) নির্ধারণ করা হয়। যেহেতু পরিবহন সমস্যাটি সাধারণত মোট ব্যয় ন্যূনতম করার চেষ্টা করে, এই বড় ব্যয় নিশ্চিত করে যে অনুকূল সমাধানে ওই রুটে কোনো পণ্য বরাদ্দ করা হবে না।
Explanation: A very large cost (M) is assigned to the prohibited route. Since the transportation problem typically aims to minimize total cost, this large cost ensures that no goods will be allocated to that route in the optimal solution.
Explanation: A very large cost (M) is assigned to the prohibited route. Since the transportation problem typically aims to minimize total cost, this large cost ensures that no goods will be allocated to that route in the optimal solution.
41. গ্রাফিক্যাল পদ্ধতিতে, যদি সম্ভাব্য অঞ্চলটি দুটি বিচ্ছিন্ন (disconnected) অঞ্চলে বিভক্ত হয়, তবে LPP-টির…
In the graphical method, if the feasible region is split into two disconnected regions, the LPP…
In the graphical method, if the feasible region is split into two disconnected regions, the LPP…
সঠিক উত্তর (Correct Answer): C) সংজ্ঞায়িত নয় / is not well-defined
ব্যাখ্যা: LPP-এর সম্ভাব্য অঞ্চল সর্বদা একটি উত্তল সেট (convex set) হতে হবে। একটি উত্তল সেট কখনো বিচ্ছিন্ন হতে পারে না। যদি সীমাবদ্ধতাগুলি এমন হয় যে বিচ্ছিন্ন অঞ্চল তৈরি হয়, তবে এটি একটি বৈধ LPP নয়।
Explanation: The feasible region of an LPP must always be a convex set. A convex set can never be disconnected. If the constraints result in a disconnected region, it’s not a valid LPP.
Explanation: The feasible region of an LPP must always be a convex set. A convex set can never be disconnected. If the constraints result in a disconnected region, it’s not a valid LPP.
42. একটি LPP-এর উদ্দেশ্যমূলক অপেক্ষক যদি সম্ভাব্য অঞ্চলের দুটি প্রান্তিক বিন্দুতে একই সর্বোচ্চ মান দেয়, তাহলে…
If the objective function of an LPP gives the same maximum value at two distinct extreme points of the feasible region, then…
If the objective function of an LPP gives the same maximum value at two distinct extreme points of the feasible region, then…
সঠিক উত্তর (Correct Answer): B) অসীম সংখ্যক অনুকূল সমাধান আছে / there are infinite optimal solutions
ব্যাখ্যা: যদি দুটি প্রান্তিক বিন্দু A এবং B-তে অনুকূল মান পাওয়া যায়, তবে তাদের সংযোগকারী রেখাংশের (line segment) প্রতিটি বিন্দুতেও একই অনুকূল মান পাওয়া যাবে। যেহেতু একটি রেখাংশে অসীম সংখ্যক বিন্দু থাকে, তাই অসীম সংখ্যক অনুকূল সমাধান বিদ্যমান।
Explanation: If the optimal value is found at two extreme points A and B, then every point on the line segment joining them will also yield the same optimal value. Since a line segment contains infinite points, there are infinite optimal solutions.
Explanation: If the optimal value is found at two extreme points A and B, then every point on the line segment joining them will also yield the same optimal value. Since a line segment contains infinite points, there are infinite optimal solutions.
43. Two-Phase সিমপ্লেক্স পদ্ধতিটি কখন ব্যবহৃত হয়?
When is the Two-Phase simplex method used?
When is the Two-Phase simplex method used?
সঠিক উত্তর (Correct Answer): B) যখন সমস্যায় কৃত্রিম চলরাশি (artificial variables) প্রয়োজন হয় / When artificial variables are needed in the problem
ব্যাখ্যা: Two-Phase পদ্ধতিটি Big-M পদ্ধতির একটি বিকল্প। এটি ‘≥’ বা ‘=’ সীমাবদ্ধতাযুক্ত সমস্যা সমাধানের জন্য ব্যবহৃত হয়, যেখানে একটি প্রাথমিক সম্ভাব্য সমাধান খুঁজে বের করতে কৃত্রিম চলরাশি প্রয়োজন। Phase-I তে কৃত্রিম চলরাশিগুলির যোগফলকে ন্যূনতম করা হয়, এবং Phase-II তে মূল উদ্দেশ্যমূলক অপেক্ষককে অপ্টিমাইজ করা হয়।
Explanation: The Two-Phase method is an alternative to the Big-M method. It is used to solve problems with ‘≥’ or ‘=’ constraints, which require artificial variables to find an initial feasible solution. In Phase-I, the sum of artificial variables is minimized, and in Phase-II, the original objective function is optimized.
Explanation: The Two-Phase method is an alternative to the Big-M method. It is used to solve problems with ‘≥’ or ‘=’ constraints, which require artificial variables to find an initial feasible solution. In Phase-I, the sum of artificial variables is minimized, and in Phase-II, the original objective function is optimized.
44. যদি একটি ডুয়াল সমস্যার কোনো সম্ভাব্য সমাধান না থাকে এবং প্রাইমাল সমস্যার একটি সম্ভাব্য সমাধান থাকে, তাহলে প্রাইমাল সমস্যাটির সমাধান কী হবে?
If a dual problem has no feasible solution and the primal problem has a feasible solution, then what is the solution to the primal problem?
If a dual problem has no feasible solution and the primal problem has a feasible solution, then what is the solution to the primal problem?
সঠিক উত্তর (Correct Answer): B) অসীম (Unbounded)
ব্যাখ্যা: ডুয়ালিটি তত্ত্বের একটি উপপাদ্য অনুযায়ী, যদি ডুয়ালের কোনো সম্ভাব্য সমাধান না থাকে, এবং প্রাইমালের একটি সম্ভাব্য সমাধান থাকে, তবে প্রাইমাল সমস্যাটির সমাধান অবশ্যই অসীম (unbounded) হবে।
Explanation: According to a theorem of duality, if the dual has no feasible solution and the primal has a feasible solution, then the primal problem must have an unbounded solution.
Explanation: According to a theorem of duality, if the dual has no feasible solution and the primal has a feasible solution, then the primal problem must have an unbounded solution.
45. একটি অ্যাসাইনমেন্ট সমস্যায়, যদি কার্য (jobs) এবং কর্মীর (persons) সংখ্যা সমান না হয়, তবে সমস্যাটিকে কী বলা হয়?
In an assignment problem, if the number of jobs is not equal to the number of persons, the problem is called:
In an assignment problem, if the number of jobs is not equal to the number of persons, the problem is called:
সঠিক উত্তর (Correct Answer): C) ভারসাম্যহীন / Unbalanced
ব্যাখ্যা: একটি স্ট্যান্ডার্ড অ্যাসাইনমেন্ট সমস্যার জন্য কার্য এবং কর্মীর সংখ্যা সমান হতে হয় (একটি বর্গাকার ম্যাট্রিক্স)। যদি তা না হয়, তবে সমস্যাটি ভারসাম্যহীন। এটিকে ভারসাম্যপূর্ণ করার জন্য ডামি সারি বা কলাম যোগ করা হয়।
Explanation: A standard assignment problem requires an equal number of jobs and persons (a square matrix). If this is not the case, the problem is unbalanced. It is balanced by adding dummy rows or columns.
Explanation: A standard assignment problem requires an equal number of jobs and persons (a square matrix). If this is not the case, the problem is unbalanced. It is balanced by adding dummy rows or columns.
46. LPP-তে ‘রৈখিক’ (Linear) শব্দটি কী বোঝায়?
What does the term ‘Linear’ in LPP signify?
What does the term ‘Linear’ in LPP signify?
সঠিক উত্তর (Correct Answer): A) উদ্দেশ্যমূলক অপেক্ষক এবং সীমাবদ্ধতাগুলি রৈখিক / The objective function and constraints are linear
ব্যাখ্যা: ‘রৈখিক’ বলতে বোঝায় যে সমস্ত গাণিতিক সম্পর্ক (উদ্দেশ্যমূলক অপেক্ষক এবং সীমাবদ্ধতা) রৈখিক সমীকরণ বা অসমীকরণ। এর মানে হলো চলরাশিগুলির ঘাত ১ হবে এবং চলরাশিগুলির মধ্যে কোনো গুণফল থাকবে না।
Explanation: ‘Linear’ means all mathematical relationships (objective function and constraints) are linear equations or inequalities. This implies that the variables have a power of 1, and there are no products of variables.
Explanation: ‘Linear’ means all mathematical relationships (objective function and constraints) are linear equations or inequalities. This implies that the variables have a power of 1, and there are no products of variables.
47. পরিবহন সমস্যার লুপ (loop) কী?
What is a loop in a transportation problem?
What is a loop in a transportation problem?
সঠিক উত্তর (Correct Answer): C) একটি অনুভূমিক এবং উল্লম্ব রেখার ক্রম যা একটি খালি সেল থেকে শুরু হয়ে সেখানেই শেষ হয় / A sequence of horizontal and vertical lines starting from an empty cell and ending there
ব্যাখ্যা: MODI পদ্ধতিতে অনুকূলতা পরীক্ষার পর সমাধান উন্নত করার জন্য লুপ ব্যবহার করা হয়। এটি একটি খালি সেল থেকে শুরু হয় এবং শুধুমাত্র বরাদ্দকৃত সেলের মধ্য দিয়ে অনুভূমিক ও উল্লম্বভাবে চলে আবার সেই খালি সেলে ফিরে আসে।
Explanation: In the MODI method, a loop is used to improve the solution after the optimality test. It starts from an empty cell, moves horizontally and vertically through only allocated cells, and returns to the starting empty cell.
Explanation: In the MODI method, a loop is used to improve the solution after the optimality test. It starts from an empty cell, moves horizontally and vertically through only allocated cells, and returns to the starting empty cell.
48. যদি প্রাইমালের উদ্দেশ্যমূলক অপেক্ষক অসীম (unbounded) হয়, তাহলে এর ডুয়াল সম্পর্কে কী বলা যায়?
If the objective function of the primal is unbounded, what can be said about its dual?
If the objective function of the primal is unbounded, what can be said about its dual?
সঠিক উত্তর (Correct Answer): B) ডুয়ালের কোনো সম্ভাব্য সমাধান থাকবে না / The dual will have no feasible solution
ব্যাখ্যা: এটি ডুয়ালিটি তত্ত্বের একটি গুরুত্বপূর্ণ ফলাফল। যদি একটি LPP (প্রাইমাল) অসীম হয়, তবে তার ডুয়ালের কোনো সম্ভাব্য সমাধান থাকতে পারে না (অর্থাৎ, ডুয়ালটি অসম্ভাব্য)।
Explanation: This is a key result from duality theory. If an LPP (the primal) is unbounded, then its dual cannot have any feasible solution (i.e., the dual is infeasible).
Explanation: This is a key result from duality theory. If an LPP (the primal) is unbounded, then its dual cannot have any feasible solution (i.e., the dual is infeasible).
49. একটি LPP-তে ডিজেনারেসি (Degeneracy) কখন ঘটে?
When does Degeneracy occur in an LPP?
When does Degeneracy occur in an LPP?
সঠিক উত্তর (Correct Answer): A) যখন একটি মৌলিক চলরাশির মান শূন্য হয় / When a basic variable takes a value of zero
ব্যাখ্যা: একটি মৌলিক সম্ভাব্য সমাধানে (BFS) যদি এক বা একাধিক মৌলিক চলরাশির মান শূন্য হয়, তবে সেই সমাধানটিকে ডিজেনারেট বলা হয়। এটি সিমপ্লেক্স পদ্ধতিতে সাইক্লিং (cycling) নামক সমস্যার কারণ হতে পারে।
Explanation: If one or more basic variables in a Basic Feasible Solution (BFS) have a value of zero, the solution is said to be degenerate. This can potentially cause a problem called cycling in the simplex method.
Explanation: If one or more basic variables in a Basic Feasible Solution (BFS) have a value of zero, the solution is said to be degenerate. This can potentially cause a problem called cycling in the simplex method.
50. হাঙ্গেরিয়ান পদ্ধতিতে, সর্বোত্তম অ্যাসাইনমেন্ট (optimal assignment) নির্দেশিত হয় যখন…
In the Hungarian method, the optimal assignment is indicated when…
In the Hungarian method, the optimal assignment is indicated when…
সঠিক উত্তর (Correct Answer): C) অঙ্কিত রেখার সংখ্যা ম্যাট্রিক্সের অর্ডারের সমান হয় / The number of lines drawn equals the order of the matrix
ব্যাখ্যা: হাঙ্গেরিয়ান পদ্ধতির একটি মূল ধাপ হলো সমস্ত শূন্যকে ন্যূনতম সংখ্যক অনুভূমিক এবং উল্লম্ব রেখা দিয়ে ঢাকা। যদি এই রেখার সংখ্যা ম্যাট্রিক্সের অর্ডারের (n x n ম্যাট্রিক্সের জন্য n) সমান হয়, তবে অনুকূল অ্যাসাইনমেন্ট করা সম্ভব। যদি কম হয়, তবে ম্যাট্রিক্সটি আরও পরিবর্তন করতে হবে।
Explanation: A key step in the Hungarian method is to cover all zeros with a minimum number of horizontal and vertical lines. If the number of these lines is equal to the order of the matrix (n for an n x n matrix), then an optimal assignment can be made. If it’s less, the matrix needs further modification.
Explanation: A key step in the Hungarian method is to cover all zeros with a minimum number of horizontal and vertical lines. If the number of these lines is equal to the order of the matrix (n for an n x n matrix), then an optimal assignment can be made. If it’s less, the matrix needs further modification.
51. উদ্দেশ্যমূলক অপেক্ষক Z = 3x + 9y, এবং সীমাবদ্ধতা x + 3y ≤ 60, x + y ≥ 10, x ≤ y, x ≥ 0, y ≥ 0। এই সমস্যার সমাধান কী?
For the objective function Z = 3x + 9y, subject to constraints x + 3y ≤ 60, x + y ≥ 10, x ≤ y, x ≥ 0, y ≥ 0. What is the solution to this problem?
For the objective function Z = 3x + 9y, subject to constraints x + 3y ≤ 60, x + y ≥ 10, x ≤ y, x ≥ 0, y ≥ 0. What is the solution to this problem?
সঠিক উত্তর (Correct Answer): B) একাধিক অনুকূল সমাধান / Multiple optimal solutions
ব্যাখ্যা: লক্ষ্য করুন যে উদ্দেশ্যমূলক অপেক্ষক Z = 3(x + 3y)। একটি সীমাবদ্ধতা হলো x + 3y ≤ 60। উদ্দেশ্যমূলক অপেক্ষকের ঢাল (-3/9 = -1/3) এবং x + 3y = 60 সীমাবদ্ধতা রেখার ঢাল (-1/3) একই। এর মানে হলো উদ্দেশ্যমূলক অপেক্ষক রেখাটি সম্ভাব্য অঞ্চলের একটি প্রান্তের (edge) উপর সমাপতিত হবে। ফলে, সেই প্রান্তের সমস্ত বিন্দু অনুকূল সমাধান দেবে।
Explanation: Notice that the objective function is Z = 3(x + 3y). One of the constraints is x + 3y ≤ 60. The slope of the objective function (-3/9 = -1/3) is the same as the slope of the constraint line x + 3y = 60 (-1/3). This means the objective function line will coincide with an edge of the feasible region, resulting in all points on that edge being optimal solutions.
Explanation: Notice that the objective function is Z = 3(x + 3y). One of the constraints is x + 3y ≤ 60. The slope of the objective function (-3/9 = -1/3) is the same as the slope of the constraint line x + 3y = 60 (-1/3). This means the objective function line will coincide with an edge of the feasible region, resulting in all points on that edge being optimal solutions.
52. অ্যাসাইনমেন্ট সমস্যা (Assignment Problem) কোন ধরনের LPP-এর একটি বিশেষ রূপ?
The Assignment Problem is a special case of which type of LPP?
The Assignment Problem is a special case of which type of LPP?
সঠিক উত্তর (Correct Answer): A) পরিবহন সমস্যা / Transportation Problem
ব্যাখ্যা: অ্যাসাইনমেন্ট সমস্যাকে এমন একটি পরিবহন সমস্যা হিসাবে দেখা যেতে পারে যেখানে উৎস এবং গন্তব্যের সংখ্যা সমান, এবং প্রতিটি উৎস থেকে যোগান এবং প্রতিটি গন্তব্যে চাহিদা ঠিক 1। এই কারণে, এটি পরিবহন সমস্যার একটি বিশেষ এবং সহজ রূপ।
Explanation: The assignment problem can be viewed as a transportation problem where the number of sources equals the number of destinations, and the supply from each source and the demand at each destination is exactly 1. For this reason, it is a special and simpler case of the transportation problem.
Explanation: The assignment problem can be viewed as a transportation problem where the number of sources equals the number of destinations, and the supply from each source and the demand at each destination is exactly 1. For this reason, it is a special and simpler case of the transportation problem.