Principles of Mathematics in Operations Research

7 Convex Sets This chapter is compiled to present a brief summary of the most important concepts related to convex sets. Followi ...

94 7 Convex Sets /3xi, X2 (xi ^ X2) G X 3 x = (1 - a)xi + ax2, 0 < a < 1. Proposition 7.1.4 v4nj/ extreme point is on boun ...

7.2 Hyperplanes and Polytopes 95 Fig. 7.3. Cones 7.2 Hyperplanes and Polytopes The most important type of convex set (aside from ...

96 7 Convex Sets Proof. Let xi 6 H, and translate by -x\ obtaining M = H — x\. Since H is a hyperplane, M is an (n — 1)-dimensio ...

7.3 Separating and Supporting Hyperplanes 7.3 Separating and Supporting Hyperplanes Theorem 7.3.1 (Separating Hyperplane) Let X ...

98 7 Convex Sets Theorem 7.3.2 (Supporting Hyperplane) Let X be a convex set, and let y be a boundary point of X. Then, there is ...

7.4 Problems 99 We will show that X = K. Assume that 3y e X 3 y $ K. Then, by Theorem 7.3.1, there is a hyperplane separating y ...

100 7 Convex Sets 7.3. Cube and Octahedron Characterize cubes and octahedrons with the help of three dimensional cube C3, and oc ...

7.5 Web material 101 http://dimax.rutgers.edu/"sj aslar/ http://dogfeathers.com/j ava/hyperslice.html http://en.wikipedia.org/wi ...

102 7 Convex Sets http://www.mizar.org/JFM/Vol15/convex3.html http://www.ms.uky.edu/~sills/webprelim/sec013.html http://www.mtho ...

8 Linear Programming A Linear Programming problem, or LP, is a problem of optimizing a given linear objective function over some ...

104 8 Linear Programming Canonical form: Min z =c x + 6 y s.t. Ax — y = 6 x,y>0 <S=> Example 8.1.2 Min z =2x + 3y s.t. ...

8.1 The Simplex Method 105 Definition 8.1.3 The extreme points of the feasible set are exactly the basic feasible solutions of A ...

106 8 Linear Programming and basic: it is feasible because x > 0, it is basic since we again have n zero components. xe is go ...

8.2 Simplex Tableau cTN-cTBB~xN = [2 0] - [0 3 cTN-cTBB~lN= [2 0] - [0 3] ] -12' 0 1 "3-2' 2 -1 [l Ol 2-1 ( X Z2 v-4 3 Since t ...

108 8 Linear Programming Adding the cost row I \B-lN\\B-lb -N^0 B-lN B~xb Oc^-c^B-^ll-cSB-^ The last result is the complete tabl ...

8.2 Simplex Tableau 109 :J-:0---0 : / 0:0---0 *•••*: 1 B~lN\ '•.B~lN :ce — Cnv: • B-lb -dB^b For all the rows except the obje ...

110 8 Linear Programming "10 0 1 00 3-2 2-1 -4 3 6" 6 -18 X y 2i y\x z 2 \\RHS- -III 2 III ^ §0|0 -10 77ms, x* = 2 = y* => ...

8.4 Duality Theory 111 If Cjy — XN > 6, stop; the current solution is optimal. Otherwise, if the most negative component is ...

112 8 Linear Programming same: The minimum of cTx equals the maximum ofyTb. Otherwise, if optimal vectors do not exist, either b ...