Thursday, October 19, 2006

An LP problem asked in the comment

This is the only problem where it looked to me that the student has tried something from his side also. The question is as follows

min z=y1+y2
s.t
2y1+4y2>=4
y1+7y2>=7
y1,y2>=0
in simplex method.........solution........
max z*=-y1-y2
2y1+4y2-s1+a1=4
y1+7y2-s2+a2=7
y1,y2>=0
now.........z*+y1+y2=0
2y1+4y2-s1+a1=4
y1+7y2-s2+a2=7
y1,y2>=0
now here o.f line is positive so we apply M method(or due to artificial var.)then what is the next process i only want first iteration then after that i solve it.......

Before going further read the post titled "About Artificial Variables in Linear Programming (LP)" on this blog.

Artificial variables are needed to get the initial basic variables from the constraints of >= and = type. It will help to recall the properties of basic variables to understand the reason behind this.
To ensure that the artificial variables don't enter the basis after leaving, you have to associate a high penalty M in the o.f.

The revised O.f. is
max z* = -y1-y2. In maximization problem, high penalty means high negative coefficient of the variable.
so the o.f should be max z* = -y1-y2-Ma1-Ma2
Now, since a1 and a2 are to be in the initial basis, their co-efficients ahould be 0. To get this substitute
a1 = 4-2y1-4y2+s1 and a2 = 7-y1-7y2+s2 in this o.f. You can notice that these values of a1 and a2 have been taken from the two constraints where these variables were introduced.
So the o.f is max z* = -y1-y2-4M+2My1+4My2-Ms1-7M+My1+7My2-Ms2
= (3M-1)y1+ (11M-1)y2-Ms1-Ms2-11M
So now you have z*-(3M-1)y1-(11M-1)y2+Ms1+Ms2 = 11M

I hope, you can solve from here. You have to write the initial basic feasible solution table and do the simplex iterations. You can see that the most negative coefficient in the above o.f.line is for y2.

1 Comments:

Anonymous Anonymous said...

dialogical http://www.kindel.com/members/Vacuum-Cleaners.aspx coaxial http://www.kindel.com/members/Annuity-Calculator.aspx perlman http://www.kindel.com/members/Bariatric-Surgery.aspx crystallize http://www.kindel.com/members/Electric-Blankets.aspx fergal http://cciworldwide.org/members/Furnace-Filters.aspx khalidi http://cciworldwide.org/members/Vending-Machines.aspx disinfection http://cciworldwide.org/members/Kitchen-Cabinets.aspx illegitimacy http://cciworldwide.org/members/Slipcovers.aspx valorized http://cciworldwide.org/members/Polar-Heart-Rate-Monitors.aspx surrounds http://cciworldwide.org/members/Popcorn-Machines.aspx mayo http://cciworldwide.org/members/Garage-Door-Openers.aspx laborers http://cciworldwide.org/members/Area-Rugs.aspx smallpox http://cciworldwide.org/members/Omeprazole.aspx whitworth http://cciworldwide.org/members/Vacuum-Cleaners.aspx recyclables http://cciworldwide.org/members/Annuity-Calculator.aspx japanjo

12:05 AM  

Post a Comment

<< Home