Educational Level

Secondary school, High school and College 
Program Purpose

Provide step by step solutions of your problems using online calculators (online solvers)

Problem Source

Your textbook, etc 
1.
Assignment Problem (Using Hungarian Method)

1. A computer centre has 3expert programmers. The centre wants 3 application programmes
to be developed. The head of thecomputer centre, after studying carefully the programmes
to be developed, estimates the computer time in minutes required by the experts
for the application programmes as follows.


Programmers 


A 
B 
C 
Programmes 
1 
6 
3 
5 
2 
5 
9 
2 
3 
5 
7 
8 
2. A department has five employess with five jobs to be permormed. The time (in
hours) each men will take to perform ech job is given in the effectiveness matrix.


Employees 


I 
II 
III 
IV 
V 
Jobs 
A 
10 
5 
113 
15 
16 
B 
3 
9 
18 
13 
6 
C 
10 
7 
2 
2 
2 
D 
7 
11 
9 
7 
12 
E 
7 
9 
10 
4 
12 
How should the jobs be allocated, one per employee, so as to minimize the total
manhours?

Unbalanced Assignment Problem.
3. In the modification of a plant layout of a factory four new machines M1, M2,
M3 and M4 are to be installed in a machine shop. There are five vacant places A,
B, C, D and E available. Because of limited space, machine M2 cannot be placed at
C and M3 cannot be placed at A. The cost of locating a machine at a place (in hundred
rupess) is as follows.


Location 


A 
B 
C 
D 
E 
Machine 
M1 
9 
11 
15 
10 
11 
M2 
12 
9 
 
10 
9 
M3 
 
11 
14 
11 
7 
M4 
14 
8 
12 
7 
8 
Find the optimal assignment schedule.
4. An airline company has drawn up a new flight schedule involving five flights.
To assist in allocating five pilots to the flights, it has asked them to state their
preference scores by giving each flight a number out of 10. The higher the number,
the greater is the preference. Certain of these flights are unsuitable to some pilots
owing to domestic reasons. These have been marked with a .


Flight Number 


I 
II 
III 
IV 
V 
Pilot 
A 
8 
2 
 
5 
4 
B 
10 
9 
2 
8 
4 
C 
5 
4 
9 
6 
 
D 
3 
6 
2 
8 
7 
E 
5 
6 
10 
4 
3 
What should be the allocation of the pilots to flights in order to meet as many
preferences as possible?



2.1
Simplex Method

1. Use the simplex method to solve the following LP problem.
Maximize Z = 3x1 + 5x2 + 4x3
subject to the constraints
2x1 + 3x2 ≤ 8
2x2 + 5x3 ≤ 10
3x1 + 2x2 + 4x3 ≤ 15
and x1, x2, x3 ≥ 0
2. Use the simplex method to solve the following LP problem.
Maximize Z = 4x1 + 3x2
subject to the constraints
2x1 + x2 ≤ 1000
x1 + x2 ≤ 800
x1 ≤ 400
x2 ≤ 700
and x1, x2 ≥ 0


2.2
BigM Method

1. Use the penalty (Big  M) method to solve the following LP problem.
Minimize Z = 5x1 + 3x2
subject to the constraints
2x1 + 4x2 ≤ 12
2x1 + 2x2 = 10
5x1 + 2x2 ≥ 10
and x1, x2 ≥ 0
2. Use the penalty (Big  M) method to solve the following LP problem.
Minimize Z = x1 + 2x2 + 3x3  x4
subject to the constraints
x1 + 2x2 + 3x3 = 15
2x1 + x2 + 5x3 = 20
x1 + 2x2 + x3 + x4 = 10
and x1, x2, x3, x4 ≥ 0 


2.3
TwoPhase Method

1. Solve the following LP problem by using the twophase simplex method.
Minimize Z = x1 + x2
subject to the constraints
2x1 + 4x2 ≥ 4
x1 + 7x2 ≥ 7
and x1, x2 ≥ 0
2. Solve the following LP problem by using the twophase simplex method.
Minimize Z = x1  2x2  3x3
subject to the constraints
2x1 + 3x2 + 3x3 = 2
2x1 + 3x2 + 4x3 = 1
and x1, x2, x3 ≥ 0 

2.4
Dual Simplex Method

1. Solve the following LP problem by using the twophase simplex method.
Minimize Z = x1 + x2
subject to the constraints
2x1 + 4x2 ≥ 4
x1 + 7x2 ≥ 7
and x1, x2 ≥ 0
2. Solve the following LP problem by using the twophase simplex method.
Minimize Z = x1  2x2  3x3
subject to the constraints
2x1 + 3x2 + 3x3 = 2
2x1 + 3x2 + 4x3 = 1
and x1, x2, x3 ≥ 0 


2.5
Gomorys Integer Cutting Method

