University X - Linear Programming Assignment: Problem Solutions

This document presents solutions to a Linear Programming homework assignment. The solutions cover various aspects of Linear Programming, including the application of the simplex method. The problems involve maximizing an objective function subject to constraints. The document provides detailed steps and explanations, demonstrating how to formulate and solve these problems. The solutions include the identification of optimal solutions and the interpretation of results. The assignment highlights the importance of understanding the feasible region, slack variables, and the conditions for optimality. The document provides a valuable resource for students studying Linear Programming, offering clear and concise explanations of the concepts and techniques involved.

1 Homework Problem 1
No, the optimal solution to a Linear Programming Problem is always attained
at the boundary or more precisely corner points of the feasible region, and hence
an internal point of the area delimited by the constraints cannot be an optimal
solution.
2 Homework Problem 2
No, the solution to a Linear Programming Problem may not be always unique.
We may have Linear Programming Problems with no solution, unique solution
and infinitely many solutions.
For instance, an example of a Linear Programming Problem with infinitely
many solution is:
Maximize z =x
2 + 3y
2
subject to:
x + y ≤ 6
3x + y ≤ 15
x + 3y ≤ 15
x, y ≥ 0
3 Homework Problem 3
First we write the Linear Programming Problem in normal form by adding slack
and surplus variables:
Maximize z = 10x1 + 10x2 + 20x3 + 20x4 + 0s1 + 0s2
subject to
12x1 + 8x2 + 6x3 + 4x4 + s1 + 0s2 = 120
3x1 + 6x2 + 12x3 + 24x4 + 0s 1 + s2 = 180
x1, x2, x3, x4, s1, s2 ≥ 0
where s1 and s2 are slack variables.
We solve this by using the simplex method:
We see s2 is leaving the basis and x3 is entering the basis.
1

We see s1 is leaving the basis and x1 is entering the basis.
We see we have reached the optimal solution given by:
x1 = 2.8571, x2 = 0, x3 = 14.2857, x4 = 0
and Max z = 314.2857
2