MESTRADO EM MODELAGEM COMPUTACIONAL DE CONHECIMENTO

GAMS Rev 116  Windows NT/95/98                    10/27/04 12:42:03  PAGE      1

o problema da mochila Subset-Sum Problem  pag 215

      Por exemplo, considere o problema da mochila com variante(Subset-Sum problem),

      que os custos possuem o mesmo valor dos pesos.

   6  binary variables

   7  x1

   8  x2

   9  x3

  10  x4

  11  x5

  12  x6;

  13

  14  variables

  15

  16  z funcao objeto;

  17

  18  equations

  19  q1

  20  q2  funcao objetivo;

  21

  22

  23  q1.. x1 + 3*x2 + 2*x3 + 5*x4 + 4*x5 + 6*x6 =l=9;

  24  q2.. x1 + 2*x2 + x3 + 2*x4 + x5 + x6 =e=z;

  25  option mip=xa;

  26  model problemadamochila /all/;

  27  solve problemadamochila using mip maximized z;

COMPILATION TIME     =        0.000 SECONDS    0.7 Mb      WIN194-116

GAMS Rev 116  Windows NT/95/98                    10/27/04 12:42:03  PAGE      2

o problema da mochila Subset-Sum Problem  pag 215

Equation Listing    SOLVE problemadamochila USING MIP FROM LINE 27

---- q1  =L=

q1..  x1 + 3*x2 + 2*x3 + 5*x4 + 4*x5 + 6*x6 =L= 9 ; (LHS = 0)

---- q2  =E=  funcao objetivo

q2..  x1 + 2*x2 + x3 + 2*x4 + x5 + x6 - z =E= 0 ; (LHS = 0)

GAMS Rev 116  Windows NT/95/98                    10/27/04 12:42:03  PAGE      3

o problema da mochila Subset-Sum Problem  pag 215

Column Listing      SOLVE problemadamochila USING MIP FROM LINE 27

---- x1

x1

                (.LO, .L, .UP = 0, 0, 1)

        1       q1

        1       q2

---- x2

x2

                (.LO, .L, .UP = 0, 0, 1)

        3       q1

        2       q2

---- x3

x3

                (.LO, .L, .UP = 0, 0, 1)

        2       q1

        1       q2

---- x4

x4

                (.LO, .L, .UP = 0, 0, 1)

        5       q1

        2       q2

---- x5

x5

                (.LO, .L, .UP = 0, 0, 1)

        4       q1

        1       q2

---- x6

x6

                (.LO, .L, .UP = 0, 0, 1)

        6       q1

        1       q2

GAMS Rev 116  Windows NT/95/98                    10/27/04 12:42:03  PAGE      4

o problema da mochila Subset-Sum Problem  pag 215

Column Listing      SOLVE problemadamochila USING MIP FROM LINE 27

---- z  funcao objeto

z

                (.LO, .L, .UP = -INF, 0, +INF)

       -1       q2

GAMS Rev 116  Windows NT/95/98                    10/27/04 12:42:03  PAGE      5

o problema da mochila Subset-Sum Problem  pag 215

Model Statistics    SOLVE problemadamochila USING MIP FROM LINE 27

MODEL STATISTICS

BLOCKS OF EQUATIONS       2     SINGLE EQUATIONS        2

BLOCKS OF VARIABLES       7     SINGLE VARIABLES        7

NON ZERO ELEMENTS        13     DISCRETE VARIABLES      6

GENERATION TIME      =        0.030 SECONDS    1.4 Mb      WIN194-116

EXECUTION TIME       =        0.030 SECONDS    1.4 Mb      WIN194-116

GAMS Rev 116  Windows NT/95/98                    10/27/04 12:42:03  PAGE      6

o problema da mochila Subset-Sum Problem  pag 215

               S O L V E      S U M M A R Y

     MODEL   problemadamochila   OBJECTIVE  z

     TYPE    MIP                 DIRECTION  MAXIMIZE

     SOLVER  XA                  FROM LINE  27

**** SOLVER STATUS     1 NORMAL COMPLETION

**** MODEL STATUS      1 OPTIMAL

**** OBJECTIVE VALUE                5.0000

 RESOURCE USAGE, LIMIT          0.050     1000.000

 ITERATION COUNT, LIMIT         4        10000

GAMS/XA       Aug  7, 2000 WIN.XA.XA 19.4 008.015.038.WAT

Memory estimate (computed): 1.06MB

   Copyright (c) 1993,94,95,96,97,98,99 by SUNSET SOFTWARE TECHNOLOGY.

   1613 Chelsea Road,  Suite 153

   San Marino, California  91108   U.S.A.

   All Rights Reserved Worldwide.

   Telephone 626-441-1565   FAX 626-441-1567

   EMAIL:    [email protected]

             http://www.sunsetsoft.com

Licensed Solely To: GAMS DEVELOPMENT CORPORATION - 934001

                    WASHINGTON, DC

STATISTICS - gams Wed Oct 27 12:42:03 2004

  xa VERSION 12.00 NT DLL    USABLE MEMORY 1062K BYTES

  ENV ID 1 SOLVE NUMBER 1

  VARIABLES 7

     0 LOWER, 0 FIXED, 6 UPPER, 1 FREE, 0 RANGED, 6/0 INTEGER

  CONSTRAINTS 3

     0 GE, 1 EQ, 1 LE, 1 NULL/FREE, 0 RANGED.

     14 NON-ZEROS WORK 90,355

  MAXIMIZATION.  STRATEGY 1, NODES: 7/7

Integer solution proven optimal.

MIP solution  :          5.000000

Best possible :          5.000000

Absolute gap  :          0.000000     optca :          0.000000

Relative gap  :          0.000000     optcr :          0.100000

                       LOWER     LEVEL     UPPER    MARGINAL

---- EQU q1             -INF      9.000     9.000     0.500

---- EQU q2              .         .         .       -1.000

  q1

  q2  funcao objetivo

GAMS Rev 116  Windows NT/95/98                    10/27/04 12:42:03  PAGE      7

o problema da mochila Subset-Sum Problem  pag 215

                       LOWER     LEVEL     UPPER    MARGINAL

---- VAR x1              .        1.000     1.000     0.500

---- VAR x2              .        1.000     1.000     0.500

---- VAR x3              .         .        1.000      .

---- VAR x4              .        1.000     1.000    -0.500

---- VAR x5              .         .        1.000    -1.000

---- VAR x6              .         .        1.000    -2.000

---- VAR z              -INF      5.000     +INF       .

  x1

  x2

  x3

  x4

  x5

  x6

  z  funcao objeto

**** REPORT SUMMARY :        0     NONOPT

                             0 INFEASIBLE

                             0  UNBOUNDED

EXECUTION TIME       =        0.010 SECONDS    0.7 Mb      WIN194-116

USER: Joao Inacio Soletti                            G000920:1631AP-WIN

      Universidade Federal de Alagoas, Departamento de EngenhariaDC2982

**** FILE SUMMARY

INPUT      C:\DOCUMENTS AND SETTINGS\CONVIDADO\MEUS DOCUMENTOS\ALLAN\GAMS\PROBLE

           MA MOCHILA PAG215.GMS

OUTPUT     C:\WINDOWS\GAMSDIR\PROBLEMA MOCHILA PAG215.LST