Questions: Linear Programming

Q1 Define a linear programming problem and its parts

Answer (English): A linear programming problem is an optimisation problem in which a linear function of the variables has to be made as large or as small as possible, while the variables obey linear inequalities and stay non-negative. The linear function is the objective function; the variables are decision variables; the inequalities are constraints; and the conditions that the variables are at least zero are the non-negative restrictions. Every relation in the problem is linear, and the chapter solves problems with exactly two variables by drawing their feasible region.

Hinglish: Linear programming problem mein ek linear objective function ka maximum ya minimum nikalna hota hai, linear constraints aur non-negativity ke saath. Objective function wahi quantity hoti hai jise optimise karna hai; variables decision variables hote hain; inequalities constraints hoti hain. Sab relations linear hone chahiye, aur is chapter mein do variables wale problems graphical method se solve hote hain.

Q2 How do you formulate an LPP from a word problem?

Answer (English): Start by defining the decision variables in words: let x be the number of the first item and y the number of the second. Write the quantity to be maximised or minimised as a linear expression in x and y; this is the objective function. Translate each restriction in the story into a linear inequality, choosing the direction from the words at least and at most. Then add x at least zero and y at least zero. Check the formulation by testing one or two obvious choices, and simplify constraints by common factors where it helps.

Hinglish: Pehle decision variables define karo: x pehla item, y doosra. Jis quantity ko maximise ya minimise karna hai, use x aur y ka linear expression banao; yeh objective function hai. Har restriction ko inequality mein badlo, "at least" se ≥ aur "at most" se ≤; phir non-negativity add karo. Ek-do obvious choices se formulation check karo.

Q3 What are a feasible region, a feasible solution and an optimal solution?

Answer (English): The set of points that satisfy all the constraints together, including the non-negative restrictions, is the feasible region. Any point of that region is a feasible solution, because it satisfies every constraint. An optimal solution is a feasible solution at which the objective function takes its maximum or minimum value. Points outside the region are infeasible solutions. The feasible region is always convex, and for two variables it is a polygon, possibly unbounded.

Hinglish: Sab constraints aur non-negativity ko satisfy karne wale points ka set feasible region hota hai. Us region ka koi bhi point feasible solution hai. Jis point par objective function maximum ya minimum hota hai, wahi optimal solution hai. Region ke bahar wale points infeasible solutions hote hain, aur feasible region hamesha convex hota hai.

Q4 Explain the corner point method

Answer (English): Draw the feasible region and list all its corner points, finding each coordinate by solving the two boundary lines that meet at that corner. Evaluate the objective function at every corner point. For a bounded region, the largest of these values is the maximum and the smallest is the minimum. The method works because a linear objective has parallel level lines, and as such a line moves across a convex polygon, its extreme contact with the region happens at a corner or along an edge.

Hinglish: Corner point method mein feasible region ke saare corner points nikaalo, har corner do boundary lines solve karke. Phir har corner par objective ki value lo. Bounded region mein sabse bada value maximum aur sabse chhota value minimum hota hai. Linear objective ki level lines parallel hoti hain, isliye extreme value corner par ya edge par milti hai.

Q5 What happens when the feasible region is bounded?

Answer (English): A bounded feasible region guarantees an answer at both ends: the objective has a largest and a smallest value on it, and both are found at corner points. This is the theorem that justifies the corner point method. In practice, write the corner points with their Z values in a table and read off the largest and smallest. No half-plane test is needed in this case.

Hinglish: Bounded region mein objective function ka maximum aur minimum dono exist karte hain, aur dono kisi corner point par milte hain. Isi theorem ki wajah se corner point method chalta hai. Corner points ke saath Z ki values table mein likho aur sabse bada-chhota value pick karo; bounded case mein half-plane test ki zaroorat nahi.

Q6 How do you handle an unbounded feasible region?

