<< Предыдущая

стр. 4
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

3 0,5 0,7 1

4 0,9 1 1,5 2


Так, например, прибыль от продукта 4 на единицу продукта равна 2,
если он удовлетворяет только четвертую потребность. Если объем продаж
расширяется, и продукт 4 удовлетворяет и четвертую и третью
потребности, то это достигается за счет снижения цены на 0,5, а значит и


24
маргинальной прибыли до величины 1,5 (заметим, что совокупный объем
маргинальной прибыли при этом возрастает от 10 до 30). Дальнейший
рост объема продаж, то есть удовлетворение второй потребности, требует
дальнейшего снижения цены четвертого продукта на 0,5 и снижения
маргинальной прибыли на единицу продукта до 1,0 и т.д. На основе
таблицы 2.1 и формулы (2.8) можно определить новые длины дуг для сети
рис. 2.2. Получаем сеть, изображенную на рис. 2.3.



(20)
(10) (25)
(-10) (0) (50) (25)
4 3 2 1 0
[85]
[0] [60]
[-10] [10]
(9,5) (65)
(7,5)

Рис. 2.3.

В данном случае оптимальный стандартный набор состоит уже из
трех продуктов: Q = {1, 2, 4}.
Решение задачи в общем случае, когда не удается получить
упорядоченную последовательность накрывающих продуктов, требует
применения комбинаторных методов. Опишем алгоритм решения задачи,
основанный на методе ветвей и границ. Описание алгоритма дадим на
примере 2.1.
Определим максимально возможный есть пользующийся
(то
спросом) выпуск j-го продукта:

? v ij .
Vjm = (2.9)
i?Wj


Построим график прибыли от j-го продукта в зависимости от объема его
выпуска (рис. 2.4).

25
C



pjVj - bj
0
Vjm


bj

Рис. 2.4.

Заметим, что пунктирная прямая ОС является оценкой сверху
величины прибыли при любом выпуске Vj и совпадает с величиной
прибыли при максимальном выпуске. Определим наклон этой прямой:
p j V jm ? b j bj
qj = = pj ? . (2.10)
V jm V jm

Примем qj за оценку прибыли на единицу j-го продукта при нулевых
фиксированных затратах и рассмотрим задачу определения оптимального
стандартного набора в этом случае. Поскольку фиксированные затраты
равны нулю, то эта задача легко решается. А именно, каждая потребность i
удовлетворяется тем продуктом, для которого оценка прибыли qivij
максимальна. Очевидно, что величина полученной прибыли является
оценкой сверху величины прибыли в оптимальном решении исходной
задачи.
Для рассматриваемого примера 2.1 имеем:
w1 = {1}; w2 = {1, 2}; w3 = {1, 2, 3}; w4 = {1, 2, 3, 4};
V1m = 10; V2m = 30; V3m = 45; V4m = 50;
q1 = p1 - b1/V1m = 2,5; q2 = 22/3; q3 = 2/3; q4 = 1,6.




26
Очевидно, что в оценочной задаче первая и вторая потребность
удовлетворяются вторым продуктом, а третья и четвертая - четвертым.
При этом оценка сверху величины прибыли составит
$
П = 80 + 32 = 112.
Заметим, что оценка прибыли для третьего продукта является точной,
поскольку выпуск третьего продукта максимален. Для четвертого
продукта оценка является завышенной, поскольку выпуск четвертого
продукта существенно ниже максимального. Для уточнения оценки
проведем ветвление, то есть рассмотрим два непересекающихся
подмножества решений. В первом подмножестве четвертый продукт
удовлетворяет первую потребность, а во втором - не удовлетворяет.
Получим оценку для первого подмножества. Поскольку первая
потребность удовлетворяется за счет четвертого продукта, то первый
продукт не нужен. Для остальных продуктов получаем следующие
оценочные прибыли на единицу продукта:
q3 = 4/7;
q2 = 2,5; q4 = 1,6
(при получении оценок для второго и третьего продуктов первая
потребность не включается в объемы максимального выпуска, поскольку
она удовлетворяется за счет четвертого продукта). В данном случае вторая
потребность удовлетворяется вторым продуктом, а все остальные -
четвертым. Оценка сверху величины прибыли для данного подмножества
решений составит
$
П (1 > 4) = 50 + 48 = 98
$
(запись П (1 > 4) обозначает оценку сверху величины прибыли для
подмножества решений, в которых первая потребность удовлетворяется за
счет четвертого продукта).
Получим оценку для второго подмножества решений, в которых
первая потребность не удовлетворяется за счет четвертого продукта.

27
Оценочные прибыли для первых трех продуктов будут, очевидно, такими
же, как в (2.11). Изменится только оценка q4, поскольку уменьшится
максимальный выпуск V4m = 40 вместо 50. Имеем
q2 = 22/3; q3 = 2/3;
q1 = 2,5; q4 = 1,5.
Оптимальное решение оценочной задачи имеет вид: первая и вторая
потребности удовлетворяются вторым продуктом, а третья и четвертая -
четвертым. Оценка сверху величины прибыли для данного подмножества
равна
П(1 > 4) = 22/3?30 + 1,5?20 = 110
$ /

