Chapter 2.5 — A Taste of the Simplex Method (সিমপ্লেক্স পদ্ধতির স্বাদ)¶

🎯 এই chapter-এ যা শিখবে¶

Linear Programming(লিনিয়ার প্রোগ্রামিং) — যখন equation-এর জায়গা নেয় Inequality(অসমতা), আর "সমাধান খোঁজা"-র জায়গা নেয় "সেরা সমাধান খোঁজা"
Objective Function(লক্ষ্য ফাংশন), Constraint(শর্ত) আর Feasible Region(সম্ভাব্য অঞ্চল) — একটা বাস্তব সমস্যাকে LP-র ভাষায় লেখা
এই chapter-এর মুকুট-উপপাদ্য: linear objective-এর সেরা মান সবসময় feasible region-এর কোনো Vertex(কোণা/শীর্ষবিন্দু)-তে বসে থাকে — এবং কেন
Simplex Method(সিমপ্লেক্স পদ্ধতি)-র মূল চাল: কোণা থেকে কোণায় হাঁটা, প্রতি পায়ে উন্নতি — আর তার ভেতরে লুকিয়ে থাকা আমাদের চেনা pivot ও row operation
scipy.optimize.linprog দিয়ে কোডে LP solve করা — minimize/maximize দুটোই

🖼️ এক ছবিতে মূল idea¶

Cost line slides to a vertex

মিতুর হোস্টেল-মেনু সমস্যা (গল্প নিচে): চারটা শর্ত কেটেকুটে রেখেছে সবুজ feasible region। নীল লাইনগুলো "সম-খরচ" লাইন — একই লাইনের সব মেনুর খরচ সমান। লাইনটাকে সস্তার দিকে ঠেলতে ঠেলতে অঞ্চলের সাথে শেষ ছোঁয়াটা ঘটে একটা কোণায়: vertex \(A(8,6)\), খরচ ১০৮ টাকা। "সেরাটা সবসময় কোণায়" — পুরো chapter এই এক বাক্যের গল্প।

১. কি? (What)¶

মিতুর হোস্টেল-মেনু¶

মিতু তার হোস্টেলের মেসের দায়িত্ব পেয়েছে। প্রতি ছাত্রের জন্য সপ্তাহের নাস্তার বরাদ্দ ঠিক করতে হবে: \(x\) প্লেট রুটি (প্লেট ৬ টাকা) আর \(y\)টা কলা (প্রতিটা ১০ টাকা)। হোস্টেলের নিয়মকানুন:

রুটি ছাড়া নাস্তা চলে না — সপ্তাহে অন্তত ৪ প্লেট: \(x \ge 4\)
পুষ্টির জন্য অন্তত ৬টা কলা: \(y \ge 6\)
পেট ভরাতে মোট আইটেম অন্তত ১৪টা: \(x + y \ge 14\)
রান্নাঘর আর ভাঁড়ারের সামর্থ্যে সর্বোচ্চ ২২টা: \(x + y \le 22\)

মিতুর লক্ষ্য একটাই: এই সব নিয়ম মেনে মাথাপিছু খরচ যত কম রাখা যায়:

\[\text{minimize} \quad c = 6x + 10y\]

লক্ষ করো — প্রশ্নটা আগের চার chapter-এর প্রশ্নের চেয়ে জাতে আলাদা। এতদিন আমাদের শর্ত ছিল সমান-চিহ্নের (\(=\)), আর প্রশ্ন ছিল "সমাধান আছে কি, থাকলে কয়টা?" এখানে শর্তগুলো অসমতা (\(\le, \ge\)), তাই নিয়ম-মানা মেনু একটা-দুটো নয় — অসংখ্য (যেমন \((5,9)\), \((10,7)\), \((8,6)\)...সবই বৈধ)। প্রশ্ন এখন: এই অসংখ্যের মধ্যে কোনটা সেরা?

সংজ্ঞা, ধীরে ধীরে¶

এই ধাঁচের সমস্যার নাম Linear Programming (LP)। উপকরণ তিনটা:

Decision Variable(সিদ্ধান্ত চলক): যে সংখ্যাগুলো তুমি বেছে নেবে — এখানে \(x, y\);
Constraint(শর্ত): decision variable-দের উপর linear অসমতা/সমতা — এখানে চারটা;
Objective Function(লক্ষ্য ফাংশন): যে linear রাশিকে সবচেয়ে ছোট (minimize) বা সবচেয়ে বড় (maximize) করতে চাও — এখানে \(c = 6x+10y\)।

আর দুটো জরুরি নাম:

শর্ত-মানা প্রতিটা বিন্দুকে বলে Feasible Solution(সম্ভাব্য সমাধান); তাদের সবার সেটটা Feasible Region;
Feasible region-এর যে বিন্দুতে objective সেরা, সে হলো Optimal Solution(সেরা সমাধান) বা সংক্ষেপে optimum।

"Linear" শব্দটা এখানেও কড়া: objective আর প্রতিটা constraint-এ variable-রা শুধু প্রথম ঘাতে (\(x^2\), \(xy\) নিষেধ — Chapter 2.1-এর সেই চেকলিস্ট)। আর "Programming" মানে কিন্তু কোডিং নয় — শব্দটা ১৯৪০-এর দশকের সামরিক ভাষা থেকে আসা, মানে "পরিকল্পনা সাজানো" (রসদ কোথায় পাঠাবে, কে কী বানাবে)। কম্পিউটার প্রোগ্রামিং-এর নামকরণ বরং এর পরে!

