Задача

Темы

Сложность

9.5
Средняя: 9.5 (4 оценок)

Автор

18.06.2010, 02:45 (Алексей Суздальцев)
18.06.2010, 02:45


(0)
Все 13 городов страны $A$ расположены на одной прямой. Обозначим их слева направо $A_1,A_2,\ldots,A_{13}$. В рамках программы ускоренной модернизации правительство приняло решение о строительстве в стране первого завода по производству инновационного товара $X$. Этот товар будет доставляться во все города пропорционально количеству жителей в них. Издержки же на транспортировку пропорциональны как количеству доставляемого товара, так и расстоянию от завода до данного города. Правительство приняло еще одно инновационное решение: построить завод в такой точке плоскости, чтобы суммарные издержки на транспортировку товара $X$ в города были минимальны. В какой точке нужно построить завод, если

  1. В городах одинаковое количество жителей;
  2. В городе $A_1$ живет 1 млн. чел., в городе $A_2$ - 2 млн., в городе $A_3$ - 3 млн., и.т.д., в городе $A_{13}$ живет 13 млн. чел.?

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

Комментарии

В 1) нужно поместить завод в городе A7 ?
Это первое, что приходит на ум) Но это не так уж очевидно: если, например, расстояние между A12 и A13 равно 1000 км, а между остальными городами равно 1 км., то почему бы не построить завод поближе к A13? В общем, хочется строгого доказательства.
Ну ок. Значит S- это расстояние которое он затратит на перевозку во все города. Тогда
S=|x|+|x-L_1|+|x-L_2|+...+|x-L_12| , где x- это расстояние между точкой где будет завод и первым городом. А L_1,L_2 ... L_12 - это расстояния между 2,3..13 городов и первым город.
Таким образом если раскрыть модули то получиться , что график функции S это такая ломанная функция состоящая из 14 прямых с углами наклона -13 -11 -9 -7 -5 -3 -1 1 3 5 7 9 11 13 . т.е функция слева направо сначала убывает доход до минимума а потом возрастает , так вот, её минимум находится в точке где происход смена угла наклона с -1 на 1 , это точка соответствует городу A7 . Поэтому независимо от L т.е расстояний между городами , необходимой точкой будет A7.
ОК) а теперь докажи, что завод надо строить именно на прямой (в условии это не дано), а также попытайся решить задачу вообще не выписывая сумму модулей. Просто докажи, глядя на картинку, что любая точка, кроме A7, не оптимальна.

Ну и второй пункт попытайся решить двумя способами)

Завод надо строить на прямой, потому что , если его построить не на прямой, то нам придётся каждый раз до города проежать по гипотенузе( если завод строить параллельно какому-нибудь городу), в противном случае мы ехали бы по катету.
А превозить будет сколько транспортных единиц?
Исходя из условия, издержки от этого не зависят. Действительно, какая разница, какая машина будет ездить, одна и та же или каждый раз разная?
А если они будут выезжать обе сразу?
Посудите сами. Я с тобой согласен, что лучше всего чтобы завод находился на прямой. Нона том ли месте на прямой он должен находится, если у нас одна транспортная ед. Может если завод будет находится или у города А13 или у А1 то издержки будут меньше.
Это я про а)
Сурен достаточно строго вроде объяснил, почему именно в этом месте прямой должен стоять завод. Словесное доказательство, я думаю, тоже не заставит себя долго ждать)
.
Нет я просто хочу внести свое предположение.
НУ допустим если завод находится около города А7, то ему надо доехать до города А13 , чтобы дать товар А8,А9,А10,А11,А12, А13 . Потом ему надо опять возратиться назад и проехать этот отрезок А7 - А13
далее транспорт повезет товар до А6, А5, А4, А3, А2,А1, а потом проезжать отрезок А6 - А1, чтобы доехать до завода.
Алексей, ты, похоже неверно трактуешь условие. Для упрощения можно сказать, что выходит так, что машина ездит в каждый город по отдельности и ничего "по пути" не доставляет. "Издержки же на транспортировку пропорциональны как количеству доставляемого товара, так и расстоянию от завода до данного города" И возвращаться на завод машине не нужно. Доехала и всё - развалилась.
Ну даже если возвращается обратно - на результат минимизации это не влияет, просто издержки при любом расположении завода будут вдвое выше.
Это у меня не получилось хорошо объяснить).
На счет доставки "по пути" - да, здесь об этом думать не надо, в каждый город, грубо говоря, едет своя колонна машин. Неявно здесь предполагается, что количество товара, нужное каждому городу, больше чем вместимость одной машины, и у нас есть много машин.
Допустим, выехало из завода несколько машин. Едут - на пути встречается город. Тогда часть из них разгружается и едет обратно на завод, часть едет до следующего города, и.т.д.
Почти такая задачка каждый год на ММО по математике, я не путаю?
В этом году было нечто иное, но чем-то похожее, а тем, что нужно найти минимальные затраты))
Алексей видимо я "заболел", но мне в голову лезет, то что кол-во жителей в городах не меняет ответа, так как это кол-во определяет сколько мы повезём товара в данный город, и не зависит от того откуда мы повезём товар.
Или я не так понял условие?
От количества ввозимого в данный город товара зависят издержки на транспортировку - нужно больше машин (это написано в условии). Представь, что в 13-ом городе стал жить миллиард человек - замучаешься столько товара везти из седьмого! Так что ответ во втором пункте наверняка поменяется...
Да, точно, у меня были временные помутнения))
тогда лучше строить завод в 13-ом городе.
Это я про второй слчай.
Нет. Напиши, как ты до этого дошел, поищем ошибку.
Да нет ну вы сами поймите простая логика , ЕСЛИ численность в 13 городе большая а дальше она по убыванию идет, то просто напросто машин понадобится меньше или по-другому издержки с транспортировкой уменьшатся?
вот и все.
А вы хотите чтобы все математически было?
Конечно. Самая простая и первая мысль не всегда верная.
Смотри: ты сэкономил на том, чтобы доставлять товар в 13 город. Но при этом тебе пришлось везти кучу товара в другие города, которые, возможно, очень далеко.
Более того, легко доказать, что в 13 городе располагать завод невыгодно при любых расстояниях между другими городами.

