назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [ 75 ] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126]


75

5,>

относительно запасов j - l,n, r - I, N .

n n

5) Вычислить для всех номенклатур /• разности qr = Sr- E -ir

между запасом, необходимым для выравнивания штрафов под . и имеющимся в наличии.

6) Если между этими разностями нет положительных, перейти к этапу 8.

7) Выбрать номенклатуру гх , для которой qr максимально. Заменить го на vi . Перейти к этапу 3.

8) Рассчитать разности qj = Zjr - Sjr по всем складам и номенклатурам.

9) Сформировать значения избытков по всем j и г :

д+ f qjr, если qjy > 0; lo" иначе.

3) распределить ресурсы по остальным номенклатурам таким образом, чтобы штрафы по ним на всех складах не превышали штрафов по ключевой номенклатуре, а транспортные расходы были минимальны.

Наиболее вероятным кандидатом в «ключевые» следует считать ту номенклатуру, для которой максимальна взвешенная вероятность недоста-

ОС

чи ПО системе в целом, т.е. достигается niaxr/ Г г{х) dx , где d,.

есть среднее значение djr по всем j . Схема вычислительного процесса выглядит следующим образом:

1) Рассчитать суммарные запасы {zsr] по всем номенклатурам.

2) Вычислить взвешенные вероятности dj. f /v,.(.r)r/a и выбрать

номенклатуру 7о . Для которой это произведение максимально.

3) Для номенклатуры 7*о применением методики предыдущего раздела рассчитать по всем складам j нормативные запасы •

4) Решить уравнения

со (X)

djr I {X - Sjr)fjAx) dx = I (X - S*JfjroH dx (7.5.13)



10) Сформировать значения дефицитов по всем j и г :

д- f -qjr. если qjr < 0; \ О иначе.

И) Занести {А~,} и {А+,] в таблицу постановки транспортной задачи.

12) Приступить к выбору объемов перевозок {qijr} по минимуму транспортных затрат (в процессе минимизации затрат мы будем использовать обычно выполняемые на практике условия Cijr = Cij • Cr), ДЛЯ чего:

а) Выбрать minj j Cij .

б) Для данной пары складов вычислить qijr = min{Aj~.;A} и скорректировать остатки путем их уменьшения на qijr . Проделать эту операцию для всех г . Если на складе j все {Aj} оказались равными нулю, исключить склад j из числа получателей. Если на складе г все {А"} оказались нулевыми, вычеркнуть склад г из числа поставщиков.

в) Для той же пары складов вычислить объемы перевозок во встречном направлении qjir = minjAj"; А~} , скорректировать остатки и списки получателей и поставщиков.

г) Проверить, остался ли хоть один получатель (иначе говоря, есть ли положительный дефицит А",). Если остался, найти минимальный элемент в оставшейся части таблицы. Перейти к шагу б).

13) Конец алгоритма.

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

Совершенно аналогично решается и задача о распределении прибывшего в систему пополнения по нескольким номенклатурам: предварительно выявляется самая дефицитная номенклатура, и для нее решается система уравнений (7.5.10). Далее независимым решением уравнений (7.5.13) определяются необходимые запасы, подсчитывается



их сумма и сравнивается с располагаемым резервом. Окончательно выделив ключевую номенклатуру, вновь решаем систему уравнений (7.5.10) и назначаем объем поставок qjr по всем j,r до уравнивания штрафов. Излишняя в указанном смысле часть поставок направляется по наиболее дешевым маршрутам с учетом наличия свободного места на складах.

Задачи со способом расчета штрафов, отличным от максимального взвешенного дефицита, могут быть решены по аналогичной схеме.

Небольшая модификация предложенных алгоритмов позволяет получить приближенную методику решения задачи с учетом фиксированных составляющих {gij} по маршруту г j . Для этого необходимо всякий раз сопоставлять выигрыш от уменьшения штрафов с транспортными расходами. В частности, для однородного случая это уменьшение штрафа за вычетом расходов, пропорциональных объему перевозки, составит

оо оо

Ац = di / {x-S* -qij)fi{x)dx + dj f {x-S;+qij)fj{x)dx

OO oo

- di f{x-S:)fi{x)dx-dj J(x-S)fj{x)dx-Cijqij. s; s;

Разбив первые два интеграла на два слагаемых, можно показать, что

Aij= - diy"(x-S:)fi{x)dx + dj / ix-S*)fjix)dx

OO OO

+ Чгз dj f fj {x)dx- di f fi {x)dx ~ Cij

Для малых объемов перевозок {qij} содержимое квадратных скобок можно приравнять нулю. Применив теорему о среднем, имеем

Ао- YdjMSj - qijm - difiiS- + qij/2)]. (7.5.14)

Если Aij > gij , такая перевозка является оправданной. В противном случае она должна быть исключена. Проверив все возможные перевозки и запретив невыгодные, необходимо вновь вернуться к алгоритму разд. 7.5.1 и т.д. - до тех пор, пока не обнаружится, что все оставшиеся перевозки выгодны. Последний полученный план перевозок считается окончательным.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [ 75 ] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126]