Постановка задачи:
Имеется 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