Книги по разным темам Pages:     | 1 |   ...   | 14 | 15 | 16 | 17 | 18 |   ...   | 34 |

154 Возможность выбора (k), удовлетворяющего условию Полученное нами решение представлено в параметрической форме, т.е. существует некоторое множество решений, i = 1, n (4.3.7) базируется на допущении, что любая цена Pi,, соответствующее различным перестановкам элементов внутри входящая в выражение (4.3.3) для s(i), пренебрежимо мала по вектора U*, сохраняющим справедливость условий (4.3.8) сравнению с B, т.е. Pi = 0(B). С практической точки зрения через выполнение соотношения (4.3.7) для, вообще говоря, это допущение может означать нежесткость финансового огразличных k. Также следует отметить, что вектор U* может раничения (4.3.5), т.е. всегда есть дополнительный финансосодержать не только k первых, но, вообще говоря, k любых вый ресурс, чтобы закупить 1 единицу товара по цене Pi, каненулевых элементов, удовлетворяющих условиям (4.3.7) и кой бы эта цена не была.

(4.3.8).

Покажем, что решением вышеприведенной ЗЛП являетДля того, чтобы получить решение задачи для конкрется вектор U*:

ных значений u(i)*, u(j)*, т.е. определить: какие u(i)* 0, а U*T = (u(1)*=s(1), u(2)*=s(2), Е, u(k)*= (k)s(k), какие u(j)* = 0, нам необходимо воспользоваться дополниu(k+1)*=0, Е, u(n)*=0), тельной информацией, содержащейся в ее условиях. Попытагде U*T - вектор-строка, соответствующий вектору-столбцу емся использовать знание соотношений между коэффициенU*, а (k) задается соотношением (4.3.7). Решением ДЗЛП тами d(i) для нахождения вектора U** из множества U всех является вектор X* размерности n + 1:

допустимых векторов U*, который и будет решением задачи X*T = (x(1)*=0, x(2)*=d(1), x(3)*=d(2), Е, (4.3.4) при соблюдении условий (4.3.8) в виде:

x(k+1)*= (k)d(k), x(k+2)*=0, Е, x(n+1)*=0).

n Можно легко проверить, что для заданных векторов U* (4.3.9) F (D,U )= d (i)u(i)* max и X* выполняется соотношение i =СTU* = X*TA0, при условиях n откуда по теореме 4.3.2: U* и X* - оптимальные решения (4.3.10) (1- d(i))u(i) = B, прямой и двойственной ЗЛП, соответственно.

i=Поскольку коэффициент (k) имеет специальный вид u(1)* = s(1) (4.3.7) то, нетрудно видеть, что условие допустимости (4.3.5) u(2)* = s(2) выполняется как равенство в виде:

n (4.3.11) u(k)* = (k) s(k) < s(k) (1- d (i ))u(i)* = B i= u(k+1)* = u(1)* = s(1) u(2)* = s(2) u(n)* =0, где вектор U* может иметь не только k первых, но, вообще говоря, k любых ненулевых элементов, и удовлетворяет усло(4.3.8) u(k)* = (k) s(k) < s(k) виям (4.3.8).

u(k+1)* = Вектор U** будем искать непосредственно в виде (4.3.11), т.е. в виде u(i)** 0, i = 1, k; u(j)** = 0, j = k + 1, n.

u(n)* = 0, (B B).

156 Решение.

где r {1,Е,R( j )}.

Упорядочим путем соответствующих перестановок Для доказательства теоремы нам необходимо показать, множество D = {d(1), d(2), Е, d(n)} так, что d(1) > d(2) > Е что k> d(n) (случай более сложный, и его мы рассматривать не * d (D1,k1)ui (U 1,k1) > i будем). Полученное таким образом множество обозначим i=(4.3.14) буквой D. Множество D является упорядоченным множестk ( j,r) * вом. Для элементов D, очевидно, справедливо: 1 - d(1) < 1 - > (Dj,k( j,r))ui (U j,k( j,r)) d i d(2) < Е< 1 - d(n). Выделим из D подмножество D1, k1, со- i= j стоящее из первых k1 элементов этого множества:

