Требуется составить план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость

П.1. Общая постановка задачи.

Транспортная задача – одна из распространенных задач линейного программирования. Её цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Всё это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т.д. Под термином «Транспортные задачи» понимается широкий круг задач не только транспортного характера. Наиболее часто встречаются следующие задачи, относящиеся к транспортным:

· прикрепление потребителей ресурса к производителям;

· привязка пунктов отправления к пунктам назначения;

· взаимная привязка грузопотоков прямого и обратного направлений;

· отдельные задачи оптимальной загрузки промышленного оборудования;

· оптимальное распределение объёмов выпуска промышленной продукции между заводами – изготовителями.

В общем виде задачу можно представить следующим образом: в m пунктах производства A₁,A₂,…A_m имеется однородный груз в количестве соответственно a₁,a₂,…a_m. Этот груз необходимо доставить в n пунктов назначения B₁,B₂,…B_n в количестве соответственно b₁,b₂,…b_n. Стоимость перевозки единицы груза (тариф) из пункта A_i в пункт B_j равна C_ij.

В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нём, транспортные задачи могут быть закрытыми и открытыми.

1. Если , то задача называется закрытой.

2. Если , то задача называется открытой. Поэтому, если в исходных условиях дана открытая задача, то её необходимо привести к закрытой форме:

a) если потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

b) если запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

Тарифы, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.

Транспортным задачам присущи следующие особенности:

a) распределению подлежат однородные ресурсы;

b) условия задачи описываются только уравнениями;

c) все переменные выражаются в одинаковых единицах измерения;

d) во всех уравнениях коэффициенты при неизвестных равны единице;

e) каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

1. Нахождение исходного опорного решения;

2. Проверка этого решения на оптимальность;

3. Переход от одного опорного решения к другому.

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

	B1	B2	B3	B4	Запасы
A1	x11^с11	x12^с12	x13 ^с13	x14^с14	a1
A2	x21^с21	x22^с22	x23^с23	x24^с24	a2
A3	x31^с31	x32^с32	x33^с33	x34^с34	a3
Потребности	b1	b2	b3	b4	Σai=Σbj

x_ij – количество груза, которое необходимо перевезти из пункта A_i в пункт B_j. C_ij – тарифы транспортных расходов.

Если m – число пунктов отправления, а n – число пунктов назначения, то уравнений составлено m + n, а переменных – m * n.

Можно также показать, что если одно из уравнений системы лишнее (оно является следствием остальных), то его можно исключить из системы.

Таким образом, в общем случае система транспортной задачи должна иметь m + n – 1 – уравнений с m * n – переменными.

Дата добавления: 2014-11-08