Как доказать, что мы не можем иметь X (j) + и X (j) - одновременно положительные в LP?

Question

Как мы все знаем, в задаче линейного программирования любая переменная x (j) заменяется на разницу между двумя не отрицательными варами.

X (J) = X (к) + - X (J) -

Как мы знаем, что в базовом растворе, мы никогда не можем иметь Х (к) + и X (J) - одновременно строго положительный?

Должен ли я предполагать проблему и работать над ней, разбивая каждую переменную на x + - x-? Но это ничего не докажет мне в конце концов.

Answer 1

Прежде всего: в учебниках обычно говорится, что метод Simplex может обрабатывать только неотрицательные переменные. Это неверно: решатели LP могут обрабатывать свободные переменные напрямую. Мы по-прежнему можем использовать разделение переменных в некоторых интересных случаях моделирования, даже если мы можем использовать свободные переменные.

Если цель минимизирует |X| (т.е. это сводит к минимуму Xplus + Xmin), мы не знаем, как Xplus и Xmin может быть отличен от нуля.

Существует также другой, более экзотический аргумент. Если столбцы матрицы LP Xplus и Xmin те же, за исключением знака, они не могут отображаться как в базе (если бы они были, базовая матрица B была бы единственной). Этот аргумент, конечно, связан с методом Симплекс.

Но есть случаи, когда и Xplus, и Xmin могут быть отличными от нуля. Это иногда называют non-convexity. В этом случае можно было бы необходимо добавить бинарная переменная B с:

Xplus <= M*B 
Xmin <= M*(1-B) 

Answer 2

Обычно это не имеет значения: так как вы заинтересованы в значении х, и (5, 5) и (0, 0) для примером являются действительное представление того же решения x = 0.

Зачем вам одно из значений, которое должно быть 0?