r {1,Е,R(j)}, D1, k1 = {d(1), d(2), Е, d(k1)} D где di(, ) = d(i,, ), ui(, ) = u(i,, ), и либо j 1, либо k(j,r) k1.

так, что Рассмотрим два подмножества: D1, k1 D и любое подkмножество вида Dj, k ( j,r) D. Допустим, что l элементов (1-d(i)) u(i) = B, (4.3.12) i=этих подмножеств совпадают (для полностью несовпадаюгде u(i) - i-компонента вектора U*1, k1, который получается щих элементов доказательство является более простым).

из вектора U*, теми же перестановками, что и множество D Произведем перестановку элементов подмножеств D1,kиз множества D и содержит только k1 первых его элементов.

и Dj, k (j,r) следующим образом:

Т.е. если i-элемент множества D переходит в l-элемент под1. В качестве первых l элементов каждого из подмномножества D1, k1, то и i-компонента вектора U* переходит в жеств возьмем их совпадающие элементы, расположенные в l-компоненту вектора U*1, k1 (при l k1). порядке убывания.

Кроме подмножества D1, k1 и вектора U*1, k1 без поте2. На оставшихся, соответственно k1Цl для подмножери общности будем рассматривать только упорядоченные ства D1, k1 и k (j,r)Цl для подмножества Dj,k(j,r), позициях расподмножества и вектора вида Dj, k(j,r) и U*j, k(j,r). Подмно- положим оставшиеся (несовпадающие) элементы этих поджество Dj, k(j,r) получается из множества D путем выборки множеств, беря их также в порядке убывания. Вновь из этого множества k(j,r) элементов, начиная с j-го элемента образованные подмножества будем обозначать D1, k1 и Dj, (при выборке допускаются пропуски), с выполнением услоk(j,r).

вия аналогичного условию (4.3.12) в виде:

Правило определения номера r задавать не будем.

k j,r ( ) Для первых l элементов подмножеств Dj, k (j,r) и D1, k(4.3.13) (1-d(i)) u(i)=B, имеет место:

i=d1 (D1, k1) = d1 (D1, k(1,r)), d2 (D1, k1) = d2 (D1, k(1,r)), Е, r - номер выборки, где r {1,Е,R( j )}, а R( j ) - общее коли dl (D1, k1) = dl (D1, k(1,r)).

чество выборок такого вида, начинающихся с j-го элемента В качестве примера подмножеств D1, k1 и Dj, k(j,r) расмножества D. Вектор U*j, k(j,r) получается аналогичным обсмотрим следующие подмножества (совпадающие элементы разом.

подмножеств подчеркнуты):

Теорема 4.3.3.

D1, k1 (k1=15): 0.59.58.57.56.55.54.53.52.51.50.F(D1, k1; U*1,k) = max F(Dj, k(j,r); U*j, k(j,r)),.48.47.46.45, 158 kDj, k( j,r) ( j=5, k(5,r)=13): 0.55.54.53.50.49.48.33.* (1-d (D1,k1))u(U1,k1)= ii.31.30.29.25.(4.3.17) i=l+Подмножества D1, k1 и Dj, k( j,r) = D5, k(5,r) соответстk(1,r) * венно будут иметь вид:

(1-d (D1,k(1, r)))u(U1,k(1,r)) =B-B1.

ii i=l+D1, k1: 0.55.54.53.50.49.48.59.58.57.56.52.51.После вводных замечаний перейдем непосредственно к.46.45, доказательству теоремы 4.3.3.

Dj, k(j,r): 0.55.54.53.50.49.48.33.32.31.30.29.Доказательство.

.21.

Разделим левую и правую части неравенства (4.3.16) на Согласно правилам (1) - (2) произведем также переста(4.3.17), получим:

новку элементов векторов U*j, k(j,r) и U*1, k1, в результате kполучим вектора U*j, k(j,r) и U*1, k1, для первых l элементов * di (D1,k1)ui (U 1,k1) которых будут иметь место соотношения:

