Question

In a country whose currency is dinars, 1,5,10,20,25 and 50 dinars coins are used. In this country, a market employee must pay 91 dinars to his customer as a change. Develop an integer programming model so that the money can be paid with the least number of coins.

Answer 1

Ans:

Defining the decision variables:

x1 = No. of currency with denomination of 1 Dinar

x2= No. of currency with denomination of 5 Dinar

x3= No. of currency with denomination of 10 Dinar

x4= No. of currency with denomination of 20 Dinar

x5= No. of currency with denomination of 25 Dinar

x6= No. of currency with denomination of 50 Dinar

Constraints:

x1,x2,x3,,x4,x5,x6must be an integer

x1+5x2+10x3+20x4+25x5+50x6 = 91

Objective:

x1+x2+x3+x4+x5+x6 should be minimum

Integer programming model in excel is as follows:

1. Before running the ILP in excel using Solver

Variables
x1	0
x2	0
x3	0
x4	0
x5	0
x6	0
Objctive
Minimize	=J3+J4+J5+J6+J7+J8
Constraints		Inequalities
z	=J3+5*J4+10*J5+20*J6+25*J7+50*J8	=	91
x1	=J3	>=	0
x2	=J4	>=	0
x3	=J5	>=	0
x4	=J6	>=	0
x5	=J7	>=	0
x6	=J8	>=	0

2. Now after running the solver using the solver parameters as below:

Solver Parameters Set Objective: SC511 То: oMax o Min O Value Of: By Changing Variable Cells: SC53:5C58 Add Subject to the Constraints: SCS14 = $E$14 SCS3 = integer SCS4 = integer SCS5 = integer SCS6 = integer SCS7 = Integer SCS8 = integer Change Delete Reset All Load/Save Make Unconstrained variables Non-Negative Select a Solving GRG Nonlinear Method: Options Solving Method Select the GRG Nonlinear engine for Solver Problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth. Help Solve Close

Result is as mentioned below:

Variables
x1	1
x2	0
x3	0
x4	2
x5	0
x6	1
Objctive
Minimize	4
Constraints	LHS	Inequalities	RHS
z	91	=	91
x1	1	>=	0
x2	0	>=	0
x3	0	>=	0
x4	2	>=	0
x5	0	>=	0
x6	1	>=	0

Hence minim no. of coins are 4 using 1 coin of 1 , 2 coins of 20 and 1 coin of 50.

Note: Here in constraints plz select variables x1,x2.x3.x4.x5.x6 as integer.

To add Solver, add by going through file>option>add-in>solver