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

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

ОГЛАВЛЕНИЕ

Следующая >>

Например можно говорить о стандартном наборе марок цемента или
размеров гвоздей. Очевидно, что существует много различных вариантов
стандартных наборов. Для того, чтобы сравнивать различные наборы,
введем два показателя - показатель маргинальной прибыли и показатель
фиксированных издержек. Как известно, маргинальной прибылью
называется прибыль, определяемая с учетом только переменных затрат.
Производство каждого продукта требует, помимо переменных издержек
(пропорциональных объему выпуска), фиксированных или постоянных
(условно постоянных) издержек, то есть не зависящих от объема выпуска.
Пусть имеется n продуктов (строительных материалов и изделий),
производство которых технологически осуществимо в рассматриваемом
периоде времени. Обозначим aj - переменные затраты на производство j-го
продукта, bj - постоянные или фиксированные затраты, pj - маргинальная
прибыль на единицу j-го продукта, Vj - потребность в j-ом продукте. Пусть


17
стандартный набор состоит из множества Q продуктов. Тогда совокупная
маргинальная прибыль составит
P( Q) = ? p j Vj , (2.1)
j?Q

а совокупные фиксированные затраты
B( Q) = ? bj . (2.2)
j?Q

Разность П = P - B составляет прибыль, которую дает стандартный набор
Q.
Для постановки задачи определения оптимального стандартного
набора обозначим через m число различных типов потребностей в
строительных материалах и изделиях, Ri - множество продуктов, которые
могут удовлетворить i-ую потребность (например, покрытие крыши,
фундамент для дома, утеплитель и т.д.), vij - количество j-го продукта,
требуемого для удовлетворения i-ой потребности. Обозначим также Wj -
множество потребностей, удовлетворяемых продуктом из
j-ым
стандартного набора Q. В этом случае потребность в j-ом продукте
составит
? v ij .
Vj = (2.3)
i?Wj


Множество продуктов Q будем называть полным, если для любой
потребности i найдется продукт j?Q такой, что i?Wj (то есть найдется
продукт, который может удовлетворить i-ую потребность). Очевидно, что
стандартный набор должен быть полным множеством продуктов.
Постановка задачи. Определить полное множество Q, для которого
величина прибыли

? ( p j Vj ? b j )
П( Q) = (2.4)
j?Q

максимальна.


18
Замечание 1. В случае, если рассматривается достаточно большой
период времени, при определении прибыли и фиксированных затрат
необходимо учитывать их изменение во времени, а также учитывать
инфляцию и дисконтирование.
Замечание 2. В плановой экономике задача стандартизации
решалась, как правило, по критерию минимума совокупных затрат. В
рыночной экономике такой критерий уже не годится, поскольку он не
учитывает потребительной стоимости продуктов.
Дадим постановку задачи в терминах теории графов. Для этого
определим двудольный граф G(X, Y, U), где X - множество вершин,
соответствующих продуктам, Y - множество вершин, соответствующих
потребностям. Вершины j?X соединяются дугами (ji) с вершинами i?Y в
том и только в том случае, когда i?Wj (то есть продукт j удовлетворяет i-
ую потребность). Для каждой вершины j?X зададим числа bj, pj, а для
каждой дуги (j, i) - числа vij.
Подмножество Q множества вершин X, соответствующее полному
множеству продуктов (или стандартному набору продуктов), назовем
покрытием двудольного графа G. Обозначим Ti - множество продуктов из
набора Q, каждый из которых может удовлетворить потребность i.
Очевидно, что для удовлетворения i-ой потребности будет выбран
продукт, для которого маргинальная прибыль максимальна. С учетом
этого замечания критерий (2.4) можно записать в следующем виде:
? max p j v ij ? ? b j .
П= (2.5)
j?T
i?Y j?Q
i


Задача свелась к поиску покрытия двудольного графа, для которого
(2.5)принимает максимальное значение.
Пример. Пусть имеется четыре продукта и четыре типа
потребностей. При этом продукт 1 может удовлетворить первую


