Basic Feasible Solutions | Mathematics Optional Notes for UPSC PDF Download

 Page 1


Edurev123 
Linear Programming Problems 
1. Basic Feasible Solutions 
1.1 By the method of Vogel, determine an initial basic feasible solution for the 
following transportation problem: 
Product ?? ?? ,?? ?? ,?? ?? and ?? ?? have to be sent to destinations ?? ?? ,?? ?? and ?? ?? . The cost 
of sending product ?? ?? to destinations ?? ?? is ?? ????
, where the matrix 
[?? ????
]=[
???? ?? ???? ?? ?? ?? ?? ????
?? ?? ?? ?? ????
] 
The total requirements of destinations ?? ?? ,?? ?? and ?? ?? are given by ???? ,???? ,???? 
respectively and the availability of the products ?? ?? ,?? ?? ,?? ?? and ?? ?? are respectively 
???? ,???? ,???? and 70 . 
(2012 : 20 Marks) 
Solution: 
The above problem can be expressed as 
 
? By Vogel's method, an initial basic feasible solution of the given problem is given by 
the above table. 
 Total transportation cost ?=3×20+11×15+9×55+5×45+15×25
?=60+165+495+225+375= Rs. 1320
 
Explanation of Vogel's Method : 
1. The given values ?? ????
 (given cost) are written in the upper left corner. 
Page 2


Edurev123 
Linear Programming Problems 
1. Basic Feasible Solutions 
1.1 By the method of Vogel, determine an initial basic feasible solution for the 
following transportation problem: 
Product ?? ?? ,?? ?? ,?? ?? and ?? ?? have to be sent to destinations ?? ?? ,?? ?? and ?? ?? . The cost 
of sending product ?? ?? to destinations ?? ?? is ?? ????
, where the matrix 
[?? ????
]=[
???? ?? ???? ?? ?? ?? ?? ????
?? ?? ?? ?? ????
] 
The total requirements of destinations ?? ?? ,?? ?? and ?? ?? are given by ???? ,???? ,???? 
respectively and the availability of the products ?? ?? ,?? ?? ,?? ?? and ?? ?? are respectively 
???? ,???? ,???? and 70 . 
(2012 : 20 Marks) 
Solution: 
The above problem can be expressed as 
 
? By Vogel's method, an initial basic feasible solution of the given problem is given by 
the above table. 
 Total transportation cost ?=3×20+11×15+9×55+5×45+15×25
?=60+165+495+225+375= Rs. 1320
 
Explanation of Vogel's Method : 
1. The given values ?? ????
 (given cost) are written in the upper left corner. 
2. Find the difference between the smallest and next to the smallest ?? ????
'
 s across 
rows and columns and write at the bottom and extreme right of the boxes. 
3. Select the row/column having the largest difference. 
4. Allocate the maximum possible to the smallest cost and write in the middle. 
5. Cross-out the columns/rows whose cost/demand gets completely filled. 
1.2 How many basic solutions are there in following linearly independent set of 
equations? Find all of them. 
?? ?? ?? -?? ?? +?? ?? ?? +?? ?? ?=?? ?? ?? ?? -?? ?? ?? -?? ?? +?? ?? ?? ?=????
 
(2018 : 15 Marks) 
Solution: 
Form the table from given set of equations : 
Basic Variables Non-Basic Variables Solution Is it possible? 
?? 1
,?? 2
 ?? 3
=?? 4
=0 Inconsistent No 
?? 1
,?? 3
 ?? 2
=?? 1
=0 
?? 1
=2.57 
?? 3
=0.236 
Yes 
?? 1
,?? 4
 ?? 2
=?? 3
=0 
Inconsistent 
equation 
No 
?? 2
,?? 3
 ?? 1
=?? 4
=0 
?? 2
=-5.14 
?? 3
=0.286 
Yes 
?? 2
,?? 4
 ?? 1
=?? 3
=0 
Inconsistent 
equation 
No 
?? 3
,?? 4
 ?? 1
=?? 2
=0 
?? 3
=0.286 
?? 1
=5.14 
Yes 
 
? There are 3 basic solutions. 
(??)???????????????????????????? 1
=2.57,?? 2
=0,?? 3
=0.286,?? 4
=0
(???? )?????????????????????????? 1
=0,?? 2
=-5.14,?? 3
=0.286,?? 4
=0
(?????? )????????????????????????? 1
=0,?? 2
=0,?? 3
=0.286,?? 4
=5.14
 
Page 3


