যোগাশ্রয়ী প্রোগ্রাম (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$ একটি সরলরেখার সমীকরণ যা অক্ষদ্বয়কে ছেদ করে। অর্থাৎ,
$\mathrm{ax}+\mathrm{by}=\mathrm{c} \Rightarrow \frac{x}{c / a}+\frac{y}{c / a}=1$ সরলরেখা $x$ অক্ষকে $\left(\frac{\mathrm{c}}{\mathrm{a}}, 0\right)$ এবং $y$ অক্ষকে $\left(0, \frac{c}{a}\right)$ বিন্দুতে ছেদ করে।

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

সমীকরণে $y = 0$ বসালে $x$ অক্ষে কর্তিত অংশ (x-intercept) পাওয়া যাবে।
$a x+b(0)=c \Rightarrow x=\frac{c}{a}$

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

$a(0)+b y=c \Rightarrow y=\frac{c}{b}$

প্রাপ্ত $\left(\frac{c}{a}, 0\right)$ এবং $\left(0, \frac{c}{\mathrm{~b}}\right)$ বিন্দুদ্বয়কে যোগ করলে $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$ রেখার যে দিকে মূলবিন্দু আছে শুধুমাত্র সে দিকের সকল বিন্দুর সেট।

কিছু সমস্যা ও সমাধান:

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

$x+2 y \leq 10 \Rightarrow x / 10+y / 5 \leq 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 \leq 5, x+2 y \leq 8,4 x+3 y>12, x \geq 0, x \geq 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 \geq 0, y \geq 0, x+y \geq 6,2 x+y \geq 8$ শর্তসমূহ সাপেক্ষে $z = 2x+3y$ রাশিটির সর্বনিম্ন মান- [ DU : 06-07 ]

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

# 2. $5 \mathrm{x}_{1}+10 \mathrm{x}_{2} \leq 50, \mathrm{x}_{1}+\mathrm{x}_{2} \geq 1, \mathrm{x}_{2} \leq 4, \mathrm{x}_{1} \geq 0, \mathrm{x}_{2} \geq 0$ শর্তসমূহ সাপেক্ষে রাশিটির $2 \mathrm{x}_{1}+7 \mathrm{x}_{2}$ লঘিষ্ঠমান- [ DU : 08-09 ]

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

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

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

 

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

1. $x / 6+y / 6 \geq 1, \quad x / 4+y / 8 \geq 1 \quad 1 x+y=6$

    $2 x+y=8$
    $\approx(6,0),(0,6) \quad \approx(4,0),(0,8) \quad \approx(2,4)$
[see example 2 for details]

 

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

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

∴ $\operatorname{At}(6,0), \mathrm{z}=2(6)+3(0)=12$
   $\mathrm{At}(8,0), \mathrm{Z}=2(0)+3(8)=24$
   $\mathrm{At}(2,4), \mathrm{Z}=2(2)+3(4)=16$

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

 

2. $5 \mathbf{x}_{1}+10 \times x_{2} \leq 50, \quad x_{1}+x_{2} \geq 1, \quad x_{2} \leq 4, \quad 5 x_{1}+10 x_{2}=50$
    $\Rightarrow \mathbf{x}_{1} / \mathbf{1 0}+\mathbf{x}_{2} / 5 \leq 1 \quad \approx(1,0),(0,1) \quad 5 x_{1}+10 x_{2}=50 \quad x_{1}+x_{2}=1$
    $\approx(10,0),(0,5) \quad \approx(2,4) \quad \approx(-8,9)$
    $\approx(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), \quad z=2(0)+7(4)=28$
   At $(2,4), \quad z=2(2)+7(4)=32$

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

 

3. $\begin{array}{lll}x+y \leq 7 & 2 x+5 y \leq 20 & x+y=7\end{array}$
    $\Rightarrow \frac{x}{7}+\frac{y}{7} \leq 1 \quad \Rightarrow \frac{x}{10}+\frac{y}{4} \leq 1 \quad 2 x+5 y=20$
    $\approx(7,0),(0,7) \quad \approx(10,0),(0,4) \quad \approx(5,2)$
[see example 1 for details]

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

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

∴ At $(7,0), \mathrm{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]