19
потребность, продукт 2 - первую и вторую, продукт 3 - первую, вторую и
третью, и наконец, продукт 4 - все четыре типа потребностей. Двудольный
граф G, соответствующий этому случаю приведен на рис. 2.1.


П Р О Д У К Т Ы (Х)
[1,15] [3,10] 2 [1,15] [2,20]
1 3 4




[10] 1 [20] 2 [15] 3 4
[5]
П О Т Р Е Б Н О С Т И (Y)
Рис. 2.1.

Числа соответствующие маргинальной прибыли и
p j, b j,
фиксированным издержкам для j-го продукта указаны в квадратных
скобках у вершин множества X, а числа vi, соответствующие величине i-ой
потребности, - в квадратных скобках у вершин множества Y (для
упрощения задачи мы взяли vij = vi для всех j).
Чтобы решить эту задачу заметим, что продукт 3 включать в
стандартный набор явно нецелесообразно. Действительно, продукт 4 мы
обязаны включить в набор, поскольку только он может удовлетворить
четвертую потребность. Но тогда и третью потребность выгоднее
удовлетворять за счет четвертого продукта, а не третьего, так как у
четвертого продукта маргинальная прибыль больше. Осталось рассмотреть
четыре варианта с продуктами первым и вторым.
I вариант: в набор входят оба продукта, - и первый и второй:
Q = {1, 2, 4}, при этом первый продукт удовлетворяет первую потребность
в объеме V1 = 10, второй - вторую в объеме V2 = 20, четвертый - третью и
четвертую в суммарном объеме V4 = v3 + v4 = 20. Имеем:

20
П(1;2;4) = p1v1 + p2v2 + p4v4 - b1 - b2 - b4 = 40 + 60 + 40 - 45 = 95.
II вариант: в набор входят первый и четвертый продукты: Q = {1, 4},
при этом первый продукт удовлетворяет первую потребность в объеме
V1 = 10, а четвертый - все остальные в объеме V4 = 40. Имеем:
П(1;4) = p1v1 + p4v4 - b1 - b4 = 40 + 80 - 35 = 85.
III вариант: в набор входят второй и четвертый продукты: Q = {2, 4},
при этом второй продукт удовлетворяет первую и вторую потребность в
объеме V2 = 30, а четвертый - третью и четвертую в объеме V4 = 20.
Имеем:
П(2;4) = p2v2 + p4v4 - b2 - b4 = 90 + 40 - 30 = 100.
вариант: в набор входит только четвертый продукт
IV
удовлетворяющий все потребности в объеме V4 = 50. Имеем:
П = 100 - 20 = 80.
Легко видеть, что оптимальным является III вариант, которому
соответствует стандартный набор из двух продуктов - второго и
четвертого. Поставленная задача является экстремальной задачей
комбинаторного типа, сложности решения которой хорошо известны [1].
Рассмотрим ряд частных случаев, допускающих эффективные алгоритмы
решения.
Будем говорить, что продукт j накрывает продукт k, если Wj ? Wk,
то есть продукт j может удовлетворить все потребности, которые
удовлетворяет продукт k.
Пусть существует упорядочение продуктов j1, j2, ... , jn такое, что
каждый продукт накрывает все следующие за ним. Так, для
рассмотренного выше примера рис. соответствующее
(см. 2.1)
упорядочение - (4, 3, 2, 1). Построим сеть следующим образом. Вершины
сети соответствуют продуктам j1, j2, ... , jn и одна вершина jn+1 = 0 является



21
выходом сети (вершина j1 является входом). Вершины jk, js (s > k)
соединяются дугой (jk, js), длина которой

( )
l jk js = p jk Vjk ? Vjs ? b jk . (2.6)
Vj0 = 0 по определению.

