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


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


56

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

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

Пример. Решить следующую задачу ЦЛП

-5Xi - 22 -> min 1Ц+4х2<33 -х, + 2x2 < 8

Xi,X2 €{0,1,2,....}.

Решение.

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

X* = (х*,Х2) = (1-,4-). Если рассматривать все возможные округления 13 26

компонент оптимальной точки, то получим четыре возможных целочисленных точки (1,4), (2,4), (1,5), (2,5). Во-первых, из этих точек только точка (1,4) является допустимой для исходной задачи. А во-вторых, она



находится далеко от истинного оптимального решения исходной задачи

/=(х;,х;)=(з,о).

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

Эффект округления не слишком заметен, лишь когда искомые параметры задачи подчинены относительно нежестким ограничениям. Однако типичными для задач целочисленного программирования являются ограничения-равенства, достаточно жестко определяющие поведение релевантных переменных. Примером может служить условие Xl + 2 +... + х„ = 1, где X. = (0,1) для всех /. В такой ситуации процедура

округления не имеет смысла и необходимо обратиться к другим алгоритмам решения.

Несостоятельность округления подчеркивается также следующими соображениями. Несмотря на то что целочисленные переменные обычно выражают количество неделимых предметов (например, машин, людей, кораблей), возможны и другие типы спецификации этих переменных. Так, решение о финансировании некоторого проекта представляется булевой переменной х (х = О, если проект отклоняется, и х = 1, если проект принимается). В этом случае бессмысленно оперировать дробными значениями величины X, и процедура округления является логически неприемлемой.

Так как практическая ценность задач с целочисленными переменными не вызывает сомнений, целочисленное программирование занимает важное место среди методов исследования операций.

6.1. Примеры задач целочисленного программирования

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



6.1.1. Задача с постоянными элементами затрат. В одной из типичных задач планирования производства рассматривается N видов промышленной продукции. Затраты на производство продукции вида] складываются из постоянных затрат в объеме Kj, не зависящем от

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

Таким образом, если Xj - объем выпуска продукции вида j, функцию суммарных затрат можно записать следующим образом:

Kj+CjXj, Xj>0, О,х=0.

Естественным выглядит стремление минимизировать величину суммарных затрат

z = JCj(Xj)mm.

Рассматриваемый критерий не является линейным по переменной Xj

вследствие разрыва в начале координат. Поэтому задача с целевой функцией Z оказывается непригодной для дальнейшего исследования классическими методами.

Введение дополнительных булевых переменных позволяет преобразовать задачу к виду, «более приемлемому» с аналитических позиций. Пусть

0,Xj - О,

1,Xj > О,

что можно переписать в форме (линейного) неравенства: xj < Myj.

Здесь М> О достаточно велико, чтобы условие Xj <М выполнялось

для всех допустимых объемов выпуска продукции. Теперь исходную задачу можно сформулировать следующим образом:

z = Ya{CjXj-¥Kjyj)-mm,

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