Комбинаторная оптимизация - вариация на рюкзаке

Вот проблема комбинаторной оптимизации в реальном мире.

Нам задан большой набор ценностных предложений для некоторого произведения. Ценностные предложения имеют разные типы, но каждый тип является независимым и добавляет равную выгоду всему продукту. При создании продукта мы можем включить любое неотрицательное целое число "единиц" каждого типа. Однако после добавления первой единицы определенного типа предельное преимущество дополнительных единиц этого типа постоянно уменьшается. Фактически, предельное преимущество нового блока - это инверсия числа единиц этого типа после добавления нового блока. Из-за этого требования наш продукт должен иметь хотя бы одну единицу какого-либо типа, и из-за этого требуется небольшая коррекция, которую мы должны сделать для общего значения.

Пусть T[] - массив, представляющий число каждого типа в определенном производственном прогоне продукта. Тогда общее значение V задается (псевдокодом):

V = 1
For Each t in T
    V = V * (t + 1)
Next t
V = V - 1 // correction

Со стороны затрат единицы одного типа имеют одинаковую стоимость. Но единицы разных типов имеют уникальные иррациональные издержки. Количество типов велико, но нам присваивается массив затрат типа C[], который сортируется от наименьшего к самому большому. Пусть далее предположим, что массив типов типов T[] также сортируется по цене от минимального до самого большого. Тогда общая стоимость U представляет собой просто сумму каждой единицы стоимости:

U = 0
For i = 0, i < NumOfValueTypes
    U = U + T[i] * C[i]
Next i

Пока все хорошо. Итак, вот проблема: заданный продукт P со значением V и стоимостью U, найдите продукт Q со стоимостью U' и значением V', имеющей минимальный U' такой, что U' > U, V'/U' > V/U.

Ответ 1

Проблема, которую вы описали, представляет собой проблему нелинейного целочисленного программирования, поскольку она содержит произведение целочисленных переменных t. Его выполнимость не закрывается из-за строгих неравенств, которые можно оперировать с помощью нестрогих неравенств и добавления небольшого положительного числа (epsilon) в правые части. Тогда проблему можно сформулировать в AMPL следующим образом:

set Types;
param Costs{Types};      # C
param GivenProductValue; # V
param GivenProductCost;  # U
param Epsilon;

var units{Types} integer >= 0; # T
var productCost = sum {t in Types} units[t] * Costs[t];

minimize cost: productCost;
s.t. greaterCost: productCost >= GivenProductCost + Epsilon;
s.t. greaterValuePerCost:
  prod {t in Types} (units[t] + 1) - 1 >=
    productCost * GivenProductValue / GivenProductCost + Epsilon;

Эта проблема может быть решена с помощью решения нелинейного целочисленного программирования, такого как Couenne.

Ответ 2

Честно говоря, я не думаю, что есть простой способ решить эту проблему. Лучше всего было бы написать систему и решить ее с помощью решателя (Excel solver выполнит трюки, но вы можете использовать Ampl для решить эту нелиенарную программу.)

Программа:

Define: U;
        V;
        C=[c1,...cn];

Variables: T=[t1,t2,...tn];

Objective Function: SUM(ti.ci)

Constraints:

For all i: ti integer
SUM(ti.ci) > U 
(PROD(ti+1)-1).U > V.SUM(ti.ci)

Хорошо работает с excel (вы просто заменяете > U нa >= U + d, где d - это значимое количество затрат (т.е. если C = [1.1, 1.8, 3.0, 9.3] d = 0.1), так как excel не допускает строгих неравенств в решателе.)

Я думаю, что с реальным решателем, вроде Ampl, он будет работать отлично.

Надеюсь, что это поможет,