Working on Linear Programming Problems - Operations Management Help

Problem 1: Consider adding a constraint to a linear program of the form $\frac{1}{100}{{x}^{2}}+5x-3\ge 0$

where you may assume that other constraints force 0 ≤ x ≤ 5. You cannot add the constraint as given (Why?) in LINDO so what should you do (using UNDO)? Make suggestions and comment.

Solution: The reason why we cannot add the restriction

\[\frac{1}{100}{{x}^{2}}+5x-3\ge 0\]

is because LINDO complains that a “variable is missing”. This is a consequence of the way that LINDO parses the equations: it expects to see all the variables on the left hand side, and the constant alone on the right hand side. So, when LINDO finds the term “-3”, it wonders where is the variable that should go with that constant.

We offer quality and prompt Operations Management Homework Help

We can help you with any kind of Operations Management assignments, homeworks, tests, exams, at any level

Including topics such as Forecasting, PERT, Aggregate Planning, Waiting Lines, Network Problems, Linear Programming and Transportation Problems, Inventory, Quality Control and much more.

E-mail your OM Problems for a free quote

The way to fix it is simple: First of all, if we graph the function

\[f\left( x \right)=\frac{1}{100}{{x}^{2}}+5x-3\]

we get

The roots are x = -500.599 and x = 0.599282. The condition

\[\frac{1}{100}{{x}^{2}}+5x-3\ge 0\]

is satisfied if $x\in (-\infty ,-500.599]\cup [0.599282,\infty ) $. But since also we know that $x\in [0,5] $, the condition becomes $x\in \left[ 0.599282,\,\,5 \right] $, so we can simply add the condition

\[x\ge 0.599282\]

Problem 2: (Piecewise Linear Functions) Consider the hiring/firing model. Indicate how to add the constraint that you can fire as many workers as you want in a month but the cost increases with a cost of $420 for first 10, $600 for next 20 and $2000 for any workers beyond 30 in a given month. Add this to the existing model and solve (both obtaining a fractional solution and also the integer solution and then comparing the two objective functions).

Solution: For the original problem, we get the following output from LINDO:

LP OPTIMUM FOUND AT STEP 48

OBJECTIVE FUNCTION VALUE

1) 157066.7

VARIABLE VALUE REDUCED COST

Y1 0.000000 20.000000

Y2 0.000000 20.000000

Y3 0.000000 20.000000

Y4 0.000000 43.333332

Y5 0.000000 35.333332

Y6 0.000000 27.333334

Y7 0.000000 19.333334

Y8 0.000000 11.333333

Y9 0.000000 3.333333

Y10 583.333313 0.000000

Y11 400.000000 0.000000

Y12 0.000000 61.000000

Z1 0.000000 8.000000

Z2 0.000000 8.000000

Z3 0.000000 31.333334

Z4 1216.666626 0.000000

Z5 1133.333374 0.000000

Z6 1150.000000 0.000000

Z7 766.666687 0.000000

Z8 83.333336 0.000000

Z9 0.000000 4.666667

Z10 0.000000 8.000000

Z11 0.000000 69.000000

Z12 0.000000 0.000000

T1 10500.000000 0.000000

T2 4200.000000 0.000000

T3 14700.000000 0.000000

T4 8050.000000 0.000000

T5 0.000000 0.844444

T6 12000.000000 0.000000

T7 12000.000000 0.000000

T8 12000.000000 0.000000

T9 12000.000000 0.000000

T10 0.000000 0.952381

T11 350.000000 0.000000

T12 16800.000000 0.000000

Z0 0.000000 0.000000

X1 265.000000 0.000000

X2 255.000000 0.000000

X3 220.000000 0.000000

X4 200.833328 0.000000

X5 200.833328 0.000000

X6 240.833328 0.000000

X7 280.833344 0.000000

X8 320.833344 0.000000

X9 360.833344 0.000000

X10 360.833344 0.000000

X11 360.000000 0.000000

X12 320.000000 0.000000

X0 290.000000 0.000000

Now we have to handle the different cost for the different volumes of employees fired. First of all, we need to get rid of the restrictions in the number of people fired per month. Secondly, we need to add the restrictions

\[\begin{array}{cc} & 420\left( {{x}_{i}}-{{x}_{i+1}} \right)+180\left( {{x}_{i}}-{{x}_{i+1}}-10 \right)-{{t}_{i}}\le 0 \\ & 420\left( {{x}_{i}}-{{x}_{i+1}} \right)+180\left( {{x}_{i}}-{{x}_{i+1}}-10 \right)+1400\left( {{x}_{i}}-{{x}_{i+i}}-30 \right)-{{t}_{i}}\le 0 \\ \end{array}\]

