Assignment-1

1. Define linear programming and explain its significance in optimization problems.

2. What is meant by feasible region in linear programming?
3. Explain the difference between feasible solution, optimal solution, and infeasible solution in
linear programming.
4. Discuss the applications of linear programming in real-life situations.
5. A company produces two products, A and B. The profit per unit for product A is $10, and for
product B is $15. Each unit of product A requires 2 hours of labor, and each unit of product B
requires 3 hours of labor. The company has 100 hours of labor available per week. Product A
requires 4 units of raw material, while product B requires 5 units. The company has 80 units of
raw material available per week. Determine the number of units of each product to maximize the
profit.
Ans. Maximize Z = 10𝑥1 + 15 𝑥2
Subject to: 2𝑥1 + 3𝑥2 ≤ 100; 4 𝑥1 + 5 𝑥2 ≤ 80; 𝑥1 , 𝑥2 ≥ 0
6. A farmer has 100 acres of land available for planting wheat and barley. Each acre of wheat
requires 2 hours of labor, and each acre of barley requires 3 hours. The farmer has 240 hours of
labor available. Each acre of wheat yields a profit of $200, and each acre of barley yields a profit
of $300. Formulate a linear programming problem to maximize the profit.
Ans. Maximize Z = 200𝑥1 + 300 𝑥2
Subject to: 2𝑥1 + 3𝑥2 ≤ 240; 𝑥1 + 𝑥2 ≤ 100; 𝑥1 , 𝑥2 ≥ 0
7. A person wants to create a daily diet plan that meets the minimum requirements for various
nutrients at the lowest cost possible. The person needs at least 60 units of carbohydrates, 50 units
of protein, and 30 units of fat daily. Food A contains 10 units of carbohydrates, 5 units of protein,
and 8 units of fat per serving, costing $2 per serving. Food B contains 8 units of carbohydrates, 8
units of protein, and 6 units of fat per serving, costing $3 per serving. Formulate a linear
programming problem to minimize the cost while meeting the nutrient requirements.
Ans. Maximize Z = 2𝑥1 + 3 𝑥2
Subject to: 10𝑥1 + 8𝑥2 ≥ 60; 5𝑥1 + 8 𝑥2 ≥ 50; 8 𝑥1 + 6 𝑥2 ≥ 30; 𝑥1 , 𝑥2 ≥ 0
8. Maximize the objective function Z = 3x + 2y subject to the following constraints:
2 𝑥 + 𝑦 ≤ 10
𝑥 + 3𝑦 ≤ 12
𝑥, 𝑦 ≥ 0
Ans. The maximum value of Z occurs at point B(4, 4) where Z = 20.
9. Maximize Z = 4𝑥 + 3𝑦
Subject to:
2𝑥 + 3𝑦 ≤ 12
5𝑥 − 2𝑦 ≥ 20
 𝑥, 𝑦 ≥ 0
Ans. Infeasible solution
10. Minimize the objective function Z = 5x + 4y subject to the following constraints:
2 𝑥 + 𝑦 ≥ 20
𝑥 + 2𝑦 ≤ 20
𝑥, 𝑦 ≥ 0
Ans. The minimization problem is Z = 50 at point A(10, 0).
11. Maximize Z = 2𝑥 + 5𝑦
Subject to:

3𝑥 + 4𝑦 ≥ 15
6𝑥 + 8𝑦 ≤ 25
𝑥, 𝑦 ≥ 0
Ans. Infeasible solution
12. Maximize 𝑍 = 3𝑥 + 2𝑦
Subject to:
𝑥+𝑦 ≤6
𝑥−𝑦 ≥2
𝑥, 𝑦 ≥ 0
Ans. Unbounded solution
13. A steel company has three open hearth furnaces and five rolling mills. The transportation costs
(rupees per quintal) for shipping steel from furnaces to rolling mills are given in the following
table:
𝑀1 𝑀2 𝑀3 𝑀4 𝑀5 𝑆𝑢𝑝𝑝𝑙𝑦
𝐹1 4 2 3 2 6 8
𝐹2 5 4 5 2 1 12
𝐹3 6 5 4 7 7 14
𝐷𝑒𝑚𝑎𝑛𝑑 4 4 6 8 8

