重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research 4 ADAPTING TO OTHER MODEL FORMS Thus far we have presented the details.

Slides:



Advertisements
Similar presentations
广州市教育局教学研究室英语科 Module 1 Unit 2 Reading STANDARD ENGLISH AND DIALECTS.
Advertisements

高考短文改错专题 张柱平. 高考短文改错专题 一. 对短文改错的要求 高考短文改错的目的在于测试考生判断发现, 纠正语篇中 语言使用错误的能力, 以及考察考生在语篇中综合运用英 语知识的能力. 二. 高考短文改错的命题特点 高考短文改错题的形式有说明文. 短文故事. 书信等, 具有很 强的实用性.
期末考试作文讲解 % 的同学赞成住校 30% 的学生反对住校 1. 有利于培养我们良好的学 习和生活习惯; 1. 学生住校不利于了解外 界信息; 2 可与老师及同学充分交流有 利于共同进步。 2. 和家人交流少。 在寄宿制高中,大部分学生住校,但仍有一部分学生选 择走读。你校就就此开展了一次问卷调查,主题为.
第七课:电脑和网络. 生词 上网 vs. 网上 我上网看天气预报。 今天早上看了网上的天气预报。 正式 zhèngshì (报告,会议,纪录) 他被这所学校正式录取 大桥已经落成,日内就可以正式通车 落伍 luòw ǔ 迟到 chídào 他怕迟到,六点就起床了.
胸痛中心的时间流程管理 上海胸科医院 方唯一.
F1 VISA APPLICATION F1学生赴美留学签证申请流程.
-CHINESE TIME (中文时间): Free Response idea: 你周末做了什么?
破舊立新(三) 人生召命的更新 使徒行傳廿六章19-23節.
专题八 书面表达.
完形填空技巧 CET4.
自衛消防編組任務職責 講 義 This template can be used as a starter file for presenting training materials in a group setting. Sections Right-click on a slide to add.
Chapter 8 Liner Regression and Correlation 第八章 直线回归和相关
Academic Year TFC EFL Data Collection Outline 学年美丽中国英语测试数据收集概述
Mode Selection and Resource Allocation for Deviceto- Device Communications in 5G Cellular Networks 林柏毅 羅傑文.
Understanding Interest Rates
3-3 Modeling with Systems of DEs
Operators and Expressions
Euler’s method of construction of the Exponential function
Homework 4 an innovative design process model TEAM 7
Unit 4 I used to be afraid of the dark.
Been During the Vacation?
Module 5 Shopping 第2课时.
Population proportion and sample proportion
模式识别 Pattern Recognition
Differential Equations (DE)
微積分網路教學課程 應用統計學系 周 章.
非線性規劃 Nonlinear Programming
On Some Fuzzy Optimization Problems
Ch2 Infinite-horizon and Overlapping- generations Models (无限期与跨期模型)
Logistics 物流 昭安國際物流園區 總經理 曾玉勤.
创建型设计模式.
Unit 2 Key points summary.
第14章 竞争市场上的企业 上海杉达学院 国贸系.
机器人学基础 第四章 机器人动力学 Fundamentals of Robotics Ch.4 Manipulator Dynamics
Interval Estimation區間估計
子博弈完美Nash均衡 我们知道,一个博弈可以有多于一个的Nash均衡。在某些情况下,我们可以按照“子博弈完美”的要求,把不符合这个要求的均衡去掉。 扩展型博弈G的一部分g叫做一个子博弈,如果g包含某个节点和它所有的后继点,并且一个G的信息集或者和g不相交,或者整个含于g。 一个Nash均衡称为子博弈完美的,如果它在每.
Formal Pivot to both Language and Intelligence in Science
塑膠材料的種類 塑膠在模具內的流動模式 流動性質的影響 溫度性質的影響
GRANT UNION HIGH SCHOOL
Chapter 5 Recursion.
普通物理 General Physics 21 - Coulomb's Law
Mechanics Exercise Class Ⅰ
Guide to a successful PowerPoint design – simple is best
3.5 Region Filling Region Filling is a process of “coloring in” a definite image area or region. 2019/4/19.
中国科学技术大学计算机系 陈香兰 2013Fall 第七讲 存储器管理 中国科学技术大学计算机系 陈香兰 2013Fall.
虚 拟 仪 器 virtual instrument
中央社新聞— <LTTC:台灣學生英語聽說提升 讀寫相對下降>
关联词 Writing.
線性規劃模式 Linear Programming Models
公钥密码学与RSA.
高考应试作文写作训练 5. 正反观点对比.
6.6 線性規劃的單體法 單體法 (simplex method)
An organizational learning approach to information systems development
Q & A.
Chapter 10 Mobile IP TCP/IP Protocol Suite
Mechanics Exercise Class Ⅱ
名词从句(2).
1 如何將可視化的力量運用於IR 江昱潔.
 隐式欧拉法 /* implicit Euler method */