আগের chapter-দের সাথে সম্পর্ক¶

Chapter 2.4-এ দেখেছ: একটা linear equation \(\mathbb{R}^n\)-এ আঁকে একটা hyperplane। একটা linear inequality তাহলে কী আঁকে? Hyperplane-টা স্পেসকে দুই ভাগে কাটে — অসমতা বেছে নেয় তার এক পাশ (hyperplane নিজেসহ)। \(\mathbb{R}^2\)-তে এর নাম Half-plane(অর্ধ-সমতল)। LP-র feasible region হলো কতগুলো half-plane-এর ছেদ — আর optimum খোঁজা মানে সেই অঞ্চলের উপর একটা তির্যক "খরচ-মিটার" চালানো। চেনা যন্ত্রপাতি, নতুন খেলা।

২. দেখতে কেমন?¶

প্রতিটা শর্ত একটা ছুরির কোপ¶

Constraints carve the feasible region

চারটা শর্তের প্রতিটা একটা লাইন টেনে plane-এর এক পাশ বাতিল করে দেয়। চার কোপের পরে যা টিকে থাকে — সবুজ চতুর্ভুজ \(ABCD\) — সেটাই feasible region: মিতুর সব বৈধ মেনুর মানচিত্র।

কোণাগুলো চেনো — প্রতিটা vertex হলো দুটো constraint-লাইনের ছেদবিন্দু (Chapter 2.1-এর \(2\times2\) সিস্টেম solve করেই এদের পাওয়া!):

Vertex	কোন দুই শর্ত মিলেছে	স্থানাঙ্ক	খরচ \(6x+10y\)
\(A\)	\(y=6\) ও \(x+y=14\)	\((8,6)\)	\(108\)
\(B\)	\(y=6\) ও \(x+y=22\)	\((16,6)\)	\(156\)
\(C\)	\(x=4\) ও \(x+y=22\)	\((4,18)\)	\(204\)
\(D\)	\(x=4\) ও \(x+y=14\)	\((4,10)\)	\(124\)

বেশি variable-এ: কাটা হীরার মতো¶

Variable ৩টা হলে প্রতিটা constraint একটা প্লেন দিয়ে স্পেস কাটে — feasible region হয় একটা Polytope(পলিটোপ): চ্যাপ্টা মুখ, সোজা কিনারা, ধারালো কোণা — ঠিক কাটা হীরা বা ফুটবলের প্যানেলের মতো। \(100\) variable-এ আঁকা যায় না, কিন্তু গঠন একই: মুখ, কিনারা, কোণা। আর optimum তখনও কোণাতেই — এটাই সামনের বড় উপপাদ্য।

৩. কোথায় ইউজ হয়?¶

Linear programming সম্ভবত ইতিহাসের সবচেয়ে বেশি টাকা বাঁচানো গণিত। কয়েকটা জায়গা:

Diet Problem: মিতুর সমস্যাটাই আসলে বিখ্যাত — ১৯৪০-এর দশকে আমেরিকার সেনাবাহিনী জানতে চেয়েছিল, পুষ্টির সব শর্ত মেনে সৈনিকের খাবারের সর্বনিম্ন খরচ কত (অর্থনীতিবিদ Stigler ৭৭টা খাবার নিয়ে হাতে-কলমে চেষ্টা করেছিলেন; পরে simplex এসে নিখুঁত উত্তর দেয়)।
Airlines: কোন ক্রু কোন ফ্লাইটে, কোন প্লেন কোন রুটে, জ্বালানি কোথায় ভরবে — প্রতিটা বড় এয়ারলাইন প্রতিদিন দৈত্যাকার LP solve করে; শতকরা এক ভাগ সাশ্রয় মানেও কোটি টাকা।
কারখানা ও কৃষি: সীমিত কাঁচামাল, মেশিন-ঘণ্টা, জমি — কোন পণ্য/ফসল কতটুকু বানালে লাভ সর্বোচ্চ (§৭-এর Example 2 এই জাতের)।
Transportation: কোন গুদাম থেকে কোন দোকানে কত মাল পাঠালে পরিবহন খরচ সর্বনিম্ন — এই কাজের তত্ত্বের জন্যই Kantorovich আর Koopmans ১৯৭৫-এ অর্থনীতিতে Nobel পান। Simplex-এর জনক Dantzig (১৯৪৭) অল্পের জন্য বাদ পড়েন — কমিটির সেই সিদ্ধান্ত আজও বিতর্কিত!
ML/Data Science: least absolute deviations (\(L_1\)) regression একটা LP; optimal transport (দুটো probability distribution মেলানোর খরচ) LP; classifier-দের fairness constraint, cloud-এ resource scheduling — সবখানে LP solver ঘোরে।

মোদ্দা কথা Chapter 2.1-এর মতোই: বাস্তবের বহু "সেরা পরিকল্পনা" সমস্যা প্রায়-linear, আর linear হলে আমরা নিশ্চিতভাবে, দ্রুত সেরাটা খুঁজে দিতে জানি।

৪. Properties¶

Property 1 — Feasible region সবসময় Convex(উত্তল)¶

Convex মানে: সেটের যেকোনো দুই বিন্দু নাও, তাদের সংযোগ-রেখার প্রতিটা বিন্দুও সেটে — কোথাও "খাঁজ" বা গর্ত নেই।