Edurev123 
Linear Programming Problems 
1. Basic Feasible Solutions 
1.1 By the method of Vogel, determine an initial basic feasible solution for the 
following transportation problem: 
Product ?? ?? ,?? ?? ,?? ?? and ?? ?? have to be sent to destinations ?? ?? ,?? ?? and ?? ?? . The cost 
of sending product ?? ?? to destinations ?? ?? is ?? ????
, where the matrix 
[?? ????
]=[
???? ?? ???? ?? ?? ?? ?? ????
?? ?? ?? ?? ????
] 
The total requirements of destinations ?? ?? ,?? ?? and ?? ?? are given by ???? ,???? ,???? 
respectively and the availability of the products ?? ?? ,?? ?? ,?? ?? and ?? ?? are respectively 
???? ,???? ,???? and 70 . 
(2012 : 20 Marks) 
Solution: 
The above problem can be expressed as 
 
? By Vogel's method, an initial basic feasible solution of the given problem is given by 
the above table. 
 Total transportation cost ?=3×20+11×15+9×55+5×45+15×25
?=60+165+495+225+375= Rs. 1320
 
Explanation of Vogel's Method : 
1. The given values ?? ????
 (given cost) are written in the upper left corner. 
2. Find the difference between the smallest and next to the smallest ?? ????
'
 s across 
rows and columns and write at the bottom and extreme right of the boxes. 
3. Select the row/column having the largest difference. 
4. Allocate the maximum possible to the smallest cost and write in the middle. 
5. Cross-out the columns/rows whose cost/demand gets completely filled. 
1.2 How many basic solutions are there in following linearly independent set of 
equations? Find all of them. 
?? ?? ?? -?? ?? +?? ?? ?? +?? ?? ?=?? ?? ?? ?? -?? ?? ?? -?? ?? +?? ?? ?? ?=????
 
(2018 : 15 Marks) 
Solution: 
Form the table from given set of equations : 
Basic Variables Non-Basic Variables Solution Is it possible? 
?? 1
,?? 2
 ?? 3
=?? 4
=0 Inconsistent No 
?? 1
,?? 3
 ?? 2
=?? 1
=0 
?? 1
=2.57 
?? 3
=0.236 
Yes 
?? 1
,?? 4
 ?? 2
=?? 3
=0 
Inconsistent 
equation 
No 
?? 2
,?? 3
 ?? 1
=?? 4
=0 
?? 2
=-5.14 
?? 3
=0.286 
Yes 
?? 2
,?? 4
 ?? 1
=?? 3
=0 
Inconsistent 
equation 
No 
?? 3
,?? 4
 ?? 1
=?? 2
=0 
?? 3
=0.286 
?? 1
=5.14 
Yes 
 
? There are 3 basic solutions. 
(??)???????????????????????????? 1
=2.57,?? 2
=0,?? 3
=0.286,?? 4
=0
(???? )?????????????????????????? 1
=0,?? 2
=-5.14,?? 3
=0.286,?? 4
=0
(?????? )????????????????????????? 1
=0,?? 2
=0,?? 3
=0.286,?? 4
=5.14
 
1.3 UPSC maintenance section has purchased sufficient number of curtain cloth 
pieces to meet the curtain requirement of its building. The length of each piece is 
17 feet. The requirement according to curtain length is as follows: 
Curtain length (in feet) Number required 
5 700 
9 400 
7 300 
 
The width of all curtains is same as that of available pieces. Form a linear 
programming problem in standard form that decides the number of pieces cut in 
different ways so that the total trim loss is minimum. Also give a basic feasible 
solution to it. 
(2020 : 10 Marks) 
Solution: 
Given,                        Length of curtain =17ft 
Quantity Curtain length Loss (ft) 
 9 7 5  
?? 1
 1 1 0 1 
?? 2
 1 0 1 3 
?? 3
 0 1 2 0 
?? 4
 0 2 0 3 
?? 5
 0 0 3 2 
 
To minimize, 
?? ?=?? 1
+3?? 2
+0?? 3
+3?? 4
+2?? 5
?=?? 1
+3?? 2
+3?? 4
+2?? 5
 
For 5 feet curtain, 
0?? 1
+?? 2
+2?? 3
+0?? 4
+3?? 5
=700 (??) 
Page 4