Возьмем за единицу измерения товара количество товара, которое нужно 1 млн. чел. Пусть издержки транспортировки 1 единицы товара на 1 км равны $t$.
Тогда если ты перенесешь завод из 13-ого города на 1 км левее, то твои издержки справа вырастут на $13t$ (Тебе придется доставлять 13 единиц на расстояние 1 км., раньше ты этого не делал), но слева твои издержки сократятся на целых $(1+2+\ldots+12)t$, так как теперь товар, нужный левым городам, надо везти на 1 км. меньше! В итоге общие издержки уменьшатся, а значит, если строить завод в 13-ом городе, то издержки заведомо не минимальны - существует заведомо более хороший вариант, строить чуть левее.

Но и этот вариант не оптимален, не правда ли?

Честно я не гадаю. Это в 9 городе надо строить завод.
Уже почти!
10
Если бы стоили в девятом было бы почти равновесие 46t=45t
Ага. Я чувствую, ты проникся логикой. Но почему вообще нужно строить в одном из городов? По условию, можно вообще построить в любой точке на плоскости.
Ты предлагаешь помыслить?
Я прав?
Ответ правильный) Что помыслить предлагаю - тоже правильно.
))
Но лучше места чем на прямой не имеется.
я думаю может вблизи города 10 но не далеко от города.
чем дальше тем длиннее путь.
Одно и то же получается.
Зато, может, так ближе к другим городам будет?
Если только ближе к 11 , 12,13 туда
Примени ту логику для 10-го города, что Лёша применил для 13-го, чтобы доказать, что нельзя изменить положение так чтобы расходы сократились.
Можно это доказать с неравенством километража.
Всегда гипотинуза больше катетов и тут также. Т.е. если завод находится на прямой километраж, который перед нами стоит намного меньше , чем если завод находится не на ней.
Расстояние , которое транспорт должен проехать не на прямой =
√(13(А10-L)+ (L;А1)2+(L;А2)2+(L;А22)+(L;А3)2+(L;А4)2+(L;А5)2+ (L;А6)2+(L;А7)2+(L;А8)2+(L;А9)2+(L;А10)2+(L;А11)2+(L;А12)2+(L;А13)2 А оно гараздо больше ,а потому трансакционные издержки будут больше.
1.gif_1.gif
я хочу вставить рисунок сюда но у меня не получается.
Формат подходящий. как мне можно его вставить?
Нажми над строкой сообщение , справа от "просмотр" на картинку появится окно , вставить картинку перекинь своё изображение в открывшееся окно, если формат неверный то он напишет про это слева, если верный , то нажми вставить в сообщение. Если ты это всё проделал и ничего не вышло, то попробуй через другой браузер
:-)
Да спасибо? но я так все и делал? но пишет формат не тот хотя gif
поменяй имя файла на 1.gif .
Алексей, буду откровенным), я имел виду доказательство того, что нужно именно в городе 10 строить завод, а не на миллиметр правее/левее именно на прямой.
А то, что проекция всегда меньше наклонной т.е. расстояние поездки по прямой меньше чем расстояние поездки "по плоскости" можно, мне кажется, объяснить словесно)
А я ведь равенство уже написал.
Ну я думаю мой рисунок лишним не будет.
Да, лишним не будет. Видимо я не совсем уловил суть твоих сомнений, но ,с другой стороны, строгого доказательства по поводу того, где точно нужно расположить город ты так и не привел, хотя ты и "проникся логикой", ты только написал что для девятого какое-то равенство почти выполняется. Цель вед не получить ответ, а решить задачу полностью.
Я проникся логикой благодаря подсказки Алексея.
А разве вопрос задачи не стоял в том чтобы найти этот город. И все наши рассуждения пришли к выводу что лучше всего строить завод на прямой, в а) это 7-ой город И Сурен это доказал. А в б) это 10-ый город
И задача наверно решена , разве нет?
Если , конечно, Алексей не даст нам еще какое-нибудь задание......).
Доказательства к пункту б) в обсуждении нет, хотя, наверное все уже поняли, как доказывать.
Ну, например, пункт б) тогда можно попробовать доказать вторым способом, как это делал Сурен(через сумму модулей). Алексей к этому взывал между прочим)
Если с модулями , то сдесь может так будет
S = |x|+2|x-L_2|+3|x-L_3|+4|x-L_4|+5|x-L_5|+6|x-L_6|+7|x-L_7|+8|x-L_8|+9|x-L_9|+10|x-L_10|+11|x-L_11|+12|x-L_12|+13|x-L_13|
Ну вот давайте искать ошибки).
Было бы неплохо пояснить обозначения, но прослеживается Явная аналогия с Суреном, если так, то путь ты верно рассчитал. Хотя, как мне кажется, координатный метод несколько удобнее.
Я с вами согласен про Сурена. Мы с Тимуром решили решать эту задачу вторым способом если вы считаете что это что-то близко к правде, то это совсем неплохо. А так я уверен, что первый способ удобнее.
.
.
Все что было надо было здесь решить все решено.))
Еще можно несколькими способами найти минимум у функции с модулями:)
А не кажется ли вам удивительным, что ответ не зависит от расстояний между городами?