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

[elena_croatia]

не знаю, помогаете ли вы с транспортными задачами (не нашла такой темы в метках к посту), но надеюсь)

использовался метод наименьшей стоимости. подскажите, в каких клетках надо расставить вырожденные нули, чтобы расставить недостающие потенциалы. прочитала несколько правил, не очень поняла (например: "При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения." разве если у поставщика запасы равны нулю, он не исключается сразу же?как это понять?)

задача с огр пропускной способности. (ограничения-розовым)
получилось 10 базисных клеток-должно быть 12
небазисные клетки-подчеркнуты. клетка 4.8 (145) небазисная, тк в тот момент не вычеркнулся ни поставщик ,ни потребитель (верно же?)

@темы: Математика в экономике

Comments

[All_ex]

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

[elena_croatia]

All_ex, не больше

[All_ex]

получилось 10 базисных клеток-должно быть 12 - при таких ограничениях как у Вас базисных клеток будет побольше...

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

4.8 (145) небазисная, тк в тот момент не вычеркнулся ни поставщик ,ни потребитель (верно же?) - вроде должно обнуляться...

[elena_croatia]

All_ex,

4.8 (145) небазисная, тк в тот момент не вычеркнулся ни поставщик ,ни потребитель (верно же?) - вроде должно обнуляться...

- так ведь если идти методом мин стоимости , то когда заполнили 4.8 -145- ни поставщик,ни потребитель не вычеркнулись. а в след действии в клетке 2.8 -5 единиц- тогда вычеркивается тот потребитель
или "обнуляться" -вы имели в виду что-то другое?

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

[All_ex]

так ведь если идти методом мин стоимости , то когда заполнили 4.8 -145- ни поставщик,ни потребитель не вычеркнулись. - Я не пересчитывал Ваше решение...
Если ничего не вычеркнулось, значит, Вы выбрали мало товара для этой перевозки... надо брать не 145, а 150 ...

[elena_croatia]

All_ex,

при таких ограничениях как у Вас базисных клеток будет побольше... - а как определить сколько может получиться базисных?
сколько должно,это понятно
а как Вы определили,что их больше 10 должно получиться?

[All_ex]

Но вообще-то сначала надо добавить шесть магазинов, по одному на каждое ограничение... а потом уже выписывать план перевозки...

[All_ex]

а как Вы определили,что их больше 10 должно получиться? - базисных должно быть всегда `(n + m - 1)`... если ненулевых клеток меньше, то их дополняют нулевыми до нужного количества так. чтобы не было циклов...

[elena_croatia]

All_ex, а по-другому никак нельзя? мы решали небольшие задачки без добавления поставщиков

[All_ex]

мы решали небольшие задачки без добавления поставщиков - ну, может при малых размерах задачи это возможно... но у Вас и задача большая, и дополнительных ограничений много... ...
В принципе, писать матрицу `5 xx 8` или `11 xx 8` - невелика разница... зато всё очень стандартно, без дополнительных заморочек...

[elena_croatia]

All_ex,

а как Вы определили,что их больше 10 должно получиться? - базисных должно быть всегда `(n + m - 1)`... если ненулевых клеток меньше, то их дополняют нулевыми до нужного количества так. чтобы не было циклов...

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

[elena_croatia]

All_ex, ну мы видели,как должны выглядеть эти задачи, и там никаких дополнительных поставщиков не предполагалось(

[elena_croatia]

All_ex, может, Вы знаете ,Как это правило понять? нашла в какой-то методичке «При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения.»
разве если у поставщика запасы равны нулю, он не исключается сразу же?

[All_ex]

нашла в какой-то методичке - по одной фразе трудно сказать, что имел ввиду автор... ... тут надо читать предшествующие объяснения...

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

Кстати, про ограничения "не больше" ... по идее заполненные клетки с ограничениями тоже входят в базисные...

[All_ex]

Нашёл какое-то описание решения при ограничении "не больше"... там улучшают решение... проверяют допустимость... и при недопустимости строят "корректор"... ... но почему его выбирают именно таким - не сказано ...
Как-то мудрёно получается... дописать дополнительные строчки или столбцы проще... "я так думаю"(с) ...

[elena_croatia]

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

а клетки с ограничениями не входят в базис,как нам объясняли, тк при их заполнении не вычеркивается никто: ни поставщик,ни потребитель

[All_ex]

elena_croatia, На каждом шаге исключается либо один поставщик, либо один потребитель. - ну, тогда всё понятно...
то есть при ситуации, когда обнуляются и возможности и потребности одновременно, Вы сами выбираете кого исключить (поставщика или потребителя)... и действуете дальше по алгоритму...
Например, исключили потребителя... в какой-то момент Вы выбирается клетка этого поставщика с нулевым запасом... максимальная перевозка - нуль, но клетка будет считаться базисной...
То есть получаете то, что написано в методичке... «При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения.»


а клетки с ограничениями не входят в базис,как нам объясняли, тк при их заполнении не вычеркивается никто: ни поставщик,ни потребитель
Как бы да... но ведь в них может уменьшаться объём... то есть при ограничении `x_{21} <= 35` значение этой переменной в оптимальном плане не обязательно равно 35... а если Вы не считаете их базисными, то непонятно как Вы будете уменьшать значение в этих клетках...

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