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


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


66

5.3. Решение транспортной задачи Таблица 5.22

V! = 10

1/2 = 2

1/з = 4

i/4 = 15 Предложение

1/1 = 0

и2 = 5

из = 3 Спрос

Определив вводимую в базис переменную х31, далее следует найти исключаемую из базиса переменную. Напомним, если какая-либо переменная вводится в базис, одна из текущих базисных переменных должна стать небазисной (и равной нулю), чтобы количество базисных переменных оставалось постоянным (в данном примере количество базисных переменных равняется 3 + 4-1 = 6).

Исключаемая из базиса переменная определяется следующим образом. Выбрав в качестве вводимой переменную х31, мы хотим, чтобы перевозки по маршруту, соответствующему этой переменной, уменьшили общую стоимость перевозок. Какой объем груза можно перевезти по этому маршруту? Обозначим через 0 количество груза, перевозимого по маршруту (3, 1) (т.е. х31 = 0). Максимально возможное значение 9 определяем из следующих условий.

1. Должны выполняться ограничения на спрос и предложение.

2. Ни по какому маршруту не должны выполняться перевозки с отрицательным объемом грузов.

Эти условия позволяют найти значение 0 и определить исключаемую переменную. Сначала построим замкнутый цикл, который начинается и заканчивается в ячейке, соответствующей вводимой переменной (в данном примере - это ячейка (3, 1)). Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным переменным, и ячейку, соответствующую вводимой переменной. В табл. 5.23 показан цикл для вводимой переменной х31. Для любой вводимой переменной можно построить только один замкнутый цикл.

Теперь найдем значение 0. Для того чтобы удовлетворить ограничениям по спросу и предложению, надо поочередно отнимать и прибавлять 0 к значениям базисных переменных, расположенных в угловых ячейках цикла, как показано в табл. 5.23 (не имеет значения направление обхода цикла: по часовой стрелке или против). Новые значения базисных переменных останутся неотрицательными, если будут выполняться следующие неравенства.

хп = 5-0>0, х22 = 5-0>0, х, = 10-0>0.



Таблица 5.23

Vj = 10 v2 = 2 v3 = 4 v4 = 15 Предложение

Спрос

-е-«

-10 + в + *

11 4

-.9 ---15-"

20 -5 + в

+ 7

t 4

►10

Отсюда следует, что наибольшее значение, которое может принять 0, равно 5, при этом переменные лп и х.п обращаются в нуль. Поскольку только одна переменная исключается из базиса, в качестве исключаемой можно выбрать как хи, так и х22. Остановим свой выбор нал-,,.

Определив значение для вводимой переменной (х31 = 5) и выбрав исключаемую переменную, далее следует откорректировать значения базисных переменных, соответствующих угловым ячейкам замкнутого цикла, как показано в табл. 5.24. Поскольку перевозка единицы груза по маршруту (3, 1) уменьшает общую стоимость перевозок на 9 долл. (= м3 + v, - с31), суммарная стоимость перевозок будет на 9x5 = 45 долл. меньше, чем в предыдущем решении. Таким образом, новая суммарная стоимость перевозок будет равна 520 - 45 = 475 долл.

Имея новое базисное решение, следует повторить вычисления потенциалов, как показано в табл. 5.24. Новой вводимой в базис переменной будет хи. Замкнутый цикл, соответствующий этой переменной, позволяет найти ее значение (л,4 = 10) и исключаемую переменную л24.

Новое решение, показанное в табл. 5.25, на 4 х 10 = 40 долл. уменьшает значение целевой функции. Таким образом, новая суммарная стоимость перевозок составляет 475 - 40 = 435 долл. Теперь новые значения величин и, + vf - сц для всех небазисных переменных х. отрицательные. Поэтому решение, представленное в табл. 5.25, оптимально.

Таблица 5.24

v, = 1 v2 = 2 v3 = 4 v4=15 Предложение

и, = 0

щ = 5

А

+ : 4

: 7 0 + 6-

.. 9 -15-

Т 20

-10-е

СпР0С 5 15 15 15



Спрос 5 15 15 15

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

От элеватора До мельницы Количество зерновозов

Суммарная стоимость перевозок =

435 долл.

5.3.3. Решение транспортной задачи с помощью TORA

Ранее было показано, как решить транспортную задачу в программе TORA в автоматическом режиме. В этом разделе будет описано, как решать эту задачу в обучающем режиме (режиме пошагового выполнения). Также будет показано, как можно решить эту задачу, используя средство Excel Поиск решения и программу LINGO.

Обучающий режим программы TORA. Из меню Solve/Modify выберите команду Solved Iterations. Чтобы приступить к решению транспортной задачи, из появившегося подменю выберите один из трех методов решения (северо-западного угла, наименьшей стоимости или Фогеля). В этом режиме можно использовать два полезных интерактивных средства.

1. Любые значения потенциалов и и v можно приравнять к нулю перед вычислением второй итерации (по умолчанию и, = 0). Если вы приравняли к нулю какой-либо потенциал, отличный от uv то заметите, что, несмотря на то, что значения ut и v] изменились, значения в небазисных ячейках (= ut + vj - ctj) остались неизменными. Это означает, что изначально любые и или v могут приравниваться к нулю (в действительности могут принимать любое значение), что не влияет на применение условия оптимальности.

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

Таблица 5.25

vi = -3 V2 - 2 1/з = 4 i/4 = 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]