Bi-objective simplex

Bi-objective simplex linear programming algorithm

Usage

Revised simplex method

revised_simplex.m

Write a linear programming problem as

$$ \matrix{ \min & z = c\cdot x \\ \text{s.t.} & A\cdot x = b \\ & x \geq 0 } $$

Input arguments:

• A matrix, coefficients of left-side of equality constraints.
• b column vector, right-side of equality constraints.
• c row vector, coefficients of minimize objective function.
• max_iter integer, maximum iterations of either phase 1 or phase 2 of revised simplex.
• tol double, tolerance when calculating the reduced cost of revised simplex.

Returned values:

• solved integer, same as exitflag of MATLAB linprog. (only implemented -3, -2, 0, 1)
• x column vector, optimal feasible solution.

Bi-objective simplex method

biobjective_simplex.m

Write a linear programming problem as

$$ \matrix{ \min & z = C\cdot x \\ \text{s.t.} & A\cdot x = b \\ & x \geq 0 } $$

Input arguments:

• A matrix, coefficients of left-side of equality constraints.
• b column vector, right-side of equality constraints.
• c 2-row matrix, coefficients of minimize objective functions, where each row corresponds to an objective.
• max_iter integer, maximum iterations of either stage 1 or stage 2 of bi-objective simplex.
• tol double, tolerance when calculating the reduced cost of revised simplex.

Returned values:

• solved integer, same as exitflag of MATLAB linprog. (only implemented -3, -2, 0, 1)
• x matrix, where each column is an optimal feasible solution corresponds to a value of $\lambda$.
• lambda row vector. It lists the thresholds of $\lambda$, which decreases from 1 to 0, that makes the feasible basis of $\bar{c} = \lambda c_1 + (1 - \lambda) c_2$ changes.