COCS5313 Program-2
Due: Wednesday, 2/27/2013
Linear-Programming
(Convex Hull
Checker)
Given n points in the m-dimensional space
(m>=2),
we want to find out whether a given point P
(p1,p2,...,Pm) is inside the Convex hull of these n
points.
This problem can be formulated as a Standard LP
problem
by setting up m+1 equations using n variables as
follows:
a.
Sum of all n non-negative variables equals 1. (One more
equation here).
b.
Linear combination of all corresponding components
of
these n points and n variables must equal the
corresponding
component of the point P.
(M equations here)
We can just minimize any one variable just to see a feasible
solution
is obtained. If it is, then the answer is YES.
Else NO.
Task:
Write a program that, given
a set of n points, finds and prints out those points constituting the Convex
Hull
of
the all points of the input set and those other points not involved in the Hull
with appropriate messages.
Use the following two input sets:
Set
Number-1:
300
90
100
100
100
100
350
60
80
100
100
200
200
100
300
400
0
100
100
100
0
0
50
50
Set
Number-2:
20
60
60
100
20
20
80
0
100
40
100
100
80
35
60
25
70
70
50
82
92
50
75
100
Output Requirements:
For each input set, print
the following with appropriate heading:
1.
All
input points,
2.
All
points constituting the Convex Hull
3.
All
other points inside the Convex Hull
Computational notes:
For this program, you only need the
First-Phase.
1. Make sure all b-values are nonnegative.
2. Introduce m+2 artificial variables such that
a. Xn+m+1 = -cX (The objective function with its
sign
reversed)
b. Xn+m+2 = -(Xn+1 + Xn+2 + ... + Xn+m)
and
hence it is <= 0
c. Xi >= 0 for i = n+1, n+2, ..., n+m
d. Am+1,j = cj for
j=1,2,3,...,n
e. Am+2,j = -(A1j + A2j + ... + Amj) for
j=1,2,...,n
f.
bm+1 = 0
g.
bm+2 = -(b1 + b2 + ..+ bm)
3. A' = A
--------------------
Am+1,1 ......Am+1,n
Am+2,1 ......Am+2,n
Hence, it is
m+2-by-n
4. U = Im+2
The last two rows of U will
be used to determine
the
nonbasic variable entering the basis (row m+2 in Phase
I
and
row m+1 in Phase II)
5. Initial basic solution: Xn+i=bi, i=1,2,...,m+2
PHASE-I: Maximize Xn+m+2
1. If Xn+m+2 < 0, then calculate
Dj
= rowm+2(U) colj(A'), j=1,2,...,n, and continue.
If Xn+m+2
is 0, then goto PHASE II,
step-1.
2. If all Dj >= 0, then Xn+m+2 is its max
and no
feasible solution to the original LP problem
exists.
If at least one Dj < 0, then the variable to be
introduced into the basic set is Xk
such that
Dk
= min Dj for Dj<= j <=
n
Ej
< 0
The variable Xk is selected to enter the basic
set.
If all Ej >= 0, then Xn+m+1 is at its maximum and
the
original LP problem is solved.
3. Compute Yi just like that of Step-3 of
PHASE-I.
4. Find Theta just as in step-4 of PHASE-I.
If all Yi <= 0, the
objective function Xn+m+1 can be made
arbitrarily large, and the original objective function
arbitrarily small accordingly.
In this case, the
computation is terminated. Else, proceed
to
step-5.
5. Compute the new values of basic variables up to
Xm+1
just as in PHASE-I, excluding the last one
Xm+2.
6. Update U only up to row m+1 excluding the last row,
Rowm+2
just as in PHASE-I.
PHASE-II:
Maximize Xn+m+1 while keeping Xn+m+2 at 0.
1. Compute Ej = rowm+1(U)*colj(A')
for j=1,2,...,n
2. Compute Ek = min Ej
1 <= j <=
n
Ej
< 0
The variable Xk is selected to enter the basic
set.
If all Ej >= 0, then Xn+m+1 is at its maximum and
the
original LP problem is solved.
3. Compute Yi just like that of Step-3 of
PHASE-I.
4. Find Theta just as in step-4 of PHASE-I.
If all Yi <= 0, the
objective function Xn+m+1 can be made
arbitrarily large, and the original objective function
arbitrarily small accordingly.
In this case, the
computation is terminated. Else, proceed
to
step-5.
5. Compute the new values of basic variables up to
Xm+1
just as in PHASE-I, excluding the last one
Xm+2.
6. Update U only up to row m+1 excluding the last row,
Rowm+2
just as in PHASE-I.