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

[Aael]

Есть задача линейной оптимизации. Подскажите, пожалуйста, не могу понять, что именно это за "тип" у неё (транспортная задача, задача о потоке, итд)? Или к какой стандартной задаче её можно свести. Решаю её сейчас в общем виде, стандартными методами, но, уверен, что есть какое-то более быстрое решение. Достаточно численного приближенного решения. Задача:
$a,b$ - два вектора из $\mathbb{R}_{>0}^n$
Нужно найти максимум функции $F(k) = a\cdot k$, при условии, что $k\in[0,1]^n$ и $a\cdot k = (e-k)\cdot b$, где $e$ - это вектор из единиц, т.е:

$\begin{array}{lc} F(k) = \sum_i a_i k_i \rightarrow \max& \\ \sum_i a_ik_i = \sum_i(1-k_i)b_i &(1) \\ 0\leq k_i \leq 1, \quad i=\overline{1..n}&(2) \end{array}$

Получается, условие (2) задает n-мерный куб, а (1) - плоскость, на которой лежит точка максимума k. И, соответственно, найдется n-1 компонета искомого вектора k принадлежащаяя множеству {0, 1}. Очень похоже на "задачу о назначениях", но и тут я не пойму как прикрутить к ней первое условие. Пример с числами:

$\begin{array}{l} a = (18, 33, 36, 46, 6, 41, 15, 27) \\ b = (\,22, \hphantom{0}8, \hphantom{0}6, 16, 8, 13, 10, 13) \\ \text{при } k = (0, 1, 1, 0, 0, 0.24074074, 0, 0) \text{ достигается максимум:} \\ F(k) = \left\lVert\begin{array}{ll} k \cdot a &= 33 + 36 + 0.24074074 \cdot 41 \\ (e-k) \cdot b &= 22 + 16 + 8 + 0.759259\cdot 13 + 10 + 13 \\ \end{array}\right\rVert = 78.87037034 \end{array}$

[B@R5uk]

Aael, что-то у вас вектор k, при котором, вы говорите, достигается максимум, не соответствует условию задачи: у него есть компонента, отличная от 0 или 1.

Так же, тут что-то нехорошее творится в задаче: без каких-либо ограничений на вектора a и b гиперплоскость, соответствующая условию (1) может не проходить ни через одну вершину гиперкуба. Тогда вообще никаких решений не будет. Более того, в n-мерном пространстве киперкуб имеет $2^n$ вершин, в то время как гиперплоскость задаётся только $n+1$ неколлинеарной точкой. (В гиперкубе есть коллинеарные точки. Кстати, интересный вопрос: через сколько вершин единичного n-мерного гиперкуба максимум может проходить n-мерная гиперплоскость?) Я это к тому, уверены ли вы, что вы описали ту задачу, что нужно?

[Aael]

B@R5uk по условию $k_i$ лежит в интервале от 0 до 1. Мы как бы делим n единиц каждую на две доли, например 0.2+0.8: одна уходит к $a_i$ (получается $0.2\cdot a_i$), другая к $b_i$ (получается $0.8\cdot b_i$), и считаем две суммы: \sum$k_ia_i$ и $\sum(1-k_i)b_i$ (все что ушло к $a$ и к $b$). Обе суммы должны быть равны, например, числу $M$ - это "ограничение" в задаче. А само значение $M$ нужно максимизировать и найти (компоненты k при которых оно достигается не важны).

То, что есть такая точка максимума в которой как минимум все доли кроме одной (т.е. n-1 штука) будут равны нулям или единицам - это уже мои соображения.

[B@R5uk]

Aael в сообщении #1566760 писал(а):

$k_i$ лежит в интервале от 0 до 1.

О! Тогда извиняюсь. Подумалась почему-то дискретность. Наверно, потому, что я когда-то дискретную оптимизационную задачу ставил.

[пианист]

Aael в сообщении #1566756 писал(а):

Очень похоже на "задачу о назначениях",

