Bi-objective simplex

Bi-objective simplex linear programming algorithm

Usage

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.

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.