or equivalently

\[\begin{array}{cc} & 600\left( {{x}_{i}}-{{x}_{i+1}} \right)-{{t}_{i}}\le 1,800 \\ & 2,000\left( {{x}_{i}}-{{x}_{i+1}} \right)-{{t}_{i}}\le 43,800 \\ \end{array}\]

for all $i = 1,2,...,12$. This means that the LINDO code is now:

min 20y1+20y2+20y3+20y4+20y5+20y6+20y7+20y8+20y9+20y10+20y11+20y12
+8z1+8z2+8z3+8z4+8z5+8z6+8z7+8z8+8z9+8z10+8z11+8z12
+t1+t2+t3+t4+t5+t6+t7+t8+t9+t10+t11+t12
st
z0=0
m1)20x1+y1+z0-z1=5300
m2)20x2+y2+z1-z2=5100
m3)20x3+y3+z2-z3=4400
m4)20x4+y4+z3-z4=2800
m5)20x5+y5+z4-z5=4100
m6)20x6+y6+z5-z6=4800
m7)20x7+y7+z6-z7=6000
m8)20x8+y8+z7-z8=7100
m9)20x9+y9+z8-z9=7300
m10)20x10+y10+z9-z10=7800
m11)20x11+y11+z10-z11=7600
m12)20x12+y12+z11-z12=6400
z12=0
x0=290
y1-6x1<0
y2-6x2<0
y3-6x3<0
y4-6x4<0
y5-6x5<0
y6-6x6<0
y7-6x7<0
y8-6x8<0
y9-6x9<0
y10-6x10<0
y11-6x11<0
y12-6x12<0
x1-x0<40
x2-x1<40
x3-x2<40
x4-x3<40
x5-x4<40
x6-x5<40
x7-x6<40
x8-x7<40
x9-x8<40
x10-x9<40
x11-x10<40
x12-x11<40
300x1-300x0-t1<0
300x2-300x1-t2<0
300x3-300x2-t3<0
300x4-300x3-t4<0
300x5-300x4-t5<0
300x6-300x5-t6<0
300x7-300x6-t7<0
300x8-300x7-t8<0
300x9-300x8-t9<0
300x10-300x9-t10<0
300x11-300x10-t11<0
300x12-300x11-t12<0
420x0-420x1-t1<0
420x1-420x2-t2<0
420x2-420x3-t3<0
420x3-420x4-t4<0
420x4-420x5-t5<0
420x5-420x6-t6<0
420x6-420x7-t7<0
420x7-420x8-t8<0
420x8-420x9-t9<0
420x9-420x10-t10<0
420x10-420x11-t11<0
420x11-420x12-t12<0
600x0-600x1-t1<1800
600x1-600x2-t2<1800
600x2-600x3-t3<1800
600x3-600x4-t4<1800
600x4-600x5-t5<1800
600x5-600x6-t6<1800
600x6-600x7-t7<1800
600x7-600x8-t8<1800
600x8-600x9-t9<1800
600x9-600x10-t10<1800
600x10-600x11-t11<1800
600x11-600x12-t12<1800
2000x0-2000x1-t1<43800
2000x1-2000x2-t2<43800
2000x2-2000x3-t3<43800
2000x3-2000x4-t4<43800
2000x4-2000x5-t5<43800
2000x5-2000x6-t6<43800
2000x6-2000x7-t7<43800
2000x7-2000x8-t8<43800
2000x8-2000x9-t9<43800
2000x9-2000x10-t10<43800
2000x10-2000x11-t11<43800
2000x11-2000x12-t12<43800

end

We get the following output from LINDO

LP OPTIMUM FOUND AT STEP 48

OBJECTIVE FUNCTION VALUE

1) 173400.0

VARIABLE VALUE REDUCED COST

Y1 0.000000 20.000000

Y2 0.000000 12.000000

Y3 0.000000 33.000000

Y4 0.000000 44.000000

Y5 0.000000 36.000000

Y6 0.000000 28.000000

Y7 0.000000 20.000000

Y8 0.000000 12.000000

Y9 0.000000 4.000000

Y10 800.000000 0.000000

Y11 600.000000 0.000000

Y12 0.000000 61.000000

Z1 100.000000 0.000000

Z2 0.000000 29.000000

Z3 0.000000 19.000000

Z4 1400.000000 0.000000

Z5 1500.000000 0.000000

Z6 1466.666626 0.000000

