HOMEWORK 4
2.39
Definition of cone: A set of :
cone must contain the origin.
is a cone when
and
which implies
. Any
Definition of convex cone: A cone S is a convex cone when S is convex.
Definition of convex set:
Definition of extreme point: Let
(
is a convex set when
be convex, then
for some x1 and x2
and
and
- for all
is an extreme point of S when
) implies x=x1=x2
** If I select a convex cone with only one extreme point (0,0): x-axis.
So if I define
) then from the definition of extreme point:
)(
) since
)(
since
we can say that (
we can tell that
If we assume x1=0
since
If we assume
then x2 has to be 0.
x1
since
then x2 has to be negative. This cannot be in our defined
set (positive x axis).
From these assumptions we have proved that (0,0) is only extreme point of a convex cone C.
HOMEWORK 4
2.41
1)
] and
We know that
[
[ ]
, so I will calculate the points as below:
] [ ]
[ ] the points are: x1=6 , x2=5 and the
rest is 0.
So if I make a tableau of all calculations:
B-1
B
[
xB
]
Points (x1,x2,x3,s1,s2)
(6,5,0,0,0)
[ ]
(-4,0,5,0,0)
(-4,0,0,5,0)
[ ]
(1,0,0,0,5)
[ ]
(0,2,3,0,0)
[ ]
(0,2,0,3,0)
(0,-1,0,0,6)
-
] linearly
independent
(determinant is zero)
[
[ ]
(0,0,1,0,4)
[ ]
(0,0,0,1,4)
HOMEWORK 4
Negative values dont count since all the variables have to be greater than or equal to 0.
So the extreme points of this polyhedral are:
(6,5,0) ; (1,0,0) ; (0,2,3) ; (0,2,0) ; (0,0,1) ;(0,0,0)
2)
]
*
We know that:
If we re-write these equations as direction equations:
] and
We know that
[
[ ]
, so I will calculate the points as below:
]
the points are: d1=1 , d2=1/2 , d3=-1/2 and the rest is 0.
] [ ]
HOMEWORK 4
So if I make a tableau of all calculations:
B-1
B
[
[
[
xB
Points (d1,d2,d3,s1,s2)
(1, 1/2, -1/2, 0, 0)
(2/3,1/3,0,-1/3,0)
(1/2,1/2,0,0,-1/2)
] linearly
(0,0,1,-1,0)
]
-
independent
(determinant is zero)
[
(1,0,0,-1,1)
(0,0,1,-1,0)
]
[
(0,1/2,1/2,0,-1)
(0,1,0,1,-1/2)
(0,0,1,-1,0)
Negative values dont count since all the variables have to be greater than or equal to 0. And
here all the points have at least one non-negative point; this polyhedral doesnt have a recession
direction.
HOMEWORK 4
2.47
If we re-write these equations as direction equations:
From the equations above we can tell
and [
[ ]
and
,
] and
therefore we can write directions iff
HOMEWORK 4
] and
We know that
[ ]
, so I will calculate the points as below:
] [ ]
So the points are: d1=1/2 , d2=1/2 , d3=0 , s1=-1/2 and the rest is 0.
So if I make a tableau of all calculations:
B-1
B
[
xB
Points (d1,d2,d3,s1,s2)
(1/2,1/2,0,1/2,0)
]
(1/3,1/3,1/3,0,1/3)
]
(1/2,1/2,0,1/2,0)
]
(0,0,1,-1,1)
]
(0,0,1,-1,1)
Negative values dont count since all the variables have to be greater than or equal to 0. So the
extreme directions of this polyhedral are:
(1/2, 1/2, 0) and (1/3, 1/3, 1/3)
HOMEWORK 4
2.52
I will solve this graphically:
(0, -3) and (3,0)
(0, 4) and (2,0)
1)
2)
3)
So if we solve 1 and 2 , 1 and 3 , 2 and 3 together we get the extreme points which are:
(7/3, -2/3) ; (-3, -6) and (-3,10)
Representing x=(0,1) as a convex combination of the extreme points:
[ ]
All
[
] and
[ ]
HOMEWORK 4
So; [ ]
2.53
Finding Extreme Points
] and
[ ]
B-1
B
[
[
]
Points
(x1,x2,x3,x4,s1,s2)
(-1,0,0,0,0,0)
(-1,0,0,0,0,0)
(-1,0,0,0,0,0)
(-1,0,0,0,0,0)
(-1,0,0,0,0,0)
(0,-3,-2,0,0,0)
[
[
xB
] det=0 so they are
[ ]
(0,1,0,1,0,0)
[ ]
(0,1,0,0,0,2)
linearly independent
[
[
[
]
]
]
[
8
(0,0,-1/2,3/4,0,0)
HOMEWORK 4
]
[
[
]
]
-
] det=0 so they are
(0,0,-2,0,-3,0)
]
]
(0,0,-1/2,0,3/2)
[ ]
(0,0,0,1,1,0)
[ ]
(0,0,0,0,1,2)
linearly independent
[
Negative values dont count since all the variables have to be greater than or equal to 0. So the
extreme points of this polyhedral are:
(0,1,0,1) , (0,1,0,0), (0,0,0,1) and (0,0,0,0)
Finding Extreme Directions
[
We know that:
] and
[ ]
If we re-write these equations as direction equations:
] and
[ ]
HOMEWORK 4
B-1
B
[
Points
(d1,d2,d3,d4,s1,s2)
xB
(-1/4, 3/4,1/2,0,0,0)
(1/3,1/3,0,1/3,0,0)
(0,1,0,0,-1,0)
(1/2,1/2,0,0,0,1)
(-1,0-2,0,3,0)
(2,0,-1,0,0,3)
(1/2,0,0,1/2,1/2,0)
(0,0,0,1,0,-2)
]
[
[ ]
]
[
[
(1,0,0,0,1,2)
]
(0,4/7,2/7,1/7,0,0)
(0,1,0,0,-1,0)
(0,2/3,1/3,0,0,1/3)
]
[
[ ]
10
(4/5,0,-2/5,3/5,0,0)
(0,0,2/3,1/3,4/3,0)
(0,0,0,1,0,-2)
(0,0,1,0,2,1)
HOMEWORK 4
]
[
(0,1,0,0,-1,0)
(0,0,0,1,0,-2)
(0,1,0,0,-1,0)
(0,0,0,1,0,-2)
Negative values dont count since all the variables have to be greater than or equal to 0. So the
extreme directions of this polyhedral are:
(1/3,1/3,0,1/3) ; (1/2,1/2,0,0) ; (1/2,0,0,1/2) ; (1,0,0,0) ; (0,4/7,2/7,1/7) ; (0,2/3,1/3,0) ; (0,0,2/3,1/3)
and (0,0,1,0)
Representing x=(1,1,1,2) as a convex combination of extreme points and non negative
combination of extreme directions:
Representation Theorem:
[ ]
[ ]
[ ]
[ ]
[ ]
11
[ ]