মিনি-প্রমাণ: \(\mathbf{u}, \mathbf{v}\) দুজনেই একটা শর্ত \(a_1x+a_2y \le b\) মানে ধরো। সংযোগ-রেখার বিন্দু \(\mathbf{w} = \mathbf{u} + t(\mathbf{v}-\mathbf{u})\), \(0\le t\le1\)-এ শর্তের বাঁপাশের মান হয় দুই প্রান্তের মানের মিশ্রণ: \((1-t)(\text{u-র মান}) + t(\text{v-র মান}) \le (1-t)b + tb = b\) ✓। (Chapter 2.4-এর Problem 6-এ hyperplane-এর জন্য ঠিক এই হিসাবই করেছিলে — অসমতায়ও সে অটুট।) প্রতিটা half-plane convex, আর convex সেটদের ছেদও convex — অতএব feasible region convex। কোণাওয়ালা, কিন্তু খাঁজহীন।

Property 2 — মুকুট-উপপাদ্য: optimum বসে কোণায়¶

উপপাদ্য। Feasible region খালি নয় এবং সসীম (bounded) হলে, linear objective-এর minimum (এবং maximum) region-এর অন্তত একটা vertex-এ অর্জিত হয়।

Linear cost is a tilted flat sheet

কেন — এক ছবিতে: খরচ \(c=6x+10y\)-কে region-এর উপরে উচ্চতা হিসেবে আঁকলে পাই একটা ঢালু কিন্তু নিখুঁত সমতল শিট। সমতল জিনিসের মাঝখানে উপত্যকা বা টিলা থাকতে পারে না — তার সর্বনিম্ন বিন্দু গড়িয়ে নামে কিনারায়, কিনারা ধরে গড়িয়ে কোণায়: \((8,6)\), খরচ \(108\)।

এই উপপাদ্যের শক্তি অপরিসীম: অসীম প্রার্থীর নির্বাচন নেমে আসে সসীম কয়েকটা কোণার তালিকায়। মিতুর সমস্যায় অসংখ্য বৈধ মেনু ছিল — উপপাদ্য বলছে, তাকাও শুধু \(A, B, C, D\)-র দিকে। টেবিল (§২) বলে দিচ্ছে: \(A\), ১০৮ টাকা।

Property 3 — LP-রও trichotomy আছে¶

Chapter 2.1-এ সমাধান-সংখ্যা ছিল \(0/1/\infty\); LP-র optimum-ভাগ্যও ঠিক তিন রকম:

ঠিক একটা optimal vertex (সাধারণ ক্ষেত্র — মিতুর \(A\));
অসীম optimum: objective-এর লাইন region-এর কোনো কিনারার (edge) সমান্তরাল হলে, শেষ ছোঁয়াটা এক বিন্দু নয়, গোটা edge — তার প্রতিটা বিন্দু সমান-সেরা (তবু দুই প্রান্তের vertex-ও সেরা, তাই উপপাদ্য অক্ষত; Problem 4);
Optimum নেই: হয় শর্তরা পরস্পরবিরোধী — feasible region-ই খালি (Infeasible(অসম্ভাব্য)), নয়তো region কোনো দিকে খোলা আর objective সেদিকে ভালো হতেই থাকে (Unbounded(অসীমাবদ্ধ) — Problem 5)।

Property 4 — Simplex-এর চুক্তি: প্রতি পায়ে উন্নতি, তাই থামবেই¶

Simplex method কোণা থেকে প্রতিবেশী কোণায় লাফায় কেবল তখনই যখন খরচ কমে। Vertex-সংখ্যা সসীম, একই vertex-এ ফেরা অসম্ভব (খরচ তো কেবল কমেছে!) — অতএব অ্যালগরিদম নিশ্চিত থামে, এবং যেখানে থামে (কোনো প্রতিবেশীই ভালো নয়) সেটাই optimum — কেন "স্থানীয় সেরা = সার্বিক সেরা", তার উত্তর §৫-এ।

Property 5 — Slack variable: অসমতাকে সমতায় ফেরানোর কৌশল¶

Simplex ভেতরে-ভেতরে কী করে? প্রথম চালটা চমৎকার: প্রতিটা inequality-তে একটা সাহায্যকারী variable ঢুকিয়ে তাকে equation বানিয়ে ফেলে:

\[x + y \le 22 \iff x + y + s = 22,\quad s \ge 0\]

\(s\)-এর নাম Slack Variable(স্ল্যাক চলক) — "ঢিলা"টুকু মাপে: বাজেটের কতটা অব্যবহৃত। সব শর্ত equation হয়ে গেলে সমস্যাটা আবার আমাদের চেনা জগতে: একটা linear system, variable বেশি equation কম — মানে free variable, অসীম সমাধান (Chapter 2.2!)। প্রতিটা vertex তখন এক-একটা বিশেষ সমাধান, আর "এক কোণা থেকে পাশের কোণায় লাফ" মানে হলো টেবিলটার (নাম tableau) উপর এক দফা pivot আর row operation — হুবহু Gaussian elimination-এর চাল! Part II-র সব অস্ত্র এখানে শেষ দৃশ্যে একসাথে মঞ্চে।

৫. Intuition — কেন সত্য?¶

ভেতরের বিন্দুতে optimum কেন অসম্ভব?¶

