The Graphical Method: An Example


 Joleen Wilson
 5 years ago
 Views:
Transcription
1 The Graphical Method: An Example Consider the following linear program: Maximize 4x 1 +3x 2 Subject to: 2x 1 +3x 2 6 (1) 3x 1 +2x 2 3 (2) 2x 2 5 (3) 2x 1 +x 2 4 (4) x 1, x 2 0, where, for ease of reference, the four functional constraints have been labelled as (1), (2), (3), and (4). Our goal is to produce a pair of values for x 1 and x 2 that (i) satisfies all constraints and (ii) has the greatest objectivefunction value. A pair of specific values for (x 1, x 2 ) is said to be a feasible solution if it satisfies all constraints. For example, (x 1, x 2 ) = (0, 0) and (x 1, x 2 ) = (1, 1) are feasible solutions, while (x 1, x 2 ) = (1, 1) and (x 1, x 2 ) = (1, 2) are not. Note that the objectivefunction value (OFV) associated with solution (0, 0) is equal to 0 (= ) and that the OFV for solution (1, 1) is equal to 7 (= ). Hence, (1, 1) is the better of these two feasible solutions. Since it is impossible to generate and compare all feasible solutions one by one, we must develop a systematic method to identify the best, or optimal, solution. The basic idea behind the graphical method is that each pair of values (x 1, x 2 ) can be represented as a point in the twodimensional coordinate system. With such a representation, we will be able to visualize the set of all feasible solutions as a graphical region, called the feasible region or the feasible set, and then to identify the optimal solution (assuming it exists). To construct the feasible region, we examine the constraints one at a time, starting with constraint (1). Suppose first that the inequality in constraint (1) is replaced by an equality. Then, it is easily seen that the set of points satisfying 2x 1 + 3x 2 = 6 corresponds to a straight line in the twodimensional plane. To plot this line, we need to identify the coordinates of two distinct points on this line. The standard approach for doing this is to set, alternatingly, one of the two variables to the value 0 and then solve the resulting one equation with one unknown to obtain the corresponding value of the other variable. Thus, if we let x 1 = 0, then x 2 must equal to 2, since x 2 = (6 2x 1 )/3. This yields the point (0, 2). Similarly, by setting x 2 = 0, we obtain the point (3, 0) (since x 1 = (6 3x 2 )/2). The resulting line that 1
2 passes through these two points is shown in Figure LP1. We shall refer to this line as line (1). Observe that line (1) cuts the plane into two halfplanes. All points on one side of this line (including the line itself) satisfy 2x 1 + 3x 2 6; whereas on the other side, 2x 1 + 3x 2 6. Note that (x 1, x 2 ) = (0, 0) satisfies 2x 1 + 3x 2 6, and that (0, 0) lies in the lowerleft direction of line (1). Therefore, we are only interested in the lowerleft portion of the plane. (What if (x 1, x 2 ) = (0, 0) happens to satisfy a given constraint as an equality?) This is also shown in Figure LP1. In this figure, next to line (1), we also placed two arrows that point toward the lowerleft direction. This is intended to indicate what will be called the feasible direction. In summary, after discarding points that violate constraint (1), we are left with the half plane that sits at the lowerleft side of the line defined by 2x 1 + 3x 2 = 6. Thus, each constraint makes a cut on the twodimensional plane, and repeating this process (do this yourself) for the remaining five constraints (the lines x 1 = 0 and x 2 = 0 correspond to the x 2 axis and the x 1 axis, respectively) yields the feasible set. This is shown in Figure LP2, where we have shaded the feasible region. Note that constraint (3) is redundant, in that its removal will not have an impact on the shape of the feasible set. The next question is: Which point within the feasible set is optimal? To answer this, we now look at the objective function. Observe that for any given constant c, the set of points satisfying 4x 1 + 3x 2 = c is again a straight line; and more importantly, that by varying c, we can generate a family of lines (one for each c) with the same slope (i.e., members of this family are parallel). Hence, we can choose an arbitrary c, draw its corresponding line 4x 1 +3x 2 = c, and then visualize the entire family by sliding this line in a parallel manner. In Figure LP3, we show two such lines: 4x 1 + 3x 2 = c 1 and 4x 1 + 3x 2 = c 2, where c 1 12 and c Since both lines do not intersect the feasible region, points on these two lines are not feasible. Note however that the line with the smaller c, namely c 1, is closer to the feasible set. Therefore, if we decrease c further, from c 1, then at some point the resulting parallel lines will eventually touch the feasible region at exactly one point. More precisely, this takes place when the family of objectivefunction lines hits the intersection of lines (1) and (4), a corner point (or an extreme point) of the feasible set. It is now clear that this corner point, marked as D in Figure LP3, must be optimal, since we need to lower c still further to reach the other points within the feasible set. Finally, we note that point D has the coordinates (3/2, 1) (Why?) and therefore, it has an objectivefunction value of 9 (= 4 (3/2) + 3 1). This completes the solution of the problem. More generally, observe that regardless of the slope of the objective function, the above process will always lead to an optimal cornerpoint solution. (This is true even when the objectivefunction line first touches the feasible set at an entire edge; in such a case, we actually have two optimal cornerpoint solutions at the end points of that edge.) This 2
3 implies that we can be assured that an optimal solution (whenever it exists) can always be found at one of the corner points of the feasible set. This fact is remarkable, as it says that we have managed to reduce the task of finding an optimal solution within the entire feasible set, which is a set containing an uncountable number of points, to that of finding an optimal solution within the set of corner points, which is a set containing a finite (why?) number of points. In this particular example, there are only five cornerpoint solutions, namely points A, B, C, D, and E (see Figure LP3). Therefore, the reduction in the search effort is truly significant. The above observation naturally suggests the following simple twostep procedure for solving a linear program: Procedure Search Step 1: Identify the coordinates of all corner points of the feasible set. Step 2: Evaluate the objective function at all of these corner points and pick the best solution. In applying Step 1 to the particular problem above, the location of the corner points can be identified via the graph. For problems with three decision variables, one can still attempt to draw threedimensional graphs. With four or more variables, it becomes impossible to implement the procedure. Therefore, in order for this search procedure to work, we must develop a general method for determining the coordinates of the corner points without relying on a graphical representation of the feasible set; and this will be our next task. In Figure LP3, the coordinates of all five corner points have been explicitly specified. For example, the coordinates of the optimal corner point, point D, is given as (3/2, 1). How does one determine these coordinates? Of course, we can attempt to determine the coordinates of a given point on a graph by visual inspection, but in general, this cannot be expected to yield accurate answers. More constructively, recall that point D is sitting at the intersection of lines (1) and (4). Thus, we can algebraically solve the system of two defining equations, 2x 1 +3x 2 = 6 (1) 2x 1 +x 2 = 4, (4) to obtain the coordinates of this intersection. (In other words, the coordinates of this intersection must satisfy both equation (1) and equation (4).) To do this, subtract equation (4) from equation (1) to yield 2x 2 = 2, implying that x 2 = 1. Next, substitution of x 2 = 1 into equation (1) (or alternatively, into equation (4)) shows that x 1 = 3/2. This verifies 3
4 that (x 1, x 2 ) = (3/2, 1) is indeed the precise location of point D. You should now verify the coordinates of points A, B, C, and E yourself. It is important to realize that this analysis still depends on the availability of the graph. Specifically, we need to know the identify of the two defining equations for each corner point (i.e., we need to know that equations (1) and (4) together define point D, equations (1) and (2) together define point C, equation (2) and x 1 = 0 together define point B, and so on). And we need to know that only these five (Out of how many? See below.) particular combinations of two defining equations give rise to corner points of the feasible region. Therefore, a fundamental question is: Can we free ourselves from the reliance on the graph? A little bit of reflection now leads us to the following procedure: Procedure Corner Points Step 1: From the given set of six equations (including x 1 = 0 and x 2 = 0), choose an arbitrary combination of two equations. Solve this chosen set of two equations to obtain the coordinates of their intersection. (A unique solution may not exist in general; see discussion below.) Step 2: If the solution in Step 1 satisfies all other constraints, then accept it as a cornerpoint solution; otherwise, discard the combination. Step 3: Repeatedly loop through Steps 1 and 2 until all possible combinations are exhausted. Despite its brutal flavor, it turns out that this procedure, indeed, will allow us to generate the coordinates of all cornerpoint solutions. To convince ourselves about the validity of this procedure, consider, for example, the choice of equations (1) and (3): 2x 1 +3x 2 = 6 (1) 2x 2 = 5. (3) From equation (3), we have x 2 = 5/2, which implies that x 1 = (6 3x 2 )/2 = 3/4. Since the resulting solution (x 1, x 2 ) = ( 3/4, 5/2) has a negative value for x 2, it is not feasible. Therefore, the combination of equations (1) and (3) does not lead to a cornerpoint solution. Now, with six equations, it is easily seen that the total number of subsets of two equations is equal to ( ) 6 = 6! 2 2!4! = 15. After cycling through all 15 of these combinations and discarding combinations that do not yield a feasible solution, it can be shown that only five combinations remain; moreover, 4
5 these five combinations correspond precisely to the pairs of defining equations for points A, B, C, D, and E. This establishes (empirically, at least) the validity of the above procedure. Procedure Search and Procedure Corner Points form the backbone of the Simplex method, which is an algebraic procedure for solving linear programs with any (finite) number of variables and constraints. We will return to a full development of this method in a later section. Discussion In general, the feasible region of a linear program may be empty. Procedure Search is meaningful only if the feasible set is not empty. Discovery of an empty feasible set will be discussed later. Consider the linear program: Maximize x 1 +x 2, subject to x 1, x 2 0. Since the values of x 1 and x 2 are allowed to be arbitrarily large, this problem does not have an optimal solution. Note that the feasible region has exactly one corner point, at (0, 0); and that this corner point is not optimal. This clearly is a contradiction to Procedure Search. A linear program of this type is said to be unbounded; we will refine the statement of Procedure Search later to deal with such examples. In general, a given pair of straight lines on the plane may not have a unique intersection point. This could occur if the two lines are parallel, in which case there is no intersection, or if the two lines coincide, in which case every point on the line is an intersection point. Algebraically, this means that a given pair of equations may not have a unique solution. For example, the equation pair has no solution; and the equation pair x 1 +2x 2 = 3 x 1 +2x 2 = 6 x 1 +2x 2 = 3 2x 1 +4x 2 = 6 has an infinite number of solutions. This issue is relevant in Step 1 of Procedure Corner Points, whose statement will also be refined later. 5
OPRE 6201 : 2. Simplex Method
OPRE 6201 : 2. Simplex Method 1 The Graphical Method: An Example Consider the following linear program: Max 4x 1 +3x 2 Subject to: 2x 1 +3x 2 6 (1) 3x 1 +2x 2 3 (2) 2x 2 5 (3) 2x 1 +x 2 4 (4) x 1, x 2
More informationSpecial Situations in the Simplex Algorithm
Special Situations in the Simplex Algorithm Degeneracy Consider the linear program: Maximize 2x 1 +x 2 Subject to: 4x 1 +3x 2 12 (1) 4x 1 +x 2 8 (2) 4x 1 +2x 2 8 (3) x 1, x 2 0. We will first apply the
More informationLinear Programming. Solving LP Models Using MS Excel, 18
SUPPLEMENT TO CHAPTER SIX Linear Programming SUPPLEMENT OUTLINE Introduction, 2 Linear Programming Models, 2 Model Formulation, 4 Graphical Linear Programming, 5 Outline of Graphical Procedure, 5 Plotting
More informationQuestion 2: How do you solve a linear programming problem with a graph?
Question 2: How do you solve a linear programming problem with a graph? Now that we have several linear programming problems, let s look at how we can solve them using the graph of the system of inequalities.
More informationChapter 9. Systems of Linear Equations
Chapter 9. Systems of Linear Equations 9.1. Solve Systems of Linear Equations by Graphing KYOTE Standards: CR 21; CA 13 In this section we discuss how to solve systems of two linear equations in two variables
More informationLINEAR EQUATIONS IN TWO VARIABLES
66 MATHEMATICS CHAPTER 4 LINEAR EQUATIONS IN TWO VARIABLES The principal use of the Analytic Art is to bring Mathematical Problems to Equations and to exhibit those Equations in the most simple terms that
More information1 Solving LPs: The Simplex Algorithm of George Dantzig
Solving LPs: The Simplex Algorithm of George Dantzig. Simplex Pivoting: Dictionary Format We illustrate a general solution procedure, called the simplex algorithm, by implementing it on a very simple example.
More informationQuestion 2: How will changes in the objective function s coefficients change the optimal solution?
Question 2: How will changes in the objective function s coefficients change the optimal solution? In the previous question, we examined how changing the constants in the constraints changed the optimal
More informationWhat does the number m in y = mx + b measure? To find out, suppose (x 1, y 1 ) and (x 2, y 2 ) are two points on the graph of y = mx + b.
PRIMARY CONTENT MODULE Algebra  Linear Equations & Inequalities T37/H37 What does the number m in y = mx + b measure? To find out, suppose (x 1, y 1 ) and (x 2, y 2 ) are two points on the graph of
More informationSolving Systems of Two Equations Algebraically
8 MODULE 3. EQUATIONS 3b Solving Systems of Two Equations Algebraically Solving Systems by Substitution In this section we introduce an algebraic technique for solving systems of two equations in two unknowns
More informationLinear Programming Notes V Problem Transformations
Linear Programming Notes V Problem Transformations 1 Introduction Any linear programming problem can be rewritten in either of two standard forms. In the first form, the objective is to maximize, the material
More informationUsing the Simplex Method to Solve Linear Programming Maximization Problems J. Reeb and S. Leavengood
PERFORMANCE EXCELLENCE IN THE WOOD PRODUCTS INDUSTRY EM 8720E October 1998 $3.00 Using the Simplex Method to Solve Linear Programming Maximization Problems J. Reeb and S. Leavengood A key problem faced
More information5 Systems of Equations
Systems of Equations Concepts: Solutions to Systems of EquationsGraphically and Algebraically Solving Systems  Substitution Method Solving Systems  Elimination Method Using Dimensional Graphs to Approximate
More informationModule1. x 1000. y 800.
Module1 1 Welcome to the first module of the course. It is indeed an exciting event to share with you the subject that has lot to offer both from theoretical side and practical aspects. To begin with,
More informationLINEAR INEQUALITIES. Mathematics is the art of saying many things in many different ways. MAXWELL
Chapter 6 LINEAR INEQUALITIES 6.1 Introduction Mathematics is the art of saying many things in many different ways. MAXWELL In earlier classes, we have studied equations in one variable and two variables
More informationCOMP 250 Fall 2012 lecture 2 binary representations Sept. 11, 2012
Binary numbers The reason humans represent numbers using decimal (the ten digits from 0,1,... 9) is that we have ten fingers. There is no other reason than that. There is nothing special otherwise about
More information3.1 Solving Systems Using Tables and Graphs
Algebra 2 Chapter 3 3.1 Solve Systems Using Tables & Graphs 3.1 Solving Systems Using Tables and Graphs A solution to a system of linear equations is an that makes all of the equations. To solve a system
More informationEQUATIONS and INEQUALITIES
EQUATIONS and INEQUALITIES Linear Equations and Slope 1. Slope a. Calculate the slope of a line given two points b. Calculate the slope of a line parallel to a given line. c. Calculate the slope of a line
More informationSection 7.2 Linear Programming: The Graphical Method
Section 7.2 Linear Programming: The Graphical Method Man problems in business, science, and economics involve finding the optimal value of a function (for instance, the maimum value of the profit function
More informationWhat is Linear Programming?
Chapter 1 What is Linear Programming? An optimization problem usually has three essential ingredients: a variable vector x consisting of a set of unknowns to be determined, an objective function of x to
More information2x + y = 3. Since the second equation is precisely the same as the first equation, it is enough to find x and y satisfying the system
1. Systems of linear equations We are interested in the solutions to systems of linear equations. A linear equation is of the form 3x 5y + 2z + w = 3. The key thing is that we don t multiply the variables
More informationGrade 6 Mathematics Performance Level Descriptors
Limited Grade 6 Mathematics Performance Level Descriptors A student performing at the Limited Level demonstrates a minimal command of Ohio s Learning Standards for Grade 6 Mathematics. A student at this
More informationDetermine If An Equation Represents a Function
Question : What is a linear function? The term linear function consists of two parts: linear and function. To understand what these terms mean together, we must first understand what a function is. The
More informationReview of Fundamental Mathematics
Review of Fundamental Mathematics As explained in the Preface and in Chapter 1 of your textbook, managerial economics applies microeconomic theory to business decision making. The decisionmaking tools
More information3. Evaluate the objective function at each vertex. Put the vertices into a table: Vertex P=3x+2y (0, 0) 0 min (0, 5) 10 (15, 0) 45 (12, 2) 40 Max
SOLUTION OF LINEAR PROGRAMMING PROBLEMS THEOREM 1 If a linear programming problem has a solution, then it must occur at a vertex, or corner point, of the feasible set, S, associated with the problem. Furthermore,
More informationTemperature Scales. The metric system that we are now using includes a unit that is specific for the representation of measured temperatures.
Temperature Scales INTRODUCTION The metric system that we are now using includes a unit that is specific for the representation of measured temperatures. The unit of temperature in the metric system is
More informationSYSTEMS OF LINEAR EQUATIONS
SYSTEMS OF LINEAR EQUATIONS Sstems of linear equations refer to a set of two or more linear equations used to find the value of the unknown variables. If the set of linear equations consist of two equations
More informationHigh School Algebra Reasoning with Equations and Inequalities Solve systems of equations.
Performance Assessment Task Graphs (2006) Grade 9 This task challenges a student to use knowledge of graphs and their significant features to identify the linear equations for various lines. A student
More information1. Briefly explain what an indifference curve is and how it can be graphically derived.
Chapter 2: Consumer Choice Short Answer Questions 1. Briefly explain what an indifference curve is and how it can be graphically derived. Answer: An indifference curve shows the set of consumption bundles
More informationChapter 27: Taxation. 27.1: Introduction. 27.2: The Two Prices with a Tax. 27.2: The PreTax Position
Chapter 27: Taxation 27.1: Introduction We consider the effect of taxation on some good on the market for that good. We ask the questions: who pays the tax? what effect does it have on the equilibrium
More informationLinear Programming. March 14, 2014
Linear Programming March 1, 01 Parts of this introduction to linear programming were adapted from Chapter 9 of Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest and Stein [1]. 1
More informationEdExcel Decision Mathematics 1
EdExcel Decision Mathematics 1 Linear Programming Section 1: Formulating and solving graphically Notes and Examples These notes contain subsections on: Formulating LP problems Solving LP problems Minimisation
More informationPYTHAGOREAN TRIPLES KEITH CONRAD
PYTHAGOREAN TRIPLES KEITH CONRAD 1. Introduction A Pythagorean triple is a triple of positive integers (a, b, c) where a + b = c. Examples include (3, 4, 5), (5, 1, 13), and (8, 15, 17). Below is an ancient
More information10.1 Systems of Linear Equations: Substitution and Elimination
726 CHAPTER 10 Systems of Equations and Inequalities 10.1 Systems of Linear Equations: Sustitution and Elimination PREPARING FOR THIS SECTION Before getting started, review the following: Linear Equations
More informationManagerial Economics Prof. Trupti Mishra S.J.M. School of Management Indian Institute of Technology, Bombay. Lecture  13 Consumer Behaviour (Contd )
(Refer Slide Time: 00:28) Managerial Economics Prof. Trupti Mishra S.J.M. School of Management Indian Institute of Technology, Bombay Lecture  13 Consumer Behaviour (Contd ) We will continue our discussion
More informationChapter 5. Linear Inequalities and Linear Programming. Linear Programming in Two Dimensions: A Geometric Approach
Chapter 5 Linear Programming in Two Dimensions: A Geometric Approach Linear Inequalities and Linear Programming Section 3 Linear Programming gin Two Dimensions: A Geometric Approach In this section, we
More informationLEARNING OBJECTIVES FOR THIS CHAPTER
CHAPTER 2 American mathematician Paul Halmos (1916 2006), who in 1942 published the first modern linear algebra book. The title of Halmos s book was the same as the title of this chapter. FiniteDimensional
More information1. Prove that the empty set is a subset of every set.
1. Prove that the empty set is a subset of every set. Basic Topology Written by MenGen Tsai email: b89902089@ntu.edu.tw Proof: For any element x of the empty set, x is also an element of every set since
More informationMATRIX ALGEBRA AND SYSTEMS OF EQUATIONS
MATRIX ALGEBRA AND SYSTEMS OF EQUATIONS Systems of Equations and Matrices Representation of a linear system The general system of m equations in n unknowns can be written a x + a 2 x 2 + + a n x n b a
More informationThe PointSlope Form
7. The PointSlope Form 7. OBJECTIVES 1. Given a point and a slope, find the graph of a line. Given a point and the slope, find the equation of a line. Given two points, find the equation of a line y Slope
More information1. Graphing Linear Inequalities
Notation. CHAPTER 4 Linear Programming 1. Graphing Linear Inequalities x apple y means x is less than or equal to y. x y means x is greater than or equal to y. x < y means x is less than y. x > y means
More informationSolving Systems of Linear Equations
LECTURE 5 Solving Systems of Linear Equations Recall that we introduced the notion of matrices as a way of standardizing the expression of systems of linear equations In today s lecture I shall show how
More informationLargest FixedAspect, AxisAligned Rectangle
Largest FixedAspect, AxisAligned Rectangle David Eberly Geometric Tools, LLC http://www.geometrictools.com/ Copyright c 19982016. All Rights Reserved. Created: February 21, 2004 Last Modified: February
More informationPractical Guide to the Simplex Method of Linear Programming
Practical Guide to the Simplex Method of Linear Programming Marcel Oliver Revised: April, 0 The basic steps of the simplex algorithm Step : Write the linear programming problem in standard form Linear
More informationSession 7 Bivariate Data and Analysis
Session 7 Bivariate Data and Analysis Key Terms for This Session Previously Introduced mean standard deviation New in This Session association bivariate analysis contingency table covariation least squares
More informationObjectives. Materials
Activity 4 Objectives Understand what a slope field represents in terms of Create a slope field for a given differential equation Materials TI84 Plus / TI83 Plus Graph paper Introduction One of the ways
More informationLinear Programming. April 12, 2005
Linear Programming April 1, 005 Parts of this were adapted from Chapter 9 of i Introduction to Algorithms (Second Edition) /i by Cormen, Leiserson, Rivest and Stein. 1 What is linear programming? The first
More informationx 2 + y 2 = 1 y 1 = x 2 + 2x y = x 2 + 2x + 1
Implicit Functions Defining Implicit Functions Up until now in this course, we have only talked about functions, which assign to every real number x in their domain exactly one real number f(x). The graphs
More informationChapter 3: Section 33 Solutions of Linear Programming Problems
Chapter 3: Section 33 Solutions of Linear Programming Problems D. S. Malik Creighton University, Omaha, NE D. S. Malik Creighton University, Omaha, NE Chapter () 3: Section 33 Solutions of Linear Programming
More informationSystems of Linear Equations in Three Variables
5.3 Systems of Linear Equations in Three Variables 5.3 OBJECTIVES 1. Find ordered triples associated with three equations 2. Solve a system by the addition method 3. Interpret a solution graphically 4.
More informationCHAPTER 3 CONSUMER BEHAVIOR
CHAPTER 3 CONSUMER BEHAVIOR EXERCISES 2. Draw the indifference curves for the following individuals preferences for two goods: hamburgers and beer. a. Al likes beer but hates hamburgers. He always prefers
More informationSolutions of Linear Equations in One Variable
2. Solutions of Linear Equations in One Variable 2. OBJECTIVES. Identify a linear equation 2. Combine like terms to solve an equation We begin this chapter by considering one of the most important tools
More informationFormal Languages and Automata Theory  Regular Expressions and Finite Automata 
Formal Languages and Automata Theory  Regular Expressions and Finite Automata  Samarjit Chakraborty Computer Engineering and Networks Laboratory Swiss Federal Institute of Technology (ETH) Zürich March
More informationPerformance Level Descriptors Grade 6 Mathematics
Performance Level Descriptors Grade 6 Mathematics Multiplying and Dividing with Fractions 6.NS.12 Grade 6 Math : SubClaim A The student solves problems involving the Major Content for grade/course with
More informationLecture L3  Vectors, Matrices and Coordinate Transformations
S. Widnall 16.07 Dynamics Fall 2009 Lecture notes based on J. Peraire Version 2.0 Lecture L3  Vectors, Matrices and Coordinate Transformations By using vectors and defining appropriate operations between
More information1 if 1 x 0 1 if 0 x 1
Chapter 3 Continuity In this chapter we begin by defining the fundamental notion of continuity for real valued functions of a single real variable. When trying to decide whether a given function is or
More information3. Mathematical Induction
3. MATHEMATICAL INDUCTION 83 3. Mathematical Induction 3.1. First Principle of Mathematical Induction. Let P (n) be a predicate with domain of discourse (over) the natural numbers N = {0, 1,,...}. If (1)
More informationMethod To Solve Linear, Polynomial, or Absolute Value Inequalities:
Solving Inequalities An inequality is the result of replacing the = sign in an equation with ,, or. For example, 3x 2 < 7 is a linear inequality. We call it linear because if the < were replaced with
More informationSolving Simultaneous Equations and Matrices
Solving Simultaneous Equations and Matrices The following represents a systematic investigation for the steps used to solve two simultaneous linear equations in two unknowns. The motivation for considering
More informationArrangements And Duality
Arrangements And Duality 3.1 Introduction 3 Point configurations are tbe most basic structure we study in computational geometry. But what about configurations of more complicated shapes? For example,
More informationChapter 2 Solving Linear Programs
Chapter 2 Solving Linear Programs Companion slides of Applied Mathematical Programming by Bradley, Hax, and Magnanti (AddisonWesley, 1977) prepared by José Fernando Oliveira Maria Antónia Carravilla A
More informationSolutions to Math 51 First Exam January 29, 2015
Solutions to Math 5 First Exam January 29, 25. ( points) (a) Complete the following sentence: A set of vectors {v,..., v k } is defined to be linearly dependent if (2 points) there exist c,... c k R, not
More informationSelected practice exam solutions (part 5, item 2) (MAT 360)
Selected practice exam solutions (part 5, item ) (MAT 360) Harder 8,91,9,94(smaller should be replaced by greater )95,103,109,140,160,(178,179,180,181 this is really one problem),188,193,194,195 8. On
More informationChapter 4 One Dimensional Kinematics
Chapter 4 One Dimensional Kinematics 41 Introduction 1 4 Position, Time Interval, Displacement 41 Position 4 Time Interval 43 Displacement 43 Velocity 3 431 Average Velocity 3 433 Instantaneous Velocity
More informationa 11 x 1 + a 12 x 2 + + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + + a 2n x n = b 2.
Chapter 1 LINEAR EQUATIONS 1.1 Introduction to linear equations A linear equation in n unknowns x 1, x,, x n is an equation of the form a 1 x 1 + a x + + a n x n = b, where a 1, a,..., a n, b are given
More informationSolving Quadratic Equations
9.3 Solving Quadratic Equations by Using the Quadratic Formula 9.3 OBJECTIVES 1. Solve a quadratic equation by using the quadratic formula 2. Determine the nature of the solutions of a quadratic equation
More informationLinear Programming for Optimization. Mark A. Schulze, Ph.D. Perceptive Scientific Instruments, Inc.
1. Introduction Linear Programming for Optimization Mark A. Schulze, Ph.D. Perceptive Scientific Instruments, Inc. 1.1 Definition Linear programming is the name of a branch of applied mathematics that
More informationLinear Programming Supplement E
Linear Programming Supplement E Linear Programming Linear programming: A technique that is useful for allocating scarce resources among competing demands. Objective function: An expression in linear programming
More information. P. 4.3 Basic feasible solutions and vertices of polyhedra. x 1. x 2
4. Basic feasible solutions and vertices of polyhedra Due to the fundamental theorem of Linear Programming, to solve any LP it suffices to consider the vertices (finitely many) of the polyhedron P of the
More information7 Gaussian Elimination and LU Factorization
7 Gaussian Elimination and LU Factorization In this final section on matrix factorization methods for solving Ax = b we want to take a closer look at Gaussian elimination (probably the best known method
More informationUnified Lecture # 4 Vectors
Fall 2005 Unified Lecture # 4 Vectors These notes were written by J. Peraire as a review of vectors for Dynamics 16.07. They have been adapted for Unified Engineering by R. Radovitzky. References [1] Feynmann,
More information1.3 LINEAR EQUATIONS IN TWO VARIABLES. Copyright Cengage Learning. All rights reserved.
1.3 LINEAR EQUATIONS IN TWO VARIABLES Copyright Cengage Learning. All rights reserved. What You Should Learn Use slope to graph linear equations in two variables. Find the slope of a line given two points
More informationwith functions, expressions and equations which follow in units 3 and 4.
Grade 8 Overview View unit yearlong overview here The unit design was created in line with the areas of focus for grade 8 Mathematics as identified by the Common Core State Standards and the PARCC Model
More informationPennsylvania System of School Assessment
Pennsylvania System of School Assessment The Assessment Anchors, as defined by the Eligible Content, are organized into cohesive blueprints, each structured with a common labeling system that can be read
More informationPractice with Proofs
Practice with Proofs October 6, 2014 Recall the following Definition 0.1. A function f is increasing if for every x, y in the domain of f, x < y = f(x) < f(y) 1. Prove that h(x) = x 3 is increasing, using
More informationGraphing Linear Equations
Graphing Linear Equations I. Graphing Linear Equations a. The graphs of first degree (linear) equations will always be straight lines. b. Graphs of lines can have Positive Slope Negative Slope Zero slope
More informationThis unit will lay the groundwork for later units where the students will extend this knowledge to quadratic and exponential functions.
Algebra I Overview View unit yearlong overview here Many of the concepts presented in Algebra I are progressions of concepts that were introduced in grades 6 through 8. The content presented in this course
More informationAlgebra Unpacked Content For the new Common Core standards that will be effective in all North Carolina schools in the 201213 school year.
This document is designed to help North Carolina educators teach the Common Core (Standard Course of Study). NCDPI staff are continually updating and improving these tools to better serve teachers. Algebra
More informationCreating, Solving, and Graphing Systems of Linear Equations and Linear Inequalities
Algebra 1, Quarter 2, Unit 2.1 Creating, Solving, and Graphing Systems of Linear Equations and Linear Inequalities Overview Number of instructional days: 15 (1 day = 45 60 minutes) Content to be learned
More informationMATH10212 Linear Algebra. Systems of Linear Equations. Definition. An ndimensional vector is a row or a column of n numbers (or letters): a 1.
MATH10212 Linear Algebra Textbook: D. Poole, Linear Algebra: A Modern Introduction. Thompson, 2006. ISBN 0534405967. Systems of Linear Equations Definition. An ndimensional vector is a row or a column
More informationSolving Linear Programs
Solving Linear Programs 2 In this chapter, we present a systematic procedure for solving linear programs. This procedure, called the simplex method, proceeds by moving from one feasible solution to another,
More informationChapter 6. Linear Programming: The Simplex Method. Introduction to the Big M Method. Section 4 Maximization and Minimization with Problem Constraints
Chapter 6 Linear Programming: The Simplex Method Introduction to the Big M Method In this section, we will present a generalized version of the simplex method that t will solve both maximization i and
More informationSection 1.1 Linear Equations: Slope and Equations of Lines
Section. Linear Equations: Slope and Equations of Lines Slope The measure of the steepness of a line is called the slope of the line. It is the amount of change in y, the rise, divided by the amount of
More informationSensitivity Analysis 3.1 AN EXAMPLE FOR ANALYSIS
Sensitivity Analysis 3 We have already been introduced to sensitivity analysis in Chapter via the geometry of a simple example. We saw that the values of the decision variables and those of the slack and
More information1 Determine whether an. 2 Solve systems of linear. 3 Solve systems of linear. 4 Solve systems of linear. 5 Select the most efficient
Section 3.1 Systems of Linear Equations in Two Variables 163 SECTION 3.1 SYSTEMS OF LINEAR EQUATIONS IN TWO VARIABLES Objectives 1 Determine whether an ordered pair is a solution of a system of linear
More informationLecture 2. Marginal Functions, Average Functions, Elasticity, the Marginal Principle, and Constrained Optimization
Lecture 2. Marginal Functions, Average Functions, Elasticity, the Marginal Principle, and Constrained Optimization 2.1. Introduction Suppose that an economic relationship can be described by a realvalued
More informationSystems of Linear Equations
Systems of Linear Equations Beifang Chen Systems of linear equations Linear systems A linear equation in variables x, x,, x n is an equation of the form a x + a x + + a n x n = b, where a, a,, a n and
More informationA Detailed Price Discrimination Example
A Detailed Price Discrimination Example Suppose that there are two different types of customers for a monopolist s product. Customers of type 1 have demand curves as follows. These demand curves include
More informationMATH2210 Notebook 1 Fall Semester 2016/2017. 1 MATH2210 Notebook 1 3. 1.1 Solving Systems of Linear Equations... 3
MATH0 Notebook Fall Semester 06/07 prepared by Professor Jenny Baglivo c Copyright 009 07 by Jenny A. Baglivo. All Rights Reserved. Contents MATH0 Notebook 3. Solving Systems of Linear Equations........................
More information7 Relations and Functions
7 Relations and Functions In this section, we introduce the concept of relations and functions. Relations A relation R from a set A to a set B is a set of ordered pairs (a, b), where a is a member of A,
More informationTOPIC 4: DERIVATIVES
TOPIC 4: DERIVATIVES 1. The derivative of a function. Differentiation rules 1.1. The slope of a curve. The slope of a curve at a point P is a measure of the steepness of the curve. If Q is a point on the
More informationChapter 25: Exchange in Insurance Markets
Chapter 25: Exchange in Insurance Markets 25.1: Introduction In this chapter we use the techniques that we have been developing in the previous 2 chapters to discuss the trade of risk. Insurance markets
More informationStandard Form of a Linear Programming Problem
494 CHAPTER 9 LINEAR PROGRAMMING 9. THE SIMPLEX METHOD: MAXIMIZATION For linear programming problems involving two variables, the graphical solution method introduced in Section 9. is convenient. However,
More informationSystems of Linear Equations: Two Variables
OpenStaxCNX module: m49420 1 Systems of Linear Equations: Two Variables OpenStax College This work is produced by OpenStaxCNX and licensed under the Creative Commons Attribution License 4.0 In this section,
More informationLet s explore the content and skills assessed by Heart of Algebra questions.
Chapter 9 Heart of Algebra Heart of Algebra focuses on the mastery of linear equations, systems of linear equations, and linear functions. The ability to analyze and create linear equations, inequalities,
More informationCRLS Mathematics Department Algebra I Curriculum Map/Pacing Guide
Curriculum Map/Pacing Guide page 1 of 14 Quarter I start (CP & HN) 170 96 Unit 1: Number Sense and Operations 24 11 Totals Always Include 2 blocks for Review & Test Operating with Real Numbers: How are
More informationReflection and Refraction
Equipment Reflection and Refraction Acrylic block set, planeconcaveconvex universal mirror, cork board, cork board stand, pins, flashlight, protractor, ruler, mirror worksheet, rectangular block worksheet,
More information3.2. Solving quadratic equations. Introduction. Prerequisites. Learning Outcomes. Learning Style
Solving quadratic equations 3.2 Introduction A quadratic equation is one which can be written in the form ax 2 + bx + c = 0 where a, b and c are numbers and x is the unknown whose value(s) we wish to find.
More information3.3. Solving Polynomial Equations. Introduction. Prerequisites. Learning Outcomes
Solving Polynomial Equations 3.3 Introduction Linear and quadratic equations, dealt within Sections 3.1 and 3.2, are members of a class of equations, called polynomial equations. These have the general
More informationAnswer Key for California State Standards: Algebra I
Algebra I: Symbolic reasoning and calculations with symbols are central in algebra. Through the study of algebra, a student develops an understanding of the symbolic language of mathematics and the sciences.
More information