Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Классические задачи. Описание и комментарии

26 апреля 2011 года в 16:50

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

23 апреля 2011 года в 17:28

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

22 апреля 2011 года в 09:13

Здесь описана так называемая задача китайского почтальона. Готовим собственную публикацию на тему: Чем отличается задача китайского почтальона от задачи коммивояжера и иллюстрации.

22 апреля 2011 года в 08:36

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of transportation, distribution and logistics.[1] Often the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. Implicit is the goal of minimizing the cost of distributing the goods. Many methods have been developed for searching for good solutions to the problem, but for all but the smallest problems, finding global minimum for the cost function is computationally complex.

22 апреля 2011 года в 08:33

In computer science and graph theory, the Canadian Traveller Problem (CTP) is a generalization of the shortest path problem to graphs that are partially observable. In other words, the graph is revealed while it is being explored, and explorative edges are charged even if they do not contribute to the final path.

This optimization problem was introduced by Christos Papadimitriou and Mihalis Yannakakis in 1989 and a number of variants of the problem have been studied since. The name supposedly originates from conversations of the authors who learned of the difficulty Canadian drivers had with snowfall randomly blocking roads. The stochastic version, where each edge is associated with a probability of independently being in the graph, has been given considerable attention in operations research under the name "the Stochastic Shortest Path Problem with Recourse" (SSPPR).

22 апреля 2011 года в 08:17

LMatrix: Материал в англоязычной части Википедии гораздо полнее и интереснее предложенного на русском.

The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

21 апреля 2011 года в 14:43

Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари).

20 апреля 2011 года в 09:30

A simplified description of a new computing procedure for the Hitchcock-Koopmans transportation problem is given, together with a step by step solu¬tion of an illustrative example. The procedure is based on Kuhn's combinatorial algorithm for the assignment problem and a simple "labeling process" for solving maximal flow problems in networks. The proposed computation appears to be considerably more efficient than the specialized form of the simplex method which is in common use.

20 апреля 2011 года в 08:29

Транспортная задача (ТЗ) - один из наиболее важных частных случаев общей задачи линейного программирования.

14 апреля 2011 года в 09:59

Задачи тысячелетия (Millennium Prize Problems) составляют семь математических проблем, охарактеризованных как «важные классические задачи, решение которых не найдено вот уже в течение многих лет». За решение каждой из этих проблем институтом Клэя предложен приз в 1 000 000 долларов США. Анонсируя приз, институт Клэя провёл параллель со списком проблем Гильберта, представленным в 1900 году и оказавшим существенное влияние на математиков XX века. Из 23 проблем Гильберта большинство уже решены, и только одна — гипотеза Римана — вошла в список Проблем тысячелетия.

По состоянию на сентябрь 2010 года только одна из семи проблем тысячелетия (гипотеза Пуанкаре) решена. Приз за её решение присужден российскому математику Г. Я. Перельману[1], который, впрочем, отказался от денежного приза.


Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта