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

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

10 голосов
/ 13 июня 2011

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

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

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

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

Что касается затрат, то единицы одного типа имеют одинаковую стоимость.Но единицы разных типов имеют уникальные иррациональные затраты.Количество типов велико, но нам дан массив значений типа C[], который отсортирован от наименьшего к наибольшему.Далее предположим, что массив типа type 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.

Ответы [ 2 ]

1 голос
/ 05 июля 2012

Вы описали проблему нелинейного целочисленного программирования, поскольку она содержит произведение целочисленных переменных t.Его набор осуществимости не закрыт из-за строгих неравенств, которые можно обойти, используя нестрогие неравенства и добавляя небольшое положительное число (эпсилон) в правые части.Тогда проблему можно сформулировать в 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 .

1 голос
/ 14 июня 2011

Честно говоря, я не думаю, что есть простой способ решить эту проблему.Лучше всего было бы написать систему и решить ее с помощью решателя (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 на> = U + d, где d - это значимое число затрат - (т.е. если C = [1.1, 1.8, 3.0, 9.3] d = 0.1), поскольку excel не допускает строгих неравенств в решателе.)

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

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

...