Главная > Дискретное программирование
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

ГЛАВА 8. О РЕШЕНИИ ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПРОИЗВОЛЬНЫМИ ДОПОЛНИТЕЛЬНЫМИ УСЛОВИЯМИ

В последние годы выполнен ряд работ, посвященных переносу метода отсечения на задачи выпуклого целочисленного программирования (см. Куртийо [61], Кюнци и Этли [107], Витцгалл [127]).

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

Постановка задачи и идея метода изложены в § 1. Там же, в сущности, изложен простейший алгоритм. § 2 посвящен использованию специфики выпуклых и некоторых невыпуклых задач. В § 3 дано более подробное изложение применения третьего алгоритма Гомори и приведен численный пример.

§ 1. Постановка задачи и идея метода решения

1.1. Рассмотрим полностью целочисленную задачу линейного программирования с дополнительным условием.

Максимизировать

при условиях

Условие (1.5) совершенно произвольно. Многогранное множество ((1.2) -(1.3)) считаем ограниченным, так что множество (1.2)-(1.4) содержит лишь конечное множество точек. Числа считаем целыми,

1.2. Идея метода состоит в последовательном решении (с помощью метода отсечения) ряда вспомогательных полностью целочисленных задач линейного программирования: Переход от задачи к задаче также совершается с помощью метода отсечения. Если решение некоторой задачи удовлетворяет дополнительному условию (1.5), то процесс решения заканчивается и оказывается оптимальным планом задачи

1.3. Опишем переход от задачи к задаче Пусть оптимальный опорный план задачи не удовлетворяет дополнительному условию (1.5), причем множество индексов небазисных переменных, соответствующих .

Решение можно «отсечь», используя прием, аналогичный упомянутому выше приему Данцига

Теорема 1.1. Пусть

X — план задачи Тогда

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

откуда вследствие неотрицательности переменных получаем

Теорема 1.1 доказана.

1.4. Выберем алгоритм метода отсечения, с помощью которого будем решать вспомогательные задачи . Под подразумевается задача

шаг Решаем задачу . Если задача неразрешима, то неразрешима и задача Если задача разрешима и ее решение удовлетворяет дополнительному условию (1.5), то является одновременно решением задачи Если же решение неудовлетворяет условию (1.5), то вводим дополнительное ограничение (см. теорему 1.1), присоединяем его к условиям задачи и получаем задачу . Конечность процесса следует из конечности числа планов задачи

1.5. Этот метод можно распространить также и на за дачи с произвольной максимизируемой целевой функцией и ограничениями но в этом случае удается получить лишь приближенное решение.

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

Введем вспомогательную целевую функцию решим (указанным выше методом) задачу (1.1) — (1.5). Получим решение запомним его и перейдем к решению задачи (1.1) — (1.5) с дополнительным условием

Если новая задача (1.1) — (1.6) не имеет решения, то следует принять за приближенное решение задачи Если же задача имеет решение то вычеркнем из памяти запомним и перейдем к решению задачи (1.1) — (1.5) с дополнительным условием

Таким образом, за конечное число шагов получим искомое приближенное решение.

1.6. Изложенные выше методы носят универсальный характер, что связано с отсутствием каких-либо ограничений, наложенных на множество (входящее в условие и функцию Поэтому соответствующий вычислительный процесс может получиться весьма длительным. Например, при решении задачи (1.1) — (1.5) количество решаемых задач будет равно количеству планов X задачи , удовлетворяющих условию

где X — лексикографический оптимум задачи (1.1) — (1.5).

В следующем параграфе будут указаны некоторые приемы для использования специальных свойств

1
Оглавление
email@scask.ru