Данциг Вульф Разложение в AMPL - PullRequest
Новая
       20

Данциг Вульф Разложение в AMPL

0 голосов
/ 16 апреля 2019

Я новичок в AMPL и пишу свою диссертацию об алгоритме декомпозиции Данцига-Вульфа, и я пытаюсь реализовать существующую проблему в AMPL. Моя проблема связана с компанией, которая производит два вида стали (сталь 1 и сталь 2) в двух местах (завод 1 и завод 2). Для производства тонны стали необходимы 3 ресурса: железо, уголь и доменное время. Два завода имеют разные типы печей, поэтому ресурсы, необходимые для производства тонны стали, зависят от местоположения (см. Ниже). У каждого завода своя угольная шахта. Каждый день на заводе имеется 12 тонн угля, а на заводе 15 тонн угля. Уголь нельзя перевозить между растениями. Железная руда добывается в шахте, расположенной на полпути между двумя заводами. Ежедневно доступно 80 тонн железа. Каждую тонну стали1 можно продать за 170 долларов, а каждую тонну стали2 можно продать за 160 долларов. Вся продаваемая сталь отгружается одному покупателю. Стоимость доставки тонны стали с завода1 составляет 80 долларов, а тонны стали с завода2 - 100 долларов. Предполагая, что единственная переменная стоимость - это стоимость доставки, мы хотим выбрать LP, чтобы максимизировать доходы компании за вычетом расходов на доставку. Требования к ресурсам 1 сталь на заводе 1 8 тонн железа 3 тонн угля 2 часа взрыва сталь 2 на заводе 1 6 тонн железа 1 тон угля 1 час взрыва сталь 1 на заводе 2 7 тонн железа 3 тонн угля 1 час взрыва сталь 2 на заводе 2 5 тонн железа 2 тонн угля 1 час взрыва

Я сформулировал ЛП и решил его вручную с помощью разложения Данцига-Вольфа (DWD) и генерации столбцов, потому что он маленький. Я нашел на сайте AMPL пример для DWD, но я должен сделать много изменений. Это типичная проблема смешанного товаропотока, и у меня есть только один покупатель, и это немного сбивает с толку. Кроме того, у меня нет спроса, но есть только предложение и, наконец, чтобы найти целевую функцию, мне пришлось вычесть расходы на доставку из выручки, и я не знаю, как добавить эту функцию или где использовать требования ресурсов. Я бы хотел, чтобы кто-то меня успокоил и показал, как с этим обращаться. 

#dwd.mod
# ----------------------------------------
# MULTI-COMMODITY FLOW USING
# DANTZIG-WOLFE DECOMPOSITION
# (one subproblem for each product)
# ----------------------------------------

### SUBPROBLEM ###

set ORIG;   # origins
set DEST;   # destinations
set PROD;   # products

param supply {ORIG,PROD} >= 0;  # amounts available at origins
param demand {DEST,PROD} >= 0;  # amounts required at destinations

   check {p in PROD}:
      sum {i in ORIG} supply[i,p] = sum {j in DEST} demand[j,p];

param price_convex {PROD};           # dual price on convexity constr
param price {ORIG,DEST} <= 0.000001; # dual price on shipment limit
param cost {ORIG,DEST,PROD} >= 0;    # shipment costs per unit

var Trans {ORIG,DEST,PROD} >= 0;   # units to be shipped

minimize Artif_Reduced_Cost {p in PROD}:
   sum {i in ORIG, j in DEST}
      (- price[i,j]) * Trans[i,j,p] - price_convex[p];

minimize Reduced_Cost {p in PROD}:
   sum {i in ORIG, j in DEST}
      (cost[i,j,p] - price[i,j]) * Trans[i,j,p] - price_convex[p];

subject to Supply {i in ORIG, p in PROD}:
   sum {j in DEST} Trans[i,j,p] = supply[i,p];

subject to Demand {j in DEST, p in PROD}:
   sum {i in ORIG} Trans[i,j,p] = demand[j,p];

### MASTER PROBLEM ###

param limit {ORIG,DEST} >= 0;   # max shipped on each link

param nPROP {PROD} integer >= 0;
param prop_ship {ORIG, DEST, p in PROD, 1..nPROP[p]} >= -0.000001;
param prop_cost {p in PROD, 1..nPROP[p]} >= 0;

            # For each proposal from each subproblem:
            # amount it ships over each link, and its cost

var Weight {p in PROD, 1..nPROP[p]} >= 0;
var Excess >= 0;

minimize Artificial: Excess;

minimize Total_Cost:
   sum {p in PROD, k in 1..nPROP[p]} prop_cost[p,k] * Weight[p,k];

subject to Multi {i in ORIG, j in DEST}:
   sum {p in PROD, k in 1..nPROP[p]} 
      prop_ship[i,j,p,k] * Weight[p,k] - Excess <= limit[i,j];

subject to Convex {p in PROD}: sum {k in 1..nPROP[p]} Weight[p,k] = 1;

Решение проблемы: z = 1040 x_2 = 10, x_4 = 4, x_1 = x_3 = 0. Это означает, что компания может максимизировать свою чистую прибыль, производя 10 тонн стали2 на заводе 1 и 4 тонны стали2 на plant2. Спасибо за ваше время.

...