2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Транспортная задача
Сообщение09.06.2012, 14:53 


27/03/09
213
Добрый день.
Имеется вот такое условие транспортной задачи:
$\[
\left( {\mathop {\left. {\underline {\, 
 {\begin{array}{*{20}c}
   4 \hfill & 7 \hfill & {\,\,1} \hfill & {\,\,\,1} \hfill  \\
   5 \hfill &  -  \hfill & {\,\,3} \hfill & {\,\,4} \hfill  \\
   3 \hfill &  -  \hfill & {\,\,2} \hfill & {\,\,8} \hfill  \\
\end{array}} \,}}\! \right| }\limits_{\begin{array}{*{20}c}
   {10} & {80} & {90} & {20\,}  \\
\end{array}} \begin{array}{*{20}c}
   {100}  \\
   {50}  \\
   {70}  \\
\end{array}} \right)
\]
$
Подскажите, пожалуйста, как решать ее в случае неизвестности этих двух значений, не встречалось раньше.

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение09.06.2012, 15:00 
Заслуженный участник


08/04/08
8556
Спросить бы у препода, что он имел ввиду. Мне такого тоже не попадалось.
Если все так, как написано, то рассуждаем так: стоимости перевозки неизвестны. Тогда нам надо получить план, минимизирующий худший случай, либо рассматривать всевозможные варианты стоимости.
В 1-м случае так: поскольку неизвестная стоимость может быть сколь угодно высока, то неизвестным способом лучше просто не возить. В таком случае 2-й поставщик отправляет свой товар (или что там у него) единственно возможным способом и размерность задачи падает с $(m,n)$ до $(m-1,n-1)$ - дальше получаем обычную ТЗ.
Или можно поставить в качестве стоимости $100500$ и решать ТЗ как обычно.
Во 2-м случае сложнее, но должно получаться конечное число вариантов. Надо подумать... (и у препода спросить - чего ему именно надо)

-- Сб июн 09, 2012 12:02:11 --

Стоп, у Вас ТЗ несбалансированная :-( Тогда скажите, где у Вас поставщики, а где потребители?

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение09.06.2012, 15:03 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Как вариант - соответствующих путей нет. Тогда стоимость принимается бесконечной.

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение10.06.2012, 19:17 
Аватара пользователя


14/02/10
4956
Евгений Машеров в сообщении #582615 писал(а):
Как вариант - соответствующих путей нет. Тогда стоимость принимается бесконечной.

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

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение11.06.2012, 04:40 


02/11/08
1187
Shtorm в сообщении #583161 писал(а):
А почему Вы говорите, что стоимость принимается бесконечной? Просто не ставим грузы в зачёркнутые клетки и получаем конечную общую стоимость.

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

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение11.06.2012, 14:11 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Бесконечность (или, как иногда используют, "число М, заведомо большее общей стоимости перевозки") употребляют для того, чтобы алгоритм для решения ТЗ без запретов мог бы без изменений использоваться и при наличии запретов. Единообразие алгоритма обычно оправдывает такой искусственный приём.

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение11.06.2012, 21:39 
Аватара пользователя


14/02/10
4956
Евгений Машеров в сообщении #583406 писал(а):
Бесконечность (или, как иногда используют, "число М, заведомо большее общей стоимости перевозки") употребляют для того, чтобы алгоритм для решения ТЗ без запретов мог бы без изменений использоваться и при наличии запретов. Единообразие алгоритма обычно оправдывает такой искусственный приём.


А при проверке опорного плана перевозок на оптимальность в таком случае нельзя использовать метод потенциалов? А если можно, то при сравнении истинных и косвенных тарифов - прибавляют или вычиатют прямо из бесконечности?

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение12.06.2012, 17:46 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Можно. Отчего нет?

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение13.06.2012, 22:13 
Аватара пользователя


14/02/10
4956
Евгений Машеров, а вот не подскажите такой момент: при решении транспортной задачи методом потенциалов, может ли в каких-то ситуациях возникнуть зацикливание? То есть, строим новый цикл - получаем стоимость, критерий оптимальности не выполняется, опять новый цикл - стоимость та же, что и была до этого - новый цикл - опять та же стоимость и так далее? А то я слышал, что при решении транспортной задачи симплексным методом такое зацикливание может возникнуть.

 Профиль  
                  
 
 Re: Транспортная задача
Сообщение14.06.2012, 09:18 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Может. В случае вырожденности. Тогда делается малое возмущение объёмов перевозок.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group