linear programming minimization

[formosan]

Here's a problem that ought to be straightforward.

 

I want to minimize 40x1+30x2

 

 

I even know the answer. The optimum is x1=30, x2=0.

 

The constraints are:

.4x1+.3x2>=8

.2x1+.45x2>=6

.3x1+.1x2>=7

.1x1+.05x2>=3

 

 

Now, of course, the two-phase approach would seem to work. I.e. first try to minimize four slack variables, one for each constraint, until you get a feasible solution -- then optimize the feasible solution.

 

Well ... I tried plugging this into an applet that uses the two-phase approach and it does the first phase in four iterations! But they don't make sense!

 

The applet is here:

http://neos.mcs.anl.gov/CaseStudies/simplex/applet/SimplexTool.html

 

And the iterations go like this:

 

x1 enters, x7 is leaving Basic variable;

x2 enters, x8 is LBV

x3 enters, x9 is LBV

x5 enters, x10 is LBV

 

at that point, x1=30 and the solution is feasible.

 

But *why* is x1 chosen as the entering basic variable at the beginning? It seems to make no sense to me. Normally the EBV has a nonzero coefficient in the objective function. x1 has a zero coefficient in the objective function at the start of the two-phase method...

 

 

Edit:

At the very first iteration, the applet calculates "reduced costs." Normally I thought "reduced costs" were found by looking at the objective function. The applet seems to do it by adding up coefficients, which doesn't match anything I can find in my textbooks....

---

Merged post follows:

Consecutive posts merged

I think the program must be selecting entering variables arbitrarily.

 

Several books, including Hillier and Lieberman, say that entering variables can be chosen arbitrarily if there is a tie.

---

Merged post follows:

Consecutive posts merged

Several books, including Hillier and Lieberman, say that entering variables can be chosen arbitrarily if there is a tie.

 

Looking at my other text, Belegundu and Chandrupatla, it looks like this is not arbitrary.

 

in fact, it looks like the matrix gets initialized with four 1's in the obj fcn row.

 

Then the lower four rows are all subtracted from the upper row.

 

This leaves -1 and -0.9 in the first two columns of the first row, which explains why x1 is the first entering basic variable!