1. Solve the following integer programming problem using Gomory's cutting plane algorithm.
Maximize Z = x1 + x2
subject to the constraints
3x1 + 2x2 ≤ 5
x2 ≤ 2
and x1, x2 ≥ 0 and are integers.
2. Solve the following integer programming problem using Gomory's cutting plane algorithm.
Maximize Z = 2x1 + 20x2  10x3
subject to the constraints
2x1 + 20x2 + 4x3 ≤ 15
6x1 + 20x2 + 4x3 ≤ 20
and x1, x2, x3 ≥ 0 and are integers. 

2.6
Graphical Method

1. Use graphical method to solve following LP problem.
Maximize Z = x1 + x2
subject to the constraints
3x1 + 2x2 ≤ 5
x2 ≤ 2
and x1, x2 ≥ 0
2. Use graphical method to solve following LP problem.
Maximize Z = 2x1 + x2
subject to the constraints
x1 + 2x2 ≤ 10
x1 + x2 ≤ 6
x1  x2 ≤ 2
x1  2x2 ≤ 1
and x1, x2 ≥ 0



2.7
Primal to dual conversion

1. Write the dual to the following LP problem.
Maximize Z = x1  x2 + 3x3
subject to the constraints
x1 + x2 + x3 ≤ 10
2x1  x2  x3 ≤ 2
2x1  2x2  3x3 ≤ 6
and x1, x2, x3 ≥ 0
2. Write the dual to the following LP problem.
Minimize Z = 3x1  2x2 + 4x3
subject to the constraints
3x1 + 5x2 + 4x3 ≥ 7
6x1 + x2 + 3x3 ≥ 4
7x1  2x2  x3 ≤ 10
x1  2x2 + 5x3 ≥ 3
4x1 + 7x2  2x3 ≥ 2
and x1, x2, x3 ≥ 0 



Examples

