Midterm 2, 5 problems, 15 points each. Return this page.

Solve linear programs where all

Solutions.

1. The second row says

-2-3x_{1} -*x*_{3}
= *x*_{4} which contradicts
the condition that all *x _{i}* >= 0. So the LP
is infeasible.

2. We simplify the tableau:

x_{2} |
x_{1} |
1 |
Problem 2 |

2* |
-4 |
11 |
= x_{1} |

6 |
0 |
31 |
= x_{4} |

1 |
-3 |
6 |
-> min |

We pivot this (nonstandard) tableau and obtain

x_{1} |
x_{1} |
1 |
Problem 2 |

1/2 |
2 |
-11/2 |
=x_{2} |

3 |
12 |
-2 |
= x_{4} |

1/2 |
-1 |
1/2 |
-> min |

x_{1} |
1 |
Problem 2 |

2.5 |
-11/2 |
=x_{2} |

15 |
-2 |
= x_{4} |

-0.5 |
1/2 |
-> min |

3. We simplify the tableau :

x_{2} |
x_{3} |
1 |
Problem 3 |

-2 |
-4 |
7 |
= x_{1} |

6 |
-1 |
11 |
= x_{1} |

1 |
-3 |
6 |
=f -> max |

We subtract the first row from the second row and multiply the last
row by -1

x_{2} |
x_{3} |
1 |
Problem 3 |

-2 |
-4 |
7 |
= x_{1} |

8* |
3 |
4 |
= 0 |

-1 |
3 |
-6 |
=-f -> min |

Now we pivot on 8 and drop the first column (with 0 on top):

tract the first row from the second row and multiply the last ropw by -1

x_{3} |
1 |
Problem 3 |

-4 |
7 |
= x_{1} |

-3/8 |
-1/2 |
= x_{2} |

27/8 |
13/2 |
=-f -> min |

This is a standard tableau, and the

A short cut: the = 0 row in the tableau we pivoted is infeasible in presense of

the condition that all

4.We simplify the tableau:

x_{3} |
x_{2} |
1 | Problem 4 |

-3* | 2 | 9 | = x_{1} |

0 | 1 | 21 | = x_{4} |

-3 | 1 | 6 | -> min |

We pivot and obtain

x_{1}_{} |
x_{2} |
1 | Problem 4 |

-1/3 | 2/3 | 3 | =x_{3} |

0 | 1 | 21 | = x_{4} |

1 | -1 | -3 | -> min |

5. We simplify the tableau:

x_{2} |
x_{3} |
1_{} |
Problem 5 |

2 | -4 | 3 | = x_{1} |

6 | 1 | 7 | = x_{4} |

1 | 0 | 2 | -> min |

min = 2 at

0 | x_{2} |
1 | -x_{3} |
Problem 5 |

1 | 2 | 3 | 4 | = x_{1} |

5 | 6 | 7 | -1 | = x_{4} |

0 | 1 | 2 | 0 | -> min |