i=l+>.

u1(U*1, k1) = u1(U*j, k(j,r)), u2(U*1, k1) = B- Bk 1,r ( ) = u2(U*j, k(j,r)), Е, ul(U*1, k1) = ul(U*j, k(j,r)).

* di (D1,k(1,r))ui (U 1,k(1,r)) Далее введем обозначение:

i=l+ll.

B- Bd (D1,k1)u(U* 1,k1)= d (D1,k(1,r))u(U* 1,k(1,r))=F1.

iiii i=1i=1 Или, что то же самое, kТаким образом, для доказательства теоремы нам необхоdi(D1,k1)u(U*1,k1) i димо показать, что i= l+k1 > k* F1+ d(D1,k1)u(U1,k1)> ii (1- di(D1,k1))u(U*1,k1) i i=l +(4.3.15) i= l+(4.3.18) k(1,r) k 1,r ( ) * F1+ d(D1,k(1,r))u(U1,k(1, r)).

ii di(D1,k(1,r))u(U*1,k(1,r)) i i=l +i= l+.

Или, что то же самое, k(1, r) k(1- di(D1,k(1,r)))u(U*1,k(1,r)) i di(D1, k1) ui(U*1, k1)> i= l+ (4.3.16) i =l +1 Обозначим k 1,r ( ) (4.3.19) d = min{d (l+1), d (l+2),Е, d (k)} D1, k1;

di(D1, k(1,r)) ui(U*1, k(1,r)).

(4.3.20) d = max{d (l+1), d (l+2),Е, d (k (1,r))} D1, k(1,r).

i =l +Очевидно в силу упорядоченности D1, k1 и D1, k (1,r):

Введем обозначение:

l d = d (k) D1, k1, а d = d (l+1) D1, k (1,r).

