Составители:
54
Примерами практических задач о назначениях могут быть задачи
размещения туристов в гостинице, распределения отпусков сотрудни-
ков, составления графика дежурств.
Транспортная задача
Транспортной задачей обычно называют задачу о выборе плана пере-
возок из m пунктов отправления в n пунктов назначения [15]. В качестве
условия задачи задается набор коэффициентов c
ij
, определяющий стоимость
доставки продукции из пункта i в пункт j. Ресурсы продукта в пунктах
отправления обозначим a
i
, а потребность продуктов в пунктах назначения
b
j
. Обычно предполагается, что должна быть выполнена вся программа
перевозок, которая задается в виде ограничений
11
.
mn
i
j
ij
ab
==
=
∑∑
Целевая функция задачи имеет вид
11
mi
n,
mn
ij ij
ij
Ecx
==
=→
∑∑
где x
ij
– расчетная программа перевозки из пункта i в пункт j. Так,
например, если m = 4, n = 5, количество имеющихся ресурсов в пунк-
тах отправления описывается набором значений a ={3,43; 6,56; 1,31; 6,43};
потребность в ресурсах в пунктах назначения описывается набором
значений b ={1,72; 4,92; 3,38; 1,89; 5,83}; матрица коэффициентов c
ij
имеет
вид табл. 3.7, в которой столбцы соответствуют номерам пунктов от-
правления, а строки – номерам пунктов назначения. Тогда решением
Таблица 3.5
Значения прибыли
от назначения кандидата
на соответствующую работу
в открытой задаче
Таблица 3.6
Оптимальный вариант
назначения кандидатов
на должности (решение)
в открытой задаче
c
ji
12345
100,027,037,087,092,0
255,085,068,069,073,0
320,009,086,086,033,0
400,029,084,050,085,0
: ! " #
!
"
Страницы
- « первая
- ‹ предыдущая
- …
- 52
- 53
- 54
- 55
- 56
- …
- следующая ›
- последняя »
