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


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


65

Таблица 5.20

1 2 3 4 Штрафы для строк

11-2 = 9

9-7 = 2

16-14 = 2

0 15 15 15

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

Продолжая этот процесс, находим, что на следующем шаге вторая строка будет иметь наибольший штраф (20 -9 = 11). Поэтому переменной х23 присваиваем значение 15. В результате будет вычеркнут третий столбец, во второй строке останется нереализованным предложение объемом в 10 единиц. Остается невычеркнутым только четвертый столбец с положительным неудовлетворенным спросом объемом в 15 единиц. Применяя метод наименьшей стоимости к этому столбцу, последовательно получаем л14 = 0, x3t = 5 и x2i = 10 (проверьте!). Соответствующее значение целевой функции равно

z = 15 х2 + 0х 11 + 15x9 + 10 х 20 + 5x4 + 5x 18 = 475 долл.

В данном случае значение целевой функции такое же, как и при методе наименьшей стоимости. Но обычно метод Фогеля дает наилучшее начальное решение для транспортной задачи.

УПРАЖНЕНИЕ 5.3.1

1. Найдите начальные решения методами северо-западного угла, наименьшей стоимости и Фогеля для следующих транспортных задач.

5.3.2. Итерационный алгоритм решения транспортной задачи

После определения начального решения (с помощью одного из трех методов, описанных в предыдущем разделе) применяется алгоритм, позволяющий найти оптимальное решение транспортной задачи.



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

Шаг 2. С помощью симплексного условия допустимости определяется исключаемая из базиса переменная. Происходит изменение базиса и возврат к первому этапу.

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

Пример 5.3.5

Решим транспортную задачу из примера 5.3.1, используя начальное решение (табл. 5.21), полученное методом северо-западного угла в примере 5.3.2.

Таблица 5.21

12 3 4 Предложение

Спрос 5 15 15 15

Определение вводимой переменной среди текущих небазисных (т.е. среди тех переменных, которые не входят в начальное базисное решение) основано на вычислении коэффициентов z-строки, соответствующих небазисным переменным, с использованием метода потенциалов (который, как будет показано в разделе 5.4, основан на соотношениях двойственности задачи ЛП).

В методе потенциалов каждой строке i и каждому столбцу j транспортной таблицы ставятся в соответствие числа (потенциалы) ut и vy. Для каждой базисной переменной х, потенциалы ut и vy (как показано в разделе 5.4) удовлетворяют уравнению

В рассматриваемой задаче имеем 7 неизвестных переменных (потенциалов) и 6 уравнений, соответствующих шести базисным переменным. Чтобы найти значения потенциалов из этой системы уравнений, нужно присвоить одному из них произвольное значение (обычно полагают и, = 0) и затем последовательно вычислять значения остальных потенциалов.



Базисные переменные

Уравнения относительно потенциалов

Решение

и: + vi = 10

Ui = 0 -> = 10

щ + v2 = 2

1/1 = 0 -> i/2 = 2

U2 + V2 = 7

l/2 = 2-t/2 = 5

1/2+1/3 = 9

1/2 = 5 -> 1/3 = 4

u2 + V4 = 20

1/2 = 5 -> 1/4 = 1 5

1/3+1/4 = 18

1/4 = 15 -> 1/3 = 3

Итак, имеем

Wj = 0, ы2 = 5, u3 - 3,

v, = 10, v2 = 2, v3 = 4, v4= 15.

Далее, используя найденные значения потенциалов, для каждой небазисной переменной вычисляются величины ul + vt - с,. Результаты вычисления этих величин приведены в следующей таблице.

Небазисные переменные

Значения и, + i/y - с,у

Х13 *14 *21 *31 *32 *33

Щ + 1/з - Ci3 = 0 + 4 - 20 = -16 Ul + 1/4 - С14 = 0 + 15- 11 = 4 и2 + 1/1 - с21 = 5 + 10- 12 = 3 из + 1/1 - с31 = 3 + 10 - 4 = 9 иъ + 1/2 - с32 = 3 + 2 - 14 = -9 и3 + 1/3 - Сзз = 3 + 4 - 16 = -9

Вычисленные значения совместно с нулевыми значениями для базисных переменных (поскольку ut + v - ctj = 0 для любой базисной переменной х ) фактически являются коэффициентами z-строки симплекс-таблицы.

Базис

Поскольку в транспортной задаче ведется поиск минимума стоимости перевозок, вводимой в базис будет переменная, имеющая наибольший положительный коэффициент в z-строке. В данном случае вводимой переменной будет лг31.

Описанные вычисления обычно выполняются непосредственно в транспортной таблице, как показано в табл. 5.22. В этом случае нет необходимости в явном виде выписывать уравнения для потенциалов. Вычисления в транспортной таблице начинаются с присвоения потенциалу их нулевого значения: их = 0. Затем вычисляются v-потенциалы для всех столбцов, имеющих базисные переменные в первой строке. Далее на основании уравнения для потенциалов, соответствующего переменной jc22, определяется величина потенциала и2. Зная значение потенциала и2, вычисляем потенциалы v3 и v4, что позволяет найти потенциал и3. Поскольку все потенциалы определены, далее вычисляются величины ut + vs - ctj для каждой небазисной переменной х . Эти величины показаны в табл. 5.22 в левом нижнем углу ячеек транспортной таблицы.

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