# linear programming problem

• Jul 30th 2007, 02:09 PM
lillian
linear programming problem
Consider the linear programming problem below:

Max 3A + 2B
s.t.
1A + 1B is less than or equal to 10
3A + 1B is less than or equal to 24
1A + 2B is less than or equal to 16
A, B is greater than or equal to 0

a. Use Management Scientist to solve the problem.

b. If the objective function coefficient for A changes from 3 to 5, does the optimal solution changes? why?

c. If the objective function coefficient for A remains 3, but the objective function coefficient for B varies from 2 to 4, does the optimal solution changes? why?

• Jul 31st 2007, 07:02 AM
earboth
Quote:

Originally Posted by lillian
Consider the linear programming problem below:
Max 3A + 2B
s.t.
1A + 1B is less than or equal to 10
3A + 1B is less than or equal to 24
1A + 2B is less than or equal to 16
A, B is greater than or equal to 0

a. Use Management Scientist to solve the problem.
b. If the objective function coefficient for A changes from 3 to 5, does the optimal solution changes? why?
c. If the objective function coefficient for A remains 3, but the objective function coefficient for B varies from 2 to 4, does the optimal solution changes? why?

Hello,

to a). I don't know a Management Scientist but I can give you a solution.

I use x for your A and I use y for your B.

1A + 1B is less than or equal to 10: $\displaystyle x+y\leq 10~\Longrightarrow \boxed{y\leq -x+10}$
3A + 1B is less than or equal to 24: $\displaystyle 3x+y\leq 24~\Longrightarrow \boxed{y\leq -3x+24}$
1A + 2B is less than or equal to 16: $\displaystyle x+2y\leq 16~\Longrightarrow \boxed{y\leq -\frac{1}{2}x+8}$
A, B is greater than or equal to 0: $\displaystyle x\geq 0~\wedge~y\geq 0$

I sketched the 3 straight lines which are the borders of the half-planes. You get an irregular pentagon (hmm... don't forget we are talking about math). The graph of the objective function must pass at least through one point of this pentagon.

Max = 3A + 2B: $\displaystyle y = -\frac{3}{2}x+\frac{Max}{2}$. That means the y-intercept is $\displaystyle \frac{Max}{2}$. The larger the y-intercept the larger is Max. If the graph of the objective function passes through B(7, 3) then the y-intercept will be the largest.
Calculate the equation of the obj. function (sketched in red):
$\displaystyle B(7,3) \in y = -\frac{3}{2}x+c~\Longrightarrow~ 3= -\frac{3}{2}\cdot 7+c ~\Longrightarrow c = 11.5$. Therefore $\displaystyle \frac{Max}{2} = 11.5~\Longrightarrow~Max = 23$.

to b).
Max = 5A + 2B: $\displaystyle y = -\frac{5}{2}x+\frac{Max}{2}$. That means the y-intercept is $\displaystyle \frac{Max}{2}$. The larger the y-intercept the larger is Max. If the graph of the objective function passes through B(7, 3) then the y-intercept will be the largest.
Calculate the equation of the obj. function (sketched in green):
$\displaystyle B(7,3) \in y = -\frac{5}{2}x+c~\Longrightarrow~ 3= -\frac{5}{2}\cdot 7+c ~\Longrightarrow c = 20.5$. Therefore $\displaystyle \frac{Max}{2} = 20.5~\Longrightarrow~Max = 41$.

to c).
Max = 3A + 4B: $\displaystyle y = -\frac{3}{4}x+\frac{Max}{4}$. That means the y-intercept is $\displaystyle \frac{Max}{4}$. The larger the y-intercept the larger is Max. If the graph of the objective function passes through A(4, 3) then the y-intercept will be the largest.
Calculate the equation of the obj. function (sketched in blue):
$\displaystyle B(4, 6) \in y = -\frac{3}{4}x+c~\Longrightarrow~ 6= -\frac{3}{4}\cdot 4+c ~\Longrightarrow c = 9$. Therefore $\displaystyle \frac{Max}{4} = 9~\Longrightarrow~Max = 36$.