Транспортная задача
Математическая модель задачи
Линейные транспортные задачи составляют особый класс задач линейного программирования.
Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат.
Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы kСij.
Далее, предполагается, что
где ai есть количество продукции, находящееся на складе i, и bj – потребность потребителя >j. Такая транспортная задача называется закрытой. Однако, если данное равенство не выполняется, то получаем открытую транспортную задачу, которая сводится к закрытой по следующим правилам:
- Если сумма запасов в пунктах отправления превышает сумму поданных заявок
то количество продукции, равное 
остается на складах. В этом случае мы введем "фиктивного" потребителя n+1 с потребностью 
и положим транспортные расходы pi,n+1 равными 0 для всех i. - Если сумма поданных заявок превышает наличные запасы
то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m+1 с запасом 
и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.
Математическая модель транспортной задачи имеет вид:
где xij количество продукции, поставляемое со склада i потребителю j, а Сij издержки (стоимость перевозок со склада i потребителю j).
Рассмотрим пример:
ПРИМЕР. Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации , проводящие строительные работы на разных объектах этого же региона дали заказ на поставку соответственно 300, 600, 650 и 750 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:
| Содержание в 1 кг. |
Комбикорм
|
|
А
|
В
|
С
|
|
| Жиры |
320
|
240
|
300
|
| Белки |
170
|
130
|
110
|
| Углеводы |
380
|
440
|
450
|
| Стоимость 1 кг |
31
|
23
|
20
|
Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными.
Данная транспортная задача является закрытой, так как запасы поставщиков 800+900+600=2300 равны спросу потребителей 300+600+650+750=2300. Математическая модель ЗЛП в данном случае имеет вид:
- количество щебенки, перевозимой с i–го карьера на j–й объект. Тогда целевая функция равна
Ограничения имеют вид