ধরো কেউ দাবি করলো region-এর ভেতরের (কিনারা থেকে দূরের) একটা বিন্দু \(P\)-ই সবচেয়ে সস্তা। ভেতরের বিন্দু মানে তার চারদিকে ছোট্ট একটা চাকতি পুরোটাই feasible। এখন খরচ \(c = 6x+10y\) — \(x\) এক পা কমালে খরচ ৬ টাকা কমে, \(y\) কমালে ১০। তাহলে \(P\) থেকে \((-6,-10)\) দিকে এক চুল হাঁটো: এখনো feasible (চাকতির ভেতরেই), কিন্তু খরচ কমে গেল — দাবি ভুল! এই যুক্তি প্রতিটা ভেতরের বিন্দুতে খাটে, কারণ linear objective-এর "কমার দিক"টা সব জায়গায় একই — কোথাও সে শূন্য হয়ে থেমে যায় না (\(x^2\)-জাতীয় ফাংশনে যেত!)। তাই সেরা বিন্দু বাধ্য হয়ে সীমানায়; সীমানার (edge-এর) উপরেও একই যুক্তি এক মাত্রা নিচে চলে — ঠেলতে ঠেলতে কোণায়।

Simplex-এর হাঁটা — fig04 পড়া শেখো¶

Simplex walks from vertex to vertex

Simplex-এর হাঁটা: শুরু যেকোনো vertex-এ — ধরো \(C(4,18)\), খরচ ২০৪। প্রতিবেশীদের দেখো, খরচ-কমানো কিনারা ধরে লাফাও: \(C \to D\) (২০৪ → ১২৪), \(D \to A\) (১২৪ → ১০৮)। \(A\)-তে এসে দুই প্রতিবেশী \(D(124)\) আর \(B(156)\) — কেউ সস্তা নয়। থামো: \(A\)-ই optimum।

কিন্তু দাঁড়াও — "আমার কোনো প্রতিবেশী ভালো নয়" থেকে "গোটা region-এ কেউ ভালো নয়" আসে কীভাবে? এখানেই convexity (Property 1) টাকা ফেরত দেয়: যদি দূরের কোনো \(Q\) সস্তা হতো, তাহলে \(A\) থেকে \(Q\)-র দিকে সোজা হাঁটা যেত (রেখাটা region-এর ভেতরেই — convex!), আর linear objective সেই রেখা বরাবর একটানা কমতো — মানে \(A\)-র গা-ঘেঁষা দিকেই খরচ কমছে, অথচ \(A\)-র আশেপাশের সব দিক তো প্রতিবেশী কিনারারাই ঢেকে রাখে — কোনো-না-কোনো প্রতিবেশী সস্তা হতোই। স্ববিরোধ। তাই স্থানীয় জয় = সার্বিক জয় — convex জগতের সবচেয়ে দামি উপহার (Part V-এর optimization-এও এই বাক্যই ফিরবে)।

সব কোণা চেক করলেই তো হয় — হাঁটাহাঁটি কেন?¶

মিতুর সমস্যায় কোণা ৪টা — টেবিল বানিয়েই মিটে গেল। কিন্তু কোণার সংখ্যা variable আর constraint-এর সাথে বিস্ফোরকভাবে বাড়ে: মোটে ৫০ variable, ১০০ constraint-এর মাঝারি সমস্যাতেও সম্ভাব্য কোণা এত বেশি যে সব গুনতে মহাবিশ্বের আয়ু ফুরাবে। Simplex-এর জাদু: সে সাধারণত মুষ্টিমেয় কয়েকটা লাফেই পৌঁছে যায় — পথের বাইরের কোণাদের দিকে ফিরেও তাকায় না। (তাত্ত্বিক সবচেয়ে-খারাপ ক্ষেত্রে সে-ও ধীর হতে পারে; তাই আধুনিক solver-রা সাথে interior point method-ও রাখে — সে ভেতর দিয়ে সুড়ঙ্গ কেটে যায়। সে গল্প অনেক পরের।)

৬. Code-এ কেমনে লিখে¶

SciPy-র linprog LP solve করে এক ডাকে। তার ভাষায় সব constraint লিখতে হয় \(A_{ub}\,\mathbf{x} \le \mathbf{b}_{ub}\) আকারে — তাই \(\ge\)-শর্তদের দুই পাশ \(-1\) দিয়ে গুণ করে উল্টে নিই (\(x \ge 4 \iff -x \le -4\)):

import numpy as np
from scipy.optimize import linprog

# মিতুর সমস্যা: minimize 6x + 10y
c = [6, 10]
A_ub = [[-1,  0],    # -x      <= -4    (x >= 4)
        [ 0, -1],    #     -y  <= -6    (y >= 6)
        [-1, -1],    # -x - y  <= -14   (x + y >= 14)
        [ 1,  1]]    #  x + y  <= 22
b_ub = [-4, -6, -14, 22]

res = linprog(c, A_ub=A_ub, b_ub=b_ub)
print("optimum x, y :", res.x)
print("minimum cost :", res.fun)

Output:

optimum x, y : [8. 6.]
minimum cost : 108.0

ঠিক আমাদের হাতের হিসাব: \((8,6)\), ১০৮ টাকা ✓। এবার মুকুট-উপপাদ্যটাও কোডে যাচাই করি — সব কোণা নিজে খুঁজে বের করে (প্রতি জোড়া constraint-লাইনের ছেদ = একটা \(2\times2\) system, Chapter 2.1!):

from itertools import combinations

A = np.array(A_ub, dtype=float)
b = np.array(b_ub, dtype=float)

for i, j in combinations(range(len(b)), 2):
    try:
        p = np.linalg.solve(A[[i, j]], b[[i, j]])   # দুই লাইনের ছেদ
    except np.linalg.LinAlgError:
        continue                                    # সমান্তরাল জোড়া — ছেদ নেই
    if np.all(A @ p <= b + 1e-9):                   # সব শর্ত মানে? (feasible?)
        print(f"vertex ({p[0]:5.1f}, {p[1]:5.1f})  cost = {c @ p:.0f}")

