Example 1: Consider Farmer Jone’s problem restated. Slack variables have been inserted, making the constraints equalities, and the variables are x_j, j = 1, \dots, 5, instead of indicating the slack variables by s_i‘s:
Maximize: 80x_1 + 60x_2
Subject to: x_1 + x_2 + x_3 = 100, 2x_1 + x_2 + x_4 = 150, 5x_1 + 10x_2 + x_5 = 800, x_i \ge 0, i = 1, \dots, 5.
The vector x^T = [60, 30, 10, 0, 200] is a (nonbasic) feasible solution. Determine a vector y and a basic feasible solution of the form x+ty.
Solution: If we can determine a solution y to the associated homogenous system below
y_1 + y_2 + y_3 = 0, 2y_1 + y_2 + y_4 = 0, 5y_1 + 10y_2 + y_5 = 0,such that 80y_1 + 60y_2 > 0 and y_4 = 0 (because x_4 = 0), then a basic feasible solution x' can be found whose objective function value is at least as great as that of x.
We start by setting y_4 = 0 since x_4 = 0. Then choose y_1 = 1, y_2 = -2 to satisfy the resulting second equation 2y_1 + y_2 = 0. Substituting these values in turn into equations one and three yields y_3 = 1, y_5 = 15. Thus, we obtained the solution y^T = [1,-2,1,0,15]. Since 80\cdot 1 + 60\cdot (-2) < 0, we replace y with -y, so that y^T = [-1,2,-1,0,-15] and 80\cdot (-1) + 60\cdot 2 = 40 > 0.
Now we determine a scalar t such that x + ty is a basic feasible solution, and 80(x_1 + ty_1) + 60(x_2 + ty_2) \ge 80x_1 + 60x_2. Consider the vector (x+ty)^T = [60-t, 30+2t,10-t, 0, 200-15t]. Choosing the largest value of t that will make x+ty nonnegative, we get t = \min(60/1, 10/1, 200/15) = 10. Thus, the new candidate for a basic feasible solution is [50,50,0,0,50].
Example 2: Formulate the linear program to solve the following problem: The MF&S supplies castings to a variety of customers. It plans to devote the next week of production to just two, J and W. MF&S uses a combination of pure steel and scrap metal to fulfill its orders and has 400 pounds of pure steel and 360 pounds of scrap metal in stock. The pure steel costs MF&S $6 per pound and the scrap $3 per pound. Pure steel requires 3 hours per pound to process into a casting, while scrap requires only 2 hours per pound. Total available processing time in the week is 2,000 hours.
The castings for J each require 5 pounds of metal, with a quality control restriction limiting the ratio of scrap to pure steel to a maximum of 5/7. J has ordered 30 castings at a price of $50 each.
The castings for W each require 8 pounds of metal, with a quality restriction of maximum scrap to pure steel ratio of 2/3. W has ordered 40 castings at a price of $80 each.
Determine how MF&S should allocate their metal stocks to produce the castings ordered by these two customers if the objective is to maximize the value added to the metal, i.e., to maximize the selling price minus the cost of the metal.
Solution: Suppose x_1, x_2 are the amount of pure steel and scrap metal for J and y_1, y_2 are those for M. The value added to the metal is 50\times 30 + 80 \times 40 - [6(x_1 + y_1) + 3(x_2 + y_2)], and so we want to minimize 6(x_1 + y_1) + 3(x_2 + y_2). The constraints are:
- Inventory contraints: x_1+y_1 \le 400, x_2 + y_2 \le 360.
- Total processing time constraints: 3(x_1 + y_1)+2(x_2 + y_2) \le 2000.
- Order constraints: x_1 + x_2 = 30 \times 5, y_1 + y_2 = 40\times 8.
- Quality constraints: -5x_1 + 7x_2 \le 0 (equivalently, x_2 / x_1 \le 5 / 7), -2y_1 + 3y_2 \le 0 (equivalently, y_2 / y_1 \le 2/3).
- Non-negativity constraints: x_1, x_2, y_1, y_2 \ge 0.
Example 3: RSC produces three imaginative lines of children’s riding vehicles: ambulances, fire trucks, and roadsters. They sell exclusively by mail order and thus ship each vehicle individually.
The key activity in production is molding the plastic body. The molding equipment can produce four ambulance bodies an hour, three fire trucks an hour, and six roadsters an hour. After the vehicle body is made, the only other production step is “dressing”, where any rough edges are smoothed and parts such as tires, steering wheels and insignia are added. The vehicles then move to the packing and shipping department. The times required in each of these departments are tabled below along with the per-unit profits:
| Dressing | Packing & shipping | Profit | |
|---|---|---|---|
| Ambulance | 15 min | 20 min | $70 |
| Fire truck | 20 min | 10 min | $80 |
| Roadster | 10 min | 10 min | $50 |
RSC prides itself on the versatility of its employees. Each of the four employees can work in any of the three jobs, and each of the four works 40 hours a week.RSC is planning production for a 13-week quarter. Demand for their vehicles has shown a seasonal pattern, and they plan for the demand for fire tucks to be at least as great as the total demand for the other two lines. How should RSC allocate the time of their four employees, and how many of each vehicle should they make to maximize their profit during the period?
Solution: Suppose x_1 ambulances, x_2 fire trucks and x_3 roadsters are to be produced. The times required in each of the molding, dressing and packing & shipping department along with the per-unit profits are:
| Molding | Dressing | Packing & shipping | Profit | |
|---|---|---|---|---|
| Ambulance | 1/4 hr | 1/4 hr | 1/3 hr | $70 |
| Fire truck | 1/3 hr | 1/3 hr | 1/6 hr | $80 |
| Roadster | 1/6 hr | 1/6 hr | 1/6 hr | $50 |
Maximize: 70x_1 + 80x_2 + 50x_3.
Subject to: (1/4 + 1/4 + 1/3)x_1 + (1/3 + 1/3 + 1/6)x_2 + (1/6+1/6+1/6)x_3 \le 40 \times 4 \times 13, x_1 - x_2 + x_3 \le 0 (equivalently, x_2 \ge x_1 + x_3), x_1, x_2, x_3 \ge 0.
It is clear that four employees should work on molding, dressing and packing & shipping subsequently.