Principles of Mathematics in Operations Research

116 8 Linear Programming

combination of extreme points plus the canonical combination of extreme

rays (if any) of P.

e) Let the problem be

minxi + 2x2 + 2x3 subject to (xi,X2,X3) € P.

1. Solve.


2. What if we reduce the right hand side of (1) by 3 and (3) by 1.


3. Consider the solution found above. What if we add a new constraint

2xi + 5x2 + X3 < 3.

8.3. Upper bounded simplex

Modify the simplex algorithm without treating the bounds as specific con-

straints but modifying the optimality, entering and leaving variable selection

conditions to solve the following LP problem:

max 2xi + 3x2 + x 3 + 4x 4

s.t.

xa + 2x 2 + 3x 3 + 5x 4 < 30 (1)

xx + x 2 < 13 (2)

3x 3 + x 4 < 20 (3)

1 < xi < 6, 0 < x 2 < 10, 3 < x 3 < 9, 0 < x 4 < 5

a) Start with the initial basis as {si,S2,S3} where si,S2,ss are the corre-

sponding slack variables at their lower bounds. Use Bland's (lexicographically

ordering) rule in determining the entering variables. Find the optimal solu-

tion.

b) Take the dual after expressing the nonzero lower/upper bounds as specific

constraints. Find the optimal dual values by considering only the optimal

primal solution.

8.4. Decomposition
Let a e A be an arc of a network TV = (V,A), where ||V|| = n, \A\ = m.
Given a node i € V, let T(i) be the set of arcs entering to i and H(i) be
the set of arcs leaving from i. Let there be k — 1,..., K commodities to be
distributed; Cka denotes the unit cost of sending a commodity through an arc,
Uka denotes the corresponding arc capacity, du% denotes the supply/demand
at node i, and Ua is the total carrying capacity of arc a.
a) Let Xfc 0 be the decision variable representing the flow of commodity k
across arc a. Give the classical Node-Arc formulation of the minimum cost
multi-commodity flow problem, where commodities share capacity. Discuss
the size of the formulation.