[SOLVED] Si152 numerical optimization homework 2

Convert the following problem to a linear program in standard form. [20pts]
max
x∈R4
2×1 − x3 + x4
s.t. x1 + x2 ≥ 5
x1 − x3 ≤ 2
4×2 + 3×3 − x4 ≤ 10
x1 ≥ 0
(1)Use the two-phase simplex procedure to solve the following problem. [40pts]
min
x∈R4
− 3×1 + x2 + 3×3 − x4
s.t. x1 + 2×2 − x3 + x4 = 0
2×1 − 2×2 + 3×3 + 3×4 = 9
x1 − x2 + 2×3 − x4 = 6
x1, x2, x3, x4 ≥ 0
(2)3.1 Q1
Prove that the extreme points of the following two sets are in one-to-one correspondence. [20pts]
S1 = {x ∈ R
n
: Ax ≤ b, x ≥ 0}
S2 = {(x, y) ∈ R
n × R
m : Ax + y = b, x ≥ 0, y ≥ 0}
(3)
, where A ∈ R
m×n, b ∈ R
m.
1
3.2 Q2
Does the set P = {x ∈ R
2
: 0 ≤ x1 ≤ 1} have extreme points? What is its standard form? Does it have extreme
points in its standard form? If so, give a extreme point and explain why it is a extreme point. [20pts]