Странная ЗЛП

[Andrey_Kireew]

Возникла такая задачи линейного программирования:
$\begin{cases} a_1\cdot x_{11}+a_2\cdot x_{12}+...+a_2\cdot x_{1p}\geqslant C_1\\ -a_1\cdot x_{11}-a_2\cdot x_{12}-...-a_2\cdot x_{1p}\leqslant -C_1\\ ....................................\\ a_1\cdot x_{n1}+a_2\cdot x_{n2}+...+a_2\cdot x_{np}\geqslant C_n\\ -a_1\cdot x_{n1}-a_2\cdot x_{n2}-...-a_2\cdot x_{np}\leqslant -C_n\\ a_i\leqslant 1 \forall i \\ a_1\cdot O_1+a_2\cdot O_2+...+a_2\cdot O_p \to max\\ } \end{cases}$

как видно, соседние пары неравенств сводятся к уравнениям
$\begin{cases} a_1\cdot x_{11}+a_2\cdot x_{12}+...+a_2\cdot x_{1p}= C_1\\ ....................................\\ a_1\cdot x_{n1}+a_2\cdot x_{n2}+...+a_2\cdot x_{np}= C_n\\ a_i\leqslant 1 \forall i \\ a_1\cdot O_1+a_2\cdot O_2+...+a_2\cdot O_p \to max\\ } \end{cases}$

в принципе, если выбросить $a_i\leqslant 1 \forall i$, то задачу можно решить,
а потом уже, "усечь" найденные $a_i$ по этим условиям.

Корректно ли это будет, или так нельзя?

[teleglaz]

Что-то у вас там в Вашей ЗЛП странное написано, кажется мне.

А как "усекать" то будем?

[Someone]

Andrey_Kireew в сообщении #1323381 писал(а):

как видно, соседние пары неравенств сводятся к уравнениям

Не сводятся. Поскольку второе неравенство получается из первого умножением на $-1$, то одно из неравенств можно просто выбросить.

Andrey_Kireew в сообщении #1323381 писал(а):

в принципе, если выбросить $a_i\leqslant 1 \forall i$, то задачу можно решить,
а потом уже, "усечь" найденные $a_i$ по этим условиям.

Нет, нельзя. Надо либо считать неравенства $a_i<1$ наравне с остальными, увеличивая размерность задачи, либо применять специальный вариант симплекс-метода.

P.S. Э-э-э… У Вас переменные $a_1$ и $a_2$? Всего две штуки? А "иксы" с индексами — это коэффициенты?

[Andrey_Kireew]

Someone в сообщении #1323385 писал(а):

Не сводятся. Поскольку второе неравенство получается из первого умножением на $-1$, то одно из неравенств можно просто выбросить.

ещё как сводится
$ -a\geqslant -b \to a\leqslant b$

Someone в сообщении #1323385 писал(а):

Нет, нельзя. Надо либо считать неравенства $a_i<1$ наравне с остальными, увеличивая размерность задачи, либо применять специальный вариант симплекс-метода.

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

PS: конечно "иксы" коэффициенты, а Вы про что подумали? переменные там только $a$, и их не две, а много.

-- 29.06.2018, 18:29 --

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

[Someone]

Andrey_Kireew в сообщении #1323394 писал(а):

ещё как сводится
$ -a\geqslant -b \to a\leqslant b$

Поскольку ещё и $a\leqslant b\rightarrow-a\geqslant-b$, то эти неравенства равносильны, и из них двух можно спокойно оставить одно. Поэтому никакого равенства не получится. Равенство получилось бы, если бы у Вас была пара неравенств $-a\geqslant-b$ и $a\geqslant b$, которые как раз друг из друга не следуют.

Andrey_Kireew в сообщении #1323394 писал(а):

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

Разумеется. Но есть специальная модификация симплекс-метода для задач с ограниченными переменными. Поищите в литературе.

-- Пт июн 29, 2018 19:49:46 --

Andrey_Kireew в сообщении #1323394 писал(а):

переменные там только $a$, и их не две, а много.

В вашей системе есть только $a_1$ и $a_2$. Посмотрите внимательнее.

Andrey_Kireew в сообщении #1323394 писал(а):

конечно "иксы" коэффициенты, а Вы про что подумали?

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

Andrey_Kireew в сообщении #1323394 писал(а):

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

Ну конечно, если знаки неравенства написать в одну сторону, то пара неравенств равносильна одному уравнению. Только зачем так писать? Пишите сразу уравнения.

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

"Усекать" - нельзя. И равенства перестанут выполняться, и оптимальности не станет. Решать, как общую задачу ЛП.
Предполагаю, что Вы всё же исправите пары неравенств, как уже было сказано, это тавтология, в нынешнем виде они повторяют друг друга. Если же там одинаковые знаки неравенств, то пара неравенств действительно задаёт равенство.
Поскольку условие на то, что неизвестные больше или равны нулю, отсутствует (опять же предположу, что это так, а не Вы его забыли), можно ввести такое, обычное для ЛП условие, заменив
$y_i=1-a_i$, внеся соответственные поправки в равенства. И решать обычным образом.

[Andrey_Kireew]

Someone в сообщении #1323436 писал(а):

Равенство получилось бы, если бы у Вас была пара неравенств $-a\geqslant-b$ и $a\geqslant b$, которые как раз друг из друга не следуют.

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

Someone в сообщении #1323436 писал(а):

Разумеется. Но есть специальная модификация симплекс-метода для задач с ограниченными переменными. Поищите в литературе.

Спасибо! сейчас посмотрю.