What is the optimal shipping schedule?

Ans. Total requirement (30) < Total capacity (34), add a dummy mill with requirement (34 – 30) = 4.
Degeneracy occur at the initial solution (VAM).

𝑥12 = 4, 𝑥14 = 4, 𝑥24 = 2, 𝑥25 = 8, 𝑥31 = 4, 𝑥33 = 6, 𝑥36 = 4, Total cost = Rs 80.

14. Consider the following unbalanced transportation problem. Since there is not enough supply,
some of the demands at these destinations may not be satisfied. Suppose there are penalty
 costs for every unsatisfied demand unit which are given by 5, 3 and 2 for destinations I, II and III,
respectively. Find the optimal solution.

I II III Supply
A 5 1 7 10
B 6 4 6 80
C 3 2 5 15
Demand 75 20 50

Ans. Demand (145) > Supply (105), add dummy source with supply (145 – 105) = 40 and
transportation costs 5, 3 and 2 for destination 1, 2 and 3, respectively.

x12 = 0, x21 = 60, x22 = 10, x23 = 10, x31 = 5, x43 = 40 Transportation cost = Rs 515. Penalty
for transportation of 40 units to destination 3 at the cost of Rs 2 per unit = Rs 80. Thus, total cost =
515 + 80 = Rs 595

15. Goods have to be transported from sources S1, S2 and S3 to destinations D1, D2 and D3. The
transportation cost per unit, capacities of the sources, and the requirements of the destinations
are given in the following table

𝐷1 𝐷2 𝐷3 Supply
𝑆1 8 5 6 120
𝑆2 15 10 12 80
𝑆3 3 9 10 80
Demand 150 80 50

Determine a transportation schedule so that cost is minimized.

Ans. 𝑥11 = 70, 𝑥13 = 50, 𝑥22 = 80, 𝑥31 = 80, Total cost = Rs 1,900.

16. A manufacturer wants to ship 22 loads of his product as shown below. The matrix gives the
kilometers from sources of supply to the destinations.

𝐷1 𝐷2 𝐷3 𝐷4 𝐷5 Supply
𝑆1 5 8 6 6 3 8
𝑆2 4 7 7 6 5 5
𝑆3 8 4 6 6 4 9
Demand 4 4 5 4 8

The shipping cost is Rs 10 per load per km. What shipping schedule should be used in order to
minimize the total transportation cost?

Ans. 𝑥15 = 8, 𝑥21 = 4, 𝑥24 = 1, 𝑥32 = 4, 𝑥33 = 2, 𝑥34 = 3, Total cost = Rs 920.

17. A company has received a contract to supply gravel to three new construction projects located
in towns A, B and C. The construction engineers have estimated that the required amounts of
gravel which will be needed at these construction projects are:
 Project Location Weekly Requirement
(Truckloads)
A 72
B 102
C 41

The company has 3 gravel pits located in towns X, Y and Z. The gravel required by the
construction projects can be supplied by three pits. The amount of gravel that can be supplied
by each pit is as follows:
Plant X Y Z
Amount available 76 82 77
(turckloads)
The company has computed the delivery cost from each pit to each project site. These costs (in
Rs) are shown in the following table:
A B C
X 4 8 8
Y 16 24 16
Z 8 16 24
Schedule the shipment from each pit to each project in such a manner that it minimizes the total
transportation cost within the constraints imposed by pit capacities and project requirements.
Also find the minimum cost.

Ans. 𝑥12 = 76, 𝑥22 = 21, 𝑥23 = 41, 𝑥31 = 72, 𝑥32 = 5, Total cost = Rs. 2424.

