Рассмотрим задачу поиска максимума в массиве. (8.1...

Пусть дан массив чисел $a_1,\dots,a_n$. Требуется найти его максимум:

$$\max_{i=1,\dots,n} a_i.$$

(8.1.1) Формулировка как задачи линейного программирования

Введем переменную $x$, которая должна быть не меньше каждого элемента массива. Тогда минимум такой верхней границы и будет максимумом массива:

$$\begin{aligned} \min \quad & x \\ \text{при условиях}\quad & x \ge a_i,\quad i=1,\dots,n. \end{aligned}$$

Это и есть задача линейного программирования.

Почему это верно

Ограничения требуют, чтобы $x$ был верхней границей всех $a_i$.
Среди всех верхних границ мы выбираем наименьшую.
Но наименьшая верхняя граница конечного набора чисел — это как раз

$$x^*=\max_i a_i.$$

---

(8.1.2) Двойственная задача

Приведем прямую задачу к стандартному виду. Ограничения

$$x \ge a_i$$

можно записать как

$$-x \le -a_i.$$

Тогда прямая задача:

$$\begin{aligned} \min \quad & x \\ \text{при условиях}\quad & -x \le -a_i,\quad i=1,\dots,n. \end{aligned}$$

Построим двойственную задачу. Для каждого ограничения введем двойственную переменную $y_i \ge 0$. Получаем:

$$\begin{aligned} \max \quad & \sum_{i=1}^n a_i y_i \\ \text{при условиях}\quad & \sum_{i=1}^n y_i = 1, \\ & y_i \ge 0,\quad i=1,\dots,n. \end{aligned}$$

---

Интерпретация двойственной задачи

Условия

$$y_i \ge 0,\qquad \sum_{i=1}^n y_i = 1$$

означают, что вектор $y$ задает выпуклую комбинацию элементов массива.

Целевая функция:

$$\sum_{i=1}^n a_i y_i$$

— это взвешенное среднее элементов массива.

Значит, двойственная задача говорит:

выбрать неотрицательные веса с суммой 1 так, чтобы взвешенное среднее элементов массива было как можно больше.

Но любое взвешенное среднее не может превышать максимальный элемент массива. Поэтому оптимум достигается, если весь вес положить на индекс $k$, где

$$a_k=\max_i a_i.$$

То есть оптимальное решение двойственной задачи:

$$y_k=1,\qquad y_i=0 \ (i\ne k).$$

И тогда

$$\sum_{i=1}^n a_i y_i = a_k = \max_i a_i.$$

---

Физический смысл

Можно понимать $y_i$ как “долю внимания”, “массу” или “вероятность”, распределенную по элементам массива.

Тогда двойственная задача ищет такое распределение массы по элементам, которое максимизирует среднее значение. Очевидно, чтобы среднее было максимально, всю массу нужно сосредоточить на самом большом элементе.

То есть:

• прямая задача ищет минимальную общую верхнюю границу для всех элементов;
• двойственная задача ищет наилучшее распределение веса по элементам, чтобы получить наибольшее возможное среднее;
• обе дают одно и то же значение:

$$\max_i a_i.$$

---

Если нужно, я могу еще записать это в матричной форме $Ax \ge b$ и аккуратно вывести двойственную задачу по правилам ЛП.