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

সাধারণ ধারণা :

• যোগাশ্রয়ী প্রোগ্রাম

প্রাপ্ত সম্পদের ভিত্তিতে পরস্পর নির্ভরশীল কাজ বা শর্ত থেকে সবচেয়ে অনুকূল ফল অর্জনের গাণিতিক পদ্ধতি বা কৌশলকে যোগাশ্রয়ী প্রোগ্রাম বলা হয়।

• x ≥ a অসমতার লেখ অঙ্কন :

আমরা জানি, x = a , y অক্ষের সমান্তরাল রেখার সমীকরণ। x ≥ a অসমতার লেখ হবে x = a রেখার উপরস্থিত সকল বিন্দু এবং তার চেয়ে বড় সকল বিন্দুর লেখ অর্থাৎ x = a রেখা ও তার ডানপাশের সকল বিন্দুর লেখ।

তাহলে, x > a অসমতার লেখ হবে x = a রেখার শুধুমাত্র ডানপাশের সকল বিন্দুর লেখ।

• x ≤ a অসমতার লেখ অঙ্কন :

অনুরূপভাবে , x ≤ a অসমতার লেখ হবে x = a রেখার উপরস্থিত সকল বিন্দু এবং তার চেয়ে ছোট সকল বিন্দুর লেখ অর্থাৎ x = a রেখা ও তার বামপাশের সকল বিন্দুর লেখ।

তাহলে, x < a অসমতার লেখ হবে x = a রেখার শুধুমাত্র বামপাশের সকল বিন্দুর লেখ।

• y ≥ b অসমতার লেখ অঙ্কন :

আমরা জানি, y = b , x অক্ষের সমান্তরাল রেখার সমীকরণ। y ≥ b অসমতার লেখ হবে y = b রেখার উপরস্থিত সকল বিন্দু এবং তার চেয়ে বড় সকল বিন্দুর লেখ অর্থাৎ y = b রেখা ও তার উপরের সকল বিন্দুর লেখ।

তাহলে, y > b অসমতার লেখ হবে y = b রেখার শুধুমাত্র উপরের সকল বিন্দুর লেখ।

• y ≤ b অসমতার লেখ অঙ্কন :

অনুরূপভাবে , y ≤ b অসমতার লেখ হবে y = b রেখার উপরস্থিত সকল বিন্দু এবং তার চেয়ে ছোট সকল বিন্দুর লেখ অর্থাৎ y = b রেখা ও তার নিচের সকল বিন্দুর লেখ।

তাহলে, y < b অসমতার লেখ হবে y = b রেখার শুধুমাত্র নিচের সকল বিন্দুর লেখ।

• যোগাশ্রয়ী প্রোগ্রামের কোন চলকই ঋণাত্মক হবে না। অর্থাৎ x ≥ o এবং y ≥ o হবে।

• ax+by ≥ c অসমতার লেখ অঙ্কন :

আমরা জানি, ax+by = c একটি সরলরেখার সমীকরণ যেটি অক্ষদ্বয়কে ছেদ করে। অর্থাৎ,
ax+by=c ⇒ + = 1 সরলরেখা x অক্ষকে (c/a, 0) এবং y অক্ষকে (0, c/a) বিন্দুতে ছেদ করে।

অথবা, সরলরেখাটি যে বিন্দুতে x অক্ষকে ছেদ করে সে বিন্দুতে কোটি শূন্য।

সমীকরণে y = 0 বসালে x অক্ষে কর্তিত অংশ (x-intercept) পাওয়া যাবে।
ax+b(0) = c ⇒ x=c/a

এবং সরলরেখাটি যে বিন্দুতে y অক্ষকে ছেদ করে সে বিন্দুতে ভুজ শূন্য। সমীকরণে x=0 বসালে y অক্ষে কর্তিত অংশ (y-intercept) পাওয়া যাবে।

a(0)+by = c ⇒ y=c/b

