Даны векторы $c \in \mathbb{R}^n$, $b \in \mathbb{R}^m$ и матрица $A \in \mathbb{R}^{m \times n}$ такая что $m < n$ и $\mathrm{rank}(A) = m$
Производство оптимального количества товара при ресурсных ограничениях: \begin{align*} &\max_x c^{\top}x \\ \text{s.t. } & Ax \leq b\\ & x_i \geq 0, \; i = 1,\dots, n, \end{align*} где $x_i$ - количество $i$-го товара, $c_i$ - прибыль от производства $i$-го товара, $b_i$ - доступное количество $i$-го материала, $a_{ij}$ - количество $i$-го материала, который требуется для производства единицы $j$-го товара.
Потоки в сетях: транспортная задача, задача о максимальном потоке, выбор пути в коммуникационной сети для передачи сообщения с минимальной стоимостью
Задача регрессии в нормах $\ell_1$ и $\ell_{\infty}$ может быть сведена к задаче линейного программирования
Вопросы:
Теорема Все угловые точки являются вершинами соответствующего многоугольника.
Дана угловая точка $x$, соответствующая ей матрица базиса $B$ и множество индексов $\mathcal{B}$.
Матрица $U$ имеет ранг 1
Итоговая сложность $O(m^2)$ в лучшем случае, если оценки замещения вычисляются с выбором ведущего элемента, и $O(mn)$ в худшем случае, если необходимо вычислить все оценки замещения.
Пусть допустимое множество непусто и каждая угловая
точка невырождена.
Тогда симплекс-метод останавливается за конечное число итераций:
Определение. Угловая точка называется вырожденной, если она содержит больше $n - m$ нулевых компонент.
Вопрос: что геометрически означает вырожденность?
Р. Бланд - американский математик,
один из создателей теории ориентированных матроидов.
Для поиска начальной угловой точки составим следующую вспомогательную задачу при условии, что $b_i \geq 0, \; i =1, \dots,m$. Этого легко добиться умножение строк матрицы $A$ и соответствующих элементов $b$ на $-1$. \begin{align*} & \min_{z, y} y_1 + \ldots + y_m \\ \text{s.t. } & Az + y = b\\ & z \geq 0, \; y \geq 0 \end{align*}
Идея: объединить двухфазный симплекс-метод в однофазный
\begin{align*} & \min_{z, y} c^{\top}z + M(y_1 + \ldots + y_m) \\ \text{s.t. } & Az + y = b\\ & z \geq 0, \; y \geq 0 \end{align*}$M$ - произвольное большое положительное число, можно оставить как параметр и при необходимости сделать достаточно большим
Примеры приведены здесь
In [1]:
import scipy.optimize as scopt
import numpy as np
n = 1000
m = 10
c = 10 * np.random.rand(n)
b = np.random.rand(m)
A = np.random.randn(m, n)
res = scopt.linprog(c, A, b, bounds=[(-1, None) for i in range(n)])
print(res)
В задаче \begin{align*} & \max_{x \in \mathbb{R}^n} 2^{n-1}x_1 + 2^{n-2}x_2 + \dots + 2x_{n-1} + x_n\\ \text{s.t. } & x_1 \leq 5\\ & 4x_1 + x_2 \leq 25\\ & 8x_1 + 4x_2 + x_3 \leq 125\\ & \ldots\\ & 2^n x_1 + 2^{n-1}x_2 + 2^{n-2}x_3 + \ldots + x_n \leq 5^n\\ & x \geq 0 \end{align*} начиная с точки $x_0 = 0$ и следуя симплекс-методу, необходимо обойти $2^n - 1$ вершину.
Упражнение: решите эту задачу для $n = 2$ и $n = 3$, и обобщите результат, получив решение для произвольного $n$.
In [3]:
def generate_KleeMinty_test_problem(n):
c = np.array([2**i for i in range(n)])
c = c[::-1]
bounds = [(0, None) for i in range(n)]
b = np.array([5**(i+1) for i in range(n)])
a = np.array([1] + [2**(i+1) for i in range(1, n)])
A = np.zeros((n, n))
for i in range(n):
A[i:, i] = a[:n-i]
return -c, A, b, bounds
In [4]:
n = 5
c, A, b, bounds = generate_KleeMinty_test_problem(n)
print(c)
print(A)
print(b)
print(bounds)
In [5]:
res = scopt.linprog(c, A, b, bounds=bounds)
print(res)
In [6]:
n_list = range(3, 16)
n_iters = np.zeros(len(n_list))
times = np.zeros(len(n_list))
for i, n in enumerate(n_list):
c, A, b, bounds = generate_KleeMinty_test_problem(n)
res = scopt.linprog(c, A, b, bounds=bounds, options={"maxiter": 2**max(n_list)})
time = %timeit -o scopt.linprog(c, A, b, bounds=bounds, options={"maxiter": 2**max(n_list) + 1})
n_iters[i] = res.nit
times[i] = time.best
In [7]:
USE_COLAB = False
%matplotlib inline
import matplotlib.pyplot as plt
if not USE_COLAB:
plt.rc("text", usetex=True)
plt.figure(figsize=(20,5))
plt.subplot(1, 2, 1)
plt.plot(n_list, n_iters - np.array([2**n - 1 for n in n_list]), label="$K_t - K_{exp}$")
# plt.semilogy(n_list, [2**n - 1 for n in n_list], label="Theory")
plt.xlabel("Dimension, $n$", fontsize=24)
plt.ylabel("Number of iterations, $K$", fontsize=24)
plt.xticks(fontsize=18)
plt.yticks(fontsize=18)
plt.legend(fontsize=18)
plt.subplot(1, 2, 2)
plt.semilogy(n_list, times)
plt.xlabel("Dimension, $n$", fontsize=24)
plt.ylabel("Computation time", fontsize=24)
plt.xticks(fontsize=18)
_ = plt.yticks(fontsize=18)