Транспортная задача

[NatNiM]

Добрый день.
Имеется вот такое условие транспортной задачи:
$\[ \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) \] $
Подскажите, пожалуйста, как решать ее в случае неизвестности этих двух значений, не встречалось раньше.

[Sonic86]

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

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

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

[Евгений Машеров]

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

[Shtorm]

Евгений Машеров в сообщении #582615 писал(а):

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

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

[Yu_K]

Shtorm в сообщении #583161 писал(а):

А почему Вы говорите, что стоимость принимается бесконечной? Просто не ставим грузы в зачёркнутые клетки и получаем конечную общую стоимость.

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

[Евгений Машеров]

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

[Shtorm]

Евгений Машеров в сообщении #583406 писал(а):

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

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

[Евгений Машеров]

Можно. Отчего нет?

[Shtorm]

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

[Евгений Машеров]

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