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

[пианист]

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

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

Что-то туплю: почему одной?

мат-ламер в сообщении #1566940 писал(а):

То есть по каждой переменной задачу можно решать отдельно.

Можно поподробнее, как тут можно "разделить" переменные?

[мат-ламер]

пианист в сообщении #1566954 писал(а):

Можно поподробнее, как тут можно "разделить" переменные?

Я понял условие так, что нужно найти максимум линейной функции $f(x)=(c,x)$ (круглые скобки - скалярное произведение) на единичном кубе $0 \leqslant x_i \leqslant 1$ . Решаем отдельно для каждого $i$ задачу нахождения максимума функции $f_i(x_i)=c_ix_i$ на отрезке $$0 \leqslant x_i\leqslant 1$ с очевидным решением $x_i^*$ . В итоге общий ответ в задаче получаем $x^*=(x_1^*,...,x_n^*)$ .

[пианист]

Есть еще условие (1), Ваши $x^*$ ему удовлетворять не обязаны же.

[мат-ламер]

пианист в сообщении #1566960 писал(а):

Есть еще условие (1), Ваши $x^*$ ему удовлетворять не обязаны же.

Извиняюсь. Я наверное неправильно понял условие (а может и правильно, пока не пойму) . Я просто подставил это условие в целевую функцию. В итоге это условие у меня исчезло. Но целевая функция приобрела новый вид.

[B@R5uk]

Если с помощью условия (1) понизить размерность задачи, то, действительно, условие (1) исчезнет, появятся новые искомый вектор и целевая функция. Но область поиска тоже изменится: теперь это будет не гиберкуб, а его гиперсечение, лежащее в гиперплоскости, задаваемой условием (1). Переменные, вообще говоря, не будут сепарабельны.

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

[Aael]

мат-ламер в сообщении #1566923 писал(а):

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

вот я не могу доказать почему это так... и, наверное, поэтому не понимаю, что делать с нулевыми компонентами градиента.

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

Если с помощью условия (1) понизить размерность задачи, то, действительно, условие (1) исчезнет, появятся новые искомый вектор и целевая функция.

Да, но из первой задачи мы узнаём, что все компонеты точки максимума - единицы и нули, кроме какой-то $s$'ой, это поможет нам решить вторую задачу, в которой мы исключаем эту $s$'ю компоненту. Получаем целевую функцию (совпадающую по значениям с исходной) для которой не нужно знать чему равна "дробная" компонента $k_s$:

$$\frac{1}{a_s+b_s}\left[ a_s \sum b_i + \sum\limits_{i\neq s}(a_i b_s -a_s b_i)k_i \right]$$

условия $0\leq k_s \leq 1$ станут такими:

$$0\leq \sum\limits_{i\neq s} b_i - \sum\limits_{i\neq s}(a_i+b_i)k_i \leq a_s + b_s \qquad(3)(4) $$

А компоненты максимума уже известны (учитывая предположение о градиенте):

$$k_i = \left\{ \begin{array}{ccl} 1&\text{если} &a_i / b_i > a_s / b_s \\ 0&\text{если} &a_i / b_i > a_s / b_s \\ ???&\text{если} &a_i / b_i = a_s / b_s \end{array} \right.$$

Теперь, получается, что максимум, который ищем - это некая функция от $s \in \overline{1,n}$ (для $s$ должны выполняться условия (3) и (4)). Если все варинты перебирать, то выходит алгоритм за $O(n^2)$ (выглядит так, что еще быстрее можно). Остаётся случай где "компоненты градиента" равны нулю, там нужно проверить и 0 и 1, что вываливается в экспоненциальное решение.

[пианист]

пианист в сообщении #1566954 писал(а):

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

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

Что-то туплю: почему одной?

А, все, понял. Вопрос снимается.

[мат-ламер]

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

вот я не могу доказать почему это так... и, наверное, поэтому не понимаю, что делать с нулевыми компонентами градиента.

Я должен извиниться. Я неправильно понял условие и все свои посты снимаю. Задача мне кажется выглядит так. Есть $n$-мерный куб. Он пересекается гиперплоскостью. Пересечение это есть $(n-1)$-мерный выпуклый многогранник, все вершины которого лежат на рёбрах куба. И надо найти максимум линейной функции на этом многограннике, который достигается в одной из вершин (не обязательно именно в одной и не обязательно именно в вершине). Стандартный алгоритм предполагает сначала осуществить процесс выхода на этот многогранник. Затем последовательно двигаемся от вершине к вершине так, чтобы увеличивалась целевая функция. Особой специфики тут нет. Можно воспользоваться стандартными программами линейного программирования. Но если есть большой избыток свободного времени и желание разобраться в деталях процесса перевешивает желание быстро получить эффективную программу, то можно и самому чего-то сварганить.

[Aael]

мат-ламер в сообщении #1567028 писал(а):

Я должен извиниться. Я неправильно понял условие и все свои посты снимаю.

Но благодаря вашим рассуждениям было построено решение. Алгоритм такой:
1. Выбираем приближение $k = (1,1,\ldots,1)$ и считаем суммы $S_a=\sum k_i a_i = \sum a_i$ и $S_b=\sum(1-k_i)b_i = 0$
2. Перебираем индексы $s$ в порядке увеличения $a_s / b_s$:
--------- Если $S_a - a_s > S_b + b_s$, то зануляем компоненту $k_s$, и пересчитываем суммы:
----------------- $S_a \leftarrow (S_a - a_s)$
----------------- $S_b \leftarrow (S_b + b_s)$
--------- Иначе (нашли "дробную" компоненту) пишем ответ (это максимум целевой функции):
----------------- $\displaystyle \frac{S_a b_s + S_b a_s}{a_s + b_s}$

Учитывая что почти все компоненты решения состоят из нулей и единиц и работает жадный алгоритм их поиска, то задача прям похожа на все эти "о назначениях", "о разбиение множества", "о одномерном линейном раскрое", "о составлении расписания", на какую-нибудь "бинарную задачу о двух рюкзаках", но не в точных их формулировках. Никогда не видел такую

[B@R5uk]

Задачу о назначениях я решал, поэтому ответственно заявляю, что жадный алгоритм там не работает.

В вашем случае это будет скорее кардинальное отличие, а не схожесть.