প্রাপ্ত (c/a,0) এবং (0,c/b) বিন্দুদ্বয়কে যোগ করলে ax+by = c রেখার লেখ পাওয়া যাবে। ax+by ≥ c অসমতার লেখ হবে ax+by = c রেখার উপরস্থিত সকল বিন্দু এবং তার চেয়ে বড় সকল বিন্দুর সেট অর্থাৎ ax+by = c রেখা ও তার যে দিকে মূলবিন্দু আছে তার বিপরীত দিকের সকল বিন্দুর সেট।

তাহলে, ax+by > c অসমতার লেখ হবে ax+by = c রেখার যে দিকে মূলবিন্দু আছে শুধুমাত্র তার বিপরীত দিকের সকল বিন্দুর সেট।

• ax+by ≤ c অসমতার লেখ অঙ্কন :

অনুরূপভাবে , ax+by ≤ c অসমতার লেখ হবে ax+by = c রেখার উপরস্থিত সকল বিন্দু এবং তার চেয়ে ছোট সকল বিন্দুর সেট অর্থাৎ ax+by = c রেখা ও তার যে দিকে মূলবিন্দু আছে সে দিকের সকল বিন্দুর সেট।

তাহলে, ax+by < c অসমতার লেখ হবে ax+by = c রেখার যে দিকে মূলবিন্দু আছে শুধুমাত্র সে দিকের সকল বিন্দুর সেট।

Exemplary Problems With Solution :

1. x+2y≤10, x+y≤6, x≤4, x≥0, y≥0 শর্তসমূহ সাপেক্ষে z=2x+3y রাশিটির সর্বোচ্চকরণ কর।

 

 

 

x+2y≤10 ⇒ x/10 + y/5 ≤ 1 অসমতার লেখ :

x+y≤6 অসমতার লেখ :

x≤4 অসমতার লেখ :

∴ সম্পূর্ণ প্রোগ্রামের লেখ :

এখানে, A, B, C ও D প্রান্তিক বিন্দুসমূহ অর্থাৎ সম্ভাব্য সে সকল বিন্দু যাদের জন্য প্রদত্ত রাশির সর্বোচ্চ মান পাওয়া যেতে পারে।

এখানে,
A ≡ (0,5)

B ≡ (2,4) [ x+2y=10 ও x+y=6 রেখার ছেদবিন্দু। সমীকরণদ্বয় সমাধান করলে যার
মান পাওয়া যায় । Use calculator to solve equations to save time. ]

C ≡ (4,2) [ x+y=6 ও x=4 রেখার ছেদবিন্দু ]

D ≡ (4,0)

A (0,5) বিন্দুতে z = 2(0)+3(5) = 15
B (2,4) বিন্দুতে z = 2(2)+3(4) = 16
C (4,2) বিন্দুতে z = 2(4)+3(2) = 14
D (4,0) বিন্দুতে z = 2(4)+3(0) = 8

∴ Z এর সর্বোচ্চ মান 16 ।
[Answer]

2. x+y≤5, x+2y≤8, 4x+3y>12, x≥0, x≥0 শর্তসমূহ সাপেক্ষে রাশিটির সর্বনিম্নকরণ কর।

∴ সম্পূর্ণ প্রোগ্রামের লেখ :

এখানে, A,B,C ও D প্রান্তিক বিন্দুসমূহ অর্থাৎ সম্ভাব্য সে সকল বিন্দু যাদের জন্য প্রদত্ত রাশির সর্বনিম্ন মান পাওয়া যেতে পারে।

কিন্তু A এবং D 4x+3y > 12 অসমতার লেখের বিন্দু নয়। কেননা, 4x+3y = 0 রেখার যে পাশে মূলবিন্দু আছে তার বিপরীত পাশের সকল বিন্দুই শুধুমাত্র 4x+3y > 12 অসমতার লেখের বিন্দু। ∴ A এবং D বিন্দু শর্ত বহির্ভূত।

এখানে,
B ≡ (2,3) [ x+y = 5 ও x+2y = 8 রেখার ছেদবিন্দু। সমীকরণদ্বয় সমাধান করলে যার মান
পাওয়া যায় । Use calculator to solve equations to save time. ]

C ≡ (5.0)

