Существуют ли решения предлагаемой транспортной задачи

[ArtemT]

Привет Форумчанам.

Господа, есть вопрос к специалистам. У меня техническое боразование в области ИТ. Знания математики- базовые инженерные. А как говорил наш замечательный преподаватель Баскаков В.А., Царство ему небесное, все инженера - бездарные математики.
Вопрос такой:
Есть задача (насколько я понимаю, задачи такого типа называются транспортными)
Есть набор точек продаж (например терминалы самообслуживания типа eleks-net), расположенных в разных местах.
Интересуют задача оптимальной инкассации этих точек, учитывая что:
1. Есть стандарнтые параметры задачи, это:
загруженность дорог, стоимость бензина, стандартные маршруты из одного места в другое
2.Нестандартное условие: необходимость инкассации точки зависит от количества наличности в ней - вот это суть вопроса. Например, можно ездить инкассировать когда уже переполнено, или например ездить чаще, когда необходима инкассация других точек, расположенных рядом - заехать близко и недорого.

Есть ли решение данного вопроса? Просьба подсказать конкретно где копать и что читать ( для меня чтение матем. литературы - сложное занятие и я не хотел бы терять время, читая не то, что нужно).

ps Возможно вопрсо не в той ветке, но в ветку задач меня не пустили, да я и прошу не решение, а принципиальность существования уже решенной задачи (я так понимаю кто-то с таким уже сталкивался) и где это можно прочитать.

Спасибо. С уважением, Артем

[Highwind]

2 ArtemT

Мдя... я понимаю так. Если все так туго, надо почитать что-то простое, но по теме. Особливо, ежели это транспортная задача (а похожа, зараза). Тээкс...что там для инженеров...

1. Таха, Хемди А. "Введение в исследование операций" - все что про транспортную задачу.
2. Волков И.К., Загоруйо Е.А. "Исследование операций" - аналогично.

Эти книги, как говорится, "написаны без излишнего академизма" . Первая очень толстая, а вторая потоньше, но зато почти полностью слизана с первой , хотя при этом получилось что-то новое

p.s. А что, разве ИТ-спецам не читают теорию принятия решений или исследование операций?

[ArtemT]

Спасибо! Теперь мне в книжный.
Исследование операций читали, но плохо((((
хорошо читали матан, как раз Баскаков, и тервер - Калиниченко. С этим у меня все нормально.
Остальная математика прошла мимо меня))

[Highwind]

2 ArtemT

ArtemT писал(а):

Исследование операций читали, но плохо((((

О, да... к сожалению современная проблема технических вузов...

[MMyaf]

Сперва, наверное, необходимо ввести для каждой точке(инкассируемому обьекту) степень важности этой точки. Эту величину можно ввести разными путями, в зависимости от количества и качества известных данных. Например,если известно (по предыдущим инкассациям) количество выручки получаемой от каждой точки $x_1,x_2,...,x_n$, можно посчитать долю выручки каждой точки

$$\lambda_j=\frac{x_j}{\sum\limits_{i=1}^nx_i} , j=\overline{1,n}$$

. Чем выше доля прибыли точки, тем выше степень важности этой точки. Или если неизвестна прибыль каждой точки, то степень важности можно ввести по кол-ву близлежащих домов хк данной точке и количеству проезжающих машин в час(у) мимо той или иной точки.Чем больше x, y тем вероятнее , что точка будет иметь большую прибыль, а значит и степень важности ее будет выше. Далее можно ввести классификацию, присвоить самой вероятно прибыльной точке число 1, менее вероятноприбыльной - 2, и т. д. Так для каждой точке установим степень ее важности. В итоге имеем:карту с обозначенными на ней точками(инкассируемыми обьектами), точки упорядочены по степени их важности, также на карте обозначены пути, назовем их ветки (ветка - на карте отрезок соединяющий одну точку(инкассируемый обьект) с другой, причем этому отрезку могут принадлежать только две точки(т.е. два инкассируемых обьекта), очевидно они будут лежать наконцах этого отрезка).Введем для каждой такой ветви величину - времяемкость

$$\alpha$$

,

$$\alpha < 0$$

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

$$\alpha$$

эта ветка имеет. Отсюда вывод:самая легкопроходимая ветка из всех веток имеет величину

$$\alpha = -1$$

.Самая легкопроходимая ветка из всех веток за исключением той ветки, которой мы уже присвоили

$$\alpha = -1$$

, имеет значение

$$\alpha = -2$$

, и т.д. Если всего веток на карте n штук, то самая труднопроходимая ветвь будет иметь значение

$$\alpha = -n$$

. Времяемкость почти похожа на звездную величину, введенную в астрономии, чем больше светимость звезды, тем меньше звездная величина этой звезды.В отличии от звездной величины, времяемкость всегда отрицательна. В итоге: на карте обозначены точки(инкассируемые обьекты), этим точкам присвоены различные числа от 1 до m(где m - кол-во
точек на карте), на карте обозначены дороги(ветки), этим дорогам присвоены числа от -1 до -n.
Далее разобьем карту на две половинки, скажем вертикальной чертой.Карта разобьется на две половинки, левую и правую. Посчитаем степень важности каждой половинки. Эт степень важности половинки будет получаться как сумма всех степеней важности точек находящихся в данном квадрате да плюс сумма всех времяемкостей веток, которые находятся в заданном квадрате.Найдем степень важности левой и правой половинки.Если степень левой половинки карты будет больше степени правой половинки карты. то инкасировать надо начинать с левой половинки, если наоборот, степень правой больше левой, то начинать надо с правой. Таким образом. мы определим с какой половинки надо начинать инкассировать.Даллее ту половинку, степень которой больше разделим снова на пополам. Теперь карта будет состоять из 3-ех частей. Посчитаем степень важности двух частей , которые находятся в половинке . Пусть они равны(x,y). Начнем инкассирование с тойчасти , степень важности которой max(x,y), эту часть назовем часть А. Затем разделим вторую половинку карты, на две части , посчитаем степень важности. И так далее каждый участок снова делим на пополам . считаем их степень важности. Когда разделим на пополам, часть А, посчитаем их степень важности пусть они равны (p,q), и выберем ту часть степень которой max(p,q).Эту часть мы назовем часть А.И т.д.Все время часть А,делим на 2 части ,большую часть(в смысле степень важности) на зываем часть А.
В итоге: наша карта превратиться в карту на которой , будут нанесены площади(квадраты), с нанесенной степенью важности квадрата.Это деление будет продолжаться до тех пока часть А не будет содержать только одну точку(один инкассируемый обьект). =>Первоначально начинаем инкассировать точку в текущей части А.А затем едем в соседнюю часть, причем в ту соседнюю, что обе две части составляли часть А предидущего шага.И т.д.
Модель к сожалению получилась статическая. К примеру не учтен, час пик.Т.е изменение времяемкости ветки в течении суток.
Вряд ли такая модель оптимальная, но в этой модели учтено практически все, кроме стоимости бензина.
А вообще, эта задача решается с помощью ЭВМ.Программирование. Эта задача сходна с задачей коммивояжера, или еще ее называют задача кладоискателя. Пишется прога, используя метод рекурсии.

[Руст]

Так или иначе нужен факториально растущий перебор на компьютере. На самом деле в практических задачах можно избежать неподъёмный для компьютера перебор некоторым упрощением, связанным с отказом от поиска настоящего максимума целевой функции, заменив на поиск варианта, который не сильно уступает принципиального максимума. Обычно, для полноценной замены, нужно знать более детальную информацию.