> restart;                                                                                           
> with(simplex):
Warning, the protected names maximize and minimize have been redefined and unprotected
> consts := {x4 = -319+20*x1+35*x2+95*x3};
                                               consts := {x4 = -319 + 20 x1 + 35 x2 + 95 x3}

> dic := {z=-5*x1-9*x2-23*x3} union consts:                                   
> maximize(-5*x1-9*x2-23*x3, consts, NONNEGATIVE);                            
                                                                                  319
                                                    {x4 = 0, x2 = 0, x1 = 0, x3 = ---}
                                                                                  95

> solve(dic,{z,x3});
                                           x4    319   4 x1   7 x2        23 x4   7337   10 x2   3 x1
                                    {x3 = ---- + --- - ---- - ----, z = - ----- - ---- - ----- - ----}
                                           95    95     19     19          95      95     19      19

# Add the cut of the 'z' row with slack variable x5

> consts := consts union {x5 = 23*x4/95 +10*x2/19+3*x1/19 -73/95};
                                                                                  23 x4   10 x2   3 x1   73
                               consts := {x4 = -319 + 20 x1 + 35 x2 + 95 x3, x5 = ----- + ----- + ---- - --}
                                                                                   95      19      19    95

> dic := {z=-5*x1-9*x2-23*x3} union consts:                                   
> maximize(-5*x1-9*x2-23*x3, consts, NONNEGATIVE);                            
                                                                                        73
                                                {x4 = 0, x2 = 0, x5 = 0, x3 = 7/3, x1 = --}
                                                                                        15

> solve(dic,{z,x1,x3});
                                    4 x5          x4     x2          23 x4   73   10 x2   19 x5
                            {x3 = - ---- + 7/3 + ---- + ----, x1 = - ----- + -- - ----- + -----, z = -78 - x5}
                                     3            3      3            15     15     3       3

# Add the cut on the x3 row with slack variable x6 and add the cut on the x1 row with slack variable x7

> consts := consts union {x6 = -1/3 + x5/3 + 2*x4/3 + 2*x2/3, x7 = -13/15 + 8*x4/15 + x2/3 + 2*x5/3};
consts :=

                                             23 x4   10 x2   3 x1   73                x5    2 x4   2 x2         13   8 x4    x2    2 x5
    {x4 = -319 + 20 x1 + 35 x2 + 95 x3, x5 = ----- + ----- + ---- - --, x6 = - 1/3 + ---- + ---- + ----, x7 = - -- + ---- + ---- + ----}
                                              95      19      19    95                3      3      3           15    15     3      3

> dic := {z=-5*x1-9*x2-23*x3} union consts:                                                          
> maximize(-5*x1-9*x2-23*x3, consts, NONNEGATIVE);                                                   
                                    {x2 = 0, x5 = 0, x7 = 0, x4 = 13/8, x3 = 23/8, x1 = 19/8, x6 = 3/4}

> solve(dic,{z,x1,x3,x4,x6});                                                                        
bytes used=4000064, alloc=3210676, time=0.36
                    33 x5          19 x2   23 x7               x2    7 x5   5 x7       15 x7          5 x2   5 x5
{z = -x5 - 78, x1 = ----- + 19/8 - ----- - -----, x3 = 23/8 + ---- - ---- + ----, x4 = ----- + 13/8 - ---- - ----,
                      4              8       8                 8      4      8           8             8      4

         5 x7          x2     x5
    x6 = ---- + 3/4 + ---- - ----}
          4            4      2



# Add the cut on the x1 row with slack variable x8 and add the cut on the x3 row with slack variable x9


> consts := consts union {x8 = -3/8 + 3*x2/8 + 3*x5/4 + 7*x7/8, x9 = -7/8 + 7*x2/8 + 3*x5/4 + 3*x7/8};
                                                           3 x2   3 x5   7 x7               7 x2   3 x5   3 x7
consts := {x4 = -319 + 20 x1 + 35 x2 + 95 x3, x8 = - 3/8 + ---- + ---- + ----, x9 = - 7/8 + ---- + ---- + ----,
                                                            8      4      8                  8      4      8

         23 x4   10 x2   3 x1   73                x5    2 x4   2 x2         13   8 x4    x2    2 x5
    x5 = ----- + ----- + ---- - --, x6 = - 1/3 + ---- + ---- + ----, x7 = - -- + ---- + ---- + ----}
          95      19      19    95                3      3      3           15    15     3      3

> dic := {z=-5*x1-9*x2-23*x3} union consts:                                                           
> maximize(-5*x1-9*x2-23*x3, consts, NONNEGATIVE);                                                    
                                 {x9 = 0, x1 = 0, x5 = 0, x8 = 0, x2 = 1, x4 = 1, x6 = 1, x3 = 3, x7 = 0}


                                                                      
# We have integrality, our optimal solution is 78 with (x1,x2,x3) = (0,1,3), our final dictionary is below:

> solve(dic,{z,x2,x3,x4,x6,x8,x9});
                    72 x5   13 x7   7 x1       66 x5   23 x7   8 x1             2 x1       7 x5   18 x7            x1    25 x5   9 x7
{z = -x5 - 78, x9 = ----- - ----- - ----, x2 = ----- - ----- - ---- + 1, x6 = - ---- + 1 + ---- + -----, x3 = 3 - ---- - ----- + ----,
                     19      19      19         19      19      19               19         19     19              19     19      19

         39 x5   3 x1   8 x7       50 x7       65 x5   5 x1
    x8 = ----- - ---- + ----, x4 = ----- + 1 - ----- + ----}
          19      19     19         19          19      19