У меня есть семейство задач линейного программирования: максимизировать учетом , . Элементы , и являются неотрицательными целыми числами, строго положительными. ( также должен быть целым, но я буду беспокоиться об этом позже.)
В моем приложении часто случается, что коэффициенты и таковы, что упрощенный однопроходный алгоритм дает оптимальное решение для каждого выбора : однопроходный алгоритм определяет элементы в последовательности, выбирая каждый - максимально возможное значение, согласующееся с уже определенными значениями . В симплексном языке последовательность ввода переменных составляет от до и заканчивается через шагов. Это экономит много времени по сравнению с полнофункциональным симплексом.
Этот алгоритм работает, когда столбцы и элементы отсортированы от «дешевых» до «дорогих». «Дешевая» переменная - это столбец с обычно небольшими значениями, для которого соответствующий элемент большой: для этого элемента вы получаете много выходных данных с не очень большой нагрузкой на ограничение . Таким образом, алгоритм просто говорит «делай сначала простые вещи».
Мой вопрос: какое свойство и может заверить нас, что этот упрощенный алгоритм работает для всех ? Моя первоначальная гипотеза состояла в том, что ненулевые элементы должны увеличиваться в каждой строке, но это не правильно.
Вот несколько примеров, все с : , , , , Для всего этого последовательный алгоритм дает оптимальное решение для всех значений (путем численных экспериментов). это единственный, для которого все перестановки столбцов также работают. а также особенно сбивают с толку, так как выглядит дороже, чем а также дороже чем ,
Я был бы чрезвычайно признателен за любые ссылки на литературу, за любые подобные проблемы, или любые предложения вообще. Должны быть и другие случаи, когда некоторые переменные могут быть определены как «более дешевые», чем другие, и их можно безопасно сделать в первую очередь. Со всей работой, проделанной за линейное программирование на протяжении многих лет, кажется, что-то похожее должно было произойти, но я не смог найти это.
источник
Благодаря предложению профессора Спиви я, наконец, нашел то, что я считаю современным: Ульрих Фейгл, Алан Дж. Хоффман и Уолтер Керн, «Характеристика неотрицательных матриц Бокса-Жадности», SIAM J. Disc. Математика 9 (1996), стр. 1-6. Матрица «жадная», если алгоритм, который я описал выше, дает оптимальное решение для всехb , Матрица является «коробчато-жадной», если жадный алгоритм дает оптимальное решение с дополнительным условиемx≤d для всех b и все d≥0 , Ясно, что жадность в поле - более сильное условие, чем жадность.
Всегда предполагайте, чтоc1≥⋯≥cn>0 , Файгл, Хоффман и Керн доказывают этоA коробка жадная, если и только если она не имеет k×(k+1) (для любой k ) подматрица формы ⎛⎝⎜⎜⎜⎜⎜r1r2⋮rks1s2⋱sk⎞⎠⎟⎟⎟⎟⎟ с каждым rj>0 а также ∑i:si>0risi>1 , При извлечении подматриц допускаются произвольные перестановки строк, но не столбцов, а также разрешается произвольная подстановка строк и столбцов. Таким образом, в частности, сk=1 ненулевые элементы в каждом ряду A должно быть неубывающим.
К сожалению, оказывается, что в моей задаче матрицы не являются жадными, хотя я все еще считаю, что они жадные. Например, в моемA1 выше условие нарушается, и эта матрица не является жадной, хотя она жадная. Насколько я знаю, результатов по выявлению жадных матриц нет.
источник
Самым простым примером для чего-то подобного может быть проблема дробного ранца, когда предметы разрешено дробить. Эту проблему (и ее двойственное значение) можно решить, отсортировав элементы по прибыли на вес, выбрав самую длинную последовательность в этом порядке и выполнив дробную часть последнего элемента.
источник