18. Determine an initial basic feasible solution to the following transportation problem by using (a)
NWCR, (b) LCM and (c) VAM.

𝐷1 𝐷2 𝐷3 𝐷4 Supply
𝑆1 21 16 15 3 11
𝑆2 17 18 14 23 13
𝑆3 32 27 18 41 19
Demand 6 6 8 23

Ans. X14 = 11, x21 = 6, x22 = 3, x24 = 4, x32 = 3, x33 = 4, x34 = 12; Total cost = 686.

19. Five men (A,B,C,D,E) are available to do five different jobs (I,II,III,IV,V). From past records, the
time (in hours) that each man takes to do each job is known and is given in the following table:

Jobs
I II III IV V
A 2 9 2 7 1
Men B 6 8 7 6 1
C 4 6 5 3 1
D 4 2 7 3 1
E 5 3 9 5 1
 Find out how men should be assigned the jobs in way that will minimize the total time taken.

Ans. A – III, B – V, C – I, D – IV, E – II; Optimal value = 13 hours

20. A national truck rental service has a surplus of one truck in each of the cities, 1, 2, 3, 4, 5 and 6;
and a deficit of one truck in each of the cities 7, 8, 9, 10, 11 and 12. The distances (in km)
between the cities with a surplus and cities with deficit are displayed in the table below:

To
7 8 9 10 11 12
1 31 62 29 42 15 41
2 12 19 39 55 71 40
From 3 17 29 50 41 22 22
4 35 40 38 42 27 33
5 19 30 29 16 20 23
6 72 30 30 50 41 20

How should the trucks be displayed so as to minimize the total distance travelled?

Ans. 1 – 11, 2 – 8, 3 – 7, 4 – 9, 5 – 10, 6 – 12; Minimum distance = 125 km.

21. A departmental head has four subordinates and four tasks to be performed. The subordinates
differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the times that
each man would take to perform each task is given in the matrix below:
Tasks
I II III IV
A 8 26 17 11
Subordinates B 13 28 4 26
C 38 19 18 15
D 19 26 24 10

How should the tasks be allocated to subordinates so as to minimize the total man-hours?

Ans. A – I, B – III, C – II, D – IV; Total man-hours = 41 hours.

22. . An automobile dealer wishes to put four repairmen to four different jobs. The repairmen have
somewhat different kinds of skills and they exhibit different levels of efficiency from one job to
another. The dealer has estimated the number of man-hours that would be required for each
job-man combination. This is given in matrix form in the following table:

Jobs
A B C D
1 5 3 2 8
Men 2 7 9 2 6
3 6 4 5 7
4 5 7 7 8
 Find the optimal assignment that will result in minimum man hours needed.

Ans. 1 – B, 2– C, 3– D, 4– A ; 1– C, 2– D, 3– B, 4– A; Total man-hours = 17 hours.

23. Solve the following assignment problem for minimum optimal cost

Jobs
I II III IV V VI
A 2 9 2 7 1 8
Men B 6 8 7 6 1 12
C 4 6 5 3 1 9
D 4 2 7 3 1 12
E 5 3 9 5 1 10

Ans. A – II, B – VI, C – III, D – I, E – IV; Optimal value = 38.

24. A company has four machines to do three jobs. Each job can be assigned to one and only one
machine. The cost of each job on each machine is given in the following table:
Machine
W X Y Z
A 18 24 28 32
Jobs B 8 13 17 19
C 10 15 19 22
What are the job assignments which will minimize the cost?

Ans. A – W, B – X, C – Y; Optimal value = 50.

25. Find the optimal assignment for the assignment problem with the following cost matrix:
I II III IV
A 5 3 1 8
B 7 9 2 6
C 6 4 5 7
D 5 7 7 6
Ans. A – III, B – IV, C – II, D – I; Optimal value is 16.