perplexing simplex

[Chris Chiasson]

Hello sci.math.num-analysis members,

First, this is a homework problem, so if you don't want to help me
with homework - uh... forget what I just told you and continue
reading.

Here is a Linear Programming problem I am trying to solve:

F=2*X1+4*X2
2*X1+X2>=2
X1>=0
X2>=0

A computer algebra system can easily give me the answer (1,0) and even
create a nice contour plot showing the boundaries and optimum.

http://chris.chiasson.name/Engineering_Optimization/hw4/mout/p4-3_plot_pt1.png

What it can't do is tell me how to apply the simplex method to the
tableau associated with the above problem:

{{2,1,-1,2},
{2,4,0,F}}

I can't see where I would be able to create a basis of two variables if
I only have one (non sign) constraint. I have solved all the other
linear programming problems thrown at me so far (not many, to be sure),
but this one leaves me scratching my head. I have tried augmenting the
tableau with extra variables and also tried expressing the sign
constraints in the tableau, but both avenues didn't yield an answer.

Will someone please explain what is happening in this problem and how
one should apply the simplex method in this case?

Thank you,

[Chris Chiasson]

[Julian V. Noble]

I suggest you look at

http://galileo.phys.virginia.edu/classes/551.jvn.fall01/Notes/optimization.pdf

Section 4 is a quick-and-dirty discussion of the simplex method in
linear programming.

--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia

[Chris Chiasson]

Dr. Noble,

Thank you for the link. I was not able to find where it shows how to
deal with one constraint and two independant variables. I have a
feeling that the problem I am attempting to solve _really is just like
the others_ I have solved. However, I fail to see how to apply the
techniques I've already learned in doing the following problems on my
own to the one I'm working on now:

http://chris.chiasson.name/Engineering_Optimization/ch04.html

and the first two problems of

http://chris.chiasson.name/Engineering_Optimization/ch06.html

Thanks again,

[Peter Spellucci]

In article <1147193906.1...@v46g2000cwv.googlegroups.com>,

"Chris Chiasson" <chris.c...@gmail.com> writes:
>Hello sci.math.num-analysis members,
>
>First, this is a homework problem, so if you don't want to help me
> with homework - uh... forget what I just told you and continue
>reading.
>
>Here is a Linear Programming problem I am trying to solve:
>
>F=2*X1+4*X2
>2*X1+X2>=2
>X1>=0
> X2>=0
>
>A computer algebra system can easily give me the answer (1,0) and even
>create a nice contour plot showing the boundaries and optimum.
>
>http://chris.chiasson.name/Engineering_Optimization/hw4/mout/p4-3_plot_pt1.png
>
>What it can't do is tell me how to apply the simplex method to the
>tableau associated with the above problem:
>
>{{2,1,-1,2},
>{2,4,0,F}}
>
>I can't see where I would be able to create a basis of two variables if
> I only have one (non sign) constraint. I have solved all the other
>linear programming problems thrown at me so far (not many, to be sure),

>but this one leaves me scratching my head. I have tried ...

(something went wrong with xrn here )
I wonder why you insist to construct a basis of dimension 2 then there is
only one row in the constraint matrix
hth
peter

[Chris Chiasson]

Peter,

Thank you. I had a misconception that there should be as many variables
in the basis as there are independant variables. Apparently, this is
not the case.

Here are my tableaus:

{2, 1, -1, 2}
{2, 4, 0, F}

{2, 1, -1, 1, 2}
{2, 4, 0, 0, F}
{0, 0, 0, 1, w}

{2, 1, -1, 1, 2}
{2, 4, 0, 0, F}
{-2, -1, 1, 0, -2 + w}

{1, 1/2, -(1/2), 1/2, 1}
{0, 3, 1, -1, -2 + F}
{0, 0, 0, 1, w}

{1, 1/2, -(1/2), 1}
{0, 3, 1, -2 + F}

This gives the answer (1,0) with the minimum being 2.

Thanks again,