Optimization Engineering Lecture Notes PDF

‫جايعح انًرقة‬ ECE _ ‫كهٍح انهنذسح‬ ‫انخًس – نٍثٍا‬ Master Program Optimization Engineering Lecture #5&6 1  ‫االستمثال الهندسي‬ ‫‪Eng.‬‬ ‫‪Optimization‬‬ ‫"وق ل اعملوا فسيرى هللاُ عملَكم ورسولُه‬ ‫والمؤمنون وستُردُون إلى عالِم ِ‬ ‫الغيب‬...

‫جايعح انًرقة‬ ECE _ ‫كهٍح انهنذسح‬ ‫انخًس – نٍثٍا‬ Master Program Optimization Engineering Lecture #5&6 1  ‫االستمثال الهندسي‬ ‫‪Eng.‬‬ ‫‪Optimization‬‬ ‫"وق ل اعملوا فسيرى هللاُ عملَكم ورسولُه‬ ‫والمؤمنون وستُردُون إلى عالِم ِ‬ ‫الغيب‬ ‫ِ‬ ‫والشهادة فينبئكم بما كنتم تعملون‪".‬‬ ‫صدق هللا العظيم‬ ‫‪4‬‬ ‫‪4‬‬  ‫دكتىر عثذانسالو انهادي انذٌة‬ ‫استار هنذسح نظى ويعانجح انًعهىياخ‬ ‫يستشار إدارج األعًال ويشارٌع انتغٍٍر وانتطىٌر‬ ‫يؤهم فً تذرٌة وتناء فرق انعًم يهنٍا‬ ‫خثٍر انتنًٍح انثشرٌح & وإدارج انًىارد انثشرٌح‬ ‫_______________________________________________‬ ‫انًؤهالخ‬ ‫دكتوراه ‪ ،‬هندسة نظم ومعالجة المعلومات ‪ ،‬جامعة ميزوري – أمريكا‬ ‫‪ ،‬أيرٌكا )‪ (MBA‬ياجستٍر إدارج األعًال‪ ،‬تًٍز إلدارج األعًال وانًشارٌع‬ ‫‪ ،‬أيرٌكا )‪ (PMP‬انشهادج انًهنٍح فً إدارج انًشارٌع ‪ ،‬انستتٍىخ إدارج انًشارٌع‬ ‫انشهادج انتأههٍح فً تقٍٍى وتناء فرق انعًم ‪ ،‬تاٌة رٌسىرسس ‪ -‬أيرٌكا‬ ‫انشهادج انتأههٍح فً انسًاخ وانًهاراخ انقٍادٌح ‪ ،‬تاٌة رٌسىرسس ‪ -‬أيرٌكا‬ ‫شهادج تذرٌة انًذرتٍن ‪ ،‬تاٌك قرووب ‪ -‬أيرٌكا‬  LPP Optimization (Graphical Method)  Group Discussion Decision Variables/Objective Fun Parameters Constraint Determination Model & Standard Form Linear Programming Optimization Feasible/Optimal/Best Solution Super & Superior & Supreme ‫تىضٍح تعض‬ ‫انًصطهحاخ‬ Decision variables i& Objective Function The objective function is needed to solve the optimization problems. A linear representation of the form Z = ax + by, where a, b are constraints, and x, y are variables, which have to be maximized or minimized is called an objective function. The variables x and y are called the decision variables. Decision variables represent the unknown information in a problem. Decision variables differ from normal programming variables in that they have domains of possible values and may have constraints placed on the allowed combinations of theses values.  LP Model Parameters In linear programming models rely on various parameters that define known quantities or data related to the problem. In the furniture problem, as an example, we encounter three types of parameters: prices, resource capacity, and technology coefficients (or parameters). In other problems, we may have times, sizes, machines, human resources etc.  The role of Constraints in Optimization Constraints are logical conditions that a solution to an optimization problem must satisfy. Constraints reflect real-world limits on production capacity, market demand, available funds, and so on.  ‫‪To define a constraint, you first‬‬ ‫‪compute the value of interest using the‬‬ ‫‪decision variables.‬‬ ‫لتحديد قيد‪ ،‬عليك أوالً حساب قيمة الفائدة منه‬ ‫باستخدام متغيرات القرار‪ ،‬عبر جمع البيانات‬ ‫والتحليل لمعرفة وتحديد احتياجات المنظمة مثال‪.‬‬ Decision variables represent the unknown information in a problem. Decision variables differ from normal programming variables in that they have domains of possible values and may have constraints placed on the allowed combinations of theses values.  Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear relationships. ،‫ضا التحسين الخطي‬ ً ‫ والتي تسمى أي‬،(LP) ‫البرمجة الخطية‬ ‫هي طريقة لتحقيق أفضل النتائج (مثل الحد األقصى للربح‬ ‫أو أقل تكلفة) في نموذج رياضي يتم تمثيل متطلباته‬..‫وأهدافه من خالل عالقات خطية‬  Feasible Solution & Optimal Solution The maximization or minimization of some quantity is the objective in all linear programming problems. A feasible solution satisfies all the problem's constraints. An optimal solution is a feasible solution that results in the largest possible objective function value when maximizing (or smallest when minimizing).  Graphical Method of Linear Programming Optimization  Graphical Method The graphical method is used to optimize the two-variable linear programming. If the problem has two decision variables, a graphical method is the best method to find the optimal solution. In this method, the set of inequalities are subjected to constraints. Then the inequalities are plotted in the XY plane..  Graphical Method (continued) Once, all the inequalities are plotted in the XY graph, the intersecting region will help to decide the feasible region. The feasible region will provide the optimal solution as well as explains what all values our model can take. Let us see an example here and understand the concept of linear programming in a better way.  Graphical Method Steps  Step1 Formulate the Linear programming problem (LPP). We have already understood the mathematical formulation of an LP problem in a previous section. Note that this is the most crucial step as all the subsequent steps depend on our analysis here. Step 2: Construct a graph and plot the constraint lines The graph must be constructed in ‘n’ dimensions where ‘n’ is the number of decision variables. This should give you an idea about the complexity of this step if the number of decision variables increases.  One must know that one cannot imagine more than 3-dimensions anyway! The constraint lines can be constructed by joining the horizontal and vertical intercepts found from each constraint equation. Step 3: Determine the valid side of each constraint line. This is used to determine the domain of the available space, which can result in a feasible solution. How to check? A simple method is to put the coordinates of the origin (0,0) in the problem & determine if the objective function takes on a physical solution or not. If yes, then the side of the constraint lines on which the origin lies is the valid side. Else it lies on the opposite one. Step 4: Identify the feasible solution region The feasible solution region on the graph is the one which is satisfied by all the constraints. It could be viewed as the intersection of the valid regions of each constraint line as well. Choosing any point in this area would result in a valid solution for our objective function. Step 5: Plot objective fun. on the graph It will clearly be a straight line since we are dealing with linear equations here. One must be sure to draw it differently from the constraint lines to avoid confusion Choose the constant value in the equat- ion. of the objective function randomly, just to make it clearly distinguishable. Step 6: Find the optimum point An optimum point always lies on one of the corners of the feasible region. How to find it? Place a ruler on the graph sheet, parallel to the objective function. Be sure to keep the orientation of this ruler fixed in space. We only need the direction of the straight line of the objective function. Now begin from the far corner of the graph and tend to slide it towards the origin. If the goal is to minimize the objective function, find the point of contact of the ruler with the feasible region, which is the closest to the origin. This is the optimum pt. to minimize the func. If the goal is to maximize the objective function, find the point of contact of the ruler with the feasible region, which is the farthest from the origin. This is the optimum point for maximizing the function.0 Step 7: Calculate the coordinates of the optimum point. This is the last step of the process. Once you locate the optimum point, you’ll need to find its coordinates. This can be done by drawing two perpendicular lines from the point onto the coordinate axes and noting down the coordinates. Otherwise, you may proceed algebraically also if the optimum point is at the intersection of Step 7 Continued: Otherwise, you may proceed algebraically also if the optimum point is at the intersection of two constraint lines and find it by solving a set of simultaneous linear equations. The Optimum Point gives you the values of the decision variables necessary to optimize the objective function. To find out the optimized objective function, one can simply put in the values of these parameters in the equation of the objective function. You have found your solution! Worried about the execution of this seemingly long algorithm? Check out a solved example below! Linear Programming Examples Example #1 Example #2  Linear Programming Examples A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B. At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours. The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximize the combined sum of the units of X and the units of Y in stock at the end of the week. Formulate the problem of deciding how much of each product to make in the current week as a linear program. Solve this linear program graphically. Solution Let x be the number of units of X produced in the current week y be the number of units of Y produced in the current week, then the constraints are: 50x + 24y = 45 so production of X >= demand (75) - initial stock (30), which ensures we meet demand y >= 95 - 90 i.e. y >= 5 so production of Y >= demand (95) - initial stock (90), which ensures we meet demand The objective is: maximize (x+30-75) + (y+90-95) = (x+y-50) i.e. to maximize the number of units left in stock at the end of the week It is plain from the diagram below that the maximum occurs at the intersection of x=45 and 50x + 24y = 2400 Solving simultaneously, rather than by reading values off the graph, x=45 and y=6.25 with the value of the objective function being 1.25 Example #3  Problem: Calculate the maximal and minimal value of z = 5x + 3y for the following constraints. x + 2y ≤ 14 3x – y ≥ 0 x–y≤2  Solution: The three inequalities indicate the constraints. The area of the plane that will be marked is the feasible region. The optimization equation (z), z = 5x + 3y. You have to find the (x, y) corner points that give the largest and smallest values of z. To begin with, first solve each inequality. x + 2y ≤ 14 ⇒ y ≤ -(1/2)x + 7 3x – y ≥ 0 ⇒ y ≤ 3x x–y≤2⇒y≥x–2 Here is the graph for the above equations. In the following slide. Now pair the lines to form a system of linear equations to find the corner points. y = -(½) x + 7 y = 3x Solving the above equations, we get the corner points as follows, (2, 6) y = -1/2 x + 7 Solving the equations of the corresponding lines, we get the corner points as (-1, -3) For linear systems, the maximum and minimum values of the optimization equation lie on the corners of the feasibility region. Therefore, to find the optimum solution, you only need to plug these three points in z = 3x + 4y Let’s see: z = 3x + 4y The point (2, 6) : z = 5(2) + 3(6) = 10 + 18 = 28 The point (6, 4): z = 5(6) + 3(4) = 30 + 12 = 42 The point, (–1, –3): z = 5(-1) + 3(-3) = -5 -9 = -14 Hence, the maximum of z = 42 lies at (6, 4) and the minimum of z = -14 lies at (-1, -3) Example #4  Problem Solve the following linear program: maximize 5x1 + 6x2 subject to x1 + x2 = 3 5x1 + 4x2 = 0 x2 >= 0  The Solution by Inspection It is plain from the diagram below that the maximum occurs at the intersection of 5x1 + 4x2 = 35 and x1 - x2 = 3 Solving simultaneously, rather than by reading values off the graph, we have that 5(3 + x2) + 4x2 = 35 i.e. 15 + 9x2 = 35 i.e. x2 = (20/9) = 2.222 and x1 = 3 + x2 = (47/9) = 5.222 The maximum value is 5(47/9) + 6(20/9) = (355/9) = 39.444 Example #5  Problem A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair..  Problem (continued) Customer demand requires that he makes at least three times as many chairs as tables. Tables take up 4 times as much storage space as chairs and 3 is room for at most four tables each week. Formulate this problem as a linear programming optimization problem and solve it graphically.  Solution Variables Let xT = number of tables made per week xC = number of chairs made per week Constraints total work time 6xT + 3xC = 3xT storage space (xC/4) + xT = 0 Objective maximize 30xT + 10xC  The graphical representation of the problem is given below and from that we have that the solution lies at the intersection of (xC/4) + xT = 4 and 6xT + 3xC = 40 Solving these two equations simultaneously we get xC = 10.667, xT = 1.333 and the corresponding profit = £146.667  ‫شكرا‬ ‫عهى حسن اإلنصاخ‬