Лекции.Орг


Поиск:




Построение математической модели.

Транспортная задача.

Имеется m поставщиков - пунктов производства (хранения) однородного продукта. Для каждого из поставщиков известна мощность, т.е. количество единиц продукции, доступных для отправки от соответствующего поставщика в единицу времени (неделю, месяц, квартал). Мощности будем обозначать: а1, а2,..., аm,

Имеется n потребителей - пунктов потребления рассматриваемого продукта. Для каждого из потребителей предполагается известной потребность в единицу времени (неделю, месяц, квартал). Потребности будем обозначать: b1, b2,..., bn.

Возможна доставка грузов от каждого поставщика к каждому потребителю. Удельные затраты (транспортные тарифы) на перевозку единицы продукта от поставщика с номером- i к потребителю с номером- j - известны для всех маршрутов и будут обозначаться сij. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы на доставку продуктов минимальны.

Рисунок 3.1. Графическое представление условий транспортной задачи.

Построение математической модели.

Предположим, что суммарная мощность всех поставщиков равна суммарной потребности всех потребителей. Такую модель будем называть сбалансированной (или замкнутой) моделью транспортной задачи. Формально условие баланса представлено соотношением (3.1).

(3.1)

Если через хij обозначить количество груза, планируемого к перевозке от i-го поставщика j-му потребителю, то математическая модель транспортной задачи будет выглядеть так:

найти план перевозок Х = (хij), минимизирующий общую стоимость всех перевозок

(3.2)

при условии, что из каждого пункта производства вывозится весь продукт

(3.3)

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

(3.4)

причем по смыслу задачи все переменные могут принимать только неотрицательные значения хij ³0.

Из системы условий (3.2 – 3.5) видно, что транспортная задача является задачей линейного программирования. Но эта система имеет ряд особенностей, которые позволили разработать для решения транспортной задачи алгоритмы, более эффективные, чем симплекс-метод, предназначенный для решения задач линейного программирования общего вида.

Нарушение условий баланса: åаi = åbi

Если суммарная мощность поставщиков превосходит общий заказ потребителей, можно ввести фиктивный пункт потребления с объемом потребления b0 =åаi – åbi, причем тарифы на перевозку в этот пункт условимся считать равными нулю.

Если суммарная мощность поставщиков меньше общего заказа потребителей, можно ввести фиктивного поставщика с мощностью а0 =åbi –åаi, причем тарифы на перевозки из этого пункта условимся считать равными нулю.

 



<== предыдущая лекция | следующая лекция ==>
Методические указания по выполнению задачи 2. | 
Поделиться с друзьями:


Дата добавления: 2017-01-28; Мы поможем в написании ваших работ!; просмотров: 324 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Надо любить жизнь больше, чем смысл жизни. © Федор Достоевский
==> читать все изречения...

821 - | 660 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.