1. A Company has 3 production facilities S1, S2 and S3 with production capacity
of 7, 9 and 18 units (in 100's) per week of a product, respectively. These units
are tobe shipped to 4 warehouses D1, D2, D3 and D4 with requirement of 5,6,7 and
14 units (in 100's) per week, respectively. The transportation costs (in rupees)
per unit between factories to warehouses are given in the table below.

D_{1} 
D_{2} 
D_{3} 
D_{4} 
Capacity 
S_{1} 
19 
30 
50 
10 
7 
S_{2} 
70 
30 
40 
60 
9 
S_{3} 
40 
8 
70 
20 
18 
Demand 
5 
8 
7 
14 
34 
Find initial basic feasible solution for given problem by using
(a) NorthWest corner method
(b) Least cost method
(c) Vogel's approximation method
(d) obtain an optimal solution by MODI method
if the object is to minimize the total transportation cost.
2. Find an initial basic feasible solution for given transportation problem by using
(a) NorthWest corner method
(b) Least cost method
(c) Vogel's approximation method

D_{1} 
D_{2} 
D_{3} 
D_{4} 
Supply 
S_{1} 
11 
13 
17 
14 
250 
S_{2} 
16 
18 
14 
10 
300 
S_{3} 
21 
24 
13 
10 
400 
Demand 
200 
225 
275 
250 

3. A company has factories at F1, F2 and F3 which supply to warehouses at W1, W2
and W3. Weekly factory capacities are 200, 160 and 90 units, respectively. Weekly
warehouse requiremnet are 180, 120 and 150 units, respectively. Unit shipping costs
(in rupess) are as follows:

W_{1} 
W_{2} 
W_{3} 
Supply 
F_{1} 
16 
20 
12 
200 
F_{2} 
14 
8 
18 
160 
F_{3} 
26 
24 
16 
90 
Demand 
180 
120 
150 
450 
Determine the optimal distribution for this company to minimize total shipping cost.
4. Find an initial basic feasible solution for given transportation problem by using
(a) NorthWest corner method
(b) Least cost method
(c) Vogel's approximation method

P 
Q 
R 
S 
Supply 
A 
6 
3 
5 
4 
22 
B 
5 
9 
2 
7 
15 
C 
5 
7 
8 
6 
8 
Demand 
7 
12 
17 
9 
45 



Examples

1. An assembly is to be made from two parts X and Y. Both parts must be turned on a lathe
Y must be polished where as X need not be polished. The sequence of acitivities, together with their
predecessors, is given below
Activity 
Description 
Predecessor Activity 
A 
Open work order 
 
B 
Get material for X 
A 
C 
Get material for Y 
A 
D 
Turn X on lathe 
B 
E 
Turn Y on lathe 
B,C 
F 
Polish Y 
E 
G 
Assemble X and Y 
D,F 
H 
Pack 
G 
Draw a network diagram of activities for the project.
2. An established company has decided to add a new product to its line. It will buy the
product from a manufacturing concern, package it, and sell it to a number of distributors that have been
selected on a geographical basis. Market research has already indicated the volume expected and the size
of sales force required. The steps shown in the following table are to be planned.
Activity 
Description 
Predecessor Activity 
Duration (days) 
A 
Organize sales office 
 
6 
B 
Hire salesman 
A 
4 
C 
Train salesman 
B 
7 
D 
Select advertising agency 
A 
2 
E 
Plan advertising campaign 
D 
4 
F 
Conduct advertising campaign 
E 
10 
G 
Design package 
 
2 
H 
Setup packaging campaign 
G 
10 
I 
Package initial stocks 
J,H 
6 
J 
Order stock from manufacturer 
 
13 
K 
Select distributors 
A 
9 
L 
Sell to distributors 
C,K 
3 
M 
Ship stocks to distributors 
I,L 
5 
(a) Draw an arrow diagram for the project.
(b) Indicate the criticla path.
(c) For each noncritical activity, find the total and free float.



Examples

1. There are seven jobs, each of which has to go through the machines A and B in the order
AB. Processing times in hours are as follows.
Job 
1 
2 
3 
4 
5 
6 
7 
Machine A 
3 
12 
15 
6 
10 
11 
9 
Machine B 
8 
10 
10 
6 
12 
1 
3 
Decide a sequence of these jobs that will minimize the total elapsed time T. Also find T and idle
time for machines A and B.
2. Find the sequence that minimizes the total time required in performing the following job
on three machines in the order ABC. Processing times (in hours) are given in the following table.
Job 
1 
2 
3 
4 
5 
Machine A 
8 
10 
6 
7 
11 
Machine B 
5 
6 
2 
3 
4 
Machine C 
4 
9 
8 
6 
5 



Model1.1

1. A firm is considering the replacement of a machine, whose cost price is Rs 12,200 and its scrap value is Rs 200. From experience the running (maintenance and operating) costs are found to be as follows:
Year  1  2  3  4  5  6  7  8 

Running Cost  200  500  800  1,200  1,800  2,500  3,200  4,000 

When should the machine be replaced?



Model1.2

1. The data collected in running a machine, the cost of which is Rs 60,000 are given below:
Year  1  2  3  4  5 

Resale Value  42,000  30,000  20,400  14,400  9,650 

Cost of spares  4,000  4,270  4,880  5,700  6,800 

Cost of labour  14,000  16,000  18,000  21,000  25,000 

Determine the optimum period for replacement of the machine.



Model1.3

1. Machine A costs Rs 45,000 and its operating costs are estimated to be Rs 1,000 for the first year
increasing by Rs 10,000 per year in the second and subsequent years.
Machine B costs Rs 50,000 and operating costs are Rs 2,000 for the first year, increasing by Rs 4,000 in the second and subsequent years.
If at present we have a machine of type A, should we replace it with B? if so when?
Assume that both machines have no resale value and their future costs are not discounted.



Model2
Replacement policy for items whose running cost increases with time but value of money changes constant rate during a period

1. An engineering company is offered a material handling equipment A. It is priced at
Rs 60,000 includeing cost of installation. The costs for operation and maintenance are estimated to be
Rs 10,000 for each of the first five years, increasing every year by Rs 3,000 in the sixth and subsequent years.
The company expects a return of 10 percent on all its investment. What is the optimal replacement period?
Year  1  2  3  4  5  6  7  8  9  10 

Running Cost  10,000  10,000  10,000  10,000  10,000  13,000  16,000  19,000  22,000  25,000 

2. A company is buying mini computers. It costs Rs 5 lakh, and its running and maintenance costs are Rs 60,000
for each of the first five years, increasing by Rs 20,000 per year in the sixth and subsequent years.
If the money is worth 10 percent per year, What is the optimal replacement period?



Model3 Group replacement policy

1. A computer contains 10,000 resistors. When any resistor fails, it is replaced. The cost of replacing a resistor
individually is Rs 1 only. If all the resistors are replaced at the same time, the cost per resistor would be
reduced to 35 paise. The percentage of surviving resistors say S(t) at the end of month t and the probability
of failure P(t) during the month t are as follows:
t  0  1  2  3  4  5  6 

P(t)  0  0.03  0.07  0.20  0.40  0.15  0.15 

What is the optimal replacement plan?
2. The following mortality rates have been observed for a certain type of fuse:
t  0  1  2  3  4  5 

P(t)  0  0.05  0.10  0.20  0.40  0.25 

There are 1,000 fuses in use and it costs Rs 5 to replace an individual fuse. If all fuses were replaced
simultaneously it would cost Rs 1.25 per fuse. It is proposed to replace all fuses at fixed intervals of time,
whether or not they have burnt out, and to contiune replacing burnt out fuses as they fail. At what time
intervals should the group replacement be made? Also prove that this optimal policy is superior to the straight
forward policy of replacing each fuse only when it fails.