Output:

vertex (  4.0,  10.0)  cost = 124
vertex (  4.0,  18.0)  cost = 204
vertex (  8.0,   6.0)  cost = 108
vertex ( 16.0,   6.0)  cost = 156

চারটা কোণা, সর্বনিম্ন \(108\) — linprog-এর উত্তরের সাথে হুবহু মিল। আর maximize করতে চাইলে? linprog শুধু minimize জানে — তাই objective-কে \(-1\) দিয়ে গুণ করো (সবচেয়ে বড় লাভ = সবচেয়ে ছোট "ঋণাত্মক লাভ"), শেষে উত্তরের চিহ্ন ফেরত উল্টাও:

# §৭-এর দর্জির সমস্যা: maximize 500x + 400y
res = linprog([-500, -400], A_ub=[[2, 1], [1, 2]], b_ub=[16, 14])
print(res.x, "max profit =", -res.fun)   # [6. 4.] max profit = 4600.0

৭. Worked Examples¶

Example 1 — মিতুর সমস্যা, পুরোটা হাতে¶

ধাপ ১ (কোণা খোঁজা): চার constraint-লাইন থেকে জোড়া বাছাই করে \(2\times2\) system solve — যেমন \(y=6,\ x+y=14\) থেকে \(A(8,6)\)। ছয় জোড়ার মধ্যে দুটো ছেদবিন্দু বাদ পড়ে (\(x=4\) ও \(y=6\)-এর ছেদ \((4,6)\): কিন্তু \(4+6=10 < 14\) — পেট ভরে না, infeasible! একইভাবে \((16,6)\)... না, সেটা \(B\), বৈধ; বাদ পড়ে \((4,6)\) আর \(x+y=14,\ x+y=22\) জোড়া — সমান্তরাল, ছেদই নেই)। টিকে থাকে \(A, B, C, D\)।

ধাপ ২ (খরচ তুলনা): \(c(A)=108,\ c(B)=156,\ c(C)=204,\ c(D)=124\)।

ধাপ ৩ (রায়): সর্বনিম্ন \(A(8,6)\) — সপ্তাহে ৮ প্লেট রুটি, ৬টা কলা, মাথাপিছু ১০৮ টাকা।

যাচাই: \(8\ge4\) ✓, \(6\ge6\) ✓, \(14\ge14\) ✓, \(14\le22\) ✓ — চার শর্তই মানা; আর লক্ষ করো optimum-এ দুটো শর্ত টানটান (equality হয়ে গেছে) — সেরা মেনুতে এক পয়সাও বাড়তি ঢিলা নেই, কলাও ন্যূনতম, মোট আইটেমও ন্যূনতম!

Example 2 — এবার maximize: দর্জি রফিকের লাভ¶

রফিক সপ্তাহে বানায় \(x\)টা পাঞ্জাবি (লাভ ৫০০ টাকা) আর \(y\)টা শার্ট (লাভ ৪০০ টাকা)। সীমা দুটো: কাপড় আছে ১৬ গজ (পাঞ্জাবিতে ২ গজ, শার্টে ১), সেলাইয়ের সময় ১৪ ঘণ্টা (পাঞ্জাবি ১ ঘণ্টা, শার্ট ২)। অবশ্যই \(x, y \ge 0\)। LP:

\[\text{maximize } P = 500x + 400y \quad \text{subject to} \quad 2x+y \le 16,\; x+2y \le 14,\; x,y \ge 0\]

Tailor shop profit maximization

Maximize মানে সম-লাভ লাইনটাকে এবার উল্টো দিকে — বাড়ার দিকে — ঠেলা। শেষ ছোঁয়া আবারও কোণায়: \((6,4)\), লাভ ৪৬০০ টাকা।

কোণা ও লাভ: \((0,0)\to0\); \((8,0)\to4000\) (কাপড় শেষ); \((0,7)\to2800\) (সময় শেষ); আর দুই সীমার ছেদ — solve করো \(2x+y=16,\ x+2y=14\): প্রথম থেকে \(y=16-2x\), বসিয়ে \(x+32-4x=14 \Rightarrow x=6,\ y=4\) — লাভ \(3000+1600=4600\)।

রায়: সপ্তাহে ৬টা পাঞ্জাবি + ৪টা শার্ট, লাভ ৪৬০০ টাকা। মজা দেখো: একক-লাভে পাঞ্জাবি সেরা, তবু "শুধু পাঞ্জাবি" (\(8,0\to4000\)) সেরা নয় — কারণ পাঞ্জাবি কাপড় খায় বেশি; বেঁচে-যাওয়া সময়ে শার্ট মিশিয়ে দুই সম্পদই পুরো কাজে লাগে। মিশ্রণ একক-সেরাকে হারায় — LP-র চিরন্তন শিক্ষা।

Example 3 — Simplex-এর পায়ে পায়ে (fig04-এর হিসাব)¶

মিতুর সমস্যায় simplex ছাড়ি, শুরু \(C(4,18)\) থেকে (খরচ ২০৪):

হপ ১: \(C\)-র প্রতিবেশী (কিনারা-শেয়ার-করা কোণা) দুটো: \(B(16,6)\) — খরচ ১৫৬, আর \(D(4,10)\) — খরচ ১২৪। দুটোই উন্নতি; সবচেয়ে বড় উন্নতি \(D\)-তে। যাও \(D\)-তে।
হপ ২: \(D\)-র প্রতিবেশী: \(C(204)\) — পেছনে, বাদ; \(A(8,6)\) — খরচ ১০৮ < ১২৪। যাও \(A\)-তে।
হপ ৩ (থামা): \(A\)-র প্রতিবেশী \(D(124)\) আর \(B(156)\) — কেউ ১০৮-এর নিচে নয়। থামো: \(A\) optimum।

