Linear Programming MSIS 683 Homework 2

by user

Category: Documents





Linear Programming MSIS 683 Homework 2
Linear Programming
MSIS 683
Homework 2
Instructor: Farid Alizadeh
Due Date: Wednesday September 25, 2000 in class
last updated on October 19, 2000
1. Solve the linear program in problem 2.4 on page 22 of your text using dual
simplex method. Show your work step by step.
2. Solve the linear programming problem 2.1 on page 21 of your text using
the revised simplex method.
3. show that in general finding any feasible solution for a linear program in
canonical form is equivalent to finding the optimal solution. To do so
prove that any optimal solution of
min cT x
s.t. Ax ≥ b
is feasible for the system of inequalities
Ax ≥ b
AT y ≤ c
cT x − bT y ≥ 0
4. Use the duality theorem of linear programming to prove the Farkas lemma:
Lemma Suppose A ∈ <m×n , and b ∈ <m are given. Then:
Either: there is x ∈ <n such that x ≥ 0 and Ax = b
Or: there is y ∈ <m such that AT y ≥ 0 and bT y < 0.
5. Use Farkas lemma to prove the arbitrage theorem:
lemma Let there be n outcomes of an experience and m different wagers
on these outcomes. Let R ∈ <m×n be the payoff (or loss) matrix, that
MSIS 683, Fall 2000
Homework 2
Due date: 10/25/00
is if wager i is made and outcome j occurs, then a payoff of Rij is made
for each wager i. An arbitrage is a vector x such that xTP
R > 0. Prove
that either there exists a probability vector p ∈ <n (with i pi = 1 and
pi ≥ 0) such that Rp = 0, or there exist an arbitrage vector x.
6. Suppose that in a game a die with 6 sides is rolled. It costs $1 for a
contestant to enter the game. Contestants have to guess the outcome of
the die. If they guess i and i comes they will win $Ri otherwise they win
nothing. (Clearly Ri > 0.) Show that there is no betting scheme that
results in a sure positive win if and only if
1 + Ri
7. Consider the upper bounded linear programming problem:
min cT x
s.t. Ax = b
where u is a given vector of upper bounds on x.
(a) Find the dual of this problem.
(b) Let y be the dual variable corresponding to equality constraints Ax =
b, that is yi corresponds to constraint aTi x = bi where ai is the ith
row of A. Show that the complementary slackness theorem in this
case implies:
• if xi = ui then ci < aTi y
• if 0 < xi < ui then ci = aTi y
• if ci > aTi x then xi = 0.
8. There is in general a strong connection between optimization theory and
free competition in economics. Here is an example: Suppose there are n
economic activities (for example building a factory, or a shopping mall or
homes etc.) and that are to be individually located on n distinct parcels
of land. If activity i is located on parcel j then it yields sij units of value
(say in dollars).
If the assignment of activities to the land parcels are made by a central
(say some state agency) it might be made so as to maximize
. Thus the optimization problem may be written as:
s x
Pi,j ij ij
= 1 for all land parcels j
1 for all activities i
xij ∈ {0, 1}
MSIS 683, Fall 2000
Homework 2
Due date: 10/25/00
Even though this is an integer programming problem, it turns out that if
we replace xij ∈ {0, 1} by xij ≥ 0, the results will automatically be 0 or 1.
Now consider the problem from the view of free competition. Suppose that
rather than a central authority determining the assignment, the individuals (entrepreneurs or companies) that can conduct the economic activities
bid for the land parcel in an auction and thereby establish prices.
(a) Show that there exist a set of activity prices pi for i = 1, 2, . . . , n
and a set of land prices qj for j = 1, 2, . . . , n such that for all i, j :
pi + qj ≥ sij with equality holding if in the optimum activity i is
assigned to parcel j.
(b) Show that part 8a implies that if activity i is optimally assigned to
land parcel j, and if j0 is any other parcel, then sij − qj ≥ sij0 − qj .
Give an economic interpretation of this result and explain the relation
between free competition and optimality in this context.
Fly UP