* (D1, k1))u(U1, k1)= (1- d ii Также очевидно, в силу того, что только l элементов D1, i =k1 и D1, k (1,r)совпадают, имеет место l * (4.3.21) d > d, (1- di(D1, k(1, r)))u(U1, k(1,r)) =B1.

i i =и поскольку в силу условий задачи Тогда в силу (4.3.12) и (4.3.13):

0 < di(Х) < 1, i: n i 1, 160 kи, очевидно, du(U*1,k1) i (4.3.22) 1 - d = max{1 - d (l+1), 1 - d (l+2),Е, 1Цd (k)} = 1 - d (k), i=l+= k{d (l+1), d (l+2),Е, d (k)} D1, k1, * (1-d)u(U 1,k1) i и (4.3.27) i=l+k(4.3.23) 1Цd= min{1Цd (l+1), 1Цd (l+2),Е, 1Цd (k (1,r))}=1Цd (l+1), d u(U*1,k1) i {d (l+1), d (l+2),Е, d (k)} D1, k (1,r), d i=l+=.

то и k(1-d) (1-d) u(U*1,k1) i (4.3.24) 1Цd > 1 - d.

i=l+Из (4.3.19) и (4.3.22) следует Преобразуем левую часть неравенства (4.3.26):

kk(1,r) * (D1, k1)ui (U 1,k1) di du(U 1,k(1,r)) i i= +> i=l+k1 = k(1,r) * ( 1 - di (D1, k1) )ui (U 1,k1) (1- d )u(U 1,k(1,r)) i i= +(4.3.28) 1=l+kk(1,r) * d ui (U 1,k1) d u(U 1,k(1,r)) (4.3.25) i i= +1 d i=l+>,.

= kk(1,r) (n-d ) * (1 - d)ui (U 1,k1) (1- d ) u(U 1,k(1,r)) i i= +i=l+а из (4.3.20) и (4.3.23) - Из (4.3.21) и очевидного ограничения 0 < d, d < 1 следует k 1,r ( ) dd du(U*1,k(1,r)) i (4.3.29) >.

i=l+(1- d ) (1- d ) > k 1,r ( ) Откуда с учетом (4.3.25) и (4.3.26):

(1- d) u(U*1,k(1,r)) i (4.3.26) ki=l+di(D1,k1)u(U*1,k1) k 1,r i ( ) d i=l+di(D1,k(1,r)) u(U*1,k(1,r)) >> i ki=l+1 (1- d ).

(1- di (D1,k1))u(U*1,k1) k 1,r ( ) i i=l+(4.3.30) (1- di(D1,k(1,r)))u(U*1,k(1,r)) i k(1,r) i=l+di(D1,k(1,r))u(U*1,k(1,r)) Преобразуем правую часть неравенства (4.3.25): i d i=l+.

>> k(1,r) (1- d ) (1- di (D1,k(1,r)))u(U*1,k(1,r)) i i=l+Откуда 162 kгде Uk1 Un и Un - соответственно k1-мерное и n-мерное евк* d(D1,k1)u(U1,k1) ii лидовы пространства. При этом проекции вектора U*1, k1 на i=l+kостальные n-k1 координатных осей Un равны нулю, т.е. имеет * (1-d(D1,k1))u(U1,k1) ii место:

i=l+(4.3.31) U** = U*1, k.

k(1,r) * Проекции на оси 1,Еk1-1 являются максимально допусd(D1,k(1,r))u(U1,k(1,r)) ii i=l+тимыми. Т.е. u(i)=s(i), i = 1,k1-1; а проекция на ось k1 задает>.

k(1,r) * ся соотношением u(k1)= (k1) s(k), где коэффициент (k1) (1-d(D1,k(1,r)))u(U1,k(1,r)) ii i=l+1 имеет вид (4.3.7) при k=k1, т.е. U*1, k1 и будет являться реНо поскольку согласно (4.3.17): шением задачи (4.3.4) при ограничениях (4.3.5):

k1 k* * T (1-d(D1, k1))u(U1, k1)= (4.3.32), d D1,k1 ui U 1,k1 = max C U ( ) ( ) ii i U i=l+i=k(1, r) AU A0.

* (1-d(D1, k(1, r)))u(U1, k(1, r)) =B-B, ii Вообще говоря, можно рассматривать множество D, i=l+подмножества D1, k1 и Dj, k(j,r) как вектора в соответствуют.е. знаменатели обеих дробей, стоящих в левой и правой часщих евклидовых пространствах размерности n, k1, k(j,r), сотях неравенства(4.3.31), совпадают, то имеет место (4.3.16):

ответственно, а выражение, стоящee в правой части равенства k(4.3.32), - как скалярное произведения в пространстве разd(D1,k1)u(U*1,k1)> ii i= l+мерности n, а в левой части этого равенства - как скалярное k 1,r ( ) произведение в пространстве размерности k1.

d(D1,k(1,r))u(U*1,k(1,r)) ii Решение задачи (4.3.9) - (4.3.11) и доказательство тео, i= l+ремы 4.3.3 могут быть проиллюстрированы рисунками 4.3.1 и и справедливо соотношение (4.3.15). Далее с учетом инвари4.3.2, которые для наглядности исполнены в различных масантности (4.3.14) по отношению к перестановкам (1) - (2), на штабах. На этих рисунках в целях упрощения (не требуется основании которых из подмножеств D1, k1 и Dj, k(j,r) полуперехода от Dj, k(j,r) к Dj, k (j,r) и от D1, k1 к D1, k1) и красочаются подмножества D1, k1 и Dj, k(j,r), устанавливаем спраты изображения в качестве подмножества Dj, k(j,r) представведливость соотношения (4.3.14):

ено подмножество D1, k(1,r).

k* На обоих рисунках по оси абсцисс (H) представлены d(D1,k1)u(U1,k1)> ii i=скалярные произведения (4.3.12) и (4.3.13) в виде последоваk 1,r ( ) тельно отложенных на этой оси входящих в них слагаемых. А, d(Dj,k( j,r))u(U* j,k( j,r)) ii по оси ординат (G) таким же образом представлены скалярi=ные произведения, стоящие, соответственно, в левой и правой и, следовательно, теорема доказана.

части неравенства (4.3.14). Соответственно, G1 и G2, H1 и H2 - Мы доказали тот факт, что подмножество D1, k1 D и текущие значения этих произведений.

соответствующий ему вектор U*1, k1 Uk1 Un обеспечивают максимум функции (4.3.9) при условиях (4.3.10) и (4.3.11), 164 kG1 = k 1,r ( ) Получим теперь решение рассматриваемой задачи в исdu G2 = i i G i=ходной постановке (4.3.1) - (4.3.2). В силу (4.3.3) имеем du i i i==F(D1, k1;U*1, k1) 1,n ui(U*1, k1) = u(i)** = Piui**, i = i =.

Откуда =F(D1, k(1, r);U*1, k(1, r)) 1, n (4.3.33) ui** = u(i)**/Pi, i =.

+ =FНайденные таким образом величины ui** с учетом пе+dl ul рестановок, указанных перед формулировкой теоремы 4.3.3, +dl-1 ul-будут являться решением задачи (4.3.1) - (4.3.2).

+ Отметим, что имеет место +d2 u(4.3.34) uk1** = (k1)sk1, d1uгде величина (k1) задается соотношением (4.3.7), и H tg =B1 B j=k1+1, n (4.3.35) uj** = 0,, H1=(D1, k1;U*1, k1): (1-d1) u1+(1-d2) u2Е(1-dl-1) ul-1+(1-dl) ul = B1 +(1-dl+1) ul+1+Е+(1-dk1) uk1 = B а величины di упорядочены перестановками (отсортированы) так, что имеет место H2=(D1, k(1, r);U*1, k(1, r)): (1-d1) u1+(1-d2) u2Е(1-dl-1) ul-1+(1-dl) ul = B1 +(1-dl+1) ul+1+Е+(1-dk (1, r)) uk (1, r) = B (4.3.36) d1 > d2 > Е>dn.

Как уже указывалось выше, решение задачи (4.3.1) - Рис. 4.3.1. К доказательству теоремы 4.3.(4.3.2) для случая является более громоздким по сравнению со случаем (4.3.36) и здесь не представлено.

Содержательная интерпретация решения (4.3.33) - G (4.3.36) состоит в том, что при ограниченном в момент t0 веtg = d F(D1,k1;U*1,k1) личиной B финансовом ресурсе следует осуществлять закуп ки ui для периода [t1,t2], руководствуясь следующими прави tg = d лами, с тем, чтобы прибыль от продажи закупленных товаров была максимальной:

F(D1,k(1,r);U*1,k(1,r)) 1. Необходимо упорядочить товары в соответствии с убыванием рентабельности di так, что будет иметь место соFkотношение (4.3.36).

G1 = d ui i k (1,r ) 2. Следует производить закупку (осуществлять формиi = G2 = d ui i рование заказа) товаров в порядке убывания рентабельности в i = H объемах ui = si, где si - дефицит товара i-го вида (недостаток товара i-го вида для покрытия спроса предстоящего пеB1 B риода [t1, t2]), до тех пор, пока для какого-то товара с номером k1 (номер получен товаром при упорядочивании согласно п. настоящих правил) не будет нарушено первое из условий, Рис. 4.3.2. К доказательству теоремы 4.3.входящих в (4.3.2), т.е. финансового ресурса уже не будет 166 хватать для закупки (включения в заказ) товара k1 в полном шим, а интервал времени между событиями - приходами пообъеме. следовательных заявок на обслуживание является случайной 3. Объем закупки товара с номером k1 определяется со- величиной, распределенной по показательному закону (см., отношением (4.3.34), т.е. товар k1 закупается на все финансо- например, [117, с. 266 - 269]) с плотностью распределения вые средства из B, которые остались после закупки товаров с p(t) = e- t, t 0, которое характеризует количество заявок на номерами от 1 до k1 - 1.

Pages:     | 1 |   ...   | 14 | 15 | 16 | 17 | 18 |   ...   | 34 |    Книги по разным темам