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


[Старт] [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] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [ 139 ] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293] [294] [295] [296] [297] [298] [299] [300] [301] [302] [303]


139

От: 1

Фиктивный

источник

поставок

Спрос

В Предложение

\170 170\

Следующая наименьшая стоимость ячейки - $6 в ячейке 1-В. В эту ячейку {на этот маршрут) надо распределить как можно больше единиц. Оставшийся спрос для столбца В - 15, и общее количество строки -- 75. Мы назначаем меньшую из этих величин, т. е. 15, ячейке 1 -В, таким образом исчерпывая столбец и уменьшая поставки в строке до 60. Затем мы перечеркиваем затраты ячеек столбца В.

Фиктивный

источник

поставок

Спрос

-1*:

\170 170\

Предложение

Если по-прежнему игнорировать фиктивную строку, то следующая самая низкая стоимость ячейки - $9 в ячейке 1-А, где поставка 60 и спрос 80 единиц. Мы назначаем меньшее из этих значений, т. е. 60 единиц ячейке 1-А, поэтому значения затрат в строке 1 должны быть вычеркнуты. Также, пересмотрев столбец А, получаем его общее количество, равное 20.

Фиктивный

источник

поставок

Спрос

\70 170\

Теперь остается только фиктивная строка. Фиктивная ячейка А имеет поставку и спрос, равные 20; распределение данного количества в ячейку исчерпывает как поставку, так и спрос, заканчивая начальное распределение.

чДо:

От: 1

Фиктивный

источник

поставок

Спрос

В Предложение

\170 170\



, Следующий шаг -проверка полученного решения на оптимальность. Сначала мы должны проверить полноценность: R + С - 1 = 3 (строки) + 2 (столбца) -1=4, необходимое количество заполненных ячеек. Поскольку в нашем решении имеются четыре заполненных ячейки, решение не является неполноценным. Для оценки может использоваться или метод «перехода по камням» или MODI. Предположим, что будем использовать MODI. Мы всегда начинаем с размещения ноля слева в строке 1. Это индекс строки 1. Мы можем использовать его, чтобы найти индекс столбца для любой заполненной ячейки в строке 1. Поскольку и ячейка 1 -А, и ячейка 1 -В являются заполненными, мы можем получать для обеих значение индекса столбца. Для заполненных ячеек, сумма индексов строки и столбца должна равняться значению ячейки. Для ячейки 1-А: О -ь индекс столбца = 9, следовательно индекс столбца А должен равняться 9. Аналогично, для ячейки 1-В, О -ь индекс столбца = 6, следовательно, индекс столбца должен равняться 6. Затем эти индексы используются, чтобы найти значения индекса строки для законченных ячеек в соответствующих им столбцах. Таким образом, для ячейки 2-В, 6 -ь индекс строки = 3, поэтому индекс строки должен равняться -3. Для фиктивной ячейки А, 9 -ь индекс строки = О, поэтому индекс строки должен быть -9.

От: О 1

-3 2

Фиктивный

источник

поставок

Спрос

А 9 В 6 Предложение

ll 75-

\170 170\

Затем мы используем эти индексы для оценки пустых ячеек. Оценка ячейки определяется, вычитая из значения ячейки суммы индексов строки и столбца. Таким образом, для ячейки 2-А мы имеем 5 - (-3 -ь 9) = -1, и для фиктивной ячейки В мы имеем О - (-9 -ь 6) = 3.

От: О 1

-3 2

фиктивный

источник

поставок

Спрос

А 9 В 6 Предложение

\170 170\

Появление отрицательной оценки ячейки говорит о том, что решение может быть улучшено. Когда появляются отрицательные значения, мы выбираем ячейку с наибольшим из них, и концентрируем на ней наши усилия, чтобы улучшить решение. Так как имеется только одна такая ячейка, мы ее и выбираем, г. Значение -1 в ячейке 2-А говорит нам, что каждая единица, которую мы распределим в эту ячейку, уменьшает общую стоимость решения на $1. Разумеется, желательно поместить в эту ячейку как можно больше единиц, но мы ограничены общими количествами строки и столбца (строка 2 и столбец А). Мы также ограничены необходимостью сохранить общие количества для всех строк и столбцов. Чтобы помещать единицы в ячейку 2-А, мы должны брать их из некоторой другой ячейки, которая будет находиться в другой строке или другом столбце. К счастью, эту проблему несложно решить: определите путь перехода для ячейки 2-А (методом «перехода по камешкам») и используйте его для руководства перераспределением. Этот путь проиллюстрирован в следующей таблице:



От: 1

Фиктивный

источник

поставок

Спрос

.До: А

В Предложение

(-)--

(+)-,-

\170 170\

Количество, которое может быть перемещено в ячейку 2-А, - это наименьщая величина, которая появляется в отрицательной позиции пути. Имеются две таких величины, 60 и 75. Поскольку 60 меньшая из них, она перемещается по всему пути (т.е. прибавляется там, где имеется знак + и вычитается там, где имеется знак -). Результат - наше пересмотренное решение:

ЧДоА От:-

Фиктивный

источник

поставок

Спрос

В Предложение

\170 170\

. Это улучшенное решение может быть оптимальным, или может требовать дальнейшего изменения. Чтобы выяснить это, мы должны его оценить. Сначала мы проверяем его полноценность: R + C-1=3-l-2-l=4. У нас имеются 4 заполненные ячейки, значит, решение полноценно.

Затем мы разрабатываем индексы MODI, используя заполненные ячейки. Мы всегда начинаем, назначая индекс О первой строке. Тогда для любой заполненной ячейки в первой строке номер индекса столбца-такой же, как стоимость ячейки. Поскольку ячейка 1 -В имеет стоимость ячейки 6, то индекс столбца В также равен 6. Используя это значение и стоимость заполненной ячейки 2-В, получаем индекс для строки 2: стоимость ячейки - индекс столбца = индекс строки. Таким образом, 3 - 6 = -3. Индекс этой строки 2 можно использовать вместе со стоимостью законченной ячейки 2-А, чтобы найти ицдекс столбца А, 5 - (-3) = 8, а индекс 8 можно использовать со стоимостью фиктивной ячейки А, для получения индекса фиктивной строки: 0-8 =-8 Эти индексы показаны в следующей таблице:

-3 2 -8

Фиктивный

источник

поставок

Спрос

4/*°- А 8 В 6 Предложение

\170 170\

Теперь можно определить оценки для пустых ячеек. Ячейка 1-А: 9 - (О-I-8) = 1

Ячейка фиктивная В: О - (-8 + 6) = 2

Поскольку отрицательные оценки отсутствуют, полученное решение оптимально: Отправьте 75 единиц от 1 к В, 60 единиц от 2 к А, и 15 единиц от 2 к В. 20 единиц

[Старт] [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] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [ 139 ] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293] [294] [295] [296] [297] [298] [299] [300] [301] [302] [303]