2014 dxdy logo

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

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




 
 Транспортная задача
Сообщение09.06.2012, 14:53 
Добрый день.
Имеется вот такое условие транспортной задачи:
$\[
\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 
Спросить бы у препода, что он имел ввиду. Мне такого тоже не попадалось.
Если все так, как написано, то рассуждаем так: стоимости перевозки неизвестны. Тогда нам надо получить план, минимизирующий худший случай, либо рассматривать всевозможные варианты стоимости.
В 1-м случае так: поскольку неизвестная стоимость может быть сколь угодно высока, то неизвестным способом лучше просто не возить. В таком случае 2-й поставщик отправляет свой товар (или что там у него) единственно возможным способом и размерность задачи падает с $(m,n)$ до $(m-1,n-1)$ - дальше получаем обычную ТЗ.
Или можно поставить в качестве стоимости $100500$ и решать ТЗ как обычно.
Во 2-м случае сложнее, но должно получаться конечное число вариантов. Надо подумать... (и у препода спросить - чего ему именно надо)

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

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

 
 
 
 Re: Транспортная задача
Сообщение09.06.2012, 15:03 
Аватара пользователя
Как вариант - соответствующих путей нет. Тогда стоимость принимается бесконечной.

 
 
 
 Re: Транспортная задача
Сообщение10.06.2012, 19:17 
Аватара пользователя
Евгений Машеров в сообщении #582615 писал(а):
Как вариант - соответствующих путей нет. Тогда стоимость принимается бесконечной.

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

 
 
 
 Re: Транспортная задача
Сообщение11.06.2012, 04:40 
Shtorm в сообщении #583161 писал(а):
А почему Вы говорите, что стоимость принимается бесконечной? Просто не ставим грузы в зачёркнутые клетки и получаем конечную общую стоимость.

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

 
 
 
 Re: Транспортная задача
Сообщение11.06.2012, 14:11 
Аватара пользователя
Бесконечность (или, как иногда используют, "число М, заведомо большее общей стоимости перевозки") употребляют для того, чтобы алгоритм для решения ТЗ без запретов мог бы без изменений использоваться и при наличии запретов. Единообразие алгоритма обычно оправдывает такой искусственный приём.

 
 
 
 Re: Транспортная задача
Сообщение11.06.2012, 21:39 
Аватара пользователя
Евгений Машеров в сообщении #583406 писал(а):
Бесконечность (или, как иногда используют, "число М, заведомо большее общей стоимости перевозки") употребляют для того, чтобы алгоритм для решения ТЗ без запретов мог бы без изменений использоваться и при наличии запретов. Единообразие алгоритма обычно оправдывает такой искусственный приём.


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

 
 
 
 Re: Транспортная задача
Сообщение12.06.2012, 17:46 
Аватара пользователя
Можно. Отчего нет?

 
 
 
 Re: Транспортная задача
Сообщение13.06.2012, 22:13 
Аватара пользователя
Евгений Машеров, а вот не подскажите такой момент: при решении транспортной задачи методом потенциалов, может ли в каких-то ситуациях возникнуть зацикливание? То есть, строим новый цикл - получаем стоимость, критерий оптимальности не выполняется, опять новый цикл - стоимость та же, что и была до этого - новый цикл - опять та же стоимость и так далее? А то я слышал, что при решении транспортной задачи симплексным методом такое зацикливание может возникнуть.

 
 
 
 Re: Транспортная задача
Сообщение14.06.2012, 09:18 
Аватара пользователя
Может. В случае вырожденности. Тогда делается малое возмущение объёмов перевозок.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group