Содержательный смысл дуги (jk, js) состоит в том, что продукт jk
удовлетворяет все потребности, которые он может удовлетворить за
исключением тех, которые может удовлетворить продукт js, а длина дуги
(jk, js) при этом определяет прибыль, получаемую от продукта js. При таком
построении сети любой путь, соединяющий вершину j1 с вершиной j0
определяет некоторый стандартный набор продуктов и наоборот, любому
стандартному набору продуктов соответствует некоторый путь в сети,
соединяющий вход j1 с выходом j0. Каждой дуге (jk, lj) пути,
соединяющего вход с выходом соответствует продукт jk, входящий в
стандартный набор. Поэтому длина пути равна прибыли, получаемой от
соответствующего этому пути стандартного набора. Таким образом задача
определения оптимального стандартного набора свелась к задаче поиска
пути в сети, имеющего максимальную длину. Для этой задачи, как
известно, существуют эффективные алгоритмы [1]. Для графа рис. 2.1
соответствующая сеть приведена на рис. 2.2.



(60)
(20) (80)
(-10) (0) (50) (25)
4 3 2 1 0
[0] [100]
[20] [70]
[-10]
(20) (80)
(30)

Рис. 2.2.


22
Длины дуг указаны в круглых скобках. В данном случае для
определения пути максимальной длины, учитывая, что вершины сети
правильно пронумерованы (для каждой дуги (ik, il) имеет место k < l),
эффективнее всего применить алгоритм Форда для сетей, имеющих
правильную нумерацию [1]. Согласно этому алгоритму, потенциал
вершины j1 полагается равным 0, а потенциалы следующих вершин ?j
определяются последовательно:

[ ]
? jl = max ? jk + l jk jl . (2.7)
k<l

Заметим, что фактически это метод динамического программирования
Беллмана применительно к данной задаче. При этом потенциал вершины
jn+1 = 0 будет равен длине максимального пути. Сам максимальный путь
определяется «обратным ходом», а именно, начиная с вершины jn+1
определяется вершина js, такая что
? jn +1 ? ? js = l js jn +1 .

Эта вершина принадлежит пути максимальной длины. Далее, начиная с
вершины js аналогичным образом определяется следующая вершина а т.д.,
пока не будет получена вершина j1. Потенциалы вершин, полученные
описанным алгоритмом, указаны в квадратных скобках у
соответствующих вершин (рис. 2.2). Путь максимальной длины выделен
толстыми дугами. Как легко видеть, мы получили тот же стандартный
набор Q = {2, 4}, что и в примере 2.1, где решение было получено методом
перебора. Рассмотренная модель позволяет решить задачу и в более
сложном случае. А именно, до сих пор мы считали, что прибыль от
продажи единицы продукта не зависит от объема продажи. На самом деле
с ростом объема продаж прибыль на единицу продукта, как правило,
уменьшается (хотя объем прибыли, естественно, растет с ростом объема
продаж). Это происходит потому, что увеличение объема продаж


23
происходит, как правило, за счет вытеснения с рынка конкурирующих
продуктов, что достигается за счет снижения цены, а значит уменьшения
маргинальной прибыли на единицу продукта.
Пусть известна зависимость цены, а значит и маргинальной прибыли
на единицу j-го продукта от объема его продаж pj(Vj). В рассмотренной
выше модели эту зависимость легко учесть, поскольку для каждой дуги
(jk, jl) известен продукт jk, который соответствует этой дуге и объем этого

(V )
? Vjl . Следовательно, легко определить длину дуги,
продукта jk

соответствующую совокупной прибыли от продажи продукта jk:

)( )
(V
l jk jl = p jk ? Vjl ? V jk ? V jl ? b jk . (2.8)
jk


Вернемся к примеру 2.1 и примем, что маргинальная прибыль на
единицу продукта уменьшается всякий раз при увеличении объема продаж
за счет удовлетворения новой потребности. Соответствующие значения
маргинальной прибыли приведены в таблице 2.1.
Таблица 2.1.
Потребности
1 2 3 4
Продукты

1 4

2 2,5 3

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

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

ОГЛАВЛЕНИЕ

Следующая >>