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


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


69

4. В несбалансированной транспортной модели (табл. 5.28) стоимость хранения единицы груза, не отправленного из первого, второго и третьего пунктов отправления, составляет соответственно 5, 4 и 3 долл. Найдите оптимальное решение, если из второго пункта отправления груз должен быть вывезен полностью. Для получения начального решения используйте метод Фогеля.

Таблица 5.28

1 2 1 3 4 5

2 3 3 30 20 20

5. Пусть в транспортной модели размерностью 3x3 через хц обозначено количество грузов, перевозимых из пункта отправления i в пункт назначения

а через ctj - стоимость перевозки. Объемы грузов в первом, втором и третьем пунктах отправления равны соответственно 15, 30 и 85 единиц. Спрос в первом, втором и третьем пунктах назначения составляет 20, 30 и 80 единиц соответственно. Предположим, что начальное решение, полученное методом северо-западного угла, оптимально со следующими значениями потенциалов: их = -2, и2 = 3, и3 = 5, и, = 2, v2 = 5 и v3 = 10.

a) Найдите оптимальную стоимость транспортных расходов.

b) Определите наименьшие значения ctj для всех небазисных переменных, сохраняющих оптимальность решения, полученного методом северозападного угла.

6. В табл. 5.29 показано вырожденное базисное решение некой транспортной задачи. Пусть этому решению соответствуют следующие значения потенциалов: и, = 1, и2 = -1, и, = 2, Dj = 2hds= 5. Стоимости перевозок для всех нулевых (базисных и небазисных) переменных хц представим в виде

с,. = / + ;9, -с» < 0 < сю.

Таблица 5.29

10 20 20

20 40 30

a) Найдите значение целевой функции, если данное решение оптимально.

b) Укажите значения параметра 0, гарантирующие оптимальность данного решения. (Совет. Определите местоположение нулевых базисных переменных.)

7. Дана следующая задача.

т п

Минимизировать z = c,y*,y ;=i }-\

при выполнении ограничений



>„>г>,, у = 1,2,..., и,

хц > 0, для всех i и у.

Логично предположить, что оптимальное решение обращает первое или второе множество неравенств в равенства (в зависимости от того, будет ли выполняться неравенство я,>6уили 2e, <fy). Контрпример, опровергающий это предположение, представлен в табл. 5.30.

Таблица 5.30

1 1 2 6 5 1

2 7 1

Покажите, что данное предположение приводит к "оптимальному" решению хи = 2, х12 = 3, х22 = 4, лг23 = 2, дающему 2 = 27 долл., которое хуже решения хи = 2, х12 = 7, лг23 = 6 с г = 15 долл.

5.3.4. Интерпретация метода потенциалов как симплекс-метода

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

Максимизировать z = а,и, + bJvj

при ограничениях

и. + у < cti для всех i и ui и v. - свободные переменные,

"а - предложение (объем грузов) пункта отправления i, Ь - спрос (заявка на грузы) пункта назначения

с - стоимость перевозки единицы груза из пункта отправления i в пункт назначения

ut - двойственная переменная, соответствующая ограничению на предложение пункта отправления i,

vj - двойственная переменная, соответствующая ограничению на спрос пункта назначения /.

Из формулы 2 раздела 4.2.4 следует, что коэффициент при переменной х в выражении целевой функции должен быть равен разности между левой и правой частями соответствующего ограничения двойственной задачи, т.е. величине ut + v - су. Но как мы уже знаем, эта величина должна быть равной нулю для каждой базисной переменной. Другими словами, для этих переменных должно выполняться равенство ut + v = ctj. Имея т + п - 1 таких равенств и ре-



шая их как систему линейных уравнений (после присвоения какой-либо переменной произвольного значения, например и, = 0), находим значения потенциалов и, и i>y. Вычислив значения потенциалов, далее определяем вводимую в базис переменную среди всех небазисных как переменную, имеющую наибольшее положительное значение величины и, + и - с1}.

Присвоение одной из двойственных переменных произвольного значения (например, и, = 0) противоречит представлениям раздела 4.2.3, поскольку это присвоение показывает, что, возможно, решение двойственной задачи (определяется вычисленными значениями двойственных переменных (потенциа-лов)) не единственное. В действительности противоречия здесь нет, и решение упражнения 5.3.3.2 объясняет, - почему.

УПРАЖНЕНИЯ 5.3.3

1. Запишите двойственную задачу для транспортной модели из примера 5.3.5 (см. табл. 5.21). Вычислите оптимальное значение целевой функции двойственной задачи с помощью значений двойственных переменных, приведенных в табл. 5.25, и покажите, что найденное значение совпадает с оптимальным значением целевой функции транспортной задачи.

2. В транспортной модели одной из двойственных переменных присваивается произвольное значение. Это означает, что одному и тому же базисному решению прямой задачи соответствует не единственный набор значений двойственных переменных. Это противоречит положениям теории линейного программирования, где значения двойственных переменных вычисляются как произведение вектора коэффициентов целевой функции, стоящих при базисных переменных, на обратную матрицу соответствующего базиса (см. метод 1 из раздела 4.2.3). Покажите, что в транспортной модели обратная матрица всегда определяется однозначно, в то время как вектор коэффициентов целевой функции, стоящих при базисных переменных, можно определить не единственным образом. В частности, покажите, что если коэффициенты ctj заменить на сц + к для всех i и у, где к - произвольная константа, то оптимальные значения переменных хц не изменятся. Покажите, что присвоение одной двойственной переменной произвольного значения эквивалентно прибавлению к коэффициентам ctj некой константы к.

5.4. ЗАДАЧА О НАЗНАЧЕНИЯХ

"Лучший работник для выполнения данной работы" - вот подходящее краткое описание задачи о назначениях. В этой задаче необходимо назначить работников на определенные работы; каждый работник может выполнять любую работу, хотя и с различной степенью мастерства. Если на некоторую работу назначается работник именно той квалификации, которая необходима для ее выполнения, тогда стоимость выполнения работы будет ниже, чем при назначении на данную работу работника неподходящей квалификации. Цель задачи - найти оптимальное (минимальной стоимости) распределение работников по всем заявленным работам.

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