Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Транспортная задача - это модель ситуации, в которой требуется найти оптимальный план перевозки некоторого груза из конечного числа пунктов поставки (отправления) с заданными объемами производства в конечное число пунктов потребления (назначения) с требуемыми объемами потребностей при известных затратах на перевозку единицы груза между каждой парой пунктов поставки и потребления. Предполагается, что удельные затраты не зависят от количества перевозимого груза. Здесь под оптимальным понимается план, минимизирующий суммарные затраты на перевозки.
В качестве примера рассмотрим задачу с двумя пунктами отправления и тремя пунктами назначения, схема которой показана на рис.4.1. Здесь а 1 и а 2 – количество груза, которым располагают пункты отправления, b 1, b 2, b 3 – потребности в грузе пунктов назначения.
Задача является сбалансированной, если суммарная потребность равна суммарной возможности. В нашем примере это значит, что
Рис. 4.1.
Если ввести обозначения:
xij - количество груза, перевозимого из i- го пункта отправления в j -й пункт назначения;
Сij – затраты на перевозку единицы груза из i -го пункта отправления в j -й пункт назначения,
то исходные данные вместе с переменными можно представить в одной таблице (табл. 4.3):
Таблица 4.3
Пункты | B1 | B2 | B3 | Количество груза |
A1 | С 11 Х 11 | С 12 Х 12 | С 13 Х 13 | a 1 |
A2 | С 21 Х 21 | С 22 Х 22 | С 23 Х 23 | a 2 |
Потребность в грузе | b 1 | b 2 | b 3 |
Так как необходимо минимизировать суммарные затраты по перевозке, то целевая функция запишется в виде
L=C 11 x 11 + C 12 x 12 + C 23 x 23 → min.
Каждый пункт назначения должен получить требуемое количество груза. Отсюда следуют равенства, соответствующие этим пунктам
B1: x 11 +x 21 =b 1;
B2: x 12 +x 22 =b 2;
B3: x 13 +x 23 =b 3.
Поскольку задача сбалансированная, весь груз из пунктов отправления должен быть вывезен. Это требование отражается в модели двумя равенствами:
А1: х 11 +х 12 +х 13 =а 1;
А2: х 21 +х 22 +х 23 =а 2.
Наконец, физический смысл переменных накладывает на них ограничение неотрицательности
" xij³0.
В результате мы получили модель транспортной задачи, содержащей только линейные функции. Очевидно, что характер модели не изменится при увеличении числа пунктов.
Дата публикования: 2015-01-23; Прочитано: 542 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!