Зенкевич Н.А. Практикум по исследованию операций

Подождите немного. Документ загружается.

5.4. ЗАДАЧА О ЗАГРУЗКЕ 121

Прибыль от распределения пяти единиц капитала по четырем экономическим ре-

гионам F

1234

(A) = 120, оптимальная политика распределения (1,2,1,1), т. е. в первый

экономический регион следует вложить одну единицу капитала, во второй две, в третий

и четвертый регион одну единицу капитала.

5.4 Задача о загрузке

Экспедиторская фирма имеет заказ на доставку N предметов различных типов. Каж-

дый предмет типа i имеет веc w

и страховую стоимость c

, (i =

1, N) Максимальная

грузоподъемность фургона экспедиторской фирмы равна M. Требуется определить мак-

симальную стоимость груза, вес которого не должен превышать максимально допусти-

мой грузоподъемности фургона. Для определенности предположим, что M = 5 и всего

имеются три типа предметов, сведения о которых приведены в таблице:

i w

1 2 70

2 3 60

3 1 30

Рассмотрим задачу в общей постановке. Обозначим количество предметов типа i че-

рез k

. Тогда задача загрузки фургона может быть записана в виде:

max z = max(c

+ c

+ . . . + c

)







+ w

+ . . . + w

≤ M,

≥ 0, k

− целые, i =

1, N

Если бы возможно было бы отбросить требование целочисленности, то это задача

линейного программирования и ее можно было бы решить симплекс-методом

Выделим три основных элемента динамической модели.

1. Этап j ставится в соответствие типу j, j = 1, 2, . . . , N

2. Состояние y

на этапе j выражает суммарный вес предметов, решение о погрузке

которых приняты на этапах j, j + 1. . . . , N; при этом y

может принимать значения

0, 1, . . . , M при j = 1, 2, . . . , N.

3. Варианты решения. Величины k

на этапе j описывают количеством предметов

типа j. Значение k

∈ [0, [M/w

]], где [M/w

] – целая часть числа M/w

122 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Пусть f

) – максимальная суммарная стоимость предметов, решение о по грузке

которых приняты на этапах j, j + 1. . . . , N при заданном состоянии y

Рекуррентное соотношение имеет следующий вид:

) = max

∈ {0, 1, . . . , N},

= 0, 1, . . . , M

};

) = max

= 0, 1, . . . , [M/w

]

= 0, 1, . . . , M

+ f

j+1

− w

)}, j = 1, 2, . . . , N − 1;

Максимальное значение k

ограничено величиной [M/w

], что позволяет отсекать все

не являющиеся допустимыми варианты при заданном значении переменного состояния

Для нашего примера поэтапные расчеты начинаются с третьего этапа и осуществля-

ются следующим образом.

Этап 3.

) = max

(30k

), max k

= [5/1] = 5

30k

Оптимальное решение

= 0 1 2 3 4 5

= 0 30 60 90 120 150 f

) k

∗

0 0 - - - - - 0 0

1 0 30 - - - - 30 1

2 0 30 60 - - - 60 2

3 0 30 60 90 - - 90 3

4 0 30 60 90 120 - 120 4

5 0 30 60 90 120 150 150 5

Этап 2.

) = max

(60k

+ f

− 3k

)), max k

= [5/3] = 1

5.4. ЗАДАЧА О ЗАГРУЗКЕ 123

60k

+ f

− 3k

) Оптимальное решение

= 0 1

= 0 60 f

) k

∗

0 0 + 0 = 0 - 0 0

1 0 + 30 = 30 - 30 0

2 0 + 60 = 60 - 60 0

3 0 + 90 = 90 60+0=60 90 0

4 0 + 120 = 120 60+30=90 120 0

5 0 + 150 = 150 60+60=120 150 0

Значения в столбцах получаются при использовании реккурентных соотношений.

Например, значение в столбце c

= 0 при y

= 1 получаем следующим образом:

) = max

(60 ∗ 0 + f

(1 − 3 ∗ 0)) = 0 + f

(1) = 0 + 30, поскольку из таблицы эта-

па 3, f

(1) = 30.

Этап 1.

) = max

(70k

+ f

− 2k

)), max k

= [5/2] = 2

70k

