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


[Старт] [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]


64

10 5.....

-1.0

: 7

5.....

-15.....>

: 18

Спрос 5 15 15 15

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

Пример 5.3.3

Применим метод наименьшей стоимости к задаче из примера 5.3.1.

1. Ячейка (1,2) имеет наименьшую в таблице стоимость (2 долл.). Наибольшее значение, которое можно присвоить переменной хи, равно 15. В этом случае удовлетворяются ограничения, соответствующие первой строке и второму столбцу. Вычеркиваем второй столбец, предложение первой строки и спрос второго столбца принимают нулевые значения.

2. Следующей ячейкой с наименьшей стоимостью в незачеркнутой части таблицы будет (3, 1). Присвоим переменной x3i значение 5 и вычеркнем первый столбец. Ограничение по предложению, соответствующее третьей строке, станет равным 10 - 5 = 5.

3. Продолжая процедуру, последовательно присваиваем переменной x2i значение 15, переменной хи - значение 0; далее находим х34 = 5 их,4 = 10 (проверьте!).

Процесс поиска начального решения представлен в табл. 5.18. Стрелками показана последовательность присвоения переменным значений. Итак, мы получили следующее начальное базисное решение (состоящее из 6 переменных):

Этот метод в русской математической литературе часто называют методом минимального элемента. - Прим. ред.

Таблица 5.17

1 2 3 4 Предложение



.г12= 15,х14 = 0, .г23=15,х24 = 10, Аз1 = •>> *34 = 5.

Соответствующее значение целевой функции равно

z=15x2 + 0xll + 15x9 + 10x 20 + 5x4 + 5x 18 = 475 долл. Отсюда следует, что полученное методом наименьшей стоимости начальное решение лучше, чем начальное решение, представленное методом северо-западного угла (сравните данное значение целевой функции с аналогичным значением из примера 5.3.2).

Таблица 5.18

1 2 3 4 Предложение

, о.

/9 г 15

10 4

.--14

Спрос 5 15 15 15

Метод Фогеля. Данный метод является вариацией метода наименьшей стоимости и в общем случае находит лучшее начальное решение. Алгоритм этого метода состоит из следующих шагов.

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

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



ШагЗ.

а) Если не вычеркнута только одна строка или только один столбец с нулевым спросом или предложением, вычисления заканчиваются.

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

в) Если всем невычеркнутым строкам и столбцам соответствуют нулевые объемы предложения и спроса, методом наименьшей стоимости находятся нулевые базисные переменные, и вычисления заканчиваются.

г) Во всех остальных случаях необходимо перейти к п. 1.

Пример 5.3.4

Применим метод Фогеля к задаче из примера 5.3.1. В табл. 5.19 показан первый набор вычисленных штрафов.

Поскольку третья строка имеет наибольший штраф (10) и в этой строке наименьшая стоимость содержится в ячейке (3, 1), присваиваем переменной х31 значение 5. В этом случае полностью выполняется ограничение первого столбца, его вычеркиваем. Новый набор пересчитанных штрафов показан в табл. 5.20.

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

Таблица 5.19

Штрафы для строк

10-2 = 8

9-7 = 2

14-4 = 10

Штрафы для столбцов

10-4

7-2 = 5

16-9

18-11

[Старт] [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]