Solution Approoch Linear Programming The Graphical Solution B 100 (2) Feasible region D 80 (4) 60 G 40 (40.30) z=100 (3) 60 2=180 E C 10 20 40 50 60 80 Xi Chen (chenxi0109@bfsu.edu.cn) Optimization Method 11/41
Solution Approach Linear Programming The Graphical Solution Xi Chen (chenxi0109@bfsu.edu.cn) Optimization Method 11 / 41
Solution Approach Linear Programming The simplex algorithm proceeds as follows: Step 1 Convert the LP to standard form. Step 2 Obtain a bfs(if possible)from the standard form. Step 3 Determine whether the current bfs is optimal. Step 4 If the current bfs is not optimal,then determine which nonbasic variable should become a basic variable and which basic variable should become a nonbasic variable to find a new bfs with a better objective function value. Step 5 Use EROs to find the new bfs with the better objective function value.Go back to step 3. 4口4得+之至，三)Q0 Xi Chen (chenxi0109@bfsu.edu.cn) Optimization Method 12/41
Solution Approach Linear Programming The simplex algorithm proceeds as follows: Step 1 Convert the LP to standard form. Step 2 Obtain a bfs (if possible) from the standard form. Step 3 Determine whether the current bfs is optimal. Step 4 If the current bfs is not optimal, then determine which nonbasic variable should become a basic variable and which basic variable should become a nonbasic variable to find a new bfs with a better objective function value. Step 5 Use EROs to find the new bfs with the better objective function value. Go back to step 3. Xi Chen (chenxi0109@bfsu.edu.cn) Optimization Method 12 / 41
Solution Approach Linear Programming Example 2 The Dakota Furniture Company manufactures desks,tables,and chairs. The manufacture of each type of furniture requires lumber and two types of skilled labor:finishing and carpentry.The amount of each resource needed to make each type of furniture is given in the following table. Currently,48 board feet of lumber,20 finishing hours,and 8 carpentry hours are available.A desk sells for $60,a table for $30,and a chair for $20.Dakota believes that demand for desks and chairs is unlimited,but at most five tables can be sold.Because the available resources have already been purchased,Dakota wants to maximize total revenue. Resource Requirements for Dakota Furniture Resource Desk Table Chair Lumber (board ft) 8 6 1 Finishing hours 4 1.5 Carpentry hours 2 1.5 0.5 0Q0 Xi Chen (chenxi0109@bfsu.edu.cn) Optimization Method 13/41
Solution Approach Linear Programming Example 2 The Dakota Furniture Company manufactures desks, tables, and chairs. The manufacture of each type of furniture requires lumber and two types of skilled labor: finishing and carpentry. The amount of each resource needed to make each type of furniture is given in the following table. Currently, 48 board feet of lumber, 20 finishing hours, and 8 carpentry hours are available. A desk sells for $60, a table for $30, and a chair for $20. Dakota believes that demand for desks and chairs is unlimited, but at most five tables can be sold. Because the available resources have already been purchased, Dakota wants to maximize total revenue. Xi Chen (chenxi0109@bfsu.edu.cn) Optimization Method 13 / 41
Solution Approach Linear Programming Define the decision variables as x1 the number of desks produced,x2 the number of tables produced,and x3 the number of chairs produced. max60x1+30x9+20x3 s.t. 8x1+6x2+x3 48 (Lumber constraint) 4x1+2x2+1.5x3 20 (Finishing constraint) 2x1 +1.5x2+0.5x3 8 (Carpentry constraint) x2≤5(Limitation on table demand)x为，x2,x为≥0 Canonical Form 0 Basic Row Variable 0 2-60x1-302-20x3 =0 2=0 1 8x1+6x2+x3+1 =48 1=48 2 4x1+2x3+1.5x3 +s2 =20 =20 3 2x1+1.5x3+0.5x3 +S3 =8 83=8 X2 +54=5 S4=5 BV={z,51,52,53,54}and NBV {x1,x2,x3}. DaO Xi Chen (chenxi0109@bfsu.edu.cn) Optimization Method 14/41
Solution Approach Linear Programming Define the decision variables as x1 the number of desks produced, x2 the number of tables produced, and x3 the number of chairs produced. max 60x1 + 30x2 + 20x3 s.t. 8x1 + 6x2 + x3 ≤ 48 (Lumber constraint) 4x1 + 2x2 + 1.5x3 ≤ 20 (Finishing constraint) 2x1 + 1.5x2 + 0.5x3 ≤ 8 (Carpentry constraint) x2 ≤ 5 (Limitation on table demand) x1, x2, x3 ≥ 0 BV = {z,s1,s2,s3,s4} and NBV = {x1, x2, x3}. Xi Chen (chenxi0109@bfsu.edu.cn) Optimization Method 14 / 41