+ f

− 2k

) Оптимальное решение

= 0 1 2

= 0 70 140 f

) k

∗

0 0 + 0 = 0 - - 0 0

1 0 + 30 = 30 - - 30 1

2 0 + 60 = 60 70+0=70 - 65 1

3 0 + 90 = 90 70+30=100 - 95 1

4 0 + 120 = 120 70+60=130 140+0=140 140 2

5 0 + 150 = 150 70+90=160 140+30=170 170 2

При заданном y

= M = 5 оптимальным решение является (k

∗

, k

∗

, k

∗

) = (2, 0, 1), а

суммарная стоимость груза равна 170.

124 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

5.5 Задача календарного планирования трудовых ре-

сурсов

Фермерскому хозяйству необходимо составить план регулирования численности сезон-

ных рабочих на последующие пять недель. Управляющий хозяйством оценивает мини-

мально необходимую потребность в рабочей силе b

на каждую из пяти недель. Потреб-

ность в рабочих по пяти неделям распределяется следующим образом b

= 5, 7, 8, 4, 6, i =

1, 5.

Управляющий имеет возможность регулировать количество рабочих имеющихся в

наличии путем найма и увольнения. При найме рабочих управляющий терпит убытки в

виде накладных расходов по найму: 600 руб. в неделю плюс 300 руб. на каждого рабочего.

С другой стороны сохранение в течении какой-либо неделе количество рабочих, которое

превышает минимальную потребность, приводит к убыткам, связанным с выплатами 500

руб. на каждого рабочего в неделю.

Введем обозначения: y

– количество рабочих, имеющихся на j-ой неделе, g

− b

)–

величина убытков, связанных с тем, что y

превышает заданное значение b

. g

−y

j−1

)–

величина накладных расходов по найму новый рабочих y

≥ y

j−1

Пусть предприниматель располагает следующими данными:

− b

) = 5(y

− b

), j = 1, . . . , 5;

− y

j−1

) =







6 + 3(y

− y

j−1

), y

> y

j−1

;

0, y

≤ y

j−1

Из определения g

видно, что увольнение (y

≤ y

j−1

) не требует накладных расходов.

Необходимо составить оптимальный план регулирования численности рабочих для 5-

недельного периода планирования, при условии, что количество рабочих y

, имеющихся

к началу первой недели, составляет пять человек.

Задаче календарного планирования подразделяется на несколько этапов.

1.j-й этап соответствует j-ой неделе.

2.Состояние y

j−1

на этапе j выражает количество рабочих, имеющихся к концу этапа

j − 1.

3.Варианты решения y

описываются количеством рабочих имеющихся на этапе j.

Обозначим через f

− 1) минимальную величину расходов, осуществленных в те-

чении периодов времени (недель) j, j + 1. . . . , 5 при заданном (y

− 1). Рекуррентные

5.5. ЗАДАЧА КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ТРУДОВЫХ РЕСУРСОВ 125

соотношения записываются в виде:

) = min

− b

) + g

− y

)};

j−1

) = min

≥ b

j = 1, 2, 3, 4.

− b

) + g

− y

j−1

) + f

j+1

)};

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

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

, j = 1, 2, 3, 4, 5. Значение j = 5

соответствует последнему периоду времени, а увольнение не несет за собой накладных

расходов, то значение y

должно равняться минимальной потребности в рабочей силе b

то есть y

= b

= 6. На этапе 4, b

< b

(4<6), то есть предприниматель может при пере-

ходе от этапа 4 к этапу 5 рассматривать варианты решения y

= 4, 5 или 6, в поисках

решения с минимальными издержками. Действуя аналогично получим что на этапе 3 у

предпринимателя есть один вариант решения y

= 8, поскольку на этапе 3 необходимо

восемь рабочих, а на этапе 4 не более 6, следовательно при переходе на этап 4 пред-

приниматель будет сокращать количество рабочих. На втором этапе предприниматель

имеет два варианта решения y

= 7 или 8, и на этапе 1 выбирает между вариантами

= 5, 6, 7, 8. Из условия задачи следует количество рабочих перед началом первого

этапа y

= 5.

Этап 5.

= 6 Оптимальное

− 6) + g

− y

) решение

= 6 f

) y

