Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 17

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 11 12 13 14 15 16 < 17 > 18 19 20 21 22 23 .. 84 >> Следующая


Экономическая интерпретация. Пусть имеется п проектов, и для их реализации задан вектор ресурсов b = (Ьі, • • • > Ъш), bi > 0. Обозначим через CLij > 0 количество единиц ресурса типа г, необходимое для реализации проекта с номером j, при этом для любого ресурса s

п

выполнено условие asj > т«е. реализация всех проектов невоз-

J=I

можна. Пусть Cj > 0, j = 1, 2,..., п — прибыль, полученная при реализации проекта j. Требуется выбрать для реализации набор проектов с максимальной суммарной прибылью. Введем п булевых переменных:

{0, если проект j не реализуется, . _

1, если проект j реализуется, ^ 555

Получим задачу о многомерном ранце (2.2.4)-(2.2.6).

2.2.3. Общие свойства задач о ранце.

Существование допустимого решения. В задачах (2.2.1)-(2.2.3) и (2.2.4)-(2.2.6) допустимое решение всегда существует (например, нулевое). Если решить задачи линейного программирования (2.2.1)-(2.2.3') и (2.2.4)-(2.2.6') и в полученных оптимальных решениях заменить дробные значения Xj нулевыми, то получим допустимые решения задач (2.2.1)-(2.2.3) и (2.2.4)-(2.2.6). Число дробных значений в оптимальных решениях линейных задач не превосходит т.

Отсев подмножеств булевых векторов, не содержащих оптимальных решений. Рассмотрим вектор х = (жі, X2,..., хп), имеющий к единиц и п — к нулей. Если вектор х является допустимым (т.е. условия (2.2.2) или (2.2.5) выполнены), то можно исключить из дальнейшего рассмотрения 2к векторов, получающихся из х заменой любого числа единиц нулями, так как для любого такого вектора х значение функции f(x) будет меньше, чем f(x). Если вектор х не является допустимым (т.е. условия (2.2.2) или (2.2.5) не выполняются), то можно исключить из дальнейшего рассмотрения 2п~к векторов, которые получаются из х заменой любого числа нулей единицами, так как все эти векторы недопустимы.
46 Разд. I. Предмет и модели дискретного программирования

Оценка точности приближенных булевых решений. Пусть Z0 = = (z°,z2,, zJJ) — допустимое булево решение задачи (2.2.1)-(2.2.3) или (2.2.4)-(2.2.6); X0 = (х°, х\,..., X0n) — оптимальное булево решение; у0 = (2/1,2/2? • • • ?2/п) — оптимальное решение задачи (2.2.1)-(2.2.3') или (2.2.4)-(2.2.6'). Тогда имеет место следующее неравенство: Л

f(z°) < f(x°) < f(y°). (2.2.7)

Величина A = / (2/0) — / (z0) есть гарантированная оценка отклонения приближенного решения Z0 от оптимума X0.

Нахождение вектора у0 связано с решением задачи линейного программирования. Далее в п. 2.2.4 показано, что задача (2.2.1)-(2.2.3') решается просто. Для решения задачи (2.2.4)-(2.2.6') необходимо применение симплексного алгоритма, что не всегда удобно. Для задачи (2.2.4)-(2.2.6) можно получить более грубую оценку, решив последовательность из т задач вида (2.2.1)-(2.2.3').

Пусть fi — значение целевой функции для оптимального решения линейной задачи, полученной из задачи (2.2.4)-(2.2.6') с учетом лишь одного ограничения с номером і. Тогда вместо неравенства (2.2.7) получим

/ (*°) < / (ж0) < / (у0) < minm U (2.2.8)

В этом случае гарантированная оценка отклонения приближенного решения Z0 от оптимума X0 имеет вид

А = min fi - f(z°) .

1 <г<т

2.2.4. Алгоритм Данцига для линейной одномерной задачи о ранце. Рассмотрим задачу линейного программирования (2.2.1)-(2.2.3') и опишем алгоритм нахождения оптимального решения у0 =

= (у°1,у1---,у°п)-

Теорема (правило Данцига). Пусть переменные Xj1 I < j < п перенумерованы так, что Ai > Л2 > ... > An, где Aj= Cjfaj. Тогда

оптимальное решение у0 = (2/1 ? 2/2 ? • • • ? Уп) имеет вид

У°1 =2/2° = ... = 2/2-1 = 1, y°s+1 = y°s+2 = ... = 2/°= О,

5-1

¦2= U-V<

уs = [я- 2^аз) /

j=і

где s определяется из условия
Гл. 2. Модели дискретного программирования

47

Смысл этого правила очевиден. Единичные значения следует последовательно назначать переменным, начиная с наибольшей удельной ценности (ценности на единицу веса), при этом

f(y°) = E СІ + с* (R ~ E ai) /as-j=і ' j=і ''

Если все компоненты у9, j = 1,2,...,п целые (число дробных

компонент не больше одной), то у0 = х°; если 0 < у® < 1, то план Z0

получится при 2/0 — о, тогда

/ (у°) - / (^0) = Cs (д - j aS-

Перейдем к доказательству теоремы.

Рассмотрим решение линейной задачи (2.2.1)-(2.2.3'), полученное в соответствии с правилом Данцига:

V01 =V02 = ... = yti = h y°s+1 = y°s+2 = ... = 2/°= О,

Vs = Ir-YI ai) / a«-

Для этого решения имеем

/ (у0) = Y сз + с« (R ~ E ai) / a«’

і=I V J=I ' '

5-1

E aJ + = R¦

J = I

Пусть / = {I, 2,..., n} и Wr = {I, 2,..., s — I}. Построим допустимое решение X задачи (2.2.1)-(2.2.3') по следующему правилу: пусть W0 С W, тогда

Xj = I-Sj, jeW°, 0<Sj<l,

Xj = i, j є тп^°,

xJ=Iji j Є 0 < 7j < 1.

Покажем, что f(y°) — f(x) > 0. Вычислим /(ж):

/ (ж) = Ci (1 “ 5J') + E С3 + E cHi =

JGW0 jeW\W° jeI\W

= — ^ 5-/ Cj7j =

JGW0 jeW° jeW\W° jeI\W

s — 1

= ^sCj ~ ^CiTr

J = I JGW0 jel\w
48 Разд. I. Предмет и модели дискретного программирования

Выпишем ограничение для решения х:
Предыдущая << 1 .. 11 12 13 14 15 16 < 17 > 18 19 20 21 22 23 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100