∴ B (2,3) বিন্দুতে , z = 2(2) – 3 =1
∴ C (5,0) বিন্দুতে , z = 2(5) – 0 =10

∴ Z এর সর্বনিম্ন মান 1 .
[Answer ]

ঢাবির বিগত বছরের প্রশ্ন ও সমাধান :

ঢাবির বিগত বছরের প্রশ্ন :

# 1. x ≥ 0, y ≥ 0, x+y ≥ 6, 2x+y ≥ 8 শর্তসমূহ সাপেক্ষে z = 2x+3y রাশিটির সর্বনিম্ন মান- [ DU : 06-07 ]

a.16
b.10
c.12
d.14

# 2. 5×1+10×2≤50, x1+x2≥1, x2≤4, x1≥0, x2≥0 শর্তসমূহ সাপেক্ষে রাশিটির 2×1+7×2 লঘিষ্ঠমান- [ DU : 08-09 ]

a.2
b.7
c.20
d.28

# 3. নিম্নের লিনিয়ার প্রোগ্রামিং সমস্যার সমাধান কর :
গরিষ্ঠকরণ কর, z = 3x+4y
শর্ত হচ্ছে, x+y ≤ 7, 2x+5y ≤ 20, x ≥ 0, y ≥ 0

a.(5,2)
b.(7,0)
c.(10,0)
d.(0,7)

ঢাবির বিগত বছরের প্রশ্নের সমাধান :

1. x/6 + y/6 ≥ 1, x/4 + y/8 ≥ 1 1x+y = 6
2x+y = 8
≈ (6,0), (0,6) ≈ (4,0), (0,8) ≈ (2,4)
[see example 2 for details]

প্রান্তিক বিন্দু হিসেবে (0,6) কে বাদ দেয়া যেতে পারে ∵ দ্বিতীয় শর্তমতে, y≥8

প্রান্তিক বিন্দু হিসেবে (4,0) কে বাদ দেয়া যেতে পারে ∵ প্রথম শর্তমতে, x≥6

∴ At (6,0), z = 2(6)+3(0) = 12
At (8,0), z = 2(0)+3(8) = 24
At (2,4), z = 2(2)+3(4) = 16

∴ z এর সর্বনিম্ন মান 12.
[ Answer : C ]

2. 5×1+10×2≤50, x1+x2≥1, x2≤4, 5×1+10×2=50
⇒ x1/10 + x2/5 ≤ 1 ≈ (1,0), (0,1) 5×1+10×2=50 x1+x2=1
≈ (10,0), (0,5) ≈ (2,4) ≈ (-8,9)
≈ (0,4)

প্রান্তিক বিন্দু হিসেবে (0,5) ও (-8,9) কে বাদ দেয়া যেতে পারে ∵ দ্বিতীয় শর্তমতে x1≥1

∴ At (10,0), z = 2(10)+7(0) = 20
At (1,0), z = 2(1)+7(0) = 2
At (0,1), z = 2(0)+7(1) = 7
At (0,4), z = 2(0)+7(4) = 28
At (2,4), z = 2(2)+7(4) = 32

∴ z এর লঘিষ্ঠমান 2.
[Answer : A]

3. x+y≤7 2x+5y≤20 x+y=7
⇒ x/7+y/7 ≤ 1 ⇒ x/10+y/4 ≤ 1 2x+5y=20
≈ (7,0), (0,7) ≈ (10,0), (0,4) ≈ (5,2)
[see example 1 for details]

প্রান্তিক বিন্দু হিসেবে (10,9) কে বাদ দেয়া যেতে পারে ∵ প্রথম শর্তমতে, x≤7

প্রান্তিক বিন্দু হিসেবে (0,7) কে বাদ দেয়া যেতে পারে ∵ দ্বিতীয় শর্তমতে, y≤4

∴ At (7,0), z = 3(7)+4(0) = 21
At (0,4), z = 3(0)+4(4) = 16
At (5,2), z = 3(5)+4(2) = 23

∴ (5,2) এ z এর সর্বোচ্চ মান পাওয়া যায় ।
[Answer : A]