∗

4 5 ∗ (0) + 6 + 3 ∗ (2) = 12 12 6

5 5 ∗ (0) + 6 + 3 ∗ (1) = 9 9 6

6 5 ∗ (0) + 0 = 0 0 6

Этап 4.

= 4 Оптимальное

− 4) + g

− y

) + f

) решение

= 4 5 6 f

) y

∗

8 0 + 0 + 12 = 12 5 ∗ (1) + 0 + 9 = 14 5 ∗ (2) + 0 + 0 = 10 10 6

126 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Этап 3.

= 8 Оптимальное

− 8) + g

− y

) + f

) решение

= 8 f

) y

∗

7 0 + 6 + 3 ∗ (1) + 10 = 19 19 8

8 0 + 0 + 10 = 10 10 8

Этап 2.

= 7 Оптимальное

− 7) + g

− y

) + f

) решение

= 7 8 f

) y

∗

5 0 + 6 + 3 ∗ (2) + 19 = 31 5 ∗ (1) + 6 + 3 ∗ (3) + 10 = 30 30 8

6 0 + 6 + 3 ∗ (1) + 19 = 28 5 ∗ (1) + 6 + 3 ∗ (2) + 10 = 27 27 8

7 0 + 0 + 19 = 19 5 ∗ (1) + 6 + 3 ∗ (1) + 10 = 24 19 7

8 0 + 0 + 19 = 19 5 ∗ (1) + 0 + 10 = 15 15 8

Этап 1.

= 5 Оптимальное

− 5) + g

− y

) + f

) решение

= 5 6 7 8 f

) y

∗

5 0 + 0 5 ∗ (1) + 6 5 ∗ (2) + 6 5 ∗ (3) + 6 43 5

+30 = 30 +3 ∗ (1)+ +3 ∗ (2)+ +3 ∗ (3)+

+27 = 38 +24 = 46 +15 = 45

Оптимальное решение задачи находится последовательно:

= 5 → y

∗

= 5 → y

∗

= 8 → y

∗

= 8 → y

∗

= 6 → y

∗

= 6.

Полученному решению соответствует следующий план:

5.6. ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ 127

Неделя j

Минималь-

ная по-

требность

в рабочей

силе b

Решение

1 5 5 Никого не нанимать и не увольнять

2 7 8 Нанять трех сезонных рабочих

3 8 8 Никого не нанимать и не увольнять

4 4 6 Уволить двух сезонных рабочих

5 6 6 Никого не нанимать и не увольнять

5.6 Задача о кратчайшем пути

Рассмотрим сеть c конечным числом вершин i

, . . . , i

. Обозначим t

i,j

> 0 – время пере-

хода из узла i в узел j, i

-начальная вершина. Необходимо перейти из узла i

в узел M за

кратчайшее время. Пусть T (j) – минимальное время перехода из вершины i в вершину

Переходим из вершины i

в любую вершину j, а далее действуем оптимально, то есть

T (i

) ≤ t

+ T (j).

Тогда справедливо







T (j) = min

+ T (j)),

T (M) = 0.

Введем понятие минимального времени перехода из вершины i в вершину M, исполь-

зуя ноль промежуточных вершин

(i) = t

(i) – минимальное время перехода из вершины i в вершину M, используя не бо-

лее одного промежуточного хода. Аналогично T

(i) – минимальное время перехода из

вершины i в вершину M, используя не более k промежуточных вершин.

Таким образом, получаем невозрастающую последовательность {T

(i)}

k=0

(i) = min

+ T

k−1

(j)),

если j

∗

= i, то T

(i) = T

k−1

(j).

Пусть мы нашли путь (

, . . . , i

), l ≤ n, минимизирующий время.

128 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Уравнение Беллмана вдоль этого пути:

T (

) = t

+ T (

T (i

) – оптимальное время перехода. Точное время перехода – разность оптимальных

времен: t

= T (

) − T (i

)

Пример 5.6.1.

Необходимо построить кратчайший путь из вершины 1 в вершину 5.

Пишем функциональное уравнение для нашего примера.







(j) = min

+ T

k−1

(j)),

(M) = 0.

(j) – минимальное время перехода из вершины j в вершину M, используя не более

