Operation research-1:

Hello everybody hopefull,you are very well and healthy.Today we will examine simplex algorithm and how this method contribute our optimal solution.

The simplex Algorithm and goal programming

Definiton of simplex algorithm:the simplex algorithm is used to solve LPs with thousands of constraints and variables.LINDO and LINGO will be used.

Example1):Leather Limited manufactures two types of belts: the deluxe model and the regular model. Each type requires 1 sq yd of leather. A regular belt requires 1 hour of skilled labor, and a deluxe belt requires 2 hours. Each week, 40 sq yd of leather and 60 hours of skilled labor are available. Each regular belt contributes $3 to profit and each deluxe belt, $4. If we define.

Solution:This question already given profit each belt model so,we can compute maximization.Max=4x1+4x2

solution1.2:This question already given a weekly required this reason,we can find descison variables. x1=number of deluxe belts produced weekly.X2=number of regular belts produced weekly.

solution1.3 :Each type requires 1 sq yd of leather.Each week, 40 sq yd of leather.

x1 +x2 <-40(Leather constraint)

solution1.4:A regular belt requires 1 hour of skilled labor,deluxe belt requires 2 hours of skilled labor.

2x1+x2<-60(labor constraint)

x1,x2,…..>-0 always!(sign restriction)

slack variable:which is the amount of the resource unused in the ith constraint.

s1= 40-x1 -x2 OR x1+x2+s1=40

s2=60–2x1-x2 OR 2x1+x2=60

Observe that a point (x1, x2) satisfies the ith constraint if and only if si 0>-

EX:x1=15,x2=20 40–15–20=5>-0 (15,20) for that we can use leather constraint and 5 sql is so leather are unused.

Ex2)= 60–2.(15)-20=10>-0 (15,20) for that we can use labor constraint and 10 sql so labor are unused.

This converts LP 1to =

max z=4x1+3x2

st.x1+x2+s1=40

2x1+x2+s2=60

x1,x2,s1,s2>-0 always!

excess variable:(sometimes called a surplus variable)

min z 50x1 + 20x2 + 30x3 + 80x4 s.t. 400x1  200x2  150x3  500x4 >-500 (Calorie constraint) (3) s.t. 3x1+ 2x2>- 6 (Chocolate constraint) (4) s.t. 2x1 + 2x2 + 4x3 + 4x4 >-10 (Sugar constraint) (5) s.t. 2x1 + 4x2 + x3 + 5x4>- 8 (Fat constraint) (6) x1, x2, x3, x4>- 0

e1:400x1+200x2+150x3+500x4–500 OR 500=400x1+200x2+150x3+500x4-e1

e2=3x1+2x2–6 OR 6=3x1+2x2-e2

e3=2x1+2x2+4x3–10 OR 10=2x1+2x2+4x3-e3

e4=2x1+4x2+x3+5x4–8 OR 8=2x1+4x2+x3+5x4-e4

xi,ei>-0 (i=1,2,3,4)

Basic and Nonbasic Variables:A basic solution to Ax b is obtained by setting n  m variables equal to 0 and solving for the values of the remaining m variables. This assumes that setting the n  m variables equal to 0 yields unique values for the remaining m variables or, equivalently, the columns for the remaining m variables are linearly independent.

Feasible Solutions:Any basic solution to (7) in which all variables are nonnegative is a basic feasible solution.