Бережная_Матметоды моделирования эк cистем

оптимальности, если же направление стрелки противоположно, Сц вычитаем (см. рис. 8.2).

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

Если все ребра без стрелок имеют неотрицательные характери­ стики, то составленный план является оптимальным.

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

сменьшим потенциалом к вершине с большим потенциалом.

Внашем примере новая стрелка направлена от вершины II к вершине III (штриховая линия (см. рис. 8.2).

Для определения величины поставки (р) для ребра 6*23 рассма­ триваются все стрелки образовавшегося замкнутого контура, име­ ющие направление, противоположное новой стрелке (участок ^23), и среди них находится стрелка с наименьшей поставкой Л (в нашем примере X = 15 на ребре S^j), Выбранная таким образом величина прибавляется ко всем поставкам в стрелках, имеющих то же на­ правление, что и новая стрелка, и вычитается из поставок в стрел­ ках, имеющих противоположное направление. Поставки в стрел­ ках, не входящих в контур, сохраняются неизменными. Стрелка, на

Рис. 8.3. Новый опорный план распределения груза

290

которой выбрано число Я, ликвидируется и общее число стрелок остается прежним. Новый опорный план представлен на рис. 8.3.

Полученный план исследуется на оптимальность, подобно предыдущему. Сделав еще шаг, получим оптимальный план (рис. 8.4), когда все характеристики Sy на участках без стрелок неотри­ цательны.

Рис, 8.4. Оптимальный план распределения груза

Определим значение целевой функции:

^min = 100 . 2 + 25 • 1 + 15 • 3 + 70 . 3 + 10 • 6 + 20 • 5 = 640.

Вырождение плана транспортной задачи в сетевой постановке проявляется в том, что при полном использовании запасов и пол­ ном удовлетворении потребностей количество стрелок оказывается меньше чем /w + л - 1, где л - поставщики, a w - потребители.

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

В случае открытой модели вводят фиктивного потребителя (по­ ставщика) со спросом, равным небалансу Фиктивный потребитель (поставщик) соединяется дугами непосредственно со всеми постав­ щиками (потребителями), при этом показатели С^- ребер, соединя­ ющих фиктивного потребителя (поставщика) с реальными постав­ щиками (потребителями), следует брать одинаковыми и сравни­ тельно большими. Это делается для того, чтобы исключить воз­ можность использования фиктивной вершины в качестве промежуточного пункта.

291

8.6.Доставка груза в кратчайший срок

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

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

Для решения подобных задач рассмотренный ранее метод по­ тенциалов непригоден. Эти задачи решаются с помощью специаль­ ного алгоритма.

1.Любым способом строим один из опорных планов.

2.Определяем наибольший элемент t' из всех /^y, соответствую­ щих занятым клеткам, и все клетки с элементами ty > t' (это могут быть лишь свободные клетки) вычеркиваются.

3.Начиная с клетки с наибольшим временем доставки t\ стро­ им разфузочный цикл так, чтобы клетки с нечетными номерами (считая первой разгружаемую клетку с элементом t') были заняты­ ми. Одна из вершин разгрузочного цикла будет свободной. В об­ щем случае построение разгрузочного цикла неоднозначно.

4.Сделав в свободную вершину цикла поставку р, проводим компенсации по вершинам цикла, определяем величину р (так же, как в методе потенциалов), строим новый план.

5.Переходим ко второму пункту алгоритма, естественно, не учитывая ранее вычеркнутые клетки.

6.Алгоритмом пользуемся до тех пор, пока построение разгру­ зочного цикла становится невозможным.

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

Пример 8.4.

Определить оптимальный план перевозок из условия доставки груза в кратчайший срок. Известны ресурсы а{. 30; 35; 40, потреб­ ности в^: 20; 34; 16; 10; 25 и матрица

''2 6 3 4 %^

т=\Ы= 1 5 6 9 7

3 4 1 6 10

где tji^ — время, затрачиваемое на перевозку фуза из /-го пункта отправле­ ния в k-ii пункт назначения.

292

Решение

Запишем в виде таблицы исходную информацию и внесем в нее один из опорных планов (пункт 1 алгоритма).

Согласно пункту 2 алгоритма ^' = ^35"^ ^^ строим цикл перерас­ чета (3-й пункт). В свободную вершину цикла (2,5) делаем постав­ ку р и проводим компенсации по вершинам цикла, затем опреде­ ляем величину р:

р = 1 1 .

Строим новый план и переходим к пункту 2 алгоритма (табл. 8.14).

293

в новой таблице t' = t^^ = 10 (клетка 3,5 оказалась не полно­ стью разгруженной). Из анализа нового цикла пересчета заключа­ ем: р = 14; строим новый план (табл. 8.15).

Таблица 8.15

Оптимальный план

/' = /25 ~ 7, вычеркиваем все свободные клетки, для которых ty > 7. Для дальнейшего улучшения плана необходимо разгрузить клетку (2,5), но построение разгрузочного цикла для этой клетки невоз­ можно. На основании этого заключаем, что решение, полученное в последней таблице, является оптимальным, обеспечивающим пе­ ревозки за время /j^j^ = 7.

Задачи

8.1. в пунктах А и В находятся соответственно 150 и 90 т горю­ чего. Пунктам 1, 2, 3 требуются соответственно 60, 70, ПО т горю­ чего. Стоимость перевозки 1 т горючего из пункта Л в пункты 1, 2, 3 равна 60, 10, 40 тыс. руб. за 1 т соответственно, а из пункта В в пункты 1, 2, 3 — 120, 20, 80 тыс. руб. за 1 т соответственно.

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

8.2. Три завода выпускают грузовые автомобили, которые от­ правляются четырем потребителям. Первый завод поставляет 90 платформ грузовиков, второй — 30 платформ, третий - 40 плат­ форм. Требуется поставить платформы следующим потребителям:

первому — 70 шт., второму — 30, третьему — 20, четвертому — 40 шт. Стоимость перевозки одной платформы от поставщика до потреби­ теля указана в следующей таблице (д. е.):

294

Составьте оптимальный план доставки грузовых автомобилей. 8.3. Строительство магистральной дороги включает задачу запол­ нения имеющихся на трассе выбоин до уровня основной дороги и срезания в некоторых местах дороги выступов. Срезанным грунтом заполняются выбоины. Перевозка грунта осуществляется грузовика­ ми одинаковой фузоподъемности. Расстояние в километрах от сре­

зов до выбоин и объем работ указаны в следующей таблице:

Составьте план перевозок, минимизирующий общий пробег грузовиков.

8.4. Груз, хранящийся на трех складах и требующий для пере­ возки 60, 80, 106 автомашин соответственно, необходимо перевез­ ти в четыре магазина. Первому магазину требуется 44 машины гру­ за, второму — 70, третьему — 50 и четвертому — 82 машины. Стои­ мость пробега одной автомашины за 1 км составляет 10 д. е. Рас­ стояния от складов до магазинов указаны в следующей таблице:

Составьте оптимальный по стоимости план перевозки груза от складов до магазинов.

295

8.5. На складах А, В, С находится сортовое зерно 100, 150, 250 т, которое нужно доставить в четыре пункта. Пункту 1 необходимо поставить 50 т, пункту 2 — 100, пункту 3 — 200, пункту 4 — 150 т сортового зерна. Стоимость доставки 1 т зерна со склада А в ука­ занные пункты соответственно равна (д. е.) 80, 30, 50, 20; со скла­ да В - 40, 10, 60, 70; со склада С - 10, 90, 40, 30.

Составьте оптимальный план перевозки зерна из условия ми­ нимума стоимости перевозки.

8.6.Завод имеет три цеха — А, В, С и четыре склада — 1; 2; 3;

4.Цех А производит 30 тыс. шт. изделий, цех В — 40; цех С — 20 тыс. шт. изделий. Пропускная способность складов за то же время характеризуется следующими показателями: склад 1 — 20 тыс. шт. изделий; склад 2 — 30; склад 3 — 30 и склад 4—10 тыс. шт. изде­

лий. Стоимость перевозки 1 тыс. шт. изделий из цеха А на склады 1, 2, 3, 4 - соответственно (д. е.): 20, 30, 40, 40, из цеха В - со­ ответственно 30, 20, 50, 10, а из цеха С — соответственно 40, 30, 20, 60.

Составьте такой план перевозки изделий, при котором расхо­ ды на перевозку 90 тыс. шт. изделий были бы наименьшими.

8.7. На строительном полигоне имеется пять кирпичных заво­ дов, объем производства которых в сутки равен 600; 600; 500; 650; 700 т. Заводы удовлетворяют потребности семи строительных объ­ ектов соответственно в количестве 350; 450; 300; 450; 300; 200; 450 т. Оставшийся кирпич отправляют по железной дороге в другие районы. Кирпич на строительные объекты доставляется автомо­ бильным транспортом. Расстояние в километрах от заводов до объ­ ектов указано в следующей таблице:

Определите, с каких заводов и на какие объекты должен достав­ ляться кирпич, а также какие заводы и в каком количестве должны отправлять кирпич в другие районы, чтобы транспортные издерж­ ки по доставке кирпича автотранспортом были минимальными. Стоимость перевозки 1 т кирпича автотранспортом удовлетворяет условию с = а + d{i — 1), где а = 25 д. е., t/ = 5 д. е., i — пробег, км.

296

8.8. Имеются две станции технического обслуживания (СТО), выполняющие ремонтные работы для трех автопредприятий. Произ­ водственные мощности СТО, стоимость ремонта в различных СТО, затраты на транспортировку от автопредприятий на СТО и обратно и прогнозируемое количество ремонтов в планируемом периоде на каждом автопредприятии приведены в следующей таблице:

Требуется определить, какое количество автомашин из каждого автопредприятия необходимо отремонтировать на каждой СТО, чтобы суммарные расходы на ремонт и транспортировку были ми­ нимальными.

8.9. Найдите оптимальный план распределения заявок на ре­ монт для условий, приведенных в следующей таблице:

8.10. Имеются два хранилища с однородным продуктом, в ко­ торых сосредоточено 200 и 120 т продукта соответственно. Продук­ ты необходимо перевезти трем потребителям соответственно в ко­ личестве 80, 100 и 120 т. Расстояния от хранилищ до потребителей (в км) следующие:

297

Затраты на перевозку 1 т продукта на 1 км постоянны и равны 5 д. е.

Определите план перевозок продукта от хранилищ до потреби­ телей из условия минимизации транспортных расходов.

8.11.Промышленный концерн имеет два завода и пять складов

вразличных регионах страны. Каждый месяц первый завод произ­ водит 40, а второй ~ 70 ед. продукции. Вся продукция, производи­ мая заводами, должна быть направлена на склады. Вместимость первого склада равна 20 ед. продукции; второго ~ 30; третьего — 15; четвертого — 27; пятого — 28 ед. Издержки транспортировки про­ дукции от завода до склада следующие (ед.):

Распределите план перевозок из условия минимизации ежеме­ сячных расходов на транспортировку.

8.12. Три нефтеперерабатывающих завода с суточной произво­ дительностью 10; 8 и 6 млн галлонов бензина снабжают три бензо­ хранилища, спрос которых составляет 6; 11 и 7 млн галлонов. Бен­ зин транспортируется в бензохранилища по трубопроводу Стои­ мость перекачки бензина на 1 км составляет 5 д. е. на 100 галлонов. Завод 1 не связан с хранилищем 3. Расстояние от заводов до бен­ зохранилищ следующее (км):

Сформулируйте соответствующую транспортную задачу и реши­ те на минимум транспортных затрат.

298

8.13. Пусть в задаче 8.12 производительность нефтеперерабатыва­ ющего завода 1 снизилась до 8 млн галлонов. Кроме того, обязатель­ но полное удовлетворение спроса бензохранилища 2. Недопоставки в хранилища 1 и 3 штрафуются на сумму 8 д. е. за каждый галлон.

Сформулируйте соответствующую транспортную задачу и реши­ те на минимум издержек.

8.14. Автомобили перевозятся на трайлерах из трех центров рас­ пределения пяти продавцам. Стоимость перевозки в расчете на 1 км пути, пройденного трайлером, равна 60 д. е. Один трайлер может перевозить до 15 автомобилей. Стоимость перевозок не зависит от того, насколько полно загружается трайлер. В приведенной ниже таблице указаны расстояния (км) между центрами распределения и продавцами, а также величины, характеризующие ежемесячный спрос и объемы поставок, исчисляемые количеством автомобилей:

Определите минимальные затраты на доставку автомобилей. 8.15. Решите задачу распределения станков четырех различ­

ных типов по шести типам работ. Пусть имеются 30; 45; 25 и 20 станков соответствующих типов. Шесть типов работ характеризу­ ются 30; 20; 10; 40; 10 и 10 операциями соответственно. На стан­ ке 3 не может выполняться работа 6. Исходя из коэффициентов стоимости операции, представленных в следующей таблице, по­ стройте модель и выполните оптимальное распределение станков по работам:

299