k промежуточных вершин.

В нашем случае имеем:

(4) = 1, T

(3) = 2, T

(2) = 3,

(2) = min{t

+ T

(3), T

(2)} = {3, 7} = 3,

(4) = min{t

+ T

(3), T

(4)} = {1, 7} = 1,

(3) = min{t

+ T

(4), t

+ T

(2), T

(3)} = {6, 8, 2} = 2,

(1) = min{t

+ T

(3), t

+ T

(4), t

+ T

(2)} = {5, 5, 4} = 4,

(1) = min{t

+ T

(4), t

+ T

(3), t

+ T

(2)} = {5, 5, 4} = 4,

(1) = T

(1) = 4, следовательно алгоритм останавливается, из первой вершины в

пятую можно попасть за минимальное время 4, используя одну промежуточную верши-

ну.

5.7. ЗАДАЧА О ДВУХ СТАНКАХ 129

5.7 Задача о двух станках

Пусть имеется N деталей, которые должны пройти последовательную обработку на двух

станках.

Введем обозначения:

– время обработки i-ой детали на первом станке;

– время обработки i-ой детали на первом станке.

Процесс обработки деталей протекает следующим образом. Детали располагают в

некотором порядке, например 1, 2, . . . , N . После того как первая деталь проходит про-

цесс обработки на первом станке, она попадает на обработку на второй станок. Второй

станок не может приступить к обработке второй детали, пока не закончится ее обработ-

ка на первом станке. Задача формулируется следующим образом: требуется определить

порядок запуска деталей в обработку (перестановку из множества деталей), минимизи-

рующую суммарное время простоя второго станка в ожидании деталей.

Пусть x

– время простоя второго станка перед тем, как на него поступит деталь i.

Запишем рекуррентные соотношения:

= a

= max(a

+ a

− b

− x

, 0),

+ x

= max(a

+ a

− b

, a

= max(

i=1

−

i=1

−

i=1

, 0),

+ x

= max(

i=1

−

i=1

− b

, a

по индукции получаем:

i=1

= max

1≤n≤N

, где K

i=1

−

n−1

i=1

Введем функцию Беллмана: w(a

, b

, a

, b

, . . . , a

, b

, t) – время, необходимое для об-

работки N деталей при условии, что второй станок начинает работать на t единиц позже

первого и при этом использует оптимальную перестановку деталей.

Если станки начинают обработку с детали i, то мы получаем следующее функцио-

нальное уравнение:

w(a

, b

, a

, b

, . . . , a

, b

, t) = min

+ w(a

, b

, a

, b

, . . . , 0, 0, . . . , a

, b

; b

+ max[t − a

, 0])] ,

130 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

где на месте пары (a

, b

) стоит пара (0, 0).

Чтобы из этого соотношения получить оптимальную перестановку, поменяем местами

две детали. Тогда обрабатывая сначала деталь i, а затем деталь j, получим:

w(a

, b

, a

, b

, . . . , a

, b

, t) = a

+ a

+ w(a

, b

, a

, b

, . . . , 0, 0, . . . , a

, b

, t),

где

= b

+ max[b

+ max(t − a

, 0) − a

, 0] =

= b

+ b

− a

+ max[max(t − a

, 0), a

− b

] =

= b

+ b

− a

+ max[t − a

, a

− b

, 0] =

= b

+ b

− a

+ max[t, a

+ a

− b

, a

] =

= b

+ b

− a

+ max[t, max[a

+ a

− b

, a

]].

Пусть теперь деталь под номером j находится на первом месте:

= b

+ b

− a

+ max[t, max[a

+ a

− b

, a

]].

Теперь мы видим, что если выполняется условие:

max[a

+ a

− b

, a

] > max[a

+ a

− b

, a

то деталь i и деталь j следует поменять местами.

Этот критерий можно переписать в виде:

+ a

+ max[−b

, −a

] > a

+ a

+ max[−b

, −a

Таким образом можно сказать, что перестановка необходима в том случае если вы-

полняется

min[b

, a

] < min[b

, a

откуда непосредственно следует алгоритм.

5.7.1 Алгоритм решения задачи о двух станках.

Алгоритм впервые предложил Джоносон.

Шаг 1. Начать с таблицы