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


[Старт] [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] [294] [295] [296] [297] [298] [299] [300] [301] [302] [303]


86

OPTIMAL:

VARIABLE

QUANTITY

OPTIMAL Z = 740

VARIABLE

REDUCED COST

DUAL PRICE

-13.33

Тем не менее, все числа те же, что появляются в строке C-Z конечной таблицы.

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

2xi + Х2<22 3x] + 3x2<39 Xi,X2>0

Ввод задачи в компьютер выглядит примерно так:

60X1+ 50X2

4X1 + 10X2 < = 100 2X1 + Х2 < = 22 3X1 + 3X2 < = 39

Обратите внимание на ключевые различия между данным вводом и нашей основной моделью:

1. Два нажатия клавиши используются для ограничения < (Некоторые программы обрабатывают < как эквивалент < и требуют только одного нажатия клавиши.)

2. Ограничения неотрицательности необязательны - они автоматически приняты компьютерным кодом (программой).

3. Резерв и избыточные переменные не используются; они используются компьютером автоматически по мере необходимости.

4. Хотя данная модель не содержит коэффициентов в виде дробных выражений (например, 1/4x1, 1/2x2), дроби вообще не допускаются. Все коэффициенты должны быть целыми числами или десятичными дробями (например, 5х], 2,5x2).

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

Таблица 5п-9 содержит пример того, что выводит компьютер при решении предшествующей LP модели. Вывод показывает оптимальные значения переменных и оптимальное значение целевой функции. Термины редуцированная стоимость и двойная цена будут объяснены ниже в данном разделе.

Таблица 5п-9. Пример компьютерной распечатки

AFTER 2 ITERATIONS THIS SOLUTION IS



Таблица 5п-10. Второй пример компьютерной распечатки

VARIABLE XI Х2

LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 740.000

VALUE 9.00000 4.00000

REDUCED COST 0.00000 0.00000

ROW 2) 3) 4)

SLACK OR SURPLUS 24.00000 0.00000 0.00000

DUAL PRICES 0.00000 10.00000 13.33334

Компьютерные пакеты обычно имеют возможность вывода таблиц отдельного вида в дополнение к обеспечению оптимального решения. Например, в LINDO распечатка таблиц выглядела бы следующим образом:

SUBJECT ТО

60 XI +50 Х2

+ 10x2 <= 100

+ x2 <= 22

+ 3x2 <= 3 9

THE TABLEAU

ROW (BASIS),

SLK 2

SLK 3

1 ART

-60.000

-50.000

0.000

0.000

0.000

2 SLK

4.000

10.000

1.000

0.000

100.000

3 SLK

2.000

1.000

0.000

1.000

22.000

4 SLK

3.000

3.000

0.000

0.000

39.000

XI ENTERS

VALUE

11.000

IN ROW

3 OBJ.

VALUE

660.00

THE TABLEAU

ROW (BASIS)

SLK 2

SLK 3

1 ART

0.000

-20.000

0.000

30.000

660.000

2 SLK

0.000

8.000

1. ООО

-2.000

,000

56.000

1.000

0.500

0.000

0.500

11.000

4 SLK

0.000

1.500

0.000

-1.500

6.000

X2 ENTERS

VALUE

4 .000

IN ROW

4 OBJ.

VALUE

740.00

THE TABLEAU

ROW (BASIS)

SLK 2

SLK 3

1 ART

0.000

0.000

0.000

10.000

,333

740.000

2 SLK

0.000

0.000

1.000

6.000

.333

24.000

1. ООО

0.000

0.000

1.000

,333

9. ООО

0.000

1.000

0.000

-1.000

.667

4.000

LP OPTIMUM FOUND AT STEP

OBJECTIVE FUNCTION VALUE 1) 740.000000



VARIABLE VALUE REDUCED COST

XI 9.000000 0.000000

X2 4.000000 0.000000

pOW SLACK OR SURPLUS DUALPRICES

2) 24.000000 0.000000

3) 0.000000 10.000000

4) 0.000000 13.333333

NO. INTERATIONS = 2

Вывод является в принципе самодостаточным, и требует мало комментариев. Верхняя строка каждой таблицы имеет обозначение ART. Это сокращение от artificial (искусственный), и значения в строке - это те, что появляются в строке C-Z таблицы, только отрицательные. Например, в последней таблице 10.000 и 13.333 появляются в верхней строке, а в таблице 5п-9 они появляются как отрицательные. Следовательно, верхняя строка - это скорее Z-C, чем C-Z. Строка Z не появляется вообще. Обозначение SLK относится к переменной резерва (англ. slack). Однако LINDO начинает нумерацию с верхней строки, так что S] помечен SLK 2, Sj как SLK 3, и так далее. Интервал по верхним меткам позволяет номеру каждой переменной резерва появиться непосредственно над соответствующим столбцом, а само обозначение немного смещено влево. Таким образом, третий столбец - это SLK 2.

Компьютеры обрабатывают задачи линейного программирования с такой легкостью, быстротой и точностью, что вы можете удивиться, зачем вообще нужно учиться выполнять решения вручную. Тем не менее, для изучения ручного метода имеется несколько убедительных причин. Важно понимать, как именно вырабатываются решения. Без такого понимания компьютер становится волшебным черным ящиком, из которого таинственно появляется решение. Люди, которые используют компьютеры таким образом, редко достигают таких же результатов, как те, кто обладает базовым пониманием основного процесса, - как в формулировке задач, так и в понимании результатов. Решение нескольких проблем управления вручную даст такую глубину понимания, которую невозможно получить никаким другим способом. Кроме того, важна также и возможность отточить математические навыки; мир информации становится все более и более числовым. Утех, кто может уверенно ориентироваться в этом мире, меньше причин бояться компьютеров или числовой информации. Другая причина, по которой важно знать ручной способ решения, состоит в том, что другие методы решения задач линейного программирования очень похожи на симплексные методы. Следовательно, изучение и понимание этих методов становится проще после знакомства с симплексной процедурой.

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

Хотя разные пакеты программ отличаются в том, как они представляют результаты, эти различия, как правило, незначительны; все пакеты представляют аналогичную общую информацию.

Имея это в виду, давайте рассмотрим протокол вывода компьютера. Таблица 5п-11 повторяет конечную таблицу предшествующего ЛП решения для ссылки, а таблица 5п-12 иллюстрирует компьютерную распечатку анализа чувствительности проблемы на микро ЭВМ.

[Старт] [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] [294] [295] [296] [297] [298] [299] [300] [301] [302] [303]