যোগাশ্রয়ী প্রোগ্রাম (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. 5x1+10x2≤50, x1+x2≥1, x2≤4, x1≥0, x2≥0 শর্তসমূহ সাপেক্ষে রাশিটির 2x1+7x2 লঘিষ্ঠমান- [ 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. 5x1+10x2≤50,          x1+x2≥1,                      x2≤4,                            5x1+10x2=50
x1/10 + x2/5 ≤ 1       ≈ (1,0), (0,1)                5x1+10x2=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]

 

 

 

 

Twitter icon
Facebook icon
Google icon
StumbleUpon icon
Del.icio.us icon
Digg icon
LinkedIn icon
MySpace icon
Newsvine icon
Pinterest icon
Reddit icon
Technorati icon
Yahoo! icon
e-mail icon