Edurev123 
Linear Programming Problems 
1. Basic Feasible Solutions 
1.1 By the method of Vogel, determine an initial basic feasible solution for the 
following transportation problem: 
Product ?? ?? ,?? ?? ,?? ?? and ?? ?? have to be sent to destinations ?? ?? ,?? ?? and ?? ?? . The cost 
of sending product ?? ?? to destinations ?? ?? is ?? ????
, where the matrix 
[?? ????
]=[
???? ?? ???? ?? ?? ?? ?? ????
?? ?? ?? ?? ????
] 
The total requirements of destinations ?? ?? ,?? ?? and ?? ?? are given by ???? ,???? ,???? 
respectively and the availability of the products ?? ?? ,?? ?? ,?? ?? and ?? ?? are respectively 
???? ,???? ,???? and 70 . 
(2012 : 20 Marks) 
Solution: 
The above problem can be expressed as 
 
? By Vogel's method, an initial basic feasible solution of the given problem is given by 
the above table. 
 Total transportation cost ?=3×20+11×15+9×55+5×45+15×25
?=60+165+495+225+375= Rs. 1320
 
Explanation of Vogel's Method : 
1. The given values ?? ????
 (given cost) are written in the upper left corner. 
2. Find the difference between the smallest and next to the smallest ?? ????
'
 s across 
rows and columns and write at the bottom and extreme right of the boxes. 
3. Select the row/column having the largest difference. 
4. Allocate the maximum possible to the smallest cost and write in the middle. 
5. Cross-out the columns/rows whose cost/demand gets completely filled. 
1.2 How many basic solutions are there in following linearly independent set of 
equations? Find all of them. 
?? ?? ?? -?? ?? +?? ?? ?? +?? ?? ?=?? ?? ?? ?? -?? ?? ?? -?? ?? +?? ?? ?? ?=????
 
(2018 : 15 Marks) 
Solution: 
Form the table from given set of equations : 
Basic Variables Non-Basic Variables Solution Is it possible? 
?? 1
,?? 2
 ?? 3
=?? 4
=0 Inconsistent No 
?? 1
,?? 3
 ?? 2
=?? 1
=0 
?? 1
=2.57 
?? 3
=0.236 
Yes 
?? 1
,?? 4
 ?? 2
=?? 3
=0 
Inconsistent 
equation 
No 
?? 2
,?? 3
 ?? 1
=?? 4
=0 
?? 2
=-5.14 
?? 3
=0.286 
Yes 
?? 2
,?? 4
 ?? 1
=?? 3
=0 
Inconsistent 
equation 
No 
?? 3
,?? 4
 ?? 1
=?? 2
=0 
?? 3
=0.286 
?? 1
=5.14 
Yes 
 
? There are 3 basic solutions. 
(??)???????????????????????????? 1
=2.57,?? 2
=0,?? 3
=0.286,?? 4
=0
(???? )?????????????????????????? 1
=0,?? 2
=-5.14,?? 3
=0.286,?? 4
=0
(?????? )????????????????????????? 1
=0,?? 2
=0,?? 3
=0.286,?? 4
=5.14
 
1.3 UPSC maintenance section has purchased sufficient number of curtain cloth 
pieces to meet the curtain requirement of its building. The length of each piece is 
17 feet. The requirement according to curtain length is as follows: 
Curtain length (in feet) Number required 
5 700 
9 400 
7 300 
 
The width of all curtains is same as that of available pieces. Form a linear 
programming problem in standard form that decides the number of pieces cut in 
different ways so that the total trim loss is minimum. Also give a basic feasible 
solution to it. 
(2020 : 10 Marks) 
Solution: 
Given,                        Length of curtain =17ft 
Quantity Curtain length Loss (ft) 
 9 7 5  
?? 1
 1 1 0 1 
?? 2
 1 0 1 3 
?? 3
 0 1 2 0 
?? 4
 0 2 0 3 
?? 5
 0 0 3 2 
 
To minimize, 
?? ?=?? 1
+3?? 2
+0?? 3
+3?? 4
+2?? 5
?=?? 1
+3?? 2
+3?? 4
+2?? 5
 
For 5 feet curtain, 
0?? 1
+?? 2
+2?? 3
+0?? 4
+3?? 5
=700 (??) 
For 7 feet curtain, 
?? 1
+0?? 2
+?? 3
+2?? 4
+0?? 5
=300 (???? ) 
For 9 feet, 
?? 1
+?? 2
+0?? 3
+0?? 4
+0?? 5
?=400 (?????? )
?? 1
,?? 2
,?? 3
,?? 4
,?? 5
?=0 (???? )
 
Basic feasible solution: Let ?? 3
,?? 4
=0. Thus we have 3 equations and 3 variable . 
Thus, ?? 1
=300,?? 2
=100 and ?? 3
=200 from (i), (ii) and (iii). 
? Basic solution (300,100,0,0,200) . 
 Max =1000 feet