############################################################################################################# ## Exercise set 6 for ORMS1020-Operations Research, Fall 2011 week 42 ## ## All the 5 exercises are in this file. ## ## In this file we play around with a little bit of interactivity: We use the function input and the ## programming structure switch. We also use deeper indentation than before. ############################################################################################################# printf("############################################################################\n"); printf("Exercise set 6 for ORMS1020-Operations Research, Fall 2011 week 40. \n"); printf(" \n"); printf("This script file will define the function dea. (Actually, it just did it.) \n"); printf("############################################################################\n"); printf(" \n"); ## The function dea for calculating DEA efficiencies. function theta = dea(inputs, outputs) [n_in, n_DMUs] = size(inputs); [n_out, jippo] = size(outputs); if (n_DMUs != jippo) error("dea: Dimensions on inputs and outputs do not match.\n"); endif c = zeros(n_out+n_in, 1); # To be set later. A = zeros(1+n_DMUs, n_out+n_in); # An initialization. A(2:(n_DMUs+1), 1:n_out) = outputs'; # outputs part. A(2:(n_DMUs+1),(n_out+1):(n_out+n_in)) = -inputs'; # inputs part. b = zeros(n_DMUs+1, 1); # Just 0s now. b(1) = 1; # 1 and then 0s now. theta = zeros(n_DMUs,1); # 0s for now. ## Set constraint types ctype = "S"; for i=1:n_DMUs ctype = [ctype, "U"]; endfor ## Set variable types vtype = ""; for i=1:(n_in+n_out) vtype = [vtype, "C"]; endfor ## Solve the CCR LP for each DMUs: for o=1:n_DMUs c(1:n_out,1) = outputs(:,o); A(1,(n_out+1):(n_out+n_in)) = inputs(:,o)'; [x,theta(o)] = glpk(c,A,b,zeros(1,n_in+n_out),[],ctype,vtype,-1); endfor endfunction fflush(stdout); request = input("Which exercise would you want to see [1-5]? ","s"); switch request case "1" printf("############################################################################\n"); printf("Exercise 1: Exercise 6.2 from \n"); printf("http://www.uwasa.fi/~tsottine/or_with_octave/or_with_octave.pdf \n"); printf("############################################################################\n"); printf(" \n"); printf("First we set the names of the departments in the vector deps: \n"); deps = ["MS"; "P "; "C "; "CS"] printf(" \n"); printf("Then we set the input matrix X: \n"); X = [ 3 1 6 7; # P 3 5 4 6; # L 2 3 20 4] # A printf(" \n"); printf("Then we set the output matrix Y: \n"); Y = [10 14 10 21; # B 5 9 15 11; # M 5 1 11 10; # D 24 4 1 7;] # J printf(" \n"); printf("And here are the DEA efficiencies calculated by using the function dea that\n"); printf("was defined earlier in this script file. (It is the same as in the script\n"); printf("file ex5.m). Then the results are printed in a loop: \n"); printf(" \n"); theta = dea(X,Y); for o=1:length(theta) printf("%2s: %3.0f%% \n", deps(o,:), 100*theta(o)); endfor case "2" printf("############################################################################\n"); printf("Exercise 2: Exercise 6.3 from \n"); printf("http://www.uwasa.fi/~tsottine/or_with_octave/or_with_octave.pdf \n"); printf("############################################################################\n"); printf(" \n"); input("[Press Enter to see part (a)]"); printf(" \n"); printf("Part (a): First we set deps, X and Y as in exercise 1, except that we remove\n"); printf("the department P: \n"); deps = ["P "; "C "; "CS"] X = [ 1 6 7; # P 5 4 6; # L 3 20 4] # A Y = [14 10 21; # B 9 15 11; # M 1 11 10; # D 4 1 7;] # J printf(" \n"); printf("And here are the DEA efficiencies calculated: \n"); printf(" \n"); theta = dea(X,Y); for o=1:length(theta) printf("%2s: %3.0f%% \n", deps(o,:), 100*theta(o)); endfor input("[Press Enter to see part (b)]"); printf(" \n"); printf("Part (b): First we set deps, X and Y as in exercise 1, except that we remove\n"); printf("the output J: \n"); deps = ["MS"; "P "; "C "; "CS"] X = [ 3 1 6 7; # P 3 5 4 6; # L 2 3 20 3] # A Y = [10 14 10 21; # B 5 9 15 11; # M 5 1 11 10;] # D printf(" \n"); printf("And here are the DEA efficiencies calculated: \n"); printf(" \n"); theta = dea(X,Y); for o=1:length(theta) printf("%2s: %3.0f%% \n", deps(o,:), 100*theta(o)); endfor case "3" printf("############################################################################\n"); printf("Exercise 3: Exercise 7.1 from \n"); printf("http://www.uwasa.fi/~tsottine/or_with_octave/or_with_octave.pdf \n"); printf("############################################################################\n"); printf(" \n"); printf("First we introduce the cost matrix C (note the dump), the supply vector s\n"); printf("and the demand vector d: \n"); C = [ 8 6 10 9 0; 9 12 13 7 0; 14 9 16 5 0;] s = [35 50 40]' d = [40 20 30 30 5]'; printf(" \n"); printf("Then we calculate the answer by using the function trans_solver: \n"); [cost, schedule] = trans_solver(C, s, d) case "4" printf("############################################################################\n"); printf("Exercise 4: \n"); printf("An employer must assign 5 jobs to his 5 employees. The time it takes for\n"); printf("each employee to complete each job is given in the table below. The employer\n"); printf("wants to minimize the total time (since the employees are paid by the hour).\n"); printf("How should the employer assign the jobs assuming that each employer can take\n"); printf("only one job? \n"); printf(" \n"); printf(" Job1 Job2 Job3 Job4 Job5 \n"); printf("Employee 1 11 10 10 10 1 \n"); printf("Employee 2 19 18 18 19 20 \n"); printf("Employee 3 17 19 17 19 21 \n"); printf("Employee 4 18 17 18 17 19 \n"); printf("Employee 5 98 97 99 99 31 \n"); printf(" \n"); input("[Press Enter to continue]"); printf(" \n"); printf("We se C, s, d for trans_solver, and then use it: \n"); C = [ 11 10 10 10 1; 19 18 18 19 20; 17 19 17 19 21; 18 17 18 17 19; 98 97 99 99 31 ] s = d = [1 1 1 1 1]'; [cost, assignment] = trans_solver(C, s, d) case "5" printf("############################################################################\n"); printf("Exercise 5: Exercise 7.3 from \n"); printf("http://www.uwasa.fi/~tsottine/or_with_octave/or_with_octave.pdf \n"); printf("############################################################################\n"); printf(" \n"); input("[Press Enter to see part (a)]"); printf(" \n"); printf("(a): First we set M to be 1000 (big number): \n"); M = 1000 printf("Then we set C (note dump, company splitting, and M), s, and d. Then we use\n"); printf("the function trans_solver: \n"); C = [50 46 42 40 0; 51 48 44 M 0; 51 48 44 M 0; M 47 45 45 0; M 47 45 45 0;] s = d = [1 1 1 1 1]' [cost, assignment] = trans_solver(C, s, d) printf(" \n"); input("[Press Enter to see part (b)]"); printf(" \n"); printf("(b): The result will not change. Indeed, this is essential in modeling the\n"); printf("assignment problem as an LP instead of (more correctly) as a BIP. To see\n"); printf("that the result really does not change we repeat part (a) with 1 replaced\n"); printf("by 100%% :) \n"); M = 1000 C = [50 46 42 40 0; 51 48 44 M 0; 51 48 44 M 0; M 47 45 45 0; M 47 45 45 0;] s = d = [100 100 100 100 100]' [cost, assignment] = trans_solver(C, s, d) otherwise error("Invalid choice. Quitting. Type \"ex5\" to get back. \n"); endswitch