Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида продукции (однородного груза) из нескольких пунктов поставки (например, баз или заводов) в пункты потребления (например, заводы или склады).

Транспортная задача, по существу, представляет собой задачу линейного программирования, которую можно решать симплекс-методом. Но, в силу особой своей структуры, она допускает решение более простым методом, который по своей сути вытекает из теории двойственности.

В простейшей формулировке транспортная задача выглядит следующим образом. Пусть m поставщиков располагают a1, a2,..., am единицами некоторого однородного груза и этот груз должен быть доставлен n потребителям в количествах b1, b2,..., bn единиц соответственно. Предполагается, что ai >0, bj >0. Известны стоимости cij ( ) перевозки единицы груза от i-го поставщика j-му потребителю. Следует определить план перевозок, т. е. указать количество груза, которое каждый поставщик должен доставить каждому потребителю, так, чтобы суммарные транспортные затраты были минимальными.

Пусть xij – количество груза, перевозимого от i-го поставщика j-му потребителю, тогда план перевозок транспортной задачи можно представить в виде матрицы X=(xij) размера , и математическая модель задачи линейного программирования транспортного типа имеет вид:

минимизировать целевую функцию

(2.9)

при ограничениях

, (2.10)

, (2.11)

. (2.12)

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

Заметим, что система уравнений (2.10)–(2.11) совместна тогда и только тогда, когда выполняется равенство между суммарными ресурсами и суммарными потребностями:

 

. (2.13)

 

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

Если , т. е. имеется избыток продукции по отношению к действительно требуемому ее количеству, то введем в рассмотрение формально еще одного потребителя (фиктивного), с объемом потребностей, равным избытку продукции . Тогда формально имеем закрытую транспортную задачу. Все стоимости перевозок ci,n+1 ( ) от каждого поставщика фиктивному потребителю примем равными нулю. Совершенно аналогично можно поступить в случае, когда количество продукции недостаточно для удовлетворения потребностей, т. е. . В этом случае вводится фиктивный поставщик с объемом возможных поставок, равным недостатку продукции . Стоимости перевозок cm+1,j ( ) от фиктивного поставщика ко всем потребителям принимаем также равными нулю. В первом случае значения фиктивных перевозок xi,n+1 в оптимальном плане будут равны объемам продукции, остающимся у соответствующих поставщиков, во втором случае значения xm+1,j в оптимальном плане будут означать количество продукции, недополученной соответствующим потребителем.

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

Рассмотрим закрытую модель транспортной задачи. Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного плана. Для транспортной задачи общее число уравнений равно m + n, а число линейно независимых уравнений равно m + n – 1 (сумма первых m уравнений совпадает с суммой последних n). Общее число переменных xij равно mn, число базисных переменных равно m + n – 1, т. е. числу линейно независимых уравнений. Остальные mn – (m + n – 1) = (m – 1)(n – 1) переменных равны нулю и называются свободными переменными. Таким образом, допустимый план будем называть опорным, если в нем отличны от нуля не более m + n – 1 базисных переменных, а остальные переменные равны нулю.

Решение транспортной задачи удобно записывать в виде таблицы, имеющей вид матрицы, в которой строки соответствуют пунктам отправления, а столбцы – пунктам потребления. Клеткой (i,j) мы будем называть клетку, стоящую в i-й строке и j-м столбце таблицы. Коэффициенты стоимости cij расположены в правом верхнем углу каждой клетки (i,j). Каждая клетка соответствует паре поставщик-потребитель.

Для нахождения исходного опорного решения могут быть использованы различные методы. Рассмотрим некоторые из них.

 







Дата добавления: 2014-11-10; просмотров: 1694. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.019 сек.) русская версия | украинская версия








Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7