Контрольная работа №2. Тема 4. Транспортная задача

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

Пусть необходимо перевезти некоторый однородный груз от нескольких поставщиков нескольким потребителям.

Поставщики: А₁, А₂, …,А_m

Их запасы: а ₁, а ₂, …, а _m.

Потребители: В₁, В₂, …,В_n

Их потребности: b ₁, b ₂, …, b _n.

Известны тарифы перевозок c _ij – это стоимость перевозки 1 единицы груза от каждого поставщика Аi каждому потребителю Вj: i= 1, 2, …, m; j= 1, 2, …, n.

Обозначим поставки x _ij– это количество груза, перевозимое от поставщика Аiпотребителю Вj. Очевидно, что соблюдается условие не отрицательности: x _ij ≥ 0.

Общая стоимость всех перевозок Z = c_11* x ₁₁ + c_12* x ₁₂ + … + c_mn* x _mn. Нужно найти план перевозок { x _ij}, который обеспечит минимальные общие затраты на перевозки: Z " min.

Пусть суммарные запасы поставщиковравны суммарным потребностям потребителей∑ а _i = ∑ b _j. В этом случае транспортная задача называется закрытой. Транспортная задача называется открытой, если нарушено условие баланса между суммарными запасами груза и суммарными потребностями, то есть ∑ а _i≠∑ b _j. Открытую транспортную задачу всегда легко привести к закрытой задаче путём введения фиктивного поставщика или фиктивного потребителя с недостающим количеством груза и нулевыми тарифами.

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

Данные задачи и её решение удобно располагать в таблице перевозок.

Задача 31–40. Три склада обслуживают пять магазинов одинаковым товаром. Первый склад располагает a 1, второй a 2, третий a 3 единицами товара. Каждому из пяти магазинов требуется по плану соответственно b 1, b 2, b 3, b 4, b 5 единиц товара. Известны тарифы всех перевозок, заданные матрицей тарифов С.

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

2) Составить план перевозок по методу минимального тарифа и проверить является ли он опорным.

2) Найти общую стоимость перевозок для этого плана.

3) Проверить является ли составленный план оптимальным, пользуясь методом потенциалов.

4) Составить математическую модель для данной транспортной задачи.

a 1 =110, a 2 =190, a 3 =160;

b 1 =120, b 2 = 100, b 3 =80, b 4 =70, b 5 =90.

С =

Дата добавления: 2015-08-31