L, C, c1, c2,... cN, p1min, p1max, p2min, p2max...pNmin, pNmax — постоянные
надо найти такие x1, x2, ... xN что бы
L = x1 + x2 + .. + xN
p1min <= x1 <= p1max
p2min <= x2 <= p2max
....
pNmin <= xN <= pNmax

и при этом
C = c1*x1 + c2*x2 + ... cN*xN — была минимальна

Это линейное программирование уже и его только симплексом можно? Или чем-то попроще решить? Желательно без каких-либо библиотек (т.е. простым алгоритмом).

Здравствуйте, Ватакуси, Вы писали:

В>Это линейное программирование уже и его только симплексом можно? Или чем-то попроще решить? Желательно без каких-либо библиотек (т.е. простым алгоритмом).

Нет, это не совсем оно. В задаче линейного программирования ограничения — любой выпуклый многогранник, у тебя — после простого преобразования координат — просто куб, явно можно проще решить. Поищи, где гиперплоскость целевой функции пересекает грани куба. Экстремальные значения будут на линии пересечения с гранями, может даже с ребрами куба, надо подумать немного. Хотя, конечно, симплекс метод тоже с таким справится.

Ну и это, ты не сказал, должны ли например x_i быть целыми. Тогда это ILP и симплекс метод тоже не катит.

В>>Это линейное программирование уже и его только симплексом можно? Или чем-то попроще решить? Желательно без каких-либо библиотек (т.е. простым алгоритмом).

A>Нет, это не совсем оно. В задаче линейного программирования ограничения — любой выпуклый многогранник, у тебя — после простого преобразования координат — просто куб, явно можно проще решить. Поищи, где гиперплоскость целевой функции пересекает грани куба. Экстремальные значения будут на линии пересечения с гранями, может даже с ребрами куба, надо подумать немного. Хотя, конечно, симплекс метод тоже с таким справится.

A>Ну и это, ты не сказал, должны ли например x_i быть целыми. Тогда это ILP и симплекс метод тоже не катит.

Нет, могут быть дробными (в пределах 0.1)
Да, можно этот пересечение куба и плоскости (для произвольного N) выразить уравнением?

Здравствуйте, Ватакуси, Вы писали:

В>Это линейное программирование уже и его только симплексом можно? Или чем-то попроще решить? Желательно без каких-либо библиотек (т.е. простым алгоритмом).
В общем случае линейка, решить можно в Excel его же встроенным солвером.

Здравствуйте, Ватакуси, Вы писали:

В>Да, можно этот пересечение куба и плоскости (для произвольного N) выразить уравнением?

Это не нужно. Можешь действовать так:

Преобразуй координаты в y_i, чтобы перейти к гиперкубу для ограничений. Тогда неравенства ограничений примут вид
0 ≤ y_i ≤ 1.


Выбери любую вершину, например из всех нулей. Рассчитай в ней целевую функцию . Перебирай соседние N вершин, пока не найдешь вершину, где целевая функция больше. Переходи в нее. Повторяй для N-1 новых соседних вершин. Если во всех соседних вершинах целевая функция не больше, чем в текущей, то максимум найден.

Координаты вершин гиперкуба — вектора из 0 и 1. Соседние вершины получаются изменением одной из координат, например для N = 4 соседями вершины с нулевыми координатами будут

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

Все. Вот такая простая вариация симплекс-метода для гиперкуба получается.

Здравствуйте, Ватакуси, Вы писали:

В>C = c1*x1 + c2*x2 + ... cN*xN — была минимальна

В>Это линейное программирование уже и его только симплексом можно? Или чем-то попроще решить? Желательно без каких-либо библиотек (т.е. простым алгоритмом).

Если ты про ту задачу, что в "о работе" публиковал, то у тебя еще и бинарные переменные есть, которые только 0/1 могут быть (ветряк включен/выключен). И обычным LP ты тут не отделаешься.
Да и не нужно оно тут, скорее всего. Тут можно сначала сортировать по возрастанию Сi, находить такое i, что сумма Pmaxj j=1...i >= P.
И потом пытаться решать задачу меньшей размерности, оставив только j < i, чтобы получить сумму, попадающую в диапазон [P — Pmax i, P — Pmin i]. Правда, нужно еще подумать, как лучше быть, когда есть станции, у которых Ci одинаковы, а диапазоны мощностей разные.

