<< Предыдущая

стр. 7
(из 9 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


Ее решение дает оценку снизу решения исходной задачи. Более того, мы
получаем допустимое решение, а значит можем оценить его погрешность.
Пример 3.1. Программа развития отрасли состоит из трех проектов,
данные о которых приведены в таблице 3.1. Пусть график финансирования
имеет вид N1 = 10, N2 = 8, N3 = 6, N4 = 4. Значения dik приведены в таблице
3.2, а значения cik транспортной задачи приведены в таблице 3.3.
46

Таблица 3.1.

i 1 2 3

10 12 6
wi

5 4 3
ai

?i 2 3 2

3 4 2
ci




Таблица 3.2.
k
1 2 3 4
i
1 1 2 2
1

1 1 1 2
2

1 1 2 2
3




Таблица 3.3.
k
1 2 3 4
i
3 3 6 6
1
5 5 5 5
1 1 1 2
2
2 2 4 4
3
3 3 3 3
47

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



1
(3)
(4) (10)
(1)
1
(2)
(10)
(4) 2 (8)
(4)
(12)
0 2 Z
(6)
3
(4)
(3)
(6)
(3) (4)
3

4

Рис.3.1.


Величина критерия С оценочной задачи (3.6) - (3.8) равна 253/5. Мы
видим, что в полученном решении проект 1 завершается в четвертом
периоде, проект 2 - в третьем, а проект 3 - во втором. Это допустимое
решение для задачи минимизации упущенной выгоды с величиной
упущенной выгоды
F = 4с1 + 3с2 + 2с3 = 12 + 12 + 4 = 28.
Таким образом отклонение полученного решения от оптимального не
превышает 2 единицы, поскольку оценку снизу 253/5 можно заменить на 26
в силу целочисленности значений упущенной выгоды. Для того, чтобы
получить оптимальное решение применим метод ветвей и границ. Для
этого разобьем множество всех решений на два подмножества. В первом
подмножестве проект 1 завершается в четвертом периоде, а во втором -
48

раньше четвертого периода. Для первого подмножества мы уже имеем
оптимальное решение со значением F = 28, поскольку второй проект не
может завершаться раньше третьего периода, а третий - раньше второго.
Оценим второе подмножество. Для этого нужно решить
транспортную задачу, исключив дугу соответствующую
(1, 4),
выполнению проекта 1 в четвертом периоде. Оптимальное решение этой
задачи приведено на рис. 3.2.



1
(5)
(4) (10)
(3)
1
(2)
(10)
(4) 2 (8)
(3)
(12)
0 2 Z
(6)
3
(4)
(1)
(6)
(4)
(2) (1)
3
(3)
4

Рис.3.2.


Величина критерия оценочной задачи равна 271/5 или 28 с учетом
целочисленности. Следовательно, полученное выше решение не хуже, чем
оптимальное решение во втором подмножестве, а значит является
оптимальным.
В рамках рассмотренного подхода можно учесть и ограничения на
моменты начала и завершения проектов а также запрещения на
выполнение проекта в определенных периодах. Для этого достаточно
49

оставить в транспортной сети только допустимые дуги (i, j) (проект i
может выполняться в периоде j).
Пример 3.2. Пусть в задаче, рассмотренной в примере 3.1 имеются
дополнительные ограничения. А именно, проект 3 может начинаться
только со второго периода, а проект 1 должен завершаться не позже
третьего периода. График финансирования имеет вид: N1 = 6, N2 = 9,
N3 = 10, N4 = 3. Так как матрица затрат (таблица 3.3) не изменилась, то
решаем транспортную задачу исключив из сети дугу (3, 1), так как проект
3 не может выполняться в первом периоде, и дугу (1, 4), так как проект 1
должен завершиться не позже третьего периода. Оптимальное решение
задачи приведено на рис.3.3.



1
(2)
(6)
(3)
1
(5)
(10)
2 (9)
(4)
(4)
(12)
0 2 Z
(4) (10)
3
(2)
(6)
(1) (3)
3
(3)
4

Рис.3.3.


Имеем величину оценки снизу C = 9 + 12 + 62/3 = 272/3, или 28. Так
как первый проект завершается в третьем периоде, второй также в
третьем, а третий - в четвертом, то величина упущенной выгоды F = 3?3 +
50

4?3 + 2?4 = 29. Погрешность полученного решения составляет 29 - 28 = 1.
Покажем, что полученное решение является оптимальным. Для этого
заметим, что первый проект не может быть завершен во втором периоде,
поскольку в этом случае в третьем периоде образуется избыток
финансовых ресурсов. Третий проект может завершиться в третьем
периоде, но тогда второй проект завершится в четвертом периоде, что
приведет к росту упущенной выгоды на две единицы.
На практике часто встречаются задачи, в которых задан срок
завершения проекта, при превышении которого возникают потери. В этом
случае выражение для упущенной выгоды принимает вид
n
F = ? c i ( t i ? D i )1[ t i ? D i ] , (3.9)
i =1

где Di - желательный срок завершения i-го проекта, 1[x] = 1, если ti > Di и 0
в противном случае. Для того, чтобы сформулировать оценочную задачу
для этого случая определяем числа dik по аналогии с вышеописанным
случаем, принимая за начальный период (Di + 1), то есть dik=0 если k ? Di и
? k + ? i ? D i ? 1?
d ik = ? ?,
?i
? ?
если k > Di. В этом случае, если ti > Di, то
x ik d ik
?
t i ? Di ? .
ai
k > Di

Доказательство этого факта проводится по аналогии с доказательством
леммы 3.1.
Таким образом мы получаем оценочную задачу (3.6) - (3.8), решение
которой дает приближенное решение исходной задачи с оцениваемой
погрешностью.
Пример 3.3. Примем, что все ai = 1. В этом случае объем
финансирования проекта совпадает с минимальной
wi
51

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

i 1 2 3 4

?i 2 3 1 2

3 4 3 2
Di

3 4 2 1
ci


Пусть Nk = 1, k = 1, 8 .
Таблица коэффициентов сij оценочной транспортной задачи
приведена ниже.
Таблица 3.5.
k
1 2 3 4 5 6 7 8
i
0 0 3 6 6 9
1 0 3

0 0 4 4 8
2 0 0 4

0 0 2 4 6 8 10
3 0

0 0 1 1 2 3
4 2 3


Оптимальное решение оценочной задачи выделено жирным шрифтом с
подчеркиванием. Имеем C = 12, а величина упущенной выгоды для
соответствующего допустимого решения F = 24. Действительно, t1 = 5,
t2 = 7, t3 = 1, t4 = 8 и следовательно
F = 3(t1 - 3) + 4(t2 - 4) + 1?( t4 - 2) = 24.
Разобьем множество всех решений на два подмножества. В первом
проект 2 завершается не раньше 7-го периода, а во втором - не позже 6-го
52

<< Предыдущая

стр. 7
(из 9 стр.)

ОГЛАВЛЕНИЕ

Следующая >>