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


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


68

F

J К

Общая сетевая модель

2 Входные данные:

3 К-во п. отправления

«маюимум 10

К-во п. назначения

«максимум 10

Пр.способностьи пи"

изыемиетенз

V, \«*"М8ется пр способность

Матрица удельных стоимостей

1!.

Предложение

S1

ипрос

Оптимальное решение:

Промежуточные вычисления:

Общая стоимость

Узел

Поток

Спрос

Уд. стоимость

От-в

Поток

Пр спос.

. 1S

S1-D1

99959»

1 25

SI - D2

999999

S1 - D3

999999

7 11

S1 -D4

999999

4 ,2

S2-D1

999999

S2-D2

999999

S2-D3

999999

S2-D4

999999

S3-D1

999999

S3-D2

999999

S3-D3

999999

S3-D4

999999

34 •

Поиск решения

Установить целевую «чайку: Равной; 11мсииальнаму значению С

Р ницимапьному значению Изменяя ячейки:-

$В$22:$В$ЗЭ

Ограничения:-

JB$22:$B$33 <=$C$22:$C$33 F$21:$F$27 = $G$21:$G$27

Рис. 5.6. Решение примера 5.3.1, полученное с использованием сетей

Можно также наложить ограничения на пропускные способности на различных маршрутах транспортной модели. Сначала введите латинскую букву "у" (без кавычек) в ячейку В5. В результате будут созданы и соответствующим образом озаглавлены ячейки в диапазоне N8:W17, в которые можно ввести ограничения пропускной способности маршрута. Если пропускная способность маршрута не ограничена, то соответствующая ячейка должна остаться пустой. После этого ограничения пропускной способности с помощью функции ИНДЕКС будут автоматически скопированы в столбец С (начиная с ячейки С22). Число 999 999 представляет неограниченную пропускную способность.



Теперь для решения задачи осталось только задать параметры средства Поиск решения. Целевая ячейка уже содержит следующую общую формулу, которую не нужно изменять для моделей, размер которых не превышает 10 х 10.

=CyMMnPOH3B(B22:B122;J21:J121)

Осталось заполнить поля Изменяя ячейки и Ограничения в диалоговом окне средства Поиск решения. На рис. 5.6 показано, что в поле Изменяя ячейки содержится ссылка $В$22:$В$33.

В строках 22:33 содержатся все возможные маршруты модели, которые изменяются в соответствии с размерами транспортной задачи.

Ограничения можно сформулировать следующим образом.

Поток на маршруте (/, ;) < пропускной способности на маршруте (/, j), (входной поток - выходной поток) через узел = спрос в узле

Для первого множества ограничений левая часть выражения соответствует значениям в столбце В (начиная с ячейки В22), а правая часть - значениям в столбце С (начиная с ячейки С22). Например, на рис. 5.6 первой группе ограничений соответствует такое выражение.

$В$22:$В$33 <= $С$22:$С$33

Значения для второго множества ограничений содержатся в столбцах F и G, а выражение выглядит следующим образом.

$F$21:$F27 = $G$21:$G$27

Условия неотрицательными можно задать в диалоговом окне Параметры поиска решения, которое появляется после щелчка на кнопке Параметры в окне средства Поиск решения6.

Решение транспортной задачи в программе LINGO. На рис. 5.7 представлена модель LINGO для транспортной задачи примера 5.3.1 (файл ch5LingoTrans.lg4). Используемые в модели имена не нуждаются в пояснениях. Обратите внимание на то, что имена пунктов отправлений (SI, S2, S3) и пунктов назначений (Dl, D2, D3, D4) можно ввести так, как показано на рисунке, вместо того, чтобы включать их в раздел DATA (Данные) модели.

УПРАЖНЕНИЯ 5.3.2

1. В табл. 5.26 приведены исходные данные (в долл.) для трех транспортных задач.

a) Используя начальное решение, полученное методом северо-западного угла, найдите их оптимальное решение.

b) В программе TORA сравните начальные решения, полученные методами северо-западного угла, наименьшей стоимости и Фогеля.

c) Решите задачи с помощью средства Excel Поиск решения.

d) Решите задачи с помощью программы LINGO.

Следует быть внимательным, поскольку стандартная версия средства Поиск решения, входящая в поставку Excel, обладает некоторыми "особенностями". Если в диалоговом окне Параметры поиска решения установить слишком маленькое значение в поле Относительная погрешность (например, 0,000000001), будет выдано непонятное сообщение о том, что модель не удовлетворяет условиям линейности. Кроме того, выходные результаты будет легче читать, если их округлить (например, число 1Е-14 должно отображаться как 0, а 9,999999999 - как 10).



MODEL:

TITLE: Transportation model, Example 5.3-1; SETS:

from/SI S2 S3/:supply; to/Dl D2 D3 D4/:demand; route (from, to) :cost, ship; ENDSETS

MIN=0SUM(route (I, J) .-cost (I, J) *ship(l,J)) ; !subject to; 0FOR (

to(J):0SUM(from(I):ship(I,J))=demand(J) ) ;

@FOR (

from (I) :@SUM(to (J) : ship (I, J) )=supply(I) ) ;

DATA:

supply=15 25 10; demand=5 15 15 15; cost=10 2 20 11 12 7 9 20 4 14 16 18; ENDDATA END

Рис. 5.7. Решение транспортной задачи в программе LINGO

Таблица 5.26

2. В транспортной модели (табл. 5.27) суммарный спрос превышает общий объем предложений. Пусть штрафы за необеспеченный единичный спрос составляют 5 долл. для первого пункта назначения, 3 - для второго и 2 - для третьего.

a) Используя начальное решение, полученное методом наименьшей стоимости, найдите оптимальное решение.

b) Решите задачу с помощью средства Excel Поиск решения.

c) Решите задачу с помощью программы LINGO.

Таблица 5.27

5 1 7

6 4 6 3 2 5 75 20 50

3. Пусть в транспортной модели из предыдущего упражнения штрафы не назначаются, но спрос третьего пункта назначения должен быть выполнен полностью. Найдите оптимальное решение в программах a) TORA, b) Excel, с) LINGO.

10 80 15

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