Ken Montgomery
EMAT 6690
MATHEMATICS
APPLIED IN INDUSTRY
Linear
Programming: Graphical Solution
A company produces two types of product (Gadgets and Gizmos). The manufacturing process consists of assembly, polishing and packaging. The time required for each stage of manufacturing, for each product is given in Table 1.
Process 
Gadgets 
Gizmos 
Total
Time Required 
Assembly 
2 
4 
36 
Polishing 
3 
1 
36 
Packaging 
5 
2 
30 




Profit 
$30 
$20 
 
Table 1: Production Time Requirements
We let _{}and_{}represent the numbers of dozen Gadgets and Gizmos, respectively and thus obtain the objective function (Equation 1) for profit, which we desire to maximize.
Equation 1: _{}
From table 1 we obtain the following production constraints.
_{}
We also assume that production capability (parts, labor, etc.) will never be negative, so we satisfy the following necessary inequalities.
_{}
To solve this problem using the graphical method, we begin by first graphing the system of inequalities. We plot these inequalities one at a time, to better understand how the constraint space is developed. Figure 1 shows a graph of the first inequality.
Figure 1: Graph of _{}
Graphing the second inequality on top of the first yields the composite graph in Figure 2.
Figure 2: Graph of _{}and_{}
Our constraint space begins to take space as the darker, bounded intersection of these two inequalities. Graphing the third inequality on top of the first two yields the composite graph in Figure 3.
Figure 3: Graph of _{},_{}and _{}
In Figure 3, we have the final composite graph of the three However since we also have the inequalities _{}and_{}, our constraint space is further confined to only the positive region of the bounded region above. This final constraint space is given in Figure 4, with _{}and_{}plotted in yellow, on top of the previous three inequalities.
Figure 4: Composite graph of _{},_{},_{},_{}and_{}
Notice the darkest region of the graph, a quadrilateral with vertices (0,0), (0,9), (6,0) and (3,7.5), which is the bounded constraint space. Testing each of these vertices in turn we obtain four possible values of z, given by the following four equations.
_{}
Testing values inside the constraint space will demonstrate that 240 is the highest zvalue. To understand why the maximum zvalue must correspond to a vertex we plot the objective function over our constraint space.
We next plot the objective function for profit. However, this equation is in three variables, representing a plane and requiring a threedimensional plot. Nevertheless, the above graphs each represent the xy plane, and the intersection of the objective profit plane with the xy plane should be a line, which we can then plot in our present perspective.
Solving the objective profit equation for y, in terms of z provides an entire family of lines with the same slope and with yintercepts that are related to the value of z (Equation 1).
Equation 1: _{}
You may download the Graphing Calculator file Gadgets&Gizmos.gcf to explore this parameterization in z or view the Quicktime movie Gadgets&Gizmos to see the dynamic representation of this family of lines.
The only corner or vertex of the constraint space below that the line touches is given by the values x = 3, y = 7.5 and which correspond to the zvalue of 240. Notice that the line passes through the point at this corner of the constraint space illustrating this optimal value of z for the parameterized line equation and thus for the plane equation (Figure 5).
Figure 5: Objective function plotted with optimum zvalue
Notice that if the objective function (Equation 1) were plotted so that it passed through another vertex or points inside of the constraint space, these lines would have lower yintercepts and since there is a direct, linear correlation between the yintercept and z (i.e. _{}), a lower yintercept corresponds to a lower zvalue or profit. Figure 6 provides a plot of the objective function minus the yellow, overlaying constraints of positive x and y values for contrast.
Figure 6: Plot of objective function over constraint space without _{}and_{}constraints
Return to EMAT 6690