National university of uzbekistan named after mirzo ulugbek uzbek-israel joint faculty

Example 2 The Simplex Method with Three Decision Variables
Use the simplex method to find the maximum value of
⇒ Objective function
subject to the constraints

where , and .
Solution
Using the basic feasible solution

the initial and subsequent simplex tableaus for this problem are shown below. (Check the computations, and note the “tie” that occurs when choosing the first entering variable.)

							Basic Variable
2	1	0	1	0	0	10
1	2	-2	0	1	0	20
0	1	2	0	0	1	5		←Departing
-2	1	-2	0	0	0	0
		↑
		Entering

							Basic Variable
2	1	0	1	0	0	10		←Departing
1	3	0	0	1	1	25
0	½	1	0	0	½	5/2
-2	2	0	0	0	1	5
↑
Entering

							Basic Variable
1	½	0	½	0	0	5
0	5/2	0	-1/2	1	1	20
0	½	1	0	0	½	5/2
0	3	0	1	0	1	15

This implies that the optimal solution is

and the maximum value of z is 15.
Note that . The optimal solution yields a maximum value of provided that , and Check that these values satisfy the constraints giving equality in the first and third constraints, yet the second constraint has a slack of 20.
Occasionally, the constraints in a linear programming problem will include an equation. In such cases, add a “slack variable” called an artificial variable to form the initial simplex tableau. Technically, this new variable is not a slack variable (because there is no slack to be taken). Once you have determined an optimal solution in such a problem, check that any equations in the original constraints are satisfied. Example 3 illustrates such a case.
Example 3 A Business Application: Maximum Profit
A manufacturer produces three types of plastic fixtures. The table below shows the times required for molding, trimming, and packaging. (Times are in hours per dozen fixtures, and profits are in dollars per dozen fixtures.)

Process	Type A	Type B	Type C
Molding	1	2	3/2
Trimming	2/3	2/3	1
Packaging	1/2	1/3	1/2
Profit	$11	$16	$15

The maximum amounts of production time that the manufacturer can allocate to each component are listed below.

Molding: 12,000 hours Trimming: 4600 hours Packaging: 2400 hours

How many dozen units of each type of fixture should the manufacturer produce to obtain a maximum profit?
Solution
Let , and represent the numbers of dozens of types A, B, and C fixtures, respectively. The objective function to be maximized is
Profit
where , and . Moreover, using the information in the table, you can write the constraints below.

So, the initial simplex tableau with the basic feasible solution

is as shown below

							Basic Variable
1	2	3/2	1	0	0	12,000		←Departing
2/3	2/3	1	0	1	0	4600
1/2	1/3	1/2	0	0	1	2400
-11	-16	-15	0	0	0	0
	↑
	Entering

							Basic Variable
1/2	1	3/4	1/2	0	0	6000
1/3	0	1/2	-1/3	1	0	600
1/3	0	1/4	-1/6	0	1	400		←Departing
-3	0	-3	8	0	0	96,000
↑
Entering

							Basic Variable
0	1	3/8	3/4	0	-3/4	5400
0	0	1/4	-1/6	1	-1	200		←Departing
1	0	3/4	-1/2	0	3	1200
0	0	-3/4	13/2	0	9	99,600
		↑
		Entering

							Basic Variable
0	1	0	-1	-3/2	0	5100
0	0	1	-2/3	4	-4	800
1	0	0	0	-3	6	600
0	0	0	6	3	6	100,200

So the maximum profit is $100,200, obtained by producing 600 dozen units of Type A, 5100 dozen units of Type B, and 800 dozen units of Type C.
In Example 3, note the “tie” that occurs when choosing the second entering variable. Verify that choosing instead of as the second entering variable results in the two intermediate simplex tableaus below, and the same final tableau (and optimal solution) shown in Example 3.

							Basic Variable
1/2	1	3/4	1/2	0	0	6000
1/3	0	1/2	-1/3	1	0	600		←Departing
1/3	0	¼	-1/6	0	1	400
-3	0	-3	8	0	0	96,000
		↑
		Entering

							Basic Variable
0	1	0	1	-3/2	0	5100
2/3	0	1	-2/3	2	0	1200
1/6	0	0	0	-1/2	1	100		←Departing
-1	0	0	6	6	0	99,600
↑
Entering