Постановка задачи:
Имеется m пунктов отправления, в каждом из которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте имеется a[1] единиц этого продукта, во втором - a[2] единиц, в i-м пункте a[i] единиц, и, наконец, в m-м пункте a[m] единиц продукта. Этот продукт следует доставить в n пунктов назначения (потребления), причем в первый пункт назначения следует доставить b[1] единиц продукта, во второй - b[2] единиц, в j-й пункт b[j] единиц, и, наконец, в n-й пункт b[n] единиц продукта.
Каждый пункт отправления соединен с каждым пунктом назначения некоторым маршрутом (число таких маршрутов m X n), причем известна удельная стоимость c[i,j] перевозки одной единицы продукта из i-го пункта отправления в j-й пункт назначения. Общая стоимость перевозки по любому маршруту пропорциональна количеству перевозимого продукта. Известно также время t[i,j] перевозки продукта из i-го пункта отправления в j-й пункт назначения, причем это время не зависит от количества перевозимого груза.
Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод минимального элемента.
ИрГТУ, 2009 год.
Имеется m пунктов отправления, в каждом из которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте имеется a[1] единиц этого продукта, во втором - a[2] единиц, в i-м пункте a[i] единиц, и, наконец, в m-м пункте a[m] единиц продукта. Этот продукт следует доставить в n пунктов назначения (потребления), причем в первый пункт назначения следует доставить b[1] единиц продукта, во второй - b[2] единиц, в j-й пункт b[j] единиц, и, наконец, в n-й пункт b[n] единиц продукта.
Каждый пункт отправления соединен с каждым пунктом назначения некоторым маршрутом (число таких маршрутов m X n), причем известна удельная стоимость c[i,j] перевозки одной единицы продукта из i-го пункта отправления в j-й пункт назначения. Общая стоимость перевозки по любому маршруту пропорциональна количеству перевозимого продукта. Известно также время t[i,j] перевозки продукта из i-го пункта отправления в j-й пункт назначения, причем это время не зависит от количества перевозимого груза.
Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод минимального элемента.
ИрГТУ, 2009 год.