help-glpk
[Top][All Lists]

## Re: [Help-glpk] two fases

 From: Andrew Makhorin Subject: Re: [Help-glpk] two fases Date: Thu, 26 Jan 2006 03:00:00 +0300

```> I am working with the following problem :
>
> MAX  Z=x1+6x2-7x3+x4+5x5
>
> Subjecto to
>
> 5x1-4x2+13x3-2x4+x5=20
> x1-x2+5x3-x4+x5=8
>
> the obtained result when I put the problem in GLPK is:
>
> PROBLEM HAS UNBOUNDED SOLUTION

This means that your instance has no finite maximum.

Maximize
Z:x1+6x2-7x3+x4+5x5

Subject to
e1:5x1-4x2+13x3-2x4+x5=20
e2:x1-x2+5x3-x4+x5=8

End

Problem:
Rows:       2
Columns:    5
Non-zeros:  10
Status:     UNBOUNDED
Objective:  Z = 28 (MAXimum)

No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 e1           NS            20            20             =            -1
2 e2           NS             8             8             =             6

No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x1           B              3             0
2 x2           NL             0             0                           8
3 x3           NL             0             0                         -24
4 x4           NL             0             0                           5
5 x5           B              5             0

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 5.00e-16 on row 2
max.rel.err. = 1.92e-16 on row 2
High quality

KKT.PB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality

KKT.DE: max.abs.err. = 1.15e-14 on column 1
max.rel.err. = 3.20e-15 on column 1
High quality

KKT.DB: max.abs.err. = 2.60e+01 on column 2
max.rel.err. = 1.03e+00 on column 2
DUAL SOLUTION IS INFEASIBLE

Unbounded ray: column 2

End of output

A feasible basic solution found by glpsol is:
x1 = 3, x2 = 0, x3 = 0, x4 = 0, x5 = 5

However, variable x2 having positive reduced cost can infinitely
increase, that leads to infinitely increasing the objective function.

>
> That was necessary to work with the method of two phases. GLPK has
> the option to work with this method ?????
>
> That the ideal solution of the problem is : x3=12/7   x2=4/7 all
> other xj=0 z=-60/7   but I not as obtaining this response using GLPK.
>
> That I can do to obtain the ideal solution ?????????????

Can you explain what is ideal solution?

```