Имеется m пунктов отправления, в каждом из которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте имеется единиц этого продукта, во втором - единиц, в i -ом - единиц, и, наконец, в m -ом пункте - единиц продукта. Этот продукт следует доставить в n пунктов назначения (потребления), причем в первый пункт назначения следует доставить единиц продукта, во второй - единиц, в j -й - единиц, и, наконец, в n -й пункт - единиц продукта.
Каждый пункт отправления соединен с каждым пунктом назначения некоторым маршрутом (число таких маршрутов ), причем известна удельная стоимость перевозки одной единицы продукта из i -го пункта отправления в j -й пункт назначения. Общая стоимость перевозки по любому маршруту пропорциональна количеству перевозимого продукта. Известно также время перевозки продукта из i -го пункта отправления в j -й пункт назначения, причем это время не зависит от количества перевозимого груза.
Удельные стоимости и время перевозок приведены в таблице, при этом:
1) на пропускные способности коммуникаций ограничения не накладываются;
2) и - количество условных единиц продукта;
3) в верхних отделениях клеток таблицы помещены удельные стоимости в рублях, а в нижних - время перевозок в часах.
Bj Þ Ai ß | B 1 | B 2 | B 3 | B 4 | B 5 | B6 | B7 | B8 | ai |
A 1 | |||||||||
A 2 | |||||||||
A 3 | |||||||||
A 4 | |||||||||
A 5 | |||||||||
A 6 | |||||||||
A 7 | |||||||||
bj |
Вариант 3.1. Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод северо-западного угла [9].
Вариант 3.2. Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод минимального элемента [9].
Вариант 3.3. Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить венгерским методом [9].
Вариант 3.4. Составить план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок; определить для этого плана стоимость перевозок; произвести, если это возможно, дооптимизацию по критерию стоимости. Поставленную задачу решить, применяя метод, в основе которого лежит построение "разгрузочного" цикла [13].
Вариант 3.5. Составить план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок; определить для этого плана стоимость перевозок; произвести, если это возможно, дооптимизацию по критерию стоимости. Первую часть задачи решить, применяя вариант метода потенциалов, при дополнительных условиях, вводимых последовательно в процесс решения [13].