Вообще всё это не плод моего воображения. В одном источнике как раз, такие неравенства "чудесным образом" превращаются в область определения параметров. Но там вывода этих формул нет, только конечный результат. Я сам составил систему, и всё приходит именно к этому. На счёт превращения неравенств в уравнения, без введения дополнительных переменных я понял, а вот с ограниченными переменными непонятно. Причём несколько примеров, у меня получаются ограничения на переменные, там же - вместо этих ограничений приводится область определения, вот, например, так $a \in[0,n]^n$ - где $a$ - это вектор.
Получается, будто бы эти параметры изначально не могут выходить за эти пределы.

-- 29.06.2018, 21:06 --

Евгений Машеров и тогда эти ограничения на переменные $a$ можно отбросить?

[Someone]

Andrey_Kireew в сообщении #1323443 писал(а):

вот, например, так $a \in[0,n]^n$ - где $a$ - это вектор

То есть, ограничения $a_i\geqslant 0$ молча предполагаются? (Я считал, что они выполняются, хотя Вы их и не написали. Симплекс-метод требует, чтобы переменные были неотрицательными.)

Andrey_Kireew в сообщении #1323443 писал(а):

и тогда эти ограничения на переменные $a$ можно отбросить?

Если неравенства $a_i\geqslant 0$ не предполагались, то да, после указанной замены неравенства $a_i\leqslant 1$ превратятся в $y_i\geqslant 0$. Именно так, как это требуется для симплекс-метода.

Вы всё-таки выпишите правильный вид вашей задачи. Без лишних неравенств (пары $a\geqslant b$ и $-a\geqslant-b$ замените равенствами вида $a=b$) и не пропуская никаких существенных неравенств (включая $a_i\geqslant 0$, если они есть).

[Andrey_Kireew]

У меня получается такая система:

$\begin{cases} a_1\cdot x_{1,1}+a_2 \cdot x_{1,2}+...+a_p\cdot x_{1,p}=c_1}\\ a_1\cdot x_{2,1}+a_2 \cdot x_{2,2}+...+a_p\cdot x_{2,p}=c_2}\\ ................. \\ a_1 \cdot x_{n,1}+a_2 \cdot x{n,2}+...+a_p\cdot x_{n,p}=c_n}\\ a_1 \leqslant 1\\ a_2 \leqslant 1\\ ...................... \\ a_n \leqslant 1\\ a_1\cdot o_1+a_2 \cdot o_2+...+a_p\cdot o_n \to max} \end{cases}$

а вот такую я вижу в мануале:
$\begin{cases} a_1\cdot x_{1,1}+a_2 \cdot x_{1,2}+...+a_p\cdot x_{1,p}=c_1}\\ a_1\cdot x_{2,1}+a_2 \cdot x_{2,2}+...+a_p\cdot x_{2,p}=c_2}\\ ................. \\ a_1 \cdot x_{n,1}+a_2 \cdot x{n,2}+...+a_p\cdot x_{n,p}=c_n}\\ a_1\cdot o_1+a_2 \cdot o_2+...+a_p\cdot o_n \to max\\ a\in [0,1]^n } \end{cases}$

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

-- 29.06.2018, 21:49 --

На счёт $a\geqslant 0$ это так. Здесь не то, чтобы они такими полагались, просто они ищутся среди положительных чисел (простой симплекс-метод).

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

Так всё-таки - есть ограничения на неотрицательность?

[Andrey_Kireew]

Ну да, они неотрицательные.

[Someone]

Andrey_Kireew в сообщении #1323473 писал(а):

Ну да, они неотрицательные.

А в вашем варианте не написано, что они неотрицательные, хотя я специально просил Вас это написать.

Andrey_Kireew в сообщении #1323450 писал(а):

эти ограничения не рассматриваются, в решении задачи они не участвуют

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

[Andrey_Kireew]

Вот смотрите как у них там записано
$max(y'a|X'a=kX'e_n, a\in [0,1]^n)$
это запись в матричной форме, но думаю понятно, $a$ - это собственно искомый вектор, $e_n$ - вектор из $n$ единиц, $k$ - скалярная константа.

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

Вычисляются они там методом обратной матрицы (m-simplex).
Но есть одна тонкость, не входящие в план переменные $a_i$ могут принимать значения не только $0$, но и $1$, т.е. два фиксированных значения. Может это не просто область определения, а она используется и в решении.

-- 30.06.2018, 00:43 --

Написано, что это

Цитата:

Such "bounded variables" problems

, я так понимаю как раз то, на что Вы Someone и намекали. Значит это не просто область определения, видимо таким путём указаны эти ограничения, собственно это те же неравенства и есть + условия не отрицательности. (правда у меня , условия не отрицательности в явном виде не получились, может что то упустил).

[Andrey_Kireew]

Да, это ЗЛП с ограниченными переменными, прочитал Someone методичку, по Вашей ссылке, там есть такой раздел. Формулы очень похожи на формулы в моём мануале. Теперь немножко прояснилось. В общем буду разбираться. Спасибо за помощь.

[Someone]

Andrey_Kireew в сообщении #1323483 писал(а):

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

А Вы, когда учились в школе, так и не поняли, что запись $a\in[0,1]$ означает в точности то же самое, что двойное неравенство $0\leqslant a\leqslant 1$ или система неравенств $\begin{cases}a\geqslant 0\\ a\leqslant 1\end{cases}$, и вовсе не означает никакой области определения? Хотя, конечно, может использоваться и используется для записи области определения. Но область определения можно записать и комбинациями неравенств. Вообще, в задачах линейного программирования встречаются исключительно линейные функции, область определения которых совпадает с $\mathbb R^n$. Поэтому я рекомендую Вам не употреблять термин "область определения". Во избежание недоразумений.