Требуемые знания: знакомство с методами линейного программирования, методы решения транспортной задачи(особенно метод потенциалов).
Год назад, на третьем
курсе в качестве одной из лабораторных работ по курсу «Методы оптимизации» мне задали реализовать решение транспортной задачи, но с одним небольшим условием: перевозки происходят партиями. Это значит, что теперь, в отличие от классической постановки, оплачивается перевозка партии товаров (e.g. 10 штук), и, даже если Вам надо перевезти 11 штук, Вы заплатите за две партии(в один трейлер 11 штук не влезут). Казалось бы, мелкое дополнение, однако как теперь решать задачу, да хотя бы как её формализовать? Как студенту кафедры прикладной математики, мне было не привыкать, что великий google.ru чего-то не знает, но каково же было моё удивление, когда ни его старший брат — англоязычный google, ни тьма перебранных мной книг по теории оптимизации не смогли ответить на этот вопрос.
Год назад, на третьем
курсе в качестве одной из лабораторных работ по курсу «Методы оптимизации» мне задали реализовать решение транспортной задачи, но с одним небольшим условием: перевозки происходят партиями. Это значит, что теперь, в отличие от классической постановки, оплачивается перевозка партии товаров (e.g. 10 штук), и, даже если Вам надо перевезти 11 штук, Вы заплатите за две партии(в один трейлер 11 штук не влезут). Казалось бы, мелкое дополнение, однако как теперь решать задачу, да хотя бы как её формализовать? Как студенту кафедры прикладной математики, мне было не привыкать, что великий google.ru чего-то не знает, но каково же было моё удивление, когда ни его старший брат — англоязычный google, ни тьма перебранных мной книг по теории оптимизации не смогли ответить на этот вопрос.
При решении такой задачи классифицируемые элементы (далее образцы) представляются в виде элементов векторного пространства размерности n. На практике в таких задачах n может быть чрезвычайно большим, например для задачи классификации генов оно может исчисляться десятками тысяч. Большая размерность влечёт, по-мимо высокого времени вычисления, потенциально высокую погрешность численных рассчётов. Кроме того использование большой размерности может требовать больших финансовых затрат (на проведение опытов). Постановка вопроса такова: можно ли и как уменьшить n отбрасыванием незначимых компонент образцов так, чтобы образцы разделялись «не хуже» в новом пространстве (оставались линейно разделимы) или «не сильно хуже».
Карл Гаусс, в своё время, назвал математику царицей всех наук, отдавая ей особое место в сфере человеческого знания. Действительно, совершенно непохожая на другие науки, она скорее служит для них языком или методом изучения. Являясь, пожалуй, самой строгой из всех наук, она не имеет собственного строгого и общепринятого определения. На протяжении всей своей истории, преобразуясь сама, преобразовывалось и понятие о математике. Учёные, в течении всего развития математики, смогли составить скорее не определения математики, а набор афоризмов характеризующий её или представления о ней.