Транспортная задача. 
Характеристика задач линейного программирования

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов производства A1,…, Am, в которых сосредоточены запасы однородных продуктов в количестве a1,…, am единиц. Кроме того имеется n пунктов потребления B1,…, Bn, потребность которых в указанных продуктах составляет b1,…, bn единиц. Известны также транспортные расходы ci, j, связанные с перевозкой единицы продукта из пункта Ai в пункт Bj, i 1,…, m; j 1,…, n. Требуется составить такой план перевозок, чтобы удовлетворить спрос всех пунктов потребления, при минимальной общей стоимости всех перевозок.

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

(11).

Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно не превышать запаса продукта в данном пункте. Формально это означает, что.

(), (12).

Суммарное количество груза, доставляемого в каждый пункт потребления из всех пунктов производства, должно удовлетворять потребности пункта потребления:

(), (13).

Объемы перевозок должны быть неотрицательными числами, так как перевозки из пунктов потребления в пункты производства исключены:

(,), (14).

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

Пример 5. Предприятие имеет три склада со своей продукцией:

Этот товар необходимо перевезти в три магазина, учитывая следующие потребности:

Стоимость перевозок одной единицы продукции определяется следующей таблицей:

Необходимо составить план перевозок так, чтобы стоимость перевозок была минимальной.

Задания.

1. Фирма должна отправить некоторое количество единиц своей продукции с трех складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 единиц продукции, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 единиц продукции. Стоимость перевозки одной единицы продукции со склада в магазин приведены в таблице:

Как следует спланировать перевозку, чтобы ее общая стоимость была минимальной?

2. Организация имеет следующие минимальные потребности в количестве сотрудников в различное время суток:

При этом первый период следует сразу за шестым. Каждый сотрудник работает 12 часов без перерыва. Необходимо составить график рабочего времени таким образом, чтобы, не нарушая сформулированных выше требований, обойтись минимальным числом сотрудников.

3. Фабрика производит два вида лака — для внутренних и наружных работ. Для производства лаков используется два вида исходных продуктов — нефть и кислота.

Максимально возможные суточные запасы этих продуктов определяются емкостями их хранения и равны 6 и 8 тонн (т) соответственно. Для производства 1 т. лака для внутренних работ расходуется 1 т. нефти и 2 т. кислоты, а для производства 1 т. лака для наружных работ расходуется 2 т. нефти и 1 т. кислоты. Суточный спрос на лак для наружных работ не превышает 2 т. Спрос на лак для внутренних работ неограничен.

Доход от реализации 1 т. лака для внутренних работ равен 3 млн. рублей, а доход от реализации 1 т. лака для наружных работ — 2 млн. рублей.

Необходимо определить, какое количество лака каждого вида должна производить фабрика в сутки, чтобы доход от его реализации был максимальным.