Просмотр исходного текста страницы Citeseer/The continuous knapsack set (2014) 10.1.1.642.3962

{{checked|}}
{{citeseerlink|citeseer/The continuous knapsack set (2014) 10.1.1.642.3962|
Мы изучаем выпуклую оболочку непрерывного ранцевого множества, состоящего из одного ограничения неравенства с n неотрицательными целыми и m неотрицательными ограниченными непрерывными переменными. 

При n = 1 это множество является небольшим обобщением множества потока одиночных дуг, изученного Magnanti, Mirchandani, and Vachani (1993). 

Сначала мы покажем, что в любом неравенстве, определяющем грань, число различных ненулевых коэффициентов непрерывных переменных ограничено <m>2^n—n</m>. Наш следующий результат - показать, что при n=2 эта верхняя граница на самом деле равна 1. 

Из этого следует, что при n=2 коэффициенты непрерывных переменных в любом неравенстве, определяющем фасет, после масштабирования равны либо 0, либо 1, и что все фасеты могут быть получены из фасетов непрерывных ранцевых множеств с m=1. 

Затем показано, что выпуклый корпус множеств с n=2 и m=1 задается гранями либо двухпеременных чисто целочисленных ранцевых множеств, либо непрерывных ранцевых множеств с n=2 и m=1, в которых непрерывная переменная не ограничена.  

Мы покажем на примере, что при n=3 ненулевые коэффициенты непрерывных переменных могут принимать различные значения.
}}
{{enddiv}}

[[Категория:CiteSeerArticles]]