Здравствуйте, andyp, Вы писали:

A>Преобразуй координаты в y_i, чтобы перейти к гиперкубу для ограничений. Тогда неравенства ограничений примут вид
A>0 ≤ y_i ≤ 1.

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

Здравствуйте, Lexey, Вы писали:

L>Ты забыл, что у него есть еще ограничение на L. Оно к такому виду не приводится.

Не забыл, а просто невнимательно прочитал собственно условие. Это ж вообще тогда не задача максимизации линейного функционала при ограничениях получается. Каюсь, вечерние затупы в течение двух дней.

В>>C = c1*x1 + c2*x2 + ... cN*xN — была минимальна

В>>Это линейное программирование уже и его только симплексом можно? Или чем-то попроще решить? Желательно без каких-либо библиотек (т.е. простым алгоритмом).

L>Если ты про ту задачу, что в "о работе" публиковал, то у тебя еще и бинарные переменные есть, которые только 0/1 могут быть (ветряк включен/выключен). И обычным LP ты тут не отделаешься.
Это её вариация. Зачем бинарные? Остальные же тоже могут работать или нет.

L>Да и не нужно оно тут, скорее всего. Тут можно сначала сортировать по возрастанию Сi, находить такое i, что сумма Pmaxj j=1...i >= P.
L>И потом пытаться решать задачу меньшей размерности, оставив только j < i, чтобы получить сумму, попадающую в диапазон [P — Pmax i, P — Pmin i]. Правда, нужно еще подумать, как лучше быть, когда есть станции, у которых Ci одинаковы, а диапазоны мощностей разные.
Я пробовал так подойти, но непонятно, что делать с разными (или даже пересекающимися) диапазонами мощностей.

Здравствуйте, Ватакуси, Вы писали:

В>Это линейное программирование уже и его только симплексом можно? Или чем-то попроще решить?

В такой постановке — это простой жадный алгоритм. Для начала рассмотрим, когда все ci >= 0. Тогда:

1. Берем все xi = pimin
   
2. Сортируем все безобразие по возрастанию ci.
   
3. Далее по одной станции (в порядке возрастания c) добавляем мощность. Либо столько, сколько нужно до L, либо до максимума станции (что меньше).

Так как мы берем мощность за минимум денег, у нас будет минимальная сумма.

Для случая отрицательных c — почти тоже самое. Только мы выбираем xi=pimax для ci<0. Затем смотрим на сумму. И либо увеличиваем мощность оставшихся станций при недолете, либо уменьшаем мощностью существующих (начиная с максимальных негативных ci) при перелете.

Только вот подобный алгоритм в исходной задаче не работает. Там есть разрывы в функции (xi=0) и структура совсем другая. Я могу с ходу предложить два пути.

Первый — перебор по всем подмножествам "нулевых" x. Т.е. мы считаем, что какое-то подмножество x=0 а остальные — нет. И используем для ненулевых предыдущий алгоритм. Это будет неплохо работать при количестве станций до 20-30 штук. С использованием многопоточности — еще несколько штук можно добавить. Сложность — O(2^N*N*log(N))

Если станций может быть много но итоговая мощность и мощность станции в разумных пределах, работает динамическое программирование.

Пусть S(e, k) — минимальная стоимость получить e энергии (в целых числах, в них проще, умножить на 10 должно быть не слишком сложно) используя только первые k станций. Считается так:

S(0, 0) = 0
S(e, 0) = inf
S(e, k+1) = min(S(e, k), min({ (S(e-o, k) + o*ck) | forall o: pkmin <= o <= pkmax }))

Обходим, считаем. Еще запоминаем, по какой ветке пришли (т.е. использовалась ли станция k и если да, то на сколько). Растет линейно от количества станций. И как произведение максимальных мощностей.

Отмечу еще и в этой теме, что в случае всех ветряков — это задача о рюкзаке. Которая, в свою очередь, NP-полная. Так что на хорошее полиномиальное решение можете даже не надеяться.