/******************************************************** * APPOINTMENT METHOD * * ------------------ * * * * LIST OF MAIN VARIABLES: * * * * NP: NUMBER OF JOBS * * C(NP,NP): APPOINTMENT COST MATRIX * * MP(NP,NP): JOB/APPLICANT MATRIX * * IF1: FLAG=1 IF OPTIMAL APPOINTMENT IS FOUND * * IZ: FLAG TO MARK A ZERO * * XMIN: MINIMUM VALUE * * XCASE: APPOINTMENT OF A ZERO IN RELATION WITH * * THE ZEROES' MINIMUM * * NZ: NUMBER OF ZEROES * * ZI,ZJ: COORDINATES OF CURRENT CASE * * M,N: COORDINATES OF A MARKED ZERO * * A,B: AUXILIARY VARIABLES TO CHANGE * * APPOINTMENTS. * * ----------------------------------------------------- * * PROBLEM DESCRIPTION * * An employer receives four applicants for four avail- * * able jobs. They must give a mark from 1 to 100 to * * each job (1=very poor preference, 100=very good). * * See table below: * * J O B S * * J1 J2 J3 J4 * * A1 90 80 20 40 * * APPLICANTS A2 90 70 30 80 * * A3 40 70 20 80 * * A4 50 40 20 60 * * The employer's purpose is to appoint the four jobs so * * as to maximize the applicants' satisfaction. * * ----------------------------------------------------- * * SAMPLE RUN: * * (appoint four jobs with the following regrets matrix: * * J O B S * * J1 J2 J3 J4 * * A1 10 20 80 60 * * APPLICANTS A2 10 30 70 20 * * A3 60 30 80 20 * * A4 50 60 80 40 ) * * * * LINEAR PROGRAMMING * * * * APPOINTMENT METHOD * * * * NUMBER OF JOBS ? 4 * * * * INPUT APPOINTMENT COSTS/REGRETS OF APPLICANTS: * * * * APPLICANT #1: * * JOB #1 ? 10 * * JOB #2 ? 20 * * JOB #3 ? 80 * * JOB #4 ? 60 * * * * APPLICANT #2: * * JOB #1 ? 10 * * JOB #2 ? 30 * * JOB #3 ? 70 * * JOB #4 ? 20 * * * * APPLICANT #3: * * JOB #1 ? 60 * * JOB #2 ? 30 * * JOB #3 ? 80 * * JOB #4 ? 20 * * * * APPLICANT #4: * * JOB #1 ? 50 * * JOB #2 ? 60 * * JOB #3 ? 80 * * JOB #4 ? 40 * * * * APPOINTMENTS: * * * * APPLICANT #1 => JOB #2 * * APPLICANT #2 => JOB #1 * * APPLICANT #3 => JOB #4 * * APPLICANT #4 => JOB #3 * * * * ----------------------------------------------------- * * REFERENCE: * * Modèles pratiques de décision Tome 2, By Jean-Pierre * * Blanger, PSI Editions, France, 1982. * * * * C++ Release 1.0 By J-P Moreau, Paris. * * (www.jpmoreau.fr) * ********************************************************/ #include #include #define NMAX 10 double C[NMAX][NMAX]; int MP[NMAX][NMAX]; int IF1,IZ,M,N,NP,NZ,ZI,ZJ; double A,B,XCASE,XMIN; void Data() { //INPUT COST/APPOINT int I,J; printf("\n LINEAR PROGRAMMING\n\n"); printf(" APPOINTMENT METHOD\n\n"); printf(" NUMBER OF JOBS ? "); scanf("%d", &NP); printf("\n INPUT APPOINTMENT COSTS/REGRETS OF APPLICANTS:\n"); for (I=1; I<=NP; I++) { printf("\n APPLICANT #%d:\n", I); for (J=1; J<=NP; J++) { printf(" JOB #%d ? ", J); scanf("%lf", &C[I][J]); } } printf("\n APPOINTMENTS:\n\n"); } void Zeroes(); void Appoint(); void Mark(); void Sub_add(); void Sub_Main() { //HUNGARIAN ALGORITHM e10:Zeroes(); Appoint(); Mark(); Sub_add(); Appoint(); if (IF1 != NP) goto e10; } void Zeroes() { int I,J; double R; IZ = 0; R = 0; for (I=1; I<=NP; I++) { XMIN = C[I][1]; for (J=1; J<=NP; J++) { if (C[I][J] == 0) IZ = 1; if (C[I][J] < XMIN) XMIN = C[I][J]; } if (IZ == 1) { IZ = 0; goto e10; } for (J=1; J<=NP; J++) C[I][J] -= XMIN; e10:;} for (J=1; J<=NP; J++) { XMIN = C[1][J]; for (I=1; I<=NP; I++) { if (C[I][J] == 0) IZ = 1; if (C[I][J] < XMIN) XMIN = C[I][J]; } if (IZ == 1) { IZ = 0; goto e20; } for (I=1; I<=NP; I++) C[I][J] -= XMIN; e20:;} } void Appoint() { int I,J,K; for (I=1; I<=NP; I++) { for (J=1; J<=NP; J++) { MP[I][J] = 0; C[0][J] = 0; } C[I][0] = 0; } for (I=1; I<=NP; I++) { XCASE = 999999; for (J=1; J<=NP; J++) { if (C[I][J] != 0 || MP[I][J] != 0) goto e10; NZ = 0; for (K=1; K<=NP; K++) if (C[K][J] == 0) NZ++; if (1.0*NZ < XCASE) { XCASE = 1.0*NZ; ZI = I; ZJ = J; } e10:;} MP[ZI][ZJ] = 1; for (K=1; K<=NP; K++) if (C[K][ZJ] == 0 && MP[K][ZJ] == 0) MP[K][ZJ] = -1; for (K=1; K<=NP; K++) if (C[ZI][K] == 0 && MP[ZI][K] == 0) MP[ZI][K] = -1; } IF1 = 0; for (I=1; I<=NP; I++) for (J=1; J<=NP; J++) if (MP[I][J] == 1) IF1++; } void Mark() { int I,J; e10: for (I=1; I<=NP; I++) { N = 0; for (J=1; J<=NP; J++) if (MP[I][J] == 1) N = 1; if (N == 0 && C[I][0] == 0) { C[I][0] = 1; M = 1; } } for (J=1; J<=NP; J++) for (I=1; I<=NP; I++) if (MP[I][J] == -1 && C[I][0] == 1 && C[0][J] == 0) { C[0][J] = 1; M = 1; } for (I=1; I<=NP; I++) for (I=1; I<=NP; I++) if (MP[I][J] == 1 && C[0][J] == 1 && C[I][0] == 0) { C[I][0] = 1; M = 1; } if (M == 1) { M = 0; goto e10; } } void Sub_add() { int I,J; XMIN = 999999; for (I=1; I<=NP; I++) for (J=1; J<=NP; J++) { A = C[I][0]; B = C[0][J]; if (A == 1 && B == 0 && C[I][J] < XMIN) XMIN = C[I][J]; } for (I=1; I<=NP; I++) for (J=1; J<=NP; J++) { A = C[I][0]; B = C[0][J]; if (A == 1 && B == 0) C[I][J] -= XMIN; if (A == 0 && B == 1) C[I][J] += 2 * XMIN; } } void Results() { int I,J; for (I=1; I<=NP; I++) for (J=1; J<=NP; J++) { if (MP[I][J] != 1) goto e10; printf(" APPLICANT #%d => JOB #%d\n", I, J); e10:;} printf("\n"); } void main() { Data(); // INPUT COST/APPOINT} Sub_Main(); // HUNGARIAN ALGORITHM Results(); // PRINT RESULTS } // END OF FILE APPOINT.CPP