定语从句(11).
动词不定式(6).
2 Number Systems, Operations, and Codes
怎樣把同一評估 給與在不同班級的學生 How to administer the Same assessment to students from Different classes and groups.
Race Conditions and Semaphore
簡單迴歸分析與相關分析 莊文忠 副教授 世新大學行政管理學系 計量分析一(莊文忠副教授) 2019/8/3.
Sun-Star第六届全国青少年英语口语大赛 全国总决赛 2015年2月 北京
Principle and application of optical information technology
高考英语作文指导 福建省教研室 姚瑞兰.
Train Track and Children
When using opening and closing presentation slides, use the masterbrand logo at the correct size and in the right position. This slide meets both needs.
Presentation transcript:

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research 4 ADAPTING TO OTHER MODEL FORMS Thus far we have presented the details of the simplex method under the assumptions that the problem is in our standard form (maximize Z subject to functional constraints in ≤ form and nonnegativity constraints on all variables) and that bi ≥ 0 for all i = 1, 2...., m. In this section we point out how to make the adjustments required for other legitimate forms of the linear programming model.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The only serious problem introduced by the other forms for functional constraints (the = or ≥ forms, or having a negative right-hand side) lies in identifying an initial BF solution. Before, this initial solution was found very conveniently by letting the slack variables be the initial basic variables, so that each one just equals the nonnegative, right- hand side of its equation, Now, something else must be done.  The standard approach that is used for all these cases is the artificial- variable technique. This technique constructs a more convenient artificial problem by introducing a dummy variable (called an artificial variable) into each constraint that needs one. This new variable is introduced just for the purpose of being the initial basic variable for that equation. The usual nonnegativity constraints are placed on these variables, and the objective function also is modified to impose an exorbitant penalty on their having values larger than zero. The iterations of the simplex method then automatically force the artificial variables to disappear (become zero), one at a time, until they are all gone, after which the real problem is solved.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  To illustrate the artificial-variable technique, first we consider the case where the only nonstandard form in the problem is the presence of one or more equality constraints.  EQUALITY CONSTRAINTS  Any equality constraint  a il X 1 + a i2 X a in X n = b i  actually is equivalent to a pair of inequality constraints  a il X 1 + a i2 X a in X n <= b i  a il X 1 + a i2 X a in X n >= b i.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  However, rather than making this substitution and thereby increasing the number of constraints, it is more convenient to use the artificial-variable technique.  Example  Suppose that the Wyndor Glass Co. problem in Sec. 3.1 is modified to require that Plant 3 be used at full capacity. The only resulting change in the linear programming model is that the third constraint, 3X 1 + 2X 2 <= 18, instead becomes an equality constraint 3x1 + 2x2 = 18, so that the complete model becomes the one shown in the upper right-hand corner of Fig This figure also shows in darker ink the feasible region which now consists of just the line segment connecting (2, 6) and (4, 3).

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  After the slack variables still needed for the inequality constraints are introduced, the system of equations for the augmented form of the problem becomes  (0) Z- 3x1 - 5x2 = 0  (1) x1 + x3 = 4  (2) 2x2 + x4 = 12  (3) 3x1 + 2x2 = 18.  Unfortunately, these equations do not have an obvious initial BF solution because there is no longer a slack variable to use as the initial basic variable for Eq. (3).  It is necessary to find an initial BF solution to start the simplex method.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Obtaining an Initial BF Solution  The procedure is to construct an artificial problem that has the same optimal solution as the real problem by making two modifications of the real problem.  1. Apply the artificial-variable technique by introducing a nonnegative artificial variable (call it x5) into Eq. (3), just as if it were a slack variable  (3) 3x1 + 2x2 + X5 = 18.  2. Assign an overwhelming penalty to having X5 > 0 by changing the objective function  Z = 3x1 + 5x2 to  Z = 3x1 + 5x2 – MX5,  Where M symbolically represents a huge positive number.  This method of forcing X5 to be X5 = 0 in the optimal solution is called the Big M method.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Now find the optimal solution for the real problem by applying the simplex method to the artificial problem, starting with the following initial BF solution:  Initial BF Solution  Nonbasic variables: x1 = 0, x2 = 0  Basic variables: x3 = 4, x4 = 12, X5 = 18.  Because X5 plays the role of the slack variable for the third constraint in the artificial problem, this constraint is equivalent to 3x1 + 2x2 <= 18 (just as for the original Wyndor Glass Co. problem in Sec. 3.1). We show below the resulting artificial problem (before augmenting) next to the real problem.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Obtaining an Initial BF Solution

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Note that the simplex method moves counterclockwise here whereas it moved clockwise for the original Wyndor Glass Co. problem (see Fig. 4.2). The reason for this difference is the extra term - MX5 in the objective function for the artificial problem.  Before applying the simplex method and demonstrating that it follows the path shown in Fig. 4.4, the following preparatory step is needed.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Converting Equation (0) to Proper Form  The system of equations after the artificial problem is augmented is  (0) Z- 3x1 - 5x2 + MX5 = 0  (1) x1 + x3 = 4  (2) 2x2 + x4 = 12  (3) 3x1+ 2x2 + X5 = 18  where the initial basic variables (x3, x4, X5) are shown in green type. However, this system is not yet in proper form from Gaussian elimination because a basic variable X5 has a nonzero coefficient in Eq. (0). Recall that all basic variables must be algebraically eliminated from Eq. (0) before the simplex method can either apply the optimality test or find the entering basic variable. This elimination is necessary so that the negative of the coefficient of each nonbasic variable will give the rate at which Z would increase if that nonbasic variable were to be increased from 0 while adjusting the values of the basic variables accordingly.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Application of the Simplex Method  This new Eq. (0) gives Z in terms of just the nonbasic variables (xl, x2),  Z = -18M + (3M + 3)x1 + (2M + 5)x2.  Since 3M + 3 > 2M + 5 (remember that M represents a huge number), increasing x1 increases Z at a faster rate than increasing x2 does, so x1 is chosen as the entering basic variable. This leads to the move from (0, 0) to (4, 0) at iteration 1, shown in Fig. 4.4, thereby increasing Z by 4(3M + 3).

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Negative Right-Hand Sides  The technique mentioned in the preceding sentence for dealing with an equality constraint with a negative right-hand side (namely, multiply through both sides by -1) also works for any inequality constraint with a negative right-hand side. Multiplying through both sides of an inequality by - 1 also reverses the direction of the inequality; i.e., = or vice versa.  For example, doing this to the constraint  x1 - x2 <= -1 (namely, x1 <= x2 - 1) gives the equivalent constraint  -x1 + x2 >= 1 (that is, x2 - 1 >= x1)  but now the right-hand side is positive. Having nonnegative right- hand sides for all the functional constraints enables the simplex method to begin, because (after augmenting) these right-hand sides become the respective values of the initial basic variables, which must satisfy nonnegativity constraints.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Functional Constraints in >= Form  To illustrate how the artificial-variable technique deals with functional constraints in >= form, we will use the model for designing Mary's radiation therapy, as presented in Sec For your convenience, this model is repeated right, where we have placed a box around the constraint of special interest here.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research 

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Our approach involves introducing both a surplus variable x5 (defined as x5 = 0.6xl + 0.4x2 - 6) and an artificial variable X6, as shown next. Here x5 is called a surplus variable because it subtracts the surplus of the left-hand side over the right-hand side to convert the inequality constraint to an equivalent equality constraint. Once this conversion is accomplished, the artificial variable is introduced just as for any equality constraint. Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  After a slack variable x3 is introduced into the first constraint, an artificial variable x4 is introduced into the second constraint, and the Big M method is applied, so the complete artificial problem (in augmented form) is Note that the coefficients of the artificial variables in the objective function are +M, instead of -M, because we now are minimizing Z. Thus, even though x4 > 0 and/or x6 > 0 is possible for a feasible solution for the artificial problem, the huge unit penalty of +M prevents this from occurring in an optimal solution. Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  As usual, introducing artificial variables enlarges the feasible region. Compare below the original constraints for the real problem with the corresponding constraints on (xl, x2) for the artificial problem. Introducing the artificial variable x4 to play the role of a slack variable in the second constraint allows values of (x1, x2) below the 0.5x x2 = 6 line in Fig Introducing x5 and X6 into the third constraint of the real problem (and moving these variables to the right-hand side) yields the equation Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Because both x5 and X6 are constrained only to be nonnegative, their difference x5 - x6 can be any positive or negative number. Therefore, 0.6x x2 can have any value, which has the effect of eliminating the third constraint from the artificial problem and allowing points on either side of the 0.6x x2 = 6 line in Fig. (We keep the third constraint in the system of equations only because it will become relevant again later, after the Big M method forces x6 to be zero.)  Consequently, the feasible region for the artificial problem is the entire polyhedron in figure whose vertices are (0, 0), (9, 0), (7.5, 4.5), and (0, 12). Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research 

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Since the origin now is feasible for the artificial problem, the simplex method starts with (0, 0) as the initial CPF solution, i.e., with (x1, x2, x3, X4, x5, X6) = (0, 0, 2.7, 6, 0, 6) as the initial BF solution. (Making the origin feasible as a convenient starting point for the simplex method is the whole point of creating the artificial problem.) We soon will trace the entire path followed by the simplex method from the origin to the optimal solution for both the artificial and real problems. But, first, how does the simplex method handle minimization? Functional Constraints in >= Form

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Minimization  One straightforward way of minimizing Z with the simplex method is to exchange the roles of the positive and negative coefficients in row 0 for both the optimality test and step 1 of an iteration. However, rather than changing our instructions for the simplex method for this case, we present the following simple way of converting any minimization problem to an equivalent maximization problem: i.e., the two formulations yield the same optimal solutions.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The two formulations are equivalent because the smaller Z is, the larger -Z is, so the solution that gives the smallest value of Z in the entire feasible region must also give the largest value of -Z in this region.  Therefore, in the radiation therapy example, we make the following change in the formulation:  Minimize Z = 0.4x x2  ---> Maximize -Z = -0.4x x2.  After artificial variables X4 and X6 are introduced and then the Big M method is applied, the corresponding conversion is  Minimize Z = 0.4x x2 + MX4 + MX6  --> Maximize -Z = -0.4x x2 - MX4 - MX6. Minimization

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  We now are nearly ready to apply the simplex method to the radiation therapy example. By using the maximization form just obtained, the entire system of equations is now  (0) -Z + 0.4x x2 + MX4 + MX6 = 0  (1) 0.3x x2 + x3 = 2.7  (2) 0.5x x2 + x4 = 6  (3) 0.6x x2 - x5 + X6 = 6.  The basic variables (x3, X4, X6) for the initial BF solution (for this artificial problem) are shown in green type. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Note that this system of equations is not yet in proper form from Gaussian elimination, as required by the simplex method, since the basic variables X4 and X6 still need to be algebraically eliminated from Eq. (0). Because X4 and X6 both have a coefficient of M, Eq. (0) needs to have subtracted from it both M times Eq. (2) and M times Eq. (3). The calculations for all the coefficients (and the right-hand sides) are summarized below, where the vectors are the relevant rows of the simplex tableau corresponding to the above system of equations. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The resulting initial simplex tableau, ready to begin the simplex method, is shown at the top of Table Applying the simplex method in just the usual way then yields the sequence of simplex tableaux shown in the rest of Table For the optimality test and the selection of the entering basic variable at each iteration, the quantities involving M are treated just as discussed in connection with Table Note in Table 4.12 the progression of values of the artificial variables X4 and X6 and of Z. We start with large values, X4 = 6 and X6 = 6, with Z = 12M (-Z = - 12M). The first iteration greatly reduces these values. The Big M method succeeds in driving X6 to zero (as a new nonbasic variable) at the second iteration and then in doing the same to X4 at the next iteration. With both X4 = 0 and X6 = 0, the basic solution given in the last tableau is guaranteed to be feasible for the real problem. Since it passes the optimality test, it also is optimal. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Now see what the Big M method has done graphically in Fig The feasible region for the artificial problem initially has four CPF solutions--(0, 0), (9, 0), (0, 12), and (7.5, 4.5)--and then replaces the first three with two new CPF solutions--(8, 3), (6, 6)- after X6 decreases to x6 = 0 so that 0.6x x2 >= 6 becomes an additional constraint. Starting with the origin as the convenient initial CPF solution for the artificial problem, we move around the boundary to three other CPF solutions--(9, 0), (8, 3), and (7.5, 4.5). The last of these is the first one that also is feasible for the real problem. Fortuitously, this first feasible solution also is optimal, so no additional iterations are needed. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  For other problems with artificial variables, it may be necessary to perform additional iterations to reach an optimal solution after the first feasible solution is obtained for the real problem. Thus, the Big M method can be thought of as having two phases. In the first phase, all the artificial variables are driven to zero (because of the penalty of M per unit for being greater than zero) in order to reach an initial BF solution for the real problem. In the second phase, all the artificial variables are kept at zero (because of this same penalty) while the simplex method generates a sequence of BF solutions for the real problem that leads to an optimal solution. The two-phase method described next is a streamlined procedure for performing these two phases directly, without even introducing M explicitly. Solving the Radiation Therapy Example

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research The Two-Phase Method  For the radiation therapy example just solved in Table 4.12, recall its real objective function  Real problem: Minimize Z = 0.4x x2.  However, the Big M method uses the following objective function (or its equivalent in maximization form) throughout the entire procedure:  Big M method: Minimize Z = 0.4x x2 + MX4 + MX6.  Since the first two coefficients are negligible compared to M, the two-phase method is able to drop M by using the following two objective functions with completely different definitions of Z in turn.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Two-phase method:  Phase 1: Minimize Z = X4 + X6 (until X4 = 0, X6 = 0).  Phase 2: Minimize Z = 0.4x x2 (with X4 = 0, X6 = 0).  The phase 1 objective function is obtained by dividing the Big M method objective function by M and then dropping the negligible terms. Since phase 1 concludes by obtaining a BF solution for the real problem (one where X4 = 0 and X6 = 0), this solution is then used as the initial BF solution for applying the simplex method to the real problem (with its real objective function) in phase 2.  Before solving the example in this way, we summarize the general method. The Two-Phase Method

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Initialization: Revise the constraints of the original problem by introducing artificial variables as needed to obtain an obvious initial BF solution for the artificial problem.  Phase 1: The objective for this phase is to find a BF solution for the real problem. To do this, Minimize Z = ∑artificial variables, subject to revised constraints.  The optimal solution obtained for this problem (with Z = 0) will be a BF solution for the real problem.  Phase 2: The objective for this phase is to find an optimal solution for the real problem. Since the artificial variables are not part of the real problem, these variables can now be dropped (they are all zero now anyway). Starting from the BF solution obtained at the end of phase 1, use the simplex method to solve the real problem. Summary of the Two-Phase Method

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  For the example, the problems to be solved by the simplex method in the respective phases are summarized below. (Radiation Therapy Example):  Phase 1 Problem: Minimize Z = X4 + X6, subject to:  0.3xl + 0.1x2 + x3 = 2.7  0.5x x2 + X4 = 6  0.6xl + 0.4x2 - x5 +X6 = 6  and x1 >= 0, x2 >= 0, x3 >= 0, X4 >= 0, x5 >= 0, X6 >= 0.  Phase 2 Problem: Minimize Z = 0.4x x2, subject to:  0.3xl + 0.1x2 + x3 = 2.7  0.5x x2 = 6  0.6xl + 0.4x2 - x5 = 6  and x1 >= 0, x2 >= 0, x3 >= 0, x5 >= 0.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 1  The only differences between these two problems are in the objective function and in the inclusion (phase 1) or exclusion (phase 2) of the artificial variables x4 and X6. Without the artificial variables, the phase 2 problem does not have an obvious initial BF solution. The sole purpose of solving the phase 1 problem is to obtain a BF solution with x4 = 0 and X6 = 0 so that this solution (without the artificial variables) can be used as the initial BF solution for phase 2.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 1  Table 4.13 shows the result of applying the simplex method to this phase 1 problem. [Row 0 in the initial tableau is obtained by converting Minimize Z = X4 + X6 to Maximize (-Z) = -X4 - X6 and then using elementary row operations to eliminate the basic variables X4 and X6 from -Z + X4 + X6 = 0. In the next-to-last tableau, there is a tie for the entering basic variable between x3 and x5, which is broken arbitrarily in favor of x3. The solution obtained at the end of phase 1, then, is (xl, x2, x3, X4, x5, X6) = (6, 6, 0.3, 0, 0, 0) or, after X4 and X6 are dropped, (x1, x2, x3, x5) = (6, 6, 0.3, 0).

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 1  As claimed in the summary, this solution from phase 1 is indeed a BF solution for the real problem (the phase 2 problem) because it is the solution (after you set x5 = 0) to the system of equations consisting of the three functional constraints for the phase 2 problem. In fact, after deleting the x4 and x6 columns as well as row 0 for each iteration, Table 4.13 shows one way of using Gaussian elimination to solve this system of equations by reducing the system to the form displayed in the final tableau.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 2  Table 4.14 shows the preparations for beginning phase 2 after phase 1 is completed. Starting from the final tableau in Table 4.13, we drop the artificial variables (x4 and X6), substitute the phase 2 objective function (-Z = -0.4x x2 in maximization form) into row 0, and then restore the proper form from Gaussian elimination (by algebraically eliminating the basic variables x1 and x2 from row 0). Thus, row 0 in the last tableau is obtained by performing the following elementary row operations in the next-to-last tableau: from row 0 subtract both the product, 0.4 times row 1, and the product, 0.5 times row 3. Except for the deletion of the two columns, note that rows 1 to 3 never change. The only adjustments occur in row 0 in order to replace the phase I objective function by the phase 2 objective function.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 2

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The last tableau in Table 4.14 is the initial tableau for applying the simplex method to the phase 2 problem, as shown at the top of Table Just one iteration then leads to the optimal solution shown in the second tableau: (x1, x2, x3, x5) = (7.5, 4.5, 0, 0.3). This solution is the desired optimal solution for the real problem of interest rather than the artificial problem constructed for phase 1. Phase 2

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Phase 2

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Now we see what the two-phase method has done graphically in Fig Starting at the origin, phase 1 examines a total of four CPF solutions for the artificial problem. The first three actually were corner-point infeasible solutions for the real problem shown in Fig The fourth CPF solution, at (6, 6), is the first one that also is feasible for the real problem, so it becomes the initial CPF solution for phase 2. One iteration in phase 2 leads to the optimal CPF solution at (7.5, 4.5).

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research Compare the Big M and Two-Phase Methods  Begin with their objective functions.  Big M Method: Minimize Z = 0.4x x2 + MX4 + MX6.  Two-Phase Method:  Phase 1: Minimize Z = X4 + X6.  Phase 2: Minimize Z = 0.4x x2.  Because the MX4 and MX6 terms dominate the 0.4x1 and 0.5x2 terms in the objective function for the Big M method, this objective function is essentially equivalent to the phase 1 objective function as long as X4 and/or X6 is greater than zero. Then, when both X4 = 0 and X6 = 0, the objective function for the Big M method becomes completely equivalent to the phase 2 objective function.

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  Because of these virtual equivalencies in objective functions, the Big M and two- phase methods generally have the same sequence of BF solutions: The one possible exception occurs when there is a tie for the entering basic variable in phase 1 of the two- phase method, as happened in the third tableau of Table Notice that the first three tableaux of Tables 4.12 and 4.13 are almost identical, with the only difference being that the multiplicative factors of M in Table 4.12 become the sole quantities in the corresponding spots in Table Consequently, the additive terms that broke the tie for the entering basic variable in the third tableau of Table 4.12 were not present to break this same tie in Table The result for this example was an extra iteration for the two-phase method. Generally, however, the advantage of having the additive factors is minimal. Compare the Big M and Two-Phase Methods

重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research  The two-phase method streamlines the Big M method by using only the multiplicative factors in phase 1 and by dropping the artificial variables in phase 2. (The Big M method could combine the multiplicative and additive factors by assigning an actual huge number to M, but this might create numerical instability problems.) For these reasons, the two-phase method is commonly used in computer codes. Compare the Big M and Two-Phase Methods