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

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

Выполнила:
студентка 4 курса гр.ОАБ-10.03.01-41
Истомина Полина

2. Общие сведения о транспортной задаче

Транспортная
задача,
это
специальный
вид
задачи
линейного
программирования. Для решения транспортной задачи можно использовать
методы решения задач линейного программирования, однако ввиду
специфического вида задачи, были построены алгоритмы специально для
решения этой задачи.
Общая постановка транспортной задачи заключается в определении
оптимального плана перевозок некоторого однородного груза из пунктов
отправления A1, A2,..., Am в пункты назначения B1, B2,..., Bn. Критерий
оптимальности берется минимальная стоимость перевозки или минимальное
время доставки груза.

3. Общие сведения о транспортной задаче

Обычно данные транспортной задачи записывают в виде таблицы:

4. Общая формулировка транспортной задачи

В таблице указаны поставщики А1… , у которых имеется в наличии соответственно
а1… единиц однородного груза. Данный груз должен быть доставлен n
потребителям, в количествах в1… единиц, заданы стоимости сij перевозок груза от
i поставщика j потребителю. Требуется спланировать перевозки(указать, сколько
единиц груза должно быть отправлено от I того поставщика j потребителю, так
чтобы максимально удовлетворить спрос потребителя и чтобы суммарные затрата
на перевозки были при этом минимальными).

5.

Транспортная задача, в которой суммарные запасы и потребности совпадают,
является закрытой.
Для открытой модели изменяется только вид системы ограничений.
Для составления математической модели закрытой транспортной задачи
введем переменные Xij (i - имеется от 1 до m, j – от 1 до n), обозначающие
количество единиц груза, перевозимого от i-го поставщика к j-му
потребителю.
Математическая модель транспортной задачи сводится к минимизации
целевой функции, выражающей суммарные затраты на перевозку всего груза:

6.

7. Особенности ограничений транспортной задачи

Транспортная задача является задачей линейного программирования, и ее можно
решить симплексным методом. Однако специфика ограничений транспортной задачи
позволяет применять для ее решения методы значительно менее громоздкие, чем
симплексный метод. Один из них - метод потенциалов.
Особенности ограничений транспортной задачи следующие:
а) ограничения заданы в виде уравнений;
б) каждая переменная xij встречается только в двух уравнениях;
в) коэффициенты при неизвестных, входящих в уравнение, равны единице (или
нулю, если переменные не входят в уравнение).
г) матрица составленная из коэффициентов при переменных Xij состоит из единиц и
нулей, причем каждый столбец матрицы содержит два элемента равных 1, а
остальные – 0.

8. Пример 1

9.

10.

11. Пример 2

12.

13. Список использованных источников:

https://studopedia.ru/21_47327_sushchnost-transportnoy-zadachi.html
https://vuzlit.ru/2308541/uslovie_razreshimosti_transportnoy_zadachi
https://economy-ru.info/article/38598/
Прикладные задачи математического программирования : учеб. пособие
для втузов рек. МО РФ / А.А. Грешилов. - 2-е изд., доп. - М. : Логос, 2006.
Практикум по исследованию операций/ Зенкевич Н. А., Губар Е. А.: 2007.

14. Спасибо за внимание!