Class 12: Linear Programming

Question 1.
Two godowns, A and B, have grain storage capacity of 100 quintals and 50 quintals respectively. They supply to 3 ration shops, D, E and F, whose requirements are 60, 50 and 40 quintals respectively. The cost of transportation per quintal from the godowns to the shops are given in the following table:

Transportation cost per quintal (in Rs)

$\displaystyle \begin{array}{|c|c|c|} \hline \text{To} & A & B \\ \hline D & 6.00 & 4.00 \\ E & 3.00 & 2.00 \\ F & 2.50 & 3.00 \\ \hline \end{array}$

How should the supplies be transported in order that the transportation cost is minimum?

$\displaystyle \text{Answer:}$
$\displaystyle \text{Let godown }A\text{ supply }x\text{ quintals and }y\text{ quintals of grain to the shops }D\text{ and }E \\ \text{ respectively.}$
$\displaystyle \text{Then }(100-x-y)\text{ will be supplied to shop }F.$
$\displaystyle \text{The requirement at shop }D\text{ is }60\text{ quintals.}$
$\displaystyle \text{Therefore, the remaining }(60-x)\text{ quintals will be transported from godown }B.$
$\displaystyle \text{Similarly, }(50-y)\text{ quintals and }40-(100-x-y)\text{ i.e. }(x+y-60)\text{ quintals will be transported} \\ \text{from godown }B\text{ to shop }E\text{ and }F\text{ respectively.}$
$\displaystyle \text{Quantity of the grain cannot be negative.}$
$\displaystyle x\ge0,\ y\ge0,\ 100-x-y\ge0$
$\displaystyle \Rightarrow x\ge0,\ y\ge0,\ x+y\le100$
$\displaystyle 60-x\ge0,\ 50-y\ge0,\ x+y-60\ge0$
$\displaystyle \Rightarrow x\le60,\ y\le50,\ x+y\ge60$
$\displaystyle \text{Total transportation cost }Z\text{ is given by,}$
$\displaystyle Z=6x+3y+2.5(100-x-y)+4(60-x)+2(50-y)+3(x+y-60)$
$\displaystyle =6x+3y+250-2.5x-2.5y+240-4x+100-2y+3x+3y-180$
$\displaystyle =2.5x+1.5y+410$
$\displaystyle \text{The given problem can be formulated as:}$
$\displaystyle \text{Minimize }Z=2.5x+1.5y+410$
$\displaystyle \text{subject to}$
$\displaystyle x+y\le100$
$\displaystyle x\le60$
$\displaystyle y\le50$
$\displaystyle x+y\ge60$
$\displaystyle x\ge0,\ y\ge0$
$\displaystyle \text{The feasible region determined by the constraints is represented graphically.}$ $\displaystyle \text{The corner points are }(60,0),\ (60,40),\ (50,50),\ (10,50).$
$\displaystyle \text{The values of }Z\text{ at these corner points are as follows:}$
$\displaystyle \begin{array}{|c|c|} \hline \text{Corner Point} & Z=2.5x+1.5y+410 \\ \hline (60,0) & 560 \\ (60,40) & 620 \\ (50,50) & 610 \\ (10,50) & 510 \\ \hline \end{array}$
$\displaystyle \text{The minimum value of }Z\text{ is }510\text{ at }(10,50).$
$\displaystyle \text{Thus, the amount of grain transported from }A\text{ to }D,E,F\text{ is }10,50,40\text{ quintals respectively.}$
$\displaystyle \text{From }B\text{ to }D,E,F\text{ is }50,0,0\text{ quintals respectively.}$
$\displaystyle \text{The minimum cost is Rs }510.$

Question 2.
A medical company has factories at two places A and B. From these places, supply is made to each of its three agencies situated at P, Q and R. The monthly requirements of the agencies are respectively 40, 40 and 50 packets of the medicines, while the production capacity of the factories A and B are 60 and 70 packets respectively. The transportation cost per packet from the factories to the agencies are given below:

Transportation cost per packet (in Rs)

$\displaystyle \begin{array}{|c|c|c|} \hline \text{To}\backslash \text{From} & A & B \\ \hline P & 5 & 4 \\ Q & 4 & 2 \\ R & 3 & 5 \\ \hline \end{array}$

How many packets from each factory be transported to each agency so that the cost of transportation is minimum? Also find the minimum cost.

$\displaystyle \text{Answer:}$
$\displaystyle \text{Let } x \text{ and } y \text{ packets be transported from factory } A \text{ to agencies } P \text{ and } Q \text{ respectively.}$
$\displaystyle \text{Then } 60-(x+y) \text{ packets are transported from factory } A \text{ to agency } R.$
$\displaystyle \text{The requirement at agency } P \text{ is } 40 \text{ packets.}$
$\displaystyle \text{Hence, } 40-x \text{ packets are transported from factory } B \text{ to agency } P.$
$\displaystyle \text{Similarly, } 40-y \text{ packets are transported from factory } B \text{ to agency } Q.$
$\displaystyle \text{Since the total requirement at } R \text{ is } 50,$
$\displaystyle 50-[60-(x+y)]=x+y-10 \text{ packets are transported from factory } B \text{ to agency } R.$
$\displaystyle \text{Since the number of packets cannot be negative,}$
$\displaystyle x \ge 0,\ y \ge 0,\ 60-x-y \ge 0$
$\displaystyle x+y \le 60$
$\displaystyle 40-x \ge 0,\ 40-y \ge 0,\ x+y-10 \ge 0$
$\displaystyle x \le 40,\ y \le 40,\ x+y \ge 10$
$\displaystyle \text{The total transportation cost is}$
$\displaystyle Z=5x+4y+3[60-(x+y)]+4(40-x)+2(40-y)+5(x+y-10)$
$\displaystyle Z=3x+4y+370$
$\displaystyle \text{Minimise } Z=3x+4y+370$
$\displaystyle \text{subject to}$
$\displaystyle x+y \le 60$
$\displaystyle x \le 40$
$\displaystyle y \le 40$
$\displaystyle x+y \ge 10$
$\displaystyle x \ge 0,\ y \ge 0$
$\displaystyle \text{The feasible region determined by the constraints is represented graphically.}$ $\displaystyle \text{The corner points of the feasible region are } (0,40),\ (20,40),\ (40,20),\ (40,0),\ (10,0),\ (0,10).$
$\displaystyle Z(0,40)=3(0)+4(40)+370=530$
$\displaystyle Z(20,40)=3(20)+4(40)+370=590$
$\displaystyle Z(40,20)=3(40)+4(20)+370=570$
$\displaystyle Z(40,0)=3(40)+4(0)+370=490$
$\displaystyle Z(10,0)=3(10)+4(0)+370=400$
$\displaystyle Z(0,10)=3(0)+4(10)+370=410$
$\displaystyle \text{The minimum value of } Z \text{ is } 400 \text{ at } (10,0).$
$\displaystyle \text{Therefore, the minimum transportation cost is Rs }400.$
$\displaystyle \text{From factory } A:\ 10,0,50 \text{ packets to } P,Q,R \text{ respectively.}$
$\displaystyle \text{From factory } B:\ 30,40,0 \text{ packets to } P,Q,R \text{ respectively.}$