Я должен выразить условие И в линейной программе. Булева переменная z принимает значение 1, если обе булевы переменные x и y принимают значение 1. В противном случае z принимает значение 0. Как мне записать это в линейной программе?
Логическое выражение в линейной программе
comment
Отвечает ли это на ваш вопрос? cs.stackexchange.com/questions/12102/
- person DV82XL schedule 29.07.2020
Ответы (1)
В чистой линейной программе логические выражения невозможны.
Если вы находитесь в (смешанной) целочисленной программе и все x, y, z являются двоичными переменными, вы можете реализовать AND следующим образом.
- z >= x+y-1
- z <= x
- z <= y
Здесь первое обеспечивает z=1, если x=y=1, а последние два заставляют z=0, если любое из двух не равно 1.
Как отметил @Erwin Kalvelagen в комментариях, это лучше расслаблено, чем формулировка с использованием 2z <= x+y.
person
SimonT
schedule
29.07.2020
Большое спасибо. С первым разобрался, а со вторым не разобрался. Еще раз спасибо за вашу помощь.
- person Arun Sen; 29.07.2020
Это совершенно правильно. Однако более сильная формулировка:
z ≤ x, z ≤ y, z ≥ x+y-1. Это настолько жестко, что мы можем ослабить x, чтобы оно было непрерывным между 0 и 1. Иногда это может иметь значение.
- person Erwin Kalvelagen; 04.08.2020
Хорошая точка зрения! Я понял это сам после ответа на вопрос. Я просто еще не изменил ответ. Но спасибо, что снова указали на это.
- person SimonT; 04.08.2020
Теперь я изменил ответ, чтобы показать более сильную формулировку.
- person SimonT; 04.08.2020