Z7 1033.333374 0.000000

Z8 300.000000 0.000000

Z9 0.000000 4.000000

Z10 0.000000 8.000000

Z11 0.000000 69.000000

Z12 0.000000 0.000000

T1 10200.000000 0.000000

T2 10200.000000 0.000000

T3 16200.000000 0.000000

T4 4200.000000 0.000000

T5 0.000000 0.952381

T6 8500.000000 0.000000

T7 12000.000000 0.000000

T8 12000.000000 0.000000

T9 9500.000000 0.000000

T10 0.000000 0.952381

T11 0.000000 0.000000

T12 16200.000000 0.000000

Z0 0.000000 0.000000

X1 270.000000 0.000000

X2 250.000000 0.000000

X3 220.000000 0.000000

X4 210.000000 0.000000

X5 210.000000 0.000000

X6 238.333328 0.000000

X7 278.333344 0.000000

X8 318.333344 0.000000

X9 350.000000 0.000000

X10 350.000000 0.000000

X11 350.000000 0.000000

X12 320.000000 0.000000

X0 290.000000 0.000000

Based on these results, the objective function increased from $157,066.7 (with the restriction in the number of employees fired per month) to $173,400 (without the restriction, but with more expensive firing costs).

Problem 3: (Branch and Bound) Use our branch and bound procedure to solve the following LP where

LP = max 3x1 +6x2 +25x3 +60x4 = z .

24x1 +76x2 +43x3 +754x4 < 860 - n

755x1 +27x2 +33x3 +67x4 < 860 - n

x1 < 1
x2< 1
x3<1
x4< 1

where n is the number formed from the last two digits of your student number.

Consider the ILP (Integer Linear Program) obtained from the above LP by adding the constraints that all the variables are 0 or 1. Use Branch and Bound to solve. You may make your own choices which variables to branch on. Record for each LP solved the value for z, the solution and as well as the extra constraints you have added to the LP which determine the current LP. Obtain a Branch and Bound tree as given in the handout with the actual solutions recorded.

Now obtain a solution to the ILP above by using LINDO with the GIN command (INT will also work). Obviously the final answer, at least its z values should agree with what you obtained by using Branch and Bound. Record number of iterations. You might also try to figure out what LINDO is doing (it appears to be our branch and bound with something else I don't understand!).

Solution: My last two digits are n = 54. Therefore, we need to solve the problem:

\[\begin{array}{cc} & Maximize\,\,\,\,3{{x}_{1}}+6{{x}_{2}}+25{{x}_{3}}+60{{x}_{4}} \\ & s.t.\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,24{{x}_{1}}+76{{x}_{2}}+43{{x}_{3}}+754{{x}_{4}}\le 806 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,755{{x}_{1}}+27{{x}_{2}}+33{{x}_{3}}+67{{x}_{4}}\le 806 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{1}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{2}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{3}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{4}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{i}}\ge 0 \\ \end{array}\]

Using LINDO, we get the following results:

Now we add the integer restriction: ${{x}_{i}}\in \{0,1\}$. This restriction converts the problem into:

\[\begin{array}{cc} & Maximize\,\,\,\,3{{x}_{1}}+6{{x}_{2}}+25{{x}_{3}}+60{{x}_{4}} \\ & s.t.\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,24{{x}_{1}}+76{{x}_{2}}+43{{x}_{3}}+754{{x}_{4}}\le 806 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,755{{x}_{1}}+27{{x}_{2}}+33{{x}_{3}}+67{{x}_{4}}\le 806 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{1}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{2}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{3}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{4}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{i}}\in \{0,1\} \\ \end{array}\]

Using LINDO, we solve this ILP, and we obtain the following results:

Now we use Branch and Bound: We first need to replace by

\[\begin{array}{cc} & Minimize\,\,\,-\,3{{x}_{1}}-6{{x}_{2}}-25{{x}_{3}}-60{{x}_{4}} \\ & s.t.\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,24{{x}_{1}}+76{{x}_{2}}+43{{x}_{3}}+754{{x}_{4}}\le 806 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,755{{x}_{1}}+27{{x}_{2}}+33{{x}_{3}}+67{{x}_{4}}\le 806 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{1}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{2}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{3}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{4}}\le 1 \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{x}_{i}}\in \{0,1\} \\ \end{array}\]

The tree is shown below:

Our experts can help YOU with your Operations Management Homework. Get your FREE Quote. Learn about our satisfaction guaranteed policy: If you're not satisfied, we'll refund you. Please see our terms of service for more information about this policy.