Question

16. A developer of video game software has seven proposals for new games. Unfortunately,
the company cannot develop all the proposals because its budget for new projects
is limited to $950,000, and it has only 20 programmers to assign to new projects.
The financial requirements, returns, and the number of programmers required by each project are summarized in the following table. Projects 2 and 6 require specialized
programming knowledge that only one of the programmers has. Both of these
projects cannot be selected because the programmer with the necessary skills can be
assigned to only one of the projects. (Note: All dollar amounts represent thousands.)
Project Programmers Required Capital Required Estimated NPV
1 7 $250 $650
2 6 $175 $550
3 9 $300 $600
4 5 $150 $450
5 6 $145 $375
6 4 $160 $525
7 8 $325 $750
a. Formulate an ILP model for this problem.
b. Create a spreadsheet model for this problem and solve it.
c. What is the optimal solution?

Answer 1

(a): Let each project be assigned a binary variable. The binary variable will represent if a project is being selected or not. For instance if binary variable for project 1 is 0 it means that project 1 is not being selected. Variable 1 means project is being selected. The binary variables for the 7 projects are - a,b,c,d,e,f,g

Here we have to maximize the NPV. So objective function = 650a+550b+600c+450d+375e+525f+750g

Constraints:

(1) Total capital is $950,000. Hence 250a+175b+300c+150d+145e+160f+325g<=950

(2) No. of programmers is 20. Hence 7a+6b+9c+5d+6e+4f+8g<=20

(3) Only one of project 2 and 6 will be selected. Hence b+f<=1

(4) all variables are binary

b. Spreadsheet model and solution is provided below:

Project	Binary variable (as computed by solver)	Programmers	Capital	NPV
1	1	7	250	650
2	0	0	0	0
3	0	0	0	0
4	0	0	0	0
5	0	0	0	0
6	1	4	160	525
7	1	8	325	750
	Total	19	735	1925
						Formula
	Objective function	1925				650a+550b+600c+450d+375e+525f+750g
	Constraints
	735	<=	950			250a+175b+300c+150d+145e+160f+325g<=950
	19	<=	20			7a+6b+9c+5d+6e+4f+8g<=20
	1	<=	1			b+f<=1

c. In the optimal solution projects 1, 6 and 7 are selected. The total NPV of the selected projects is $1,925 (in thousands). All constraints are satisfied.