П(1 > 4) означает оценку сверху величины прибыли для
$ /
(запись

подмножества решений, в которых первая потребность не
удовлетворяется за счет четвертого продукта).
Согласно методу ветвей и границ, из двух подмножеств выбирается
подмножество с большей оценкой, то есть второе подмножество.
Анализируя оценку для второго подмножества мы видим, что оценка
прибыли для третьего продукта является точной, а для четвертого
завышенной, поскольку его выпуск меньше максимального. Поэтому
второе подмножество делим на два подмножества. В первом вторая
потребность удовлетворяется четвертым продуктом, а во втором - не
удовлетворяется четвертым продуктом.
Оценим первое подмножество. Имеем величины оценочных
прибылей:
q1 = 2,5; q2 = 2; q3 = 0,4; q4 = 1,5
(при определении оценочных прибылей необходимо учитывать, что объем
второй потребности не входит в максимальные выпуски для второго и
третьего продуктов, а объем первой потребности не входит в
максимальный выпуск для четвертого продукта).



28
В данном случае в оптимальном решением оценочной задачи первая
потребность удовлетворяется за счет первого продукта, а остальные - за
счет четвертого. Величина оценки для данного подмножества решений
равна
П(1 > 4; 2 > 4) = 25 + 60 = 85.
$ /
Оценим второе подмножество, в котором ни первая, ни вторая
потребности не удовлетворяются за счет четвертого продукта. Оценочные
прибыли будут равны
q2 = 22/3; q3 = 2/3;
q1 = 2,5; q4 = 1,0.
В оптимальном решении оценочной задачи первая и вторая
потребности удовлетворяются за счет второго продукта, а третья и
четвертая за счет четвертого. Оценка прибыли для данного
-
подмножества будет равна
П(1 > 4; 2 > 4) = 80 + 20 = 100
$ / /

(запись П(1 > 4; 2 > 4) означает оценку сверху величины прибыли для
$ / /
подмножества решений, в которых ни первая, ни вторая потребности не
удовлетворяется за счет четвертого продукта).
Сравнивая все рассмотренные подмножества решений (их три, с
оценками 98, 85 и 100) мы видим, что последнее подмножество имеет
наибольшую оценку. Поэтому это подмножество и выбирается для
дальнейшего разбиения (ветвления). Заметим, однако, что полученная
$
оценка П = 100 является точной, поскольку в оптимальном решении
оценочной задачи оба продукта, - 2 и 4, образующие стандартный набор,
выпускаются максимально возможными объемами. Поэтому полученное
решение является оптимальным решением исходной задачи.
Дерево ветвлений (разбиения множества решений на подмножества)
приведено на рис. 2.5 (толстыми дугами выделена ветвь, ведущая к


29
оптимальному решению, оценки подмножеств указаны в соответствующих
вершинах).



112
(4 > 1)
/
(4>1)

98 110

(4 > 2)
/
(4>2)

85 100


Рис. 2.5.

В случае, если для нескольких продуктов, вошедших в оптимальное
решение оценочной задачи, оценка прибыли является завышенной,
следует провести ветвление по каждому из этих продуктов и выбрать для
дальнейшего разбиения тот продукт, для которого разность оценок
подмножеств максимальна.
При решении задач большого размера построение всего дерева
ветвлений является задачей, требующей большого времени и объема
памяти. В этих случаях рекомендуется рандомизированный вариант
метода ветвей и границ, в котором подмножества выбираются случайным
образом, однако, вероятность выбора того или иного подмножества
пропорциональна его верхней оценке. Решение большого числа задач
показало, что описанный алгоритм в рандомизированном варианте
позволяет получать достаточно хорошие решения.
Рассмотрим еще один пример, когда не существует
последовательности накрывающих продуктов, и количества различных
продуктов, удовлетворяющих одну и ту же потребность, различны.

30
Пример 2.2. Имеются четыре продукта и четыре потребности.
Данные об объемах, маргинальных прибылях на единицу продукта и
фиксированных затратах представлены на рис. 2.6.


ПРОДУКТЫ

[5,20] [4,30] 2 [3,10] [2,15]
1 3 4
(15) (25) (15)
(30)
(10) (20)
(10) (20)

1 2 3 4
[5]

ПОТРЕБНОСТИ

Рис. 2.6.

Первое число в квадратных скобках у вершин, соответствующих
продуктам, определяет маргинальную прибыль на единицу продукта, а
второе - фиксированные затраты. Числа в круглых скобках у дуг
определяют количество соответствующего продукта, необходимое для
удовлетворения соответствующей потребности.
I шаг. Получение верхней оценки прибыли для оптимального
стандартного набора.
Имеем:
V1m = 25; V2m = 45; V3m = 25; V4m = 50;
q1 = 5 - 20/25 = 4,2; q2 = 4 - 30/45 = 31/3; q3 = 3 - 10/25 = 23/5; q4 = 2 - 15/50 = 1,7.
Так как q1v11 = 4,2?10 < q2v12 = 662/3, то первая потребность

<< Предыдущая

стр. 4
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>