3.Задача о назначении

Задача о назначении

- частный случай классической транспортной задачи,

где надо положить m=n, Si = 1, i=1,…n, Dj=1, j=1,…n.

Здесь сij – стоимость выполнения i –ой работы j-ым исполнителем. Если сij –эффективность

выыполнения работ, то

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

Предположим.что нам необходимообеспечитьмножествоклиентов М= {1,...,т) грузамив коли­честве di,гдеi принадлежитМ. Для перевозкигрузовмыможем задействоватьмножество автомобилей

N= {1,...,п). Каждыйj-ый автомобильхарактеризуется грузоподъемностьюqj и затратамина использованиесj, которые назовемаренднойплатой,не зависящейот пробега,времени использованияи т.п. Вводятпонятиетеневойцены

гдеdi/qj – потребности i – го клиента на единицу грузоподъемности j – го автомобиляи булевыпеременный Xij (Xij=1 если i-й клиент включен в рейс j-гоавто и 0 в противном случае).

Тогда критерий будет иметь вид

Первая группа ограничений гарантирует, что все клиенты будут обслужены. Вторая группа ограничений — ограничения на грузоподъемность, выраженные в неравенствах. Третья группа ограничений — ограничения на количество обслуживаемых одним автомобилем клиентов, которые косвенно учитывают ограничения по времени доставки, и, наконец, последняя группа ограничений — это условия двоичности переменных.

Пример 5

Пустьнеобходимосформировать развозочные маршруты для обслуживания5 клиентов, вес партии товара каждогоиз них колеблетсяв диапазоне от 0,8 до1,45 т, а общийвес всех товаров составляет5,9 т.В нашем распоряжении имеется 7 автомобилей:5 автомобилей ГАЗ-3302 «Газель»

грузоподъемностью1,5 т и 2 автомобиля ГАЗ-53

грузоподъемностью3,0 т. Стоимостьаренды автомобиля ГАЗ3302«Газель»— 1000 руб.,а автомобиля ГАЗ-53 — 1500 руб. Таким образом,имеется избытокпровозных возможностей, следовательно,необходимоопределить подвижной состав, использование которогоминимизирует транспортные издержки,и оптимально загрузитьего, т.е.разложитьзаказы потранспортным средствам.Ниже представлены исходные данные рассматриваемой задачи.

Исходныеданные о раскладке заказов по транспортнымсредствам

Расчитываются по формулам:

Табличнаямодель задачи о раскладке заказовпо транспортным средствам (матрица теневых цен Сij)

Табличнаямодель задачи о раскладке заказовпо транспортным средствам (матрица Xij)

Табличнаямодель задачи о раскладке заказовпо транспортным средствам (матрица произведения Сij* Xij)

Окно поиск решения