চারটা কোণার সমস্যায় লাভটা চোখে পড়ে না; কিন্তু একই স্ক্রিপ্ট লক্ষ-কোণার সমস্যায় চললেও হপ লাগে সাধারণত কয়েক ডজন — এটাই simplex-এর বিখ্যাত দক্ষতা।

৮. Problems ও Solutions¶

Problem 1. নিচের কোনগুলো একটা LP-র বৈধ অংশ হতে পারে? কারণসহ বলো। (a) objective: maximize \(3x + 2y\) (b) objective: minimize \(x^2 + y\) (c) constraint: \(xy \le 4\) (d) constraint: \(2x - y \ge 3\) (e) constraint: \(|x| \le 5\)

Solution

(a) বৈধ ✓ — linear objective; maximize-ও চলে (দরকারে \(-1\) গুণে minimize বানানো যায়)।

(b) বৈধ নয় ✗ — \(x^2\) আছে; objective linear হতে হবে। (এমন সমস্যার নাম quadratic programming — Part V-এ least squares-এর পথে এর দেখা পাবে।)

(c) বৈধ নয় ✗ — \(xy\) দুই variable-এর গুণফল, linear নয়।

(d) বৈধ ✓ — linear inequality; \(\ge\)-কে \(-2x + y \le -3\) লিখে \(\le\)-ফর্মেও নেওয়া যায়।

(e) বৈধ ✓ — কৌশলে! \(|x| \le 5\) নিজে linear দেখতে নয়, কিন্তু সে আসলে দুটো linear constraint-এর প্যাকেট: \(x \le 5\) এবং \(-x \le 5\)। ভেঙে লিখলেই LP-তে ঢুকে যায়। (সাবধান: \(|x| \ge 5\) কিন্তু ভাঙলে "অথবা" আসে — সেটা আর convex নয়, LP-তে অচল!)

Problem 2. বাজারে কলার দাম নেমে হলো ৪ টাকা (রুটি ৬ টাকাই)। মিতুর নতুন objective \(c = 6x + 4y\); শর্ত চারটা একই। নতুন সেরা মেনু কী? এ থেকে কী শিখলে?

Solution

Feasible region একটুও বদলায়নি — শর্তরা একই, তাই কোণাও সেই \(A, B, C, D\)। শুধু খরচ-টেবিল নতুন:

Vertex	\(6x+4y\)
\(A(8,6)\)	\(48+24 = 72\)
\(B(16,6)\)	\(96+24 = 120\)
\(C(4,18)\)	\(24+72 = 96\)
\(D(4,10)\)	\(24+40 = 64\) ←

নতুন optimum \(D(4,10)\): রুটি ৪ প্লেট, কলা ১০টা, খরচ ৬৪ টাকা।

শিক্ষা: দাম (objective-এর সহগ) বদলালে সম-খরচ লাইনের ঢাল বদলায় — লাইন ঘুরে গিয়ে অন্য কোণায় শেষ ছোঁয়া দেয়। অঞ্চল ঠিক করে কোণাদের তালিকা, objective ঠিক করে কে জিতবে। (Chapter 2.4-এর সেই ভাগাভাগিরই প্রতিধ্বনি: আকৃতি ঠিক করে \(A\), জায়গা ঠিক করে \(\mathbf{b}\)।)

Problem 3. এক মিষ্টির দোকান দিনে বানায় \(x\) কেজি সন্দেশ (লাভ কেজিতে ৮০ টাকা) আর \(y\) কেজি রসগোল্লা (লাভ ১০০ টাকা)। দুধ আছে ২৪ লিটার (সন্দেশে কেজিপ্রতি ২, রসগোল্লায় ৩), কারিগরের সময় ১০ ঘণ্টা (দুটোতেই কেজিপ্রতি ১ ঘণ্টা), \(x,y\ge0\)। LP লিখে হাতে solve করো।

Solution

\[\text{maximize } P = 80x + 100y \quad \text{subject to} \quad 2x+3y \le 24,\; x+y \le 10,\; x, y \ge 0\]

কোণা: \((0,0)\); \((10,0)\) — দুধ লাগে \(20\le24\) ✓; \((0,8)\) — সময় \(8\le10\) ✓; আর \(2x+3y=24,\ x+y=10\)-এর ছেদ: দ্বিতীয় থেকে \(y = 10-x\), বসিয়ে \(2x + 30 - 3x = 24 \Rightarrow x = 6,\ y = 4\)।

লাভ: \((0,0)\to0\); \((10,0)\to800\); \((0,8)\to800\); \((6,4)\to480+400=880\) ←

রায়: দিনে ৬ কেজি সন্দেশ + ৪ কেজি রসগোল্লা, লাভ ৮৮০ টাকা। আবারও মিশ্রণই চ্যাম্পিয়ন — আর মজার ব্যাপার, দুই "খাঁটি" কৌশল \((10,0)\) ও \((0,8)\) এখানে সমান (৮০০) — কিন্তু কেউই সেরা নয়।

Problem 4. মিতুর region-এই objective বদলে করো: minimize \(c = 6x + 6y\)। Optimum কী হয়? Property 3-এর কোন কেসে পড়লে?

Solution

