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


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


57

Рассмотрим подробнее ограничение Xj < Myj. При условии Xj > О имеем yj = \ и целевая функция включает постоянные затраты Kj. Если Xj = О, то yj может принимать значения О или 1, однако, поскольку Kj>0 hz требуется минимизировать, переменная yj должна быть равна нулю.

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

6Л,2. Задача планирования производственной линии. Рассмотрим задачу, связанную с выполнением п различных производственных операций на одном станке за минимально возможное время. В процессе производства последовательно выполняется ряд операций, порядок которых устанавливается технологическими требованиями. Каждое изделие необходимо изготовить к заданному сроку.

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

Рассмотрим первый тип ограничений. Обозначим через xj время начала операции j (отсчитываемое от некоторого исходного момента), а через Uj - величину промежутка времени, требуемого для выполнения этой

операции. Если операция / должна предшествовать операции у, то соответствующее ограничение записывается в виде неравенства + а, < Xj.

Рассмотрим условие неразветвленности производственного процесса. Для операций / и j\ не выполняемых на станке одновременно, или х - Xj > Qj , или х - х > а,, когда в оптимальном решении j предшествует / или / предшествует j соответственно. 178



Логические ограничения вида «или - или» не укладываются в рамки обычной задачи линейного программирования (так как порождают невыпуклое пространство допустимых решений). Эту трудность можно обойти путем введения вспомогательных булевых переменных

, если операция j предшествует операции /, " " если операция / предшествует операции j.

Если М достаточно велико, ограничение вида «или - или» эквивалентно следующей системе неравенств:

ЩJ-(x,-XJ)>aJ M(\-y,j)-\(Xj-x,)>a,.

В случае, когда для оптимального решения уу = О , второе неравенство становится избыточным, а активным ограничением будет первое неравенство. Если же yij = 1, первое неравенство становится избыточным,

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

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

Если обозначить через / суммарное время, требуемое для выполнения всех п операций, рассматриваемая задача принимает следующий вид:

t->min

Xj-aj<t, j =1,...,,

и выполняются ограничения трех перечисленных выше типов.

6.1.3. Задача о рюкзаке. К задачам рассматриваемого типа относится классическая задача о рюкзаке, которая в переменных О и 1 имеет следующий вид:

шах Z = CjXj + С2Х2 +... + с„х x,g{0; 1}, / = 1, 2,...,п.



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

. Общее количество имеющегося в распоряжении ресурса равно Ь.

Эффект от выбора /-й позиции есть с,. Следует осуществить выбор среди

позиций, допустимый в смысле затрат ресурсов, и имеющий максимальный суммарный эффект.

6.1.4. Задача оптимального выбора на множестве взаимозависимых альтернатив. В общем виде задача формулируется следующим образом. Пусть имеется N альтернатив, каждая из которых приносит прибыль в размере1,Необходимо выбрать не более к из

данных альтернатив так, чтобы суммарная прибыль была бы максимальна. На альтернативы наложены некоторые ограничения нескольких типов, а именно: 1) /-я альтернатива может быть выбрана только в том случае, если выбрана у-я; 2) /-я альтернатива не может быть выбрана, если выбрана у-я; 3) хотя бы одна из альтернатив /-я или у-я обязательно должна быть выбрана; 4) одна и только одна из альтернатив /-я или у-я обязательно должна быть выбрана; 5) А:-я альтернатива может быть выбрана, только если выбрана хотя бы одна из альтернатив /-я или у-я.

Для математической постановки задачи введем переменные логического (булева) типа, а именно: положим

если альтернатива / выбирается если альтернатива / не выбирается.

Целевую функцию задачи можно записать в виде рх + ....рх . Покажем, как можно выразить математически ограничения перечисленных типов.

1)х,-х.<0,

2)х,+х<1,

3)X, +х. >1,

4)X,+х. =1,

5)х,-х,-х<0.

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

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