Эмм. А что чему соответствует? В задаче о назначениях у неизвестной, по идее, должно быть два индекса, где они в Вашей задаче?

[B@R5uk]

Я тоже как-то не очень понимаю в чём вопрос. Вот есть задача линейного программирования. У неё есть различного вида постановки, в том числе в канонической форме, это я понимаю. Дальше, есть задачи, которые так или иначе сводятся к задаче линейного программирования, это я тоже понимаю. Некоторые из них, возможно, даже имеют собственное более эффективное решение. Задача ТС, конечно, записана не в канонической форме, но очень близка к ней. Что, собственно, можно тут ещё хотеть? Как по мне, так тут можно только взять и решить.

[Евгений Машеров]

Второе условие сводится к $\Sigma_i(a_i+b_i)k_i=\Sigma_i b_i$

[Null]

Она же за $n\log n$(сортировка) решается?

[Евгений Машеров]

Чёт-то у меня напрашивается тривиальный алгоритм (и да, это никакая не задача о назначении).
Если бы не было условия (1), ответ был бы - для всех $a_i>0$ $k_i=1$, иначе $k_i=0$
Но в этом случае условие (1) может нарушаться. И надо какие-то $k_i$ изменить, восстанавливая соблюдение условия. Причём в силу того, что задача линейная, менять до упора, в 0 (или, для отрицательных $a_i$, в единицу), все, кроме, возможно, одной переменной, которой "точно настраиваем равенство".

[B@R5uk]

Евгений Машеров в сообщении #1566900 писал(а):

для всех $a_i>0$

Они и так все больше нуля:

Aael в сообщении #1566756 писал(а):

$a,b$ - два вектора из $\mathbb{R}_{>0}^n$

Евгений Машеров в сообщении #1566900 писал(а):

И надо какие-то $k_i$ изменить, восстанавливая соблюдение условия.

Проблема в этом: какие именно индексы взять? Без какой-либо стратегии это экспоненциальный перебор, что гораздо хуже ЗЛП в среднем (в худшем случае там тоже экспоненциальный перебор, если мне память не изменяет). А наивное зануление начиная с наименьших работать не будет, потому что сечение плоскостью куба — это хитрый многоугольник (от треугольника до шестиугольника), а сечение гиперплоскостью гиперкуба — объект ещё хитрее.

-- 17.10.2022, 10:25 --

Евгений Машеров в сообщении #1566900 писал(а):

все, кроме, возможно, одной переменной, которой "точно настраиваем равенство"

Фактически, вы утверждаете, что максимум будет лежать в вершине или на ребре каркаса гиперсечения. Это очень жёсткое требование. Почему не в каком-то более хитром направлении?

[Null]

B@R5uk в сообщении #1566903 писал(а):

Фактически, вы утверждаете, что максимум будет лежать на вершине или ребре каркаса гиперсечения. Это очень жёсткое требование. Почему не в каком-то более хитром направлении?

Просто из 2 любых переменных одну можно увести в 0 или 1, возможно увеличив целевую функцию.

[B@R5uk]

Да, пожалуй. Когда целевая функция линейная так и будет.

[Евгений Машеров]

B@R5uk в сообщении #1566903 писал(а):

Фактически, вы утверждаете, что максимум будет лежать в вершине или на ребре каркаса гиперсечения. Это очень жёсткое требование. Почему не в каком-то более хитром направлении?

Линейная функция.

[мат-ламер]

Aael в сообщении #1566756 писал(а):

но, уверен, что есть какое-то более быстрое решение.

Я тоже так думаю. Достаточно посмотреть на на знаки компонент градиента целевой функции. И в зависимости от этих знаков соответствующая компонента решения будет $0$ или $1$ (ну, или любое число между этими значениями) .

[мат-ламер]

Aael в сообщении #1566756 писал(а):

Есть задача линейной оптимизации. Подскажите, пожалуйста, не могу понять, что именно это за "тип" у неё

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