Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


¬ырожденные случаи. ќткрыта€ транспортна€ задача




Ќекоторые замечани€ по частным случа€м, которые могут встретитьс€ при решении.

1. ≈сли на некотором шаге построени€ базисного плана из рассмотрени€ выпадают одновременно и строка и столбец (случай вырождени€), можно использовать следующий прием: дать нулевую (фиктивную) поставку в произвольную еще не зан€тую клетку данной строки или столбца. (“ем самым сохран€етс€ число зан€тых клеток m+nЦ1 дл€ базисного распределени€ поставок).

2. ≈сли в отрицательных вершинах цикла, по которому перераспредел€етс€ поставка, две или более минимальных поставок, то все они при перераспределении обрат€тс€ в нуль. “ак как на каждом шаге число зан€тых клеток сохран€етс€ в количестве m+nЦ1, то из этих УнулевыхФ клеток образуетс€ только одна пуста€ клетка, а остальные считаютс€ заполненными поставкой равной 0.

3. ≈сли мы нашли клетку с отрицательной оценкой и построили соответствующий цикл перераспределени€, в одной из отрицательных вершин которого находитс€ нулева€ поставка, то следует переместить эту нулевую поставку (значение целевой функции при этом не изменитс€), а затем вновь определ€ть оценки пустых клеток в полученном базисном плане.

–ассмотрим некоторые моменты, имеющие практическое значение, но усложн€ющие постановку транспортной задачи:

1. ќб€зательные поставки.

Ќезависимо от оптимальных расчетов некоторому поставщику вмен€етс€ определенный объем поставки некоторому потребителю (например, определенна€ марка бетона производитс€ только на таком-то заводе, а некоторому потребителю необходимо определенное количество данной марки). ¬ этом случае на величину об€зательных поставок корректируютс€ мощности и потребности, и после этого решаетс€ задача.

2. ќграничени€ пропускной способности.

–анее мы исходили из того, что от любого поставщика любому потребителю можно перевозить любое количество продукта (в пределах мощности и спроса). ¬ реальных задачах часто приходитс€ учитывать пропускную способность коммуникаций (особенно железных дорог).

—амый простой способ учитывать пропускную способность состоит в следующем:

ѕусть поставка в клетку (i,j) ограничена числом, строго меньшим ¬j. —толбец j, соответствующий потребителю с ограниченной пропускной способностью, разбиваетс€ на два столбца, в одном спрос принимаетс€ равным ограничению, а в другом Ц остатку. ѕоказатели транспортных затрат одинаковы дл€ этих двух столбцов за исключением клетки (i,j) в столбце, где спрос равен разности (остатку). «десь сij принимаетс€ очень большим, блокирующим какую-либо поставку в эту клетку.

ƒо сих пор мы рассматривали закрытую транспортную задачу, т.е. при условии баланса спроса и объемов производства (мощностей). ¬ практических задачах это условие далеко не всегда выполн€етс€. ѕри нарушении баланса возникает открыта€ транспортна€ задача, котора€ решаетс€ сведением ее к закрытой транспортной задаче.

ѕри превышении суммарной мощности над суммарным спросом на величину D вводитс€ дополнительный столбец так называемого фиктивного потребител€ со спросом равным D. ѕоказатели сin+1(i=1,2,Е,m) в этом столбце выбираютс€ произвольно, но с одним условием, что все они равны между собой. ”добнее всего принимать их равными 0. ƒалее задача решаетс€ как закрыта€.

јналогично, при превышении суммарного спроса над суммарной мощностью на величину D вводитс€ дополнительна€ строка так называемого фиктивного поставщика с мощностью равной D и с нулевыми транспортными издержками.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-09-20; ћы поможем в написании ваших работ!; просмотров: 630 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќаука Ч это организованные знани€, мудрость Ч это организованна€ жизнь. © »ммануил  ант
==> читать все изречени€...

1278 - | 1135 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.007 с.