Да, разумеется это задачи плохо сформулированы.

З.Ы. Методами линейного/нелинейного программирования обе задачи не решаются по определению.

На мой скромный взгляд в этой теме все не так просто. Самые простые искусственные задачи имеют сложность NP. То есть они вообще не разрешимы на данный момент на реальных размерностях. Выкручиваются применением эвристических методов + вместо общего решения делают допущения, которые позволяет специфика конкретной задачи. Когда появляется слово "вероятность" (а оно в реальной жизни всегда имеет место), начинается ад. Но зато для вероятностных задач не так важно точное решение. В общем вот эта адаптация задачи под реальную жизнь и есть самое сложное, простора для деятельности там много. И на сколько я знал лет 15 назад, именно ребята из частных компаний (сталкивался с авиакомпаниями, про перевозки не берусь судить) двигали науку вперед в этой сфере.

+1, озвученные задачи(в общем случае их можно свести к задаче о ранце и задаче коммивояжера) являются NP полными и если кто и сможет предоставить адекватные способы их решения для произвольного n за линейное время - станет героем, а для фирм занимающихся шифрованием - иудой

вы такие задачи берете из олимпиад по математике что ли? детский сад
В реальной жизни все намного проще и сложней одновременно. И прежде всего, чтобы решать подобную задачу (если она реальна), нужно хотя бы знать какой груз, какие машины с какими кузовами, какие требования к перевозке груза. Куда и что везти (вряд ли это из точки А в точку Б). И имеет ли смысл вообще решать данную задачу (вдруг это просто безсмысленно и не стоит затрат)



вот я себе представляю синьер конса по логистике или тим-лида (или синьер девелопера), который сидит и решает подобный бред

Вот так бывало сидишь, доказываешь гипотезу Рингеля — Коцига... А тут херак, запрос с 8кой упал...

Я эти задачи написал, чтобы проверить, что оппонент понимает что такое класс NP задач и какие проблемы с ними связаны. На собеседованиях никто не ждет, что человек без гугла напишет "алгоритм Хипа без рекурсий".

Если конс по логистике на собеседовании решит такую задачу за полиномиальное время, то миллион баксов от института Клея и Филдсовская премия ему гарантированы. После этого можно уже уходить из науки.

вместо задач лучше бы спросить, какие таски он решал по оптимизации транспортировок, какие знает решения, примеры решений на пальцах. Если надо знание мат апарата, можно об этом напрямую и спросить, какой бекграуннд и тд (тот же пример с задачей комиввояжера, человек должен примерно представлять её и что там делать (чтобы быстро можно было восстановить в памяти), но фактически решать пример на собеседовании это бред)

Никто не просит человека решать NP-трудные задачи на собеседовании. Важно чтобы он их идентифицировать мог. Кроме того, первая задача имеет целый ряд возможных упрощений, которая позволяет отчасти снизить сложность. Вот именно как снизить сложность - интересно поговорить. Однако, если нет мат аппарата, то говорить будет просто не о чем. Эвристики несостоятельны на больших множествах.

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

Может-может! thebestsaper, без обид, но мне кажется, что Вы не вполне осознаете, что из себя представляет класс NP задач. Эти задачи решаются аналитически только на метрическом графе. Во всех остальных случаях это численная оптимизация - High Performance Computing (HPC). Там очень много специфичной математики, железа и софта. Это невозможно просто взять и забыть.

может быть, но при чем тут сап?

Я откуда знаю причем sap. Начиналось все так

Вопрос чайника - а генетический алгоритм + GPU в качестве мощной числодробилки не решает вопрос?

Основная загвоздка - прокладка между GPU и алгоритмом. Следующая проблема - это необходимость гонять данные каждую эпоху между девайсами. Кроме того, Nvidia CUDA в целом - крайне капризная и сырая штуковина. Пока единственное, что она делает хорошо - это перемножает матрицы и генерит кучи случайных чисел. Со всем остальным какая-то бесконечная битва с багами. Самая жесть, когда начинает глючить адресация памяти. В итоге получается как в анекдоте:

Устраивается блондинка на работу в офис…
- Что Вы умеете делать?
- Я умею быстро печатать!
- Сколько знаков в минуту печатаете?
- Ну, примерно, 15'000 знаков в минуту…
- ООО!
- Но, вот, только в результате, такая фигня получается…