Answer (English): For an unbounded region, the corner values are candidates only. Suppose the largest corner value is M. Draw the line where the objective equals M and check whether the half plane where the objective is greater than M has any point in common with the feasible region. If it does, the objective can be increased without limit and there is no maximum. If it does not, M is the maximum. The minimum is tested the same way with the half plane below the smallest corner value.

Hinglish: Unbounded region mein corner values sirf candidates hoti hain. Agar sabse bada corner value M hai, to objective = M wali line draw karo aur dekho ki objective > M wali half plane feasible region ko cut karti hai ya nahi. Cut kare to maximum exist nahi karta; cut na kare to M hi maximum hai. Minimum ke liye objective < m wali half plane se yahi test karo.

Q7 When does an LPP have multiple optimal solutions?

Answer (English): When two corners of the feasible region carry equal optimal values of the objective, the whole edge between those corners carries that value too. The reason is that the objective is linear, so along that edge its value is constant. Such a problem has infinitely many optimal solutions, and the answer should say so rather than naming a single point. The exercises include a case where the minimum is 60 at two different corners and along the edge between them.

Hinglish: Agar do corner points same optimal value dein, to unke beech ke poore edge par bhi wahi value milti hai, kyunki objective linear hai aur us edge par constant rehta hai. Aise problem mein infinitely many optimal solutions hote hain, aur answer mein ye baat likhni chahiye, sirf ek point ka naam nahi. Exercise mein 60 wala minimum do corners aur unke beech ke edge par milta hai.

Q8 What does it mean when an LPP has no feasible solution?

Answer (English): If the half planes defined by the constraints have no point in common, the feasible region is empty. Then no point satisfies all the constraints, so the problem has no feasible solution and the objective cannot be optimised. A typical example has one constraint requiring large values of the variables and another keeping them small, so the two conditions contradict each other. On the graph the shaded regions do not overlap.

Hinglish: Agar constraints wali half planes ka koi common point nahi hota, to feasible region khaali hota hai. Tab koi point saare constraints satisfy nahi karta, isliye problem ka koi feasible solution nahi hota aur objective optimise nahi ho sakta. Aisa tab hota hai jab ek constraint bade values maange aur doosra chhote values par rok de; graph par shaded regions overlap nahi karte.

Q9 How is a bounded region different from an unbounded region?

Answer (English): A feasible region is bounded if it can be enclosed inside a circle; otherwise it is unbounded and extends without limit in some direction. For a bounded region, both the maximum and the minimum of the objective exist and occur at corner points. For an unbounded region, a maximum or a minimum may fail to exist even though the corner values exist, so the half-plane test is needed. Both kinds appear in the exercise, and the distinction is the first thing to note after shading.

Hinglish: Bounded region ko ek circle ke andar band kiya ja sakta hai; unbounded region kisi direction mein bina limit badhta rehta hai. Bounded region mein maximum aur minimum dono corners par milte hain. Unbounded region mein corner values hone ke baawajood optimum exist na kare, isliye half-plane test zaroori hai. Shading ke baad pehle yahi farq note karo.

Q10 Outline the steps of the graphical method for an LPP

Answer (English): Draw each constraint as a boundary line, using its intercepts, and shade the side that satisfies the inequality. The common shaded region is the feasible region. Find its corner points by solving the pairs of boundary lines that meet there. Evaluate the objective function at each corner and tabulate the values. If the region is bounded, take the largest and smallest values as the maximum and minimum; if it is unbounded, test the candidate values with the appropriate half plane. Finish with the optimal point and the optimal value.

Hinglish: Har constraint ki boundary line intercepts se draw karo aur inequality satisfy karne wali side shade karo; common region feasible region hai. Uske corner points boundary lines ke pairs solve karke nikaalo, phir har corner par objective ki value table mein likho. Bounded case mein sabse bada aur chhota value hi answer hai; unbounded case mein half-plane test karo. Aakhir mein optimal point aur optimal value likho.

That completes the ten questions. The five MCQ quiz below checks the vocabulary, the corner point method, the bounded and unbounded tests, and the meaning of multiple optimal solutions.