Курсовой проект По дисциплине: «Логистика на транспорте» Студент 5 курса
жүктеу/скачать 0,68 Mb.
|
Логистика ПЗ
- Бұл бет үшін навигация:
- 2.1 Математическая постановка транспортной задачи.
| 2.Сущность транспортной задачи
Транспортная задача - это специальный вид задачи линейного программирования. Для решения транспортной задачи можно использовать методы решения задач линейного программирования, однако ввиду специфического вида задачи, были построены алгоритмы специально для решения этой задачи. 2.1 Математическая постановка транспортной задачи. Общая постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза из пунктов отправления A1, A2,..., Am в пункты назначения B1, B2,..., Bn. Критерий оптимальности берется минимальная стоимость перевозки или минимальное время доставки груза. Рассмотрим транспортную задачу, где в качестве критерия оптимальности взята минимальная стоимость перевозок всего груза. Обозначим через Сij тарифы перевозки единицы груза из пункта отправления i в пункт назначения j. Обозначим через Ai запасы груза i-м пункте отправления, а через Bj потребности груза j-м пункте назначения, а через Xj количество единиц груза переводимого из пункта отправления i в пункт назначения j. Тогда математическая модель транспортной задачи состоит в определении минимального значения функции
при условиях
Поскольку удовлетворяется условия (1.2)−(1.4), то обеспечивается доставка необходимого количества груза в каждый из пунктов назначения, вывоз груза из всех пунктов отправления, а также исключаются обратные перевозки. Определение 1. Любое неотрицательное решение Xij=∥xij∥ (i=1,..,m; j=1,...,n) систем (1.2) и (1.3) называется допустимым планом транспортной задачи. Определение 2. План при котором функция (1.1) принимает минимальное значение, называется оптимальным планом транспортной задачи. Если сумма груза у поставщиков равно общей сумме потребностей в пунктах назначения:
то модель транспортной задачи называется закрытой . Если (1.5) не удовлетворяется, то модель транспортной задачи называется открытой. Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие (1.5). В случае превышения запаса над потребностью, т.е. при
вводится фиктивный (n+1)-ый пункт назначения с потребностью
Соответствующие тарифы считаются равными нулю: ci n+1=0 (i=1,...,m). После этих преобразований получим закрытую модель транспортной задачи. Аналогично, при вводится фиктивный (m+1) пункт отправления с грузом а тарифы полагаются равными нулю: cm+1j=0 (j=1,...,n). После этих преобразований получим закрытую модель транспортной задачи. Обычно данные транспортной задачи записывают в виде таблицы:
Число переменных Xij равно mn, где m число пунктов отправления , а n число пунктов назначения. Число уравнений в (1.2) и (1.3) равно m+n. Так как мы рассматриваем закрытую модель транспортной задачи (выполняется равенство (1.5)), то число линейно независимых уравнений равно m+n−1. Следовательно опорный план транспортной задачи может иметь не более m+n−1 отличных от нуля неизвестных. Если в опорном плане количество отличных от нуля компонентов равно в точности m+n−1, то опорный план называется невырожденным, а если меньше − то вырожденным. жүктеу/скачать 0,68 Mb. Достарыңызбен бөлісу:
|