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


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


101

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

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

Со временем эти спекулятивные сделки вышли из-под контроля, что привело всех брокеров к банкротству. К тому же, финансовое положение брокерской фирмы было таково, что все деньги брокеров были вложены во внешних клиентов и сделки между самими брокерами, причем таким образом, что практически каждый брокер стал должником другого.

Брокеры, чьи активы позволяли погасить долги, были объявлены платежеспособными. Остальные через судебные инстанции должны были погасить свои долги в интересах сторонних клиентов. Поскольку активы и авуары несостоятельных брокеров меньше общего объема долгов, долги погашаются пропорционально их объемам.

Из-за финансовых затруднений неплатежеспособной группы брокеров судебные инстанции постановили, что заключенные ранее сделки должны выполняться только для удовлетворения определенных судом требований, поскольку брокеры не имеют собственных источников капитала. В частности, судебные инстанции требуют свести количество погашаемых сделок между брокерами к минимуму. Это означает, что если брокер А должен брокеру В сумму X, а брокер В - брокеру А сумму Y, то эти взаимные долги сведутся к одному с суммой долга Х - Y. Эта сумма считается долгом А перед В, если X > Y, и долгом В перед А, когда X < Y. Если X = У, долг погашен. Эта идея погашения взаимных долгов распространяется на все долги между брокерами.

Каковы ваши предложения по выходу из данной финансовой ситуации? В частности, ответьте на следующие вопросы.

1. Как рассчитать доли возвращаемых долгов?

2. К какому минимальному количеству можно свести взаимные долги между брокерами?

Задача основана на материалах статьи Taha Н. "Operations Research Analysis of a Stock Market Problem", Computers and Operations Research, Vol. 18, No. 7, pp.597-602, 1991.



ГЛАВА 7

ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

В этой главе используется аппарат матричной алгебры. Читатель, не знакомый с матричной алгеброй, может обратиться к приложению А.

В задачах линейного программирования пространство допустимых решений всегда имеет форму выпуклого множества. Множество называется выпуклым, если отрезок прямой, соединяющий две различные точки этого множества, полностью принадлежит данному множеству. Крайней точкой выпуклого множества является точка, принадлежащая этому множеству, но которая не лежит ни на каком отрезке прямой, соединяющей две различные точки этого множества. Фактически крайние точки - это то же самое, что и угловые точки, которые использовались в главах 2, 3 и 4.

На рис. 7.1 показаны два множества. Множество а, которое представляет типичное пространство решений задачи ЛП, является выпуклым множеством, тогда как множество б невыпуклое.

7.1. ОСНОВЫ СИМПЛЕКС-МЕТОДА

Рис. 7.1. Примеры выпуклого и невыпуклого множеств



В разделе 2.3 мы графически показали, что оптимальное (конечное) решение двухмерной задачи ЛП соответствует крайней (угловой) точке пространства допустимых решений. Этот результат основан на том факте, что в задачах ЛП любая допустимая точка представима как функция крайних точек пространства решений. Например, в выпуклом множестве на рис. 7.1, а имеется шесть крайних точек X,, Х2, Х6, произвольную допустимую точку X можно представить как линейную комбинацию крайних точек:

X - оцХ, + сс2Х2 + ОзХ3 + сс4Х4 + сс5Х5 + сс6Х6,

где все коэффициенты ос, > 0 и выполняется равенство

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

Пример 7.1.1

Покажем, что следующее множество является выпуклым.

С = {(х„ х,) х, < 2, х2< 3, х, > 0, х2 >0}. Пусть X, ={х,,л2} и X, = [х;,х;) - две различные точки из множества С. Если множество С выпукло, тогда точка X = (х,, хг) = otjX, + ос-Д., должна принадлежать этому множеству. Чтобы точка X принадлежала множеству С, ее координаты должны удовлетворять неравенствам, которые определяют это множество.

х, = a,xj + a, xj* < a, х 2 + a, х 2 = 2 .

x, = asx\ + a2x\ < a, x3 + a, x3 = 3 .

Таким образом (поскольку a, + a2 = 1), x, < 2 и x2 < 3. Так как коэффициенты a, и otj неотрицательны, то координаты также удовлетворяют условиям неотрицательности.

УПРАЖНЕНИЯ 7.1.1

1. Покажите, что множество Q = {xt, х21 х, + х2 < 1, х, > 0, х2 > 0} выпуклое. Существенно ли в данном случае условие неотрицательности переменных?

2. Покажите, что множество Q = {х,, х2 х> 1 или х2 > 2} не является выпуклым.

3. Найдите графически крайние точки выпуклого множества

Q = {х,, х21 х, + х2 < 2, х, > 0, х2 > 0}.

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

4. Представьте внутреннюю точку (3, 1) пространства решений, показанного на рис. 7.2, как выпуклую комбинацию крайних точек А, В, С и D, где каждая крайняя точка должна иметь строго положительный весовой коэффициент.

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