\(c = 6(x+y)\) — অর্থাৎ খরচ শুধু মোট আইটেম-সংখ্যার উপর। সম-খরচ লাইনগুলো (\(x+y = \text{ধ্রুবক}\)) এবার constraint-লাইন \(x+y=14\)-এর নিখুঁত সমান্তরাল! সস্তার দিকে ঠেলতে ঠেলতে শেষ ছোঁয়া কোনো এক বিন্দুতে নয় — গোটা কিনারা \(D(4,10)\) থেকে \(A(8,6)\) পর্যন্ত, সবার খরচ \(6\times14 = 84\)।

কোণা-টেবিলে দেখো: \(c(A) = 84 = c(D)\), আর \(c(B)=132,\ c(C)=132\)। দুই কোণায় টাই মানেই মাঝের পুরো edge জুড়ে অসীম optimum — Property 3-এর কেস ২। উপপাদ্য তবু বহাল: vertex-এও (\(A\) আর \(D\)-তে) optimum আছেই। মিতুর জন্য সুখবর: ৮৪ টাকা বাজেটে সে \((4,10)\) থেকে \((8,6)\) — রুচিমতো যেকোনো মিশ্রণ নিতে পারে!

Problem 5. মিতুর হোস্টেল বাজেট-সীমা তুলে দিলো (\(x+y\le22\) বাতিল)। বাকি তিন শর্তে (a) minimize \(6x+10y\)-এর কী হয়? (b) maximize \(6x+10y\)-এর? (c) Property 3-এর ভাষায় ব্যাখ্যা করো।

Solution

(a) কিছুই বদলায় না! Region এখন উপর-ডান দিকে অসীম খোলা, কিন্তু সস্তার দিক (\(x, y\) কমানো) আগের মতোই \(x\ge4, y\ge6, x+y\ge14\) দেয়ালে আটকে — optimum সেই \(A(8,6)\), ১০৮ টাকা।

(b) সর্বনাশ: যত খুশি রুটি-কলা — \(x\) বাড়াও, খরচ \(6x+10y\) সীমাহীন বাড়ে। Maximum-এর কোনো উত্তর নেই।

(c) এটা Property 3-এর কেস ৩ (unbounded): region কোনো দিকে খোলা এবং objective সেই দিকে "ভালো" হতে থাকে — তবেই বিপদ। খোলা region-ও নিরাপদ, যদি objective-এর ভালো-হওয়ার দিকটা দেয়ালের দিকে হয় (এখানে (a))। কোডে linprog তখন status = 3 (unbounded) বলে সাবধান করে দেয়।

Problem 6. দর্জি রফিকের সমস্যাটা (Example 2) linprog-এর ভাষায় নিজে লেখো: c, A_ub, b_ub কী হবে, আর কোড চালালে কী আসবে? (মনে রাখো: linprog শুধু minimize জানে, আর সে default-এ \(x, y \ge 0\) ধরেই নেয়।)

Solution

Maximize \(500x+400y\) = minimize \(-500x-400y\), তাই c = [-500, -400]। দুই সম্পদ-শর্ত এমনিতেই \(\le\) আকারে:

from scipy.optimize import linprog
res = linprog(c=[-500, -400],
              A_ub=[[2, 1],     # 2x + y <= 16 (কাপড়)
                    [1, 2]],    # x + 2y <= 14 (সময়)
              b_ub=[16, 14])
print(res.x, -res.fun)

Output: [6. 4.] 4600.0 — Example 2-এর হাতের হিসাব ✓। খেয়াল করো দুটো ফাঁদ এড়িয়েছি: (১) res.fun আসবে \(-4600\) — চিহ্ন ফেরত উল্টাতে হয়; (২) \(x,y\ge0\) আলাদা করে দিতে হয়নি — linprog-এর default bound \((0,\infty)\); কোনো variable ঋণাত্মক হতে দিতে চাইলে বরং bounds argument-এ বলতে হতো।

Problem 7. প্রমাণের স্বাদ: দেখাও, feasible region-এর কোনো ভেতরের বিন্দু (যার চারপাশে ছোট একটা চাকতি পুরোটা region-এ) কখনোই \(c = 6x+10y\)-এর কঠোর (strict) minimum হতে পারে না। তোমার যুক্তির কোন ধাপটা \(c = x^2 + y^2\)-এর জন্য ভেঙে পড়ে?

Solution

\(P=(p_1, p_2)\) ভেতরের বিন্দু হোক, চারপাশের \(\varepsilon\)-চাকতি feasible। \(P\) থেকে \((-6, -10)\) দিকে ছোট্ট এক পা নিই — ঠিক করে লিখলে, \(\mathbf{d} = \frac{(-6,-10)}{\|(-6,-10)\|}\) ধরে \(Q = P + \delta\,\mathbf{d}\), যেখানে \(0 < \delta < \varepsilon\)। তাহলে \(Q\) feasible (চাকতির ভেতরে), আর

\[c(Q) = c(P) + \delta\,\frac{(6)(-6) + (10)(-10)}{\sqrt{6^2+10^2}} = c(P) - \delta\sqrt{136} < c(P)\]

— \(P\)-র চেয়ে সস্তা feasible বিন্দু পাওয়া গেল; \(P\) minimum নয়। যেহেতু যুক্তিটা যেকোনো ভেতরের বিন্দুতে খাটে, minimum থাকতে বাধ্য সীমানায়। \(\blacksquare\)

\(x^2+y^2\)-এ কোথায় ভাঙে: সেখানে "কমার দিক" বিন্দুভেদে বদলায় — \((-2p_1, -2p_2)\) — এবং \((0,0)\)-তে সে শূন্য হয়ে যায়: ওই বিন্দুতে আর কোনো দিকে হাঁটলেই মান কমে না। তাই \(x^2+y^2\)-এর minimum দিব্যি region-এর ভেতরে বসতে পারে (origin ভেতরে থাকলে সেখানেই)। Linear objective-এর ঢাল কোথাও শূন্য হয় না — এই একটাই পার্থক্য, আর এতেই "optimum কোণায়" উপপাদ্যের জন্ম।

৯. Common ভুল¶

ভুল ১: Inequality-র ভুল পাশ shade করা। ✗ \(x + y \ge 14\) দেখে লাইনের নিচের দিক নেওয়া — region উল্টে যায়, উত্তর অর্থহীন। ✓ ঠিক অভ্যাস: একটা টেস্ট বিন্দু বসাও (origin সবচেয়ে সহজ): \(0+0 = 0 \ge 14\)? না — তাহলে origin-এর উল্টো পাশ।

ভুল ২: দুই লাইনের প্রতিটা ছেদবিন্দুকেই vertex ভাবা। ✗ Constraint-লাইনদের সব ছেদ region-এর কোণা নয় — যেমন মিতুর \(x=4,\ y=6\)-এর ছেদ \((4,6)\): \(4+6 < 14\), region-এর বাইরেই। ✓ ছেদবিন্দু পাওয়ার পর বাকি সব constraint-এ বসিয়ে feasible কি না দেখো — তবেই সে vertex (§৬-এর কোডে সেই np.all(A @ p <= b) লাইনটা)।

ভুল ৩: "Optimum সবসময় ঠিক একটাই" ভাবা। ✗ Objective কোনো edge-এর সমান্তরাল হলে সেই গোটা edge-ই সেরা (Problem 4) — "এক উত্তর" খুঁজে হয়রান হয়ো না। ✓ দুই কোণায় সমান মান পেলেই বুঝবে মাঝের সবটাই optimum; জানিয়ে দাও পুরো সেটটা।

ভুল ৪: Maximize-এর সমস্যায় linprog-এ চিহ্ন গুলানো। ✗ linprog([500, 400], ...) লিখে "লাভ minimize" করে ফেলা — উত্তর আসবে \((0,0)\)! ✓ Maximize মানে c-তে \(-1\) গুণ, আর ফলাফলে -res.fun — দুই জায়গাতেই উল্টাতে হয় (Problem 6)।

ভুল ৫: LP-র উত্তর ভগ্নাংশ এলে জোর করে rounding। ✗ "সপ্তাহে \(6.5\)টা পাঞ্জাবি" এলে কাছের পূর্ণসংখ্যায় গোল করা — গোল-করা বিন্দুটা infeasible বা সেরা-থেকে-দূরে হতে পারে। ✓ LP ভগ্নাংশ উত্তর দিতেই পারে — সেটা তার অধিকার। পূর্ণসংখ্যা লাগলেই সমস্যাটা আসলে Integer Programming — দেখতে ভাই-ভাই, কিন্তু বহুগুণ কঠিন জগৎ (কোণা-উপপাদ্য সেখানে আর বাঁচায় না!)।

১০. এক নজরে¶

ধারণা	এক লাইনে
Linear Programming	linear objective + linear constraint (অসমতা); লক্ষ্য: সেরা feasible বিন্দু
Feasible region	half-plane/half-space-দের ছেদ; সবসময় convex, কোণাওয়ালা কিন্তু খাঁজহীন
মুকুট-উপপাদ্য	bounded, nonempty region-এ optimum অন্তত একটা vertex-এ
কেন কোণায়	linear cost = ঢালু সমতল শিট — মাঝে উপত্যকা নেই; কমার দিক কোথাও শূন্য হয় না
LP-র trichotomy	এক vertex / এক edge জুড়ে অসীম / নেই (infeasible বা unbounded)
Simplex method	কোণা→প্রতিবেশী কোণা, প্রতি হপে খরচ কমে; convexity-তে local সেরা = global সেরা
ভেতরের যন্ত্র	slack variable-এ অসমতা→equation, তারপর tableau-তে pivot ও row operation
কোডে	`scipy.optimize.linprog(c, A_ub, b_ub)`; সব শর্ত \(\le\)-ফর্মে, maximize হলে \(c\)-তে \(-1\) গুণ

পরের chapter-এর সেতু: Part II এখানেই শেষ — দেখো কতদূর এলে: equation-এর সিস্টেম থেকে শুরু করে elimination, LU, সমাধান সেটের geometry, শেষে অসমতার জগতে "সেরা"-র সন্ধান। পুরো পথে matrix ছিল আমাদের খাতা — সংখ্যা গুছিয়ে রাখার টেবিল। Part III-এ সে আর খাতা নয়, নায়ক: matrix-দের নিজেদের বীজগণিত — যোগ, গুণ, transpose, আর সবচেয়ে দামি প্রশ্নটা: কোন matrix-এর "উল্টো" (\(A^{-1}\)) আছে, কীভাবে পাই, আর সে দিয়ে কী কী দরজা খোলে।

📓 Notebook Project¶

notebooks/part-02/ch05-project.ipynb — নিজের হাতে বানাও "কোণা-শিকারি LP solver": সব constraint-জোড়ার ছেদ থেকে vertex খুঁজবে, feasibility ছেঁকে cost তুলনা করবে, linprog-এর সাথে উত্তর মেলাবে, আর মিতুর feasible region + সম-খরচ লাইনের ছবি এঁকে দেখাবে।